kminor@ms.uky.edu (Kevin R. Minor) (11/30/89)
Hello. I am doing a term paper, and I've run into an interesting question. I am }iattempting to implement an AVL tree. I have the insertion and deletion routines. I'm using pointers to access the nodes of the tree. Here's my question. Is there a way to free up the entire memory without having to deallocate each node? If I can free the entire tree structure in one step, it will dramatically save in run-time. Either way, I'd like to know for my paper. Thanks in advance. Kevin (kminor@ms.uky.edu) -- Not much going on around here.
cpcahil@virtech.uucp (Conor P. Cahill) (12/01/89)
In article <13367@s.ms.uky.edu>, kminor@ms.uky.edu (Kevin R. Minor) writes: > Here's my question. Is there a way to free up the entire memory > without having to deallocate each node? If I can free the entire tree > structure in one step, it will dramatically save in run-time. Either way, > I'd like to know for my paper. It depends upon how you are allocating the space for the tree. If you are using malloc() to allocate each node individually, then you cannot free the entire list in a single operation. If you use malloc() to allocate room for say 1000 of these entries and you handle the distribution of the pointers yourself, you can free the big chunks as opposed to the individual pointers. This could be done as follows: struct mydata { .... struct mydata * p;}; static struct mydata * head; static struct mydata * top; static struct mydata * ptr; static int count; struct mydata * mymalloc() { if( count == 0 ) { count = 1000; ptr = (cast..) malloc(count * sizeof(struct...) /* check for valid malloc return here */ if( head == NULL ) { head = ptr; } else { top->p = ptr; } top = ptr++; top->p = NULL; count--; } count--; return(ptr++); } myfree() { while(head != NULL) { p = head; head = head->p; free(p); } count = 0; } NOTE-> The above code is untested, uncompiled, etc. So there are sure to be typos, and possibly real problems, but you should get the idea. And finally, if you don't use any code that may use malloc() (and remember, lots of section 3 commands use malloced areas) you could do the following: saveptr = sbrk(0); /* do all of your allocating and such stuff */ brk(saveptr); Note that the use of brk() will break any of the malloc() family of functions, so this is only usable if you are doing your own allocating. -- +-----------------------------------------------------------------------+ | Conor P. Cahill uunet!virtech!cpcahil 703-430-9247 ! | Virtual Technologies Inc., P. O. Box 876, Sterling, VA 22170 | +-----------------------------------------------------------------------+
djones@megatest.UUCP (Dave Jones) (12/01/89)
From article <13367@s.ms.uky.edu>, by kminor@ms.uky.edu (Kevin R. Minor): > Hello. > Hello. > ... > Here's my question. Is there a way to free up the entire memory > without having to deallocate each node? Here's my answer. Sort of. Define a class of objects, called "heaps" or whatever, that allocate packets by dividing up much larger blocks of memory. Dedicate a heap to each large composite structure which you may want to zap all at once. When it comes time to recycle the memory, you give it back to malloc() in big chunks rather than little ones. I use a couple of packages like that extensively. One allocates packets of a fixed size out of a free-list. The other allocates arbitrary sized packets, which must be returned in the reverse order, by means of _mark_ and _pop_ procedures. In both cases, the _allocate_ and _free_ procedures are implemented as macros, and are much, much faster than the vendor supplied malloc() and free() which they call only intermittently. Here's the header-file for the fixed size heap package, to give you the flavor of the thing. typedef union Heap_unit { /* The "next" variant is used to link free packets, * and to link blocks of packets: */ union Heap_unit* next; /* The rest are only dummies, to give the structure the most * general alignment characteristic, for better portability. */ float Xflt; double Xdbl; char Xchar; short Xshort; long Xlong; char *Xcharp; void *Xvoidp; void (*Xfuncp)(); } Heap_Unit; typedef struct heap /* heap of packets of a fixed size */ { int packet_size; /* ... in units of sizeof(Heap_unit) */ int num_elements; /* number of packets to allocate in next block */ Heap_Unit* cache; /* linked list of all blocks of packets */ Heap_Unit* next_free; /* linked free store of packets */ Heap_Unit* tmp; /* temporary, used in alloc and free macros */ }Heap; extern Ptr Heap_underflow(); /* Public macros */ #define Heap_alloc(obj) \ ((obj)->next_free == 0 ? \ Heap_underflow(obj): \ (Ptr) ( (obj)->tmp = (obj)->next_free, \ (obj)->next_free = (obj)->next_free->next, \ (obj)->tmp \ ) \ ) #define Heap_free(obj,packet) \ ((void)( (obj)->tmp = (obj)->next_free, \ (obj)->next_free = (Heap_Unit*)packet, \ ((Heap_Unit*)packet)->next = (obj)->tmp \ ) \ ) /* Public routines */ extern Heap* Heap_new(); extern Heap* Heap_init(); extern Heap* Heap_init_sized(); extern Heap* Heap_clean(); extern void Heap_dispose();
greg@cheers.uucp (Greg Onufer) (12/02/89)
kminor@ms.uky.edu (Kevin R. Minor) writes: >Here's my question. Is there a way to free up the entire memory >without having to deallocate each node? If I can free the entire tree >structure in one step, it will dramatically save in run-time. Either way, >I'd like to know for my paper. Well, calling exit() will do exactly what you want. :-) Cheers!greg