Data structure for efficient enqueuing and dequeuing
US7310649B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Sep 30, 2000 |
| Grant date | Dec 18, 2007 |
| Priority date | — |
| Expiry date | Jan 28, 2024 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99944
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A data structure for efficient enqueuing and dequeuing is disclosed. The structure includes a horizontally linked list, an array, a vertically linked list, and a head pointer. Entity ranks are distributed over the array, where each array entry has a range of ranks. Each array entry points to null or the entity having the greatest rank within that entry's range. The horizontally linked list links at least a subset of ranked entities. Each entity in the linked list has a unique rank as compared to the ranks of the other entities in the list. Each vertically linked list links a subset of entities having an identical rank. The head pointer points to the entity that has the greatest rank. Methods for adding entities to and removing entities from the data structure are also disclosed. The invention can be used to enqueue threads to and dequeue threads from a priority queue.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.