Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-05-28
2001-09-25
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C711S147000
Reexamination Certificate
active
06295534
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to data storage devices and more particularly relates to an apparatus for storing and modifying an ordered list suitable for use in data communications and other equipment.
BACKGROUND OF THE INVENTION
In many applications such as the field of networking, it is highly desirable to maintain a list of items that are ordered in some type of fashion, i.e., alphabetical, numerical, chronological, etc. The list comprises a form of a database wherein small or large amounts of data can be maintained in the ordered list. The fact that the list is maintained as an ordered list enables easy and relatively fast access to large databases of items. For example, many networking device applications need to keep track and store MAC addresses for various reasons such as network bridge applications.
One conventional solution to the problem stores the ordered list in regular memory. A diagram illustrating a prior art example of a block of memory utilized to store and maintain an ordered list of data is shown in FIG.
1
. The block of memory
10
comprises a plurality of memory locations
12
numbered 1 through N. Each memory location holds one item of data Data items can be inserted and deleted from the list using push and pop operations. Assuming data is to be inserted at the index point, a push operation functions to move all locations below the index down one space and inserts the new data into the location at the index point. Removing an item from the index location involves reading the location at the index point and then moving all locations below the index up one space.
Note that this prior art scheme can be performed using either software or hardware means. In the case of software, the push and pop operations are time consuming and could take relatively long periods of time to complete as the size of the list increases. Handling large lists in hardware require large number of components to construct the necessary circuitry to perform the push and pop operations.
A second prior art solution to the problem uses a singly or doubly linked list to maintain the ordered list. In a pointer linked list implementation, each data item is combined with one or more pointer fields in which each pointer field functions to store one pointer. In the case of a doubly linked list, two pointers are stored to keep track of both the next data item in the list and the previous data item in the, list. The next and previous pointers are chosen such that they maintain the order in the list.
A diagram illustrating another prior art example of a portion of a doubly linked list utilized to store and maintain an ordered list of data is shown in FIG.
2
. The linked list, generally referenced
20
, comprises a plurality of structures
22
wherein each structure represents one index. For illustrative purposes, only index #X, #Y and #Z are shown. Each structure
22
comprises a list cell
24
which contains the data to be stored in the list, a next pointer
26
and a previous pointer
28
. As shown by the arrows, the next and previous pointers dictate the order of the indexes in the list. For example, the next pointer of index #X points to index #Y and the previous pointer of index Z points to index #Y.
If an item is to be added to the list, the appropriate place of insertion is determined by some process that functions to maintain the ordering scheme. To add an item, the linked list is broken at an appropriate place and the new item placed therein. The linked list is then closed. A diagram illustrating the prior art example shown in
FIG. 2
after the insertion of a new index entry is shown in FIG.
3
.
The new linked list, generally referenced
30
, now comprises a new item—index #M. The ordering mechanism has determined that item #M is to be inserted between index #Y and index #Z. To insert item #M, the next pointer of index #Y is modified to point to index #M and the previous pointer of index #Z is set to point to index #M. Similarly, the next pointer of index #M is set to point to index #Z and the previous pointer of index #M is set to point to index #Y.
A disadvantage of using linked lists, created using either hardware or software, is that locating and reading out a particular entry can be time consuming. In addition, the insert and remove operations can be time consuming as well, especially as the number of entries grows larger and larger. This is due to the fact that to find an entry, the linked list must be traversed link by link. There is no quick random access technique that permits quick reading of any arbitrary data item.
Other prior art schemes of maintaining an ordered list typically implement a hashing scheme or involve some form of content addressable memory (CAM) technique. These techniques also have the disadvantage of requiring relatively large amounts of software and/or hardware resources.
SUMMARY OF THE INVENTION
The present invention is an apparatus for maintaining an ordered list. The list can store any type and number of data items. The ordered list is preferably implemented in hardware so as to enable fast, efficient maintenance of an ordered list of data. The data to be stored in the list, is stored as a plurality of data cells. Each data cell can comprise any number of bits and can be made any size, limited only by the size constraints imposed by the application.
The ordered list permits data to be read from, written to and deleted from the list. Data is written to the list using a push operation and data is deleted from the listing using a pop operation. A controller, processor or other source, provides the cell address information for each read, push and pop operation.
The ordered list comprises a plurality of index units with each index unit comprising a 3 to 1 multiplexor whose output is connected to a data cell. The data cell comprises a register or suitable data storage device. The mux selects data to its output from either (1) input cell data (2) the data cell in the previous index unit or (3) the data cell in the next index unit.
Individual operations of pushing, popping and reading are defined. In addition, a push operation and a pop operation can be performed simultaneously regardless of whether the push address is greater than, smaller than or equal to the pop address.
There is provided in accordance with the present invention an apparatus for storing a, plurality of data items as an ordered list comprising a plurality of index units connected in a linear fashion to form a list of data items, each index unit adapted to receive new data and data from both the next and previous index units and wherein each index unit, except for the first and last, is coupled to a previous and a next index unit, an input data bus adapted to be connected to each index unit in the list, an output data bus adapted to be connected to each index unit in the list and control circuitry adapted to receive a plurality of address and control signals and in response thereto to perform a plurality of operations on the ordered list.
The index unit comprises a multiplexor adapted to receive data from the input bus and data from both its previous and next index units and a data register having an input and an output, the input coupled to the output of the multiplexor, the output coupled to the input of the multiplexor associated with the next index unit, the data register for storing a single data item. The multiplexor may comprise a 3 to 1 multiplexor.
The plurality of control signals comprises a push signal and a pop signal. The plurality of control signals comprises a read signal and the plurality of address signals comprises an address corresponding to on one of the index units.
In addition, the plurality of operations comprises a push operation whereby a new data item is stored in the index unit corresponding to a specified address, comprises a pop operation whereby a data item is removed from the index unit corresponding to a specified address and a read operation whereby
3Com Corporation
Alam Hosain T.
Fleurantin Jean Bolte
McDonnell & Boehnen Hulbert & Berghoff
Zaretsky Howard
LandOfFree
Apparatus for maintaining an ordered list does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus for maintaining an ordered list, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus for maintaining an ordered list will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2489781