5 simple steps to create an abstract data type in C
For many software developers, object-oriented programming is a great tool. Unfortunately, embedded software engineers stuck using the procedural C programming language lose out on many modern programming language features. Abstract data types (often written ADT for short) are data types whose implementation details are hidden from user view for the data structure, but ADTs can be developed in C using five simple steps.
Step #1 – Define the abstract data type
The ADT in C is usually defined as a pointer to a structure. A header file contains the ADT declaration without any of the underlying details, leaving it up to the implementer to fully declare the ADT in the source module. Examples of ADTs include a StackPtr_t, NodePtr_t or QueuePtr_t to name a few. The example below shows how a developer might declare an ADT:
- typedef struct StackStruct_t * StackPtr_t;
The declaration would go in the stack.h file, allowing the module's user to make use of StackPtr_t, which is a pointer to StackStruct_t. The details of StackStruct_t's members are completely hidden from the users’ perspective. Any interaction with StackPtr_t must be done using predefined operations.
Step #2 – Define the operations that can be performed on the data
The operations that may be performed on an ADT completely depend on the ADT's purpose. For example, an ADT for a stack might include operations such as initialization, pushing data, popping data, destroying the stack, checking to see if the stack is full, checking to see if the stack is empty, and so on. Keep in mind that using an ADT is quite different from the way in which a developer would normally manipulate data. Typically, a developer would define the data and write code that directly manipulates the data. With an abstract data type, developers create an interface where the data is indirectly modified behind the scenes.
Step #3 – Fill in the interface specification
The interface specification is the function prototype for all of the public operations that can be performed on the ADT. The interface specification should be located in the ADT header file. Going back to the stack example, a developer might find that the interface specification looks something like the following:
Step #4 – Create the implementation
The ADT's implementation could change from one application to the next. In fact, the ADT implementation could change during project development. That is one of the nice aspects of using an ADT: the implementation details are located in the source module and “hidden” from view of the higher level application developer. The use of an ADT thus provides a developer with a high degree of flexibility. An example of what portions of the stack implementation might look like can be found below:
Step #5 – Put the abstract data type to the test
Finally, once a developer has specified and implemented an ADT it is time to put it to the test by writing some application code. The application code should declare an ADT and then manipulate the data's contents through by using the interface specification. An example of initializing the ADT and interacting with its data can be seen below:
An ADT in C is usually broken up into three distinct pieces: the application, the specification, and the implementation. The purpose of the ADT is to hide the implementation details of a data structure, thus improving software maintenance, reuse and portability. Developers who use ADTs will find that they are able to quickly adapt to changing requirements and save time by not having to dig through code searching for obscure data references.
Developers interested in the Stack example source can download it here.
Jacob Beningo is principal consultant at Beningo Engineering, an embedded software consulting company. Jacob has experience developing, reviewing and critiquing drivers, frameworks and application code for companies requiring robust and scalable firmware. Jacob is actively involved in improving the general understanding of embedded software development through workshops, webinars and blogging. Feel free to contact him at firstname.lastname@example.org, at his website www.beningo.com, and sign-up for his monthly Embedded Bytes Newsletter here.