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.




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.


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.



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.



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.




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.


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.