Methods and apparatus for linked-list circular buffer management

摘要

A buffer memory is provided that comprises a plurality of memory elements for storing data elements in an order of arrival, wherein the plurality of memory elements have a variable size and wherein each memory element comprises a pointer (such as a next block starting index) to a memory element storing a next data element. Additionally, each memory element optionally further comprises a block size field indicating the variable size and/or a sequence number field indicating a sequence number of the corresponding data element. The buffer memory optionally comprises a largest sequence variable to store a sequence number of a data element in the buffer memory having a largest sequence number. The largest sequence variable is updated if a newly arrived data element has a sequence number that is larger than the largest sequence variable. A method is also provided for managing the disclosed buffer memories.

主权项

1. A buffer memory, comprising:
a plurality of continuous memory elements for storing data elements in an order of arrival along with sequence information for the data elements stored therein, wherein said plurality of continuous memory elements have a variable size, wherein each memory element comprises a pointer to another memory element in said plurality of continuous memory elements storing a next data element, wherein said variable size is determined when a corresponding data element is stored and is based on a size of said corresponding data element, wherein a memory hole in said buffer memory is dissolved by a read pointer moving forward to skip a reading of the memory element associated with the memory hole, and wherein said buffer memory is defragmented by copying one or more memory fragments toward a direction of the read pointer or a write pointer; and a largest sequence variable to store a sequence number of a data element in said buffer memory having a largest sequence number, wherein said largest sequence variable is updated if a newly arrived data element has a sequence number that is larger than said largest sequence variable.