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