Virtual elastic queue
An electronic device may implement a virtual elastic queue in memory, where, as needed, the virtual elastic queue grows in size to accommodate more queue elements, or shrinks in size to free up queue-element capacity and space in the memory. The virtual elastic queue may include a virtual queue and one or more physical queues, where the virtual queue provides a mapping to the one or more physical queues, and where a data structure may represent queue elements in the one or more physical queues. Notably, the virtual queue may point to the one or more physical queues, and the one or more physical queues may point to physical queue memory where data elements are enqueued and dequeued. Note that the virtual elastic queue may not have a predefined memory size and, up to a size of the memory, may not be constrained.
1. An electronic device, comprising:
a processor; and
memory configured to store program instructions, wherein, when executed by the processor, the program instructions cause the electronic device to perform one or more operations comprising:
implementing a virtual elastic queue in the memory, wherein, as needed, the virtual elastic queue grows in size to accommodate more queue elements, or shrinks in size to free up queue-element capacity and space in the memory;
wherein the virtual elastic queue comprises a virtual queue and one or more physical queues;
wherein the virtual queue provides a mapping to the one or more physical queues, and a data structure represents queue elements in the one or more physical queues; and
wherein, when the one or more physical queues comprise multiple physical queues, a head-end pointer in the virtual queue points to a first physical queue in the multiple physical queues, a tail-end pointer in the virtual queue points to a last physical queue in the multiple physical queues, and a given physical queue, until the last physical queue, points to a next physical queue in the multiple physical queues.
2. The electronic device of claim 1 , wherein the virtual elastic queue does not have a predefined memory size.
3. The electronic device of claim 1 , wherein, up to a size of the memory, a memory size associated with the virtual elastic queue is not constrained.
4. The electronic device of claim 1 , wherein the virtual elastic queue is transparent to one or more threads in the electronic device that use the virtual elastic queue, such that a given thread may ignore a size of a message queue associated with the virtual elastic queue.
5. The electronic device of claim 1 , wherein the virtual queue points to the one or more physical queues, and the one or more physical queues point to physical queue memory where data elements are enqueued and dequeued.
6. The electronic device of claim 1 , wherein the given physical queue has a physical queue size and a base address in the memory.
7. The electronic device of claim 1 , wherein the data structure comprises a sequence of queue elements associated with the given physical queue and, after a last queue element in the sequence of queue elements associated with the given physical queue, there is a logical extension to a next sequence of queue elements associated with the next physical queue.
8. The electronic device of claim 1 , wherein the virtual queue comprises a read pointer that points to a first queue element in the first physical queue with least-recent enqueued data that has yet to be dequeued, and a write pointer that points to a queue element in the one or more physical queues with most-recent enqueued data.
9. The electronic device of claim 8 , wherein, when data is enqueued in the virtual elastic queue and the one or more physical queues are not full, the data is written to a next available queue element following the write pointer, and the write pointer is incremented to point to the next available queue element.
10. The electronic device of claim 8 , wherein, when data is enqueued in the virtual elastic queue and the one or more physical queues are full, a new physical queue is added to the one or more physical queues with a logical extension from a last queue element associated with the last physical queue to a first queue element associated with the new physical queue, the data is written to the first queue element associated with the new physical queue, and the write pointer is changed to point to the first queue element associated with the new physical queue.
11. The electronic device of claim 8 , wherein, when data is dequeued from the virtual elastic queue, the data is dequeued from the first queue element in the first physical queue corresponding to the read pointer, and the read pointer is incremented to point to a next queue element in the data structure.
12. The electronic device of claim 11 , wherein, when the next queue element is included in the next physical queue, then the head-end pointer in the virtual queue is adjusted to point to the next physical queue and the first physical queue is removed from the one or more physical queues.
13. A non-transitory computer-readable storage medium for use in conjunction with an electronic device, the computer-readable storage medium storing program instructions that, when executed by the electronic device, causes the electronic device to perform operations comprising:
implementing a virtual elastic queue in memory;
increasing, as needed, a size of the virtual elastic queue to accommodate more queue elements; and
decreasing, as needed, the size of the virtual elastic queue to free up queue-element capacity and space in the memory, wherein the virtual elastic queue comprises a virtual queue and one or more physical queues;
wherein the virtual queue provides a mapping to the one or more physical queues, and a data structure represents queue elements in the one or more physical queues; and
wherein, when the one or more physical queues comprise multiple physical queues, a head-end pointer in the virtual queue points to a first physical queue in the multiple physical queues, a tail-end pointer in the virtual queue points to a last physical queue in the multiple physical queues, and a given physical queue, until the last physical queue, points to a next physical queue in the multiple physical queues.
14. The non-transitory computer-readable storage medium of claim 13 , wherein the virtual elastic queue does not have a predefined memory size.
15. The non-transitory computer-readable storage medium of claim 13 , wherein the virtual queue comprises a write pointer that points to a queue element associated with the last physical queue in the one or more physical queues with most-recent enqueued data; and
wherein the operations comprise:
when data is enqueued in the virtual elastic queue and the one or more physical queues are full, adding a new physical queue is added to the one or more physical queues with a logical extension from a last queue element associated with the last physical queue to a first queue element associated with the new physical queue;
writing the data to the first queue element associated with the new physical queue and
changing the write pointer to point to the first queue element associated with the new physical queue.
16. The non-transitory computer-readable storage medium of claim 13 , wherein the virtual queue comprises a read pointer that points to a first queue element in the first physical queue in the one or more physical queues with least-recent enqueued data that has yet to be dequeued;
wherein the operations comprise:
when data is dequeued from the virtual elastic queue, dequeuing the data from the first queue element in the first physical queue corresponding to the read pointer, and incrementing the read pointer to point to a next queue element in the data structure; and
when the next queue element is included in the next physical queue, adjusting the head-end pointer in the virtual queue to point to the next physical queue and removing the first physical queue from the one or more physical queues.
17. A method for implementing a virtual elastic queue, comprising:
by an electronic device:
implementing the virtual elastic queue in memory;
increasing, as needed, a size of the virtual elastic queue to accommodate more queue elements; and
decreasing, as needed, the size of the virtual elastic queue to free up queue-element capacity and space in the memory, wherein the virtual elastic queue comprises a virtual queue and one or more physical queues;
wherein the virtual queue provides a mapping to the one or more physical queues, and a data structure represents queue elements in the one or more physical queues; and
wherein, when the one or more physical queues comprise multiple physical queues, a head-end pointer in the virtual queue points to a first physical queue in the multiple physical queues, a tail-end pointer in the virtual queue points to a last physical queue in the multiple physical queues, and a given physical queue, until the last physical queue, points to a next physical queue in the multiple physical queues.
18. The method of claim 17 , wherein the virtual elastic queue does not have a predefined memory size.
19. The method of claim 17 , wherein the virtual queue comprises a write pointer that points to a queue element associated with the last physical queue in the one or more physical queues with most-recent enqueued data; and
wherein, when data is enqueued in the virtual elastic queue and the one or more physical queues are full, the method comprises:
adding a new physical queue to the one or more physical queues with a logical extension from a last queue element associated with the last physical queue to a first queue element associated with the new physical queue;
writing the data to the first queue element associated with the new physical queue; and
changing the write pointer to point to the first queue element associated with the new physical queue.
20. The method of claim 17 , wherein the virtual queue comprises a read pointer that points to a first queue element in the first physical queue in the one or more physical queues with least-recent enqueued data that has yet to be dequeued;
wherein the method comprises:
when data is dequeued from the virtual elastic queue, dequeuing data from the first queue element in the first physical queue corresponding to the read pointer, and incrementing the read pointer to point to a next queue element in the data structure; and
when the next queue element is included in the next physical queue, adjusting the head-end pointer in the virtual queue to point to the next physical queue and removing the first physical queue from the one or more physical queues.