Method and system for queuing data for multiple readers and writers
View Patent ↗Systems and methods of queuing data for multiple readers and writers are provided. Enqueuing operations are disclosed that can process write functionality and can determine whether ring buffers have potentially filled, and dynamically declare a new ring buffer at a multiple of capacity of the current ring. Dequeuing operations are disclosed that can process read functionality for advancing control and determining whether and when to free ring buffers from memory.
1. A computer-implemented method of allocating a ring buffer, the method comprising:
sequentially storing data with a first set of values in a first ring buffer comprising x elements, wherein x is a positive integer greater than two;
determining that the first ring buffer is full because a first element of the first ring buffer and a last element of the first ring buffer have wrapped upon each other;
allocating a second ring buffer, wherein the second ring buffer contains at least x+1elements; and
sequentially storing data with a second set of values in one or more elements of the second ring buffer, wherein write operations are performed on elements of the second ring buffer because the last element of the first ring buffer is occupied by a value, and wherein reading operations are performed on the first set of values in the first ring buffer concurrently with or subsequently to the write operations being performed on the second set of values in the ring buffer.
2. The method of claim 1 , wherein, provided that x>3, the second ring buffer contains a quantity of elements equal to x times y, wherein y=2 or a positive multiple of 2.
3. The method of claim 1 , wherein added write operations are blocked to the first ring buffer.
4. The method of claim 1 , wherein a fill pointer in a queue is directed from the first ring buffer to the second ring buffer.
5. The method of claim 1 , wherein a current element is determined by performing a modulo operation wherein the numerator is derived from a value in an index field and the divisor equals x.
6. The method of claim 5 , wherein the current element represents a logical position corresponding to a value in an index field.
7. The method of claim 6 , wherein the first ring buffer is determined to be in a wrapped condition upon detecting that a logical position of a current element maps to a physical position of an element in the first ring buffer that is already occupied by a value.
8. The method of claim 1 , wherein the first ring buffer and second ring buffer are associated in a linked list data structure.
9. A computer-implemented method of deallocating a ring buffer, the method comprising:
storing a queue comprising at least one pointer;
sequentially storing data with a first set of values in a first ring buffer comprising x elements, wherein x is a positive integer greater than two;
determining that the first ring buffer is full because a first element of the first ring buffer and a last element of the first ring buffer have wrapped upon each other;
allocating a second ring buffer, wherein the second ring buffer contains at least x+1elements; and
sequentially storing data with a second set of values in one or more elements of the second ring buffer, wherein write operations are performed on an element of the second ring buffer because the last element of the first ring buffer is occupied by a value, and wherein reading operations are performed on the first set of values in the first ring buffer concurrently with or subsequently to the write operations being performed on the second set of values in the ring buffer;
determining that the first ring buffer is empty based on a head pointer being associated with the first ring buffer, and a drain pointer being associated with the second ring buffer; and
deallocating the first ring buffer.
10. The method of claim 9 , wherein it is identified that there is one reader and no writer, and, in the computing environment being used, at least some manual memory management is required for handling deallocation of a ring buffer.
11. A computer-implemented method of deallocating a ring buffer, the method comprising:
storing a first ring buffer having a plurality of elements;
sequentially storing data with a first set of values in a first ring buffer comprising x elements, wherein x is a positive integer greater than two;
determining that the first ring buffer is full because a first element of the first ring buffer and a last element of the first ring buffer have wrapped upon each other;
allocating a second ring buffer, wherein the second ring buffer contains at least x+1elements;
sequentially storing data with a second set of values in one or more elements of the second ring buffer, wherein write operations are performed on elements of the second ring buffer because the last element of the first ring buffer is occupied by a value, and wherein reading operations are performed on the first set of values in the first ring buffer concurrently with or subsequently to the write operations being performed on the second set of values in the ring buffer;
storing, in a local field, values corresponding to a current front element of the first ring buffer and an end element in the first ring buffer;
determining that the first ring buffer is empty because the first ring buffer either:
is not blocked and is not wrapped, or
the first ring buffer is blocked and the value of the current front element is not in a position corresponding to the end element; and
deallocating the first ring buffer.
12. A computer-implemented method of storing a queue, the queue associated with at least one ring buffer, the method comprising:
storing at least one queue attribute that points to at least one attribute of a first ring buffer, wherein the at least one queue attribute includes one or more of:
a head pointer,
a drain pointer,
a value corresponding to a quantity of readers, or
a value corresponding to a quantity of writers;
sequentially storing data with a first set of values in the first ring buffer; and
sequentially storing data with a second set of values in one or more elements of a second ring buffer, wherein write operations are performed on elements of the second ring buffer because the last element of the first ring buffer is occupied by a value, and wherein reading operations are performed on the first set of values in the first ring buffer concurrently with or subsequently to the write operations being performed on the second set of values in the ring buffer.
13. The method of claim 12 , wherein a second ring buffer is allocated in response to a determination that the first ring buffer is full, and a first queue attribute is caused to point to the first ring buffer and a second queue attribute is caused to point to the second ring buffer.
14. The method of claim 12 , wherein in the computing environment being used at least some degree of manual memory management is required for handling deallocation of a ring buffer, and further wherein one pointer corresponds to a quantity of readers, and one pointer corresponds to a quantity of writers.