Re: OT: Possible memory leak in an exercise of a C handbook

[Jeffrey Walton <noloader@gmail.com>]

On Wed, Dec 18, 2024 at 10:51 AM Franco Martelli <martellif67@gmail.com> wrote:
>
> On 17/12/24 at 22:09, Jeffrey Walton wrote:
> > [...]
> > There may be one logic error in the code -- if you insert one item,
> > then you may double free the node because you free 'p' and then you
> > free 'last'.
> >
> > I would rewrite the cleanup code like so:
> >
> >      void dealloc()
> >      {
> >          DIGIT *next, *p = head;
> >          while( p )
> >              next = p->next, free( p ), p = next;
> >      }
> >
> > Then add three test cases instead of one. Have a test case for 0
> > items, 1 item, and N items (like 8).
>
> I like the "for loop" statement because let me to define variables that
> are in use only inside the loop, so I can avoid variables that are
> visible in the full function block but are in use only in a (while(…)) loop:
>
> void dealloc()
> {
>          for( DIGIT *next, *p = head; p ; )
>                  next = p->next, free( p ), p = next;
> }
>
> The use of comma operator for me doesn't hurt, I always read the code
> from left to right.
> Thanks for this new optimization.

Another area you can optimize is `add_element` around line 23:

    /* Otherwise, find the last element in the list */
    for (p = head; p->next != NULL; p = p->next)
        ; /* null statement */

The code as written is Big O(n^2) since it walks the entire list on
each insert. So the code visits 1 node on the first insert, 2 nodes on
the second insert, 3 nodes on the 3rd insert, etc. 1+2+3+...+N is
(n*(n-1))/2, which is Big O(n^2).

You might try using `tail` to do the insert. Using `tail` will be
constant time or Big O(1).

If you want to measure the time, then use a string of 1000 or 5000
characters or so. The longer the string, the more time it will take to
insert under the current code.

Jeff