lib/mdb/mdb_tree.c

56 #define CHECK_INVARIANTS(root, cte, reach) \
58     if (mdb_is_reachable(root, cte) != reach) { \
59         panic("mdb_is_reachable(%p,%p) != %d", root, cte, reach); \
64 #define CHECK_INVARIANTS(root, cte, reach) ((void)0)
72 #define CHECK_INVARIANTS(root, cte, reach) \
74     if (mdb_is_reachable(root, cte) != reach) { \
75         panic("mdb_is_reachable(%p,%p) != %d", root, cte, reach); \
146     // set root
223     // Print a tree with root on the left, the smallest element at the top and the
301     // build expected end root for current node
313     // build expected end for current node. this is complex because the root
314     // acts as an address prefix, so only ends where the corresponding root is
318         // only consider current cte's end if its root is node->end_root
369 mdb_is_reachable(struct cte *root, struct cte *cte)
371     if (!root) {
374     if (root == cte) {
377     if (N(root)->left) {
378         if (mdb_is_reachable(N(root)->left, cte)) {
382     if (N(root)->right) {
383         if (mdb_is_reachable(N(root)->right, cte)) {
402     // build end root for current node
412     // build end address for current node. this is complex because the root
413     // acts as an address prefix, so only ends where the corresponding root is
417         // only consider current cte's end if its root is node->end_root
1008     // we have to perform a search through the tree from the root. This makes
1028     // we have perform a search through the tree from the root. This makes
1130 mdb_sub_find_range(mdb_root_t root, genpaddr_t address, size_t size,
1135 mdb_sub_find_range_merge(mdb_root_t root, genpaddr_t address, size_t size,
1146     int sub_ret = mdb_sub_find_range(root, address, size, max_precision, sub,
1178 mdb_sub_find_range(mdb_root_t root, genpaddr_t address, size_t size,
1190     if (N(current)->end_root < root) {
1194     if (N(current)->end_root == root && N(current)->end <= address) {
1208     if (current_root == root) {
1250         mdb_sub_find_range_merge(root, address, size, max_precision,
1259     if (N(current)->right && root >= current_root &&
1261         mdb_sub_find_range_merge(root, address, size, max_precision,
1277 mdb_find_range(mdb_root_t root, genpaddr_t address, gensize_t size,
1299     *result = mdb_sub_find_range(root, address, size, max_result, mdb_root, ret_node);