Creating more generic data structures

[Andrea Crotti]

In our project my groupmate wanted to have a generic queue (which we
don't really need since it's used once) and so he ended up with a
enormous ugly macro.

He said it's the only way to accomplish having different data types
inside a queue in C, is that true?

Would not work just creating a module which takes the size and uses some
pointers to void to obtain the same result?
Something as below (modified of course) could not work as well?

--8<---------------cut here---------------start------------->8---
#include <stdlib.h>
#include <stdio.h>

#define MAX_LEN 10
size_t queue_size;

typedef struct queue
{
void *data[MAX_LEN];
} queue;

void init_queue(size_t size) {
queue_size = size;
}

void add_to_queue(write_queue *queue, void *data) {
assert(!queue_full(queue));
LOG_DEBUG("write-queue: adding %p to the queue",data.stream);
queue->data[queue->last] = data;
// going forward of one position
queue->last = NEXT(queue->last);
}

int queue_full(write_queue *queue) {
return (NEXT(queue->last) == (queue->first));
}

int queue_empty(write_queue *queue) {
return (queue->first == queue->last);
}

void *fetch_from_queue(write_queue *queue) {
return queue->data[queue->first];
}

void delete_last(write_queue *queue) {
queue->first = NEXT(queue->first);
}

int main(int argc, char *argv[])
{

return 0;
}
--8<---------------cut here---------------end--------------->8---

 

[Nick Keighley]

In our project my groupmate wanted to have a generic queue (which we
don't really need since it's used once)

I'm half sympathetic with him. It's a useful tool to have around. But
if you spend too much time writing generic stuff you don't get
anything done. Of course the question is "why is he implementing it on
*this* project". If his queue is so brilliant why didn't he implement
it on a previous project? Or does he implement a generic queue on
every project...

and so he ended up with a enormous ugly macro.

not sure why...

He said it's the only way to accomplish having different data types
inside a queue in C, is that true?

no, complete rubbish. There are masses of ways to implement queues.
Cyclic buffers, linked lists. With linked lists the pointers can be
embedded in the data or you have a carrier node

struct Node
{
struct Node *next;
void *data;
};

To make it generic you can wite it in terms of type T which is defined
by a typedef

typedef double T;

Harder to have multiple types of queue.

You could code generate the code when you needed it.

Look up past posts for Jacob Navia's ideas on gneric data structures.
(I forget the details but he used tables of fucntion pointers and it
sounded a lot less messy than what you've got).

 

[Andrea Crotti]

no, complete rubbish. There are masses of ways to implement queues.
Cyclic buffers, linked lists. With linked lists the pointers can be
embedded in the data or you have a carrier node

struct Node
{
struct Node *next;
void *data;
};

To make it generic you can wite it in terms of type T which is defined
by a typedef

typedef double T;

I also thought that, but maybe is because we are (he is) using a class
macro to have real (not in my opinion) classes also in C.
Here is the queue:
http://gist.github.com/517456

and here the class definition:
http://gist.github.com/517457

do you see any sense?

 

[Ben Bacarisse]

The void * solutions complicate the memory management. For some
situations a queue that holds the actual data (rather than pointing to
it) can be simpler.

I also thought that, but maybe is because we are (he is) using a class
macro to have real (not in my opinion) classes also in C.
Here is the queue:
http://gist.github.com/517456

and here the class definition:
http://gist.github.com/517457

This is code by someone who has taken the OO red pill. Many people have,
but even C++ does not do generic containers with classes (at least
that's not the key part of the way it's done).

do you see any sense?

Yes I do, but why are you not using C++? If you want this sort of
facility there has to be a sound reason not to use a language that has
it built in. I notice what looks to me to be a gccism is the code so
C++ might well be a real option. People on the team who don't know C++
can program in C-like C++ with very little learning. Alternatively, C
and C++ modules can be linked together with ease.

 

[Ben Pfaff]

In our project my groupmate wanted to have a generic queue (which we
don't really need since it's used once) and so he ended up with a
enormous ugly macro.

He said it's the only way to accomplish having different data types
inside a queue in C, is that true?

Here's my generic deque (double-ended queue) in C. It doesn't
use any macros:
http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/deque.h
http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/deque.c

Here's the description from a comment in the header:

/* Deque data structure.

This code slightly simplifies the implementation of a deque as
a circular queue. To use it, declare a "struct deque" and a
pointer to the element type. For example, for a deque of
"int"s:

struct deque deque;
int *data;

To initialize the deque with a initial capacity of 0:

deque_init_null (&deque);
data = NULL;

Alternatively, to initialize the deque with an initial minimum
capacity of, e.g., 4:

data = deque_init (&deque, 4, sizeof *data);

Functions that access elements in the deque return array
indexes. This is fairly convenient:

// Push X at the back of the deque.
data[deque_push_back (&deque)] = x;

// Pop off the front of the deque into X.
x = data[deque_pop_front (&deque)];

// Obtain the element just past the back of the deque as X.
x = data[deque_back (&deque, 1)];

The push functions will not expand the deque on their own.
Use the deque_expand function if necessary, as in:

// Push X at the back of the deque, first expanding the
// deque if necessary.
if (deque_is_full (&deque))
data = deque_expand (&deque, data, sizeof *data);
data[deque_push_back (&deque)] = x;

Expanding a deque will copy its elements from one memory
region to another using memcpy. Thus, your deque elements
must tolerate copying if their deque is to be expanded. */

 

[spinoza1111]

The void * solutions complicate the memory management.  For some
situations a queue that holds the actual data (rather than pointing to
it) can be simpler.

(Sigh). "Simpler" here is used in the vulgar-programmer sense meaning,
"I understand it and it does not raise my irrational fears about being
Nonstandard and using 'pointer to void'".

You're making Heathfield's mistake which was to code a "linked list"
which contained data in the node whose performance depended too much
on the size of the data. But evidence is that real programmers use
pointer to void all the time, the prohibition of which resulted from
C99's remit, which was not to disturb the grown-ups (the CEOs) by
changing and defining the semantics of C.

This is code by someone who has taken the OO red pill.  Many people have,
but even C++ does not do generic containers with classes (at least
that's not the key part of the way it's done).

OO is not a red pill. I suggest you go back to school.

 

[Jorgen Grahn]

This is code by someone who has taken the OO red pill. Many people have,
but even C++ does not do generic containers with classes (at least
that's not the key part of the way it's done).


Yes I do, but why are you not using C++? If you want this sort of
facility there has to be a sound reason not to use a language that has
it built in. I notice what looks to me to be a gccism is the code so
C++ might well be a real option. People on the team who don't know C++
can program in C-like C++ with very little learning. Alternatively, C
and C++ modules can be linked together with ease.

As primarily a C++ user, I tend to agree. It hurts my eyes to see
people reinventing wheels like std::queue<T>, in different ways every
time.

On the other hand ... what if you say "ok, from now on a C++ compiler
compiles our code, but stay away from everything except the standard
containers"? There is no way to enforce that, and it would slowly pull
more and more code over into C++ land. If I was a C user exclusively,
I don't think I'd like that.

/Jorgen

 

[Ben Bacarisse]

As primarily a C++ user, I tend to agree. It hurts my eyes to see
people reinventing wheels like std::queue<T>, in different ways every
time.

On the other hand ... what if you say "ok, from now on a C++ compiler
compiles our code, but stay away from everything except the standard
containers"? There is no way to enforce that, and it would slowly pull
more and more code over into C++ land. If I was a C user exclusively,
I don't think I'd like that.

That's true and the problem is not limited to C++. There are situation
where using limited features of C99 would help without hurting
portability (because you happen to know that features X and Y are
implemented on all the targets you care about) but once you drop C90
standard compiler flags, you won't be warned when other, less portable,
parts of C99 sneak in.

It would be good to have flags to turn features on an off (or to warn
about those that are off) individually, but I suspect the demand is low
compared to the effort of providing this facility.