drivers/bus/dpaa/include/dpaa_rbtree.h

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright 2017 NXP.
   5  *
   6  *   Redistribution and use in source and binary forms, with or without
   7  *   modification, are permitted provided that the following conditions
   8  *   are met:
   9  *
  10  *     * Redistributions of source code must retain the above copyright
  11  *       notice, this list of conditions and the following disclaimer.
  12  *     * Redistributions in binary form must reproduce the above copyright
  13  *       notice, this list of conditions and the following disclaimer in
  14  *       the documentation and/or other materials provided with the
  15  *       distribution.
  16  *     * Neither the name of NXP nor the names of its
  17  *       contributors may be used to endorse or promote products derived
  18  *       from this software without specific prior written permission.
  19  *
  20  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  22  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  23  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  24  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  25  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  26  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  27  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  28  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  29  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  30  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  */
  32
  33 #ifndef __DPAA_RBTREE_H
  34 #define __DPAA_RBTREE_H
  35
  36 #include <rte_common.h>
  37 /************/
  38 /* RB-trees */
  39 /************/
  40
  41 /* Linux has a good RB-tree implementation, that we can't use (GPL). It also has
  42  * a flat/hooked-in interface that virtually requires license-contamination in
  43  * order to write a caller-compatible implementation. Instead, I've created an
  44  * RB-tree encapsulation on top of linux's primitives (it does some of the work
  45  * the client logic would normally do), and this gives us something we can
  46  * reimplement on LWE. Unfortunately there's no good+free RB-tree
  47  * implementations out there that are license-compatible and "flat" (ie. no
  48  * dynamic allocation). I did find a malloc-based one that I could convert, but
  49  * that will be a task for later on. For now, LWE's RB-tree is implemented using
  50  * an ordered linked-list.
  51  *
  52  * Note, the only linux-esque type is "struct rb_node", because it's used
  53  * statically in the exported header, so it can't be opaque. Our version doesn't
  54  * include a "rb_parent_color" field because we're doing linked-list instead of
  55  * a true rb-tree.
  56  */
  57
  58 struct rb_node {
  59         struct rb_node *prev, *next;
  60 };
  61
  62 struct dpa_rbtree {
  63         struct rb_node *head, *tail;
  64 };
  65
  66 #define DPAA_RBTREE { NULL, NULL }
  67 static inline void dpa_rbtree_init(struct dpa_rbtree *tree)
  68 {
  69         tree->head = tree->tail = NULL;
  70 }
  71
  72 #define QMAN_NODE2OBJ(ptr, type, node_field) \
  73         (type *)((char *)ptr - offsetof(type, node_field))
  74
  75 #define IMPLEMENT_DPAA_RBTREE(name, type, node_field, val_field) \
  76 static inline int name##_push(struct dpa_rbtree *tree, type *obj) \
  77 { \
  78         struct rb_node *node = tree->head; \
  79         if (!node) { \
  80                 tree->head = tree->tail = &obj->node_field; \
  81                 obj->node_field.prev = obj->node_field.next = NULL; \
  82                 return 0; \
  83         } \
  84         while (node) { \
  85                 type *item = QMAN_NODE2OBJ(node, type, node_field); \
  86                 if (obj->val_field == item->val_field) \
  87                         return -EBUSY; \
  88                 if (obj->val_field < item->val_field) { \
  89                         if (tree->head == node) \
  90                                 tree->head = &obj->node_field; \
  91                         else \
  92                                 node->prev->next = &obj->node_field; \
  93                         obj->node_field.prev = node->prev; \
  94                         obj->node_field.next = node; \
  95                         node->prev = &obj->node_field; \
  96                         return 0; \
  97                 } \
  98                 node = node->next; \
  99         } \
 100         obj->node_field.prev = tree->tail; \
 101         obj->node_field.next = NULL; \
 102         tree->tail->next = &obj->node_field; \
 103         tree->tail = &obj->node_field; \
 104         return 0; \
 105 } \
 106 static inline void name##_del(struct dpa_rbtree *tree, type *obj) \
 107 { \
 108         if (tree->head == &obj->node_field) { \
 109                 if (tree->tail == &obj->node_field) \
 110                         /* Only item in the list */ \
 111                         tree->head = tree->tail = NULL; \
 112                 else { \
 113                         /* Is the head, next != NULL */ \
 114                         tree->head = tree->head->next; \
 115                         tree->head->prev = NULL; \
 116                 } \
 117         } else { \
 118                 if (tree->tail == &obj->node_field) { \
 119                         /* Is the tail, prev != NULL */ \
 120                         tree->tail = tree->tail->prev; \
 121                         tree->tail->next = NULL; \
 122                 } else { \
 123                         /* Is neither the head nor the tail */ \
 124                         obj->node_field.prev->next = obj->node_field.next; \
 125                         obj->node_field.next->prev = obj->node_field.prev; \
 126                 } \
 127         } \
 128 } \
 129 static inline type *name##_find(struct dpa_rbtree *tree, u32 val) \
 130 { \
 131         struct rb_node *node = tree->head; \
 132         while (node) { \
 133                 type *item = QMAN_NODE2OBJ(node, type, node_field); \
 134                 if (val == item->val_field) \
 135                         return item; \
 136                 if (val < item->val_field) \
 137                         return NULL; \
 138                 node = node->next; \
 139         } \
 140         return NULL; \
 141 }
 142
 143 #endif /* __DPAA_RBTREE_H */