Producer-consumer data transfer using piecewise circular queue

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:

• providing a queue data structure including a first array of storage locations and second array of storage locations for storing values, the first array having a first head pointer and a first linking pointer which links the first array to the second array, the second array having a second head pointer;
• consuming and processing values read from the queue with a consumer thread;
• performing a first dequeue operation to read a value stored at a storage location pointed to by the first head pointer and advance the first head pointer;
• and
• performing a second dequeue operation to read a value stored at a storage location pointed to by the second head pointer and advance the second head pointer.

A method performed by a computing device, the 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, a first head pointer, and a first linking pointer;
• reading, with the producer thread, the first head pointer and the first tail pointer;
• storing, with the producer thread, a local copy of the first head pointer, which is only refreshed when the local copy of the first head pointer is not sufficient to indicate whether the first array has room for another value which occurs when the first tail pointer and the local copy of the head pointer indicate that the number of values stored in the first array is equal to the capacity of the first array;
• 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;
• and
• performing 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.