1
2
3
4
5
6
7#ifndef __DPAA_RBTREE_H
8#define __DPAA_RBTREE_H
9
10#include <rte_common.h>
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32struct rb_node {
33 struct rb_node *prev, *next;
34};
35
36struct dpa_rbtree {
37 struct rb_node *head, *tail;
38};
39
40#define DPAA_RBTREE { NULL, NULL }
41static 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) \
50static 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} \
80static 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 \
85 tree->head = tree->tail = NULL; \
86 else { \
87 \
88 tree->head = tree->head->next; \
89 tree->head->prev = NULL; \
90 } \
91 } else { \
92 if (tree->tail == &obj->node_field) { \
93 \
94 tree->tail = tree->tail->prev; \
95 tree->tail->next = NULL; \
96 } else { \
97 \
98 obj->node_field.prev->next = obj->node_field.next; \
99 obj->node_field.next->prev = obj->node_field.prev; \
100 } \
101 } \
102} \
103static 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
118