How to create abstract data type in C

Object-oriented programming is a great tool for many software developers. 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 initialisation, 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:

Conclusion
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.

About the author
Jacob Beningo is a Certified Software Development Professional (CSDP) whose expertise is in embedded software. He works with companies to decrease costs and time to market while maintaining a quality and robust product.