Bidirectional data structure processing
AssigneeUnisys Corporation
InventorsCharles D. Steigerwald, Donald G. Smith
Life of this patent
Estimating the term…
Abstract
To enhance data structure processing performance, data is organized bi-directionally in a data structure. That is, depending on the value of a data key associated with an entry, the entry is stored either from a low end or from a high end of the data structure. For example, the low end of the data structure may store entries having even-valued keys, while the high end of the data structure may store entries having odd-valued keys. Subsequent data structure processing can be facilitated by searching the data structure in either a forward direction starting with the low end or a reverse direction starting with the high end, depending on whether a search key is even or odd.
Claims21
A method to access an entry in a data structure comprising:
- storing a plurality of entries in the data structure, wherein the data structure is an array and each entry includes a data key, and a plurality of the data keys are stored in sequentially indexed entries in the array and are not ordered by values of the data keys in the sequentially indexed entries;
- based on the value of a search key, selecting one of multiple possible index values to use as a preliminary index, the preliminary index being associated with a preliminary entry that is associated with a data key to which the search key will be first compared;
- selecting an increment value from two or more increment values as a function of the search key;
- comparing the search key with the data key associated with the preliminary entry associated with the preliminary index;
- and
- adjusting the preliminary index by the increment value when the search key and the data key associated with the preliminary entry do not match.
A computer system comprising:
- means for storing a data structure comprising a plurality of entries, wherein the data structure is an array and each entry includes a respective data key and is associated with a respective index, and a plurality of the data keys are stored in sequentially indexed entries in the array and are not ordered by values of the data keys in the sequentially indexed entries;
- means for selecting a start index from among multiple possible start index values, an end index, and an increment value from two or more increment values all as a function of a search key, an entry associated with the start index being the first entry of the data structure to process for comparison with the search key;
- means for comparing the search key with the data key associated with the entry associated with the start index;
- and
- means for adjusting the start index by the increment value when the search key and the data key associated with the entry associated with the start index do not match.
A computer arrangement comprising:
- a memory configured to store a data structure comprising a plurality of entries, wherein the data structure is an array and each entry includes a respective data key and is associated with a respective index, and a plurality of the data keys are stored in sequentially indexed entries in the array and are not ordered by values of the data keys in the sequentially indexed entries;
- a system bus operatively coupled to the memory to access the data structure;
- and
- a processor operatively coupled to the system bus to access the data structure, the processor configured to
- select a start index from multiple possible start index values, an end index, and an increment value from two or more increment values, all being selected as a function of a search key, an entry associated with the start index being the first entry of the data structure to access,
- compare the search key with a data key associated with the entry associated with the start index, and
- adjust the start index by the increment value when the search key and the data key associated with the entry associated with the start index do not match.
Dependencies are inferred from the claim text.