LCOV - code coverage report
Current view: top level - include/zephyr/sys - rb.h (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 2 0.0 %
Date: 2022-08-18 11:36:24 Functions: 0 1 0.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            :  * Copyright (c) 2018 Intel Corporation
       3                 :            :  *
       4                 :            :  * SPDX-License-Identifier: Apache-2.0
       5                 :            :  */
       6                 :            : 
       7                 :            : /* Our SDK/toolchains integration seems to be inconsistent about
       8                 :            :  * whether they expose alloca.h or not.  On gcc it's a moot point as
       9                 :            :  * it's always builtin.
      10                 :            :  */
      11                 :            : #ifdef __GNUC__
      12                 :            : #ifndef alloca
      13                 :            : #define alloca __builtin_alloca
      14                 :            : #endif
      15                 :            : #else
      16                 :            : #include <alloca.h>
      17                 :            : #endif
      18                 :            : 
      19                 :            : /**
      20                 :            :  * @file
      21                 :            :  * @brief Red/Black balanced tree data structure
      22                 :            :  *
      23                 :            :  * This implements an intrusive balanced tree that guarantees
      24                 :            :  * O(log2(N)) runtime for all operations and amortized O(1) behavior
      25                 :            :  * for creation and destruction of whole trees.  The algorithms and
      26                 :            :  * naming are conventional per existing academic and didactic
      27                 :            :  * implementations, c.f.:
      28                 :            :  *
      29                 :            :  * https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
      30                 :            :  *
      31                 :            :  * The implementation is size-optimized to prioritize runtime memory
      32                 :            :  * usage.  The data structure is intrusive, which is to say the struct
      33                 :            :  * rbnode handle is intended to be placed in a separate struct the
      34                 :            :  * same way other such structures (e.g. Zephyr's dlist list) and
      35                 :            :  * requires no data pointer to be stored in the node.  The color bit
      36                 :            :  * is unioned with a pointer (fairly common for such libraries).  Most
      37                 :            :  * notably, there is no "parent" pointer stored in the node, the upper
      38                 :            :  * structure of the tree being generated dynamically via a stack as
      39                 :            :  * the tree is recursed.  So the overall memory overhead of a node is
      40                 :            :  * just two pointers, identical with a doubly-linked list.
      41                 :            :  */
      42                 :            : 
      43                 :            : #ifndef ZEPHYR_INCLUDE_SYS_RB_H_
      44                 :            : #define ZEPHYR_INCLUDE_SYS_RB_H_
      45                 :            : 
      46                 :            : #include <stdbool.h>
      47                 :            : #include <stdint.h>
      48                 :            : 
      49                 :            : struct rbnode {
      50                 :            :         struct rbnode *children[2];
      51                 :            : };
      52                 :            : 
      53                 :            : /* Theoretical maximum depth of tree based on pointer size. If memory
      54                 :            :  * is filled with 2-pointer nodes, and the tree can be twice as a
      55                 :            :  * packed binary tree, plus root...  Works out to 59 entries for 32
      56                 :            :  * bit pointers and 121 at 64 bits.
      57                 :            :  */
      58                 :            : #define Z_TBITS(t) ((sizeof(t)) < 8 ? 2 : 3)
      59                 :            : #define Z_PBITS(t) (8 * sizeof(t))
      60                 :            : #define Z_MAX_RBTREE_DEPTH (2 * (Z_PBITS(int *) - Z_TBITS(int *) - 1) + 1)
      61                 :            : 
      62                 :            : 
      63                 :            :  /**
      64                 :            :   * @defgroup rbtree_apis Balanced Red/Black Tree
      65                 :            :   * @ingroup datastructure_apis
      66                 :            :   * @{
      67                 :            :   */
      68                 :            : /**
      69                 :            :  * @typedef rb_lessthan_t
      70                 :            :  * @brief Red/black tree comparison predicate
      71                 :            :  *
      72                 :            :  * Compares the two nodes and returns true if node A is strictly less
      73                 :            :  * than B according to the tree's sorting criteria, false otherwise.
      74                 :            :  *
      75                 :            :  * Note that during insert, the new node being inserted will always be
      76                 :            :  * "A", where "B" is the existing node within the tree against which
      77                 :            :  * it is being compared.  This trait can be used (with care!) to
      78                 :            :  * implement "most/least recently added" semantics between nodes which
      79                 :            :  * would otherwise compare as equal.
      80                 :            :  */
      81                 :            : typedef bool (*rb_lessthan_t)(struct rbnode *a, struct rbnode *b);
      82                 :            : 
      83                 :            : struct rbtree {
      84                 :            :         struct rbnode *root;
      85                 :            :         rb_lessthan_t lessthan_fn;
      86                 :            :         int max_depth;
      87                 :            : #ifdef CONFIG_MISRA_SANE
      88                 :            :         struct rbnode *iter_stack[Z_MAX_RBTREE_DEPTH];
      89                 :            :         unsigned char iter_left[Z_MAX_RBTREE_DEPTH];
      90                 :            : #endif
      91                 :            : };
      92                 :            : 
      93                 :            : typedef void (*rb_visit_t)(struct rbnode *node, void *cookie);
      94                 :            : 
      95                 :            : struct rbnode *z_rb_child(struct rbnode *node, uint8_t side);
      96                 :            : int z_rb_is_black(struct rbnode *node);
      97                 :            : #ifndef CONFIG_MISRA_SANE
      98                 :            : void z_rb_walk(struct rbnode *node, rb_visit_t visit_fn, void *cookie);
      99                 :            : #endif
     100                 :            : struct rbnode *z_rb_get_minmax(struct rbtree *tree, uint8_t side);
     101                 :            : 
     102                 :            : /**
     103                 :            :  * @brief Insert node into tree
     104                 :            :  */
     105                 :            : void rb_insert(struct rbtree *tree, struct rbnode *node);
     106                 :            : 
     107                 :            : /**
     108                 :            :  * @brief Remove node from tree
     109                 :            :  */
     110                 :            : void rb_remove(struct rbtree *tree, struct rbnode *node);
     111                 :            : 
     112                 :            : /**
     113                 :            :  * @brief Returns the lowest-sorted member of the tree
     114                 :            :  */
     115                 :          0 : static inline struct rbnode *rb_get_min(struct rbtree *tree)
     116                 :            : {
     117                 :          0 :         return z_rb_get_minmax(tree, 0U);
     118                 :            : }
     119                 :            : 
     120                 :            : /**
     121                 :            :  * @brief Returns the highest-sorted member of the tree
     122                 :            :  */
     123                 :            : static inline struct rbnode *rb_get_max(struct rbtree *tree)
     124                 :            : {
     125                 :            :         return z_rb_get_minmax(tree, 1U);
     126                 :            : }
     127                 :            : 
     128                 :            : /**
     129                 :            :  * @brief Returns true if the given node is part of the tree
     130                 :            :  *
     131                 :            :  * Note that this does not internally dereference the node pointer
     132                 :            :  * (though the tree's lessthan callback might!), it just tests it for
     133                 :            :  * equality with items in the tree.  So it's feasible to use this to
     134                 :            :  * implement a "set" construct by simply testing the pointer value
     135                 :            :  * itself.
     136                 :            :  */
     137                 :            : bool rb_contains(struct rbtree *tree, struct rbnode *node);
     138                 :            : 
     139                 :            : #ifndef CONFIG_MISRA_SANE
     140                 :            : /**
     141                 :            :  * @brief Walk/enumerate a rbtree
     142                 :            :  *
     143                 :            :  * Very simple recursive enumeration.  Low code size, but requiring a
     144                 :            :  * separate function can be clumsy for the user and there is no way to
     145                 :            :  * break out of the loop early.  See RB_FOR_EACH for an iterative
     146                 :            :  * implementation.
     147                 :            :  */
     148                 :            : static inline void rb_walk(struct rbtree *tree, rb_visit_t visit_fn,
     149                 :            :                            void *cookie)
     150                 :            : {
     151                 :            :         z_rb_walk(tree->root, visit_fn, cookie);
     152                 :            : }
     153                 :            : #endif
     154                 :            : 
     155                 :            : struct _rb_foreach {
     156                 :            :         struct rbnode **stack;
     157                 :            :         uint8_t *is_left;
     158                 :            :         int32_t top;
     159                 :            : };
     160                 :            : 
     161                 :            : #ifdef CONFIG_MISRA_SANE
     162                 :            : #define _RB_FOREACH_INIT(tree, node) {                                  \
     163                 :            :         .stack   = &(tree)->iter_stack[0],                               \
     164                 :            :         .is_left = &(tree)->iter_left[0],                                \
     165                 :            :         .top     = -1                                                   \
     166                 :            : }
     167                 :            : #else
     168                 :            : #define _RB_FOREACH_INIT(tree, node) {                                  \
     169                 :            :         .stack   = (struct rbnode **)                                   \
     170                 :            :                         alloca((tree)->max_depth * sizeof(struct rbnode *)), \
     171                 :            :         .is_left = (uint8_t *)alloca((tree)->max_depth * sizeof(uint8_t)),\
     172                 :            :         .top     = -1                                                   \
     173                 :            : }
     174                 :            : #endif
     175                 :            : 
     176                 :            : struct rbnode *z_rb_foreach_next(struct rbtree *tree, struct _rb_foreach *f);
     177                 :            : 
     178                 :            : /**
     179                 :            :  * @brief Walk a tree in-order without recursing
     180                 :            :  *
     181                 :            :  * While @ref rb_walk() is very simple, recursing on the C stack can
     182                 :            :  * be clumsy for some purposes and on some architectures wastes
     183                 :            :  * significant memory in stack frames.  This macro implements a
     184                 :            :  * non-recursive "foreach" loop that can iterate directly on the tree,
     185                 :            :  * at a moderate cost in code size.
     186                 :            :  *
     187                 :            :  * Note that the resulting loop is not safe against modifications to
     188                 :            :  * the tree.  Changes to the tree structure during the loop will
     189                 :            :  * produce incorrect results, as nodes may be skipped or duplicated.
     190                 :            :  * Unlike linked lists, no _SAFE variant exists.
     191                 :            :  *
     192                 :            :  * Note also that the macro expands its arguments multiple times, so
     193                 :            :  * they should not be expressions with side effects.
     194                 :            :  *
     195                 :            :  * @param tree A pointer to a struct rbtree to walk
     196                 :            :  * @param node The symbol name of a local struct rbnode* variable to
     197                 :            :  *             use as the iterator
     198                 :            :  */
     199                 :            : #define RB_FOR_EACH(tree, node) \
     200                 :            :         for (struct _rb_foreach __f = _RB_FOREACH_INIT(tree, node);     \
     201                 :            :              (node = z_rb_foreach_next(tree, &__f));                        \
     202                 :            :              /**/)
     203                 :            : 
     204                 :            : /**
     205                 :            :  * @brief Loop over rbtree with implicit container field logic
     206                 :            :  *
     207                 :            :  * As for RB_FOR_EACH(), but "node" can have an arbitrary type
     208                 :            :  * containing a struct rbnode.
     209                 :            :  *
     210                 :            :  * @param tree A pointer to a struct rbtree to walk
     211                 :            :  * @param node The symbol name of a local iterator
     212                 :            :  * @param field The field name of a struct rbnode inside node
     213                 :            :  */
     214                 :            : #define RB_FOR_EACH_CONTAINER(tree, node, field)                           \
     215                 :            :         for (struct _rb_foreach __f = _RB_FOREACH_INIT(tree, node);        \
     216                 :            :                         ({struct rbnode *n = z_rb_foreach_next(tree, &__f); \
     217                 :            :                          node = n ? CONTAINER_OF(n, __typeof__(*(node)),   \
     218                 :            :                                          field) : NULL; }) != NULL;        \
     219                 :            :                          /**/)
     220                 :            : 
     221                 :            : /** @} */
     222                 :            : 
     223                 :            : #endif /* ZEPHYR_INCLUDE_SYS_RB_H_ */

Generated by: LCOV version 1.14