System and Method for Generating a Linked List in a Computer Memory

1. Field of the Invention

The present invention relates generally to computer memories and more specifically to a system and method for generating one or more linked lists in a computer memory architecture.

2. Related Art

Contemporary computer memories are often partitioned by linking data in those memories in chains, or lists, according to data types. Data of a particular data type stored in memory can be linked to other data of the same type regardless of where the data are physically stored in the memory. For example, where data from multiple processes are being stored, it may be desirable to link the data from each particular process together with all the other data of the same data type from the same process. In this manner, several chains of data are formed, and each chain is dedicated to a particular data type.

Such memory linkages can be applied to memories used to store packetized data. In conventional packet memories using linkages, the data are stored in memory cells. Typically, each memory cell contains space for the data packet as well as a pointer to the next cell containing a packet of the same type. Thus, the cell pointer is used to link together cells containing the same type of data.

The present invention is directed toward a system and method for storing data in a linked list memory architecture. According to the invention, several key list parameters are maintained and are made easily accessible to a memory manager. When data to be stored in the memory is received, the memory manager retrieves the list parameters, writes the data to the correct memory location, and at the same time updates the pointer in that location to point to the next location in that list. Thus, each memory location in a list is updated with the pointer to the next location at the same time the data is written to the current location. Therefore, only one write cycle is required to write the data to memory and update the memory linkages.

In operation, when data is received, the memory manager looks up the address of the next available location at which data is to be stored (NEXT AVAILABLE ADDRESS) and an address indicating the next available undesignated space in memory (FREE LIST START ADDRESS). The data is written to the location pointed to by the NEXT AVAILABLE ADDRESS and the FREE LIST START ADDRESS is written as the pointer in that location to the NEXT AVAILABLE ADDRESS. This FREE LIST START ADDRESS then becomes the NEXT AVAILABLE ADDRESS. As a result, only one write cycle is required to store data and maintain the list linkages.

Further features and advantages of the present invention, as well as the structure and operation of various embodiments of the present invention, are described in detail below with reference to the accompanying drawings.

The present invention is described with reference to the accompanying drawings. In the drawings, like reference numbers indicate identical or functionally similar elements. Additionally, the left-most digit of a reference number identifies the drawing in which the reference number first appears.

FIG. 1 illustrates one conventional process for linking data in memory.

FIG. 2 is a high-level block diagram illustrating a representative architecture for storing data in a linked list memory according to one embodiment of the invention.

FIG. 3 is a diagram illustrating an example of how memory may be divided into several lists for storing data.

FIG. 4 is a flow diagram illustrating a process for storing data in a linked list according to the invention.

FIG. 5 is a flow diagram illustrating a process for reading data from the linked list according to the invention.

The present invention is directed toward a system and method for storing data in a linked list memory architecture. The linked list architecture according to the present invention, uses a linkage pointer, or linkage address, associated with each memory location. The linkage pointer points to the location in memory at which the next data item in that list is stored. According to the present invention, when data is written to a memory location, the pointer to the next location is written at the same time. Because the pointer is "pre-loaded" with the next address when data is written to the current location, the system does not have to go back and write an address to that pointer when data is written to the next location. Thus, only one write cycle is required to write data to a memory location.

According to one conventional method, multiple write cycles are required to store data in a list and update the linkages. FIG. 1 illustrates one conventional process for linking data in memory. Referring now to FIG. 1, in a step 104 packet data to be stored in memory are received. In a step 108, the memory manager determines the chain (or list) in which the received packet is to be stored. As stated above, the chain is dictated by the data type of the packet. For example, the packets may be linked according to a source or destination identification, a user identification, or a process identification.

In a step 112, the memory manager determines the address of the available memory space at which the received packet is to be stored. In a step 116, the packet is written to the location at that address.

As noted, each memory location has two fields: a data field to store the packet data; and a pointer field to store a pointer to the next space in memory for that chain. To maintain the linkage of the chain, the address determined in step 112 is written to the pointer field in the immediately preceding memory location in which data for that chain was written. This occurs in a step 120.

Thus, according to this conventional solution, the storing of data in memory requires two write cycles. One cycle to write the received packet into the designated location, and a second cycle to write the address of that designated location to the pointer field of the preceding location.

In contrast to this conventional solution, the present invention accomplishes the tasks of storing data in memory and updating the linkages. FIG. 2 is a high-level block diagram illustrating a representative architecture for storing data in a linked list memory according to one embodiment of the invention. Referring now to FIG. 2, the system includes a memory manager 204, a memory 208, and list parameters table 212. Memory 208 is divided into several virtual queues or lists (302A, 302B, 302C as illustrated in FIG. 3) using a linked list structure. List parameters table 212 stores list parameters used by memory manager 208 when storing data to memory 208 in one of the lists.

FIG. 3 is a diagram illustrating an example of how memory 208 may be divided into several lists for storing data. Referring now to FIG. 3, in this example, memory 208 is divided into three (3) lists 302A, 302B, 302C (generally referred to as list(s) 302) for storing data and a free list 306. Memory 208 could be divided into any number of lists 302, but three are illustrated here for simplicity of explanation. Lists 302 of the actual linked lists that contain data. This is in contrast to free list 306. Free list 306 is a linked list of locations 336 that are available for storing data therein. When data is received to be stored in a list 302, an available location 336 is taken from free list 306, attached to the appropriate list 302, and the data is stored therein.

According to the invention, when data 342 are received they are stored into one of the lists 302. Any of a number of parameters could be used to determine in which list 302 to store received data 342. For example, data 342 may be packet data that is classified according to a user's priority. In this example, it may be desirable to link together packets of data 342 in a specific list 302 based on each packet's priority. In this example, all data 342 having the highest priority could be stored in list 302A, while all data 342 having the next-highest priority could be stored in list 302B, and all data having the lowest priority could be stored in list 302C.

Each list 302 can include one or more storage locations 331. Each location 331 contains data 342 and a pointer 344. Pointer 344 points to the next location in that list. For example, in list 302A, location 331A contains data 342A and a pointer, 344A. Pointer 344A points to location 331B which is the next location in list 301. In one embodiment, pointer 344A actually contains the address 321B to location 331B.

Each list 302 also has associated list parameters. These parameters can include a LAST ADDRESS N, and a NEXT AVAILABLE ADDRESS N. As depicted in FIG. 3, LAST ADDRESS N is the address in memory 208 of the last location of a list N at which data 342 is stored. NEXT AVAILABLE ADDRESS N is the address in memory 208 of a location that is logically linked to list N, at the present time does not contain data 342, and is the location at which the next data 342 belonging to list N will be stored when it is input to memory 208.

For example, for list 302A, LAST ADDRESS 1 321C is the address at which location 331C begins. In this example, location 331C is the last location in list 301 at which data 342 is currently being stored. NEXT AVAILABLE ADDRESS 1 341A is the address at which location 336A begins. When data 342 is received that is destined for list 302A, that received data 342 will be stored in location 336A, and location 336A will be linked to list 302A. Therefore, the address pointing to this location 336A is NEXT AVAILABLE ADDRESS 1 341A.

Two additional parameters, FREE LIST START ADDRESS 348 and FREE LIST END ADDRESS 346 are used by memory manager 208 when storing data 342 in lists 302. FREE LIST START ADDRESS 348 points to location 336D in free list 306. Location 336D is the first location available for storing data 342 that has not already been designated as a next location 336A, 336B, 336C for a particular list. FREE LIST END ADDRESS 346 points to location 336N which is the last location in free list 306 that is available for storing data.

Note that pointers 344 in free list 306 must be pre-loaded to point to the next available location in free list 306. This is necessary when memory manager 208 updates list parameters table 212 to update the FREE LIST START ADDRESS 348.

A parameter BEGIN POINTER N indicates the address of the first location in a list N. For example, for list 302A, BEGIN POINTER 1 indicates address 321A of location 331A, the first location in list 302A. Once data is read out of location 331A, pointer 344A to the next location 331B in list 302A becomes the new BEGIN POINTER 1 parameter for list 302A.

An overview of how data 342 are stored in memory 208 in one embodiment of the invention is now described. FIG. 4 is an operational flow diagram illustrating the manner in which data 342 is stored in memory 208. Referring now to FIGS. 2, 3, and 4, in a step 404 a packet of data 342 that is to be stored in memory 208 is received. In a step 408, the list 302 in which the packet of data 342 is to be stored is determined. As discussed above, this can be determined based on user identification, user priority, or other information contained in the packet header.

In a step 412, memory manager 208 examines list parameters 212 to determine where to store the received data 342. Specifically, memory manager 208 reads the NEXT AVAILABLE ADDRESS N 341. The NEXT AVAILABLE ADDRESS N 341 read is for the list N as determined in step 408 above.

In a step 416, memory manager 208 writes the received data 342 to the location pointed to by NEXT AVAILABLE ADDRESS N 341, and writes the FREE LIST START ADDRESS 348 to the pointer 344 in that location. As a result, the specific list 302 is updated to include the data 342 just received and a pointer 344 containing the FREE LIST START ADDRESS 348. This FREE LIST START ADDRESS 348 becomes the new NEXT AVAILABLE ADDRESS N 341 for that list.

In a step 420, memory manager 208 updates the parameters to reflect the fact that FREE LIST START ADDRESS 348 has now become the NEXT AVAILABLE ADDRESS N for the updated list and to also reflect that the address of the next open location in free list 306 becomes the new FREE LIST START ADDRESS 348. In an embodiment where free list 306 is linked using pointers 344, the pointer 344 in the location pointed to by FREE LIST START ADDRESS 348 (now NEXT AVAILABLE ADDRESS N) is used as the address for the new FREE LIST START ADDRESS 348.

As is evident from the above description, the data 342 can be written to a list 302 and the linkage is updated without having to use two write cycles. This is accomplished because at the same time data 342 is written to the new location, a pointer 344 to a next location is written as well. The new pointer 344 (FREE LIST START ADDRESS 348) is retrieved from list parameters table 212 at the same time that the NEXT AVAILABLE ADDRESS N is retrieved. Because there are only a few list parameters, they can be stored in a very small amount of storage space. Therefore, this storage space can be a rapid access memory without being cost prohibitive. Thus, the time required to retrieve and update the list parameters is very fast relative to the time it takes to write data 342 and pointers 344 to memory 208. Thus, the parameters can be retrieved quickly and the data 342 and new pointer 344 can be written to memory 208 in one write cycle. This provides a savings of one write cycle over the conventional method.

A more specific example of the above description is now provided. In this example, a packet of data 342 is received that is to be stored in list 302A (e.g., list N, where N=A). When the packet data 342 is received, memory manager 208 retrieves FREE LIST START ADDRESS 348 and NEXT AVAILABLE ADDRESS A 341A from list parameters table 212. Memory manager 208 stores data 342 in location 336A (pointed to by NEXT AVAILABLE ADDRESS A 341A) and stores FREE LIST START ADDRESS 348 as the pointer 344 in location 336A.

Memory manager 208 then updates the parameters in list parameters table 212 to reflect the fact that the original FREE LIST START ADDRESS 348 is updated to point to the next available location 336E in free list 306, and to reflect the fact that the previous FREE LIST START ADDRESS 348 is now the NEXT AVAILABLE ADDRESS A 341A for list 302A.

In one embodiment, the free list 306 is maintained just as any of the other linked lists are and free cells do not need to be contiguous. Upon initialization, all cells in memory are linked together with pointers in a contiguous manner. When data is stored and read, cells are allocated and de-allocated for the lists 302 and free list 306 becomes non-contiguous. In this embodiment, a new FREE LIST START ADDRESS 348 can be obtained by using pointer 344 in the location pointed to by the original FREE LIST START ADDRESS 348. Thus, when locations are used and reused, and free list 306 is no longer a contiguous chain of available memory, the pointers 344 in locations in free list 306 can be maintained to indicate the next cell in free list 306.

According to the invention, when data 342 is received, it is stored into one of the lists 302. As stated above, any of a number of factors could be used to determine in which list, 302 to store received data 342. For example, data 342 may be the packet data that is classified according to a user's priority, and it may be desirable to link together packets of data 342 in a specific list 302 based on this priority. For example, all data 342 having a user priority of one could be stored in list 302A, while all data 342 having a priority two could be stored in list 302B, and all data having a priority three could be stored in list 302C.

Because the order in which data 342 is received can be random, the lists are not made up of contiguous locations 331 in memory 208. That is, each list is not a physical queue made up of a series of locations one next to the other. Instead, each list is made up of locations 331 linked to one another by the pointer 344. Each location 331 has a pointer 344 pointing to the next location, which is not necessarily the next physical address space in memory 208. Thus, each list 301 is a logical list. To read data out of a list, memory manager 208 determines the address of the first data location to be read and reads the data from this first location. Memory manager 208, then reads the data in the location pointed to by the pointer in the first location. By repeating this cycle in an iterative manner, all the data from a particular list can be read out of the memory in order. As data locations are read out of memory, if the data does not need to be retained in those locations, the locations can be returned to free list 306 so that they can be used and reused when additional data 342 is received. When new locations are added to free list 306, FREE LIST END ADDRESS 346 is updated to reflect such addition.

FIG. 5 is a flowchart illustrating a manner in which data may be read from a particular list 302. Referring now to FIGS. 2, 3, and 5, the read processes is now described. In a step 504, memory manager 208 reads BEGIN POINTER N from list parameters table 212. In one embodiment, memory manager 208 is a DSP (digital signal processor) and list parameters table 212 is a high speed memory device that can be quickly accessed by the DSP memory manager 208.

In a step 508, BEGIN POINTER N is provided to a read-out machine. After reading the description provided herein, the structure and operation of the read-out machine would be apparent to a person skilled in the relevant art. In a step 512 a command is sent to start the read-out machine, commanding it to read the cell. The readout machine continues to read the cell until the read-out buffer is full. This is illustrated by step 516. In step 516 the readout machine is reading data from the location pointed to by BEGIN POINTER N provided to it in step 508. Once data is read from the location at that address and sent to the proper destination, this location is no longer needed and must be returned to the free list 306.

In one embodiment, to return the now available location to free list 306, it is linked to the end of free list 306. Thus, in a step 518, memory manager 208 reads FREE LIST END ADDRESS 346 from list parameters 212. The pointer 344 in the last location in free list 306 (i.e., the location pointed to by FREE LIST END ADDRESS 346) is updated to point to the now-available address. This will link the now-available address to the end of free list 306. Therefore, in a step 524, the old BEGIN POINTER N that now points to the now-available address is written to pointer 344 in the location pointed to by FREE LIST END ADDRESS 346.

When the data 342 is read out of the memory location, the pointer 344 which was in that location is read in a step 528. This pointer points to the new beginning location 331 for that particular list 302. For example, if data 342A is read out of location 331A, pointer 344A which pointed to address 321B of location 331B is read. This pointer 344 (344A in the above example) is stored as the new BEGIN POINTER N for that list (list 302A in the above example).

Although the above description was provided in terms of data 342, being packet data or data cells, it would be apparent to a person skilled in the relevant art how this system and method could be implemented using data 342 other than packet data.

While various embodiments of the present invention have been described above, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of the present invention should not be limited by any of the above-described exemplary embodiments, but should be defined only in accordance with the following claims and their equivalents.