This source file includes following definitions.
- phpdbg_btree_init
- phpdbg_btree_find
- phpdbg_btree_find_closest
- phpdbg_btree_find_between
- phpdbg_btree_next
- phpdbg_btree_insert_or_update
- phpdbg_btree_delete
- phpdbg_btree_branch_dump
- phpdbg_btree_dump
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 #include "phpdbg_btree.h"
22 #include "phpdbg.h"
23
24 #define CHOOSE_BRANCH(n) \
25 branch = branch->branches[!!(n)];
26
27 #ifdef _Win32
28 # define emalloc malloc
29 # define efree free
30 #endif
31
32
33 void phpdbg_btree_init(phpdbg_btree *tree, zend_ulong depth) {
34 tree->depth = depth;
35 tree->branch = NULL;
36 tree->count = 0;
37 }
38
39 phpdbg_btree_result *phpdbg_btree_find(phpdbg_btree *tree, zend_ulong idx) {
40 phpdbg_btree_branch *branch = tree->branch;
41 int i = tree->depth - 1;
42
43 if (branch == NULL) {
44 return NULL;
45 }
46
47 do {
48 if ((idx >> i) % 2 == 1) {
49 if (branch->branches[1]) {
50 CHOOSE_BRANCH(1);
51 } else {
52 return NULL;
53 }
54 } else {
55 if (branch->branches[0]) {
56 CHOOSE_BRANCH(0);
57 } else {
58 return NULL;
59 }
60 }
61 } while (i--);
62
63 return &branch->result;
64 }
65
66 phpdbg_btree_result *phpdbg_btree_find_closest(phpdbg_btree *tree, zend_ulong idx) {
67 phpdbg_btree_branch *branch = tree->branch;
68 int i = tree->depth - 1, last_superior_i = -1;
69
70 if (branch == NULL) {
71 return NULL;
72 }
73
74
75 do {
76 if ((idx >> i) % 2 == 0) {
77 if (branch->branches[0]) {
78 CHOOSE_BRANCH(0);
79
80 } else {
81
82 if (last_superior_i == -1) {
83
84 return NULL;
85 }
86
87 branch = tree->branch;
88 i = tree->depth - 1;
89
90 do {
91 CHOOSE_BRANCH((idx >> i) % 2 == 1 && branch->branches[1]);
92 } while (--i > last_superior_i);
93
94 CHOOSE_BRANCH(0);
95
96 while (i--) {
97 CHOOSE_BRANCH(branch->branches[1]);
98 }
99 break;
100 }
101
102 } else {
103 if (branch->branches[1]) {
104 if (branch->branches[0]) {
105 last_superior_i = i;
106 }
107 CHOOSE_BRANCH(1);
108 } else {
109 CHOOSE_BRANCH(0);
110 while (i--) {
111 CHOOSE_BRANCH(branch->branches[1]);
112 }
113 break;
114 }
115 }
116 } while (i--);
117
118 return &branch->result;
119 }
120
121 phpdbg_btree_position phpdbg_btree_find_between(phpdbg_btree *tree, zend_ulong lower_idx, zend_ulong higher_idx) {
122 phpdbg_btree_position pos;
123
124 pos.tree = tree;
125 pos.end = lower_idx;
126 pos.cur = higher_idx;
127
128 return pos;
129 }
130
131 phpdbg_btree_result *phpdbg_btree_next(phpdbg_btree_position *pos) {
132 phpdbg_btree_result *result = phpdbg_btree_find_closest(pos->tree, pos->cur);
133
134 if (result == NULL || result->idx < pos->end) {
135 return NULL;
136 }
137
138 pos->cur = result->idx - 1;
139
140 return result;
141 }
142
143 int phpdbg_btree_insert_or_update(phpdbg_btree *tree, zend_ulong idx, void *ptr, int flags) {
144 int i = tree->depth - 1;
145 phpdbg_btree_branch **branch = &tree->branch;
146
147 do {
148 if (*branch == NULL) {
149 break;
150 }
151 branch = &(*branch)->branches[(idx >> i) % 2];
152 } while (i--);
153
154 if (*branch == NULL) {
155 if (!(flags & PHPDBG_BTREE_INSERT)) {
156 return FAILURE;
157 }
158
159 {
160 phpdbg_btree_branch *memory = *branch = emalloc((i + 2) * sizeof(phpdbg_btree_branch));
161 do {
162 (*branch)->branches[!((idx >> i) % 2)] = NULL;
163 branch = &(*branch)->branches[(idx >> i) % 2];
164 *branch = ++memory;
165 } while (i--);
166 tree->count++;
167 }
168 } else if (!(flags & PHPDBG_BTREE_UPDATE)) {
169 return FAILURE;
170 }
171
172 (*branch)->result.idx = idx;
173 (*branch)->result.ptr = ptr;
174
175 return SUCCESS;
176 }
177
178 int phpdbg_btree_delete(phpdbg_btree *tree, zend_ulong idx) {
179 int i = tree->depth;
180 phpdbg_btree_branch *branch = tree->branch;
181 int i_last_dual_branch = -1, last_dual_branch_branch;
182 phpdbg_btree_branch *last_dual_branch = NULL;
183
184 goto check_branch_existence;
185 do {
186 if (branch->branches[0] && branch->branches[1]) {
187 last_dual_branch = branch;
188 i_last_dual_branch = i;
189 last_dual_branch_branch = (idx >> i) % 2;
190 }
191 branch = branch->branches[(idx >> i) % 2];
192
193 check_branch_existence:
194 if (branch == NULL) {
195 return FAILURE;
196 }
197 } while (i--);
198
199 tree->count--;
200
201 if (i_last_dual_branch == -1) {
202 efree(tree->branch);
203 tree->branch = NULL;
204 } else {
205 if (last_dual_branch->branches[last_dual_branch_branch] == last_dual_branch + 1) {
206 phpdbg_btree_branch *original_branch = last_dual_branch->branches[!last_dual_branch_branch];
207
208 memcpy(last_dual_branch + 1, last_dual_branch->branches[!last_dual_branch_branch], (i_last_dual_branch + 1) * sizeof(phpdbg_btree_branch));
209 efree(last_dual_branch->branches[!last_dual_branch_branch]);
210 last_dual_branch->branches[!last_dual_branch_branch] = last_dual_branch + 1;
211
212 branch = last_dual_branch->branches[!last_dual_branch_branch];
213 for (i = i_last_dual_branch; i--;) {
214 branch = (branch->branches[branch->branches[1] == ++original_branch] = last_dual_branch + i_last_dual_branch - i + 1);
215 }
216 } else {
217 efree(last_dual_branch->branches[last_dual_branch_branch]);
218 }
219
220 last_dual_branch->branches[last_dual_branch_branch] = NULL;
221 }
222
223 return SUCCESS;
224 }
225
226 void phpdbg_btree_branch_dump(phpdbg_btree_branch *branch, zend_ulong depth) {
227 if (branch) {
228 if (depth--) {
229 phpdbg_btree_branch_dump(branch->branches[0], depth);
230 phpdbg_btree_branch_dump(branch->branches[1], depth);
231 } else {
232 fprintf(stderr, "%p: %p\n", (void *) branch->result.idx, branch->result.ptr);
233 }
234 }
235 }
236
237 void phpdbg_btree_dump(phpdbg_btree *tree) {
238 phpdbg_btree_branch_dump(tree->branch, tree->depth);
239 }