Management of data structures

Details Management of data structures Management of data structures

1997-06-05

2001-06-26

Nguyen, Chau (Department: 2663)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395430, C370S474000

Reexamination Certificate

active

06252876

ABSTRACT:

TECHNICAL FIELD
This invention relates to data structures, and in particular to the management of dynamic data lists within a real-time environment. One particular application of the invention is in updating connection maps in telecommunications systems.
BACKGROUND OF THE INVENTION
One known way of storing data is in the form of a linked list. A linked list enables the dynamic storage of uniform or non-uniform data items. A number of related data items can be contained within a single list, with each item being linked to the next in the list by a pointer field. This is essentially a software process. The pointer field enables the list to be traversed and the data accessed. In its simplest form new items are always added to the bottom of the list and old items are always removed from the top of the list. A common example of this is a FIFO device. Updating this type of list requires the operations of list concatenation and item removal. One example of an application in which this type of list is used is in the queuing of tasks within an operating system, with tasks being scheduled purely according to their arrival time.
A more complex use of a linked list allows for the ordering of all or part of the data information within the list. Updating this type of list requires the ability to add new items or delete existing items at arbitrary positions within the list. Examples of applications in which this type of list is used include the configuration of routing tables, call records, and translation tables in telecommunications systems and the scheduling of tasks, by priority, in computer operating systems. U.S. Pat. No. 5,274,768 (Traw et al.) describes an interface for Asynchronous Transfer Mode (ATM) networks which uses this kind of linked list manager.
An example of this type of list is shown in
FIG. 1. A
memory
30
has a plurality of memory locations, which are numbered 1 to 20. A reserved part of the memory, such as location
1
, holds a pointer start_ptr to the memory location of the first element in the list. In this example the first element in the list occupies memory location
4
. It could however occupy any one of the memory locations. An enlargement shows the contents of memory location
4
in more detail. A data item DATA and a pointer ptr_next are stored at this memory location. The pointer points to the memory location of the next element in the linked list. This has a value “
16
” which is the memory location where the second element in the list is stored. The memory holds a number of similar elements which are linked to one another in this manner.
The process for updating this type of list will now be described with reference to
FIGS. 1A
to
1
C.
FIG. 1A
shows two elements, one stored at memory location
4
, and a second at memory location
9
. The pointer of the element at location
4
points to the memory location
9
.
Firstly, the situation where a new element needs to be added to the list is considered. The new element is inserted at an available location in the memory. This is location
16
. The element must be tied into the list at the required point.
FIG. 1B
shows the result of adding this new element to the list between the two existing elements. The pointer value of the element held at memory location
4
now points to memory location
16
, and the pointer value of the newly inserted element points to memory location
9
.
Secondly, the situation where an existing element needs to be deleted from the list is considered. The existing element at memory location
16
needs to be removed from the list. The pointer value of the element held at location
4
is changed to point to the memory location of the element following the one to be deleted i.e. the element at location
9
.
A problem associated with linked lists is that in order to find a particular data item the list must be searched in a systematic manner, beginning at the first element in the list and continuing through the list until the item is found. This makes the search process slow. To improve the access process, doubly linked lists are also commonly used. In a doubly linked list, for each data item, pointers are used to indicate both the next element in the list and the previous item in the list. In this manner the list may be traversed in either direction.
The use of linked lists and doubly-linked lists has a number of problems. Firstly the process of configuring and maintaining the lists is complex and thus necessitates its implementation using software. This precludes their use for real-time, high throughput applications. Secondly, the task of updating the linked lists usually requires that the process of accessing the data is interrupted. Thirdly, there is a need to store both the data elements and the pointers which link the elements together.
One known method for updating data lists within real-time hardware systems involves the use of a shadow memory. Firstly, an updated list is configured within the shadow memory and then, secondly, this is swapped with the original memory to complete the update process. Using a shadow memory has a disadvantage of requiring a doubling of the overall memory requirement. It is therefore a particularly expensive option for very high speed real-time applications which demand expensive, high-performance memory devices.
Both of these techniques have undesirable attributes, particularly for use in real-time applications.
The present invention seeks to provide an improved method of updating a data table or list which minimises the disadvantages of the prior art methods.
SUMMARY OF THE INVENTION
According to an aspect of the present invention there is provided a method of updating at least one list of data elements stored in a predetermined sequence of locations of a memory device, the method comprising updating the list by moving a portion of the list through the sequence of memory locations. Storing data elements in a predetermined sequence of locations avoids the need for complex pointer mechanisms to link one element in the list to the next. Several linked lists can be managed simultaneously, sharing a common memory resource. The method is suitable for many of the applications where linked lists and doubly-linked lists have traditionally been used to maintain dynamic data structures under software and/or hardware control.
The moving process avoids the need for a large additional high speed memory, as used in known shadow memory techniques. The method is both simple and requires a minimum of apparatus for its implementation.
The order in which the elements of the list are maintained may have a significance. By updating the list such that a new element is inserted into, or an existing element at a particular position in the list is deleted or changed by moving a portion of the list through the sequence of memory locations has the important advantage of maintaining the elements of the list in their order when updates are performed.
Preferably the step of updating the list to insert a new element into the list at a particular position comprises moving data elements which follow that position forward through the sequence of memory locations to open a space to fit the new element, and inserting the new element into the space.
Preferably the step of updating the list to delete an existing item at a particular position in the list comprises moving data elements which follow that position backwards through the sequence of memory locations to overwrite the existing item.
Preferably the predetermined sequence of memory locations in which the data elements are stored is a sequence of contiguous memory locations. This simplifies the process of stepping between data elements in the list.
Preferably the elements of the list are accessed in the sequence in which they are stored and the list is updated during the accessing of the structure. Performing updates during the normal accessing of the list removes the necessity to interrupt the system during an update period. This technique is ideally suited to cyclic applications where the complete set of data is read sequentia

Affiliated with

Also associated with

Rating

Management of data structures does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Management of data structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Management of data structures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2444945