US 5,671,406 AGranted

Data structure enhancements for in-place sorting of a singly linked list

AssigneeDigital Equipment Corporation

InventorsClark E. Lubbers, Susan G. Elkington

Life of this patent

Estimating the term…

Loading patent…

Abstract

An apparatus and method for performing a skip list insertion sort on a singly linked list of elements is provided. Each element to be sorted includes a key, an element pointer in an element pointer field and a flag bit. Also provided is an indexed array of pointer arrays. If an element is to be inserted at a node level greater than zero, a free pointer array is allocated by storing an index corresponding to the allocated pointer array in the element pointer field and setting the corresponding flag bit. If a free pointer array is not available, then the node level of the element is forced to zero. If the level of the element is either assigned as or forced to zero, the flag bit is not set and the pointer array itself occupies the element pointer field as the element pointer instead of the index. Thus, the pointer to the element pointer field will point directly to the specified pointer array location without having to index into the array of pointer arrays. The skip list insertion search part of the sorting routine for each subsequent item to be inserted then tests the flag bit when traversing the list to determine whether the pointer array is in the array of pointer arrays or the element pointer field itself.

Claims5

Dependent claims

A digital computer system comprising:

a memory;
a data structure stored in the memory, the data structure including an unsorted singly linked list of elements, each of the elements having a key being assigned prior to an insertion sort operation;
an array of pointer arrays, each pointer array of the array of pointer arrays having an associated index;
a flag corresponding to each element, the flag being initialized to zero, the flag for indicating whether the corresponding element has a level greater than zero;
a list head having a maximum allowable number of levels and a pointer at each of the levels, the pointer for pointing to a one of the elements inserted at a level equal to the pointer level during the insertion sort operation, the pointer being initialized to point to a NULLPTR prior to the insertion sort operation;
an array of element pointer fields, each element pointer field in the array storing an element pointer corresponding to a separate element, each element pointer field storing as the element pointer one of said indices when the flag indicates a level greater than zero and a pointer array when the flag indicates a level not greater than zero;
and
a system agent for performing the skip list insertion sorting operation on the unsorted singly linked list, the system agent checking the flag during linking to determine whether the pointer array for a given element is located in the array of pointer arrays if set or in the element pointer field if not set.

5 more elements

A method of inserting an element in a linked list of elements, each element having an element pointer field for storing an element pointer and having an assigned key, the linked list being pointed to by a list head including a maximum allowed number of pointers, the pointers indexed from a lowest to a maximum number, the index corresponding to a level, the linked list having a current level no greater than the maximum allowed number of pointers, comprising the steps of:

assigning a randomly generated level as a new level to the element;
comparing the new level to the current level to determine if the new level is greater than the current level;
if the new level is greater than the current level, the current level is increased such that the new level is the same as the current level;
determining if the assigned new level is greater than zero;
if the new level is greater than zero, the performing the steps including:
determining if a pointer array in an array of pointer arrays is available;
if a pointer array is not available, forcing the new level to zero;
if a pointer array is available, allocating the available pointer array for use by the element;
setting a flag bit in the element in response to the allocating of a pointer array to indicate that a pointer array is allocated to the element;
storing an associated index of the allocated pointer array in the element pointer field of the element, thereby enabling the element pointer in the element pointer field to index into the array of pointer arrays to obtain an address of the pointer array;
and
performing an insertion search.

9 more elements

Dependencies are inferred from the claim text.