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 ==========================
[[email protected] C]$ gcc -ansi -pedantic -Wall -Wextra Queue.c
[[email protected] 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
 
Ad

Advertisements

E

Eric Sosman

WANTED: [...]

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;
}

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.

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;

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");
}
}

======================== OUTPUT ==========================
[[email protected] C]$ gcc -ansi -pedantic -Wall -Wextra Queue.c
[[email protected] 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

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.
Why didn't you use a debugger? That's how I found the bug.

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 ==========================
[[email protected] C]$ gcc -ansi -pedantic -Wall -Wextra Queue.c
[[email protected] 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

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;

Are you sure?
                }

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

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;
}
}
 
Ad

Advertisements

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);
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;
}
}

}
}

[SNIP]
 
A

arnuld

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


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);

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;

ret is already initialized to CODE_ERR.
}

else
{
struct myStruct* h;
h = q->head;
q->head = q->head->next;

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;

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;

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

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

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)

During iteration 2, this is false.

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

if(num == q->tail->num)

During iteration 2, this is true.

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

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)

During iteration 2, this is true.

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

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

The node containing 3 now points to NULL.
}

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

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.

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)
{

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)

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

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.

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

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.

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

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.
 
Ad

Advertisements

A

arnuld

ret is already initialized to CODE_ERR.

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.

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


You already know q->head is NULL.

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.
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

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.

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...
you could tidy things up by factoring out your queue check code that
appears in at least three places

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!

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).

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)

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.

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

Advertisements

A

arnuld

What is the point of multiplying by 1?

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.
Whenever you free current in the loop, the third expression above
invokes undefined behavior on the next iteration.

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.

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)

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

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?

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.

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.

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.

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)

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.

True. I apologize for my excess sarcasm.
 
G

Guest

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

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>
 
Ad

Advertisements

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 ==========================
[[email protected] C]$ gcc -ansi -pedantic -Wall -Wextra Queue.c
[[email protected] 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

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


Top