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