The InnovationQ application will be updated on Sunday, May 31st from 10am-noon ET. You may experience brief service interruptions during that time.
Browse Prior Art Database

Fast insertion/lookup by priority

IP.com Disclosure Number: IPCOM000015261D
Original Publication Date: 2001-Sep-16
Included in the Prior Art Database: 2003-Jun-20

Publishing Venue



Disclosed is a mechanism by which certain advantages of linked lists and fixed reference points are combined. This could be used in a messaging system in which messages are retreived and inserted by priority. Linked lists are admirably suited to quick insertion, but searching the list for the insertion point can be expensive. This disclosure describes the use of 'dummy' entries in the list that do not partake in the nessaging system, but act as markers for the boundaries between entries of different priorities. These dummy entries are created with the linked list (see diagram 1), and remain until the linked list is destroyed. An array of references to these dummies is also created when the linked list is created. The array of refererences can be used to rapidly find the insertion point for any message. The insertion point for a message of priority P is the boundaries between the messages of priority P and the next higher priority P+1. This boundary is marked by the dummy entry at position P in the array of references. Although this mechanism is similar to maintaining a separate linked list for each priority, it does not require special processing at the list boundaries. Separate list would also require almost twice as many cached references each list requires a start and a finish. The mechanism disclosed uses most (all but two) dummy entries as both start and end points. Diagram 1: Initial Linked List Each rectangle represents a dummy entry. The arrows show the forward links between them. The numberred entries indicate the insertion points for a given priority