Data structures

The framework API features a small library of data structures that are solely exist to support the framework implementation. They have been designed under the following considerations:

List and registry

Most book-keeping tasks in Genode rely on single-connected lists, which use the List template.

Genode::List

Genode::List_element

Registry

Most commonly, lists are used as containers that solely remember dynamically created objects. In this use case, the lifetime of the remembered object is tightly coupled with its presence in the list. The Registry class template represents a safe wrapper around the raw list that ensures this presumption and thereby eliminates classes of list-related bugs by design, e.g., double insertion, missing removal.

An object type to be remembered in a Registry inherits the Registry::Element base class, which takes its registry and a reference to the object itself as arguments. Thereby, the relationship of the object with its corresponding registry is fixed at the object's construction time. Once constructed, it is implicitly part of the registry. The registry provides a for_each method to iterate over its elements. Unlike the traversal of a raw list, this for_each operation is thread safe. It also supports the safe destruction of the currently visited object.

Genode::Registry

As an alternative to the use of the Registry::Element base class, the Registered and Registered_no_delete helper templates supplement arbitrary object types with the ability to become registry elements. They wrap a given object type in a new type whereby the original type remains untainted by the fact that its objects are kept in a registry.

Genode::Registered

Genode::Registered_no_delete

Fifo queue

Because the List inserts new list elements at the list head, it cannot be used for implementing wait queues requiring first-in-first-out semantics. For such use cases, there exists a dedicated Fifo template.

Genode::Fifo

Genode::Fifo_element

AVL tree

For use cases where associative arrays are needed such as allocators, there is class template for creating AVL trees. The tree-balancing mechanism is implemented in the Avl_node_base class. The actual Avl_node and Avl_tree classes are tagged with the element type, which ensures that each AVL tree hosts only one type of elements.

Genode::Avl_node_base

Genode::Avl_node

Genode::Avl_tree

Dictionary

The Dictionary provides an easy and safe way to organize objects by using strings as keys. It alleviates the need to manually use the bare-bones AVL tree for this prominent use case. The Dictionary attains its safety from following the principle design of the Registry. That is, elements are automatically added to the dictionary at construction time, respectively removed at destruction time. The method with_element calls a functor with one element by specifying its name as key, and the with_any_element interface supports the orderly destruction of all dictionary items. These patterns limit the exposure of individual dictionary elements to a local scope at the caller.

Genode::Dictionary

ID space

Similar to how the Registry provides a safe wrapper around list's most common use case, the Id_space covers a prominent use case for AVL trees in a safeguarded fashion, namely the association of objects with IDs. Internally, IDs are kept in an AVL tree but that implementation detail remains hidden from the API. In contrast to a bit allocator, the ID space can be sparsely populated and does not need to be dimensioned. The lifetime of an ID is bound to an Element object, which relieves the programmer from manually allocating/deallocating IDs for objects.

Genode::Id_space

Bit array

Bit arrays are typically used for the allocation of IDs. The Bit_array_base class operates on a memory buffer specified to its constructor. The Bit_array class template addresses the common case where the ID space is dimensioned at compile time. It takes the number of bits as arguments and hosts the memory buffer for storing the bits within the object.

Genode::Bit_array_base

Genode::Bit_array