Data structure enhancements for in-place sorting of a singly linked list
October 18, 2015. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.Patent ReferencesData sorting method System for sorting records having sorted strings each having a plurality of linked elements each element storing next record address Augmented doubly-linked list search and management method for a system having data stored in a list of data elements in memory Method of sorting and compressing data Virtual pocket sorting Computer driven systems and methods for managing data which use two generic data elements and a single ordered file Method of storing national language support text by presorting followed by insertion sorting Threaded, height-balanced binary tree data structure Entity-relation database Reallocation of returned memory blocks sorted in predetermined sizes and addressed by pointer addresses in a free memory list Patent #: 5577243 InventorsAssigneeApplicationNo. 544949 filed on 10/18/1995US Classes:707/7, Sorting707/100, DATABASE SCHEMA OR DATA STRUCTURE707/101, Manipulating data structure (e.g., compression, compaction, compilation)707/102, Generating database or data structure (e.g., via user interface)707/104.1, Application of database or data structure (e.g., distributed, multimedia, image)711/170Memory configuringExaminersPrimary: Black, Thomas G.Assistant: Homere, Jean R. Attorney, Agent or FirmInternational ClassesG06F 007/08G06F 007/00 AbstractAn 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.Other References
| |
