A Queue implementation of doubly linked list in C

[Chris M. Thomasson]

[...]
struct my_list
{
char arrc[SIZE_ARR];
struct my_list* next;
struct my_list* prev;
};


struct my_queue
{
struct my_list* head;
struct my_list* tail;
};
[...]

FWIW, you can make your queue more generic/flexable by simply defining the
links as:


struct slink {
struct slink* next;
};


You don't need to hard code in a `void*' pointer, or extra space for a user
to store information in. Here is a very simple example code:
___________________________________________________________________
#include <stddef.h>




/* Sample Generic Queue
______________________________________________________________*/
#define CONTAINS(mp_self, mp_struct, mp_member) ((mp_struct*)( \
(unsigned char*)(mp_self) - offsetof(mp_struct, mp_member) \
))


struct slink {
struct slink* next;
};


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


#define QUEUE_SINIT { NULL }


#define QUEUE_ITERATE_BEGIN(mp_self, mp_name, mp_struct, mp_member) { \
struct slink* QUEUE_slink__ = (mp_self)->head; \
while (QUEUE_slink__) { \
struct slink* QUEUE_next__ = QUEUE_slink__->next; \
mp_struct* mp_name = CONTAINS(QUEUE_slink__, mp_struct, mp_member)


#define QUEUE_ITERATE_END() \
QUEUE_slink__ = QUEUE_next__; \
} \
} ((void)0)




struct slink*
queue_push(
struct queue* const self,
struct slink* node
) {
if (node) {
node->next = NULL;
if (! self->tail) {
self->head = node;
} else {
self->tail->next = node;
}
self->tail = node;
}
return node;
}


struct slink*
queue_pop(
struct queue* const self
) {
struct slink* node = self->head;
if (node) {
self->head = node->next;
if (! self->head) {
self->tail = NULL;
}
}
return node;
}




/* Sample Application Code
______________________________________________________________*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>




#define BUFSIZE 16U


struct my_slink {
char buf[BUFSIZE];
struct slink slink;
};




struct my_slink*
my_slink_push(
struct queue* const self,
char const* buf
) {
struct my_slink* const my_slink = malloc(sizeof(*my_slink));
if (my_slink) {
size_t len = strlen(buf);
if (len > BUFSIZE - 1) {
len = BUFSIZE - 1;
}
memcpy(my_slink->buf, buf, len);
my_slink->buf[len] = '\0';
queue_push(self, &my_slink->slink);
printf("pushed(%p):%s\n", (void*)my_slink, my_slink->buf);
}
return my_slink;
}


void
my_slink_print(
struct queue* const self
) {
size_t i = 0;
QUEUE_ITERATE_BEGIN(self, iter, struct my_slink, slink);
printf("printing(%lu/%p):%s\n", (unsigned long)i,
(void*)iter, iter->buf);
++i;
QUEUE_ITERATE_END();
}


void
my_slink_flush(
struct queue* const self
) {
size_t i = 0;
struct slink* slink = queue_pop(self);
while (slink) {
struct my_slink* const my_slink = CONTAINS(slink, struct my_slink,
slink);
printf("destroying(%lu/%p):%s\n", (unsigned long)i,
(void*)my_slink, my_slink->buf);
free(my_slink);
++i;
slink = queue_pop(self);
}
}




int main(void) {
struct queue queue = QUEUE_SINIT;

my_slink_push(&queue, "Chris");
my_slink_push(&queue, "John");
my_slink_push(&queue, "Steve");
my_slink_push(&queue, "Lindsay");
my_slink_push(&queue, "Richard");
my_slink_push(&queue, "Tommy");
my_slink_print(&queue);
my_slink_flush(&queue);
my_slink_push(&queue, "Lisa");
my_slink_push(&queue, "Jane");
my_slink_push(&queue, "Mary");
my_slink_push(&queue, "This String Is Too Long!!");
my_slink_print(&queue);
my_slink_flush(&queue);

return 0;
}
___________________________________________________________________




Here is the code in pastebin just in case the post gets mangled by your
newsreader:

http://pastebin.com/m4b4bc009

 

[Barry Schwarz]

No I don't, I really wonder why it even worked, it should have Segfaulted.
I have changed it, see my new code in my reply to Richard Heathfield.

Undefined behavior is by definition not required to do what you expect
nor expected to do what you require.

 

[Barry Schwarz]

snip

/* A Queue implementation in C using doubly linked list. It has all of the operation required by section 2.4 of "Data Structures and
* Algorithms" written by by Aho Hopcraft and Ullman. The name sof the queue operations were taken from that book.
*
* VERSION 0.2

If you are going to the trouble to produce a new version, you should
spend some time thinking about how to apply the responses you
received. The object of the exercise is not to see how fast you can
generate the version but how many corrections you can include in it.

Your previous version had a problem dereferencing NULL pointers. You
fixed the places that were specified but made no apparent effort to
see where else you made the same mistake.

*
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { QUEUE_NOT_EMPTY, QUEUE_EMPTY, QUEUE_NOT_INITIALIZED };
enum { SIZE_ARR = 10 } ;

struct my_list
{
char arrc[SIZE_ARR];
struct my_list* next;
struct my_list* prev;
};


struct my_queue
{
struct my_list* head;
struct my_list* tail;
};


struct my_queue* enqueue( struct my_queue*, const char* );
struct my_queue* dequeue( struct my_queue* );
struct my_list* front( struct my_queue* );
struct my_queue* queue_new( void );
struct my_list* make_null( struct my_queue* );
int is_empty( struct my_queue* );

void queue_print( struct my_queue* );
void queue_print_element( struct my_list* );


int main( void )
{
struct my_queue* m = queue_new();

queue_print( m );
enqueue( m, "comp" );
enqueue( m, "." );
enqueue( m, "lang" );
enqueue( m, "." );
enqueue( m, "c" );

queue_print( m );

dequeue( m );
dequeue( m );
dequeue( m );
dequeue( m );
dequeue( m );
dequeue( m );

queue_print( m );
printf(" Front = ");
queue_print_element( front(m) );

if( is_empty(m) )
{
printf("Queue is empty\n");
}
else
{
printf("Queue not empty\n");
}

The number of times you need more than a single line of vertical white
space within a function can be counted on the thumbs of your left
foot.

make_null( m );
free( m );
m = NULL;

return 0;
}
snip

struct my_list* make_null( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue is already NULL\n", __LINE__ );
}
else
{
while( s->head ) dequeue(s);
}

return s->head; /* head will be NULL if make_null was success */

If s started out NULL, you still try to dereference it.

}


struct my_list* front( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue not initialized ?\n", __LINE__);
}

return s->head;

If s is NULL, you still try to dereference it.

}


int is_empty( struct my_queue* s )
{
int ret_value = QUEUE_NOT_EMPTY;

if( NULL == s )
{
ret_value = QUEUE_NOT_INITIALIZED;
}
else if( NULL == s->head && NULL == s->tail )
{
ret_value = QUEUE_EMPTY;
}

In a couple of other functions you went to the trouble to test if one
of head/tail was empty but the other not. Why not here?

 

[arnuld]

The number of times you need more than a single line of vertical white
space within a function can be counted on the thumbs of your left
foot.

I don't have any rules for white-space. Arr they any good ?

If s is NULL, you still try to dereference it.

Okay, code fixed.

In a couple of other functions you went to the trouble to test if one
of head/tail was empty but the other not. Why not here?

Because in that condition I have to return QUEUE_NOT_EMPTY which I am
returning anyway in the end.

 

[Guest]

I haven't the time to come up with one, but the key thing that justifies
the use of doubly-linked lists is the necessity of traversing the list
in each direction. Try to imagine an application where you would need to
look backwards from a specified point in a list, as well as forward (If
you only needed to search backwards, just use a singly-linked list in
the opposite direction).

a simple list of items where you need to add and delete items.
Deleteing is slightly easier with doubly linked lists.

The project I work on has coding standards that require that our
delivered code should always check for any error indicators returned by
a function.

re-read it. It probably says "you must check any return value".
Meaning check it if there is one. It doesn't mean always return a
value.
Though I am assuming your programming standards are sane!

 

[James Kuyper]

re-read it. It probably says "you must check any return value".

No. Only return values that indicate errors. It also requires that if
the function uses some method other than the return value to indicate an
error, that method should also be checked.

Meaning check it if there is one. It doesn't mean always return a
value.

Yes, that's precisely the point I was making.

Though I am assuming your programming standards are sane!

Well, that's open to question. Those same standards also require that we
produce code which "conforms" to the C90 standard, as amended by the
next two TRs, which implies it was, at the very least, written by
someone who didn't understand how C90 defines "conforming code".

 

[Barry Schwarz]

snip




Because in that condition I have to return QUEUE_NOT_EMPTY which I am
returning anyway in the end.

The specified condition describes a broken queue, not a not empty
queue. Since you previously stated you wanted to reuse these
functions in other code, the question is "Why do some functions test
for a broken queue and not others?"

 

[arnuld]

The specified condition describes a broken queue, not a not empty
queue. Since you previously stated you wanted to reuse these
functions in other code, the question is "Why do some functions test
for a broken queue and not others?"

Hmm.. thats a really a logical question. Since it can be used a library
code, I think it is time for my enum values to not to function as a
boolean values but error indicator values:


/* A Queue implementation in C using doubly linked list. It has all of the operation required by section 2.4 of "Data Structures and
* Algorithms" written by by Aho Hopcraft and Ullman. The name sof the queue operations were taken from that book.
*
* VERSION 0.3
*
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


enum { QUEUE_NOT_EMPTY, QUEUE_EMPTY, QUEUE_BROKEN, QUEUE_NOT_INITIALIZED };
enum { SIZE_ARR = 10 } ;

struct my_list
{
char arrc[SIZE_ARR];
struct my_list* next;
struct my_list* prev;
};


struct my_queue
{
struct my_list* head;
struct my_list* tail;
};


struct my_queue* enqueue( struct my_queue*, const char* );
struct my_queue* dequeue( struct my_queue* );
struct my_list* front( struct my_queue* );
struct my_queue* queue_new( void );
struct my_list* make_null( struct my_queue* );
int is_empty( struct my_queue* );

void queue_print( struct my_queue* );
void queue_print_element( struct my_list* );


int main( void )
{
struct my_queue* m = queue_new();

queue_print( m );
enqueue( m, "comp" );
enqueue( m, "." );
enqueue( m, "lang" );
enqueue( m, "." );
enqueue( m, "c" );

queue_print( m );

dequeue( m );
dequeue( m );
dequeue( m );

printf(" Front = ");
queue_print_element( front(m) );

dequeue( m );
dequeue( m );
dequeue( m );

queue_print( m );

if( is_empty(m) )
{
printf("Queue is empty\n");
}
else
{
printf("Queue not empty\n");
}


make_null( m );
free( m );
m = NULL;

return 0;
}


struct my_queue* enqueue( struct my_queue* s, const char* c )
{
struct my_list* p = malloc( 1 * sizeof *p );

/* Check 1: the new element just malloc()ed */
if( NULL == p )
{
fprintf(stderr, "LINE: %d, malloc() failed\n", __LINE__ );
return s;
}

if( strlen(c) < SIZE_ARR )
{
strcpy( p->arrc, c );
p->prev = p->next = NULL;
}
else
{
printf("Size of array of the element is larger than required\n");
free(p);
return s;
}

/* Check 2: the original queue */
if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );
free(p);
}
else if( NULL == s->head && NULL == s->tail )
{
/* printf("Adding First element to Queue\n"); */
s->head = s->tail = p;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
free(p);
return s;
}
else
{
/* printf("Adding element to the tail\n"); */
s->tail->next = p;
p->prev = s->tail;
s->tail = p;
}

return s;
}


struct my_queue* dequeue( struct my_queue* s )
{
if( NULL == s)
{
printf("LINE: %d, Queue not initialized\n", __LINE__ );
}
else if( NULL == s->head && NULL == s->tail )
{
printf("There are no elements in the queue\n");
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
}
else
{
/* printf("Removing element\n"); */
struct my_list* r = s->head;
s->head = s->head->next; /* head removed from the queue */
free(r);

if( NULL == s->head ) /* in case we removed the last remaining element */
{
s->tail = s->head;
}
else
{
s->head->prev = NULL; /* set the prev of the head to the NULL */
}
}


return s;
}



struct my_list* make_null( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue is already NULL\n", __LINE__ );
return NULL;
}
else
{
while( s->head ) dequeue(s);
}

return s->head; /* head will be NULL if make_null was success */
}


struct my_list* front( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue not initialized ?\n", __LINE__);
return NULL;
}

return s->head;
}


int is_empty( struct my_queue* s )
{
int ret_value = QUEUE_NOT_EMPTY;

if( NULL == s )
{
ret_value = QUEUE_NOT_INITIALIZED;
}
else if( NULL == s->head && NULL == s->tail )
{
ret_value = QUEUE_EMPTY;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
ret_value = QUEUE_BROKEN;
}

return ret_value;
}



struct my_queue* queue_new( void )
{
struct my_queue* p = malloc( 1 * sizeof *p );

if( NULL == p )
{
fprintf( stderr, "LINE: %d, malloc() failed, can not initialize queue\n", __LINE__ );
exit( EXIT_FAILURE );
}

p->head = p->tail = NULL;

return p;
}


void queue_print( struct my_queue* s )
{
struct my_list* p = NULL;

if( NULL == s )
{
printf("Can not print a NULL queue\n");
}
else
{
for( p = s->head; p; p = p->next )
{
queue_print_element(p);
printf("PREV = ");
queue_print_element(p->prev);

printf("NEXT = ");
queue_print_element(p->next);
printf("\n\n");
}
}

printf("--------------------------------------\n");

}


void queue_print_element( struct my_list* p )
{
if( NULL == p )
{
printf("[NULL element]\n");
}
else
{
printf("[%s]\n", p->arrc);
}
}

 

[Barry Schwarz]

/* A Queue implementation in C using doubly linked list. It has all of the operation required by section 2.4 of "Data Structures and
* Algorithms" written by by Aho Hopcraft and Ullman. The name sof the queue operations were taken from that book.
*
* VERSION 0.3
*
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


enum { QUEUE_NOT_EMPTY, QUEUE_EMPTY, QUEUE_BROKEN, QUEUE_NOT_INITIALIZED };
enum { SIZE_ARR = 10 } ;

struct my_list
{
char arrc[SIZE_ARR];
struct my_list* next;
struct my_list* prev;
};


struct my_queue
{
struct my_list* head;
struct my_list* tail;
};


struct my_queue* enqueue( struct my_queue*, const char* );
struct my_queue* dequeue( struct my_queue* );
struct my_list* front( struct my_queue* );
struct my_queue* queue_new( void );
struct my_list* make_null( struct my_queue* );
int is_empty( struct my_queue* );

void queue_print( struct my_queue* );
void queue_print_element( struct my_list* );


int main( void )
{
struct my_queue* m = queue_new();

queue_print( m );
enqueue( m, "comp" );
enqueue( m, "." );
enqueue( m, "lang" );
enqueue( m, "." );
enqueue( m, "c" );

queue_print( m );

dequeue( m );
dequeue( m );
dequeue( m );

printf(" Front = ");
queue_print_element( front(m) );

dequeue( m );
dequeue( m );
dequeue( m );

queue_print( m );

if( is_empty(m) )

is_empty is no longer boolean.

{
printf("Queue is empty\n");

or broken or uninitialized.

}
else
{
printf("Queue not empty\n");
}


make_null( m );
free( m );
m = NULL;

return 0;
}


snip

struct my_list* make_null( struct my_queue* s )
{
if( NULL == s )
{
printf("LINE: %d, Queue is already NULL\n", __LINE__ );

If s is NULL, the queue is uninitialized which is different than empty
which is the purpose of make_null.

return NULL;
}
else
{
while( s->head ) dequeue(s);
}

return s->head; /* head will be NULL if make_null was success */

Since all paths return NULL, how is the user to know if it succeeded
or not?

It seems to me this function should return a my_queue* and on success
return s, not s->head.

}
snip

int is_empty( struct my_queue* s )
{
int ret_value = QUEUE_NOT_EMPTY;

if( NULL == s )
{
ret_value = QUEUE_NOT_INITIALIZED;
}
else if( NULL == s->head && NULL == s->tail )
{
ret_value = QUEUE_EMPTY;
}
else if( NULL == s->head || NULL == s->tail )
{
fprintf(stderr, "LINE: %d, one of head/tail is NULL while other is not, WHY ???\n", __LINE__ );
ret_value = QUEUE_BROKEN;
}

return ret_value;
}

snip

 

[arnuld]

is_empty is no longer boolean.

Okay, I will make it simple. It has to be a boolean, so lets return true
in case queue exists and is empty, and return false in every other case,
like queue does not exist or queue's head/tail are mismatched. Will it be
fine idea ?

Since all paths return NULL, how is the user to know if it succeeded
or not?

It seems to me this function should return a my_queue* and on success
return s, not s->head.

Now I think I was wrong in choosing s->head.

 

[Guest]

Okay, I will make it simple. It has to be a boolean, so lets return true
in case queue exists and is empty, and return false in every other case,
like queue does not exist or queue's head/tail are mismatched. Will it be
fine idea ?

you probably need an is_valid() predicate (function) as well.
This returns true if the queue is valid (presumably "exists" and
has sane values in its head and tail pointers).

Never call any other queue function, including, is_empty() unless
you are sure is_valid() is true. I'd be very tempted to
assert(is_valid(q)) at key points in the program. Especially
in your test harness. You do have a test harness?

 

[Guest]

(e-mail address removed) said:

And one such key point is at the beginning of is_empty()!

I think the value of assertions is massively underrated by most C
programmers.

nice to see such a diversity of opinion on the subject of assert()!

 

[squeamz]

Sounds really amateurish and sloppy.

I would test it properly and have no such asserts cluttering up the
code.

That's a really naive statement. As assert(is_valid(q)) protects
against someone breaking the code in the future. No matter how
"proper" your tests are, they still have to be maintained when someone
changes your code.

You seem to argue with everyone else in this group, but you're just
another idealogue.

 

[Barry Schwarz]

Okay, I will make it simple. It has to be a boolean, so lets return true
in case queue exists and is empty, and return false in every other case,
like queue does not exist or queue's head/tail are mismatched. Will it be
fine idea ?

Not in my opinion. It begs the question of why you feel the need to
test for queue validity sometimes but not others.

 

[arnuld]

Not in my opinion. It begs the question of why you feel the need to
test for queue validity sometimes but not others.

It has to return true or false, so what one does in such a situation ?
(As I said, I am implementing from Aho, Hopcraft and Ullman's book and
is_empty() there is boolean.)

 

[arnuld]

I have yet to meet a high quality programmer who objects to them. I
have, however, met quite a few high quality programmers who don't
use them *enough* (as they themselves would agree). It is perhaps
not too much of a stretch to say that a programmer who objects to
them is almost certainly not a good programmer.

..SNIP...

I never used assertions. I am not saying they are good bad, I never
found any need for an assert(), though my colleagues do use them a
lot. I try to check for every expected or unexpected value in the
function itself and then print the relevant error andreturn
appropriately as per my knowledge.

 

[Beej Jorgensen]

I never used assertions. I am not saying they are good bad, I never
found any need for an assert()

There are definitely plenty of legitimate defensive coding techniques
that don't make use of asserts.

Wikipedia has a good page on the matter:

http://en.wikipedia.org/wiki/Assert

-Beej

 

[Barry Schwarz]

It has to return true or false, so what one does in such a situation ?
(As I said, I am implementing from Aho, Hopcraft and Ullman's book and
is_empty() there is boolean.)

Since you have modified it three times already, are their previous
design decisions really the driving force any more?

 

[Guest]

could you leave more context?

well? Why do you sometime stest for queue validity in some places and
not in others? The point is asking if the queue is empty when IT
ISN'T
A QUEUE is meaningless. There is allegedly a japanese word "mu" which
is the answer given to a question that the answerer believes to be
ill-
formed.

I show you a dog and ask you "is the apple red?"

It has to return true or false, so what one does in such a situation ?

if it's a valid queue then return true if is empty and false if it not
empty.

(As I said, I am implementing from Aho, Hopcraft and Ullman's book and
is_empty() there is boolean.)

but it presumably makes the assumption (either explicitly or
implicitly)
that it is only used on a correctly formed queue.


--
Nick Keighley

De maan likt niet hoog The moon doesn't look high
Maar het is niet zo But it is not so
De maan is wel hoog The moon is very high
Of niet sams? Or is it?

 

[arnuld]

Since you have modified it three times already, are their previous
design decisions really the driving force any more?

If the current discussion makes my queue better (in practical terms)
as compared to earlier design, I am sure I will ignore the earlier
design decisions.

I am able to do my job because of the skill I have gained. Whatever I
have learned about C, whatever skill I have gained over the last 6
months by reading/wrting posts on CLC is what I have never learned
anywhere. I always do what CLC folks say, Its my learning ground, it
smy mentor, my teacher and everything I know about C. CLC ==
practical mentoring