C generic programming

Question

First of all, I am a beginner programmer (still much to learn). In one of my small school projects I have written a stack for a struct . Now I have a slightly different struct and I need a stack for this one too. Should I write another data structure [stack] (very similar to the initial one), or try to achieve some generic programming...

Do you know any good generic programming strategies (online resources eventually) in C ? I've used google, but I haven't found nothing satisfactory, as most of the results are about C++ strategies.

Thanks!

LATER EDIT: After some reading, and experiencing, eventually I've found two solutions for my problem. I've documented them here: http://andreinc.net/2010/09/30/generic-data-structures-in-c/ . That article may contain errors or inexactitudes, still it summarize what I know so far.

Answer 1

C is a pretty low-level programming language giving you only a little abstraction over the machine the code runs on but nearly nothing in abstraction from a language point of view. C++ has templates for generic programming but in C you don't have something similar.

The best thing you could do is write your data structures to always use void* and leave every allocation/deallocation/casting to the caller. It's messy and error-prone, though.

Answer 2

I don't do a lot of C hacking, but I think the way to go with this is void*.

So, just rewrite your stack of push/pop void* instead of some_struct*. It becomes your problem to keep the types correct, but that's just a price you pay for using such a low-level* programming language.

_{*Not to imply that this is a bad thing.}

Answer 3

For production code, I generally prefer C++. Even if you don't plan to go all out with OO, generics and metaprogramming, you can use C++ as a better C (in this case, just to get std::stack for free).

If you have to use C, try to keep it simple and make pragmatic choices based on your particular circumstance. For instance, if you know for sure that your stack is bounded to some small limit and the data you're holding is simple, then your stack code could be as simple as stack[tos++] = x; and return stack[--tos] without needing a reusable library. The answers suggesting a library based on void* are also appropriate under different circumstances. C++'s std::stack pretty much solves this problem once and for all; C doesn't quite give you that luxury.

Answer 4

I put an example here of generic programming in C. Although its not a data structure algorithm, a sort though, it can give you some clues about this subject. I hope it can help you.

The algorithm below is an generic implementation of the bubble sort algorithm. I'm using void pointers and cast the data to work at byte level. Also I use an external comparison function that is the only code that knows the type of the data being sorted. This comparison function is passed as a parameter to the sort algorithm.

Another important point is that the main algorithm needs to know the size in bytes of the data being manipulated in order to know how many bytes are necessary to move this data to a new position in the array. It also creates a buffer to store one instance of this data (k variable in the bubleSort function).

    static int compare(void *menor, void *maior)
    {
       int *pMenor = (int *)menor;
       int *pMaior = (int *)maior;

       return ( *pMenor > *pMaior );
    }

    void bubleSort(void *base, int bWidth, int len, int (*func)(void *key, void *data))
    {
       int i, j;
       char *k=0;
       char *bPtr = (char *)base;         //Points to the beginning of the array 
       char *pi, *pj;

       k = (char *)malloc(bWidth);        //Creates a new var with the size of the data type

       if(!k)
          return;

       for(i = 0; i < len; i++)
       {
          pi = (bPtr + (i*bWidth));

          for(j=i+1; j < len; j++)
          {
             pj = (bPtr+(j*bWidth));

             if( func((void *)pi, (void *)pj) )
             {
                memcpy(k, pi, bWidth);
                memcpy(pi,pj, bWidth);
                memcpy(pj, k, bWidth);
             }
          }
       }

       free(k);
    }

int main()
{
   int vet[5] = {4, 1, 3, 5, 2};
   bubleSort((void *)vet, sizeof(int), 5, compare);

   return 0;
}

Answer 5

Finding commonalities and creating abstractions is one of the most valuable skills for a programmer. As you're still learning, I'd suggest you do the following things:

(1) Implement the stack for that other struct. Yes, it's double work, but at your stage every working program counts. Builds up experience.

(2) Compare the programs. What are the parts they have in common? What are the parts that differ? Your goal is to separate the parts that are common from the parts that are different. What are the means that these two groups use to communicate? The parts that they have in common go into one part of your system (stack.h/stack.c), the parts that are different go into their own files (account.h/c, person.h/c, etc.). And the part where you combine them should do an include of stack.h and the parameterizing entity.

(3) Try to find all possible ways you know that the language offers that you can use to implement the abstract struct functionality. At first it always seems as if there is only one way, but for every non-trivial problem there are alsway several approaches. In the stack case, using standard C, for example, zou can use void pointers, you can use preprocessor macros, you should look into token pasting, you can use function pointers plus struct pointers, etc.

(4) Implement as many of them as possible. Again, this is for the learning experience. C has so many traps, and the earlier you run into them, the better.

(5) After you have enumerated and implemented all these different approaches, you should evaluate them: Which one was easiest to use? Which one was easiest to implement? Which one is fastest? Which one is easiest to debug?

Answer 6

I believe that abstraction is mostly in the eye of the programmer. A great programmer can see the pattern in simple statements, even in a low level language as C. Languages and their syntax can surely help but how statements and expressions are finally written are somewhat what differentiate good programmers from bad ones. That said, how do this help you? Well, my point is to become familiar with the constructs in C so you know them when you see them, and the void* as Kevin Montrose mention is a common one. Strategies I think are good is to think about stdlib, how has things been solved there? and reflect in great code when you see some. Ie a common pattern in stdlib is to have zero (0) to represent OK. Or reflect on how well a filedescriptor work with all the read, write etc functions regardless its origin (socket, file, pipe etc). This SO question (link) has some good links to great code to read.

Picture from Thinking Forth, a great old programming book regardless of language.

Answer 7

While much of the advice here is stellar (I urge you to try a lot of different methods to gain experience), I recommend using C++. Use the stack template, to create the implementation, then use extern "C" to create a set of set of C api functions to use it.

you would need a

  o constructor to create the object
  o a destructor to destroy the object
  o a push function
  o a pop function
  o an "is_empty" function.

The last 3 functions would take a pointer to the object as their first (void *) parameter. Inside the function that pointer would be typecast to the stack object type, then used in normal c++ fashion.

Trying that implementation would put another arrow in your quiver, so you could hunt bigger game.