Circular queue management with split indexes
AssigneeUT-Battelle, LLC
InventorsNarasinga Rao Miniskar, Frank Y. Liu, Jeffrey S. Vetter
Life of this patent
Estimating the term…
Abstract
Methods and apparatus for managing circular queues are disclosed. A pointer designates an index position of a particular queue element and contains an additional pointer state, whereby two pointer values (split indexes) can designate the same index position. Front and rear pointers are respectively managed by dequeue and enqueue logic. The front pointer state and rear pointer state distinguish full and empty queue states when both pointers designate the same index position. Asynchronous dequeue and enqueue operations are supported, no lock is required, and no queue entry is wasted. Hardware and software embodiments for numerous applications are disclosed.
Claims16
A system for managing a lock free circular queue, wherein the queue has a predetermined number of elements and each element has a predetermined size, wherein the elements are indexed using respective element indexes and each element index is split into a respective pair of split indexes, and wherein a rear pointer of the queue is updated when an enqueue operation is performed, and a front pointer of the queue is updated when a dequeue operation is performed, the system comprising:
- a rear-pointer controller configured to:
- determine whether a requested enqueue operation would fill the queue;
- if so, set the rear pointer to a given rear split index that indicates, in conjunction with a current value of the front pointer, that the queue is full;
- and
- otherwise, set the rear pointer to a default rear split index;
- and
- a front-pointer controller configured to:
- evaluate whether a requested dequeue operation would empty the queue;
- if so, set the front pointer to a given front split index that indicates, in conjunction with a current value of the rear pointer, that the queue is empty;
- and
- otherwise, set the front pointer to a default front split index.
Dependencies are inferred from the claim text.