De-allocating linked lists 
Author Message
 De-allocating linked lists

Would it be safe to write a single function to de-allocate linked lists
of different structure types? I'm assuming the first member of each
structure type would be the link, so it would look something like this:

void dealloclist(void *this) {

        struct listmember {
                struct listmember *next;
        } p, q;

        p = (struct listmember)this;
        while ( p != NULL ) {
                q = p->next;
                free( p );
                p = q;
        }

Quote:
}

I'm imagining that free() doesn't actually need to know the type
originally allocated because all it's concerned with is block size and
location. This function should provide the correct block location, and
I'm assuming the correct block size is recorded by the heap manager
somewhere internally (which it can recover if it knows where the block
is).

Or is this a Grave Violation of Generally Accepted Programming Practice?

- Anton
--



Thu, 16 Jan 2003 03:00:00 GMT  
 De-allocating linked lists

Quote:

> Would it be safe to write a single function to de-allocate linked lists
> of different structure types? I'm assuming the first member of each
> structure type would be the link, so it would look something like this:

> void dealloclist(void *this) {

>    struct listmember {
>            struct listmember *next;
>    } p, q;

You mean *p, *q;

Quote:
>    p = (struct listmember)this;

You mean p = this;

Quote:
>    while ( p != NULL ) {
>            q = p->next;
>            free( p );
>            p = q;
>    }
> }

> I'm imagining that free() doesn't actually need to know the type
> originally allocated because all it's concerned with is block size and
> location.

free() has no way to know the type of data stored in the area it
is freeing.

Quote:
> This function should provide the correct block location, and
> I'm assuming the correct block size is recorded by the heap manager
> somewhere internally (which it can recover if it knows where the block
> is).

Yes.

Quote:
> Or is this a Grave Violation of Generally Accepted Programming Practice?

The basic rule in the standard that supports this sort of
practice is that a pointer to the first member of a structure,
"suitably converted", points to the structure, and vice versa.
This rule can obviously be used to ensure that trickery like the
above will work if the first member is always the same type,
e.g., void *.  It doesn't ensure that it'll work if different
structures start with different types, e.g., struct list_type_1 *
and struct list_type_2 *.
--



Fri, 17 Jan 2003 03:00:00 GMT  
 De-allocating linked lists

Quote:

> void dealloclist(void *this) {
>         struct listmember {
>                 struct listmember *next;
>         } p, q;
>         p = (struct listmember)this;
>         while ( p != NULL ) {
>                 q = p->next;
>                 free( p );
>                 p = q;
>         }
> }
> ...
> Or is this a Grave Violation of Generally Accepted Programming Practice?

Well, the error in the code (bad cast) is a Grave Violation.
However, the general idea of using a type pun of a pointer to
a structure with "the same" initial member is more or less
workable; The C standard guarantees that the layout of strutures
with identical initial member types is the same, that pointers
to structs can be converted to void* and back without loss of
information, and that pointers to structures of all kinds have
conformable representations.

Note that this scheme doesn't work right when some of the actual
structure members are the primary handles to allocated storage.
Therefore, in general you're better off writing a separate
list-freeing function for each data type.
--



Fri, 17 Jan 2003 03:00:00 GMT  
 De-allocating linked lists
On 30 Jul 2000 16:03:56 GMT, Anton Treuenfels

Quote:

>Would it be safe to write a single function to de-allocate linked lists
>of different structure types? I'm assuming the first member of each
>structure type would be the link, so it would look something like this:

>void dealloclist(void *this) {

>    struct listmember {
>            struct listmember *next;
>    } p, q;

>    p = (struct listmember)this;
>    while ( p != NULL ) {
>            q = p->next;
>            free( p );
>            p = q;
>    }
>}

>I'm imagining that free() doesn't actually need to know the type
>originally allocated because all it's concerned with is block size and
>location. This function should provide the correct block location, and
>I'm assuming the correct block size is recorded by the heap manager
>somewhere internally (which it can recover if it knows where the block
>is).

>Or is this a Grave Violation of Generally Accepted Programming Practice?

>- Anton

You are guaranteed that there is no padding before the first member of
a struct.  What I don't know is if a pointer to struct a and a pointer
to struct b are guaranteed to "have the same format."  If so (which is
the practical situation), then your concept should work.  If not, you
could still make it work by having all structs start with a void
pointer and cast it when you need it in your other functions.

Your code however has a couple of problems:

        p and q need to be pointers, not structs.

        The cast in the first executable is both unnecessary and
incorrect.  If you insist on keeping it, change it to (struct
listmember *).

<<Remove the del for email>>
--



Fri, 17 Jan 2003 03:00:00 GMT  
 De-allocating linked lists
On 30 Jul 2000 16:03:56 GMT, Anton Treuenfels

Quote:

>I'm imagining that free() doesn't actually need to know the type
>originally allocated because all it's concerned with is block size and
>location. This function should provide the correct block location, and
>I'm assuming the correct block size is recorded by the heap manager
>somewhere internally (which it can recover if it knows where the block
>is).

>Or is this a Grave Violation of Generally Accepted Programming Practice?

If each struct in the list contains its own dynamically allocated
members, this would result in a memory leak. This would, I imagine, be
quite common in practice.

--
Hong Ooi                    | Centre for Maths and its Applications/

Ph: (02) 6267 4140          | Australian National University
                            | ACT 0200 Australia
--



Sat, 18 Jan 2003 03:00:00 GMT  
 De-allocating linked lists


Quote:
> Would it be safe to write a single function to de-allocate linked lists
> of different structure types? ...

...

No problem at all.

Quote:
> I'm imagining that free() doesn't actually need to know the type

...

Keeping the phrasing colloquial rather than exact: malloc() returns a void
pointer -- only when _you_ are using that block of memory you are
assigning it some type. So if you want to free() that block you can use
any type of pointer.

--
Greetings from
 _____
 /_|__| Auke Reitsma, Delft, The Netherlands.
/  | \  -------------------------------------
        Remove SPAMBLOCK from my address ...
--



Sat, 18 Jan 2003 03:00:00 GMT  
 De-allocating linked lists

Quote:


> > void dealloclist(void *this) {
> >         struct listmember {
> >                 struct listmember *next;
> >         } p, q;
> >         p = (struct listmember)this;
> >         while ( p != NULL ) {
> >                 q = p->next;
> >                 free( p );
> >                 p = q;
> >         }
> > }
> > ...
> > Or is this a Grave Violation of Generally Accepted Programming Practice?

> Well, the error in the code (bad cast) is a Grave Violation.

True, but any decent compiler would be only too happy to point that out.
The really good ones would no doubt reach through the screen and slap me
up a bit as well.

Quote:
> However, the general idea of using a type pun of a pointer to
> a structure with "the same" initial member is more or less
> workable; The C standard guarantees that the layout of strutures
> with identical initial member types is the same, that pointers
> to structs can be converted to void* and back without loss of
> information, and that pointers to structures of all kinds have
> conformable representations.

> Note that this scheme doesn't work right when some of the actual
> structure members are the primary handles to allocated storage.
> Therefore, in general you're better off writing a separate
> list-freeing function for each data type.

Ah, I think you're saying that if some of the structure members are
themselves the only pointers to dynamically allocated memory, then
calling this function first would result in a memory leak. YesBut - if I
was somehow clever enough to deal with those before I freed the list, it
should be ok, no?

- Anton
--



Sun, 19 Jan 2003 03:00:00 GMT  
 De-allocating linked lists

Quote:


[...]
>> Note that this scheme doesn't work right when some of the actual
>> structure members are the primary handles to allocated storage.
>> Therefore, in general you're better off writing a separate
>> list-freeing function for each data type.
> Ah, I think you're saying that if some of the structure members are
> themselves the only pointers to dynamically allocated memory, then
> calling this function first would result in a memory leak. YesBut - if I
> was somehow clever enough to deal with those before I freed the list, it
> should be ok, no?

OK, yes. But then, you just might be better off switching your
programming language. Your plan is a re-invention of the concept of
destructors, and automatic destructor calling methods. C++ could
reduce the hassle of implementing all this drastically, as it is a
'native' concept there, unlike in C.
--

Even if all the snow were burnt, ashes would remain.
--



Sun, 19 Jan 2003 03:00:00 GMT  
 De-allocating linked lists

Quote:
> Would it be safe to write a single function to de-allocate linked lists
> of different structure types? I'm assuming the first member of each
> structure type would be the link, so it would look something like this:

> void dealloclist(void *this) {

> struct listmember {
> struct listmember *next;
> } p, q;

> p = (struct listmember)this;
> while ( p != NULL ) {
> q = p->next;
> free( p );
> p = q;
> }
> }

> I'm imagining that free() doesn't actually need to know the type
> originally allocated because all it's concerned with is block size and
> location. This function should provide the correct block location, and
> I'm assuming the correct block size is recorded by the heap manager
> somewhere internally (which it can recover if it knows where the block
> is).

> Or is this a Grave Violation of Generally Accepted Programming Practice?

What I found usefull is a structure that resembles what you were writing:

typedef struct
    linkListStruct
    {
    unsigned short                 type;
    struct linkListStruct    *    prev;
    struct linkListStruct    *    next;
    } linkListElm;

I found this to be a very usefull structure to have for double linked lists:
type type field contains one bit stating "this is the head/tail" of the
double linked list, and the other 15 bits you can use for a "structure
identifier" to be used by the programmer itself. It can be used with:

typedef struct                        /* some data structure to include in a
double linked list */
    {
    linkListElm        link;
    ... other data of the structure
    } someStructure;

and

linkListElm        headerOfList;        /* The head/tail of the double
linked list */

and is easily managed by macro's doing all sorts of list manipulation (e.g.
different types of structures in the same double linked list).

In any case, my point being: to avoid any of the problems the other replies
mentioned (e.g. you don't know what to do with any memory that may have been
claimed by the process in the "actual" structure (someStructure)), you could
either add some behaviour based on the "type", or you can add some function
that can do numerous things with the structure. E.g.

typedef struct
    linkListStruct
    {
    unsigned short                 type;
    void                                (someFunc *)(int behaviour, struct
linkListStruct *linkListPtr);
    struct linkListStruct    *    prev;
    struct linkListStruct    *    next;
    } linkListElm;

I added the 'behaviour' parameter as an example (e.g. to "initialize" the
'someStructure' members, or free them), but you could also have different
functions for each desired behaviour.

Come to think of it, some of this stuff sounds a bit like what C++ would
offer.

Hope you got the idea of what I was talking about, since I didn't cover all
details :-)

Regards,
    Pieter Winter

--



Tue, 21 Jan 2003 03:00:00 GMT  
 De-allocating linked lists

Quote:

> typedef struct
>     linkListStruct
>     {
>     unsigned short                 type;
>     struct linkListStruct    *    prev;
>     struct linkListStruct    *    next;
>     } linkListElm;

> I found this to be a very usefull structure to have for double linked
lists:
> type type field contains one bit stating "this is the head/tail" of the
> double linked list, and the other 15 bits you can use for a "structure
> identifier" to be used by the programmer itself. It can be used with:

Partially nitpicking, partially because the answers may educate me:

Why would you use a bit to determine head/tail? Isn't that information
automatically provided by the prev and/or next being NULL?

If adding a bitfield is necessary/desirable, why not choose the type value
so that the struct aligns naturally?

Michael Christie
--



Tue, 21 Jan 2003 03:00:00 GMT  
 De-allocating linked lists

Quote:

> Why would you use a bit to determine head/tail? Isn't that information
> automatically provided by the prev and/or next being NULL?

Doubly-linked lists work best if there is a distinct head node,
and the links form a complete circuit in both directions.
Then the code for manipulating the lists is faster because no
special tests for head/tail are needed.

Quote:
> If adding a bitfield is necessary/desirable, why not choose the
> type value so that the struct aligns naturally?

The head/tail bit isn't actually necessary, so long as there
is no attempt to free the whole list starting anywhere other
than the head node.
--



Wed, 22 Jan 2003 03:00:00 GMT  
 De-allocating linked lists

Quote:


> > typedef struct
> >     linkListStruct
> >     {
> >     unsigned short                 type;
> >     struct linkListStruct    *    prev;
> >     struct linkListStruct    *    next;
> >     } linkListElm;

> > I found this to be a very usefull structure to have for double linked
> lists:
> > type type field contains one bit stating "this is the head/tail" of the
> > double linked list, and the other 15 bits you can use for a "structure
> > identifier" to be used by the programmer itself. It can be used with:

> Partially nitpicking, partially because the answers may educate me:

> Why would you use a bit to determine head/tail? Isn't that information
> automatically provided by the prev and/or next being NULL?

True. Except in this case I'm not using the NULL values for that. At some
point when dealing with double linked lists, I was getting tired of checking
elements for being "at the head" or "at the tail" of a double linked list.
So I introduced a "master" element. The bit is used to distinguish the
master from the elements.

linkListElm    master;

The master would be initialized with the "master" flag set and with the next
and prev pointer pointing to itself. An element would be initialized with
the "master" flag clear and with the next and prev pointer set to NULL (i.e.
"not in double linked list").

The real benifit (at least complexity wise, since "code" wise the "normal"
way of doing is probably more fit for code-optimisation) is when removing an
element:
        elm->next->prev = elm->prev;
        elm->prev->next = elm->next;
        elm->next = NULL;
        elm->prev = NULL;

In this case you really don't care what the head or the tail of the list is.
You don't even care in which double linked list you are.

It would have been posible to omit the clearing of next and prev when
removing an element, but this lends itself better for error tracking.

Adding an element to the head or tail of a list is a similar simple task.

The method extends itself easily (or "without too much effort") to a
structure that can handle structures that reside in 2 double linked lists
simultaneously (or 3 or more).

The method also allows itself to be implemented using macros.

Further, since the structure only needs a "master" flag, the other 15 bits
can be used as type information about the structure that the linkListElm is
used in. (In practise, I've never used a double linked list that contains
multiple structure types, although the algorithm allows it).

Quote:
> If adding a bitfield is necessary/desirable, why not choose the type value
> so that the struct aligns naturally?

You are right. There _are_ some architectures that allow pointer to be
aligned at "word" boundaries (e.g. the QUICC), but I'm not sure if there is
any "C" rule that specifies anything about that.

Since the linkListElm will be as a first element of another structure,
alignment may be less efficient there also, in which case the shifting
around (at least in this case) does not help.

Pieter Winter
--



Wed, 22 Jan 2003 03:00:00 GMT  
 De-allocating linked lists


Quote:

<snip>
> > If adding a bitfield is necessary/desirable, why not choose the
> > type value so that the struct aligns naturally?

> The head/tail bit isn't actually necessary, so long as there
> is no attempt to free the whole list starting anywhere other
> than the head node.

Knowing what the head element of the list is, is easier if you scan through
the list. Obviously, this could be done by "knowing" what the head element
is, or by having this "head/tail" bit. It works for me, not requiring to
know what the head/tail of the double-linked list that a given item resides
in.

Quote:
> --


--



Fri, 31 Jan 2003 03:00:00 GMT  
 De-allocating linked lists

Quote:


> > The head/tail bit isn't actually necessary, so long as there
> > is no attempt to free the whole list starting anywhere other
> > than the head node.
> Knowing what the head element of the list is, is easier if you scan through
> the list. Obviously, this could be done by "knowing" what the head element
> is, or by having this "head/tail" bit. It works for me, not requiring to
> know what the head/tail of the double-linked list that a given item resides
> in.

It is not necessary to know which node is the head/tail node
of a doubly-linked list in order to perform local operations
on it (insert/remove nodes).  However, the head/tail node
("attachment point") must be known, or in some way treated
specially, when performing global operations such as searching
of freeing the entire list.
--



Sat, 01 Feb 2003 10:36:41 GMT  
 
 [ 14 post ] 

 Relevant Pages 

1. link list of a linked list (chained links?)

2. Repeatedly Allocating/Deallocating Memory

3. Allocating/Deallocating Memory in a DLL and EXE causes Assertion-Error

4. string allocated in DLL to be deallocated in calling program

5. Allocating/DeAllocating Memory associated to an array of structures

6. CStringT allocate/deallocate issues is VC7?

7. Problem De-allocating Memory in variable sized arrays

8. Dynamic memory allocate/deallocate crashes on release build

9. Q: allocating/deallocating LPBITMAPINFO structure.

10. Incompatible NULL Assignments || Linked List inside Linked List

11. Clearing Memory || Linked List INSIDE of a Linked List

12. Freeing a Linked List inside of a Linked List

 

 
Powered by phpBB® Forum Software