Lockless access to a ring buffer
A reader and writer access a ring buffer without using a locking mechanism, thereby avoiding any delays attendant to using a locking mechanism when performing read operations to supply the reader with data from the ring buffer. Other measures are used to reduce delayed performance of read operations. If data requested by a reader is not available in the ring buffer, rather than waiting until the data becomes available, substitute data not from the ring buffer is provided instead. The ring buffer's size may be dynamically increased or decreased to improve performance of read and write operations and/or to conserve computer resources.
1. A method for lockless access to a buffer, comprising the steps of:
a computing device generating a set of elements, the set of elements comprising at least a first element, a second element, a third element, and a fourth element;
wherein said first element comprises a next pointer that points to said second element and a nextfilled pointer that does not point to any particular location;
wherein said second element comprises a next pointer that points to said third element;
wherein said third element comprises a next pointer that points to said fourth element and a nextfilled pointer that does not point to any particular location;
after a writer has finished writing to a buffer associated with said second element, the writer performing the steps of,
determining whether the nextfilled pointer of the third element points to any particular location, and
in response to determining that the nextfilled pointer of the third element does not point to any particular location, advancing to the third element and setting the nextfilled pointer of the first element to point to the second element;
after a reader has finished reading from a buffer associated with the first element, the reader performing the steps of,
determining whether the nextfilled pointer of the first element points to any particular location, and
in response to determining that the nextfilled pointer of the first element points to a particular location, advancing to the second element and setting the nextfilled pointer of the first element to not point to any particular location.
2. The method of claim 1 , wherein the step performed by the writer of determining whether the nextfilled pointer of the third element points to any particular location comprises determining whether the nextfilled pointer of the third element is set to NULL.
3. The method of claim 1 , wherein the step performed by the reader of determining whether the nextfilled pointer of the first element points to any particular location comprises determining whether the nextfilled pointer of the first element is set to NULL.
4. The method of claim 1 , wherein the step performed by the reader of setting the nextfilled pointer of the first element to not point to any particular location comprises setting the nextfilled pointer of the first element to NULL.
5. The method of claim 1 , wherein the step performed by the writer of advancing to the third element is performed by the writer in response to the writer determining that the nextfilled pointer of the third element is set to NULL.
6. The method of claim 1 , further comprising the steps of:
generating a ring buffer comprising,
a set of buffers for being filled by said writer and for being read by said reader, and
said set of elements, wherein said set of elements are circularly ordered, each element of said set of elements being associated with a particular buffer from the set of buffers;
wherein each element of said set of elements includes,
a next pointer that points to a next element that follows in the circular order, and
a nextfilled pointer that points to said next element only when the buffer associated with the next element can be read by the reader.
7. The method of claim 6 , the steps further including:
performing a read operation to return a quantity of data requested by the reader when data available in the ring buffer is less than the quantity of data; and
returning, as part of said read operation, said quantity of data, said quantity of data including data not from said ring buffer.
8. The method of claim 7 , wherein:
said ring buffer holds ordered data denoted by ordinal information;
said quantity of data corresponds to an ordinal position; and
said data that is not from said ring buffer is returned as data that corresponds to said ordinal position.
9. The method of claim 8 , wherein:
said ring buffer holds audio/video data;
said ordinal position covers a time period; and
said data that is not from said ring buffer corresponds to a time period.
10. The method of claim 6 , the steps further including:
performing a read operation to return data that corresponds to a particular time specified by said reader; and
as part of said read operation, returning a quantity of data as said data that corresponds to the particular time.
11. The method of claim 10 , wherein:
at least a portion of the data that corresponds to the particular time is not available in said ring buffer; and
wherein the quantity of data includes data not from said ring buffer.
12. The method of claim 6 , the steps further including:
said writer writing certain data to said ring buffer;
adding a plurality of elements to said ring buffer; and
after adding said plurality of elements to said ring buffer, said reader reading said certain data from said ring buffer.
13. The method of claim 12 , wherein the step of adding a plurality of elements is performed during a write operation.
14. The method of claim 6 , the steps further including:
said writer writing certain data to said ring buffer;
removing at least one element from said ring buffer; and
after removing said at least one element from said ring buffer, said reader reading said certain data from said ring buffer.
15. The method of claim 14 , wherein said removing is performed during a write operation.
16. The method of claim 15 , wherein:
a series of elements is next to the first element based on the circular order; and
said removing includes removing one or more elements of said series of elements having a nextfilled pointer set to NULL.
17. The method of claim 6 wherein said writer writes audio/video data to said set of buffers.
18. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1 .
19. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2 .
20. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3 .
21. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4 .
22. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5 .
23. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6 .
24. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7 .
25. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9 .
26. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10 .
27. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11 .
28. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12 .
29. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13 .
30. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14 .
31. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15 .
32. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16 .
33. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 17 .
34. A computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8 .
35. An computing device comprising:
one or more processors;
a writer and a reader;
a set of elements, the set of elements comprising at least a first element, a second element, a third element, and a fourth element; wherein the first element comprises a next pointer that points to said second element and a nextfilled pointer that does not point to any particular location; wherein the second element comprises a next pointer that points to said third element; wherein the third element comprises a next pointer that points to said fourth element and a nextfilled pointer that does not point to any particular location; and
logic encoded in one or more computer-readable media wherein execution by the one or more processors causes:
after the writer has finished writing to a buffer associated with said second element, the writer performing,
determining whether the nextfilled pointer of the third element points to any particular location, and
in response to determining that the nextfilled pointer of the third element does not point to any particular location, advancing to the third element and setting the nextfilled pointer of the first element to point to the second element;
after the reader has finished reading from a buffer associated with the first element, the reader performing,
determining whether the nextfilled pointer of the first element points to any particular location, and
in response to determining that the nextfilled pointer of the first element points to a particular location, advancing to the second element and setting the nextfilled pointer of the first element to not point to any particular location.
36. The computing device of claim 35 , wherein the writer performing determining whether the nextfilled pointer of the third element points to any particular location comprises determining whether the nextfilled pointer of the third element is set to NULL.
37. The computing device of claim 35 , wherein the reader performing determining whether the nextfilled pointer of the first element points to any particular location comprises determining whether the nextfilled pointer of the first element is set to NULL.
38. The computing device of claim 35 , wherein reader performing setting the nextfilled pointer of the first element to not point to any particular location comprises setting the nextfilled pointer of the first element to NULL.
39. The computing device of claim 35 , wherein the writer performing advancing to the third element is performed by the writer in response to the writer determining that the nextfilled pointer of the third element is set to NULL.
40. The computing device of claim 35 , wherein the logic when executed further causes:
generating a ring buffer comprising,
a set of buffers for being filled by said writer and for being read by said reader, and
said set of elements, wherein said set of elements are circularly ordered, each element of said set of elements being associated with a particular buffer from the set of buffers;
wherein each element of said set of elements includes,
a next pointer that points to a next element that follows in the circular order, and
a nextfilled pointer that points to said next element only when the buffer associated with the next element can be read by the reader.