LINKED LIST IMPLEMENTATION in ANY GRASS PROGRAM
dpgerdes at zorro.cecer.army.mil
Thu Jun 11 12:35:20 EDT 1992
I have placed a new library on moon for anonymous ftp. It is in directory:
The library is called LINKM and is a memory manager for linked list
type of structures. It is not a linked list library. It provides simple
and efficient creation and disposal of structures. In my testing on
a sun machine it has been from 2.5 to 7 times faster than malloc/free. In
normal use, it should average around 5 times faster.
Here is the README that comes with it:
LINKED LIST MEMORY MANAGER
Assumption: malloc/free is inefficient and wasteful for things like
Workaround: I found myself frequently writing a program specific memory
manager to allocate large chunks which were then parcelled out.
Solution: Develop a generic linked list memory manger which does all the
work for you.
Descriptn: Remember those school days when we used Pascal?
Remember the new and dispose functions? Well that's what
you get with this library. The front end consists of
init(), new(), dispose(), and cleanup().
The innards is a memory manager which provides a structure on
demand and maintains its own efficient free memory list
to minimize the number of calls to malloc() and free().
Notes: The memory returned by link_new() is NOT guaranteed to be zeroed.
This could be added as an option later if there is demand.
The key item for this library is that the linked list is
a list of homogenous elements all of the same size. what
is returned by link_new() for a given token is always the
Unlike free(), the contents of the disposed structure are
no longer available. The link_dispose () modifies part of
the disposed of structure.
The minimum size of a structure is the size of a pointer.
If the structure size is less than that, it will be increased
to that minimum.
link_init (int size)
initialize the system for a given linked list. Size is the size
of your link structure.
Returns a token which identifies that list's manager.
You can have several different lists actively managed with
a different structure for each.
link_set_chunk_size (int cnt)
changes the number of structures requested in each malloc
If this routine is not called, the default is 100.
Calling this routine affects all further calls to link_init()
or until the next call to link_set_chunk_size().
link_cleanup (void *token)
Clean up all memory when done using the list.
should only be called once per list per run for best performance.
Pass it the token returned by link_init ()
link_new (void *token)
return a new memory slot, 'size' bytes long as specified by link_init()
This return pointer should be cast to your link structure type.
link_dispose (void *token, void *ptr)
pass it the token and a pointer to the structure to be de-allocated.
The memory is returned to the memory manager.
US Army Construction Engineering Research Lab
Spatial Analysis & Systems Team
dpgerdes at cerl.cecer.army.mil
(217) 352-6511 x591
More information about the grass-dev