A generic/polymorphic stack implementation in plain C

This is a discussion on A generic/polymorphic stack implementation in plain C within the C Programming forums, part of the General Programming Boards category; I rather enjoy generic data structures in object oriented languages. After programming in an object oriented language for a while ...

  1. #1
    Registered User \007's Avatar
    Join Date
    Dec 2010
    Posts
    179

    A generic/polymorphic stack implementation in plain C

    I rather enjoy generic data structures in object oriented languages. After programming in an object oriented language for a while I decided to re-fresh some of my C skills by attempting to implement a generic stack in C.

    Do you think you could achieve type safety within a generic data structure in C (without pre-processing commands or compiler specific checks like GCC's typeof() etc. ?). How would you implement a generic data structure such as a stack in C?

    I toyed around for a little while and whipped up some code. Valgrind shows no memory loss so I think it's safe. I can't be quite sure though. I haven't done a lot of testing with it and it is by no means perfect. It doesn't guarantee any type safety and error handling is very basic since I was messing around. Not to mention the biggest annoyance is it doesn't support literals.

    Do you think such constructs would be useful in plain C? or, does the type safety of a type specific data structure appeal more to you?

    This is a pretty interesting topic and fun to mess around with. The Linux kernel code has some generic data structures done up using some pretty complex pre-processor commands and compiler tricks. It's pretty amazing what you can do~

    cstacks.h

    Code:
    #ifndef CSTACKS_H_
    #define CSTACKS_H_
    
    #include <stdio.h>
    #include <stdlib.h>  /* malloc */
    #include <strings.h> /* bcopy  */
    
    typedef struct Stack Stack;
    struct Stack{
      int counter;
      int max;
      void** container;
    };
    
    /***
    * newStack - allocates space and sets up stack
    * @size: the desired default container size (5 minimum)
    *
    **/
    Stack* newStack(int size);
    
    /***
    * freeStack - frees container and stack memory
    * @stack: target stack
    *
    **/
    void freeStack(Stack* stack);
    
    /***
    * getSize - returns current stack counter position
    * @stack: target stack
    *
    **/
    int getSize(Stack* stack);
    
    /***
    * getMax - returns the current max stack size
    * @stack: target stack
    *
    **/
    int getMax(Stack* stack);
    
    /***
    * isEmpty - returns 1 if stack is empty, 0 if not
    * @stack: target stack
    *
    **/
    int isEmpty(Stack* stack);
    
    /***
    * resizeContainer - expands container to 2*max
    * @stack: target stack
    *
    **/
    void** resizeContainer(Stack* stack);
    
    /***
    * trace - prints the current stack layout
    * @stack: target stack
    *
    **/
    void trace(Stack* stack);
    
    /***
    * search - searches for value in stack and returns index of the found value
    *          or returns -1 if not found.
    * @value: target value
    * @stack: target stack
    *
    **/
    int search(void* value, Stack* stack);
    
    /***
    * peek - returns top of the stack without removing it
    * @stack: target stack
    *
    **/
    void* peek(Stack* stack);
    
    /***
    * push - pushes an item onto a stack
    * @item: target item
    * @stack: target stack
    *
    **/
    void push(void* item, Stack* stack);
    
    /***
    * pop - pops an item off the top of the target stack
    * @stack: target stack
    *
    **/
    void* pop(Stack* stack);
    
    #endif /* CSTACKS_H_ */
    cstacks.c

    Code:
    #include "cstacks.h"
    
    Stack* newStack(int size){
      /* NYI: better error checks */
      if (size < 5){
        size = 5;
      }
    
      Stack* stack = malloc(sizeof(Stack));
      stack->container = malloc(sizeof(void**) * size);
    
      stack->counter = 0;
      stack->max = size;
      return stack;
    }
    
    void freeStack(Stack* stack){
      free(stack->container);
      free(stack);
    }
    
    int getSize(Stack* stack){
      return stack->counter;
    }
    
    int getMax(Stack* stack){
      return stack->max;
    }
    
    int isEmpty(Stack* stack){
      if(stack->counter == 0)
        return 1;
      return 0;
    }
    
    void** resizeContainer(Stack* stack){
      /* NYI: error checks */
      void** tmpContainer = malloc(sizeof(void**) * stack->max * 2);
      bcopy(stack->container, tmpContainer, sizeof(void**)*stack->max);
      stack->max *= 2;
      return tmpContainer;
    }
    
    void trace(Stack* stack){
      int i;
      for(i = stack->counter - 1; i >= 0; i--)
        printf("%d: %p \n", i, stack->container[i]);
    }
    
    int search(void* value, Stack* stack){
      int i;
      for(i = stack->counter - 1; i >= 0; i--){
        if(stack->container[i] == value)
          return i;
      }
      return -1;
    }
    
    void* peek(Stack* stack){
      if (stack->counter > 0){
        return stack->container[stack->counter - 1];
      }
      fprintf(stderr, "stack counter is 0... can't peek an empty stack.");
      return NULL;
    }
    
    void push(void* item, Stack* stack){
      if (stack->counter == stack->max)
        stack->container = resizeContainer(stack);
    
      stack->container[stack->counter] = item;
      stack->counter++;
    }
    
    void* pop(Stack* stack){
      if (stack->counter > 0){
        stack->counter--;
        return stack->container[stack->counter];
      }
      fprintf(stderr, "stack counter is 0... can't pop an empty stack.");
      return NULL;
    }
    basictesting.c

    Code:
    #include <stdio.h>
    #include "cstacks.h"
    
    int main(void) {
    	Stack* intStack = newStack(10);
    
    	int x = 100, y = 200, z = 300;
    
    	if(isEmpty(intStack)){
    		printf("The stack is empty.\n");
    	} else {
    		printf("The stack is not empty.\n");
    	}
    
    	push(&x, intStack);
    	push(&y, intStack);
    	push(&z, intStack);
    
    	if(isEmpty(intStack)){
    		printf("The stack is empty.\n");
    	} else {
    		printf("The stack is not empty.\n");
    	}
    
    	trace(intStack);
    
    	printf("\nPopping %d\n", *(int*)pop(intStack));
    	printf("\nPopping %d\n", *(int*)pop(intStack));
    	printf("\nPopping %d\n", *(int*)pop(intStack));
    
    	Stack* stringStack = newStack(4);
    
    	char* hello = "Hello world!";
    	char* goodbye = "Goodbye cruel world!";
    	push(hello, stringStack);
    	push(goodbye, stringStack);
    	printf("We popped: %s\n", (char*)pop(stringStack));
    	printf("We popped: %s\n", (char*)pop(stringStack));
    
    
    	freeStack(intStack);
    	freeStack(stringStack);
    	return 0;
    }
    Thanks for any code or post comments~

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by \007 View Post
    Do you think you could achieve type safety within a generic data structure in C (without pre-processing commands or compiler specific checks like GCC's typeof() etc. ?). How would you implement a generic data structure such as a stack in C?
    C is a weakly typed language so type security as such isn't a big deal but natural alignment of each type is.
    Wondering what applications are you thinking of with such a data structure, besides the obvious rpn calc.

  3. #3
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,682
    Quote Originally Posted by \007
    How would you implement a generic data structure such as a stack in C?
    Making function more generic would be quite tough in C. In the sense that you would have to send the size of the variable your sending to the function. Like for example

    Code:
    int pop( void *head, size_t s )
    {   ...   }
    Which would then be used tpo typecast the void pointer to assign scalar value right, when performing the pointer arithmatic right.

    ssharish
    Life is like riding a bicycle. To keep your balance you must keep moving - Einstein

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,325
    I haven't used a generic stack too often (though I don't write many RPN calculators these days), but I certainly have used generic queues, lists, trees and hash tables (GLib has a nice set I've used often). I haven't had too much need for type safety, but When you're stuck using C (e.g. working in a legacy system), I think there's a great use for them, since rewriting everything in C++ or Java is not an option. If you need this feature in a new project, I would go straight for some OO language.

    Depending on how you want to set up your type system in C, you can achieve a degree of type safety. One method I've used I borrowed from the PostgreSQL source. There is a "base object" struct that contains a type ID (you can add other stuff if you want). That base object is the first element of every object/struct in your type system, an enum list of type IDs, and some macros to do some allocating and token gluing. Creating/initializing a variable of that type sets the type ID field. Pass in the type you want (e.g. T_int) to your newStack function, and make sure the object you pass in to push is of the right type for that stack before allowing the push to succeed. Mix in some of the inheritance and polymorphism tricks here, and you can have a pretty sexy framework, even if it is a nightmare to debug.

    I find this stuff fascinating too, and it makes for a great academic exercise. You can learn a lot about what's under the hood of an OO language like C++. But out in the real world, the time to create such a framework, and the complexity and maintenance issues it creates often isn't worth it. I usually find it quicker/easier to write a set of wrappers around a generic data structure that enforce type correctness. The data structure itself is completely type agnostic, the wrappers are type safe. At most you need a tiny struct to wrap up your generic data structure for total type safety.

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by \007 View Post
    Do you think such constructs would be useful in plain C? or, does the type safety of a type specific data structure appeal more to you?
    I'm going to say no to both questions. I do not find excessively generic data structures useful in C, nor does something more type specific appeal to me more because of type safety.

    Something more type specific appeals to me more not because of safety, but because it will almost certainly perform better, is always easier to use, and is more likely to be tailored to a specific purpose (as opposed to trying to be all things to all people, for all purposes).

    C could easily have widely used generic libraries for stuff like LIFO stacks, trees, and what have you, the same way that C++ has Boost and other languages have similar popular repositories for modules that are/could be written in the language itself (as opposed to providing functionality that the base language cannot provide, which is what C does have common, standardized libs for).

    So why doesn't it? After all, it is still one of the most widely used programming languages in the world. But obviously the community has never got excited enough about the possibility.

    For most purposes, to write a non-generic, type specific stack does not take very long. Probably less time than it would take me to learn how to use your generic module, which again, will not perform as well, and will by nature be more awkward than something more customized.

    I love interpreted OO languages, but C is not the same thing and generally people do not use it for the same purposes. If your goal is easy, don't use C. There is no reason to do so, esp. considering the existence of other languages. But if you want something really slick and streamlined, that's what C is for. Which probably precludes the use of complex super-generic data structures, because it includes the use of very specific, tailor made structures.

    Programming data structures is a very useful exercise in C but IMO generisizing them is mostly a waste of time. I've done it too but I almost never end up using the code again as written -- I'll just refer to it WRT form and principles.
    Last edited by MK27; 06-30-2011 at 03:32 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    Registered User \007's Avatar
    Join Date
    Dec 2010
    Posts
    179

    Talking thanks

    Thanks-- lots of great replies.

    I also think C isn't a great choice for data types like this-- and I am not entirely sure how useful they would be.

    I also believe if you need structures like this it's probably a good idea to head over to an object oriented language if it is possible.

    It is still fun as heck to mess around with them though~! I also agree it's a good way to learn the ins and outs of how object oriented languages work. Heck-- as someone mentioned building data structures from scratch is an excellent exercise in any language.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Stack Implementation and Exceptions
    By audinue in forum C Programming
    Replies: 4
    Last Post: 06-22-2008, 09:32 AM
  2. code review request: stack implementation
    By cs32 in forum C Programming
    Replies: 6
    Last Post: 02-24-2008, 01:26 PM
  3. plain pong
    By lambs4 in forum Game Programming
    Replies: 16
    Last Post: 10-10-2004, 01:49 PM
  4. stack implementation problem-help needed
    By sanju in forum C Programming
    Replies: 1
    Last Post: 12-10-2002, 06:29 AM
  5. Plain Window!
    By Shakespeare in forum Windows Programming
    Replies: 1
    Last Post: 01-20-2002, 11:35 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21