Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2007-12-18
2007-12-18
Bullock, Jr., Lewis A. (Department: 2195)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C718S102000
Reexamination Certificate
active
09676552
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.
REFERENCES:
patent: 4896261 (1990-01-01), Nolan
patent: 5185861 (1993-02-01), Valencia
patent: 5379297 (1995-01-01), Glover et al.
patent: 5452452 (1995-09-01), Gaetner et al.
patent: 5819286 (1998-10-01), Yang et al.
patent: 5872938 (1999-02-01), Williams
patent: 6003101 (1999-12-01), Williams
patent: 6044393 (2000-03-01), Donaldson et al.
patent: 6317872 (2001-11-01), Gee et al.
patent: 6463484 (2002-10-01), Moss
patent: 6609161 (2003-08-01), Young
patent: 6964046 (2005-11-01), Ogus et al.
Lee, Pen-Nan et al. “Object oriented Design for a Distributed Priority Queue.” IEEE. 1995.
Gallo, Giorgio et al. “Shortest Path Algorithms”. Springer Netherlands. Vol. 13, No. 1 / Dec. 1988.
Fredman, Michael L. et al. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” ACM. 1987.
Liao, Andrew M. “Three Priority Queue Applications Revisited.” Algorithmica (1992).
Black, David L. “Scheduling Support for Concurrency and Parallelism in the Mach Operating System.” IEEE. May 1990.
Bullock, Jr. Lewis A.
Lee & Hayes PLLC
LandOfFree
Data structure for efficient enqueuing and dequeuing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data structure for efficient enqueuing and dequeuing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data structure for efficient enqueuing and dequeuing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3842284