Deallocating linked lists of linked lists

Deallocating linked lists of linked lists

[cis.ohio-state.edu!magnus.acs.ohio-state.edu!zaphod.mps.ohio-state.edu!uw]

Here's a good question...

I wrote a program that simulates a graph, and thus I need to have a linked
list, one of whose components is a linked list, showing on which vertices
that particular vertex is incident upon.

Well, enough of the nitty gritty.  Here is the question.  If I have a
variable that is a record, and one of the fields of the record is the head
pointer to another linked list, will it be sufficient to just deallocate the
one variable, or do I have to go inside and deallocate everthing?  Here are
my type declarations:

 type pointer is access edge;

 type edge is record
  incident_on : pointer;
  id_number   : positive;
 end record;

 type incidence_node;
 type edge_list is access incidence_node;

 type incidence_node is record
  item : edge;
  next : edge_list;
 end record;

 type vertex is record
  data      : node_item_type;
  id_number : positive;
  incidence : incidence_list;
 end record;

 type graph is access vertex;

So how would I dynamically deallocate something of type graph?

Thanks for any help.

-- 
Jason Lee   jplee@oboe.calpoly.edu   jlee@cash.busfac.calpoly.edu    Giants
e ^ i*pi + 1 = 0    The most beautiful equation in mathematics.      Magic
For all sad words of tongue and pen, the saddest are these:          Number:
     "It might have been."            John Greenleaf Whittier        150

Re: Deallocating linked lists of linked lists

[Mark A Biggar]

In article <1993Apr20.044555.154198@zeus.calpoly.edu> jplee@cymbal.calpoly.edu 
(JASON LEE) writes:
>I wrote a program that simulates a graph, and thus I need to have a linked
>list, one of whose components is a linked list, showing on which vertices
>that particular vertex is incident upon.
>Well, enough of the nitty gritty.  Here is the question.  If I have a
>variable that is a record, and one of the fields of the record is the head
>pointer to another linked list, will it be sufficient to just deallocate the
>one variable, or do I have to go inside and deallocate everthing?  Here are
>my type declarations:
> type pointer is access edge;
> type edge is record
>  incident_on : pointer;
>  id_number   : positive;
> end record;
> type incidence_node;
> type edge_list is access incidence_node;
> type incidence_node is record
>  item : edge;
>  next : edge_list;
> end record;
> type vertex is record
>  data      : node_item_type;
>  id_number : positive;
>  incidence : incidence_list;
> end record;
> type graph is access vertex;
>So how would I dynamically deallocate something of type graph?

If your system supports garbage collection, then just deallocating
the top record should be sufficient.  If it doesn't, then you will
have to recursivly deallocate everything from the bottom up.  The only
portable way is the latter, because most Ada systems do not support
garbage collection.  Without CG, you need one call to unchecked_deallocation
for each new allocator.

--
Mark Biggar
mab@wdl1.wdl.lorla.com

Re: Deallocating linked lists of linked lists

[cis.ohio-state.edu!zaphod.mps.ohio-state.edu!caen!msuinfo!netnews.upenn.e]

In article <1993Apr20.044555.154198@zeus.calpoly.edu>, jplee@cymbal.calpoly.edu
 (JASON LEE) writes:
|> Here's a good question...
|> 
|> I wrote a program that simulates a graph, and thus I need to have a linked
|> list, one of whose components is a linked list, showing on which vertices
|> that particular vertex is incident upon.
|> 
|> Well, enough of the nitty gritty.  Here is the question.  If I have a
|> variable that is a record, and one of the fields of the record is the head
|> pointer to another linked list, will it be sufficient to just deallocate the
|> one variable, or do I have to go inside and deallocate everthing?  Here are
|> my type declarations:
|> 
|> 
|>  << stuff deleted >>

Depends upon what you are using to perform the deallocation.  Typically,
a deallocation process deallocates one record during one call to the
process.  However, sometime when components are packaged, they might
contain a dealloation process that "knows" the structure of your data,
hence it can use that structure to properly deallocate the records in
the structure.  Most low level deallocation processes don't "know"
the structure you are using, hence they cannot use information in the
record passed to the deallocator to deallocate a structure.  

By your posting it sounds to me as if you are using a low level
deallocator with a structure you are encapsulating, in which case,
at best the deallocator will return the space to the heap of
available space -- at worst, the deallocator might just throw it
away and not recycle it, i.e., you have to write a low level
set of routines to maintain and recycle space!!

+------------------------------------------------------------------+
|  John (Jack) Beidler				                   |
|  Prof. of Computer Science Internet: BEIDLER@JAGUAR.UOFS.EDU     |
|  University of Scranton              beidler@guinness.cs.uofs.edu|
|  Scranton, PA 18510	      Bitnet : BEIDLER@SCRANTON            |
|                                                                  |
|          Phone: (717) 941-7446	 FAX:   (717) 941-4250     |
+------------------------------------------------------------------+