NOTE: After performing a blog import WordPress messed my code . If you see any problems please let  me know .

In order to prove that generic programming (the style of computer programming in which algorithms are written in terms of to-be-specified-later types that are theninstantiated when needed for specific types provided as parameters) can be achieved in C, let’s write the implementation of a generic Stack data structure . We will follow two possible approaches:

  • Hacking with the #preprocessor;
  • Using the flexibility of the void pointer (void*);

You can always try both of the approaches and see which one is more suitable for your particular case . Also note that there are already generic C libraries available (see GLib ).

1. Hacking with the preprocessor

To understand the magic (not really) behind this approach you will need to be familiar with C macros and the associated concepts: function-like macros, macro arguments, stringification and concatenation. You can find a very nice tutorial on macros here. If you already know your stuff, you can skip the following paragraphs (or you can read them to refresh your memory / find errors and correct me :P). [press here if you want to skip]

What is a macro ?
A macro is a piece of code that was labeled with a name. Whenever the preprocessor encounters it, the label is replaced by the associated code. Basically there are two kinds of macros : object-like macros (resemble data objects when used) and function-like macros (resemble function calls).

Example for object-like macros:

In the above example the label is HELLO and the associated data is “Hello World Macro! . Before compile-time the preprocessor will replace the label with the associated code. I think the results are pretty obvious.

Example for function-like macros:

In the case above MAX works exactly as a function that receives two arguments a, b and returns the maximum of the two . Note that the arguments are generic and appear to be typeless, the preprocessor is not performing any validation on types (that’s the compiler job) –  this an advantage and also a disadvantage, we will why in the future examples.

If we want to expand the above macro (see with the eyes of the compiler :p) you can use the -E switch with gcc (assuming you are using gcc) . You can also write your code by using an IDE, for example Netbeans with C/C++ plugin offer two views: one for normal code , and another with the code already expanded .

After the macro is expanded (replaced with the associated code) the sample above will look similar to this:

Note that the notion of macro will be unknown for the compiler, as the code has been already replaced: ((1) > (3)) ? (1) : (3)

Now let’s focus on a more important aspect: macro concatenation. How do we proceed when we want to merge two tokens into one while expanding macros ? The “##” preprocessing operator performs token pasting .

Example for macro-concatenation:

As you can see we supplied the token arguments (not strings!) errorinfo to the SHOW macro. The tokens were concatenated with show_ and the resulting two tokens were actually real functions: show_error and show_info . Probably the above example is not the best (officially we shouldn’t abuse macros) but it describes the concept of macro concatenation.

Now let’s build the generic STACK using the bliss of the preprocessor in its most abusive form.

Step 1 – Declaring the data structure and the associated functions (pop & push)

OK it looks like a mess… Still if you analyze the example a little you will see that this macro expands in an intelligent way. Depending on the type supplied as the argument, different code will be generated.

“” is saying the  macro is spawning over more than one row. And yes, a macro can be associated with huge blocks of code (function declarations, function definititions, etc.).

Different types, different code …

Step 2 – Defining the STACK functions (push, pop) declared in the previous step:

We will use the same strategy from Step 1, except this time we will actually define the previous declared functions .

And the expansion:

Step 3 – Wrapping generic functions into macros

Step 4 – Putting all togheter

Now let’s build an example against the newly built generic data structure. We will use two different stacks: one that holds doubles, and another that holds only integers. Then we will push / pop the numbers from [1..100] :

Major drawback for this strategy:

The type argument cannot contain “*” or spaces. For instance you cannot STACK_DECLARE(char*), you will have to typedef char*.

2. Using the void pointer (void*)

(when talking about void pointers I was inspired by this article)

Typecasting is one of the powerful features of C. Type casting represents the ability to convert between different type variables.

Not let’s focus on pointers: there are pointers of type int, char, or float, however there’s a certain pointer that doesn’t have a type, and can be used to represent pointers of any type – this is known as the void pointer. Any type of pointer can be cast to a void pointer, and conversely, any void pointer can be cast to a pointer of a type .

A good use for void pointers is when it’s not important what type of data we have. If we only need a block of data, and have no need of knowing what kind of data it is, we can simply use a void pointer. This helps us avoid using separate functions to handle separate types of data.

That’s brilliant, why don’t we write a struct, where one the members is (void*).

The next step wold be now to declare & define the functions involved in the stack manipulation : push and pop . Their signatures could look like this:

As you can see we will use void* to handle data in a generic way. Our stack will be generic, meaning that will be able to hold any type of pointers. Still we will have to cast every-time we will pass the pointer as the argument . (no we don’t, at least we are not doing that explicitly).

The next step we will be to actually write the functions bodies:

And an example of how to use the newly created stack.

And putting all togheter in a working example:

🙂

Legend
1And I love it .

11 thoughts on “Generic data structures in C

  1. Hi, two remarks about your last example:

    (1) Casting pointers from/to ‘void *’ is not needed in C. (On lines 52 and 58).

    (2) Unlike ‘sizeof (type)’, ‘sizeof object’ doesn’t need parentheses around the operand.

    Reply
  2. @schot,
    Regarding (1) , yes you are right there is not need for explicit casting from/to void* . I’ve re-edited the code and the article.
    Regarding (2) , I prefer to use parentheses, probably it’s a matter of style.

    Thanks for your comment (you are actually the first commenter here on the blog).

    Reply
  3. This is a great article. It makes even a newbie can understand and apply the method in his or her code. Thanks you for sharing the idea as well as the examples.

    Reply
  4. I tested the code that uses macro. It runs smoothly. But I think the last two lines of freeing st & st2 before return is not nessecary.
    The two variables are already NULL when every element is poped out.

    free(st);
    free(st2);

    Reply
  5. Pingback: Implementing a Priority Queue in C using a Max-Heap « andreINC.net

  6. Nice article 🙂 How would you implement the top(stack) operation using generic data types (also known as peek(stack) )?. I think that would be a rather useful article too 🙂

    Reply
  7. Pingback: Functions As Arguments | Jatin Parekh

Leave a reply

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url=""> 

required

Are we human, or are we dancer *