Page History

...

The QueueConsumerNodeList is the underlying data structure of all of QCM's lists. It is thread-safe and allows O(1) appending and given you have a pointer to an entry O(1) deletion. It is essentially a singly linked list. To achieve O(1) deletion entries are marked for deletion but only actually removed upon the next iteration.  The rational rationale being that, to delete an entry you would need to update the previous entry's "next" pointer but to get to the previous element you would need a doubly linked list which it impossible to maintain in a thread-safe way without locking. Special care must be taken when removing elements from the tail since we keep an explicit reference to it in the QueueConsumerNodeList to achieve O(1) appending. The data structure in the QueueConsumerNodeList are called QueueConsumerNodeListEntries which themselves have a reference to a QueueConsumerNode which is the persistent entity that moves between QCM's lists and has a reference to the QueueConsumer. The QueueConsumer itself also has a reference to the QueueConsumerNode to enable O(1) deletion given a Consumer. This tightly couples the QueueConsumer and QCM classes.

...