Deletions on circular singly linked lists

Details Deletions on circular singly linked lists Deletions on circular singly linked lists

2001-04-10

2003-12-30

Metjahic, Safet (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

06671690

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to methods, apparatus, and systems for manipulating data structures in a computing system. More particularly, the present invention relates to deleting data on a circular, singly linked list.
2. Description of the Related Art
Linked lists are well known in the art, and various methods have been employed to manipulate linked lists. Linked lists are one of the most common data structures employed for the manipulation of data. Linked lists are particularly important with an operating system. Operating systems control a variety of resources simultaneously. A linked list might be used, for example, to hold requests for each individual resource. Circular linked lists can also be used in a server-client environment where the server uses the circular linked list to record those clients that are waiting for service at a particular time. By using the circular linked list, a server can insure that its attention is evenly distributed amongst the waiting clients by visiting and servicing each waiting client as it circulates around the list. Using a consumer/producer model to visualize the linked list, the server can be considered the consumer and the clients each representing a producer as illustrated in
FIG. 1
that shows a linked list
100
representing individual work queues (WQ). As shown in
FIG. 1
, a producer adds work queues with new work to the list
100
as a consumer continually scans the list, processing packets from each work queue in turn and deletes a work queue when it's packets are spent. Using this arrangement, the list
100
contains all work queues that are pending where they remain so long as they still have work (or packets to transmit) until it is ultimately deleted when the work (or packet) has been depleted.
Generally, linked lists can take two forms: (1) circular singly linked lists; or (2) circular doubly linked lists. With a singly linked list, each member contains a field pointing to the next member while doubly linked lists add a second pointer to each member that points to the previous member. Although doubly linked lists facilitate scanning in the reverse direction, they are more difficult to maintain since the additional pointers require additional write operations to static random access memory (SRAM), substantially increasing cycle time over singly linked lists.
Therefore, focusing on the singly linked lists such as that shown in
FIG. 1
, the producer uses a register referred to as a root pointer that points to a member in the list. The producer adds a new member into the list
100
by copying the contents of the root pointer into the new member and overwrites the root pointer with an index to the new member where members are typically stored in SRAM. Since accesses to the same SRAM can not generally be parallelized, it is important for performance reasons to keep the number of reads and writes to memory at a minimum. Although registers can be accessed in parallel but do not have the density of SRAM.
The consumer scans the list by following the next pointer that is embedded in each member. The next pointer points to the next member on the list. The consumer scans the list by copying the next pointer into a register called the current pointer. The current pointer register is used to read the next member. When the next member is read, its next pointer field is copied into the current pointer register. By repeating the process every member on a circular linked list can be scanned. A scan is done with a single read access to SRAM.
Unfortunately, the drawback with singly linked lists is deletions. When a consumer has to delete a member, the consumer must overwrite the member preceding the one to be deleted. Since next pointers only point forward, locating the preceding member is difficult and time consuming without backward pointers.
Therefore what is desired is an efficient method, apparatus, and system for deleting a member in a circular singly linked list.
SUMMARY OF THE INVENTION
Methods and apparatus for augmenting a scan operation of a circular singly linked list by providing a method, apparatus, and system for deleting a member of a circular singly linked list using a single SRAM write access is described. During a scan operation of a list member having a next pointer field, the contents of the next pointer field are saved in the current pointer register. As the current pointer register is updated, the current register content is copied to a previous pointer register. In order to delete the list member during the scan, the content of the current pointer register is copied to the next pointer field of the list member referenced by the previous pointer register. The current member is deleted and the next pointer field of the previous member references the next member of the linked list. In this way, deletions done at the time of scanning involve only a single SRAM write access.
In another embodiment, an apparatus for deleting a current member of a circular, singly linked list is described requiring only a single memory write operation.
In yet another embodiment, a computer program product for deleting a current member of a circular, singly linked list is described.
These and other advantages of the present invention will become apparent upon reading the following detailed descriptions and studying the various figures of the drawings.


REFERENCES:
patent: 5659739 (1997-08-01), Lubbers et al.
patent: 5713014 (1998-01-01), Durflinger et al.
patent: 5933655 (1999-08-01), Vrabec et al.
patent: 6208764 (2001-03-01), Archer et al.
patent: 6272499 (2001-08-01), Wooten
patent: 6445680 (2002-09-01), Moyal

Affiliated with

Also associated with

Rating

Deletions on circular singly linked lists does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Deletions on circular singly linked lists, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deletions on circular singly linked lists will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3164012