6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
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
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.
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.
33 #ifndef __DPAA_RBTREE_H
34 #define __DPAA_RBTREE_H
36 #include <rte_common.h>
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.
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
59 struct rb_node *prev, *next;
63 struct rb_node *head, *tail;
66 #define DPAA_RBTREE { NULL, NULL }
67 static inline void dpa_rbtree_init(struct dpa_rbtree *tree)
69 tree->head = tree->tail = NULL;
72 #define QMAN_NODE2OBJ(ptr, type, node_field) \
73 (type *)((char *)ptr - offsetof(type, node_field))
75 #define IMPLEMENT_DPAA_RBTREE(name, type, node_field, val_field) \
76 static inline int name##_push(struct dpa_rbtree *tree, type *obj) \
78 struct rb_node *node = tree->head; \
80 tree->head = tree->tail = &obj->node_field; \
81 obj->node_field.prev = obj->node_field.next = NULL; \
85 type *item = QMAN_NODE2OBJ(node, type, node_field); \
86 if (obj->val_field == item->val_field) \
88 if (obj->val_field < item->val_field) { \
89 if (tree->head == node) \
90 tree->head = &obj->node_field; \
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; \
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; \
106 static inline void name##_del(struct dpa_rbtree *tree, type *obj) \
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; \
113 /* Is the head, next != NULL */ \
114 tree->head = tree->head->next; \
115 tree->head->prev = NULL; \
118 if (tree->tail == &obj->node_field) { \
119 /* Is the tail, prev != NULL */ \
120 tree->tail = tree->tail->prev; \
121 tree->tail->next = NULL; \
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; \
129 static inline type *name##_find(struct dpa_rbtree *tree, u32 val) \
131 struct rb_node *node = tree->head; \
133 type *item = QMAN_NODE2OBJ(node, type, node_field); \
134 if (val == item->val_field) \
136 if (val < item->val_field) \
143 #endif /* __DPAA_RBTREE_H */