Search mechanism for a queue system

• US 6,032,207 A
• Filed: 12/19/1997
• Issued: 02/29/2000
• Est. Priority Date: 12/23/1996
• Status: Expired due to Term

• Current Assignee: Bull HN Information Systems Incorporated (Atos SE)
• Original Assignee: Bull HN Information Systems Incorporated (Atos SE)
• Inventors: Wilson, Peter J.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): WANG, ALBERT C
• Application Number:
  US08/994,882
• Time in Patent Office: 802 Days
• Field of Search: 707/3, 707/102, 707/1, 707/100, 710/52, 710/54
• US Class Current: 710/54
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A search mechanism improves the performance of a queue system including a queue for storing a plurality of data items and search mechanism by maintaining a key cache data structure having an array of entries, each of which have a key field and a pointer field. The key and pointer fields respectively of each cache entry are used for storing a key value of a different one of the enqueued data items of the queue and a pointer to that enqueued item. The key of each data item to be enqueued is used to generate an index value for accessing a location of the key cache array to obtain immediate access to the corresponding enqueued data item thereby reducing the search time for determining the proper point within the queue for inserting the data item to be added.

Claims

1. A queue system including a queue and a queue search mechanism, the queue containing a number of locations for storing a corresponding number of queued data items, each queued data item having a number of fields, a pair of the number of fields containing information for indicating locations of preceding and succeeding queued data items and at least one field for storing a key value, the queued data items being ordered in the queue according to key value, the queue search mechanism comprising:

(a) a key cache structure having a number of entry locations for storing a corresponding number of cache data item structures, each cache data item structure having a number of fields, a first field for storing a unique key value representative of a queued data item and a second field for storing a queue address pointer value designating the location of a queued data item; and

,

(b) a control mechanism for performing queue management operations, the control mechanism when inserting a new data item in the queue, first generates a cache index value derived from the key value contained in the new data item to be enqueued for accessing an entry location in the key cache structure, the control mechanism next determines the location in the queue into which the new data item is to be inserted by comparing the key value of the queued data item initially specified by the pointer value of the accessed entry location and as a function of the results of the comparison, searches through successive queued data items in a direction defined by the comparison until a match is obtained with the key value of the new data item defining the appropriate point in the queue into which the new data item is to be inserted.

2. The system of claim 1 wherein the control mechanism is operative upon detecting an identical comparison between the key value of the new data item and the key value of the designated queued data item to insert the new data item at the location specified by the pointer value of the accessed key cache entry.

3. The system of claim 1 wherein the control mechanism is operative upon detecting that the key value of the new data item is greater than the key value of the designated queued data item to search the queue in a forward direction starting with the location specified by the pointer value.

4. The system of claim 1 wherein the control mechanism is operative upon detecting that the key value of the new data item is less than the key value of the queued data item to search the queue in a backwards direction starting with the queued data item specified by the pointer value.

5. The system of claim 1 wherein following insertion of the new data item into the queue, the control mechanism operates to update the key cache structure to reflect the insertion of the new data item into the queue.

6. The system of claim 5 wherein the key cache structure is updated by causing the key value of the new data item to be written into the first field of key cache data entry accessed and a pointer value pointing to the insertion point in the queue into which the new data item was enqueued.

7. The system of claim 1 wherein the queue has first and last entries which are not removable causing new data items to be inserted in the middle of the queue enabling new data items to be more quickly inserted and deleted.

8. The system of claim 1 wherein the queue system is initialized to a predetermined state before utilization by an application, the initialization causing the first and second fields of each key data structure in the key cache structure to be forced to contain a unique key value and a zero value respectively.

9. The system of claim 8 wherein the unique key values of each key cache data structure is selected in a predetermined manner for distributing key values uniformly relative to the number of locations contained in the key cache structure.

10. The system of claim 9 wherein the key value represents a particular time or priority allocation.

11. The system of claim 10 wherein the key value represents a time value and the control mechanism generates the cache index value by performing a mathematical function on the time value to produce a result having values within a range of 0 through n inclusive when the key cache structure has n+1 number of locations.

12. The system of claim 11 wherein the mathematical function involves computing a remainder value for the cache index value by dividing the time value by the value n+1.

13. The system of claim 1 wherein the queue always contains a first and last item which have respectively, a key value smaller than any key to be used in conjunction with the queue system and a key value larger than any key to be used in conjunction with the queue system.

14. The system of claim 1 wherein the control mechanism includes first and item pointers, the control mechanism operates to remove an enqueued data item from the queue by setting the first and item pointers to values for identifying the first actual item in the queue and the item to be removed from the queue, the control mechanism subsequently computes the key cache index value from the key of the data item to be removed and then causes the pointer field of the item to be removed to point to indexed key cache data entry.

15. A method for operating a queue system including a queue using a queue search mechanism, the queue containing a number of locations for storing a corresponding number of queued data items, each queued data item having a number of fields, a pair of the number of fields containing information for indicating locations of preceding and succeeding queued data items and at least one field for storing a key value, the queued data items being ordered in the queue according to key value, the queue search mechanism comprising:

(a) storing in a key cache structure having a number of entry locations included in the search mechanism, a corresponding number of cache data item structures, each cache data item structure having a number of fields, a first field for storing a unique key value representative of a queued data item and a second field for storing a queue address pointer value designating the location of a queued data item;

(b) performing queue management operations using a control mechanism included in the search mechanism to insert a new data item in the queue by first generating a cache index value by converting the key value in the new data item to be enqueued into a pointer value within an established range of values for accessing an entry location in the key cache structure, next determining that the accessed cache data entry is valid, then comparing the key value of a valid queued data item initially specified by the pointer value of the accessed entry location with the key value of the new data item to be enqueued and when the key value of the data item to be enqueued is greater than the key value of the valid queued data item, searching the queue entries from that point until a queued data item having a key value which is equal to the key value of the new data item.