1 /*
2 +----------------------------------------------------------------------+
3 | Copyright (c) The PHP Group |
4 +----------------------------------------------------------------------+
5 | This source file is subject to version 3.01 of the PHP license, |
6 | that is bundled with this package in the file LICENSE, and is |
7 | available through the world-wide-web at the following url: |
8 | https://www.php.net/license/3_01.txt |
9 | If you did not receive a copy of the PHP license and are unable to |
10 | obtain it through the world-wide-web, please send a note to |
11 | license@php.net so we can mail you a copy immediately. |
12 +----------------------------------------------------------------------+
13 | Authors: Felipe Pena <felipe@php.net> |
14 | Authors: Joe Watkins <joe.watkins@live.co.uk> |
15 | Authors: Bob Weinand <bwoebi@php.net> |
16 +----------------------------------------------------------------------+
17 */
18
19 #include "phpdbg_btree.h"
20 #include "phpdbg.h"
21
22 #define CHOOSE_BRANCH(n) \
23 branch = branch->branches[!!(n)];
24
25 #ifdef _Win32
26 # undef pemalloc
27 # undef pefree
28 # define pemalloc(size, persistent) malloc(size)
29 # define pefree(ptr, persistent) free(ptr)
30 #endif
31
32 /* depth in bits */
phpdbg_btree_init(phpdbg_btree * tree,zend_ulong depth)33 void phpdbg_btree_init(phpdbg_btree *tree, zend_ulong depth) {
34 tree->depth = depth;
35 tree->branch = NULL;
36 tree->persistent = 0;
37 tree->count = 0;
38 }
39
phpdbg_btree_find(phpdbg_btree * tree,zend_ulong idx)40 phpdbg_btree_result *phpdbg_btree_find(phpdbg_btree *tree, zend_ulong idx) {
41 phpdbg_btree_branch *branch = tree->branch;
42 int i = tree->depth - 1;
43
44 if (branch == NULL) {
45 return NULL;
46 }
47
48 do {
49 if ((idx >> i) % 2 == 1) {
50 if (branch->branches[1]) {
51 CHOOSE_BRANCH(1);
52 } else {
53 return NULL;
54 }
55 } else {
56 if (branch->branches[0]) {
57 CHOOSE_BRANCH(0);
58 } else {
59 return NULL;
60 }
61 }
62 } while (i--);
63
64 return &branch->result;
65 }
66
phpdbg_btree_find_closest(phpdbg_btree * tree,zend_ulong idx)67 phpdbg_btree_result *phpdbg_btree_find_closest(phpdbg_btree *tree, zend_ulong idx) {
68 phpdbg_btree_branch *branch = tree->branch;
69 int i = tree->depth - 1, last_superior_i = -1;
70
71 if (branch == NULL) {
72 return NULL;
73 }
74
75 /* find nearest watchpoint */
76 do {
77 if ((idx >> i) % 2 == 0) {
78 if (branch->branches[0]) {
79 CHOOSE_BRANCH(0);
80 /* an impossible branch was found if: */
81 } else {
82 /* there's no lower branch than idx */
83 if (last_superior_i == -1) {
84 /* failure */
85 return NULL;
86 }
87 /* reset state */
88 branch = tree->branch;
89 i = tree->depth - 1;
90 /* follow branch according to bits in idx until the last lower branch before the impossible branch */
91 do {
92 CHOOSE_BRANCH((idx >> i) % 2 == 1 && branch->branches[1]);
93 } while (--i > last_superior_i);
94 /* use now the lower branch of which we can be sure that it contains only branches lower than idx */
95 CHOOSE_BRANCH(0);
96 /* and choose the highest possible branch in the branch containing only branches lower than idx */
97 while (i--) {
98 CHOOSE_BRANCH(branch->branches[1]);
99 }
100 break;
101 }
102 /* follow branch according to bits in idx until having found an impossible branch */
103 } else {
104 if (branch->branches[1]) {
105 if (branch->branches[0]) {
106 last_superior_i = i;
107 }
108 CHOOSE_BRANCH(1);
109 } else {
110 CHOOSE_BRANCH(0);
111 while (i--) {
112 CHOOSE_BRANCH(branch->branches[1]);
113 }
114 break;
115 }
116 }
117 } while (i--);
118
119 return &branch->result;
120 }
121
phpdbg_btree_find_between(phpdbg_btree * tree,zend_ulong lower_idx,zend_ulong higher_idx)122 phpdbg_btree_position phpdbg_btree_find_between(phpdbg_btree *tree, zend_ulong lower_idx, zend_ulong higher_idx) {
123 phpdbg_btree_position pos;
124
125 pos.tree = tree;
126 pos.end = lower_idx;
127 pos.cur = higher_idx;
128
129 return pos;
130 }
131
phpdbg_btree_next(phpdbg_btree_position * pos)132 phpdbg_btree_result *phpdbg_btree_next(phpdbg_btree_position *pos) {
133 phpdbg_btree_result *result = phpdbg_btree_find_closest(pos->tree, pos->cur);
134
135 if (result == NULL || result->idx < pos->end) {
136 return NULL;
137 }
138
139 pos->cur = result->idx - 1;
140
141 return result;
142 }
143
phpdbg_btree_insert_or_update(phpdbg_btree * tree,zend_ulong idx,void * ptr,int flags)144 int phpdbg_btree_insert_or_update(phpdbg_btree *tree, zend_ulong idx, void *ptr, int flags) {
145 int i = tree->depth - 1;
146 phpdbg_btree_branch **branch = &tree->branch;
147
148 do {
149 if (*branch == NULL) {
150 break;
151 }
152 branch = &(*branch)->branches[(idx >> i) % 2];
153 } while (i--);
154
155 if (*branch == NULL) {
156 if (!(flags & PHPDBG_BTREE_INSERT)) {
157 return FAILURE;
158 }
159
160 {
161 phpdbg_btree_branch *memory = *branch = pemalloc((i + 2) * sizeof(phpdbg_btree_branch), tree->persistent);
162 do {
163 (*branch)->branches[!((idx >> i) % 2)] = NULL;
164 branch = &(*branch)->branches[(idx >> i) % 2];
165 *branch = ++memory;
166 } while (i--);
167 tree->count++;
168 }
169 } else if (!(flags & PHPDBG_BTREE_UPDATE)) {
170 return FAILURE;
171 }
172
173 (*branch)->result.idx = idx;
174 (*branch)->result.ptr = ptr;
175
176 return SUCCESS;
177 }
178
phpdbg_btree_delete(phpdbg_btree * tree,zend_ulong idx)179 int phpdbg_btree_delete(phpdbg_btree *tree, zend_ulong idx) {
180 int i = tree->depth;
181 phpdbg_btree_branch *branch = tree->branch;
182 int i_last_dual_branch = -1, last_dual_branch_branch;
183 phpdbg_btree_branch *last_dual_branch = NULL;
184
185 goto check_branch_existence;
186 do {
187 if (branch->branches[0] && branch->branches[1]) {
188 last_dual_branch = branch;
189 i_last_dual_branch = i;
190 last_dual_branch_branch = (idx >> i) % 2;
191 }
192 branch = branch->branches[(idx >> i) % 2];
193
194 check_branch_existence:
195 if (branch == NULL) {
196 return FAILURE;
197 }
198 } while (i--);
199
200 tree->count--;
201
202 if (i_last_dual_branch == -1) {
203 pefree(tree->branch, tree->persistent);
204 tree->branch = NULL;
205 } else {
206 if (last_dual_branch->branches[last_dual_branch_branch] == last_dual_branch + 1) {
207 phpdbg_btree_branch *original_branch = last_dual_branch->branches[!last_dual_branch_branch];
208
209 memcpy(last_dual_branch + 1, last_dual_branch->branches[!last_dual_branch_branch], (i_last_dual_branch + 1) * sizeof(phpdbg_btree_branch));
210 pefree(last_dual_branch->branches[!last_dual_branch_branch], tree->persistent);
211 last_dual_branch->branches[!last_dual_branch_branch] = last_dual_branch + 1;
212
213 branch = last_dual_branch->branches[!last_dual_branch_branch];
214 for (i = i_last_dual_branch; i--;) {
215 branch = (branch->branches[branch->branches[1] == ++original_branch] = last_dual_branch + i_last_dual_branch - i + 1);
216 }
217 } else {
218 pefree(last_dual_branch->branches[last_dual_branch_branch], tree->persistent);
219 }
220
221 last_dual_branch->branches[last_dual_branch_branch] = NULL;
222 }
223
224 return SUCCESS;
225 }
226
phpdbg_btree_clean_recursive(phpdbg_btree_branch * branch,zend_ulong depth,bool persistent)227 void phpdbg_btree_clean_recursive(phpdbg_btree_branch *branch, zend_ulong depth, bool persistent) {
228 phpdbg_btree_branch *start = branch;
229 while (depth--) {
230 bool use_branch = branch + 1 == branch->branches[0];
231 if (branch->branches[use_branch]) {
232 phpdbg_btree_clean_recursive(branch->branches[use_branch], depth, persistent);
233 }
234 }
235
236 pefree(start, persistent);
237 }
238
phpdbg_btree_clean(phpdbg_btree * tree)239 void phpdbg_btree_clean(phpdbg_btree *tree) {
240 if (tree->branch) {
241 phpdbg_btree_clean_recursive(tree->branch, tree->depth, tree->persistent);
242 tree->branch = NULL;
243 tree->count = 0;
244 }
245 }
246
phpdbg_btree_branch_dump(phpdbg_btree_branch * branch,zend_ulong depth)247 void phpdbg_btree_branch_dump(phpdbg_btree_branch *branch, zend_ulong depth) {
248 if (branch) {
249 if (depth--) {
250 phpdbg_btree_branch_dump(branch->branches[0], depth);
251 phpdbg_btree_branch_dump(branch->branches[1], depth);
252 } else {
253 fprintf(stderr, "%p: %p\n", (void *) branch->result.idx, branch->result.ptr);
254 }
255 }
256 }
257
phpdbg_btree_dump(phpdbg_btree * tree)258 void phpdbg_btree_dump(phpdbg_btree *tree) {
259 phpdbg_btree_branch_dump(tree->branch, tree->depth);
260 }
261
