Data Structures

The Qthreads library provides several C-based lock-free data structures.

Introduction

Qthreads provides the following C-based lock-free data structures:

• Dictionary (a hash-table for storing string-based key-value pairs)
• Queues
  • fully-ordered Single-producer single-consumer (SPSC/SWSR)
  • Fully-ordered Multi-producer multi-consumer
  • Distributed partially-ordered multi-producer multi-consumer
• Distributed arrays
• Distributed memory pools

Dictionary: qt_dictionary

This data structure is a lock-free dictionary based on a lock-free hash table implementation. The exact hash table implementation is controlled via the --with-dict configure flag. Current options include:

• simple - uses a large array of unordered linked lists
• shavit - based on the work by Ori Shalev and Nir Shavit, "Split-Ordered Lists: Lock-Free Extensible Hash Tables"
• trie - uses a hierarchical set or arrays

Header File

The header file to include to use this datatype is: <qthread/dictionary.h>

Datatype

The datatype of a Qthread dictionary is qt_dictionary. Dictionaries also have iterators: qt_dictionary_iterator. Each element of the dictionary is a list_entry, which consists of a key, a value, a hash value of the key generated by a user-provided function, and a next pointer.

Interface

The basic interface is as follows:

Function	Description
qt_dictionary_create(eq, hash, cleanup)	Creates a dictionary that uses eq to determine equality between keys, hash to generate hash values of the keys, and cleanup to destroy/deallocate keys and values (optional).
qt_dictionary_destroy(dict)	Destroys and deallocates the dictionary dict
qt_dictionary_put(dict, key, value)	Inserts the key, value pair into the dictionary dict
qt_dictionary_put_if_absent(dict, key, value)	Inserts the key, value pair into the dictionary dict only if key does not already exist in the dictionary.
qt_dictionary_get(dict, key)	Looks up key in the dictionary dict and returns the associated value.
qt_dictionary_delete(dict, key)	Removes the key from the dictionary dict and calls the cleanup function on the associated list_entry.

Dictionaries also have iterators, that have the following interface:

Function	Description
qt_dictionary_iterator_create(dict)	Creates a new iterator for the dictionary dict.
qt_dictionary_iterator_destroy(iter)	Destroys and deallocates the iterator iter.
qt_dictionary_iterator_next(iter)	Advances the iterator iter and retrieves the next entry.
qt_dictionary_iterator_get(iter)	Returns the current entry pointed to by the iterator iter.
qt_dictionary_iterator_equals(iter1, iter2)	Tests equality between two iterators.
qt_dictionary_iterator_copy(iter)	Creates a copy of the iterator iter.

Queues

Single-producer Single-consumer: qswsrqueue

Fully-ordered Multi-producer Multi-consumer: qlfqueue

Partially-ordered Multi-producer Multi-consumer: qdqueue

Distributed Arrays: qarray

Distributed Memory Pools: qpool