C data structures

[rodrigorules]

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?

[Salem]

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

#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

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

# 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

[whiteflags]

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.

[rodrigorules]

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

#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

#define QUEUE_TYPE struct pixel
#define QUEUE_IDENTIFIER pixel
#include "cutter_queue.h"

[tabstop]

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

[rodrigorules]

yep just noticed the bug minutes before you posted

[MK27]

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

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

[tabstop]

You can also embed a node/struct in another struct and use a macro like this

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

[rodrigorules]

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?

[tabstop]

Casts are for type-checking (or abuses thereof); there's no run-time action that happens.

[claudiu]

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.

[rodrigorules]

Casts are for type-checking (or abuses thereof); there's no run-time action that happens.

thanks, good to know

[MK27]

[*]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:

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

[tabstop]

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:

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.

[sbaginov]

@Salem: thank you for sharing! That's interesting indeed!