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

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

Malloc without free in linked list code

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

Contents

  Malloc without free in linked list code Paul <pepstein5@gmail.com> - 2015-04-13 11:21 -0700
    Re: Malloc without free in linked list code Lőrinczy Zsigmond <nospam@for.me> - 2015-04-13 20:45 +0200
    Re: Malloc without free in linked list code Richard Heathfield <rjh@cpax.org.uk> - 2015-04-13 19:53 +0100
    Malloc without free in linked list code asetofsymbols@gmail.com - 2015-04-13 12:05 -0700
    Re: Malloc without free in linked list code Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-13 21:58 +0100
      Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-14 09:26 +0200
        Re: Malloc without free in linked list code Paul <pepstein5@gmail.com> - 2015-04-14 01:45 -0700
          Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-14 11:39 +0200
            Re: Malloc without free in linked list code Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-14 13:43 +0100
              Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-14 15:10 +0200
                Re: Malloc without free in linked list code Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-04-14 16:10 +0100
                  Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-14 17:37 +0200
                    Re: Malloc without free in linked list code Keith Thompson <kst-u@mib.org> - 2015-04-14 11:44 -0700
                      Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-15 00:00 +0200
                    Re: Malloc without free in linked list code Richard Heathfield <rjh@cpax.org.uk> - 2015-04-14 20:12 +0100
                      Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-15 00:04 +0200
                        Re: Malloc without free in linked list code Richard Heathfield <rjh@cpax.org.uk> - 2015-04-15 00:20 +0100
                Re: Malloc without free in linked list code Tim Rentsch <txr@alumni.caltech.edu> - 2015-04-16 15:46 -0700
                  Re: Malloc without free in linked list code David Brown <david.brown@hesbynett.no> - 2015-04-17 10:38 +0200
                    Re: Malloc without free in linked list code Tim Rentsch <txr@alumni.caltech.edu> - 2015-04-17 08:30 -0700
          Re: Malloc without free in linked list code James Kuyper <jameskuyper@verizon.net> - 2015-04-14 08:04 -0400
    Re: Malloc without free in linked list code Malcolm McLean <malcolm.mclean5@btinternet.com> - 2015-04-14 05:38 -0700
    Re: Malloc without free in linked list code BGB <cr88192@hotmail.com> - 2015-04-14 10:31 -0500
    Malloc without free in linked list code Chad <cdalten@gmail.com> - 2015-04-14 19:51 -0700
      Re: Malloc without free in linked list code James Kuyper <jameskuyper@verizon.net> - 2015-04-14 23:10 -0400

Page 1 of 2  [1] 2  Next page →

#59975 — Malloc without free in linked list code

The following code is quoted verbatim from a well-known CS course at an extremely prestigious university.

Why is it ok to use malloc without free?  Does this leak memory?  If not, why not?
If yes, how can the memory be freed without destroying the data structure?

The node struct contains an int called data and a node* called next.

Thank You,

Paul

struct node* CopyList(struct node* head){

struct node* current = head;
struct node* newList = NULL;
struct node* tail = NULL;

while(current != NULL)
{
if(newList == NULL)
{
newList = malloc(sizeof(struct node));
newList -> data = current -> data;
newList -> next = NULL;
tail = newList;
}

else
{
  tail->next = malloc(sizeof(struct node));
  tail = tail->next;
  tail->data = current->data;
  tail->next = NULL;   
}

current = current->next;

}

return (newList);

}

[toc] | [next] | [standalone]

#59977

On 2015.04.13. 20:21, Paul wrote:
> The following code is quoted verbatim from a well-known CS course at an extremely prestigious university.
>
> Why is it ok to use malloc without free?  Does this leak memory?  If not, why not?
> If yes, how can the memory be freed without destroying the data structure?

off: Please use indentation
on: This is only a part of a complete program;
function 'CopyList' creates a copy from a list
Most likely you'll find another function called 'DeleteList',
with 'free' in it.

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

#59978

On 13/04/15 19:21, Paul wrote:
> The following code is quoted verbatim from a well-known CS course at an extremely prestigious university.

I recommend that you read Lorinczy Zsigmond's reply first. If that 
doesn't answer your question, read on.

> Why is it ok to use malloc without free?

It isn't. To do so is very short-sighted, as it assumes that your 
program will never turn into a library (which happens more often than 
people realise).

> Does this leak memory?  If not, why not?

It doesn't leak memory *if* you never lose the pointer value, so that 
you can always get back to the list if you need it. At the end of the 
program, all allocated memory is guaranteed to be freed.

> If yes, how can the memory be freed without destroying the data structure?

It can't. If you need to free the memory, you'll have to copy the data 
elsewhere first if you don't want to lose it.

<snip>

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#59979

Paul wrote: 
"struct node* CopyList(struct node* head){ 

struct node* current = head; 
struct node* newList = NULL; 
struct node* tail = NULL; 

while(current != NULL) 
{ 
if(newList == NULL) 
{ 
newList = malloc(sizeof(struct node)); 
newList -> data = current -> data; 
newList -> next = NULL; 
tail = newList; 
} 

else 
{ 
  tail->next = malloc(sizeof(struct node)); 
  tail = tail->next; 
  tail->data = current->data; 
  tail->next = NULL;   
} 

current = current->next; 

} 

return (newList); 

}"

The leak that you say should
not exist because there would be
one other function (the name as
FreeList())
There error should be if malloc
fail and tail->data is
0->data that should seg fault 

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

#59984

Paul <pepstein5@gmail.com> writes:

> The following code is quoted verbatim from a well-known CS course at
> an extremely prestigious university.
>
> Why is it ok to use malloc without free?  Does this leak memory?  If
> not, why not?

That's answered, so I'll just make a remark about the code.
Re-formatted a little (and with the sizeof altered to my taste) it is:

  struct node *CopyList(struct node *head)
  {
       struct node *current = head;
       struct node *newList = NULL;
       struct node *tail = NULL;
   
       while (current != NULL) {
            if (newList == NULL) {
                 newList = malloc(sizeof *newList);
                 newList->data = current->data;
                 newList->next = NULL;
                 tail = newList;
            }
            else {
                 tail->next = malloc(sizeof *tail->next);
                 tail = tail->next;
                 tail->data = current->data;
                 tail->next = NULL;   
            }
            current = current->next;
       }
       return newList;
  }

Let's rewrite the inner "if" a little and add ()s for emphasis:

            if (newList == NULL) {
                 (newList) = malloc(sizeof *newList);
                 (newList)->data = current->data;
                 (newList)->next = NULL;
                 tail = (newList);
            }
            else {
                 (tail->next) = malloc(sizeof *tail->next);
                 (tail->next)->data = current->data;
                 (tail->next)->next = NULL;   
                 tail = (tail->next);
            }

Now you can see that both arms are really doing exactly the same thing,
but one uses newList as the object to modify (on the first iteration)
and the other arm uses tail->next (on all subsequent iterations).  It's
much neater, to my mind, to combine them, thereby removing the test:

   *tailp = malloc(sizeof **tailp);
   (*tailp)->data = current->data;
   (*tailp)->next = NULL;
   tailp = &(*tailp)->next;

Finally, you might spot that setting the "next" pointer to NULL needs to
be done only once.  You get:

  struct node *CopyList(struct node *head)
  {
       struct node *current = head;
       struct node *newList = NULL;
       struct node **tailp = &newList;
   
       while (current != NULL) {
            *tailp = malloc(sizeof **tailp);
            (*tailp)->data = current->data;
            tailp = &(*tailp)->next;
            current = current->next;
       }
       *tailp = NULL;
       return newList;
  }

though I'd not bother with the extra "current" pointer.

But the clearest method of all is probably to use recursion:

  struct node *CopyList(struct node *list)
  {
       if (list) {
            struct node *new_list = malloc(sizeof *new_list);
            new_list->data = list->data;
            new_list->next = CopyList(list->next);
            return new_list;
       }
       return NULL;
  }

-- 
Ben.

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

#60007

On 13/04/15 22:58, Ben Bacarisse wrote:
> Paul <pepstein5@gmail.com> writes:
> 
>> The following code is quoted verbatim from a well-known CS course at
>> an extremely prestigious university.
>>
>> Why is it ok to use malloc without free?  Does this leak memory?  If
>> not, why not?
> 
> That's answered, so I'll just make a remark about the code.
> Re-formatted a little (and with the sizeof altered to my taste) it is:
> 
>   struct node *CopyList(struct node *head)
>   {
>        struct node *current = head;
>        struct node *newList = NULL;
>        struct node *tail = NULL;
>    
>        while (current != NULL) {
>             if (newList == NULL) {
>                  newList = malloc(sizeof *newList);
>                  newList->data = current->data;
>                  newList->next = NULL;
>                  tail = newList;
>             }
>             else {
>                  tail->next = malloc(sizeof *tail->next);
>                  tail = tail->next;
>                  tail->data = current->data;
>                  tail->next = NULL;   
>             }
>             current = current->next;
>        }
>        return newList;
>   }
> 
> Let's rewrite the inner "if" a little and add ()s for emphasis:
> 
>             if (newList == NULL) {
>                  (newList) = malloc(sizeof *newList);
>                  (newList)->data = current->data;
>                  (newList)->next = NULL;
>                  tail = (newList);
>             }
>             else {
>                  (tail->next) = malloc(sizeof *tail->next);
>                  (tail->next)->data = current->data;
>                  (tail->next)->next = NULL;   
>                  tail = (tail->next);
>             }
> 
> Now you can see that both arms are really doing exactly the same thing,
> but one uses newList as the object to modify (on the first iteration)
> and the other arm uses tail->next (on all subsequent iterations).  It's
> much neater, to my mind, to combine them, thereby removing the test:
> 
>    *tailp = malloc(sizeof **tailp);
>    (*tailp)->data = current->data;
>    (*tailp)->next = NULL;
>    tailp = &(*tailp)->next;

I agree that it makes sense to combine both arms in some way.  But
pointers-to-pointers are scary.  They make it easier to introduce new
problems and make new mistakes (especially if you are a beginner, or if
you don't know how to get strong warnings from your compiler), they look
ugly (IMHO), and they can often lead to inefficiencies in the code
generation as the compiler has to put data on the stack when it could
otherwise have held it in registers.  Obviously pointers-to-pointers are
sometimes the best solution, but personally I avoid them unless there is
a clear advantage.

struct node *CopyList(struct node *head)
{
	struct node *current = head;
	struct node *newList = NULL;
	struct node *tail;
	struct node *newNode;

	while (current != NULL) {
		newNode = malloc(sizeof(struct node));
		newNode->data = current->data;
		newNode->next = NULL;
		if (newList == NULL) {
			newList = newNode;
		} else {
			tail->next = newNode;
		}
		tail = newNode;
	}
	return newList;
}

(I've just written this out my head - it is not checked or tested.)

We could eliminate the internal conditional with another trick.  (It
won't make a speed difference when there is a "malloc" in the loop, but
if we knew the length of the loop and could pre-allocate the memory, it
might be measurable.)

struct node *CopyList(struct node *head)
{
	struct node *current = head;
	struct node dummyTail = { .next = newList };
	struct node *tail = &dummyTail;

	while (current != NULL) {
		tail->next = malloc(sizeof(struct node));
		(tail->next)->data = current->data;
		(tail->next)->next = NULL;
		tail = tail->next;
	}
	return dummyTail.next;
}

That keeps the loop as short as your version, but eliminates the
unpleasant double pointer.

However, I agree that the recursive version is the neatest choice - the
source code is clear and easily understood, and the compiler can handle
the details of producing a loop.

> 
> Finally, you might spot that setting the "next" pointer to NULL needs to
> be done only once.  You get:
> 
>   struct node *CopyList(struct node *head)
>   {
>        struct node *current = head;
>        struct node *newList = NULL;
>        struct node **tailp = &newList;
>    
>        while (current != NULL) {
>             *tailp = malloc(sizeof **tailp);
>             (*tailp)->data = current->data;
>             tailp = &(*tailp)->next;
>             current = current->next;
>        }
>        *tailp = NULL;
>        return newList;
>   }
> 
> though I'd not bother with the extra "current" pointer.
> 
> But the clearest method of all is probably to use recursion:
> 
>   struct node *CopyList(struct node *list)
>   {
>        if (list) {
>             struct node *new_list = malloc(sizeof *new_list);
>             new_list->data = list->data;
>             new_list->next = CopyList(list->next);
>             return new_list;
>        }
>        return NULL;
>   }
> 

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

#60014

On Tuesday, April 14, 2015 at 8:26:22 AM UTC+1, David Brown wrote:
> On 13/04/15 22:58, Ben Bacarisse wrote:
> > Paul <pepstein5@gmail.com> writes:
> > 
> >> The following code is quoted verbatim from a well-known CS course at
> >> an extremely prestigious university.
> >>
> >> Why is it ok to use malloc without free?  Does this leak memory?  If
> >> not, why not?
> > 
> > That's answered, so I'll just make a remark about the code.
> > Re-formatted a little (and with the sizeof altered to my taste) it is:
> > 
> >   struct node *CopyList(struct node *head)
> >   {
> >        struct node *current = head;
> >        struct node *newList = NULL;
> >        struct node *tail = NULL;
> >    
> >        while (current != NULL) {
> >             if (newList == NULL) {
> >                  newList = malloc(sizeof *newList);
> >                  newList->data = current->data;
> >                  newList->next = NULL;
> >                  tail = newList;
> >             }
> >             else {
> >                  tail->next = malloc(sizeof *tail->next);
> >                  tail = tail->next;
> >                  tail->data = current->data;
> >                  tail->next = NULL;   
> >             }
> >             current = current->next;
> >        }
> >        return newList;
> >   }
> > 
> > Let's rewrite the inner "if" a little and add ()s for emphasis:
> > 
> >             if (newList == NULL) {
> >                  (newList) = malloc(sizeof *newList);
> >                  (newList)->data = current->data;
> >                  (newList)->next = NULL;
> >                  tail = (newList);
> >             }
> >             else {
> >                  (tail->next) = malloc(sizeof *tail->next);
> >                  (tail->next)->data = current->data;
> >                  (tail->next)->next = NULL;   
> >                  tail = (tail->next);
> >             }
> > 
> > Now you can see that both arms are really doing exactly the same thing,
> > but one uses newList as the object to modify (on the first iteration)
> > and the other arm uses tail->next (on all subsequent iterations).  It's
> > much neater, to my mind, to combine them, thereby removing the test:
> > 
> >    *tailp = malloc(sizeof **tailp);
> >    (*tailp)->data = current->data;
> >    (*tailp)->next = NULL;
> >    tailp = &(*tailp)->next;
> 
> I agree that it makes sense to combine both arms in some way.  But
> pointers-to-pointers are scary.  They make it easier to introduce new
> problems and make new mistakes (especially if you are a beginner, or if
> you don't know how to get strong warnings from your compiler), they look
> ugly (IMHO), and they can often lead to inefficiencies in the code
> generation as the compiler has to put data on the stack when it could
> otherwise have held it in registers.  Obviously pointers-to-pointers are
> sometimes the best solution, but personally I avoid them unless there is
> a clear advantage.
> 
> struct node *CopyList(struct node *head)
> {
> 	struct node *current = head;
> 	struct node *newList = NULL;
> 	struct node *tail;
> 	struct node *newNode;
> 
> 	while (current != NULL) {
> 		newNode = malloc(sizeof(struct node));
> 		newNode->data = current->data;
> 		newNode->next = NULL;
> 		if (newList == NULL) {
> 			newList = newNode;
> 		} else {
> 			tail->next = newNode;
> 		}
> 		tail = newNode;
> 	}
> 	return newList;
> }
> 
> (I've just written this out my head - it is not checked or tested.)
> 
> We could eliminate the internal conditional with another trick.  (It
> won't make a speed difference when there is a "malloc" in the loop, but
> if we knew the length of the loop and could pre-allocate the memory, it
> might be measurable.)
> 
> struct node *CopyList(struct node *head)
> {
> 	struct node *current = head;
> 	struct node dummyTail = { .next = newList };
> 	struct node *tail = &dummyTail;
> 
> 	while (current != NULL) {
> 		tail->next = malloc(sizeof(struct node));
> 		(tail->next)->data = current->data;
> 		(tail->next)->next = NULL;
> 		tail = tail->next;
> 	}
> 	return dummyTail.next;
> }
> 
> That keeps the loop as short as your version, but eliminates the
> unpleasant double pointer.
> 
> However, I agree that the recursive version is the neatest choice - the
> source code is clear and easily understood, and the compiler can handle
> the details of producing a loop.
> 
...
Thanks for all the comments.  I would have expected to see a current = current->next;  It's not clear to me that these versions which omit current = current->next work. (I'm not saying that they don't work though).

Also, I'm confused by struct node dummyTail = { .next = newList };
Please could this be explained further?  For example, what is the role of the curly brackets here?

Thank You,

Paul

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

#60017

On 14/04/15 10:45, Paul wrote:
> On Tuesday, April 14, 2015 at 8:26:22 AM UTC+1, David Brown wrote:
>> On 13/04/15 22:58, Ben Bacarisse wrote:
>>> Paul <pepstein5@gmail.com> writes:
>>>
>>>> The following code is quoted verbatim from a well-known CS course at
>>>> an extremely prestigious university.
>>>>
>>>> Why is it ok to use malloc without free?  Does this leak memory?  If
>>>> not, why not?
>>>
>>> That's answered, so I'll just make a remark about the code.
>>> Re-formatted a little (and with the sizeof altered to my taste) it is:
>>>
>>>   struct node *CopyList(struct node *head)
>>>   {
>>>        struct node *current = head;
>>>        struct node *newList = NULL;
>>>        struct node *tail = NULL;
>>>    
>>>        while (current != NULL) {
>>>             if (newList == NULL) {
>>>                  newList = malloc(sizeof *newList);
>>>                  newList->data = current->data;
>>>                  newList->next = NULL;
>>>                  tail = newList;
>>>             }
>>>             else {
>>>                  tail->next = malloc(sizeof *tail->next);
>>>                  tail = tail->next;
>>>                  tail->data = current->data;
>>>                  tail->next = NULL;   
>>>             }
>>>             current = current->next;
>>>        }
>>>        return newList;
>>>   }
>>>
>>> Let's rewrite the inner "if" a little and add ()s for emphasis:
>>>
>>>             if (newList == NULL) {
>>>                  (newList) = malloc(sizeof *newList);
>>>                  (newList)->data = current->data;
>>>                  (newList)->next = NULL;
>>>                  tail = (newList);
>>>             }
>>>             else {
>>>                  (tail->next) = malloc(sizeof *tail->next);
>>>                  (tail->next)->data = current->data;
>>>                  (tail->next)->next = NULL;   
>>>                  tail = (tail->next);
>>>             }
>>>
>>> Now you can see that both arms are really doing exactly the same thing,
>>> but one uses newList as the object to modify (on the first iteration)
>>> and the other arm uses tail->next (on all subsequent iterations).  It's
>>> much neater, to my mind, to combine them, thereby removing the test:
>>>
>>>    *tailp = malloc(sizeof **tailp);
>>>    (*tailp)->data = current->data;
>>>    (*tailp)->next = NULL;
>>>    tailp = &(*tailp)->next;
>>
>> I agree that it makes sense to combine both arms in some way.  But
>> pointers-to-pointers are scary.  They make it easier to introduce new
>> problems and make new mistakes (especially if you are a beginner, or if
>> you don't know how to get strong warnings from your compiler), they look
>> ugly (IMHO), and they can often lead to inefficiencies in the code
>> generation as the compiler has to put data on the stack when it could
>> otherwise have held it in registers.  Obviously pointers-to-pointers are
>> sometimes the best solution, but personally I avoid them unless there is
>> a clear advantage.
>>
>> struct node *CopyList(struct node *head)
>> {
>> 	struct node *current = head;
>> 	struct node *newList = NULL;
>> 	struct node *tail;
>> 	struct node *newNode;
>>
>> 	while (current != NULL) {
>> 		newNode = malloc(sizeof(struct node));
>> 		newNode->data = current->data;
>> 		newNode->next = NULL;
>> 		if (newList == NULL) {
>> 			newList = newNode;
>> 		} else {
>> 			tail->next = newNode;
>> 		}
>> 		tail = newNode;
>> 	}
>> 	return newList;
>> }
>>
>> (I've just written this out my head - it is not checked or tested.)
>>
>> We could eliminate the internal conditional with another trick.  (It
>> won't make a speed difference when there is a "malloc" in the loop, but
>> if we knew the length of the loop and could pre-allocate the memory, it
>> might be measurable.)
>>
>> struct node *CopyList(struct node *head)
>> {
>> 	struct node *current = head;
>> 	struct node dummyTail = { .next = newList };
>> 	struct node *tail = &dummyTail;
>>
>> 	while (current != NULL) {
>> 		tail->next = malloc(sizeof(struct node));
>> 		(tail->next)->data = current->data;
>> 		(tail->next)->next = NULL;
>> 		tail = tail->next;
>> 	}
>> 	return dummyTail.next;
>> }
>>
>> That keeps the loop as short as your version, but eliminates the
>> unpleasant double pointer.
>>
>> However, I agree that the recursive version is the neatest choice - the
>> source code is clear and easily understood, and the compiler can handle
>> the details of producing a loop.
>>
> ...
> Thanks for all the comments.  I would have expected to see a current = current->next;  It's not clear to me that these versions which omit current = current->next work. (I'm not saying that they don't work though).

You are correct - there is a "current = current->next" missing from the
loop.  As I said, I've only written the code - not tested it!  (Ben's
code is missing it too.)

> 
> Also, I'm confused by struct node dummyTail = { .next = newList };
> Please could this be explained further?  For example, what is the role of the curly brackets here?

It's a "designated initializer" expression, valid since C99.  Basically
it means that all fields of the "dummyTail" object are initialised to
zero, except "dummyTail.next = newList".

> 
> Thank You,
> 
> Paul
> 

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

#60026

David Brown <david.brown@hesbynett.no> writes:

> On 14/04/15 10:45, Paul wrote:
>> On Tuesday, April 14, 2015 at 8:26:22 AM UTC+1, David Brown wrote:
<snip>
>>> struct node *CopyList(struct node *head)
>>> {
>>> 	struct node *current = head;
>>> 	struct node dummyTail = { .next = newList };
>>> 	struct node *tail = &dummyTail;
>>>
>>> 	while (current != NULL) {
>>> 		tail->next = malloc(sizeof(struct node));
>>> 		(tail->next)->data = current->data;
>>> 		(tail->next)->next = NULL;
>>> 		tail = tail->next;
>>> 	}
>>> 	return dummyTail.next;
>>> }
>>>
>>> That keeps the loop as short as your version, but eliminates the
>>> unpleasant double pointer.

Personally, I don't see anything unpleasant about a double pointer but
you haven't really got rid of it, you've just declared it in a funny way
(that I think might be just as confusing as **) and accessed it using
two ->s instead of a * and a ->.

It's true that in my version, the precedence of * and -> interact "the
wrong way" but that's hardly anything to worry about -- after all,
you've added redundant parentheses to your version "just in case".

>>> However, I agree that the recursive version is the neatest choice - the
>>> source code is clear and easily understood, and the compiler can handle
>>> the details of producing a loop.

Sadly, I don't think existing C compilers turn this recursive pattern
into a loop.

>> Thanks for all the comments.  I would have expected to see a current
>> = current->next; It's not clear to me that these versions which omit
>> current = current->next work. (I'm not saying that they don't work
>> though).
>
> You are correct - there is a "current = current->next" missing from the
> loop.  As I said, I've only written the code - not tested it!  (Ben's
> code is missing it too.)

No it isn't missing!  It's there in the version that has the whole loop
body, but it's obviously not there in the part where I discuss
re-writing the "if" because it was never part of the "if" to start with.

-- 
Ben.

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

#60028

On 14/04/15 14:43, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> On 14/04/15 10:45, Paul wrote:
>>> On Tuesday, April 14, 2015 at 8:26:22 AM UTC+1, David Brown wrote:
> <snip>
>>>> struct node *CopyList(struct node *head)
>>>> {
>>>> 	struct node *current = head;
>>>> 	struct node dummyTail = { .next = newList };
>>>> 	struct node *tail = &dummyTail;
>>>>
>>>> 	while (current != NULL) {
>>>> 		tail->next = malloc(sizeof(struct node));
>>>> 		(tail->next)->data = current->data;
>>>> 		(tail->next)->next = NULL;
>>>> 		tail = tail->next;
>>>> 	}
>>>> 	return dummyTail.next;
>>>> }
>>>>
>>>> That keeps the loop as short as your version, but eliminates the
>>>> unpleasant double pointer.
> 
> Personally, I don't see anything unpleasant about a double pointer

It's a matter of taste and style, of course.

> but
> you haven't really got rid of it, you've just declared it in a funny way
> (that I think might be just as confusing as **) and accessed it using
> two ->s instead of a * and a ->.

No, I've got rid of the double pointer - the two -> in a row is a chain
of nodes, rather than a pointer-to-a-pointer.  It can also be easily
removed by a slight re-arrangement (moving back towards the original
version, away from your version):

struct node *CopyList(struct node *head)
{
	struct node *current = head;
	struct node dummyTail = { .next = newList };
	struct node *tail = &dummyTail;

	while (current != NULL) {
		tail->next = malloc(sizeof(struct node));
		tail = tail->next;
		tail->data = current->data;
		tail->next = NULL;
	}
	return dummyTail.next;
}

The point is to add an initial dummy node, so that we always have a
valid tail, rather than using a double pointer to distinguish between an
empty new list and a tail'ed new list.

> 
> It's true that in my version, the precedence of * and -> interact "the
> wrong way" but that's hardly anything to worry about -- after all,
> you've added redundant parentheses to your version "just in case".

I put in the redundant parentheses for the same reason you did - it
makes the precedence abundantly clear.

> 
>>>> However, I agree that the recursive version is the neatest choice - the
>>>> source code is clear and easily understood, and the compiler can handle
>>>> the details of producing a loop.
> 
> Sadly, I don't think existing C compilers turn this recursive pattern
> into a loop.

Perhaps not.  I suspect that with a little massaging, it would be
possible to make a recursive version of the function that compilers
/could/ turn into a loop - but I haven't tried it out.

> 
>>> Thanks for all the comments.  I would have expected to see a current
>>> = current->next; It's not clear to me that these versions which omit
>>> current = current->next work. (I'm not saying that they don't work
>>> though).
>>
>> You are correct - there is a "current = current->next" missing from the
>> loop.  As I said, I've only written the code - not tested it!  (Ben's
>> code is missing it too.)
> 
> No it isn't missing!  It's there in the version that has the whole loop
> body, but it's obviously not there in the part where I discuss
> re-writing the "if" because it was never part of the "if" to start with.
> 

True - but that's the bit I copied :-)

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

#60038

David Brown <david.brown@hesbynett.no> writes:

> On 14/04/15 14:43, Ben Bacarisse wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>> 
>>> On 14/04/15 10:45, Paul wrote:
>>>> On Tuesday, April 14, 2015 at 8:26:22 AM UTC+1, David Brown wrote:
>> <snip>
>>>>> struct node *CopyList(struct node *head)
>>>>> {
>>>>> 	struct node *current = head;
>>>>> 	struct node dummyTail = { .next = newList };
>>>>> 	struct node *tail = &dummyTail;
>>>>>
>>>>> 	while (current != NULL) {
>>>>> 		tail->next = malloc(sizeof(struct node));
>>>>> 		(tail->next)->data = current->data;
>>>>> 		(tail->next)->next = NULL;
>>>>> 		tail = tail->next;
>>>>> 	}
>>>>> 	return dummyTail.next;
>>>>> }
>>>>>
>>>>> That keeps the loop as short as your version, but eliminates the
>>>>> unpleasant double pointer.
>> 
>> Personally, I don't see anything unpleasant about a double pointer
>
> It's a matter of taste and style, of course.

Of course.  That was intended to be conveyed by saying "personally...".

>> but
>> you haven't really got rid of it, you've just declared it in a funny way
>> (that I think might be just as confusing as **) and accessed it using
>> two ->s instead of a * and a ->.
>
> No, I've got rid of the double pointer - the two -> in a row is a chain
> of nodes, rather than a pointer-to-a-pointer.

And this is going to be about terminology if we don't take care!  Sure,
you've got rid of the pointer to a pointer, but not the double
indirection.  You now point to something that holds the target pointer
at a offset that is not zero.

<snip>
-- 
Ben.

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

#60043

On 14/04/15 17:10, Ben Bacarisse wrote:
> David Brown <david.brown@hesbynett.no> writes:
>
>> On 14/04/15 14:43, Ben Bacarisse wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>>
>>>> On 14/04/15 10:45, Paul wrote:
>>>>> On Tuesday, April 14, 2015 at 8:26:22 AM UTC+1, David Brown wrote:
>>> <snip>
>>>>>> struct node *CopyList(struct node *head)
>>>>>> {
>>>>>> 	struct node *current = head;
>>>>>> 	struct node dummyTail = { .next = newList };
>>>>>> 	struct node *tail = &dummyTail;
>>>>>>
>>>>>> 	while (current != NULL) {
>>>>>> 		tail->next = malloc(sizeof(struct node));
>>>>>> 		(tail->next)->data = current->data;
>>>>>> 		(tail->next)->next = NULL;
>>>>>> 		tail = tail->next;
>>>>>> 	}
>>>>>> 	return dummyTail.next;
>>>>>> }
>>>>>>
>>>>>> That keeps the loop as short as your version, but eliminates the
>>>>>> unpleasant double pointer.
>>>
>>> Personally, I don't see anything unpleasant about a double pointer
>>
>> It's a matter of taste and style, of course.
>
> Of course.  That was intended to be conveyed by saying "personally...".

Yes.  I was just acknowledging that.  (Similarly, I believe I had an 
"IMHO" somewhere when saying I don't like double pointers.)

>
>>> but
>>> you haven't really got rid of it, you've just declared it in a funny way
>>> (that I think might be just as confusing as **) and accessed it using
>>> two ->s instead of a * and a ->.
>>
>> No, I've got rid of the double pointer - the two -> in a row is a chain
>> of nodes, rather than a pointer-to-a-pointer.
>
> And this is going to be about terminology if we don't take care!  Sure,
> you've got rid of the pointer to a pointer, but not the double
> indirection.  You now point to something that holds the target pointer
> at a offset that is not zero.
>

I don't want an argument about terminology any more than you do, but I 
make a distinction between a data structure that involves a chain of 
pointers (such as a linked list), and something that is explicitly a 
pointer-to-pointer type.  Clearly we are not going to be able to remove 
the pointers to things holding pointers while keeping the same data 
structure!

But if you want to say that I have merely changed the code into a form 
that /I/ like better, without making any fundamental changes or reducing 
complexity, then I suppose that's fair enough.  Of course, the reason I 
like it better is that the code is better :-)

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

#60048

David Brown <david.brown@hesbynett.no> writes:
[...]
> Yes.  I was just acknowledging that.  (Similarly, I believe I had an
> "IMHO" somewhere when saying I don't like double pointers.)
[...]

I humbly suggest avoiding the phrase "double pointer" unless you're
talking about the type double*.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#60063

On 14/04/15 20:44, Keith Thompson wrote:
> David Brown <david.brown@hesbynett.no> writes:
> [...]
>> Yes.  I was just acknowledging that.  (Similarly, I believe I had an
>> "IMHO" somewhere when saying I don't like double pointers.)
> [...]
>
> I humbly suggest avoiding the phrase "double pointer" unless you're
> talking about the type double*.
>

I referred to it as a pointer-to-pointer elsewhere - is that okay for you?

(If I meant a pointer-to-double, I'd have said pointer-to-double or 
double*, because that's clearer.)

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

#60049

On 14/04/15 16:37, David Brown wrote:

<snip>
>
> Yes.  I was just acknowledging that.  (Similarly, I believe I had an
> "IMHO" somewhere when saying I don't like double pointers.)

How do you feel about unsigned long pointers?

I have no objection whatsoever to T**, but I do object to the misleading 
term "double pointer".

<snip>

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#60064

On 14/04/15 21:12, Richard Heathfield wrote:
> On 14/04/15 16:37, David Brown wrote:
>
> <snip>
>>
>> Yes.  I was just acknowledging that.  (Similarly, I believe I had an
>> "IMHO" somewhere when saying I don't like double pointers.)
>
> How do you feel about unsigned long pointers?
>
> I have no objection whatsoever to T**, but I do object to the misleading
> term "double pointer".
>

(I should have read this before replying to Keith's post.)

Okay - I don't see anything misleading about the term "double pointer", 
but if other people do, I'll try to remember to avoid it.

I have nothing against a pointer to an unsigned long (though usually I 
prefer sized types for the type of code I write - and thus uint32_t* 
would be much more likely in my programming).  I just think pointers to 
pointers can add complexity and should be avoided unless they are 
particularly useful (and in this case, they are unnecessary).

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

#60066

On 14/04/15 23:04, David Brown wrote:
> On 14/04/15 21:12, Richard Heathfield wrote:
>> On 14/04/15 16:37, David Brown wrote:
>>
>> <snip>
>>>
>>> Yes.  I was just acknowledging that.  (Similarly, I believe I had an
>>> "IMHO" somewhere when saying I don't like double pointers.)
>>
>> How do you feel about unsigned long pointers?
>>
>> I have no objection whatsoever to T**, but I do object to the misleading
>> term "double pointer".
>>
>
> (I should have read this before replying to Keith's post.)
>
> Okay - I don't see anything misleading about the term "double pointer",
> but if other people do, I'll try to remember to avoid it.

The phrase *always* gives me pause, because I am aware that some people 
use it in one sense and others in another.

> I have nothing against a pointer to an unsigned long

The question, of course, was designed to draw your attention to the 
ambiguity of 'double pointer'.


> (though usually I
> prefer sized types for the type of code I write - and thus uint32_t*
> would be much more likely in my programming).  I just think pointers to
> pointers can add complexity and should be avoided unless they are
> particularly useful (and in this case, they are unnecessary).

I see no particular reason to avoid them. (Nor do I see any reason to 
use them when their use is not - uh - useful.)

fclose would have benefited from taking FILE **, and being implemented 
along these lines:

int fclose(FILE **fp)
{
   int rc = !fp ? EOF : !*fp ? EOF : __fcloseinternal(*fp);
   if(fp) { *fp = NULL; }
   return rc;
}

This is where I habitually use T** - to allow a function to mark a 
resource as unavailable immediately after releasing it.

T** has other uses, of course, but for this use alone it is worth 
conquering any innate antipathy towards it.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#60181

David Brown <david.brown@hesbynett.no> writes:
> On 14/04/15 14:43, Ben Bacarisse wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>> At some unknown time, Ben Bacarisse wrote:
>>>> [edited to restore example of recursive version]
>>>>
>>>> But the clearest method of all is probably to use recursion:
>>>>
>>>>   struct node *CopyList(struct node *list)
>>>>   {
>>>>        if (list) {
>>>>             struct node *new_list = malloc(sizeof *new_list);
>>>>             new_list->data = list->data;
>>>>             new_list->next = CopyList(list->next);
>>>>             return new_list;
>>>>        }
>>>>        return NULL;
>>>>   }
>>>
>>> [end of edit]
>>>
>>> However, I agree that the recursive version is the neatest
>>> choice - the source code is clear and easily understood, and the
>>> compiler can handle the details of producing a loop.
>>
>> Sadly, I don't think existing C compilers turn this recursive
>> pattern into a loop.
>
> Perhaps not.  I suspect that with a little massaging, it would be
> possible to make a recursive version of the function that
> compilers /could/ turn into a loop - but I haven't tried it out.

Let me suggest it would be a useful experience to go through the
exercise of writing a recursive version that (for example) gcc
does compile as a loop (normally -O2 or -Os will get you there,
often -O1 won't).  You can easily check for loopness by using -S
and looking at the generated assembly, noting the absence of
recursive calls for the function(s) in question.

Functions like this one usually aren't transformed directly
into loops, because there is compuation that happens after the
recursive call, which makes the transformation difficult.  The
interface makes it hard to write the function body directly to
avoid that, because after the rest of the list is copied we
have to return a pointer to the head of the list.  Usually this
problem is avoided by introducing a recursive helper function
that does most of the work, with the original function just
calling the helper function and then returning a value.  For
the function here we might do that this way:

    struct node *
    CopyList( struct node *list ){
        struct node *result = list;
        copy_tail( &result );
        return  result;
    }

The function copy_tail() can be written fairly easily using a
recursive formulation that gcc will turn into a loop.

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

#60206

On 17/04/15 00:46, Tim Rentsch wrote:
> David Brown <david.brown@hesbynett.no> writes:
>> On 14/04/15 14:43, Ben Bacarisse wrote:
>>> David Brown <david.brown@hesbynett.no> writes:
>>>> At some unknown time, Ben Bacarisse wrote:
>>>>> [edited to restore example of recursive version]
>>>>>
>>>>> But the clearest method of all is probably to use recursion:
>>>>>
>>>>>   struct node *CopyList(struct node *list)
>>>>>   {
>>>>>        if (list) {
>>>>>             struct node *new_list = malloc(sizeof *new_list);
>>>>>             new_list->data = list->data;
>>>>>             new_list->next = CopyList(list->next);
>>>>>             return new_list;
>>>>>        }
>>>>>        return NULL;
>>>>>   }
>>>>
>>>> [end of edit]
>>>>
>>>> However, I agree that the recursive version is the neatest
>>>> choice - the source code is clear and easily understood, and the
>>>> compiler can handle the details of producing a loop.
>>>
>>> Sadly, I don't think existing C compilers turn this recursive
>>> pattern into a loop.
>>
>> Perhaps not.  I suspect that with a little massaging, it would be
>> possible to make a recursive version of the function that
>> compilers /could/ turn into a loop - but I haven't tried it out.
> 
> Let me suggest it would be a useful experience to go through the
> exercise of writing a recursive version that (for example) gcc
> does compile as a loop (normally -O2 or -Os will get you there,
> often -O1 won't).  You can easily check for loopness by using -S
> and looking at the generated assembly, noting the absence of
> recursive calls for the function(s) in question.
> 
> Functions like this one usually aren't transformed directly
> into loops, because there is compuation that happens after the
> recursive call, which makes the transformation difficult.  The
> interface makes it hard to write the function body directly to
> avoid that, because after the rest of the list is copied we
> have to return a pointer to the head of the list.  Usually this
> problem is avoided by introducing a recursive helper function
> that does most of the work, with the original function just
> calling the helper function and then returning a value.  For
> the function here we might do that this way:
> 
>     struct node *
>     CopyList( struct node *list ){
>         struct node *result = list;
>         copy_tail( &result );
>         return  result;
>     }
> 
> The function copy_tail() can be written fairly easily using a
> recursive formulation that gcc will turn into a loop.
> 

Yes, that's the sort of "massaging" I was talking about - but thanks for
making it a little more explicit.  The aim is always to write code that
is tail-recursive - i.e., the recursive call is just before (or even in)
the "return" statement.

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

#60240

David Brown <david.brown@hesbynett.no> writes:

> On 17/04/15 00:46, Tim Rentsch wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>> On 14/04/15 14:43, Ben Bacarisse wrote:
>>>> David Brown <david.brown@hesbynett.no> writes:
>>>>> At some unknown time, Ben Bacarisse wrote:
>>>>>> [edited to restore example of recursive version]
>>>>>>
>>>>>> But the clearest method of all is probably to use recursion:
>>>>>>
>>>>>>   struct node *CopyList(struct node *list)
>>>>>>   {
>>>>>>        if (list) {
>>>>>>             struct node *new_list = malloc(sizeof *new_list);
>>>>>>             new_list->data = list->data;
>>>>>>             new_list->next = CopyList(list->next);
>>>>>>             return new_list;
>>>>>>        }
>>>>>>        return NULL;
>>>>>>   }
>>>>>
>>>>> [end of edit]
>>>>>
>>>>> However, I agree that the recursive version is the neatest
>>>>> choice - the source code is clear and easily understood, and the
>>>>> compiler can handle the details of producing a loop.
>>>>
>>>> Sadly, I don't think existing C compilers turn this recursive
>>>> pattern into a loop.
>>>
>>> Perhaps not.  I suspect that with a little massaging, it would be
>>> possible to make a recursive version of the function that
>>> compilers /could/ turn into a loop - but I haven't tried it out.
>>
>> Let me suggest it would be a useful experience to go through the
>> exercise of writing a recursive version that (for example) gcc
>> does compile as a loop (normally -O2 or -Os will get you there,
>> often -O1 won't).  You can easily check for loopness by using -S
>> and looking at the generated assembly, noting the absence of
>> recursive calls for the function(s) in question.
>>
>> Functions like this one usually aren't transformed directly
>> into loops, because there is compuation that happens after the
>> recursive call, which makes the transformation difficult.  The
>> interface makes it hard to write the function body directly to
>> avoid that, because after the rest of the list is copied we
>> have to return a pointer to the head of the list.  Usually this
>> problem is avoided by introducing a recursive helper function
>> that does most of the work, with the original function just
>> calling the helper function and then returning a value.  For
>> the function here we might do that this way:
>>
>>     struct node *
>>     CopyList( struct node *list ){
>>         struct node *result = list;
>>         copy_tail( &result );
>>         return  result;
>>     }
>>
>> The function copy_tail() can be written fairly easily using a
>> recursive formulation that gcc will turn into a loop.
>
> Yes, that's the sort of "massaging" I was talking about - but
> thanks for making it a little more explicit.  The aim is always to
> write code that is tail-recursive - i.e., the recursive call is
> just before (or even in) the "return" statement.

Normally tail calls need to be an entire return expression, not
just part of one, and not before a return is done.  In the
function above the call to copy_tail() is not a tail call.

In functions whose return type is (void), a sequence like

    foo();
    return;

is a tail call (depending on the return type of foo()).  I like
to think of this as

    return  foo();

if C would allow (as C++ does) void-valued expressions to be
used in return statements of functions with (void) return type.

In functions whose return type is not (void), a tail call has to
be an entire return expression, except it can be "the last part
of" a return expression in certain cases involving operators
with sequence points.  Some examples of the latter type (for
illustration assume we are defining a recursive function foo()):

    return  *p = t,  foo( &t->next );

    return  **p  ?  foo( &something( p )->next )  :  0;

    return  some_test( whatever )  &&  foo( next( whatever ) );

The last case can be a tail call if foo() always returns 0 or 1
otherwise.  That would not be true if the call to foo() were on
the left rather than on the right.

I'm still waiting for your compiles-to-a-loop version of
copy_tail().  :)

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web