A method is disclosed for free memory allocation in a linked list memory
scheme. Free lists are link lists designating available memory for data
storage. This method leverages the ability to read memory while
concurrently updating a pointer to the next location. Multiple free lists
are used to reduce the number of cycles necessary to allocate memory. The
number of entries in each free list is tracked. When memory becomes
available, it is spliced into the shortest free list to achieve balance
between the free lists. The free list structure disclosed consists of
head, head +1, and tail pointers where head +1 is the next logical
address pointed to from the head pointer location. The free list consists
only of the head and tail pointers. Each link list structure of memory to
be freed contains the head, head +1, and tail pointers. This allows us to
simultaneously allocate and free with only 1 memory cycle. This structure
provides the ability to free and allocate memory for further processing
without executing the allocate step. A whole logical data packet can be
spliced into a free list in one processing cycle. Utilization of the dual
link lists reduces the bandwidth requirements for free memory allocation.
Balancing of these dual lists is achieved by splicing a freed block of
memory into the shortest list. The splicing method disclosed also reduces
the processing cycles necessary to allocate and free memory.