Container data types
====================

Gnulib provides several generic container data types.  They can be used to organize collections of application-defined objects.

Ordinary container data types
-----------------------------

Data type
Details
Module
Main include file
Include file for operations with out-of-memory checking
Sequential list
Can contain any number of objects in any given order.
Duplicates are allowed, but can optionally be forbidden.
list
"gl_list.h"
"gl_xlist.h"
Set
Can contain any number of objects; the order does not matter.
Duplicates (in the sense of the comparator) are forbidden.
set
"gl_set.h"
"gl_xset.h"
Ordered set
Can contain any number of objects in the order of a given comparator
function.
Duplicates (in the sense of the comparator) are forbidden.
oset
"gl_oset.h"
"gl_xoset.h"
Map
Can contain any number of (key, value) pairs, where keys and values
are objects;
there are no (key, value1) and (key, value2) pairs with the same key
(in the sense of a given comparator function).
map
"gl_map.h"
"gl_xmap.h"
Ordered map
Can contain any number of (key, value) pairs, where keys and values
are objects;
the (key, value) pairs are ordered by the key, in the order of a given
comparator function;
there are no (key, value1) and (key, value2) pairs with the same key
(in the sense of the comparator function).
omap
"gl_omap.h"
"gl_xomap.h"

Operations without out-of-memory checking (suitable for use in libraries) are declared in the ``main include file''.  Whereas operations with out-of-memory checking (suitable only in programs) are declared in the ``include file for operations with out-of-memory checking''.

For each of the data types, several implementations are available, with different performance profiles with respect to the available operations. This enables you to start with the simplest implementation (ARRAY) initially, and switch to a more suitable implementation after profiling your application. The implementation of each container instance is specified in a single place only: in the invocation of the function gl_*_create_empty that creates the instance.

The implementations and the guaranteed average performance for the operations for the ``sequential list'' data type are:

Operation
ARRAY
CARRAY
LINKED
TREE
LINKEDHASH with duplicates
LINKEDHASH without duplicates
TREEHASH with duplicates
TREEHASH without duplicates
gl_list_size
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
gl_list_node_value
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
gl_list_node_set_value
O(1)
O(1)
O(1)
O(1)
O(1)
O(1)
O((log n)^2)
O(1)
gl_list_next_node
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_list_previous_node
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_list_first_node
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_list_last_node
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_list_get_at
O(1)
O(1)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_list_get_first
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_list_get_last
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_list_set_at
O(1)
O(1)
O(n)
O(log n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_list_set_first
O(1)
O(1)
O(1)
O(log n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_set_last
O(1)
O(1)
O(1)
O(log n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_search
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O(log n)
O(1)
gl_list_search_from
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_search_from_to
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_indexof
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O(log n)
O(log n)
gl_list_indexof_from
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_list_indexof_from_to
O(n)
O(n)
O(n)
O(n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_list_add_first
O(n)
O(1)
O(1)
O(log n)
O(1)
O(1)
O((log n)^2)
O(log n)
gl_list_add_last
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O((log n)^2)
O(log n)
gl_list_add_before
O(n)
O(n)
O(1)
O(log n)
O(1)
O(1)
O((log n)^2)
O(log n)
gl_list_add_after
O(n)
O(n)
O(1)
O(log n)
O(1)
O(1)
O((log n)^2)
O(log n)
gl_list_add_at
O(n)
O(n)
O(n)
O(log n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_list_remove_node
O(n)
O(n)
O(1)
O(log n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_remove_at
O(n)
O(n)
O(n)
O(log n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_list_remove_first
O(n)
O(1)
O(1)
O(log n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_remove_last
O(1)
O(1)
O(1)
O(log n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_remove
O(n)
O(n)
O(n)
O(n)
O(n)
O(1)
O((log n)^2)
O(log n)
gl_list_iterator
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_list_iterator_from_to
O(1)
O(1)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_list_iterator_next
O(1)
O(1)
O(1)
O(log n)
O(1)
O(1)
O(log n)
O(log n)
gl_sortedlist_search
O(log n)
O(log n)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_sortedlist_search_from
O(log n)
O(log n)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_sortedlist_indexof
O(log n)
O(log n)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_sortedlist_indexof_from
O(log n)
O(log n)
O(n)
O(log n)
O(n)
O(n)
O(log n)
O(log n)
gl_sortedlist_add
O(n)
O(n)
O(n)
O(log n)
O(n)
O(n)
O((log n)^2)
O(log n)
gl_sortedlist_remove
O(n)
O(n)
O(n)
O(log n)
O(n)
O(n)
O((log n)^2)
O(log n)

The implementations and the guaranteed average performance for the operations for the ``set'' data type are:

Operation
ARRAY
LINKEDHASH, HASH
gl_set_size
O(1)
O(1)
gl_set_add
O(n)
O(1)
gl_set_remove
O(n)
O(1)
gl_set_search
O(n)
O(1)
gl_set_iterator
O(1)
O(1)
gl_set_iterator_next
O(1)
O(1)

The implementations and the guaranteed average performance for the operations for the ``ordered set'' data type are:

Operation
ARRAY
TREE
gl_oset_size
O(1)
O(1)
gl_oset_add
O(n)
O(log n)
gl_oset_remove
O(n)
O(log n)
gl_oset_search
O(log n)
O(log n)
gl_oset_search_atleast
O(log n)
O(log n)
gl_oset_iterator
O(1)
O(log n)
gl_oset_iterator_next
O(1)
O(log n)

The implementations and the guaranteed average performance for the operations for the ``map'' data type are:

Operation
ARRAY
LINKEDHASH, HASH
gl_map_size
O(1)
O(1)
gl_map_get
O(n)
O(1)
gl_map_put
O(n)
O(1)
gl_map_remove
O(n)
O(1)
gl_map_search
O(n)
O(1)
gl_map_iterator
O(1)
O(1)
gl_map_iterator_next
O(1)
O(1)

The implementations and the guaranteed average performance for the operations for the ``ordered map'' data type are:

Operation
ARRAY
TREE
gl_omap_size
O(1)
O(1)
gl_omap_get
O(log n)
O(log n)
gl_omap_put
O(n)
O(log n)
gl_omap_remove
O(n)
O(log n)
gl_omap_search
O(log n)
O(log n)
gl_omap_search_atleast
O(log n)
O(log n)
gl_omap_iterator
O(1)
O(log n)
gl_omap_iterator_next
O(1)
O(log n)

For C++, Gnulib provides a C++ template class for each of these container data types.

Data type
C++ class
Module
Include file
Sequential list
gl_List
list-c++
"gl_list.hh"
Set
gl_Set
set-c++
"gl_set.hh"
Ordered set
gl_OSet
oset-c++
"gl_oset.hh"
Map
gl_Map
map-c++
"gl_map.hh"
Ordered map
gl_OMap
omap-c++
"gl_omap.hh"

Specialized container data types
--------------------------------

The hamt module implements the hash array mapped trie (HAMT) data structure.  This is a data structure that contains (key, value) pairs. Lookup of a (key, value) pair given the key is on average an O(1) operation, assuming a good hash function for the keys is employed.

The HAMT data structure is useful when you want modifications (additions of pairs, removal, value changes) to be visible only to some part of your program, whereas other parts of the program continue to use the unmodified HAMT.  The HAMT makes this possible in a space-efficient manner: the modified and the unmodified HAMT share most of their allocated memory.  It is also time-efficient: Every such modification is O(1) on average, again assuming a good hash function for the keys.

A HAMT can be used whenever an ordinary hash table would be used.  It does however, provide non-destructive updating operations without the need to copy the whole container. On the other hand, a hash table is simpler so that its performance may be better when non-destructive update operations are not needed.

For example, a HAMT can be used to model the dynamic environment in a LISP interpreter.  Updating a value in the dynamic environment of one continuation frame would not modify values in earlier frames.

To use the module, include hamt.h in your code.  The public interface is documented in that header file.  You have to provide a hash function and an equivalence relation, which defines key equality.  The module includes a test file test-hamt.c, which demonstrates how the API can be used.

In the current implementation, each inner node of the HAMT can store up to 32 = 2^5 entries and subtries.  Whenever a collision between the initial bits of the hash values of two entries would happen, the next 5 bits of the hash values are examined and the two entries pushed down one level in the trie.

HAMTs have the same average access times as hash tables but grow and shrink dynamically, so they use memory more economically and do not have to be periodically resized.

They were described and analyzed in Phil Bagwell (2000). Ideal Hash Trees (Report). Infoscience Department, École Polytechnique Fédérale de Lausanne.

The persistence aspect of the HAMT data structure, which means that each updating operation (like inserting, replacing, or removing an entry) returns a new HAMT while leaving the original one intact, is achieved through structure sharing, which is even safe in the presence of multiple threads when the used C compiler supports atomics.