xref: /PHP-8.2/sapi/phpdbg/phpdbg_btree.c (revision 01b3fc03)
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