What data structure or mix of data structures would I use for a concurrent queue that allows for bulk and specific deletes?

Question

Here is my problem, I need a data structure that behaves like a queue, but has some other properties:

• I should be able to easily delete items given a tag (every item in this queue has a tag that groups them)
• I also need to be able to delete one item given a key (all items added to the collection will have such a unique key). Here, if it simplifies things, I could remove by tag and key if it would make it faster.
• This collection is used in a concurrent environment so using as little locking as possible would be awesome
• It should have the usual FIFO properties of a queue. I do not need to access items not in head, but i need the deleting behavior above to work.

I'm using C# to build this solution but I'd be much more interested in algorithms and data structures definitions as I hardly believe any of the available collections meet my needs.

Papers, books, blog posts and any other kind of reference to this are really welcome.

Answer 1

Sounds like you can use a concurrent singly-linked list for the queue part. For the delete-by-key part you could keep a concurrent hash-table (striped locks are easy to do) pointing to nodes in the queue.

If that approach fails, look at how database systems do this. They can do all of what you want, concurrently. They maintain a primary copy of the data in a b-tree and maintain secondary b-tree indices. For locking, they use a concurrent hash-table. B-trees have nice concurrency properties because you can easily share-lock the upper parts of them even while you update the leaves under an exclusive lock.

Answer 2

I think you can use a doubly multi-linked lists and two hashtables.

• One part of list for the queue
• Another part for grouping nodes by tag
• One hashtable for accessing a node by key
• Another hashtable for accessing nodes by a tag

Examples in Python (I'm sorry...)

Inserting an element:

 items_table['item_key'] = new_item

 my_queue.tail.next = new_item
 new_item.previous = my_queue.tail
 my_queue.tail = new_item

 new_item.next_by_tag = tags_table['item_tag'] #head of tag's list
 tags_table['item_tag'].previous_by_tag = new_item
 tags_table['item_tag'] = new_item

Removing a element by key:

item = key_table['node_key']

item.next.previous = item.previous
item.previous.next = item.next

item.next_by_tag.previous_by_tag = item.previous_by_tag
item.previous_by_tag.next_by_tag = item.next_by_tag

del item

Removing a element by tag:

def remove_elements_by_tag(tag_head):
    if tag_head == None:
        return
    else:
        remove_elements_by_tag(tag_head.next_by_tag)
        tag_head.next.previous = tag_head.previous
        tag_head.previous.next = tag_head.next

Something like that. Hope it helps.