1 /* SPDX-License-Identifier: BSD-3-Clause
7 #ifndef __DPAA_RBTREE_H
8 #define __DPAA_RBTREE_H
10 #include <rte_common.h>
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.
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
33 struct rb_node *prev, *next;
37 struct rb_node *head, *tail;
40 #define DPAA_RBTREE { NULL, NULL }
41 static inline void dpa_rbtree_init(struct dpa_rbtree *tree)
43 tree->head = tree->tail = NULL;
46 #define QMAN_NODE2OBJ(ptr, type, node_field) \
47 (type *)((char *)ptr - offsetof(type, node_field))
49 #define IMPLEMENT_DPAA_RBTREE(name, type, node_field, val_field) \
50 static inline int name##_push(struct dpa_rbtree *tree, type *obj) \
52 struct rb_node *node = tree->head; \
54 tree->head = tree->tail = &obj->node_field; \
55 obj->node_field.prev = obj->node_field.next = NULL; \
59 type *item = QMAN_NODE2OBJ(node, type, node_field); \
60 if (obj->val_field == item->val_field) \
62 if (obj->val_field < item->val_field) { \
63 if (tree->head == node) \
64 tree->head = &obj->node_field; \
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; \
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; \
80 static inline void name##_del(struct dpa_rbtree *tree, type *obj) \
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; \
87 /* Is the head, next != NULL */ \
88 tree->head = tree->head->next; \
89 tree->head->prev = NULL; \
92 if (tree->tail == &obj->node_field) { \
93 /* Is the tail, prev != NULL */ \
94 tree->tail = tree->tail->prev; \
95 tree->tail->next = NULL; \
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; \
103 static inline type *name##_find(struct dpa_rbtree *tree, u32 val) \
105 struct rb_node *node = tree->head; \
107 type *item = QMAN_NODE2OBJ(node, type, node_field); \
108 if (val == item->val_field) \
110 if (val < item->val_field) \
117 #endif /* __DPAA_RBTREE_H */