drivers/bus/dpaa/include/dpaa_rbtree.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  *
   3  *   Copyright 2017 NXP
   4  *
   5  */
   6
   7 #ifndef __DPAA_RBTREE_H
   8 #define __DPAA_RBTREE_H
   9
  10 #include <rte_common.h>
  11 /************/
  12 /* RB-trees */
  13 /************/
  14
  15 /* Linux has a good RB-tree implementation, that we can't use (GPL). It also has
  16  * a flat/hooked-in interface that virtually requires license-contamination in
  17  * order to write a caller-compatible implementation. Instead, I've created an
  18  * RB-tree encapsulation on top of linux's primitives (it does some of the work
  19  * the client logic would normally do), and this gives us something we can
  20  * reimplement on LWE. Unfortunately there's no good+free RB-tree
  21  * implementations out there that are license-compatible and "flat" (ie. no
  22  * dynamic allocation). I did find a malloc-based one that I could convert, but
  23  * that will be a task for later on. For now, LWE's RB-tree is implemented using
  24  * an ordered linked-list.
  25  *
  26  * Note, the only linux-esque type is "struct rb_node", because it's used
  27  * statically in the exported header, so it can't be opaque. Our version doesn't
  28  * include a "rb_parent_color" field because we're doing linked-list instead of
  29  * a true rb-tree.
  30  */
  31
  32 struct rb_node {
  33         struct rb_node *prev, *next;
  34 };
  35
  36 struct dpa_rbtree {
  37         struct rb_node *head, *tail;
  38 };
  39
  40 #define DPAA_RBTREE { NULL, NULL }
  41 static inline void dpa_rbtree_init(struct dpa_rbtree *tree)
  42 {
  43         tree->head = tree->tail = NULL;
  44 }
  45
  46 #define QMAN_NODE2OBJ(ptr, type, node_field) \
  47         (type *)((char *)ptr - offsetof(type, node_field))
  48
  49 #define IMPLEMENT_DPAA_RBTREE(name, type, node_field, val_field) \
  50 static inline int name##_push(struct dpa_rbtree *tree, type *obj) \
  51 { \
  52         struct rb_node *node = tree->head; \
  53         if (!node) { \
  54                 tree->head = tree->tail = &obj->node_field; \
  55                 obj->node_field.prev = obj->node_field.next = NULL; \
  56                 return 0; \
  57         } \
  58         while (node) { \
  59                 type *item = QMAN_NODE2OBJ(node, type, node_field); \
  60                 if (obj->val_field == item->val_field) \
  61                         return -EBUSY; \
  62                 if (obj->val_field < item->val_field) { \
  63                         if (tree->head == node) \
  64                                 tree->head = &obj->node_field; \
  65                         else \
  66                                 node->prev->next = &obj->node_field; \
  67                         obj->node_field.prev = node->prev; \
  68                         obj->node_field.next = node; \
  69                         node->prev = &obj->node_field; \
  70                         return 0; \
  71                 } \
  72                 node = node->next; \
  73         } \
  74         obj->node_field.prev = tree->tail; \
  75         obj->node_field.next = NULL; \
  76         tree->tail->next = &obj->node_field; \
  77         tree->tail = &obj->node_field; \
  78         return 0; \
  79 } \
  80 static inline void name##_del(struct dpa_rbtree *tree, type *obj) \
  81 { \
  82         if (tree->head == &obj->node_field) { \
  83                 if (tree->tail == &obj->node_field) \
  84                         /* Only item in the list */ \
  85                         tree->head = tree->tail = NULL; \
  86                 else { \
  87                         /* Is the head, next != NULL */ \
  88                         tree->head = tree->head->next; \
  89                         tree->head->prev = NULL; \
  90                 } \
  91         } else { \
  92                 if (tree->tail == &obj->node_field) { \
  93                         /* Is the tail, prev != NULL */ \
  94                         tree->tail = tree->tail->prev; \
  95                         tree->tail->next = NULL; \
  96                 } else { \
  97                         /* Is neither the head nor the tail */ \
  98                         obj->node_field.prev->next = obj->node_field.next; \
  99                         obj->node_field.next->prev = obj->node_field.prev; \
 100                 } \
 101         } \
 102 } \
 103 static inline type *name##_find(struct dpa_rbtree *tree, u32 val) \
 104 { \
 105         struct rb_node *node = tree->head; \
 106         while (node) { \
 107                 type *item = QMAN_NODE2OBJ(node, type, node_field); \
 108                 if (val == item->val_field) \
 109                         return item; \
 110                 if (val < item->val_field) \
 111                         return NULL; \
 112                 node = node->next; \
 113         } \
 114         return NULL; \
 115 }
 116
 117 #endif /* __DPAA_RBTREE_H */