Remving an element from Queue

A

arnuld

WANTED: Removing all elements matching a particular key from a Queue
WHAT I GOT: Segfault
WANTED: Segfaults in removeAllMatches(). I think routine/fucntion is too
complex to be understood. removeAllMatches(arg1, arg2) is supposed to
remove all elements from arg1 which match value of arg2.




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

struct myStruct
{
int num;
struct myStruct* next;
};

struct myQueue
{
struct myStruct* head;
struct myStruct* tail;
};


int enqueue(struct myQueue* q, int n);
int dequeue(struct myQueue* q);

struct myQueue* newQueue(void);
void makeNull(struct myQueue* q);
void removeAllMatches(struct myQueue* q, const int num);

void printQueue(struct myQueue* q);
void printStruct(struct myStruct* p);



int main(void)
{
struct myQueue* q = newQueue();
printQueue(q);

enqueue(q, -1);
enqueue(q, 100);
enqueue(q, 38);
enqueue(q, 100);
enqueue(q, 38);
enqueue(q, 9);
enqueue(q, 100);
printQueue(q);

removeAllMatches(q, 100);
printQueue(q);
/* makeNull(q);
printQueue(q); */
free(q);
q = NULL;

return 0;
}



int enqueue(struct myQueue* q, int n)
{
int ret;
if(NULL == q)
{
printf("Invalid Args\n");
ret = -1;
}
else
{
struct myStruct* p = malloc(1 * sizeof *p);
if(NULL == p)
{
printf("Out of memory\n");
exit(EXIT_FAILURE);
}

p->num = n;
p->next = NULL;
if(NULL == q->tail && NULL == q->head)
{
printf("Empty Queue, Adding first element\n");
q->head = q->tail = p;
ret = 0;
}
else if(NULL == q->tail || NULL == q->head)
{
printf("IN: %s @%d; ", __func__, __LINE__);
printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
free(p);
ret = 1;
}
else
{
printf("Adding Element\n");
q->tail->next = p;
q->tail = p;
ret = 0;
}
}

return ret;
}



int dequeue(struct myQueue* q)
{
int ret = -1;
if(NULL == q)
{
printf("Invalid Args\n");
ret = -1;
}
else
{
struct myStruct* h;
if(NULL == q->head && NULL == q->tail)
{
printf("Queue is already empty\n");
ret = 0;
}
else if(NULL == q->head || NULL == q->tail)
{
printf("IN: %s @%d; ", __func__, __LINE__);
printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
ret = 1;
}
else
{
h = q->head;
q->head = q->head->next;
free(h);
if(NULL == q->head)
{
printf("Removing Last element left\n");
q->head = q->tail = NULL;
}
else
{
printf("Removing Some element\n");
}
ret = 0;
}
}

return ret;
}


/* Added many months later */
void removeAllMatches(struct myQueue* q, const int num)
{
if(NULL == q)
{
printf("Invalid Args\n");
return;
}

if(NULL == q->head && NULL == q->tail)
{
printf("Queue is already empty\n");
}
else if(NULL == q->head || NULL == q->tail)
{
printf("IN: %s @%d; ", __func__, __LINE__);
printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
exit(EXIT_FAILURE);
}
else
{
struct myStruct *p, *d, *h;
p = d = h = NULL;
for(h = q->head; h; h = h->next)
{
d = h;
if(num == d->num)
{
if(num == q->head->num )
{
q->head = q->head->next;
}

if(num == q->tail->num)
{
q->tail = q->tail->next;
}

if(p)
{
p->next = h->next;
}
free(d);
}
else
{
p = h;
}
}

}
}




void makeNull(struct myQueue* q)
{
if(q)
{
while(q->head) dequeue(q);
}
}



struct myQueue* newQueue(void)
{
struct myQueue* p = malloc(1 * sizeof *p);
if(NULL == p)
{
printf("Out of Memory\n");
exit(EXIT_FAILURE);
}

return p;
}


void printQueue(struct myQueue* q)
{
if(q)
{
struct myStruct* p = q->head;
for(; p; p = p->next) printStruct(p);
printf("-----------------------------------------\n");
}
}


void printStruct(struct myStruct* p)
{
if(p)
{
printf("title: %d\n", p->num);
}
}

======================== OUTPUT ==========================
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra Queue.c
[arnuld@dune C]$ ./a.out
-----------------------------------------
Empty Queue, Adding first element
Adding Element
Adding Element
Adding Element
Adding Element
Adding Element
Adding Element
title: -1
title: 100
title: 38
title: 100
title: 38
title: 9
title: 100
 
E

Eric Sosman

WANTED: [...]
Click to expand...

I've only skimmed your code, but this bit is obviously wrong:
struct myQueue* newQueue(void)
{
struct myQueue* p = malloc(1 * sizeof *p);
if(NULL == p)
{
printf("Out of Memory\n");
exit(EXIT_FAILURE);
}

return p;
}
Click to expand...

Hint: What are the values of the elements in the newly-allocated
struct?
 
G

Guest

WANTED: Removing all elements matching a particular key from a Queue
WHAT I GOT: Segfault
WANTED: Segfaults in removeAllMatches(). I think routine/fucntion is too
complex to be understood. removeAllMatches(arg1, arg2) is supposed to
remove all elements from arg1 which match value of arg2.
Click to expand...

I don't get any output at all it crashes at the first printQueue() call in main(). The Head and Tail pointers contain crap (0xcdcdcd on a Microsoft system). They contain crap because newQueue() doesn't initialise them.

Why didn't you use a debugger? That's how I found the bug.


struct myQueue
{
struct myStruct* head;
struct myStruct* tail;
}; [...]
int main(void)
{
struct myQueue* q = newQueue();
printQueue(q); <--- DIE!

enqueue(q, -1); [...]
struct myQueue* newQueue(void)
{
struct myQueue* p = malloc(1 * sizeof *p);
if(NULL == p)
{
printf("Out of Memory\n");
exit(EXIT_FAILURE);
}

return p;
Click to expand...

what are head and tail at this point?
}


void printQueue(struct myQueue* q)
{
if(q)
{
struct myStruct* p = q->head;
oops!

for(; p; p = p->next) printStruct(p);
printf("-----------------------------------------\n");
}
}
Click to expand...

======================== OUTPUT ==========================
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra Queue.c
[arnuld@dune C]$ ./a.out
-----------------------------------------
Empty Queue, Adding first element
Adding Element
Adding Element
Adding Element
Adding Element
Adding Element
Adding Element
title: -1
title: 100
title: 38
title: 100
title: 38
title: 9
title: 100
Click to expand...

you could tidy things up by factoring out your queue check code that appears in at least three places
 
B

BartC

I don't get any output at all it crashes at the first printQueue() call in
main(). The Head and Tail pointers contain crap (0xcdcdcd on a Microsoft
system). They contain crap because newQueue() doesn't initialise them.
Click to expand...
Why didn't you use a debugger? That's how I found the bug.
Click to expand...

Mine just prints forever on printQueue(). Looking at newQueue() instantly
reveals the problem.

No need for any debugger. And what exactly did it say anyway?
 
M

Mark Bluemel

WANTED: Removing all elements matching a particular key from a Queue
WHAT I GOT: Segfault
WANTED: Segfaults in removeAllMatches().  I think routine/fucntion is too
complex to be understood. removeAllMatches(arg1, arg2) is supposed to
remove all elements from arg1 which match value of arg2.

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

struct myStruct
{
  int num;
  struct myStruct* next;

};

struct myQueue
{
  struct myStruct* head;
  struct myStruct* tail;

};

int enqueue(struct myQueue* q, int n);
int dequeue(struct myQueue* q);

struct myQueue* newQueue(void);
void makeNull(struct myQueue* q);
void removeAllMatches(struct myQueue* q, const int num);

void printQueue(struct myQueue* q);
void printStruct(struct myStruct* p);

int main(void)
{
  struct myQueue* q = newQueue();
  printQueue(q);

  enqueue(q, -1);
  enqueue(q, 100);
  enqueue(q, 38);
  enqueue(q, 100);
  enqueue(q, 38);
  enqueue(q, 9);
  enqueue(q, 100);
  printQueue(q);

  removeAllMatches(q, 100);
  printQueue(q);
  /*  makeNull(q);
      printQueue(q); */
  free(q);
  q = NULL;

  return 0;

}

int enqueue(struct myQueue* q, int n)
{
  int ret;
  if(NULL == q)
    {
      printf("Invalid Args\n");
      ret = -1;
    }
  else
    {
      struct myStruct* p = malloc(1 * sizeof *p);
      if(NULL == p)
        {
          printf("Out of memory\n");
          exit(EXIT_FAILURE);
        }

      p->num = n;
      p->next = NULL;
      if(NULL == q->tail && NULL == q->head)
        {
          printf("Empty Queue, Adding first element\n");
          q->head = q->tail = p;
          ret = 0;
        }
      else if(NULL == q->tail || NULL == q->head)
        {
          printf("IN: %s @%d; ", __func__, __LINE__);
          printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
          free(p);
          ret = 1;
        }
      else
        {
          printf("Adding Element\n");
          q->tail->next = p;
          q->tail = p;
          ret = 0;
        }
    }

  return ret;

}

int dequeue(struct myQueue* q)
{
  int ret = -1;
  if(NULL == q)
    {
      printf("Invalid Args\n");
      ret = -1;
    }
  else
    {
      struct myStruct* h;
      if(NULL == q->head && NULL == q->tail)
        {
          printf("Queue is already empty\n");
          ret = 0;
        }
      else if(NULL == q->head || NULL == q->tail)
        {
          printf("IN: %s @%d; ", __func__, __LINE__);
          printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
          ret = 1;
        }
      else
        {
          h = q->head;
          q->head = q->head->next;
          free(h);
          if(NULL == q->head)
            {
              printf("Removing Last element left\n");
              q->head = q->tail = NULL;
            }
          else
            {
              printf("Removing Some element\n");
            }
          ret = 0;
        }
    }

  return ret;

}

/* Added many months later */
void removeAllMatches(struct myQueue* q, const int num)
{
  if(NULL == q)
    {
      printf("Invalid Args\n");
      return;
    }

  if(NULL == q->head && NULL == q->tail)
    {
      printf("Queue is already empty\n");
    }
  else if(NULL == q->head || NULL == q->tail)
    {
      printf("IN: %s @%d; ", __func__, __LINE__);
      printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
      exit(EXIT_FAILURE);
    }
  else
    {
      struct myStruct *p, *d, *h;
      p = d = h = NULL;
      for(h = q->head; h; h = h->next)
        {
          d = h;
          if(num == d->num)
            {
              if(num == q->head->num )
                {
                  q->head = q->head->next;
                }

              if(num == q->tail->num)
                {
                  q->tail = q->tail->next;
                }

              if(p)
                {
                  p->next = h->next;
                }
              free(d);
            }
          else
            {
              p = h;
            }
        }

    }

}

void makeNull(struct myQueue* q)
{
  if(q)
    {
      while(q->head) dequeue(q);
    }

}

struct myQueue* newQueue(void)
{
  struct myQueue* p = malloc(1 * sizeof *p);
  if(NULL == p)
    {
      printf("Out of Memory\n");
      exit(EXIT_FAILURE);
    }

  return p;

}

void printQueue(struct myQueue* q)
{
  if(q)
    {
      struct myStruct* p = q->head;
      for(; p; p = p->next)  printStruct(p);
      printf("-----------------------------------------\n");
    }

}

void printStruct(struct myStruct* p)
{
  if(p)
    {
      printf("title: %d\n", p->num);
    }

}

======================== OUTPUT ==========================
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra Queue.c
[arnuld@dune C]$ ./a.out
-----------------------------------------
Empty Queue, Adding first element
Adding Element
Adding Element
Adding Element
Adding Element
Adding Element
Adding Element
title: -1
title: 100
title: 38
title: 100
title: 38
title: 9
title: 100
Click to expand...

You need to stop coding and start thinking...

I don't know what's wrong with your code (though I have strong
suspicions about the code which tries to do some special casing for
start and end of list), but if I could be bothered to investigate I'd
probably do the old "paper computer" exercise...

On a largish sheet of paper I'd draw the structure of my linked list
at the point that the removeAll function was invoked, with a box
representing each entry of the list, with the forward and back
pointers and the value stored.

I'd then draw boxes for p, d and h (horrid names for variables) and
walk through the code updating all the boxes as I went.

I don't know why you keep repeating your checking code rather than
extracting it to a "sanity_check" function. I also don't know why you
don't have a function for "remove the current entry" from the list,
but you seem to be making a big deal out of a fairly small exercise.
 
M

Mark Bluemel

void removeAllMatches(struct myQueue* q, const int num)
{ ....
      struct myStruct *p, *d, *h;
      p = d = h = NULL;
      for(h = q->head; h; h = h->next)
        {
          d = h;
          if(num == d->num)
            {
              if(num == q->head->num )
                {
                  q->head = q->head->next;
                }

              if(num == q->tail->num)
                {
                  q->tail = q->tail->next;
Click to expand...

Are you sure?
                }

              if(p)
                {
                  p->next = h->next;
                }
              free(d);
            }
Click to expand...

Your code seems messy here - how about this?

struct myStruct *previous = NULL;
struct myStruct *current;
for(current = q->head; current; current = current->next) {
if(num == current->num) {
if(current == q->head) {
q->head = q->head->next;
}
if(current == q->tail) {
q->tail = previous;
}
if(previous) {
previous->next = current->next;
}
free(current);
}
else {
previous = current;
}
}
 
J

Johann Klammer

arnuld wrote:

[SNIP]
/* Added many months later */
void removeAllMatches(struct myQueue* q, const int num)
{
if(NULL == q)
{
printf("Invalid Args\n");
return;
}

if(NULL == q->head&& NULL == q->tail)
{
printf("Queue is already empty\n");
}
else if(NULL == q->head || NULL == q->tail)
{
printf("IN: %s @%d; ", __func__, __LINE__);
printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
exit(EXIT_FAILURE);
}
else
{
struct myStruct *p, *d, *h;
p = d = h = NULL;
for(h = q->head; h; h = h->next)
{
d = h;
if(num == d->num)
{
if(num == q->head->num )
{
q->head = q->head->next;
}

if(num == q->tail->num)
{
q->tail = q->tail->next;
}

if(p)
{
p->next = h->next;
}
free(d);
Click to expand...
another
BUG:
you free() the memory pointed to by d (which is the same as h),
and in the for statement you access it: h = h->next
retrieve the next pointer _before_ you free() the element.

perhaps you should use some library for that...
glib or glibc's said:
}
else
{
p = h;
}
}

}
}
Click to expand...

[SNIP]
 
A

arnuld

I've only skimmed your code, but this bit is obviously wrong:
Click to expand...
Hint: What are the values of the elements in the newly-allocated
struct?
Click to expand...


One needs to keep on practicing writing code and thinking about data
structures, else he forgets (like me). (Now, taking dequeue code from
other poster), is this fine now or still some bits are wrong:




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


enum { CODE_SUCC = 0, CODE_ERR = 1 };


struct myStruct
{
int num;
struct myStruct* next;
};

struct myQueue
{
struct myStruct* head;
struct myStruct* tail;
};


int enqueue(struct myQueue* q, int n);
int dequeue(struct myQueue* q);

struct myQueue* newQueue(void);
void makeNull(struct myQueue* q);
void removeAllMatches(struct myQueue* q, const int num);

void printQueue(struct myQueue* q);
void printStruct(struct myStruct* p);
int queue_sanity_check(struct myQueue* q);


int main(void)
{
struct myQueue* q = newQueue();
printQueue(q);

enqueue(q, -1);
enqueue(q, 100);
enqueue(q, 38);
enqueue(q, 100);
enqueue(q, 38);
enqueue(q, 9);
enqueue(q, 100);
printQueue(q);

removeAllMatches(q, 100);
printQueue(q);
/*
makeNull(q);
printQueue(q);
free(q);
q = NULL;
*/
return 0;
}



int enqueue(struct myQueue* q, int n)
{
struct myStruct* p;
if(CODE_ERR == queue_sanity_check(q))
{
printf("IN: %s @%d: Sanity Check failed\n", __func__, __LINE__);
return CODE_ERR;
}

p = malloc(1 * sizeof *p);
if(NULL == p)
{
printf("Out of memory\n");
exit(EXIT_FAILURE);
}

p->num = n;
p->next = NULL;

if(NULL == q->tail && NULL == q->head)
{
printf("Empty Queue, Adding first element\n");
q->head = q->tail = p;
}
else
{
printf("Adding Element to tail\n");
q->tail->next = p;
q->tail = p;
}

return CODE_SUCC;
}



int dequeue(struct myQueue* q)
{
int ret = CODE_ERR;;

if(CODE_ERR == queue_sanity_check(q))
{
ret = CODE_ERR;
}

else
{
struct myStruct* h;
h = q->head;
q->head = q->head->next;
free(h);
if(NULL == q->head)
{
printf("Removing Last element left\n");
q->head = q->tail = NULL;
}
else
{
printf("Removing Some element\n");
}

ret = CODE_SUCC;
}

return ret;
}


/* Added many months later */
void removeAllMatches(struct myQueue* q, const int num)
{
struct myStruct *previous, *current;
if(CODE_ERR == queue_sanity_check(q))
{
return;
}

previous = NULL;

for(current = q->head; current; current = current->next)
{
if(num == current->num)
{
if(num == q->head->num)
{
q->head = q->head->next;
}

if(num == q->tail->num)
{
q->tail = previous;
}

if(previous)
{
previous->next = current->next;
}

free(current);
}
else
{
previous = current;
}
}
}




void makeNull(struct myQueue* q)
{
if(q)
{
while(q->head) dequeue(q);
}
}


struct myQueue* newQueue(void)
{
struct myQueue* p = malloc(1 * sizeof *p);
if(NULL == p)
{
printf("Out of Memory\n");
exit(EXIT_FAILURE);
}

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

return p;
}


void printQueue(struct myQueue* q)
{
if(q)
{
struct myStruct* p = q->head;
for(; p; p = p->next) printStruct(p);
printf("-----------------------------------------\n");
}
}


void printStruct(struct myStruct* p)
{
if(p)
{
printf("title: %d\n", p->num);
}
}


int queue_sanity_check(struct myQueue* q)
{
int ret = CODE_ERR;
if(NULL == q)
{
printf("Invalid Args\n");
ret = CODE_ERR;
}
else if(NULL == q->head && NULL == q->tail)
{
printf("Queue is already empty\n");
ret = CODE_SUCC;
}
else if(NULL == q->head || NULL == q->tail)
{
printf("IN: %s @%d; ", __func__, __LINE__);
printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
exit(EXIT_FAILURE);
}
else
{
ret = CODE_SUCC;
}

return ret;
}

================ OUTPUT =====================
/home/arnuld/programs/C $ gcc -ansi -pedantic -Wall -Wextra Queue.c
/home/arnuld/programs/C $ ./a.out
-----------------------------------------
Queue is already empty
Empty Queue, Adding first element
Adding Element to tail
Adding Element to tail
Adding Element to tail
Adding Element to tail
Adding Element to tail
Adding Element to tail
title: -1
title: 100
title: 38
title: 100
title: 38
title: 9
title: 100
 
B

Barry Schwarz

snip
One needs to keep on practicing writing code and thinking about data
structures, else he forgets (like me). (Now, taking dequeue code from
other poster), is this fine now or still some bits are wrong:




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


enum { CODE_SUCC = 0, CODE_ERR = 1 };


struct myStruct
{
int num;
struct myStruct* next;
};

struct myQueue
{
struct myStruct* head;
struct myStruct* tail;
};


int enqueue(struct myQueue* q, int n);
int dequeue(struct myQueue* q);

struct myQueue* newQueue(void);
void makeNull(struct myQueue* q);
void removeAllMatches(struct myQueue* q, const int num);

void printQueue(struct myQueue* q);
void printStruct(struct myStruct* p);
int queue_sanity_check(struct myQueue* q);


int main(void)
{
struct myQueue* q = newQueue();
printQueue(q);

enqueue(q, -1);
enqueue(q, 100);
enqueue(q, 38);
enqueue(q, 100);
enqueue(q, 38);
enqueue(q, 9);
enqueue(q, 100);
printQueue(q);

removeAllMatches(q, 100);
printQueue(q);
/*
makeNull(q);
printQueue(q);
free(q);
q = NULL;
*/
return 0;
}



int enqueue(struct myQueue* q, int n)
{
struct myStruct* p;
if(CODE_ERR == queue_sanity_check(q))
{
printf("IN: %s @%d: Sanity Check failed\n", __func__, __LINE__);
return CODE_ERR;
}

p = malloc(1 * sizeof *p);
Click to expand...

What is the point of multiplying by 1?
if(NULL == p)
{
printf("Out of memory\n");
exit(EXIT_FAILURE);
}

p->num = n;
p->next = NULL;

if(NULL == q->tail && NULL == q->head)
{
printf("Empty Queue, Adding first element\n");
q->head = q->tail = p;
}
else
{
printf("Adding Element to tail\n");
q->tail->next = p;
q->tail = p;
}

return CODE_SUCC;
}



int dequeue(struct myQueue* q)
{
int ret = CODE_ERR;;

if(CODE_ERR == queue_sanity_check(q))
{
ret = CODE_ERR;
Click to expand...

ret is already initialized to CODE_ERR.
}

else
{
struct myStruct* h;
h = q->head;
q->head = q->head->next;
Click to expand...

If q->head is NULL (the queue is empty), this invokes undefined
behavior.
free(h);
if(NULL == q->head)
{
printf("Removing Last element left\n");
q->head = q->tail = NULL;
Click to expand...

You already know q->head is NULL.
}
else
{
printf("Removing Some element\n");
}

ret = CODE_SUCC;
}

return ret;
}


/* Added many months later */
void removeAllMatches(struct myQueue* q, const int num)
{
struct myStruct *previous, *current;
if(CODE_ERR == queue_sanity_check(q))
{
return;
}

previous = NULL;
Click to expand...

Assume the queue consists of nodes containing 2, 1, 3, 1 and num is 1.
for(current = q->head; current; current = current->next)
Click to expand...

Whenever you free current in the loop, the third expression above
invokes undefined behavior on the next iteration.
{
if(num == current->num)
Click to expand...

During iteration 1, this is false.

During iteration 2, this is true.

During iteration 3, this is false.

During iteration 4, this is true.
{
if(num == q->head->num)
Click to expand...

During iteration 2, this is false.

During iteration 4, this is false.
{
q->head = q->head->next;
}

if(num == q->tail->num)
Click to expand...

During iteration 2, this is true.

During iteration 4 this is false because q->tail points to node
containing 2.
{
q->tail = previous;
Click to expand...

q->tail now points to node containing 2 which is same as q->head. Your
q is now broken.

I think the if test should be on the pointers, not on num:
if (current = q->tail)
}

if(previous)
Click to expand...

During iteration 2, this is true.

During iteration 4, this is true.
{
previous->next = current->next;
Click to expand...

The node containing 2 now points to the node containing 3.

The node containing 3 now points to NULL.
}

free(current);
}
else
{
previous = current;
Click to expand...

After iteration 1, previous points to node containing 2.

After iteration 2, previous still points to node containing 2.

After iteration 3, previous points to node containing 3.

After iteration 4, previous still points to node containing 3.
}
}
}
Click to expand...

Your queue consists of nodes containing 2 and 3 but q->head and
q->tail both point to the node containing 2.
void makeNull(struct myQueue* q)
{
Click to expand...

Why do you not call queue_sanity_check here also?
if(q)
{
while(q->head) dequeue(q);
}
}


struct myQueue* newQueue(void)
{
struct myQueue* p = malloc(1 * sizeof *p);
if(NULL == p)
{
printf("Out of Memory\n");
exit(EXIT_FAILURE);
}

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

return p;
}


void printQueue(struct myQueue* q)
{
if(q)
{
struct myStruct* p = q->head;
for(; p; p = p->next) printStruct(p);
printf("-----------------------------------------\n");
}
}


void printStruct(struct myStruct* p)
{
if(p)
{
printf("title: %d\n", p->num);
}
}


int queue_sanity_check(struct myQueue* q)
{
int ret = CODE_ERR;
if(NULL == q)
{
printf("Invalid Args\n");
ret = CODE_ERR;
}
else if(NULL == q->head && NULL == q->tail)
{
printf("Queue is already empty\n");
ret = CODE_SUCC;
}
else if(NULL == q->head || NULL == q->tail)
Click to expand...

Since you have managed to create the situation, you might also want to
add the following to the end of the if:
|| q->tail->next != NULL
{
printf("IN: %s @%d; ", __func__, __LINE__);
printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
exit(EXIT_FAILURE);
}
else
{
ret = CODE_SUCC;
}

return ret;
}

================ OUTPUT =====================
/home/arnuld/programs/C $ gcc -ansi -pedantic -Wall -Wextra Queue.c
/home/arnuld/programs/C $ ./a.out
-----------------------------------------
Queue is already empty
Empty Queue, Adding first element
Adding Element to tail
Adding Element to tail
Adding Element to tail
Adding Element to tail
Adding Element to tail
Adding Element to tail
title: -1
title: 100
title: 38
title: 100
title: 38
title: 9
title: 100
-----------------------------------------
title: -1
title: 38
title: 38
title: 9
Click to expand...

This demonstrates you don't use q->tail so why bother maintaining it?
 
G

Guest

Mine just prints forever on printQueue(). Looking at newQueue() instantly
reveals the problem.
Click to expand...

and main()
No need for any debugger. And what exactly did it say anyway?
Click to expand...

well the program has Undefined Behaviour so the question isn't really meaningful. Visual C++ gives:-

"Unhandled exception at 0x00411cc9 in quick.exe: 0xC0000005: Access violation reading location 0xcdcdcdcd."

The debugger shows it crashed in printStruct() and p has an insane value.
 
G

Guest

Mine just prints forever on printQueue(). Looking at newQueue() instantly
reveals the problem.
Click to expand...

and main()
No need for any debugger. And what exactly did it say anyway?
Click to expand...

well the program has Undefined Behaviour so the question isn't really meaningful. Visual C++ gives:-

"Unhandled exception at 0x00411cc9 in quick.exe: 0xC0000005: Access violation reading location 0xcdcdcdcd."

The debugger shows it crashed in printStruct() and p has an insane value.
 
A

arnuld

ret is already initialized to CODE_ERR.
Click to expand...

I know. I learned from someone here that assignment at initialization of
a variable is always a good idea. I see it solves problems for me (in
case of int types)

If q->head is NULL (the queue is empty), this invokes undefined
behavior.
Click to expand...

I have removed this in code I posted 2nd time.


You already know q->head is NULL.
Click to expand...

yeah. So, instead of s->head = s->tail = NULL, I could have used s->tail
= s->head. It was just a matter of style for me.




Assume the queue consists of nodes containing 2, 1, 3, 1 and num is 1.
Click to expand...
Whenever you free current in the loop, the third expression above
invokes undefined behavior on the next iteration.


During iteration 1, this is false.

During iteration 2, this is true.

During iteration 3, this is false.

During iteration 4, this is true.
..SNIP... LOTS OF CODE
Click to expand...

I am trying to understand rest of your comments
 
B

BartC

and main()


well the program has Undefined Behaviour so the question isn't really
meaningful. Visual C++ gives:-

"Unhandled exception at 0x00411cc9 in quick.exe: 0xC0000005: Access
violation reading location 0xcdcdcdcd."

The debugger shows it crashed in printStruct() and p has an insane value.
Click to expand...

As I said, when I tried it under one compiler, it just looped forever
p;rinting the same sequence of 3 or 4 values, so p (ie. q->head) presumably
had a sensible enough value.

Debuggers have their uses but are probably overkill for an obvious logic
error within the first dozen lines of execution!

When a program goes wrong a few billion statements from the start, because
of some unrelated code a billion or two statements back in a totally
different part, then it might be time to wheel it out (and even then I'm not
sure how they could help).
 
A

arnuld

..SNIP...
Click to expand...
you could tidy things up by factoring out your queue check code that
appears in at least three places
Click to expand...

you are right. I did that and now after reading the analysis from Barry
Schwarz I can see that head/tail pointing at wrong places, so I should
make a check for that too ?

No, unlike earlier now I think those checks will not save these
programming errors I am making. I better set pointers right rather than
spending my typing-energy to avoid/find errors.
 
G

Guest

As I said, when I tried it under one compiler, it just looped forever
p;rinting the same sequence of 3 or 4 values, so p (ie. q->head) presumably
had a sensible enough value.

Debuggers have their uses but are probably overkill for an obvious logic
error within the first dozen lines of execution!
Click to expand...

and how would I know the crash was going to occur within a few dozen lines of startup?
When a program goes wrong a few billion statements from the start, because
of some unrelated code a billion or two statements back in a totally
different part, then it might be time to wheel it out (and even then I'm not
sure how they could help).
Click to expand...

whatever. I judged running under a debugger was a quicker way to find the bug than ploughing through lots of source code. It so happened it pin-pointed the bug almost instantly.
 
J

James Kuyper

I know. I learned from someone here that assignment at initialization of
a variable is always a good idea. I see it solves problems for me (in
case of int types)
Click to expand...

I disagree, but that's a controversial opinion, and I won't bother
arguing it again. However, since you've already initialized it to
CODE_ERR, there's no need to set it to that value a second time.

....
yeah. So, instead of s->head = s->tail = NULL, I could have used s->tail
= s->head. It was just a matter of style for me.
Click to expand...

or s->tail = NULL, which is even simpler.
 
A

arnuld

What is the point of multiplying by 1?
Click to expand...

Because it makes me remember that malloc() takes number of elements. It
sounds strange but I do forget to add number of elements most of the
times.


Assume the queue consists of nodes containing 2, 1, 3, 1 and num is 1.
Click to expand...
Whenever you free current in the loop, the third expression above
invokes undefined behavior on the next iteration.
Click to expand...

It did not. Now I know why. After free(current), current may be pointing
to garbage. That's why the practice of setting the pointer to NULL after
free() was created.

Oddly, code worked fine all the time on my machine producing correct
results for 8 hours. Just now it Segfaulted.


q->tail now points to node containing 2 which is same as q->head. Your q
is now broken.
Click to expand...

It is broke, Still trying to figure out how to write it correctly.

I think the if test should be on the pointers, not on num:
if (current = q->tail)
Click to expand...

aah... pointers do compare equal like int
(you meant current == q->tail)


Since you have managed to create the situation, you might also want to
add the following to the end of the if:
|| q->tail->next != NULL
Click to expand...

I understood my mistake. Like I said, I did the analysis after reading
your analysis I can see that head/tail pointing at wrong places, so I
should make a check for that too ? No, unlike earlier now I think those
checks will not save these programming errors I am making. I better set
pointers right rather than spending my typing-energy to avoid/find errors.


This demonstrates you don't use q->tail so why bother maintaining it?
Click to expand...

q->tail to add, q->head to remove. Thats the purpose.
 
B

Barry Schwarz

Because it makes me remember that malloc() takes number of elements. It
sounds strange but I do forget to add number of elements most of the
times.
Click to expand...

Better to remember something true. malloc takes number of bytes.
calloc takes number of elements and number of bytes per element but
involves extra overhead which is not needed here.
It did not. Now I know why. After free(current), current may be pointing
to garbage. That's why the practice of setting the pointer to NULL after
free() was created.
Click to expand...

After free(current), current is indeterminate and doesn't point
anywhere. Whether or not you set current to NULL after the free, any
attempt to dereference current, as in the expression current->next,
invokes undefined behavior.
Oddly, code worked fine all the time on my machine producing correct
results for 8 hours. Just now it Segfaulted.
Click to expand...

Consider yourself lucky. Frequently undefined behavior waits until an
important customer is present for the demo.
It is broke, Still trying to figure out how to write it correctly.



aah... pointers do compare equal like int
(you meant current == q->tail)
Click to expand...

Yes, I make this mistake more often than I care to admit.
I understood my mistake. Like I said, I did the analysis after reading
your analysis I can see that head/tail pointing at wrong places, so I
should make a check for that too ? No, unlike earlier now I think those
checks will not save these programming errors I am making. I better set
pointers right rather than spending my typing-energy to avoid/find errors.




q->tail to add, q->head to remove. Thats the purpose.
Click to expand...

True. I apologize for my excess sarcasm.
 
G

Guest

no. The parameter is the number of bytes (chars)
calloc() = malloc() + memset() ??
Click to expand...

depends what your "+" ooperator does! Note calloc() allocates an array of elements. But I'm sure most implementations of calloc() call malloc() (or both call some internal allocator)

<snip>
 
8

88888 Dihedral

arnuldæ–¼ 2012å¹´5月8日星期二UTC+8下åˆ4時09分39秒寫é“：
WANTED: Removing all elements matching a particular key from a Queue
WHAT I GOT: Segfault
WANTED: Segfaults in removeAllMatches(). I think routine/fucntion is too
complex to be understood. removeAllMatches(arg1, arg2) is supposed to
remove all elements from arg1 which match value of arg2.




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

struct myStruct
{
int num;
struct myStruct* next;
};

struct myQueue
{
struct myStruct* head;
struct myStruct* tail;
};


int enqueue(struct myQueue* q, int n);
int dequeue(struct myQueue* q);

struct myQueue* newQueue(void);
void makeNull(struct myQueue* q);
void removeAllMatches(struct myQueue* q, const int num);

void printQueue(struct myQueue* q);
void printStruct(struct myStruct* p);



int main(void)
{
struct myQueue* q = newQueue();
printQueue(q);

enqueue(q, -1);
enqueue(q, 100);
enqueue(q, 38);
enqueue(q, 100);
enqueue(q, 38);
enqueue(q, 9);
enqueue(q, 100);
printQueue(q);

removeAllMatches(q, 100);
printQueue(q);
/* makeNull(q);
printQueue(q); */
free(q);
q = NULL;

return 0;
}



int enqueue(struct myQueue* q, int n)
{
int ret;
if(NULL == q)
{
printf("Invalid Args\n");
ret = -1;
}
else
{
struct myStruct* p = malloc(1 * sizeof *p);
if(NULL == p)
{
printf("Out of memory\n");
exit(EXIT_FAILURE);
}

p->num = n;
p->next = NULL;
if(NULL == q->tail && NULL == q->head)
{
printf("Empty Queue, Adding first element\n");
q->head = q->tail = p;
ret = 0;
}
else if(NULL == q->tail || NULL == q->head)
{
printf("IN: %s @%d; ", __func__, __LINE__);
printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
free(p);
ret = 1;
}
else
{
printf("Adding Element\n");
q->tail->next = p;
q->tail = p;
ret = 0;
}
}

return ret;
}



int dequeue(struct myQueue* q)
{
int ret = -1;
if(NULL == q)
{
printf("Invalid Args\n");
ret = -1;
}
else
{
struct myStruct* h;
if(NULL == q->head && NULL == q->tail)
{
printf("Queue is already empty\n");
ret = 0;
}
else if(NULL == q->head || NULL == q->tail)
{
printf("IN: %s @%d; ", __func__, __LINE__);
printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
ret = 1;
}
else
{
h = q->head;
q->head = q->head->next;
free(h);
if(NULL == q->head)
{
printf("Removing Last element left\n");
q->head = q->tail = NULL;
}
else
{
printf("Removing Some element\n");
}
ret = 0;
}
}

return ret;
}


/* Added many months later */
void removeAllMatches(struct myQueue* q, const int num)
{
if(NULL == q)
{
printf("Invalid Args\n");
return;
}

if(NULL == q->head && NULL == q->tail)
{
printf("Queue is already empty\n");
}
else if(NULL == q->head || NULL == q->tail)
{
printf("IN: %s @%d; ", __func__, __LINE__);
printf("There is something seriously wrong with head/tail
assignment of your Queue\n");
exit(EXIT_FAILURE);
}
else
{
struct myStruct *p, *d, *h;
p = d = h = NULL;
for(h = q->head; h; h = h->next)
{
d = h;
if(num == d->num)
{
if(num == q->head->num )
{
q->head = q->head->next;
}

if(num == q->tail->num)
{
q->tail = q->tail->next;
}

if(p)
{
p->next = h->next;
}
free(d);
}
else
{
p = h;
}
}

}
}




void makeNull(struct myQueue* q)
{
if(q)
{
while(q->head) dequeue(q);
}
}



struct myQueue* newQueue(void)
{
struct myQueue* p = malloc(1 * sizeof *p);
if(NULL == p)
{
printf("Out of Memory\n");
exit(EXIT_FAILURE);
}

return p;
}


void printQueue(struct myQueue* q)
{
if(q)
{
struct myStruct* p = q->head;
for(; p; p = p->next) printStruct(p);
printf("-----------------------------------------\n");
}
}


void printStruct(struct myStruct* p)
{
if(p)
{
printf("title: %d\n", p->num);
}
}

======================== OUTPUT ==========================
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra Queue.c
[arnuld@dune C]$ ./a.out
-----------------------------------------
Empty Queue, Adding first element
Adding Element
Adding Element
Adding Element
Adding Element
Adding Element
Adding Element
title: -1
title: 100
title: 38
title: 100
title: 38
title: 9
title: 100
Click to expand...

I checked your code that I assume it requires not only the standard
operations of a queue.

I suggest you should use a link list.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Queue in C 25
Queue - can not delete last element 6
Queue in C 0
Thread-Safe Generic List Queue in C 7
dequeue() not working 9
A Queue implementation of doubly linked list in C 44
pointer vs pointer to pointer 4
A car garage simulation using de-queue (link list implementation) 0

Members online

No members online now.
Total: 33 (members: 0, guests: 33)
Robots: 342

Forum statistics

Threads
473,769
Messages
2,569,582
Members
45,065
Latest member
OrderGreenAcreCBD

Latest Threads

Top