Queue in C

[Keith Thompson]

It's not clear what all these -13s mean.

Presumably they are an error return (but code -13 not documented). You
should use a #define or enum name for these:

#define unknownerror -13

[...]

That should be

#define unknownerror (-13)

to avoid operator precedence problems. It's likely that there are no
actual uses of unknownerror that would cause problems, but it's better
to be safe.

A good reason to use an enum for return values rather than an ugly macro.

Good idea; fortunately, in this case, the return values are of type int.

Yet another...

Some coding conventions require enumerators to be in all-caps as well.

I'm not necessarily defending that, but there is something to be said
for being able to tell at a glance that a given value is a compile-time
constant rather than something that could vary:

ptr = malloc(how_much);
if (ptr == NULL) {
return MEMORY_FAILURE;
}
do_some_stuff;
return result_of_previous_call; /* could denote success or failure */

 

[BartC]

Some coding conventions require enumerators to be in all-caps as well.

I'm not necessarily defending that, but there is something to be said
for being able to tell at a glance that a given value is a compile-time
constant rather than something that could vary:

ptr = malloc(how_much);
if (ptr == NULL) {
return MEMORY_FAILURE;
}
do_some_stuff;
return result_of_previous_call; /* could denote success or failure */

What about variables (or whatever the right term is) which are declared with
'const'; should they be in upper case too?

 

[Malcolm McLean]

Malcolm McLean wrote:





Wouldn't an assertion be better than calling exit?

(Baby X is the cross platform simple GUI toolkit I am developing).

At the moment it exits with an error message to stderr, which the
end-user is unlikely to see because he'll launch the program from some
sort of graphical interface. However a developer will see it.
Assuming Baby X to be debugged, the error message is unlikely to be
very informative. Baby X allocates a large number of small chunks
of memory (I was surprised, for a very simple test program that total
number of allocations was several thousand). However it also back-buffers
windows, so there are also some medium-sized allocations in there,
and it's not unthinkable that it could run a typical system out of
memory. All it really tells you is that the system is out of
resources.

Assert-failing instead of exiting is maybe a good idea. However it
doesn't make any sense to strip asserts for runtime builds.

 

[Keith Thompson]

What about variables (or whatever the right term is) which are declared with
'const'; should they be in upper case too?

Probably not.

I might consider it if (a) the initial value is a compile-time
constant, and (b) I have decided to, or am following a coding
standard that requires me to, use all-caps to denote compile-time
constant values. Of course an object defined as "const" is not
treated as a constant expression in C, which could be a good reason
not to use all-caps in that case.

 

[Siri Crews]

struct node
{
char c;
struct node* next;
};


struct queue
{
struct node* head;
struct node* tail;
};

#define QueueInterface(scope,T) \
typedef struct Queue##T *Queue##T; \
struct Queue##T {T value; Queue##T next, last;}; \
\
scope Queue##T null##T; \
\
scope Queue##T push##T(Queue##T q, T value); \
scope Queue##T append##T(Queue##T q, T value); \
\
scope Queue##T pop##T(Queue##T q); \
scope Queue##T next##T(Queue##T q); \
scope T top##T(Queue##T q,T value); \
\
scope _Bool empty##T(Queue##T q); \
\
scope Queue##T reverse##T(Queue##T q); \
\
scope void printqueue##T(Queue##T q); \
scope void printnode##T(Queue##T q); \
\
scope Queue##T search##T(Queue##T q, T seek); \
scope Queue##T deleteFrom(Queue##T q, T seek); \
scope queue##T insertAfter##T(Queue##T q, T seek, T value); \
scope Queue##T insertBefore(Queue##T q, T seek, T value);

#define QueueImplementation(scope,T,MALLOC,FREE,PRINT,EQ) \
scope Queue##T null##T = 0; \
\
scope Queue##T push##T(Queue##T q, T value) { \
Queue##T c = MALLOC(sizeof(struct Queue##T)); \
if (!c) return null##T; \
c->value = value; c->next = q; c->last = c; \
return c; \
} \
scope Queue##T append##T(Queue##T q, T value) { \
Queue##T c = MALLOC(sizeof(struct Queue##T)); \
if (!c) return null##T; \
c->value = value; c->next = q; c->last = c; \
if (q) { \
for (Queue##T p=q->last; p->next; p=p->next); \
q->last = p->next = c; \
}else \
q = c; \
return q; \
} \
\
scope Queue##T pop##T(Queue##T q) { \
if (q) {Queue##T c = q; q = q->next; FREE(c);} \
return q; \
} \
scope Queue##T next##T(Queue##T q) { \
return q ? q->next : null##T; \
} \
scope T top##T(Queue##T q,T value) { \
if (q) return q->value; \
else {T zero; memset(&T,sizeof T,0); return zero;} \
} \
\
scope _Bool empty##T(Queue##T q) { \
return !q; \
} \
\
scope Queue##T reverse##T(Queue##T q) { \
Queue##T prev = null##T; \
for (Queue##T curr=q, next=null##T; !empty##T(curr); prev=curr,
curr=next) { \
next = curr->next; curr->next = prev; curr->last = q; \
} \
return prev; \
} \
\
scope void printqueue##T(Queue##T q) { \
if (q) { \
for (; !empty##T(q); q=next##T(q)) { \
printf("Element = "); PRINT(top##T(q)); printf("\n"); \
} \
printf("--------------- EoQ -----------\n\n"); \
} \
} \
scope void printnode##T(Queue##T q) { \
if (q) { \
printf("Node = "); PRINT(top##T(q)); printf("\n"); \
} \
} \
\
scope Queue##T search##T(Queue##T q, T seek) { \
for (; !empty##T(q); q=next##T(q)) \
if (EQ(top##T(q), seek)) \
return q; \
return null##T; \
} \
scope Queue##T deleteFrom(Queue##T q, T seek) { \
Queue##T prev = null##T; \
for (Queue##T curr=q; empty##T(curr); prev=curr, curr=curr->next) \
if (!EQ(top##T(curr), seek)); \
else if (empty##T(prev)) {return pop##T(q);} \
else {prev->next = curr->next; FREE(curr); return q;} \
return null##T; \
} \
scope queue##T insertAfter##T(Queue##T q, T seek, T value) { \
for (Queue##T curr=q; empty##T(curr); curr=curr->next) \
if (EQ(top##T(curr), seek)) { \
Queue##T c = push##T(curr->next, value); \
if (!c) return null##T; \
else {curr->next = c; return q;} \
} \
return null##T; \
} \
scope Queue##T insertBefore(Queue##T q, T seek, T value) { \
Queue##T prev = null##T; \
for (Queue##T curr=q; empty##T(curr); prev=curr, curr=curr->next) \
if (EQ(top##T(curr), seek)) { \
Queue##T c = push##T(curr, value); \
if (!c) return null##T; \
else if (!prev) return c; \
else {prev->next = c; return q;} \
} \
return null##T; \
}

 

[Ike Naar]

Wouldn't an assertion be better than calling exit?

Caveat: assertions can be turned off using the NDEBUG macro.