Share via

2.4.8.3 Basic Queue Node

  • Article

A number of objects that are referenced in the remainder of this section depend on a shared generic concept of a queue node. In the context of Search, a queue is implemented as a node that contains an array of fixed-size items. To maintain the FIFO properties of a queue, new items are appended to the end of the array, and items are removed from the front of the array.

However, the PST implementation of the queue object has a special feature to optimize for speed of access by minimizing the amount of data written. Specifically, when an item is removed from the queue, instead of removing the item from the array and shifting remaining items forward, the nidParent field of the queue node is overloaded to be used as a pointer to the "head" of the queue. The following diagram illustrates how this works.

Basic queue structure

Figure 15: Basic queue structure

Because a queue is a standalone entity and does not have the concept of a "parent", the nidParent field of the queue node is re-purposed to be used as a byte offset pointer to the "head" of the queue. Initially, nidParent points to 0 (that is, Item[0]), and new items, each of size k bytes, are appended to the end of the array as shown. When the first item is removed from the queue, the contents of Items[0] is returned to the caller, and then the value of nidParent is updated to point to the next item (that is, Items[1]). Note that nidParent stores the byte offset of the "head" of the queue instead of an item index. The number of items in the queue can be determined by dividing cbData by k (that is, the size of each item). Implementations MUST NOT process the contents of a queue if cbData is not an integer multiple of k.

As an implementation detail, when the last item of the queue is removed (that is, NBTENTRY.nidParent == BBTENTRY.cbData), the entire queue contents are deleted, and both nidParent and cbData are reset to zero.

The same generic queue node concept is used throughout this section, except that each type of queue has its own specific value for the size of each item (that is, k).