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:
-
They should be as simple as possible to make them easy to evaluate for correctness. Low complexity takes precedence over performance.
-
Each data structure provides a rigid interface that is targeted at a specific use case and does not attempt to be a power tool. For example, the Fifo deliberately provides no way to randomly access elements, the List merely provides the functionality to remember elements but lacks list-manipulation operations.
-
Data structures perform no hidden anonymous memory allocations by storing meta data intrusively. This is precondition for allowing resources multiplexers and runtime environments to properly account their local memory allocations. Section Component-local heap partitioning provides the rationale behind the need for full control over memory allocations.
List and registry
Most book-keeping tasks in Genode rely on single-connected lists, which use the List template.
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.
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.