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

Groups > comp.lang.c > #20494 > unrolled thread

Remving an element from Queue

Back to article view | Back to comp.lang.c

Contents

  Remving an element from Queue arnuld <sunrise@invalid.address> - 2012-05-08 08:09 +0000
    Re: Remving an element from Queue Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-05-08 08:01 -0400
      Re: Remving an element from Queue arnuld <sunrise@invalid.address> - 2012-05-09 05:43 +0000
        Re: Remving an element from Queue Barry Schwarz <schwarzb@dqel.com> - 2012-05-08 23:21 -0700
          Re: Remving an element from Queue arnuld <sunrise@invalid.address> - 2012-05-09 09:27 +0000
            Re: Remving an element from Queue James Kuyper <jameskuyper@verizon.net> - 2012-05-09 07:54 -0400
          Re: Remving an element from Queue arnuld <sunrise@invalid.address> - 2012-05-09 13:18 +0000
            Re: Remving an element from Queue Barry Schwarz <schwarzb@dqel.com> - 2012-05-09 10:59 -0700
              Re: Remving an element from Queue arnuld <arnuld.mizong@gmail.com> - 2012-05-10 05:26 -0700
                Re: Remving an element from Queue nick_keighley_nospam@hotmail.com - 2012-05-11 00:11 -0700
                Re: Remving an element from Queue Barry Schwarz <schwarzb@dqel.com> - 2012-05-14 15:53 -0700
                  Re: Remving an element from Queue lawrence.jones@siemens.com - 2012-05-15 17:42 -0400
                    Re: Remving an element from Queue Barry Schwarz <schwarzb@dqel.com> - 2012-05-15 16:40 -0700
                      Re: Remving an element from Queue James Kuyper <jameskuyper@verizon.net> - 2012-05-15 23:03 -0400
                        Re: Remving an element from Queue Barry Schwarz <schwarzb@dqel.com> - 2012-05-15 20:38 -0700
                          Re: Remving an element from Queue Jens Gustedt <jens.gustedt@loria.fr> - 2012-05-16 08:09 +0200
                          Re: Remving an element from Queue James Kuyper <jameskuyper@verizon.net> - 2012-05-16 07:18 -0400
                            Re: Remving an element from Queue Barry Schwarz <schwarzb@dqel.com> - 2012-05-16 16:30 -0700
                              Re: Remving an element from Queue James Kuyper <jameskuyper@verizon.net> - 2012-05-17 09:09 -0400
                                Re: Remving an element from Queue Barry Schwarz <schwarzb@dqel.com> - 2012-05-17 11:48 -0700
                                  Re: Removing an element from Queue James Kuyper <jameskuyper@verizon.net> - 2012-05-17 15:38 -0400
                                    Re: Removing an element from Queue Barry Schwarz <schwarzb@dqel.com> - 2012-05-17 15:21 -0700
                                      Re: Removing an element from Queue James Kuyper <jameskuyper@verizon.net> - 2012-05-17 19:08 -0400
                                        Re: Removing an element from Queue Tim Rentsch <txr@alumni.caltech.edu> - 2012-05-19 09:05 -0700
                                          Re: Removing an element from Queue lawrence.jones@siemens.com - 2012-05-20 15:10 -0400
                                            Re: Removing an element from Queue Tim Rentsch <txr@alumni.caltech.edu> - 2012-05-21 09:00 -0700
                              Re: Remving an element from Queue Tim Rentsch <txr@alumni.caltech.edu> - 2012-05-19 08:49 -0700
                          Re: Remving an element from Queue Tim Rentsch <txr@alumni.caltech.edu> - 2012-05-17 12:36 -0700
    Re: Remving an element from Queue nick_keighley_nospam@hotmail.com - 2012-05-08 05:09 -0700
      Re: Remving an element from Queue "BartC" <bc@freeuk.com> - 2012-05-08 14:03 +0100
        Re: Remving an element from Queue nick_keighley_nospam@hotmail.com - 2012-05-09 00:01 -0700
        Re: Remving an element from Queue nick_keighley_nospam@hotmail.com - 2012-05-09 00:03 -0700
          Re: Remving an element from Queue "BartC" <bc@freeuk.com> - 2012-05-09 10:37 +0100
            Re: Remving an element from Queue nick_keighley_nospam@hotmail.com - 2012-05-09 03:05 -0700
      Re: Remving an element from Queue arnuld <sunrise@invalid.address> - 2012-05-09 09:44 +0000
    Re: Remving an element from Queue Mark Bluemel <mark.bluemel@googlemail.com> - 2012-05-08 06:07 -0700
    Re: Remving an element from Queue Mark Bluemel <mark.bluemel@googlemail.com> - 2012-05-08 06:35 -0700
    Re: Remving an element from Queue Johann Klammer <klammerj@NOSPAM.a1.net> - 2012-05-08 20:50 +0200
    Re: Remving an element from Queue 88888 Dihedral <dihedral88888@googlemail.com> - 2012-05-11 00:39 -0700

Page 1 of 2  [1] 2  Next page →

#20494 — Remving an element from Queue

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
-----------------------------------------
Segmentation fault
[arnuld@dune C]$ 





-- 
 arnuld
http://LispMachine.Wordpress.com

[toc] | [next] | [standalone]

#20502

On 5/8/2012 4:09 AM, arnuld wrote:
> 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?

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#20533

> On Tue, 08 May 2012 08:01:26 -0400, Eric Sosman wrote:

>> On 5/8/2012 4:09 AM, arnuld wrote:
 
>      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?


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
-----------------------------------------
title: -1
title: 38
title: 38
title: 9
-----------------------------------------
/home/arnuld/programs/C $ 


-- 
 arnuld
http://LispMachine.Wordpress.com

[toc] | [prev] | [next] | [standalone]

#20535

On 09 May 2012 05:43:02 GMT, arnuld <sunrise@invalid.address> wrote:

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?

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#20540

> On Tue, 08 May 2012 23:21:06 -0700, Barry Schwarz wrote:

>> On 09 May 2012 05:43:02 GMT, arnuld <sunrise@invalid.address> wrote:
 
> 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)

 
>>      struct myStruct* h;
>>      h = q->head;
>>      q->head = q->head->next;
 
> If q->head is NULL (the queue is empty), this invokes undefined
> behavior.

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



>>      free(h);
>>      if(NULL == q->head)
>>	{
>>	  printf("Removing Last element left\n"); q->head = q->tail = 
> NULL;
 
> 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.
> 
>>  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.
> ..SNIP... LOTS OF CODE

I am trying to understand rest of your comments




-- 
 arnuld
http://LispMachine.Wordpress.com

[toc] | [prev] | [next] | [standalone]

#20545

On 05/09/2012 05:27 AM, arnuld wrote:
>> On Tue, 08 May 2012 23:21:06 -0700, Barry Schwarz wrote:
> 
>>> On 09 May 2012 05:43:02 GMT, arnuld <sunrise@invalid.address> wrote:
>  
>> 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)

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.

...
>>>      if(NULL == q->head)
>>> 	{
>>> 	  printf("Removing Last element left\n"); q->head = q->tail = 
>> NULL;
>  
>> 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.

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

[toc] | [prev] | [next] | [standalone]

#20546

> On Tue, 08 May 2012 23:21:06 -0700, Barry Schwarz wrote:

>> On 09 May 2012 05:43:02 GMT, arnuld <sunrise@invalid.address> wrote:

>>  p = malloc(1 * sizeof *p);
 
> 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.
> 
>>  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.

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.






-- 
 arnuld
http://LispMachine.Wordpress.com

[toc] | [prev] | [next] | [standalone]

#20548

On 09 May 2012 13:18:08 GMT, arnuld <sunrise@invalid.address> wrote:

>> On Tue, 08 May 2012 23:21:06 -0700, Barry Schwarz wrote:
>
>>> On 09 May 2012 05:43:02 GMT, arnuld <sunrise@invalid.address> wrote:
>
>>>  p = malloc(1 * sizeof *p);
> 
>> 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. 

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.

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

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

Yes, I make this mistake more often than I care to admit.

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

True.  I apologize for my excess sarcasm.

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#20740

> On May 9, 10:59 pm, Barry Schwarz <schwa...@dqel.com> wrote:
>> On 09 May 2012 13:18:08 GMT, arnuld <sunr...@invalid.address> wrote:

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

calloc() = malloc() + memset() ??




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


understood very well.




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

> True.  I apologize for my excess sarcasm.

ah.. cmon Barry. I liked your sarcasm, especially this one:

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


Becaus of that I realized my checks were stupid. Checks are good but
not the ones I am doing , they are programming errors. Still can't
figure out how to remove an element from queue :\



>
> --
> Remove del for email

[toc] | [prev] | [next] | [standalone]

#20745

On Thursday, May 10, 2012 1:26:52 PM UTC+1, arnuld wrote:
> > On May 9, 10:59 pm, Barry Schwarz <schwa...@dqel.com> wrote:
> >> On 09 May 2012 13:18:08 GMT, arnuld <sunr...@invalid.address> wrote:

> >>Because it makes me remember that malloc() takes number of elements.

no. The parameter is the number of bytes (chars)

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

[toc] | [prev] | [next] | [standalone]

#20770

On Thu, 10 May 2012 05:26:52 -0700 (PDT), arnuld
<arnuld.mizong@gmail.com> wrote:

>> 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.
>
>calloc() = malloc() + memset() ??

As long as malloc doesn't fail,
    calloc(a,b) = memset(malloc(a*b),0,a*b)

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#20833

Barry Schwarz <schwarzb@dqel.com> wrote:
> 
> As long as malloc doesn't fail,

And a*b doesn't overflow,

>     calloc(a,b) = memset(malloc(a*b),0,a*b)
-- 
Larry Jones

Something COULD happen today.  And if anything DOES,
by golly, I'm going to be ready for it! -- Calvin

[toc] | [prev] | [next] | [standalone]

#20839

On Tue, 15 May 2012 17:42:46 -0400, lawrence.jones@siemens.com wrote:

>Barry Schwarz <schwarzb@dqel.com> wrote:
>> 
>> As long as malloc doesn't fail,
>
>And a*b doesn't overflow,
>
>>     calloc(a,b) = memset(malloc(a*b),0,a*b)

Unsigned arithmetic cannot overflow.

Given the wording in 7.20.3.1, where the allocated space constitutes a
single array, I have no idea what happens when the arithmetic product
a*b exceeds the value of SIZE_MAX.  Under such conditions I believe
calloc should fail and return NULL but the memset expression above is
under no such obligation.

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#20843

On 05/15/2012 07:40 PM, Barry Schwarz wrote:
> On Tue, 15 May 2012 17:42:46 -0400, lawrence.jones@siemens.com wrote:
> 
>> Barry Schwarz <schwarzb@dqel.com> wrote:
>>>
>>> As long as malloc doesn't fail,
>>
>> And a*b doesn't overflow,
>>
>>>     calloc(a,b) = memset(malloc(a*b),0,a*b)
> 
> Unsigned arithmetic cannot overflow.
> 
> Given the wording in 7.20.3.1, where the allocated space constitutes a
> single array, I have no idea what happens when the arithmetic product
> a*b exceeds the value of SIZE_MAX. ...

calloc(a,b) must either return a pointer to enough memory to store 'a'
objects, each of size 'b' bytes, or a null pointer. If the mathematical
product of a*b is greater than SIZE_MAX, then (size_t)(a*b) bytes will
not be sufficient to meet that requirement - but the requirement still
holds. Therefore, calloc(a,b) must either return a null pointer, or
allocate sufficient memory by some mechanism other than malloc(a*b).
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#20844

On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
<jameskuyper@verizon.net> wrote:

>On 05/15/2012 07:40 PM, Barry Schwarz wrote:
>> On Tue, 15 May 2012 17:42:46 -0400, lawrence.jones@siemens.com wrote:
>> 
>>> Barry Schwarz <schwarzb@dqel.com> wrote:
>>>>
>>>> As long as malloc doesn't fail,
>>>
>>> And a*b doesn't overflow,
>>>
>>>>     calloc(a,b) = memset(malloc(a*b),0,a*b)
>> 
>> Unsigned arithmetic cannot overflow.
>> 
>> Given the wording in 7.20.3.1, where the allocated space constitutes a
>> single array, I have no idea what happens when the arithmetic product
>> a*b exceeds the value of SIZE_MAX. ...
>
>calloc(a,b) must either return a pointer to enough memory to store 'a'
>objects, each of size 'b' bytes, or a null pointer. If the mathematical
>product of a*b is greater than SIZE_MAX, then (size_t)(a*b) bytes will
>not be sufficient to meet that requirement - but the requirement still
>holds. Therefore, calloc(a,b) must either return a null pointer, or
>allocate sufficient memory by some mechanism other than malloc(a*b).

That is not what the standard says - "The calloc function allocates
space for an array of nmemb objects, each of whose size is size. The
space is initialized to all bits zero."  Note the additional
requirement that the entire allocated space be considered a single
array.  size_t must be able to hold the size in bytes of the largest
possible object, including aggregates such as arrays.  When a*b is
mathematically larger then SIZE_MAX, a "successful" call to calloc
would violate this requirement.  Therefore, calloc should be required
to return NULL in this case, which is what I said in the part you
snipped.


-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#20846

Am 16.05.2012 05:38, schrieb Barry Schwarz:
> That is not what the standard says - "The calloc function allocates
> space for an array of nmemb objects, each of whose size is size. The
> space is initialized to all bits zero."  Note the additional
> requirement that the entire allocated space be considered a single
> array.  size_t must be able to hold the size in bytes of the largest
> possible object, including aggregates such as arrays.  When a*b is
> mathematically larger then SIZE_MAX, a "successful" call to calloc
> would violate this requirement.  Therefore, calloc should be required
> to return NULL in this case, which is what I said in the part you
> snipped.

I can't find any text in the standard about size_t that requires
this. The only requirement is that the type must be able to hold the
value of the sizeof operator. This restricts the possible size only
for objects to which that operator applies, in particular it
constrains the possible size of VLA (as a function of the size of the
base type).

But since objects allocated by the "alloc" family of functions are not
subject to the sizeof operator, this restriction doesn't seem to
apply. To me, the only implicit bound for calloc seems to be

 (SIZE_MAX + 1)*(SIZE_MAX + 1)-1

Jens

[toc] | [prev] | [next] | [standalone]

#20852

On 05/15/2012 11:38 PM, Barry Schwarz wrote:
> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
> <jameskuyper@verizon.net> wrote:
...
>> calloc(a,b) must either return a pointer to enough memory to store 'a'
>> objects, each of size 'b' bytes, or a null pointer. If the mathematical
>> product of a*b is greater than SIZE_MAX, then (size_t)(a*b) bytes will
>> not be sufficient to meet that requirement - but the requirement still
>> holds. Therefore, calloc(a,b) must either return a null pointer, or
>> allocate sufficient memory by some mechanism other than malloc(a*b).

...
> array.  size_t must be able to hold the size in bytes of the largest
> possible object, including aggregates such as arrays.

Citation, please?

"sizeof(type)" must yield the size of the specified type, "sizeof
expression" must yield the size of the type of the specified
expression(6.5.3.4p2), and in either case that value must be have the
type size_t (6.5.3.4p5). This does NOT add up to the requirement you state.

Consider an implementation with the following characteristics:
1. It rejects all code that specifies any type with a size greater than
SIZE_MAX, as exceeding that implementation's limits. If it were not
permissible for a conforming implementation to reject such code, every
implementation would be rendered non-conforming by it's inability to
yield the required results for the expression sizeof(char[SIZE_MAX][2]).
2. calloc(a,b) can, at least for some values of a and b, return a
non-null pointer which points at an array of a objects of size b, even
if such an array requires more than SIZE_MAX bytes.

It follows that on such an implementation, it's not possible to write an
expression of the form sizeof(object) that would be required by the
standard to yield the size of the array pointed at by the value returned
by such a call to calloc(). Any such expression would necessarily
require casting that pointer to point at a type with a size larger than
SIZE_MAX, and as such would be rejected by that compiler.

What requirement of the standard would be violated by such an
implementation?

Let me explain that more specifically. If you can declare a pointer p
such that

	p = calloc(a,b);
	size_t size = sizeof(*p);

would violate the requirements of 6.5.3.4 if calloc() returned a
non-null pointer for a*b>SIZE_MAX, then it would ALSO violate those
requirements if calloc() returned a null pointer. That's because the
value of sizeof(*p) depends only upon the type of 'p', not the value of
p. Therefore, you cannot use 6.5.3.4 to derive a requirement that
calloc() return a null pointer.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#20869

On Wed, 16 May 2012 07:18:35 -0400, James Kuyper
<jameskuyper@verizon.net> wrote:

>On 05/15/2012 11:38 PM, Barry Schwarz wrote:
>> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
>> <jameskuyper@verizon.net> wrote:
>...
>>> calloc(a,b) must either return a pointer to enough memory to store 'a'
>>> objects, each of size 'b' bytes, or a null pointer. If the mathematical
>>> product of a*b is greater than SIZE_MAX, then (size_t)(a*b) bytes will
>>> not be sufficient to meet that requirement - but the requirement still
>>> holds. Therefore, calloc(a,b) must either return a null pointer, or
>>> allocate sufficient memory by some mechanism other than malloc(a*b).
>
>...
>> array.  size_t must be able to hold the size in bytes of the largest
>> possible object, including aggregates such as arrays.
>
>Citation, please?

K&R II, page 135, a stand-alone unindented paragraph approximately 1/3
of the way down the page: "C provides a compile-time unary operator
called sizeof that can be used to compute the size of any object."

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

#20898

On 05/16/2012 07:30 PM, Barry Schwarz wrote:
> On Wed, 16 May 2012 07:18:35 -0400, James Kuyper
> <jameskuyper@verizon.net> wrote:
> 
>> On 05/15/2012 11:38 PM, Barry Schwarz wrote:
>>> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
>>> <jameskuyper@verizon.net> wrote:
>> ...
>>>> calloc(a,b) must either return a pointer to enough memory to store 'a'
>>>> objects, each of size 'b' bytes, or a null pointer. If the mathematical
>>>> product of a*b is greater than SIZE_MAX, then (size_t)(a*b) bytes will
>>>> not be sufficient to meet that requirement - but the requirement still
>>>> holds. Therefore, calloc(a,b) must either return a null pointer, or
>>>> allocate sufficient memory by some mechanism other than malloc(a*b).
>>
>> ...
>>> array.  size_t must be able to hold the size in bytes of the largest
>>> possible object, including aggregates such as arrays.
>>
>> Citation, please?
> 
> K&R II, page 135, a stand-alone unindented paragraph approximately 1/3
> of the way down the page: "C provides a compile-time unary operator
> called sizeof that can be used to compute the size of any object."
> 

K&R II is not authoritative. The C standard is. K&R II often says things
less precisely than the standard. Please cite a corresponding
requirement from the standard. n1570.pdf
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf> is the last
publicly available draft of the current standard, and is authoritative
enough for this discussion.

Also note that the words you cite from K&R II are not, in themselves,
sufficient to support your position. "can be used to compute" doesn't
require that the computation be carried out using size_t. If it were in
fact an authoritative requirement, it would not impose a constraint on
SIZE_MAX; it only indirectly constrains either UINTMAX_MAX or LDBL_MAX,
whichever is larger. For example:

	char (*)p[SIZE_MAX] = calloc(2, SIZE_MAX);
	long double size = 2.0L*sizeof *p;

In that code, sizeof was indeed used to calculate the size of the object
(unless calloc() failed, in which case there is no object, but the size
calculation is unaffected by that fact).
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#20925

On Thu, 17 May 2012 09:09:12 -0400, James Kuyper
<jameskuyper@verizon.net> wrote:

>On 05/16/2012 07:30 PM, Barry Schwarz wrote:
>> On Wed, 16 May 2012 07:18:35 -0400, James Kuyper
>> <jameskuyper@verizon.net> wrote:
>> 
>>> On 05/15/2012 11:38 PM, Barry Schwarz wrote:
>>>> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
>>>> <jameskuyper@verizon.net> wrote:
>>> ...
>>>>> calloc(a,b) must either return a pointer to enough memory to store 'a'
>>>>> objects, each of size 'b' bytes, or a null pointer. If the mathematical
>>>>> product of a*b is greater than SIZE_MAX, then (size_t)(a*b) bytes will
>>>>> not be sufficient to meet that requirement - but the requirement still
>>>>> holds. Therefore, calloc(a,b) must either return a null pointer, or
>>>>> allocate sufficient memory by some mechanism other than malloc(a*b).
>>>
>>> ...
>>>> array.  size_t must be able to hold the size in bytes of the largest
>>>> possible object, including aggregates such as arrays.
>>>
>>> Citation, please?
>> 
>> K&R II, page 135, a stand-alone unindented paragraph approximately 1/3
>> of the way down the page: "C provides a compile-time unary operator
>> called sizeof that can be used to compute the size of any object."
>> 
>
>K&R II is not authoritative. The C standard is. K&R II often says things
>less precisely than the standard. 

Yes.  And it's also been superceded by at least two standards.  It
just happens to be the clearest description of what the inventors of
the language intended.  And percentage wise, very little has actually
been superceded.

>
>Also note that the words you cite from K&R II are not, in themselves,
>sufficient to support your position. "can be used to compute" doesn't
>require that the computation be carried out using size_t. If it were in

Regardless of how the computation is carried out, the result must fit
in a size_t.

>fact an authoritative requirement, it would not impose a constraint on
>SIZE_MAX; it only indirectly constrains either UINTMAX_MAX or LDBL_MAX,
>whichever is larger. For example:

There is no requirement that size_t be the widest possible unsigned
type.  Surely SIZE_MAX cannot exceed UINTMAX_MAX.  I don't understand
how UINTMAX_MAX enters into this discussion.

>
>	char (*)p[SIZE_MAX] = calloc(2, SIZE_MAX);
>	long double size = 2.0L*sizeof *p;
>
>In that code, sizeof was indeed used to calculate the size of the object
>(unless calloc() failed, in which case there is no object, but the size
>calculation is unaffected by that fact).

While it is not very likely, it is possible for SIZE_MAX to exceed
LDBL_MAX (1E37 bytes is a large object and size_t would need to be in
excess of 120 bits).  In that case, the implicit conversion in your
multiplication invokes undefined behavior (6.3.1.4-2).  But there are
lots of sound mathematical expressions which cannot be performed in "C
arithmetic" due to these kinds of constraints.

My only assertion was that since the result of calloc(a,b) is to be
treated as a single array, calloc should fail if a*b mathematically
exceeds SIZE_MAX.  I didn't address whether SIZE_MAX could be
converted to a real floating type or any other integer type (though it
seems obvious it should be convertible to a uintmax_t).

The wording is unchanged in n1570.

-- 
Remove del for email

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web