Method for implementing dual link list structure to enable fast link-list pointer updates

Abstract

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.

Dependencies are inferred from the claim text.