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
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 zend_bool had_alternative_branch = 0;
70
71 if (branch == NULL) {
72 return NULL;
73 }
74
75
76 do {
77
78 if (!had_alternative_branch && (idx >> i) % 2 == 0 && !branch->branches[0]) {
79
80 if (last_superior_i == -1) {
81
82 return NULL;
83 }
84
85 branch = tree->branch;
86 i = tree->depth - 1;
87
88 do {
89 CHOOSE_BRANCH((idx >> i) % 2 == 1 && branch->branches[1]);
90 } while (--i > last_superior_i);
91
92 CHOOSE_BRANCH(0);
93
94 while (i--) {
95 CHOOSE_BRANCH(branch->branches[1]);
96 }
97 break;
98 }
99
100 if (had_alternative_branch || (idx >> i) % 2 == 1) {
101 if (branch->branches[1]) {
102 if (branch->branches[0]) {
103 last_superior_i = i;
104 }
105 CHOOSE_BRANCH(1);
106 } else {
107 CHOOSE_BRANCH(0);
108 had_alternative_branch = 1;
109 }
110 } else {
111 CHOOSE_BRANCH(0);
112 }
113 } while (i--);
114
115 return &branch->result;
116 }
117
118 phpdbg_btree_position phpdbg_btree_find_between(phpdbg_btree *tree, zend_ulong lower_idx, zend_ulong higher_idx) {
119 phpdbg_btree_position pos;
120
121 pos.tree = tree;
122 pos.end = lower_idx;
123 pos.cur = higher_idx;
124
125 return pos;
126 }
127
128 phpdbg_btree_result *phpdbg_btree_next(phpdbg_btree_position *pos) {
129 phpdbg_btree_result *result = phpdbg_btree_find_closest(pos->tree, pos->cur);
130
131 if (result == NULL || result->idx < pos->end) {
132 return NULL;
133 }
134
135 pos->cur = result->idx - 1;
136
137 return result;
138 }
139
140 int phpdbg_btree_insert_or_update(phpdbg_btree *tree, zend_ulong idx, void *ptr, int flags) {
141 int i = tree->depth - 1;
142 phpdbg_btree_branch **branch = &tree->branch;
143
144 do {
145 if (*branch == NULL) {
146 break;
147 }
148 branch = &(*branch)->branches[(idx >> i) % 2];
149 } while (i--);
150
151 if (*branch == NULL) {
152 if (!(flags & PHPDBG_BTREE_INSERT)) {
153 return FAILURE;
154 }
155
156 {
157 phpdbg_btree_branch *memory = *branch = emalloc((i + 2) * sizeof(phpdbg_btree_branch));
158 do {
159 (*branch)->branches[!((idx >> i) % 2)] = NULL;
160 branch = &(*branch)->branches[(idx >> i) % 2];
161 *branch = ++memory;
162 } while (i--);
163 tree->count++;
164 }
165 } else if (!(flags & PHPDBG_BTREE_UPDATE)) {
166 return FAILURE;
167 }
168
169 (*branch)->result.idx = idx;
170 (*branch)->result.ptr = ptr;
171
172 return SUCCESS;
173 }
174
175 int phpdbg_btree_delete(phpdbg_btree *tree, zend_ulong idx) {
176 int i = tree->depth;
177 phpdbg_btree_branch *branch = tree->branch;
178 int i_last_dual_branch = -1, last_dual_branch_branch;
179 phpdbg_btree_branch *last_dual_branch = NULL;
180
181 goto check_branch_existence;
182 do {
183 if (branch->branches[0] && branch->branches[1]) {
184 last_dual_branch = branch;
185 i_last_dual_branch = i;
186 last_dual_branch_branch = (idx >> i) % 2;
187 }
188 branch = branch->branches[(idx >> i) % 2];
189
190 check_branch_existence:
191 if (branch == NULL) {
192 return FAILURE;
193 }
194 } while (i--);
195
196 tree->count--;
197
198 if (i_last_dual_branch == -1) {
199 efree(tree->branch);
200 tree->branch = NULL;
201 } else {
202 if (last_dual_branch->branches[last_dual_branch_branch] == last_dual_branch + 1) {
203 phpdbg_btree_branch *original_branch = last_dual_branch->branches[!last_dual_branch_branch];
204
205 memcpy(last_dual_branch + 1, last_dual_branch->branches[!last_dual_branch_branch], (i_last_dual_branch + 1) * sizeof(phpdbg_btree_branch));
206 efree(last_dual_branch->branches[!last_dual_branch_branch]);
207 last_dual_branch->branches[!last_dual_branch_branch] = last_dual_branch + 1;
208
209 branch = last_dual_branch->branches[!last_dual_branch_branch];
210 for (i = i_last_dual_branch; i--;) {
211 branch = (branch->branches[branch->branches[1] == ++original_branch] = last_dual_branch + i_last_dual_branch - i + 1);
212 }
213 } else {
214 efree(last_dual_branch->branches[last_dual_branch_branch]);
215 }
216
217 last_dual_branch->branches[last_dual_branch_branch] = NULL;
218 }
219
220 return SUCCESS;
221 }