US 6,581,063 B1 · Method and apparatus for maintaining a linked list

Abstract

A linked list has an associated auxiliary data structure, containing external references to the linked list which are used by updating tasks. The auxiliary data structure is used to block subsets of the linked list from being altered by other tasks. Preferably, the linked list is doubly-linked, and list maintenance is accomplished using object-oriented programming techniques. The auxiliary data structure is an object, which comprises iterator objects, including inspector objects and mutator objects, blocker objects and view objects. Iterator objects are used by clients to access the linked list externally. An inspector object traverses the list without changing it; while a mutator alters the list, and may traverse it as well. Both inspectors and mutators have associated view objects, which contain the pointers to the actual list elements. Mutators also have associated blocker objects, which block access to selected list elements. In operation, a mutator object blocks off a portion of the linked list by altering pointers so that they point to the blocker object, the blocker object containing additional pointers by-passing the blocked list portion. Other inspectors may thereafter traverse the list through the by-passed portion. By blocking only a relatively small portion of a large linked list, multiple tasks may concurrently access different list elements and perform separate list updates.

Claims21

Dependent claims

A method for maintaining a linked list, comprising the steps of:

establishing an auxiliary data structure for said linked list, said auxiliary data structure containing external references to said linked list which are used by updating tasks;
initiating a first updating task for updating said linked list through said auxiliary data structure;
recording blocking data within said auxiliary data structure to block other updating tasks accessing said linked list through said auxiliary data structure from altering a first portion of said linked list, said first portion being fewer than all the elements of said linked list;
and
updating said linked list within said first portion of said linked list, by performing an action from the set of actions consisting of:
(a) removing an element within said first portion of said linked list from said linked list, and (b) inserting an element into said linked list within said first portion of said linked list.

3 more elements

A method for updating a doubly-linked list in a multitasking computer system, comprising the steps of:

identifying a first set of consecutive links in a region of interest of said doubly linked list, said first set of consecutive links being fewer than all the links of said doubly linked list;
blocking tasks other than a first task from altering at least some portion of links of said first set of consecutive links, while not blocking tasks other than said first task from altering links of said doubly-linked list not contained in said first set;
altering said doubly linked list within said first set by performing an operation from the set of operations consisting of:
(a) removing a link of said first set from said doubly linked list, and (b) inserting a link into said doubly linked list between two links of said first set, said operation being performed by said first task;
and
unblocking tasks other than said first task from altering at least some portion of links of said first set after performing said altering step.

3 more elements

Dependencies are inferred from the claim text.

Method and apparatus for maintaining a linked list

Life of this patent

Method and apparatus for maintaining a linked list

Life of this patent

Abstract

Claims21