Method for implementing dual link list structure to enable fast link-list pointer updates
US7111289B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 21, 2001 |
| Grant date | Sep 19, 2006 |
| Priority date | — |
| Expiry date | Jul 2, 2024 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F12/023
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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 fr…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.