C data structures

This is a discussion on C data structures within the C Programming forums, part of the General Programming Boards category; I find I have to implement every single data structure myself, If i need a queue of struct a I ...

  1. #1
    Registered User
    Join Date
    Aug 2005
    Posts
    266

    C data structures

    I find I have to implement every single data structure myself, If i need a queue of struct a I go ahead and implement it .. now I need a queue of struct b .. I reimplement it again with a different struct now?

    There are no templates like in C++ or generics like in java, so I thought maybe it might be possible with the 'void pointer' , which people say can hold any type...

    Is this how data structures are usually implemented in C? using void pointers to be able to hold any type? Or is there something I am not seeing?

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,494
    If you're trying to make any kind of generic software, then yes, void* is pretty much essential at some point.


    Another approach is to have something like pre-processor abuse (note, this gets ugly in a hurry).
    Code:
    #ifndef LIST_H
    #define LIST_H
    
    #define XLISTNAME(x,y)  x ## y
    #define LISTNAME(x,y)   XLISTNAME(x,y)
    
    #endif
    
    #ifdef LIST_TYPE
    struct LISTNAME(ListOf_,LIST_TYPE) {
        LIST_TYPE   var;
        struct LISTNAME(ListOf_,LIST_TYPE)  *prev;
        struct LISTNAME(ListOf_,LIST_TYPE)  *next;
    };
    
    void LISTNAME(initListOf_,LIST_TYPE) ( struct LISTNAME(ListOf_,LIST_TYPE) *p, LIST_TYPE *data ) {
        p->next = NULL;
        p->prev = NULL;
        p->var = *data;
    }
    #else
    #error LIST_TYPE is undefined
    #endif
    
    #undef LIST_TYPE
    Which used as follows
    Code:
    #define LIST_TYPE   int
    #include "list.h"
    #define LIST_TYPE   double
    #include "list.h"
    
    int main()
    {
        return 0;
    }
    causes the pre-processor to generate two structs and two functions...
    Code:
    # 1 "list.h" 1
    # 10 "list.h"
    struct ListOf_int {
        int var;
        struct ListOf_int *prev;
        struct ListOf_int *next;
    };
    
    void initListOf_int ( struct ListOf_int *p, int *data ) {
        p->next = NULL;
        p->prev = NULL;
        p->var = *data;
    }
    # 3 "foo.c" 2
    
    # 1 "list.h" 1
    # 10 "list.h"
    struct ListOf_double {
        double var;
        struct ListOf_double *prev;
        struct ListOf_double *next;
    };
    
    void initListOf_double ( struct ListOf_double *p, double *data ) {
        p->next = NULL;
        p->prev = NULL;
        p->var = *data;
    }
    # 5 "foo.c" 2
    
    int main()
    {
        return 0;
    }
    We now have instantiated rudimentary lists of ints and doubles.


    Expanding the header file into a feature-complete list implementation is an exercise for the reader
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,667
    download a third-party implementation of whatever-it-is to use and to learn.

    Your representation of the queue structure proper should be consistent. An array of type foo could be as much of a queue as an array of type bar.

    The real work of it is breaking C's strict typing just right. I've seen libraries that make extensive use of void*; or, forced you to implement a named internal structure like struct impl; or, pretend that unions will help in the long term; and even seen some pretty macro magic done. In general, I think implementing a named structure is too restrictive (<= 1 type of data structure foo in program bar, but reusable!). I also think that void* implementations quickly become unruly because you might try to merge two queues of different, underlying types or some such thing. C macros are even more unruly but at least users won't touch them. One macro-related example even caught some type errors at compile time, though.

    None of the choices are easily made because none of them are like C++ templates.

  4. #4
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    I like your solution salem!

    anyone have any idea why I get the following compile error?
    cutter_queue.h:16: error: expected ‘)’ before ‘*’ token
    cutter_queue.h:29: error: expected ‘)’ before ‘*’ token
    cutter_queue.h:42: error: expected ‘)’ before ‘*’ token
    Code:
    #ifndef CUTTER_QUEUE_H
    #define CUTTER_QUEUE_H
    
    #define QUEUENAME(x,y) x##_##y
    
    #endif
    
    #if  defined (QUEUE_TYPE) && defined (QUEUE_IDENTIFIER)
    struct QUEUENAME(QUEUE_IDENTIFIER,queue)
    {
    	QUEUE_TYPE * data;
    	int size;
    	int num_elem;
    };
    
    inline void enqueue( QUEUENAME(QUEUE_IDENTIFIER,queue) * q, QUEUE_TYPE p)
    {
    	/*
    		I have this queue putting new items at the end of the array, and popping from the front.
    	*/
    	if(q->num_elem == q->size)
    	{
    		q->size = ( q->data == NULL ? 32 : q->size*2 );
    		q->data = realloc( q->data, q->size*sizeof(QUEUE_TYPE));
    	}
    	q->data[q->num_elem++] = p;
    }
    
    inline QUEUE_TYPE pop( QUEUENAME(QUEUE_IDENTIFIER,queue) * q)
    {
    	assert( q->data != NULL );
    	QUEUE_TYPE r = q->data[0];
    	int i;
    	for(i=0;i<q->num_elem-1;++i)
    	{
    		q->data[i] = q->data[i+1];
    	}
    	q->num_elem -= 1;
    	return r;
    }
    
    inline char empty( QUEUENAME(QUEUE_IDENTIFIER,queue) * q )
    {
    	return (q->num_elem == 0 ? 1 : 0);
    }
    
    #else
    #error QUEUE_TYPE or QUEUE_IDENTIFIER is undefined
    #endif
    
    #undef QUEUE_TYPE
    #undef QUEUE_IDENTIFIER
    heres how I define type and identifier in the main file
    Code:
    #define QUEUE_TYPE struct pixel
    #define QUEUE_IDENTIFIER pixel
    #include "cutter_queue.h"
    Last edited by rodrigorules; 05-16-2010 at 01:06 PM.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Your struct is called "struct pixel_queue" after pre-processing, but the enqueue function tries to declare a variable of type "pixel_queue *" instead.

    (Well, at least I hope so. When I did the -E switch in gcc, I got "struct QUEUE_IDENTIFIER_queue" and "QUEUE_IDENTIFIER_queue *", but I may not have copied everything down right.) (Also, the word "queue" looks really bizarre now that I've typed it many many times.)
    Last edited by tabstop; 05-16-2010 at 05:03 PM.

  6. #6
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    yep just noticed the bug minutes before you posted

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by Salem View Post
    If you're trying to make any kind of generic software, then yes, void* is pretty much essential at some point.
    You can also embed a node/struct in another struct and use a macro like this

    Code:
    #define OFFSETOF(type,member) ((long) &((type*)0)->member)
    to find the outer struct, which means the outer struct could be anything, and you don't need to use either void* or the bloat of templates, so the code is good for C and C++.

    But I won't push this point on the OP.
    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

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by MK27 View Post
    You can also embed a node/struct in another struct and use a macro like this

    Code:
    #define OFFSETOF(type,member) ((long) &((type*)0)->member)
    to find the outer struct, which means the outer struct could be anything, and you don't need to use either void* or the bloat of templates, so the code is good for C and C++.

    But I won't push this point on the OP.
    1. Is this supposed to be different than the offsetof macro that's already in C and C++ (in stddef)?
    2. I think I vaguely see what you mean here, but I'm going to have to think about it more carefully.

  9. #9
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    Anyway now that I got the queue to work using the preprocessor method , I was wondering if theres any advantage in performance to doing it this way usually opposed to having an array of void * , since every time I want to access the data I would have to cast it back to a struct.. which would mean over 300,000 casts in my case.

    Or is a cast not really time-intensive as I think it is? or at all?

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Casts are for type-checking (or abuses thereof); there's no run-time action that happens.

  11. #11
    Registered User claudiu's Avatar
    Join Date
    Feb 2010
    Location
    London, United Kingdom
    Posts
    2,094
    Quote Originally Posted by rodrigorules View Post
    Anyway now that I got the queue to work using the preprocessor method , I was wondering if theres any advantage in performance to doing it this way usually opposed to having an array of void * , since every time I want to access the data I would have to cast it back to a struct.. which would mean over 300,000 casts in my case.

    Or is a cast not really time-intensive as I think it is? or at all?
    The main reason for using void* like Salem said I think, is that the pre-processor thing gets pretty complicated rather fast, if you have a wide range of data types you need to use within your framework.
    1. Get rid of gets(). Never ever ever use it again. Replace it with fgets() and use that instead.
    2. Get rid of void main and replace it with int main(void) and return 0 at the end of the function.
    3. Get rid of conio.h and other antiquated DOS crap headers.
    4. Don't cast the return value of malloc, even if you always always always make sure that stdlib.h is included.

  12. #12
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    Quote Originally Posted by tabstop View Post
    Casts are for type-checking (or abuses thereof); there's no run-time action that happens.
    thanks, good to know

  13. #13
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by tabstop View Post
    [*]Is this supposed to be different than the offsetof macro that's already in C and C++ (in stddef)?
    I'd have to look that one up, probably it is the same.

    [*]I think I vaguely see what you mean here, but I'm going to have to think about it more carefully.[/list]
    I got the idea from the linux kernel, which works linked lists (and trees) this way. There is a single L.L. implementation for the whole thing, so eg:

    Code:
    struct whatever {
          data_t a;
          ptr *b;
          struct node listlink;
          [...etc...]
    }
    "Listlink" contains previous and next pointers. "Struct whatever" can be strung on a linked list (possibly of heterogeneous structures) via the embedded node. OFFSETOF and CONTAINER are macros used to get the to get the containing struct.

    I'm all excited about this at the moment as I'm trying to write a b-tree array/hash table library, that could be used in C or C++. Since you can define the size of the table array and the m dimension of the b-trees in it, this should provide way way better than O(log(n)) lookups, etc. Or else I'll just get an exercise->in->concentration and hopefully learn some stuff
    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

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by MK27 View Post
    I got the idea from the linux kernel, which works linked lists (and trees) this way. There is a single L.L. implementation for the whole thing, so eg:

    Code:
    struct whatever {
          data_t a;
          ptr *b;
          struct node listlink;
          [...etc...]
    }
    "Listlink" contains previous and next pointers. "Struct whatever" can be strung on a linked list (possibly of heterogeneous structures) via the embedded node. OFFSETOF and CONTAINER are macros used to get the to get the containing struct.

    I'm all excited about this at the moment as I'm trying to write a b-tree array/hash table library, that could be used in C or C++. Since you can define the size of the table array and the m dimension of the b-trees in it, this should provide way way better than O(log(n)) lookups, etc. Or else I'll just get an exercise->in->concentration and hopefully learn some stuff
    Yeah I managed to get double linked list working with that sort of setup. It sure doesn't cut down on code bloat, but you're pretty much going to have that anyway.

  15. #15
    Registered User sbaginov's Avatar
    Join Date
    May 2010
    Location
    Italy
    Posts
    19
    @Salem: thank you for sharing! That's interesting indeed!

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. What's a good generalized data structures book?
    By indigo0086 in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-16-2006, 12:01 PM
  2. i need advice about data structures
    By sawer in forum C Programming
    Replies: 2
    Last Post: 04-22-2006, 03:40 AM
  3. Need some help regarding data structures
    By Afrinux in forum C Programming
    Replies: 15
    Last Post: 01-28-2006, 04:19 AM
  4. array of structures, data from file
    By nomi in forum C Programming
    Replies: 5
    Last Post: 01-11-2004, 12:42 PM
  5. Array Data Structures
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 03-27-2002, 05:52 PM

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