Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #22480

Re: dequeue() not working

Show all headers | View raw

On 2012-06-21, arnuld <sunrise@invalid.address> wrote:
> WANTED: to dequeue an element from Queue.
> GOT: nothing happening
>
> /* A queue implementation with the operations that I need:
>  *  (1) Add an element to the front (head) of the queue
>  *  (2) Remove an element from rear (tail) of the queue
>  *  (2) remove an element with a unique ID (string constant)
>  *  (3) compare 2 elements (string comparison) 
>  *  (4) print queue
>  *
>  * VERSION 0.0
>  */
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> enum { SIZE_ID = 100, SIZE_ARR = 20, REPS = 3 };
>
> struct myQ
> {
>   char id[SIZE_ID+1];
>   struct myQ* next;
> };
>
> struct myList
> {
>   struct myQ* head;
>   struct myQ* tail;
> };

Implementing linked lists in C may be like walking for most of
the people here, but I think you will benefit by writing down
some notes here.

Along with the struct write down the invariants for the
structures.

For example:

struct myQ
{
  char id[SIZE_ID+1]; # null-terminated string.
  struct myQ* next; # pointer to the next element or NULL.
};

struct myList
{
  struct myQ* head; # pointer to first item in list or NULL
  struct myQ* tail; # pointer to last item  in list or NULL
};
>
>
>
> struct myList* allocmyList(void);
> int enqueue(struct myList* s, const char* id);
> struct myQ* dequeue(struct myList** s); 
> void removeElement(struct myList* s, const char* id);
> struct myQ* searchElement(struct myList* s, const char* is, struct myQ** 
> pr);
> void deleteElement(struct myList* s, struct myQ* q, struct myQ* prev);
> void printQ(struct myList* s);
> /*void reverseQueue(struct myList** s); */
>
>
> int main(void)
> {
>   struct myList* s = allocmyList();
>   int i;
>   for(i = 0; i < REPS; ++i)
>     {
>       int r;
>       char arrc[SIZE_ARR+1];
>       r = sprintf(arrc, "%d", i);
>       if(0 > r) 
> 	{
> 	  printf("ERROR-SPRINF() = %d\n", r);
> 	}
>       else
> 	{
> 	  enqueue(s, arrc);
> 	}
>       printf("s->head = %p, s->tail = %p\n", (void*)s->head, (void*)s-
>>tail);
>     }
>  
>   printQ(s);
>   /*
>   for(i = 0; i < REPS; ++i) 
>     {
>       int r;
>       char arrc[SIZE_ARR+1];
>       r = sprintf(arrc, "%d", i);
>       if(0 > r) 
> 	{
> 	  printf("ERROR-SPRINF() = %d\n", r);
> 	}
>       else
> 	{
> 	  removeElement(s, arrc);
> 	}
>     }
>   */
>   dequeue(&s);
>   printQ(s);
>   free(s);
>
>   return 0;
> }
>
>
> int enqueue(struct myList* s, const char* id)
> {
>   struct myQ *p;
>   if(NULL == s || NULL == id) return -1;

This type of error checking is the equivalent of crotchless
underpants. Why bother? Anybody careless enough to pass NULL as
either of those arguments will not be checking the return value.

>   p = malloc(1 * (sizeof *p));
>   if(NULL == p) return -1;
>   strcpy(p->id, id);

You must use strncpy with SIZE_ID here to protect against
overflow of p->id.

>   if(s->head)
>     {
>       p->next = s->head;
>       s->head = p;
>     }
>   else
>     {
>       s->head = s->tail = p;

Checking invariants, in this branch p->next is left undefined.

>     }
>   return 1;
> }

I suggest paring down the interface to a minimal singly-linked
list with head and tail pointers, with perhaps an apply function
to allow you to do some tests.

The interface is confusing.

For example, your search function:

> struct myQ* searchElement(struct myList* s, const char* id, struct myQ** 
> pr)

What is pr supposed to be?

dequeue and enqueue are function names without obvious meanings.
push_front and push_back along with pop_front and pop_back would
be easier to comprehend.

-- 
Neil Cerutti

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

dequeue() not working arnuld <sunrise@invalid.address> - 2012-06-21 07:11 +0000
  Re: dequeue() not working Ike Naar <ike@iceland.freeshell.org> - 2012-06-21 08:37 +0000
    Re: dequeue() not working Ike Naar <ike@iceland.freeshell.org> - 2012-06-21 08:42 +0000
      Re: dequeue() not working Ike Naar <ike@iceland.freeshell.org> - 2012-06-21 08:43 +0000
  Re: dequeue() not working Johann Klammer <klammerj@NOSPAM.a1.net> - 2012-06-21 11:09 +0200
    Re: dequeue() not working jgk@panix.com (Joe keane) - 2012-06-22 23:23 +0000
      Re: dequeue() not working Martin Shobe <martin.shobe@yahoo.com> - 2012-06-23 00:09 +0000
      Re: dequeue() not working Heikki Kallasjoki <fis+usenet@zem.fi> - 2012-06-23 00:10 +0000
      What's in a name? Johann Klammer <klammerj@NOSPAM.a1.net> - 2012-06-23 12:19 +0200
  Re: dequeue() not working Neil Cerutti <neilc@norwich.edu> - 2012-06-21 12:38 +0000
  Re: dequeue() not working pete <pfiland@mindspring.com> - 2012-06-23 00:39 -0400

csiph-web