Hardware implementation of an N-way dynamic linked list

Claim 2

A hardware queue circuit for managing a plurality of linked lists comprising: a head of queue (HOQ) memory to store information representative of a head entry associated with each of the linked lists; a tail of queue (TOQ) memory to store information representative of a tail entry of each of the linked lists; a data memory to store data associated with entries of the linked lists; a next pointer memory; an address bus configured to selectively deliver information the HOQ memory and from the TOQ memory to the data memory in order to access a memory location in the data memory and to the next pointer memory in order to access a memory location in the next pointer memory; a free pointer memory; a first data bus configured to deliver data from an accessed memory location in the next point memory to the free pointer memory and to the HOQ memory; and a second data bus configured to deliver data from an accessed memory location in the free pointer memory to an accessed memory location in the next pointer memory.

Claim 3

The circuit of claim 1 wherein the HOQ memory comprises N first registers and the TOQ memory comprises N second registers.

Claim 4

The circuit of claim 1 further comprising a link length memory to store information representative of a length of each of the linked lists.

Claim 5

The circuit of claim 1 further comprising a controller component configured to effect a write operation of first data to a first linked list by operating the circuit to perform method steps of: obtaining a first value stored in a location in the TOQ memory that is associated with the first linked list; storing the first data in a location in the data memory that is determined from the first value; obtaining a second value stored in the free pointer memory; storing the second value in a memory location of the next pointer memory that is determined from the first value; and storing the second value in the location in the TOQ memory that is associated with the first linked list.

Claim 6

The circuit of claim 4 wherein the TOQ memory comprises a plurality of registers, wherein the first linked list is associated with one of the registers.

Claim 7

The circuit of claim 5 wherein the free pointer memory is organized as a queue and the step of obtaining the second value includes performing a pop operation on the free pointer memory.

Claim 8

The circuit of claim 1 further comprising a controller component configured to effect a read operation on a first linked list by operating the circuit to perform method steps of: obtaining a first value stored in a location in the HOQ memory that is associated with the first linked list; reading data stored in a location in the data memory that is determined from the first value; obtaining a second value stored in a memory location of the next pointer memory that is determined from the first value; storing the first value in the free pointer memory; and storing the second value in the location in the HOQ memory that is associated with the first linked list.

Claim 9

The circuit of claim 7 wherein the HOQ memory comprises a plurality of registers, wherein the first linked list is associated with one of the registers.

Claim 12

The method of claim 9 wherein the first, second, third, and fourth memories, each is a memory component separate from the others.

Claim 13

The method of claim 9 wherein the first memory is a register file comprising a plurality of first registers and a plurality of second registers, each first register associated with a linked list, each first register storing a first location in the second memory, the first location for storing data associated with an entry that represents the beginning of a linked list, each second register associated with a linked list, each second register storing a second location in the second memory, the second location for storing data associated with an entry that represents the end of a linked list.

Claim 14

The method of claim 11 wherein the register file further comprises a plurality of third registers, each third register associated with a linked list, each third register storing a value indicative of the number of entries contained in its associated linked list.

Claim 15

The method of claim 9 wherein, when data is written to the first location, the third memory contains information representative of one or more addresses which represent available locations in the second memory for storing data, the fourth memory stores information which indicates an order in which data associated with a linked list is stored in the second memory, the second address information is a location in the second memory for storing data associated with a subsequent write operation to the first linked list, and the step of storing is a step of storing the second address information in the fourth memory.

Claim 16

The method of claim 13 further comprising determining if there is sufficient memory in the second memory when data is written to the first location.

Claim 17

The method of claim 13 further comprising incrementing a counter associated with the first linked list when data is written to the first location.

Claim 18

The method of claim 9 wherein, when data is read from the first location in the second memory, the third memory stores information which indicates an order in which data associated with a linked list is stored in the second memory, the fourth memory contains information representative of one or more addresses which represent available locations in the second memory for storing data, the second address information is a location in the second memory from which data will be read in response to a subsequent read operation on the first linked list, and step of storing is a step of storing the first address information in the fourth memory thereby making the first location available for storing data.

Claim 19

The method of claim 16 further comprising decrementing a counter associated with the first linked list when data is read from the first location.

Claim 20

Apparatus for accessing one or more linked lists comprising: a first memory for storing a plurality of queue data representative of a plurality of linked lists; a second memory; a third memory for storing link address information representative of an ordering of data in the second memory that are associated with a linked list; a fourth memory for storing free address information representative of unallocated memory locations in the second memory; means for accessing the first memory to obtain first queue data representative of a first linked list, the first queue data representing at least one entry in the first linked list means for accessing a first location in the second memory based on first address information contained in the first queue data, wherein data associated with the at least one entry can be written to the first location or read from the first location; means, responsive to a write operation, for: accessing the fourth memory to obtain second address information representative of a second location in the second memory; storing the second address information in the third memory; and storing the second address information in the first queue data, wherein data associated with a subsequent write operation will be stored the second location; means, responsive to a read operation, for: accessing the third memory to obtain third address information representative of a second location in the second memory; storing the first address information in the fourth memory; and storing the third address information in the first queue data, wherein a subsequent read operation will be made from the third location.

Claim 21

Apparatus for accessing one or more linked lists comprising: a first memory for storing a plurality of queue data representative of a plurality of linked lists; a second memory; a third memory for storing link address information representative of an ordering of data in the second memory that are associated with a linked list; a fourth memory for storing free address information representative of unallocated memory locations in the second memory; means for accessing the first memory to obtain first queue data representative of a first linked list, the first queue data representing at least one entry in the first linked list means for accessing a first location in the second memory based on first address information contained in the first queue data, wherein data associated with the at least one entry can be written to the first location or read from the first location; means, responsive to a write operation, for: accessing the fourth memory to obtain second address information representative of a second location in the second memory; storing the second address information in the third memory; and storing the second address information in the first queue data, wherein data associated with a subsequent write operation will be stored the second location; means, responsive to a read operation, for: accessing the third memory to obtain third address information representative of a second location in the second memory; storing the first address information in the fourth memory; and storing the third address information in the first queue data, wherein a subsequent read operation will be made from the third location.

Claim 22

The apparatus of claim 18 wherein the first, second, third, and fourth memories, each is a memory component separate from the others.

Claim 23

The apparatus of claim 18 wherein the first memory is a register file comprising a plurality of first registers and a plurality of second registers, each first register associated with a linked list, each first register storing a first location in the second memory, the first location for storing data associated with an entry that represents the beginning of a linked list, each second register associated with a linked list, each second register storing a second location in the second memory, the second location for storing data associated with an entry that represents the end of a linked list.