Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Remving an element from Queue
161 views
Skip to first unread message
arnuld
May 8, 2012, 4:09:39 AM5/8/12
to
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
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
Eric Sosman
May 8, 2012, 8:01:26 AM5/8/12
to
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
eso...@ieee-dot-org.invalid
> 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;
> }
struct?
--
Eric Sosman
eso...@ieee-dot-org.invalid
nick_keigh...@hotmail.com
May 8, 2012, 8:09:09 AM5/8/12
to
On Tuesday, May 8, 2012 9:09:39 AM UTC+1, arnuld wrote:
> 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.
> 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.
Why didn't you use a debugger? That's how I found the bug.
<code>
[...]
> struct myQueue
> {
> struct myStruct* head;
> struct myStruct* tail;
> };
[...]
> {
> struct myStruct* head;
> struct myStruct* tail;
> };
> int main(void)
> {
> struct myQueue* q = newQueue();
> printQueue(q); <--- DIE!
> {
> struct myQueue* q = newQueue();
>
> 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?
> {
> 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");
> }
> }
>
> ======================== 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]$
BartC
May 8, 2012, 9:03:48 AM5/8/12
to
<nick_keigh...@hotmail.com> wrote in message
news:27603720.623.1336478949976.JavaMail.geo-discussion-forums@vbcm9...
> On Tuesday, May 8, 2012 9:09:39 AM UTC+1, arnuld wrote:
>
>> 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.
Mine just prints forever on printQueue(). Looking at newQueue() instantly
>
>> 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.
reveals the problem.
No need for any debugger. And what exactly did it say anyway?
--
Bartc
Mark Bluemel
May 8, 2012, 9:07:41 AM5/8/12
to
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.
Mark Bluemel
May 8, 2012, 9:35:30 AM5/8/12
to
On May 8, 9:09 am, arnuld <sunr...@invalid.address> wrote:
> 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?
> 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);
> }
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;
}
}
Johann Klammer
May 8, 2012, 2:50:26 PM5/8/12
to
arnuld wrote:
[SNIP]
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 <search.h> perhaps...
> }
> else
> {
> p = h;
> }
> }
>
> }
> }
>
[SNIP]
[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)
> void removeAllMatches(struct myQueue* q, const int num)
> {
> if(NULL == q)
> {
> printf("Invalid Args\n");
> return;
> }
>
> {
> 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
> 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);
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 <search.h> perhaps...
> }
> else
> {
> p = h;
> }
> }
>
> }
> }
>
[SNIP]
arnuld
May 9, 2012, 1:43:02 AM5/9/12
to
> 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
>> 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?
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 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);
q = NULL;
*/
return 0;
}
int enqueue(struct myQueue* q, int n)
{
struct myStruct* p;
}
int enqueue(struct myQueue* q, int n)
{
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)
{
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
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;
}
{
printf("Adding Element to tail\n");
q->tail->next = p;
q->tail = p;
}
return CODE_SUCC;
q->tail = p;
}
}
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;
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");
}
}
return ret;
}
/* Added many months later */
void removeAllMatches(struct myQueue* q, const int num)
{
struct myStruct *previous, *current;
return ret;
}
/* Added many months later */
void removeAllMatches(struct myQueue* q, const int num)
{
if(CODE_ERR == queue_sanity_check(q))
{
return;
}
previous = NULL;
for(current = q->head; current; current = current->next)
{
{
if(num == q->head->num)
{
q->head = q->head->next;
}
if(num == q->tail->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;
}
}
}
}
if(previous)
{
previous->next = current->next;
}
free(current);
}
else
{
previous = current;
}
}
}
void makeNull(struct myQueue* q)
{
if(q)
{
while(q->head) dequeue(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;
{
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);
}
}
{
int ret = CODE_ERR;
if(NULL == q)
{
printf("Invalid Args\n");
ret = CODE_ERR;
{
printf("Invalid Args\n");
}
else if(NULL == q->head && NULL == q->tail)
{
printf("Queue is already empty\n");
ret = CODE_SUCC;
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
{
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
{
}
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: 100
title: 38
title: 100
title: 38
title: 9
title: 100
-----------------------------------------
title: 38
title: 38
title: 9
-----------------------------------------
/home/arnuld/programs/C $
--
arnuld
http://LispMachine.Wordpress.com
Barry Schwarz
May 9, 2012, 2:21:06 AM5/9/12
to
On 09 May 2012 05:43:02 GMT, arnuld <sun...@invalid.address> wrote:
snip
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?
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
This demonstrates you don't use q->tail so why bother maintaining it?
--
Remove del for email
snip
> 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;
behavior.
> 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)
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 4, this is false.
> {
> q->head = q->head->next;
> }
>
> if(num == q->tail->num)
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 3 now points to NULL.
> }
>
> free(current);
> }
> else
> {
> previous = current;
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?
add the following to the end of the if:
|| q->tail->next != NULL
--
Remove del for email
nick_keigh...@hotmail.com
May 9, 2012, 3:01:24 AM5/9/12
to
> No need for any debugger. And what exactly did it say anyway?
"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.
nick_keigh...@hotmail.com
May 9, 2012, 3:03:07 AM5/9/12
to
On Tuesday, May 8, 2012 2:03:48 PM UTC+1, Bart wrote:
> No need for any debugger. And what exactly did it say anyway?
arnuld
May 9, 2012, 5:27:58 AM5/9/12
to
> On Tue, 08 May 2012 23:21:06 -0700, Barry Schwarz wrote:
>> On 09 May 2012 05:43:02 GMT, arnuld <sun...@invalid.address> wrote:
> ret is already initialized to CODE_ERR.
I know. I learned from someone here that assignment at initialization of
>> On 09 May 2012 05:43:02 GMT, arnuld <sun...@invalid.address> wrote:
> ret is already initialized to CODE_ERR.
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.
>> free(h);
>> if(NULL == q->head)
>> {
>> printf("Removing Last element left\n"); q->head = q->tail =
> NULL;
> You already know q->head is NULL.
= 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.
I am trying to understand rest of your comments
--
arnuld
http://LispMachine.Wordpress.com
BartC
May 9, 2012, 5:37:38 AM5/9/12
to
<nick_keigh...@hotmail.com> wrote in message
news:17230148.361.1336546987566.JavaMail.geo-discussion-forums@vbcm9...
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).
--
Bartc
news:17230148.361.1336546987566.JavaMail.geo-discussion-forums@vbcm9...
> On Tuesday, May 8, 2012 2:03:48 PM UTC+1, Bart wrote:
>> <nick_keigh...@hotmail.com> wrote in message
>> <nick_keigh...@hotmail.com> wrote in message
>> > 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.
>
> 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.
As I said, when I tried it under one compiler, it just looped forever
>>
>> 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.
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).
--
Bartc
arnuld
May 9, 2012, 5:44:37 AM5/9/12
to
> On Tue, 08 May 2012 05:09:09 -0700, nick_keighley_nospam wrote:
> ..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.
--
arnuld
http://LispMachine.Wordpress.com
> ..SNIP...
> you could tidy things up by factoring out your queue check code that
> appears in at least three places
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.
--
arnuld
http://LispMachine.Wordpress.com
nick_keigh...@hotmail.com
May 9, 2012, 6:05:15 AM5/9/12
to
On Wednesday, May 9, 2012 10:37:38 AM UTC+1, Bart wrote:
> <nick_keigh...@hotmail.com> wrote in message
> news:17230148.361.1336546987566.JavaMail.geo-discussion-forums@vbcm9...
> > On Tuesday, May 8, 2012 2:03:48 PM UTC+1, Bart wrote:
> >> <nick_keigh...@hotmail.com> wrote in message
> >> > Why didn't you use a debugger? That's how I found the bug.
<snip>
> <nick_keigh...@hotmail.com> wrote in message
> news:17230148.361.1336546987566.JavaMail.geo-discussion-forums@vbcm9...
> > On Tuesday, May 8, 2012 2:03:48 PM UTC+1, Bart wrote:
> >> <nick_keigh...@hotmail.com> wrote in message
> >> > Why didn't you use a debugger? That's how I found the bug.
> >> 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.
>
> 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).
James Kuyper
May 9, 2012, 7:54:35 AM5/9/12
to
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 <sun...@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
>> On Tue, 08 May 2012 23:21:06 -0700, Barry Schwarz wrote:
>
>>> On 09 May 2012 05:43:02 GMT, arnuld <sun...@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)
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.
>>> {
>>> 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.
--
James Kuyper
arnuld
May 9, 2012, 9:18:08 AM5/9/12
to
> On Tue, 08 May 2012 23:21:06 -0700, Barry Schwarz wrote:
>> On 09 May 2012 05:43:02 GMT, arnuld <sun...@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
>> p = malloc(1 * sizeof *p);
> What is the point of multiplying by 1?
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.
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.
> I think the if test should be on the pointers, not on num:
> if (current = q->tail)
>
(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
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.
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
Barry Schwarz
May 9, 2012, 1:59:17 PM5/9/12
to
On 09 May 2012 13:18:08 GMT, arnuld <sun...@invalid.address> wrote:
>> On Tue, 08 May 2012 23:21:06 -0700, Barry Schwarz wrote:
>
>>> On 09 May 2012 05:43:02 GMT, arnuld <sun...@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.
>> On Tue, 08 May 2012 23:21:06 -0700, Barry Schwarz wrote:
>
>>> On 09 May 2012 05:43:02 GMT, arnuld <sun...@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.
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.
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.
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)
>> 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
May 10, 2012, 8:26:52 AM5/10/12
to
> On May 9, 10:59 pm, Barry Schwarz <schwa...@dqel.com> wrote:
> 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
>
"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 :\
>> 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() ??
>>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.
> 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.
> >> 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 "
not the ones I am doing , they are programming errors. Still can't
figure out how to remove an element from queue :\
nick_keigh...@hotmail.com
May 11, 2012, 3:11:37 AM5/11/12
to
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)
> > 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() ??
<snip>
88888 Dihedral
May 11, 2012, 3:39:15 AM5/11/12
to
arnuld於 2012年5月8日星期二UTC+8下午4時09分39秒寫道：
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.
operations of a queue.
I suggest you should use a link list.
Barry Schwarz
May 14, 2012, 6:53:04 PM5/14/12
to
On Thu, 10 May 2012 05:26:52 -0700 (PDT), arnuld
<arnuld...@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,
<arnuld...@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() ??
calloc(a,b) = memset(malloc(a*b),0,a*b)
lawrenc...@siemens.com
May 15, 2012, 5:42:46 PM5/15/12
to
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
> 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
Barry Schwarz
May 15, 2012, 7:40:21 PM5/15/12
to
On Tue, 15 May 2012 17:42:46 -0400, lawrenc...@siemens.com wrote:
>Barry Schwarz <schw...@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.
>Barry Schwarz <schw...@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)
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.
James Kuyper
May 15, 2012, 11:03:39 PM5/15/12
to
On 05/15/2012 07:40 PM, Barry Schwarz wrote:
> On Tue, 15 May 2012 17:42:46 -0400, lawrenc...@siemens.com wrote:
>
>> Barry Schwarz <schw...@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. ...
> On Tue, 15 May 2012 17:42:46 -0400, lawrenc...@siemens.com wrote:
>
>> Barry Schwarz <schw...@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
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
Barry Schwarz
May 15, 2012, 11:38:46 PM5/15/12
to
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.
Jens Gustedt
May 16, 2012, 2:09:13 AM5/16/12
to
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
> 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.
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
James Kuyper
May 16, 2012, 7:18:35 AM5/16/12
to
On 05/15/2012 11:38 PM, Barry Schwarz wrote:
> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
> <james...@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).
...
> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
> <james...@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?
> possible object, including aggregates such as arrays.
"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
Barry Schwarz
May 16, 2012, 7:30:31 PM5/16/12
to
On Wed, 16 May 2012 07:18:35 -0400, James Kuyper
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."
<james...@verizon.net> wrote:
>On 05/15/2012 11:38 PM, Barry Schwarz wrote:
>> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
>> <james...@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
>On 05/15/2012 11:38 PM, Barry Schwarz wrote:
>> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
>> <james...@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?
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."
James Kuyper
May 17, 2012, 9:09:12 AM5/17/12
to
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
Barry Schwarz
May 17, 2012, 2:48:01 PM5/17/12
to
On Thu, 17 May 2012 09:09:12 -0400, James Kuyper
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.
<james...@verizon.net> wrote:
>On 05/16/2012 07:30 PM, Barry Schwarz wrote:
>> On Wed, 16 May 2012 07:18:35 -0400, James Kuyper
>> <james...@verizon.net> wrote:
>>
>>> On 05/15/2012 11:38 PM, Barry Schwarz wrote:
>>>> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
>>>> <james...@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
>On 05/16/2012 07:30 PM, Barry Schwarz wrote:
>> On Wed, 16 May 2012 07:18:35 -0400, James Kuyper
>> <james...@verizon.net> wrote:
>>
>>> On 05/15/2012 11:38 PM, Barry Schwarz wrote:
>>>> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
>>>> <james...@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.
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
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:
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).
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.
Tim Rentsch
May 17, 2012, 3:36:05 PM5/17/12
to
Barry Schwarz <schw...@dqel.com> writes:
> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
> <james...@verizon.net> wrote:
>
>>On 05/15/2012 07:40 PM, Barry Schwarz wrote:
>>> On Tue, 15 May 2012 17:42:46 -0400, lawrenc...@siemens.com wrote:
>>>
>>>> Barry Schwarz <schw...@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. [snip]
> On Tue, 15 May 2012 23:03:39 -0400, James Kuyper
> <james...@verizon.net> wrote:
>
>>On 05/15/2012 07:40 PM, Barry Schwarz wrote:
>>> On Tue, 15 May 2012 17:42:46 -0400, lawrenc...@siemens.com wrote:
>>>
>>>> Barry Schwarz <schw...@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
The Standard does not impose such a requirement, either for regular
objects or for those dynamically allocated. Certainly it is
typically true, and normally implementations enforce it for regular
objects whose size is known at compile time, but neither of those
conditions is necessary for an implementation to be conforming.
James Kuyper
May 17, 2012, 3:38:58 PM5/17/12
to
[Note: corrected typo in Subject: header]
...
>> 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. ...
Agreed.
> ... Surely SIZE_MAX cannot exceed UINTMAX_MAX. ...
Agreed.
> ... I don't understand
what "... sizeof ... can be used to compute ...", not size_t. That's
because the term "compute" is sufficiently vague to allow for a sizeof
expression that is no more than a sub-expression of an enclosing
expression with a result that is of some type other than size_t. The
maximum value that can be represented by such an enclosing expression is
either UINTMAX_MAX or LDBL_MAX, whichever is larger (almost certainly
LDBL_MAX). As long as the size can be correctly computed in one of those
types, with the sizeof operator playing some role somewhere in the
computation, then a hypothetical requirement that "... sizeof ... can be
used to compute the size of any object." would be satisfied.
>> 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). ...
For a hypothetical future version of the standard where there was, in
fact, a requirement that "... sizeof ... can be used to compute the size
of any object.", the existence of such a requirement would imply that a
conforming implementation of C where calloc(2,SIZE_MAX) returns a
non-null pointer must have either UINTMAX_MAX OR LDBL_MAX >= the size of
the object created by that call. Therefore, you could write:
if(p)
{
#if UINTMAX_MAX/2 >= SIZE_MAX
uintmax_t size = 2LL * sizeof *p;
#else
long double size = 2.0L * sizeof *p;
#endif
// do something with size.
}
...
nor any arguments based upon such citations. Even the citation you have
provided from K&R II fails to specify any such requirement.
> ... I didn't address whether SIZE_MAX could be
talking about calculating the size in another type, because SIZE_MAX was
too small to be used for such calculations. Because such calculations
can be performed, a requirement that the computation be possible does
not greatly constrain the value of SIZE_MAX.
That was really intended as a kind of joke. Perhaps I should have
inserted a smiley, but I thought that it was neither sufficiently funny
nor sufficiently obscure to require a smiley. I guess I was wrong on
that second part. All I was trying to do was point out that "... can be
used to compute ..." is too vague a phrase to be used in a specification
that would mean what you wanted it to mean.
> The wording is unchanged in n1570.
The wording of what? All of the citations from the standard so far have
been made by me, and none of them are worded in such a way as to
conflict with the implementation I described.
>> 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.
Citation, please?
>> 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
Agreed.
> ... Surely SIZE_MAX cannot exceed UINTMAX_MAX. ...
Agreed.
> ... I don't understand
> how UINTMAX_MAX enters into this discussion.
Because uintmax_t and long double are the types whose limits determine
what "... sizeof ... can be used to compute ...", not size_t. That's
because the term "compute" is sufficiently vague to allow for a sizeof
expression that is no more than a sub-expression of an enclosing
expression with a result that is of some type other than size_t. The
maximum value that can be represented by such an enclosing expression is
either UINTMAX_MAX or LDBL_MAX, whichever is larger (almost certainly
LDBL_MAX). As long as the size can be correctly computed in one of those
types, with the sizeof operator playing some role somewhere in the
computation, then a hypothetical requirement that "... sizeof ... can be
used to compute the size of any object." would be satisfied.
>> 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
For a hypothetical future version of the standard where there was, in
fact, a requirement that "... sizeof ... can be used to compute the size
of any object.", the existence of such a requirement would imply that a
conforming implementation of C where calloc(2,SIZE_MAX) returns a
non-null pointer must have either UINTMAX_MAX OR LDBL_MAX >= the size of
the object created by that call. Therefore, you could write:
if(p)
{
#if UINTMAX_MAX/2 >= SIZE_MAX
uintmax_t size = 2LL * sizeof *p;
#else
long double size = 2.0L * sizeof *p;
#endif
// do something with size.
}
...
> 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.
An assertion for which you've provided no citations from the standard,
> treated as a single array, calloc should fail if a*b mathematically
> exceeds SIZE_MAX.
nor any arguments based upon such citations. Even the citation you have
provided from K&R II fails to specify any such requirement.
> ... 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).
I wasn't talking about converting the size to another type; I was
> seems obvious it should be convertible to a uintmax_t).
talking about calculating the size in another type, because SIZE_MAX was
too small to be used for such calculations. Because such calculations
can be performed, a requirement that the computation be possible does
not greatly constrain the value of SIZE_MAX.
That was really intended as a kind of joke. Perhaps I should have
inserted a smiley, but I thought that it was neither sufficiently funny
nor sufficiently obscure to require a smiley. I guess I was wrong on
that second part. All I was trying to do was point out that "... can be
used to compute ..." is too vague a phrase to be used in a specification
that would mean what you wanted it to mean.
> The wording is unchanged in n1570.
been made by me, and none of them are worded in such a way as to
conflict with the implementation I described.
Barry Schwarz
May 17, 2012, 6:21:05 PM5/17/12
to
On Thu, 17 May 2012 15:38:58 -0400, James Kuyper
Unless I misread your original response, which has been snipped beyond
recognition above, the result in question was the evaluation of the
sizeof operator. Is there some debate about the type of this
evaluation?
snip
>> 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.
>
>An assertion for which you've provided no citations from the standard,
>nor any arguments based upon such citations. Even the citation you have
>provided from K&R II fails to specify any such requirement.
I'll agree to disagree.
>> The wording is unchanged in n1570.
>
>The wording of what? All of the citations from the standard so far have
>been made by me, and none of them are worded in such a way as to
>conflict with the implementation I described.
So my quote from 7.20.3.1 wasn't from the standard? OK, I confess. I
actually copied it from n1256.
We can disagree on whether I'm interpreting it correctly but I did
provide it. You even quoted it back to me in your message of 15 May
at 2303Z. Looking at snipped quotes in a response is not a good way
to remember who said what :-)
recognition above, the result in question was the evaluation of the
sizeof operator. Is there some debate about the type of this
evaluation?
snip
>> 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.
>
>An assertion for which you've provided no citations from the standard,
>nor any arguments based upon such citations. Even the citation you have
>provided from K&R II fails to specify any such requirement.
>> The wording is unchanged in n1570.
>
>The wording of what? All of the citations from the standard so far have
>been made by me, and none of them are worded in such a way as to
>conflict with the implementation I described.
actually copied it from n1256.
We can disagree on whether I'm interpreting it correctly but I did
provide it. You even quoted it back to me in your message of 15 May
at 2303Z. Looking at snipped quotes in a response is not a good way
to remember who said what :-)
James Kuyper
May 17, 2012, 7:08:10 PM5/17/12
to
No, the result in question was the calculation of "... the size of any
object." The text saying so was yours, not mine, and it has survived all
snipping.
> ... Is there some debate about the type of this
> evaluation?
No, there's a debate about whether that type is required to be capable
of holding "the size of any object". I contend it's only required to
hold the size of types, whether or not there's an object of that type.
Passing a type to sizeof, either directly or through an expression of
that type, whose size cannot be represented in size_t, renders the
behavior undefined by reason of a lack of definition (or more precisely,
by reason of an internally contradictory definition of the behavior).
>>> 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.
>>
>> An assertion for which you've provided no citations from the standard,
>> nor any arguments based upon such citations. Even the citation you have
>> provided from K&R II fails to specify any such requirement.
>
> I'll agree to disagree.
>>> The wording is unchanged in n1570.
>>
>> The wording of what? All of the citations from the standard so far have
>> been made by me, and none of them are worded in such a way as to
>> conflict with the implementation I described.
>
> So my quote from 7.20.3.1 wasn't from the standard?
it's lack of relevance.
The implementation I described conforms to the requirements of 7.20.3.1;
the (unspecified) value of SIZE_MAX is, indeed, as required by 7.20.3.1,
"the limit of size_t".
What I've repeatedly challenged you to provide is one or more citations
that say, directly or indirectly, that SIZE_MAX is the limit on the size
of objects. If they say it only indirectly, they should be accompanied
by an argument explaining how that conclusion may be derived from those
citations. All you've been doing is saying that this must be the case,
without addressing my arguments, or presenting any of your own.
I'll give you some help:
7.19p2 describes size_t: "the unsigned integer type of the result of the
sizeof operator". It does not describe it as a type with sufficient
range to store the size of any object.
6.5.3.4p2 specifies that "The sizeof operator yields the size (in bytes)
of its operand, which may be an expression or the parenthesized name of
a type. The size is determined from the type of the operand". It does
not say that arbitrary expressions which have not been passed to
sizeof() must have types small enough that sizeof() could express the
size of those types.
It does say that only the type of the expression is relevant in
determining the value yielded by "sizeof expression". Therefore, if
"sizeof expression" causes problems with 6.5.3.4p2, the problems are due
to the type of the expression, and can be fixed by changing that type;
they don't have anything to do with the value of that expression,
whether or not it is an lvalue expression referring to an actual object.
Those problems can therefore neither be avoided by having calloc()
return a null pointer value, nor caused by calloc() returning a non-null
pointer value. 6.5.3.4p2 therefore cannot constrain calloc() to return a
null pointer.
> We can disagree on whether I'm interpreting it correctly but I did
> provide it. You even quoted it back to me in your message of 15 May
> at 2303Z. Looking at snipped quotes in a response is not a good way
> to remember who said what :-)
would be if I'd failed to snip them.
Tim Rentsch
May 19, 2012, 11:49:44 AM5/19/12
to
#include <stdio.h>
int
main(){
unsigned k;
unsigned long long n;
for( k = 0; k < 20; k++ ){
n = sizeof (char [k][ (size_t)-1 / 17 ]);
printf( "k: %3u n: %40llu\n", k, n );
}
return 0;
}
The type (char [k][ (size_t)-1 / 17 ]) corresponds to what we
might expect from a calling calloc( k, (size_t)-1 / 17 ) , eg,
we might have
char (*a)[(size_t)-1 / 17] = calloc( k, (size_t)-1 / 17 );
and then use a[i][j] to access individual characters of the
allocated memory returned by calloc().
Question: could a conforming implementation define calloc()
in such a way that the allocation
char (*a)[(size_t)-1 / 17] = calloc( k, (size_t)-1 / 17 );
works for k == 100, ie, a non-null pointer is returned, and
the amount of memory allocated is sufficiently large to hold
an array of type (char[k][(size_t)-1 / 17]), and accesses to
the array using
a[i][j]
with 0 <= i < k, and 0 <= j < (size_t)-1 / 17, will all work?
My answer to this question is Yes. And that answer is consistent
with the existence and observed behavior of the conforming program
shown above.
Tim Rentsch
May 19, 2012, 12:05:15 PM5/19/12
to
that must fit in a size_t, or is the behavior of sizeof undefined in
some cases? They can't both be true. I don't see any text in the
Standard that requires that the result of doing a sizeof must fit in
a size_t, only that the type of the result is size_t.
> by reason of a lack of definition (or more precisely, by reason
> of an internally contradictory definition of the behavior).
the provisions 6.5 p5.
lawrenc...@siemens.com
May 20, 2012, 3:10:44 PM5/20/12
to
Tim Rentsch <t...@alumni.caltech.edu> wrote:
>
> Which is it? Does the Standard require sizeof to produce a value
> that must fit in a size_t, or is the behavior of sizeof undefined in
> some cases? They can't both be true.
Previous discussions have, I think, reached concensus that there are two
>
> Which is it? Does the Standard require sizeof to produce a value
> that must fit in a size_t, or is the behavior of sizeof undefined in
> some cases? They can't both be true.
valid ways to resolve the apparent contradiction: An implementation is
free to disallow declarations (including abstract ones) that would
specify a size that is too big to fit in a size_t. An implementation is
also free to accept such declarations and declare that the behavior of
sizeof is undefined in that case. Both lead to completely consistent
readings of the standard and the committee has not felt compelled to
bless one over the other.
--
Larry Jones
What's Santa's definition? How good do you have to be to qualify as good?
-- Calvin
Tim Rentsch
May 21, 2012, 12:00:39 PM5/21/12
to
lawrenc...@siemens.com writes:
> Tim Rentsch <t...@alumni.caltech.edu> wrote:
>>
>> Which is it? Does the Standard require sizeof to produce a value
>> that must fit in a size_t, or is the behavior of sizeof undefined in
>> some cases? They can't both be true.
>
> Previous discussions have, I think, reached concensus that there are two
> valid ways to resolve the apparent contradiction: An implementation is
> free to disallow declarations (including abstract ones) that would
> specify a size that is too big to fit in a size_t. An implementation is
> also free to accept such declarations and declare that the behavior of
> sizeof is undefined in that case. Both lead to completely consistent
> readings of the standard and the committee has not felt compelled to
> bless one over the other.
I would expect that implementations are always free to reject any
> Tim Rentsch <t...@alumni.caltech.edu> wrote:
>>
>> Which is it? Does the Standard require sizeof to produce a value
>> that must fit in a size_t, or is the behavior of sizeof undefined in
>> some cases? They can't both be true.
>
> Previous discussions have, I think, reached concensus that there are two
> valid ways to resolve the apparent contradiction: An implementation is
> free to disallow declarations (including abstract ones) that would
> specify a size that is too big to fit in a size_t. An implementation is
> also free to accept such declarations and declare that the behavior of
> sizeof is undefined in that case. Both lead to completely consistent
> readings of the standard and the committee has not felt compelled to
> bless one over the other.
program that has a type whose size is known to be > 65535, for
exceeding a minimum environmental limit, whether sizeof is used
or not. Certainly such a program cannot be strictly conforming,
as it is reasonable to expect any implementation with SIZE_MAX
equal to 65535 normally would reject it. Still, the Standard
doesn't require rejection of programs whose types are too large.
Moreover, it is not always possible to determine at compile time
if the size of a type will exceed SIZE_MAX, because of variable
length arrays. If sizeof is used on such a type that is overly
large, the result is not in the range of representable values
for its type, that is, this would be an /exceptional condition/
as defined in 6.5 p5, and so is explicitly undefined behavior.
Ergo I don't think there is any contradiction. The Standard
allows but does not require an implementation to reject programs
known to have overly large types; any sizeof's done on overly
large types that may arise otherwise fall under 6.5 p5, and hence
are undefined behavior.
0 new messages