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