1#include <mdb/mdb_tree.h> 2#include <mdb/mdb.h> 3#include <cap_predicates.h> 4#include <barrelfish_kpi/capabilities.h> 5#include <barrelfish_kpi/capbits.h> 6#include <capabilities.h> 7#include <assert.h> 8#include <stdio.h> 9#include "old_mdb.h" 10 11#ifdef N 12#undef N 13#endif 14#define N(cte) (&(cte)->mdbnode) 15#ifdef C 16#undef C 17#endif 18#define C(cte) (&(cte)->cap) 19 20struct cte *old_start; 21 22void old_mdb_insert(struct cte *cte) 23{ 24 if (!old_start) { 25 old_start = cte; 26 N(cte)->left = cte; 27 N(cte)->right = cte; 28 return; 29 } 30 31 struct cte *curr = old_start; 32 while (true) { 33 int cmp = compare_caps(C(curr), C(cte), true); 34 assert(cmp != 0); // cte should not be in mdb yet 35 if (cmp >= 0) { 36 break; 37 } 38 curr = N(curr)->right; 39 if (curr == old_start) { 40 break; 41 } 42 } 43 44 N(cte)->left = N(curr)->left; 45 N(cte)->right = curr; 46 47 N(N(cte)->left)->right = cte; 48 N(N(cte)->right)->left = cte; 49} 50 51void old_mdb_remove(struct cte *cte) 52{ 53 if (N(cte)->right == cte) { 54 assert(cte == old_start); 55 old_start = N(cte)->right = N(cte)->left = NULL; 56 return; 57 } 58 if (cte == old_start) { 59 old_start = N(cte)->right; 60 } 61 62 N(N(cte)->right)->left = N(cte)->left; 63 N(N(cte)->left)->right = N(cte)->right; 64 65 N(cte)->right = N(cte)->left = NULL; 66} 67 68struct cte* old_mdb_predecessor(struct cte *cte) 69{ 70 return N(cte)->left; 71} 72 73struct cte* old_mdb_successor(struct cte *cte) 74{ 75 return N(cte)->right; 76} 77 78bool old_mdb_has_copies(struct cte *cte) 79{ 80 return (N(cte)->left != cte) 81 && (is_copy(C(N(cte)->left), C(cte)) 82 || is_copy(C(N(cte)->right), C(cte))); 83} 84 85bool old_mdb_has_descendants(struct cte *cte) 86{ 87 for (struct cte *curr = N(cte)->right; 88 curr != cte; 89 curr = N(curr)->right) 90 { 91 if (!is_copy(C(cte), C(curr))) { 92 return is_ancestor(C(curr), C(cte)); 93 } 94 } 95 return false; 96} 97 98bool old_mdb_has_ancestors(struct cte *cte) 99{ 100 for (struct cte *curr = N(cte)->left; 101 curr != cte; 102 curr = N(curr)->left) 103 { 104 int cmp = compare_caps(C(curr), C(cte), true); 105 if (cmp >= 0) { 106 return false; 107 } 108 if (is_ancestor(C(cte), C(curr))) { 109 return true; 110 } 111 } 112 return false; 113} 114