Producer-consumer data transfer using piecewise circular queue

摘要

A method includes producing values with a producer thread, and providing a queue data structure including a first array of storage locations for storing the values. The first array has a first tail pointer and a first linking pointer. If a number of values stored in the first array is less than a capacity of the first array, an enqueue operation writes a new value at a storage location pointed to by the first tail pointer and advances the first tail pointer. If the number of values stored in the first array is equal to the capacity of the first array, a second array of storage locations is allocated in the queue. The second array has a second tail pointer. The first array is linked to the second array with the first linking pointer. An enqueue operation writes the new value at a storage location pointed to by the second tail pointer and advances the second tail pointer.

主权项

1. A computer readable storage medium, which does not include transitory propagating signals, storing computer-executable instructions for controlling a computing device to perform a method comprising:
producing values with a producer thread; providing a queue data structure including a first array of storage locations for storing the values, the first array having a first tail pointer and a first linking pointer; if a number of values stored in the first array is less than a capacity of the first array,
performing an enqueue operation to write a new value at a storage location pointed to by the first tail pointer and advance the first tail pointer; and if the number of values stored in the first array is equal to the capacity of the first array,
allocating a second array of storage locations in the queue, the second array having a second tail pointer;linking the first array to the second array with the first linking pointer; andperforming an enqueue operation to write the new value at a storage location pointed to by the second tail pointer and advance the second tail pointer.