Lines Matching full:a
7 a list becomes problematic due to algorithmic costs of searching it.
8 For these situations, Zephyr provides a balanced tree implementation
10 O(log2(N)) for a tree of size N. This is implemented using a
13 The :c:struct:`rbtree` tracking struct for a rbtree may be initialized
18 Unlike a list, where position is explicit, the ordering of nodes
19 within an rbtree must be provided as a predicate function by the user.
20 A function of type :c:func:`rb_lessthan_t` should be assigned to the
23 return a boolean True value if the first node argument is "less than"
25 not allowed, nodes within a tree must have a single fixed order for
29 represented as a :c:struct:`rbnode` structure which exists in
34 a list.
36 Nodes can be inserted into a tree with :c:func:`rb_insert` and removed
37 with :c:func:`rb_remove`. Access to the "first" and "last" nodes within a
39 provided by :c:func:`rb_get_min` and :c:func:`rb_get_max`. There is also a
40 predicate, :c:func:`rb_contains`, which returns a boolean True if the
46 rbtree. The first, :c:func:`rb_walk`, is a simple callback implementation
47 where the caller specifies a C function pointer and an untyped
49 each node in order. This has the advantage of a very simple
50 implementation, at the cost of a somewhat more cumbersome API for the
51 user (not unlike ISO C's :c:func:`bsearch` routine). It is a recursive
56 There is also a :c:macro:`RB_FOR_EACH` iterator provided, which, like the
57 similar APIs for the lists, works to iterate over a list in a more
58 natural way, using a nested code block instead of a callback. It is
60 default (however, this can be configured to use a fixed/maximally size
62 the lists, this is also available in a :c:macro:`RB_FOR_EACH_CONTAINER`
63 variant which enumerates using a pointer to a container field and not
69 As described, the Zephyr rbtree implementation is a conventional
78 each node, either red or black, and enforcing a rule that no red child
79 can be a child of another red child (i.e. that the number of black
82 enforced by a set of rotation rules used to "fix" trees following
90 A maximally unbalanced rbtree with a black height of two. No more
94 These rotations are conceptually implemented on top of a primitive
102 The :c:struct:`rbnode` struct for a Zephyr rbtree contains only two
103 pointers, representing the "left", and "right" children of a node
104 within the binary tree. Traversal of a tree for rebalancing following
106 "upwards" from a node as well. It is very common for red/black trees
107 in the industry to store a third "parent" pointer for this purpose.
108 Zephyr avoids this requirement by building a "stack" of node pointers
110 appropriately as modifications are made. So a Zephyr rbtree can be
111 implemented with no more runtime storage overhead than a dlist.
113 These properties, of a balanced tree data structure that works with
115 a memory allocation API, are quite rare in the industry and are