1 /*
2 * Copyright (C) by Argonne National Laboratory
3 * See COPYRIGHT in top-level directory
4 */
5
6 #ifndef MPL_GAVL_H_INCLUDED
7 #define MPL_GAVL_H_INCLUDED
8
9 typedef void *MPL_gavl_tree_t;
10
11 int MPL_gavl_tree_create(void (*free_fn) (void *), MPL_gavl_tree_t * gavl_tree);
12 int MPL_gavl_tree_insert(MPL_gavl_tree_t gavl_tree, const void *addr, uintptr_t len,
13 const void *val);
14 int MPL_gavl_tree_destory(MPL_gavl_tree_t gavl_tree);
15 int MPL_gavl_tree_delete_range(MPL_gavl_tree_t gavl_tree, const void *addr, uintptr_t len);
16 int MPL_gavl_tree_delete_start_addr(MPL_gavl_tree_t gavl_tree, const void *addr);
17 MPL_STATIC_INLINE_PREFIX int MPL_gavl_tree_search(MPL_gavl_tree_t gavl_tree, const void *addr,
18 uintptr_t len, void **val);
19
20 /*
21 * We assume AVL tree height will not exceed 64. AVL tree with 64 height in worst case
22 * can contain 27777890035287 nodes which is far enough for current applications.
23 * The idea to compute worse case nodes is as follows:
24 * In worse case, AVL tree with height h_p should have h_p - 1 height left child and
25 * h_p - 2 height right child; therefore, the worse case nodes N(h_p) = N(h_p - 1) + N(h_p - 2) + 1.
26 * Since we know N(1) = 1 and N(2) = 2, we can use iteration to compute N(64) = 27777890035287.
27 */
28 #define MPLI_GAVL_MAX_STACK_SIZE 64
29
30 enum {
31 MPLI_GAVL_SEARCH_LEFT,
32 MPLI_GAVL_SEARCH_RIGHT,
33 MPLI_GAVL_BUFFER_MATCH,
34 MPLI_GAVL_NO_BUFFER_MATCH
35 };
36
37 enum {
38 /* range search */
39 MPLI_GAVL_SUBSET_SEARCH,
40 MPLI_GAVL_INTERSECTION_SEARCH,
41 /* address search */
42 MPLI_GAVL_START_ADDR_SEARCH
43 };
44
45 typedef struct MPLI_gavl_tree_node {
46 union {
47 struct {
48 struct MPLI_gavl_tree_node *parent;
49 struct MPLI_gavl_tree_node *left;
50 struct MPLI_gavl_tree_node *right;
51 } s;
52 struct MPLI_gavl_tree_node *next;
53 } u;
54 uintptr_t height;
55 uintptr_t addr;
56 uintptr_t len;
57 const void *val;
58 } MPLI_gavl_tree_node_s;
59
60 typedef struct MPLI_gavl_tree {
61 MPLI_gavl_tree_node_s *root;
62 void (*gavl_free_fn) (void *);
63 /* internal stack structure. used to track the traverse trace for
64 * tree rebalance at node insertion or deletion */
65 MPLI_gavl_tree_node_s *stack[MPLI_GAVL_MAX_STACK_SIZE];
66 int stack_sp;
67 /* cur_node points to the starting node of tree rebalance */
68 MPLI_gavl_tree_node_s *cur_node;
69 /* store nodes that are removed from tree but haven't been freed */
70 MPLI_gavl_tree_node_s *remove_list;
71 } MPLI_gavl_tree_s;
72
MPLI_gavl_subset_cmp_func(MPLI_gavl_tree_node_s * tnode,uintptr_t ustart,uintptr_t len)73 MPL_STATIC_INLINE_PREFIX int MPLI_gavl_subset_cmp_func(MPLI_gavl_tree_node_s * tnode,
74 uintptr_t ustart, uintptr_t len)
75 {
76 int cmp_ret;
77 uintptr_t uend = ustart + len;
78 uintptr_t tstart = tnode->addr;
79 uintptr_t tend = tnode->addr + tnode->len;
80
81 if (tstart <= ustart && uend <= tend)
82 cmp_ret = MPLI_GAVL_BUFFER_MATCH;
83 else if (ustart < tstart)
84 cmp_ret = MPLI_GAVL_SEARCH_LEFT;
85 else
86 cmp_ret = MPLI_GAVL_SEARCH_RIGHT;
87
88 return cmp_ret;
89 }
90
MPLI_gavl_intersect_cmp_func(MPLI_gavl_tree_node_s * tnode,uintptr_t ustart,uintptr_t len)91 MPL_STATIC_INLINE_PREFIX int MPLI_gavl_intersect_cmp_func(MPLI_gavl_tree_node_s * tnode,
92 uintptr_t ustart, uintptr_t len)
93 {
94 int cmp_ret;
95 uintptr_t uend = ustart + len;
96 uintptr_t tstart = tnode->addr;
97 uintptr_t tend = tnode->addr + tnode->len;
98
99 if (uend <= tstart)
100 cmp_ret = MPLI_GAVL_SEARCH_LEFT;
101 else if (tend <= ustart)
102 cmp_ret = MPLI_GAVL_SEARCH_RIGHT;
103 else
104 cmp_ret = MPLI_GAVL_BUFFER_MATCH;
105
106 return cmp_ret;
107 }
108
MPLI_gavl_start_addr_cmp_func(MPLI_gavl_tree_node_s * tnode,uintptr_t ustart)109 MPL_STATIC_INLINE_PREFIX int MPLI_gavl_start_addr_cmp_func(MPLI_gavl_tree_node_s * tnode,
110 uintptr_t ustart)
111 {
112 int cmp_ret;
113 uintptr_t tstart = tnode->addr;
114
115 if (tstart == ustart)
116 cmp_ret = MPLI_GAVL_BUFFER_MATCH;
117 else if (ustart < tstart)
118 cmp_ret = MPLI_GAVL_SEARCH_LEFT;
119 else
120 cmp_ret = MPLI_GAVL_SEARCH_RIGHT;
121
122 return cmp_ret;
123 }
124
125 /*
126 * MPL_gavl_tree_search
127 * Description: search a node that matches input key (addr, len) and return corresponding
128 * buffer object. This function is not thread-safe.
129 * Parameters:
130 * gavl_tree - (IN) gavl tree object
131 * addr - (IN) input buffer starting addr
132 * len - (IN) input buffer length
133 * val - (OUT) matched buffer object
134 */
MPL_gavl_tree_search(MPL_gavl_tree_t gavl_tree,const void * addr,uintptr_t len,void ** val)135 MPL_STATIC_INLINE_PREFIX int MPL_gavl_tree_search(MPL_gavl_tree_t gavl_tree, const void *addr,
136 uintptr_t len, void **val)
137 {
138 int mpl_err = MPL_SUCCESS;
139 MPLI_gavl_tree_node_s *cur_node;
140 MPLI_gavl_tree_s *tree_ptr = (MPLI_gavl_tree_s *) gavl_tree;
141
142 *val = NULL;
143 cur_node = tree_ptr->root;
144 while (cur_node) {
145 int cmp_ret = MPLI_gavl_subset_cmp_func(cur_node, (uintptr_t) addr, len);
146 if (cmp_ret == MPLI_GAVL_BUFFER_MATCH) {
147 *val = (void *) cur_node->val;
148 break;
149 } else if (cmp_ret == MPLI_GAVL_SEARCH_LEFT) {
150 cur_node = cur_node->u.s.left;
151 } else {
152 cur_node = cur_node->u.s.right;
153 }
154 }
155
156 return mpl_err;
157 }
158
159 #endif /* MPL_GAVL_H_INCLUDED */
160