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 */ 118