Data structure for efficient enqueuing and dequeuing

• US 7,310,649 B1
• Filed: 09/30/2000
• Issued: 12/18/2007
• Est. Priority Date: 05/15/2000
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ginsberg, Michael
• Primary Examiner(s): BULLOCK JR, LEWIS ALEXANDER
• Application Number:
  US09/676,552
• Time in Patent Office: 2,635 Days
• Field of Search: 709/100, 709/101, 709/102, 718/1, 718100-108, 719310-332, 707/103.R, 707/103.Y
• US Class Current: 1/1
• CPC Class Codes: G06F 2205/064 Linked list, i.e. structure using pointers, e.g. allowing non-contiguous address segments in one logical buffer or dynamic buffer space allocation
• CPC Class Codes: G06F 2205/106 Details of pointers, i.e. structure of the address generators
• CPC Class Codes: G06F 5/10 having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using random access memory G06F5/065 takes precedence
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

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.

Claims

1. A method implemented at least in part by a computing device for adding a new entity having a rank within a plurality of N ranks to a plurality of entities as represented in a data structure for efficiently ordering the entities, the entities also having respective ranks within the plurality of N ranks, the method comprising:

of a plurality of array entries of an array having fewer than N entries over which the plurality of N ranks are distributed, such that the array entries correspond to respective ranges of ranks, determining a particular array entry corresponding to a range of ranks in which the rank of the new entity lies;

adjusting the particular array entry to point to the new entity in response to determining that the particular array entry currently points to null;

adjusting the particular array entry to point to the new entity in response to determining that the particular array entry currently points to an entity having a rank less than the rank of the new entity;

linking the new entity into a vertically linked list linking in at least one direction a corresponding subset of the plurality of entities having an identical rank, in response to determining that the rank of the new entity is equal to the rank of any other entity within the plurality of entities for a respective range of ranks associated with an array entry; and

otherwise, linking the new entity into a horizontally linked list linking at least a subset of the plurality of entities in at least a descending rank order direction, the entities in the horizontally linked list having unique ranks as compared to the ranks of other entities in the horizontally linked list that spreads over the plurality of ranges of the array, wherein at least one entity of the plurality of entities is a thread, the rank of the entity is a priority for the thread, and the array is a priority queue.

2. The method of claim 1, further comprising adjusting a head pointer pointing to an entity having a greatest rank of the plurality of ranks of the plurality of entities to point to the new entity in response to determining that the rank of the new entity is greater than the rank of the entity of the plurality of entities to which the head pointer currently points.

3. The method of claim 1, wherein the method is performed by execution of a computer program stored on a machine-readable medium by a processor.

4. A machine-readable medium having a data structure stored thereon, the data structure configured to be accessible by a computer, the data structure comprising:

a plurality of entities having respective ranks within a plurality of N ranks, at least one of the entities being a thread having a rank that is a priority for the thread;

an array having a plurality of N array entries wherein the array entries are fewer than the plurality of N ranks and are associated with respective ranges of the N ranks, at least one of the array entries pointing to an entity of the plurality of entities having a greatest rank that is within the range of ranks associated with the at least one array entry, wherein the data structure is a priority queue;

a horizontally linked list of at least a subset of the plurality of entities, each of the entities in the horizontally linked list having a respective unique rank relative to the ranks of the other entities in the horizontally liked list, the horizontally linked list arranged in rank order, wherein at least some of the entities of the horizontally linked list are identified by the array entries as having the greatest rank within that range of ranks; and

a vertically linked list of a subset of the plurality of entities that links at least one entity of the horizontally linked list with other entities of the plurality of entitles that have identical rank.

5. The machine-readable medium of claim 4, wherein the vertically linked list links the subset of entities in a first vertical direction and in a second vertical direction.

6. The machine-readable medium of claim 4, the data structure further comprising a head pointer, the head pointer pointing to an entity having a greatest rank relative to the ranks of the other entities in the data structure.

7. The machine-readable medium of claim 4, wherein the horizontally linked list is arranged in ascending rank order.

8. The machine-readable medium of claim 4, wherein the plurality of N ranks are equally distributed over the plurality of array entries.

9. The machine-readable medium of claim 4, wherein at least two entities having respectively different ranks correspond to the associated range of ranks of one of the array entries.

10. The machine-readable medium of claim 4, wherein at least one of the array entries points to null indicating that no entity corresponds to the range of ranks associated with the at least one array entry.

11. A method implemented at least in part by a computing device, the method for removing a particular entity from a plurality of entities of a data structure, the entities having respective ranks within a plurality of N ranks, the data structure including an array of one or more array entries, wherein N ranges of ranks are distributed over the array entries, and at least one array entry indicates an entity of the plurality of entities having the highest rank for that associated range of ranks, wherein at least the highest rank entities for the N respective ranges are linked in a horizontally linked list in a rank order such that elements in the horizontally linked list are also the head elements in a vertical linked list to entities having identical ranks, the method comprising:

in response to determining that the particular entity is present within the vertically linked list, delinking the particular entity from the vertically linked list;

in response to determining that the particular entity is present within the horizontally linked list, delinking the particular entity from the horizontally linked list;

in response to determining that one of the array entries points to the particular entity, adjusting the array entry to point to one of null or another one of the plurality of entities; and

storing the data structure on a single machine-readable medium accessible by the computing device, wherein at least one of the entities is a thread having a rank that is a priority for the thread, and wherein the array is a priority queue.

12. The method of claim 11, wherein the one or more array entries have respective ranges of ranks, and adjusting the array entry further comprises:

in response to determining that the particular entity was present within the vertically linked list, adjusting the array entry to point to a next entity within the vertically linked list.

13. The method of claim 12, wherein adjusting the array entry further comprises:

otherwise, in response to determining that the particular entity was present within the horizontally linked list, and that the rank of a next entity within the horizontally linked list is within the corresponding range of ranks for the array entry, adjusting the array entry to point to the next entity within the horizontally linked list.

14. The method of claim 13, wherein adjusting the array entry further comprises:

otherwise, adjusting the array entry to point to null.

15. The method of claim 11, further comprising:

in response to determining that a head pointer points to the particular entity, adjusting the head pointer to point to another one of the plurality of entities.

16. The method of claim 15, wherein adjusting the head pointer comprises:

in response to determining that the particular entity was present within the vertically linked list, adjusting the head pointer to point to a next entity within the vertically linked list.

17. The method of claim 16, wherein adjusting the head pointer comprises:

otherwise, in response to determining that the particular entity was present within the horizontally linked list, adjusting the head pointer to point to a next entity within the horizontally linked list.

18. The method of claim 11, wherein the method is performed by execution of a computer program stored on a machine-readable medium by a processor.