 |
|
|
|
|
|
 Title: |
US5671406:
Data structure enhancements for in-place sorting of a singly linked list
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Lubbers, Clark E.; Colorado Springs, CO
Elkington, Susan G.; Black Forest, CO
|
| Assignee: |
Digital Equipment Corporation, Maynard, MA
other patents from DIGITAL EQUIPMENT CORPORATION (147695) (approx. 2,345)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1997-09-23
/ 1995-10-18
|
| Application Number: |
US1995000544949
|
| IPC Code: |
Advanced:
G06F 7/24;
G06F 17/30;
Core:
G06F 7/22;
more...
IPC-7:
G06F 7/00;
G06F 7/08;
|
| ECLA Code: |
G06F7/24; G06F17/30G;
|
| U.S. Class: |
Current:
707/007;
707/100;
707/101;
707/102;
707/104.1;
707/E17.011;
711/170;
Original:
395/607;
395/611;
395/612;
395/613;
395/614;
395/615;
395/497.01;
|
| Field of Search: |
395/607,611,612,613,614,615,497.01
|
| Priority Number: |
| 1995-10-18 |
US1995000544949 |
|
| 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.
|
| Attorney, Agent or Firm: |
Hudgens, Ronald C. ;
Peterson, Cathy L. ;
|
| Primary / Asst. Examiners: |
Black, Thomas G.; Homere, Jean R.
|
| INPADOC Legal Status: |
Show legal status actions
|
| Family: |
None
|
First Claim:
Show all 5 claims |
What is claimed:
1. 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.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 16 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| U.S. References: |
Go to Result Set:
All U.S. references
| Forward references (16)
|
Backward references (10)
|
Citation Link
Buy
PDF |
Patent |
Pub.Date |
Inventor |
Assignee |
Title |
 |
US5121493 |
1992-06 |
Ferguson |
Amalgamated Software of North America, Inc. |
Data sorting method
|
|
|
US5175857 |
1992-12 |
Inoue |
Kabushiki Kaisha Toshiba |
System for sorting records having sorted strings each having a plurality of linked elements each element storing next record address
|
|
|
US5263160 |
1993-11 |
Porter, Jr. et al. |
Digital Equipment Corporation |
Augmented doubly-linked list search and management method for a system having data stored in a list of data elements in memory
|
|
|
US5274805 |
1993-12 |
Ferguson et al. |
Amalgamated Software of North America, Inc. |
Method of sorting and compressing data
|
|
|
US5278987 |
1994-01 |
Chiang et al. |
|
Virtual pocket sorting
|
|
|
US5303367 |
1994-04 |
Leenstra, Sr. et al. |
Applied Technical Systems, Inc. |
Computer driven systems and methods for managing data which use two generic data elements and a single ordered file
|
|
|
US5551018 |
1996-08 |
Hansen |
Borland International, Inc. |
Method of storing national language support text by presorting followed by insertion sorting
|
|
|
US5557786 |
1996-09 |
Johnson, Jr. |
Advanced Computer Applications, Inc. |
Threaded, height-balanced binary tree data structure
|
|
|
US5560006 |
1996-09 |
Layden et al. |
Automated Technology Associates, Inc. |
Entity-relation database
|
|
|
US5577243 |
1996-11 |
Sherwood et al. |
Lexmark International, Inc. |
Reallocation of returned memory blocks sorted in predetermined sizes and addressed by pointer addresses in a free memory list
|
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G97-479789
DERG97-479789
|
| Other References: |
William, Pugh, "Skip Lists, A Probabilistic Alternative to Balance Trees" Communications of the ACM, V33, N6, Jun. 1990, pp. 668-676.
(9 pages)
Cited by 13 patents
Gupta, Gouind, "Sorting by Hashing and Inserting", 17th Ann. ACM Conf. Communications of the ACM, 21 Feb. 1989-23 Feb. 1989.
Kirschenhoffer, Peter, "Analysis of an Optimized Search Algorithm for Skip Lists", Theoretical Computer Science, V144, N1-2, Jun. 26, 1995, pp. 199-220.
Horowitz et al., "Fundamentals of Data Structures", Computer Science Press, 1983, pp. 106-200.
|
|
 Nominate this for the Gallery...
|
|
