1 : /*
2 : * Copyright (c) 2012 The Native Client Authors. All rights reserved.
3 : * Use of this source code is governed by a BSD-style license that can be
4 : * found in the LICENSE file.
5 : */
6 :
7 : #define DEBUG_THIS 0
8 : /*
9 : * Define as 1 to get debugging output. Compiler's dead code
10 : * elimination should remove debug statements when defined as 0.
11 : */
12 :
13 : #include <stdio.h> /* tree print */
14 :
15 : #include "native_client/src/include/nacl_compiler_annotations.h"
16 : #include "native_client/src/shared/platform/nacl_log.h"
17 : #include "native_client/src/trusted/interval_multiset/nacl_interval_multiset.h"
18 : #include "native_client/src/trusted/interval_multiset/nacl_interval_range_tree.h"
19 : #include "native_client/src/trusted/interval_multiset/nacl_interval_range_tree_intern.h"
20 :
21 : struct NaClIntervalRangeTreeNode {
22 : struct NaClIntervalRangeTreeNode *left;
23 : struct NaClIntervalRangeTreeNode *right;
24 : int balance; /* AVL height balance: -1, 0, 1 */
25 :
26 : uint32_t value;
27 : /* the value at this interval end point */
28 :
29 : uint32_t value_containment_delta;
30 : /*
31 : * Each interval that uses |value| as the start point would
32 : * increment |value_containment_delta| by 1; and each range that
33 : * uses it as the end point would decrement it by 1. Can never be
34 : * negative, but may be zero, e.g., [x,y] [y,z] would make y's
35 : * value_containment_delta be zero. We cannot distinguish
36 : * [x,y][y,z] from [x1,y][x2,y][y,z1][y,z2] when looking at y.
37 : */
38 :
39 : uint32_t refcount;
40 : /*
41 : * We could keep right_delta and left_delta for counting the number
42 : * of ranges that end and start at this value respectively, but that
43 : * would require a subtraction whenever we re-computed range
44 : * information. Keeping a summed delta and a refcount simplifies
45 : * the updates, at the cost of a reduced maximum number of
46 : * (overlapped) ranges. If we didn't do either of the above, then
47 : * overlaps could cause the summed delta to be zero after a delete,
48 : * and we cannot determine whether we can actually remove the tree
49 : * node or not.
50 : */
51 :
52 : /*
53 : * Cumulative information about the subtree rooted at this node.
54 : */
55 : uint32_t range_left;
56 : uint32_t range_right;
57 : /* invariant: range_left <= value <= range_right */
58 : int32_t subtree_containment_delta;
59 : /*
60 : * The subtree_containment_delta is the number of intervals that a
61 : * point would be contained in, if a probe point were moved from
62 : * just to the left of this subtree to just the right of the
63 : * subtree, i.e., from just less than range_left to just greater
64 : * than range_right.
65 : *
66 : * subtree_containment_delta = value_containment_delta +
67 : * (NULL != left) ? left->subtree_containment_delta : 0 +
68 : * (NULL != right) ? right->subtree_containment_delta : 0;
69 : */
70 : };
71 :
72 : struct NaClIntervalMultisetVtbl const kNaClIntervalRangeTreeVtbl; /* fwd */
73 :
74 : static INLINE void indent(int depth) {
75 : while (depth != 0) {
76 : putchar(' ');
77 : --depth;
78 : }
79 : }
80 :
81 : static void TreePrint(struct NaClIntervalRangeTreeNode *node,
82 : int depth) {
83 : if (NULL == node) {
84 : return;
85 : }
86 : /* rotated head view */
87 : TreePrint(node->right, depth + 1);
88 : indent(depth);
89 : printf("v=%d [b=%d, d=%d, rl=%u, rr=%u, dd=%d]\n",
90 : node->value, node->balance, node->value_containment_delta,
91 : node->range_left, node->range_right, node->subtree_containment_delta);
92 : TreePrint(node->left, depth + 1);
93 : }
94 :
95 : static INLINE void NaClIntervalRangeTreePrint(
96 15080902 : struct NaClIntervalRangeTreeNode *node) {
97 : if (!DEBUG_THIS) {
98 : return;
99 : }
100 : putchar('\n');
101 : TreePrint(node, 0);
102 : putchar('\n');
103 15080902 : }
104 :
105 : #define NaCl_dprintf(alist) do { if (DEBUG_THIS) printf alist; } while (0)
106 :
107 : static void NaClIntervalRangeTreeNodeInit(
108 1210006 : struct NaClIntervalRangeTreeNode *node,
109 1210006 : uint32_t value,
110 1210006 : int lr) {
111 1210006 : node->left = NULL;
112 1210006 : node->right = NULL;
113 1210006 : node->balance = 0;
114 1210006 : node->value = value;
115 1210006 : node->value_containment_delta = lr; /* 1 or -1 for L or R */
116 1210006 : node->refcount = 1; /* caller */
117 1210006 : node->range_left = value;
118 1210006 : node->range_right = value;
119 1210006 : node->subtree_containment_delta = lr;
120 1210006 : }
121 :
122 : static struct NaClIntervalRangeTreeNode *NaClIntervalRangeTreeNodeFactory(
123 605290 : uint32_t value,
124 605290 : int lr) {
125 605290 : struct NaClIntervalRangeTreeNode *obj;
126 605290 : obj = (struct NaClIntervalRangeTreeNode *) malloc(sizeof *obj);
127 605290 : if (NULL == obj) {
128 0 : NaClLog(LOG_FATAL, "NaClIntervalRangeTreeNodeFactory: out of memory!\n");
129 0 : }
130 605290 : NaClIntervalRangeTreeNodeInit(obj, value, lr);
131 605290 : return obj;
132 : }
133 :
134 : /*
135 : * Updates |node|'s range_left, range_right, and
136 : * subtree_containment_delta based on its left and right children.
137 : * Does not recursively walk! |node| must not be NULL.
138 : */
139 7694253 : static void NaClRangeStatsUpdate(struct NaClIntervalRangeTreeNode *node) {
140 7694253 : uint32_t range_left = node->value;
141 7694253 : uint32_t range_right = node->value;
142 7694253 : uint32_t cumulative_delta = node->value_containment_delta;
143 :
144 7694253 : if (NULL != node->left) {
145 6770427 : range_left = node->left->range_left;
146 6770427 : cumulative_delta += node->left->subtree_containment_delta;
147 6770427 : }
148 7694253 : if (NULL != node->right) {
149 6950194 : range_right = node->right->range_right;
150 6950194 : cumulative_delta += node->right->subtree_containment_delta;
151 6950194 : }
152 7694253 : node->range_left = range_left;
153 7694253 : node->range_right = range_right;
154 7694253 : node->subtree_containment_delta = cumulative_delta;
155 7694253 : }
156 :
157 : /*
158 : * returns 1 if (sub)tree at |*treep| grew in height, 0 otherwise.
159 : * |node| should be initialized, and this takes ownership. The
160 : * refcount may be transferred to another pre-exsting node in the
161 : * tree, and |node| freed.
162 : */
163 4418211 : static int NaClAvlTreeInsert(struct NaClIntervalRangeTreeNode **treep,
164 4418211 : struct NaClIntervalRangeTreeNode *node) {
165 4418211 : struct NaClIntervalRangeTreeNode *tmp;
166 4418211 : struct NaClIntervalRangeTreeNode *tmp_l;
167 4418211 : struct NaClIntervalRangeTreeNode *tmp_r;
168 4418211 : int higher;
169 :
170 4418211 : if (NULL == (tmp = *treep)) {
171 603742 : *treep = node;
172 603742 : return 1;
173 : }
174 3814469 : if (node->value == tmp->value) {
175 1548 : tmp->value_containment_delta += node->value_containment_delta;
176 1548 : tmp->subtree_containment_delta += node->value_containment_delta;
177 1548 : tmp->refcount++;
178 1548 : free(node);
179 1548 : return 0;
180 3812921 : } else if (node->value < tmp->value) {
181 : /* recurse left. */
182 1811349 : higher = NaClAvlTreeInsert(&tmp->left, node);
183 1811349 : if (!higher) {
184 1207678 : NaClRangeStatsUpdate(tmp);
185 1207678 : return 0;
186 : }
187 603671 : --tmp->balance;
188 603671 : if (0 == tmp->balance) {
189 : /* height unchanged */
190 113581 : NaClRangeStatsUpdate(tmp);
191 113581 : return 0;
192 : }
193 490090 : if (-1 == tmp->balance) {
194 : /*
195 : * Left tree grew, but we're still within AVL balance criteria
196 : * for this subtree. Subtree height grew, so let caller know.
197 : */
198 364961 : NaClRangeStatsUpdate(tmp);
199 364961 : return 1;
200 : }
201 : /* pivot */
202 125129 : if (-1 == tmp->left->balance) {
203 : /*
204 : * L rotation:
205 : *
206 : * x x
207 : *
208 : * d b
209 : * b e -> a d
210 : * a c c e
211 : */
212 46571 : *treep = tmp->left;
213 46571 : tmp->left = (*treep)->right;
214 46571 : (*treep)->right = tmp;
215 46571 : (*treep)->balance = 0;
216 46571 : tmp->balance = 0;
217 :
218 46571 : tmp = *treep; /* b */
219 46571 : NaClRangeStatsUpdate(tmp->right); /* d */
220 46571 : NaClRangeStatsUpdate(tmp);
221 46571 : return 0;
222 : } else {
223 : /*
224 : * LR rotation:
225 : *
226 : * x x
227 : *
228 : * f d
229 : * b g -> b f
230 : * a d a c e g
231 : * c e
232 : */
233 78558 : tmp = (*treep)->left->right;
234 78558 : tmp_l = tmp->left;
235 78558 : tmp_r = tmp->right;
236 78558 : tmp->left = (*treep)->left;
237 78558 : tmp->right = (*treep);
238 78558 : *treep = tmp;
239 78558 : tmp->left->right = tmp_l;
240 78558 : tmp->right->left = tmp_r;
241 78558 : tmp->left->balance = (tmp->balance <= 0) ? 0 : -1;
242 78558 : tmp->right->balance = (tmp->balance >= 0) ? 0 : 1;
243 78558 : tmp->balance = 0;
244 78558 : NaClRangeStatsUpdate(tmp->left);
245 78558 : NaClRangeStatsUpdate(tmp->right);
246 78558 : NaClRangeStatsUpdate(tmp);
247 78558 : return 0;
248 : }
249 : } else {
250 : /* node->value > tmp->value */
251 2001572 : higher = NaClAvlTreeInsert(&tmp->right, node);
252 2001572 : if (!higher) {
253 1202038 : NaClRangeStatsUpdate(tmp);
254 1202038 : return 0;
255 : }
256 799534 : ++tmp->balance;
257 799534 : if (0 == tmp->balance) {
258 : /* height unchanged */
259 102464 : NaClRangeStatsUpdate(tmp);
260 102464 : return 0;
261 : }
262 697070 : if (1 == tmp->balance) {
263 : /*
264 : * Right tree grew, but we're still within AVL balance criteria
265 : * for this subtree. Subtree height grew, so let caller know.
266 : */
267 561370 : NaClRangeStatsUpdate(tmp);
268 561370 : return 1;
269 : }
270 : /* pivot */
271 135700 : if (1 == tmp->right->balance) {
272 : /*
273 : * R rotation:
274 : *
275 : * x x
276 : *
277 : * b d
278 : * a d -> b e
279 : * c e a c
280 : */
281 100376 : *treep = tmp->right;
282 100376 : tmp->right = (*treep)->left;
283 100376 : (*treep)->left = tmp;
284 100376 : (*treep)->balance = 0;
285 100376 : tmp->balance = 0;
286 :
287 100376 : tmp = *treep;
288 100376 : NaClRangeStatsUpdate(tmp->left);
289 100376 : NaClRangeStatsUpdate(tmp);
290 100376 : return 0;
291 : } else {
292 : /*
293 : * RL rotation:
294 : *
295 : * x x
296 : *
297 : * b d
298 : * a f -> b f
299 : * d g a c e g
300 : * c e
301 : */
302 35324 : tmp = (*treep)->right->left;
303 35324 : tmp_l = tmp->left;
304 35324 : tmp_r = tmp->right;
305 35324 : tmp->right = (*treep)->right;
306 35324 : tmp->left = (*treep);
307 35324 : *treep = tmp;
308 35324 : tmp->right->left = tmp_r;
309 35324 : tmp->left->right = tmp_l;
310 35324 : tmp->right->balance = (tmp->balance >= 0) ? 0 : 1;
311 35324 : tmp->left->balance = (tmp->balance <= 0) ? 0 : -1;
312 35324 : tmp->balance = 0;
313 35324 : NaClRangeStatsUpdate(tmp->right);
314 35324 : NaClRangeStatsUpdate(tmp->left);
315 35324 : NaClRangeStatsUpdate(tmp);
316 35324 : return 0;
317 : }
318 : }
319 4418211 : }
320 :
321 : /*
322 : * NaClAvlTreeBalanceLeft -- left subtree shrunk. Adjust balance of
323 : * node, possibly rebalancing.
324 : */
325 : static void NaClAvlTreeBalanceLeft(
326 405562 : struct NaClIntervalRangeTreeNode **treep,
327 405562 : int *height_changed) {
328 405562 : int bal;
329 405562 : struct NaClIntervalRangeTreeNode *tmp;
330 405562 : struct NaClIntervalRangeTreeNode *tmp_l;
331 405562 : struct NaClIntervalRangeTreeNode *tmp_r;
332 :
333 405562 : bal = ++(*treep)->balance;
334 405562 : if (0 == bal) {
335 124152 : return;
336 : }
337 281410 : if (1 == bal) {
338 216574 : *height_changed = 0;
339 216574 : return;
340 : }
341 : /* Rebalance needed. */
342 64836 : tmp = (*treep)->right;
343 64836 : if (tmp->balance >= 0) {
344 : /*
345 : * RR rotation (same rotation as R, but balance adjusts differ)
346 : *
347 : * x x
348 : *
349 : * b d
350 : * a d -> b e
351 : * c e a c
352 : */
353 43807 : (*treep)->right = tmp->left;
354 43807 : tmp->left = (*treep);
355 43807 : *treep = tmp;
356 43807 : if (0 == tmp->balance) {
357 24530 : tmp->balance = -1;
358 24530 : tmp->left->balance = 1;
359 24530 : *height_changed = 0;
360 24530 : } else {
361 19277 : tmp->balance = 0;
362 19277 : tmp->left->balance = 0;
363 : }
364 43807 : NaClRangeStatsUpdate(tmp->left);
365 43807 : NaClRangeStatsUpdate(tmp);
366 43807 : } else {
367 : /*
368 : * RL rotation.
369 : *
370 : * x x
371 : *
372 : * b d
373 : * a f -> b f
374 : * d g a c e g
375 : * c e
376 : */
377 21029 : tmp = tmp->left; /* d */
378 21029 : tmp_l = tmp->left;
379 21029 : tmp_r = tmp->right;
380 21029 : tmp->left = *treep;
381 21029 : tmp->right = (*treep)->right;
382 21029 : *treep = tmp;
383 21029 : tmp->left->right = tmp_l;
384 21029 : tmp->right->left = tmp_r;
385 21029 : tmp->left->balance = (tmp->balance > 0) ? -1 : 0;
386 21029 : tmp->right->balance = (tmp->balance < 0) ? 1 : 0;
387 21029 : tmp->balance = 0;
388 : /*
389 : * *h == 1 remains true.
390 : */
391 21029 : NaClRangeStatsUpdate(tmp->left);
392 21029 : NaClRangeStatsUpdate(tmp->right);
393 21029 : NaClRangeStatsUpdate(tmp);
394 : }
395 405562 : }
396 :
397 : /*
398 : * NaClAvlTreeBalanceRight -- right subtree shrunk. Adjust balance of
399 : * node, possibly rebalancing.
400 : */
401 : static void NaClAvlTreeBalanceRight(
402 503887 : struct NaClIntervalRangeTreeNode **treep,
403 503887 : int *height_changed) {
404 503887 : int bal;
405 503887 : struct NaClIntervalRangeTreeNode *tmp;
406 503887 : struct NaClIntervalRangeTreeNode *tmp_l;
407 503887 : struct NaClIntervalRangeTreeNode *tmp_r;
408 :
409 503887 : bal = --(*treep)->balance;
410 503887 : if (0 == bal) {
411 223421 : return;
412 : }
413 280466 : if (-1 == bal) {
414 210991 : *height_changed = 0;
415 210991 : return;
416 : }
417 : /* Rebalance needed. */
418 69475 : tmp = (*treep)->left;
419 69475 : if (tmp->balance <= 0) {
420 : /*
421 : * LL rotation (same rotation as L, but balance adjusts differ)
422 : *
423 : *
424 : * x x
425 : *
426 : * d b
427 : * b e -> a d
428 : * a c c e
429 : */
430 41151 : (*treep)->left = tmp->right;
431 41151 : tmp->right = (*treep);
432 41151 : *treep = tmp;
433 41151 : if (0 == tmp->balance) {
434 24238 : tmp->balance = 1;
435 24238 : tmp->right->balance = -1;
436 24238 : *height_changed = 0;
437 24238 : } else {
438 16913 : tmp->balance = 0;
439 16913 : tmp->right->balance = 0;
440 : }
441 41151 : NaClRangeStatsUpdate(tmp->right);
442 41151 : NaClRangeStatsUpdate(tmp);
443 41151 : } else {
444 : /*
445 : * LR rotation.
446 : *
447 : * x x
448 : *
449 : * f d
450 : * b g -> b f
451 : * a d a c e g
452 : * c e
453 : */
454 28324 : tmp = tmp->right; /* d */
455 28324 : tmp_l = tmp->left;
456 28324 : tmp_r = tmp->right;
457 28324 : tmp->left = (*treep)->left;
458 28324 : tmp->right = *treep;
459 28324 : *treep = tmp;
460 28324 : tmp->left->right = tmp_l;
461 28324 : tmp->right->left = tmp_r;
462 28324 : tmp->left->balance = (tmp->balance > 0) ? -1 : 0;
463 28324 : tmp->right->balance = (tmp->balance < 0) ? 1 : 0;
464 28324 : tmp->balance = 0;
465 : /*
466 : * *h == 1 remains true.
467 : */
468 28324 : NaClRangeStatsUpdate(tmp->left);
469 28324 : NaClRangeStatsUpdate(tmp->right);
470 28324 : NaClRangeStatsUpdate(tmp);
471 : }
472 503887 : }
473 :
474 : static struct NaClIntervalRangeTreeNode *NaClAvlFindRightMost(
475 342219 : struct NaClIntervalRangeTreeNode **treep,
476 342219 : int *height_changed) {
477 342219 : struct NaClIntervalRangeTreeNode *tmp;
478 :
479 342219 : if (NULL != (*treep)->right) {
480 189610 : tmp = NaClAvlFindRightMost(&(*treep)->right, height_changed);
481 189610 : NaClRangeStatsUpdate(*treep);
482 189610 : if (*height_changed) {
483 125940 : NaClAvlTreeBalanceRight(treep, height_changed);
484 125940 : }
485 189610 : return tmp;
486 : }
487 152609 : tmp = *treep;
488 152609 : *treep = tmp->left;
489 152609 : *height_changed = 1;
490 152609 : return tmp;
491 342219 : }
492 :
493 : static struct NaClIntervalRangeTreeNode *NaClAvlFindLeftMost(
494 90441 : struct NaClIntervalRangeTreeNode **treep,
495 90441 : int *height_changed) {
496 90441 : struct NaClIntervalRangeTreeNode *tmp;
497 :
498 90441 : if (NULL != (*treep)->left) {
499 54225 : tmp = NaClAvlFindLeftMost(&(*treep)->left, height_changed);
500 54225 : NaClRangeStatsUpdate(*treep);
501 54225 : if (*height_changed) {
502 36572 : NaClAvlTreeBalanceLeft(treep, height_changed);
503 36572 : }
504 54225 : return tmp;
505 : }
506 36216 : tmp = *treep;
507 36216 : *treep = tmp->right;
508 36216 : *height_changed = 1;
509 36216 : return tmp;
510 90441 : }
511 :
512 : static struct NaClIntervalRangeTreeNode *NaClAvlTreeExtract(
513 3360702 : struct NaClIntervalRangeTreeNode **treep,
514 3360702 : struct NaClIntervalRangeTreeNode *key,
515 3360702 : int *height_changed) {
516 3360702 : struct NaClIntervalRangeTreeNode *p;
517 3360702 : struct NaClIntervalRangeTreeNode *tmp;
518 :
519 3360702 : if (NULL == *treep) {
520 0 : NaClLog(LOG_FATAL, "NaClAvlTreeExtract: node not found\n");
521 0 : }
522 6721404 : NaCl_dprintf(("TreeExtract k->v %u, k->d %d, h %d\n",
523 : key->value, key->value_containment_delta, *height_changed));
524 3360702 : NaClIntervalRangeTreePrint(*treep);
525 3360702 : if (key->value < (*treep)->value) {
526 1323231 : p = NaClAvlTreeExtract(&(*treep)->left, key, height_changed);
527 1323231 : NaClRangeStatsUpdate(*treep);
528 1323231 : if (*height_changed) {
529 284231 : NaClAvlTreeBalanceLeft(treep, height_changed);
530 284231 : }
531 1323231 : return p;
532 2037471 : } else if (key->value > (*treep)->value) {
533 1432755 : p = NaClAvlTreeExtract(&(*treep)->right, key, height_changed);
534 1432755 : NaClRangeStatsUpdate(*treep);
535 1432755 : if (*height_changed) {
536 360843 : NaClAvlTreeBalanceRight(treep, height_changed);
537 360843 : }
538 1432755 : return p;
539 : } else {
540 : /*
541 : * found elt
542 : */
543 604716 : p = *treep;
544 604716 : if (0 != --p->refcount) {
545 1548 : p->value_containment_delta -= key->value_containment_delta;
546 1548 : p->subtree_containment_delta -= key->value_containment_delta;
547 1548 : return NULL;
548 : }
549 : /* zero refcount, should delete */
550 603168 : if (NULL == p->right) {
551 380927 : *treep = p->left;
552 380927 : *height_changed = 1;
553 603168 : } else if (NULL == p->left) {
554 33416 : *treep = p->right;
555 33416 : *height_changed = 1;
556 222241 : } else if (p->balance <= 0) {
557 152609 : tmp = NaClAvlFindRightMost(&p->left, height_changed);
558 152609 : tmp->left = p->left;
559 152609 : tmp->right = p->right;
560 152609 : tmp->balance = p->balance;
561 152609 : NaClRangeStatsUpdate(tmp);
562 152609 : *treep = tmp;
563 152609 : if (*height_changed) {
564 84759 : NaClAvlTreeBalanceLeft(treep, height_changed);
565 84759 : }
566 152609 : } else {
567 36216 : tmp = NaClAvlFindLeftMost(&p->right, height_changed);
568 36216 : tmp->left = p->left;
569 36216 : tmp->right = p->right;
570 36216 : tmp->balance = p->balance;
571 36216 : NaClRangeStatsUpdate(tmp);
572 36216 : *treep = tmp;
573 36216 : if (*height_changed) {
574 17104 : NaClAvlTreeBalanceRight(treep, height_changed);
575 17104 : }
576 : }
577 603168 : p->left = NULL;
578 603168 : p->right = NULL;
579 603168 : return p;
580 : }
581 3360702 : }
582 :
583 : static struct NaClIntervalRangeTreeNode *NaClIntervalRangeTreeExtract(
584 604716 : struct NaClIntervalRangeTree *self,
585 604716 : struct NaClIntervalRangeTreeNode *keyp) {
586 604716 : int height_changed = 0;
587 :
588 604716 : return NaClAvlTreeExtract(&self->root, keyp, &height_changed);
589 : }
590 :
591 604716 : static void NaClIntervalRangeTreeRemoveVal(struct NaClIntervalRangeTree *self,
592 604716 : uint32_t value,
593 604716 : int lr) {
594 604716 : struct NaClIntervalRangeTreeNode key;
595 604716 : struct NaClIntervalRangeTreeNode *zero_ref_node;
596 :
597 1209432 : NaCl_dprintf(("RemoveVal %u %d\n", value, lr));
598 604716 : NaClIntervalRangeTreeNodeInit(&key, value, lr);
599 604716 : zero_ref_node = NaClIntervalRangeTreeExtract(self, &key);
600 604716 : if (NULL != zero_ref_node) {
601 603168 : free(zero_ref_node);
602 603168 : }
603 1209432 : NaCl_dprintf(("result tree\n"));
604 604716 : NaClIntervalRangeTreePrint(self->root);
605 604716 : }
606 :
607 : /*
608 : * Returns a lower bound for the containment count at |value| (number
609 : * of intervals in the interval set that contains it). This lower
610 : * bound will never be zero if the actual containment count is
611 : * non-zero. If the count is zero, then the memory pointed to by
612 : * |gap_left| is written with the starting value of the open interval
613 : * that is the gap containing the value, i.e., *gap_left will be one
614 : * larger than the range_right value of the closed interval
615 : * immediately to the left. NB: 0 is possible for this value, i.e.,
616 : * when there are no interval that bound the gap from the left. The
617 : * value is undefined when the return value is non-zero.
618 : *
619 : * We could also provide gap_right, but it's not necessary for the
620 : * correctness of our algorithm.
621 : *
622 : * This function is called with |left_delta| equal to zero,
623 : * |left_range| equal to 0, and |tree| the root of the tree.
624 : */
625 : static uint32_t NaClAvlTreeFindValue(
626 10207549 : struct NaClIntervalRangeTreeNode *tree,
627 10207549 : uint32_t left_delta,
628 10207549 : uint32_t left_range,
629 10207549 : uint32_t value,
630 10207549 : uint32_t *gap_left) {
631 10207549 : uint32_t delta;
632 :
633 20415098 : NaCl_dprintf(("TreeFind ld %u lr %u v %u\n", left_delta, left_range, value));
634 10207549 : NaClIntervalRangeTreePrint(tree);
635 10207549 : if (NULL == tree) {
636 1372809 : *gap_left = left_range;
637 1372809 : return left_delta;
638 : }
639 8834740 : if (value < tree->value) {
640 4504616 : return NaClAvlTreeFindValue(tree->left, left_delta, left_range, value,
641 : gap_left);
642 4330124 : } else if (value == tree->value) {
643 32 : delta = left_delta;
644 32 : if (NULL != tree->left) {
645 12 : delta += tree->left->subtree_containment_delta;
646 12 : }
647 32 : delta += tree->value_containment_delta;
648 32 : if (0 == delta) {
649 : /*
650 : * This case occurs if interval set contains [x,y] and we probed
651 : * for y. Since this is an inclusive interval, we need to
652 : * increment rv -- the containment count cannot possibly be zero
653 : * at a closed-interval end point. The returned value can be a
654 : * lower bound for other reasons, e.g., if the set contained
655 : * intervals [x,y][y,z] and we probed for y, the
656 : * value_containment_delta will be zero because y is both the
657 : * end and the start of intervals, and we'd return 1 when in
658 : * reality y is included in two intervals.
659 : */
660 10 : delta = 1;
661 10 : }
662 :
663 : /* *gap_left undefined */
664 32 : return delta;
665 : } else {
666 4330092 : delta = left_delta;
667 4330092 : if (NULL != tree->left) {
668 3766955 : delta += tree->left->subtree_containment_delta;
669 3766955 : }
670 4330092 : delta += tree->value_containment_delta;
671 4330092 : left_range = tree->value + 1;
672 :
673 4330092 : return NaClAvlTreeFindValue(tree->right,
674 : delta,
675 : left_range,
676 : value,
677 : gap_left);
678 : }
679 10207549 : }
680 :
681 1144 : void NaClAvlTreeFree(struct NaClIntervalRangeTreeNode *t) {
682 1144 : if (NULL == t) {
683 574 : return;
684 : }
685 570 : NaClAvlTreeFree(t->left);
686 570 : t->left = NULL;
687 570 : NaClAvlTreeFree(t->right);
688 570 : t->right = NULL;
689 570 : free(t);
690 1714 : }
691 :
692 299 : int NaClIntervalRangeTreeCtor(struct NaClIntervalRangeTree *self) {
693 299 : self->root = NULL;
694 299 : self->base.vtbl = &kNaClIntervalRangeTreeVtbl;
695 299 : return 1;
696 : }
697 :
698 4 : void NaClIntervalRangeTreeDtor(struct NaClIntervalMultiset *vself) {
699 4 : struct NaClIntervalRangeTree *self = (struct NaClIntervalRangeTree *) vself;
700 :
701 4 : NaClAvlTreeFree(self->root);
702 4 : self->root = NULL;
703 4 : self->base.vtbl = NULL;
704 4 : }
705 :
706 302645 : void NaClIntervalRangeTreeAddInterval(struct NaClIntervalMultiset *vself,
707 302645 : uint32_t first_val, uint32_t last_val) {
708 302645 : struct NaClIntervalRangeTree *self;
709 302645 : struct NaClIntervalRangeTreeNode *range_start;
710 302645 : struct NaClIntervalRangeTreeNode *range_end;
711 :
712 302645 : self = (struct NaClIntervalRangeTree *) vself;
713 302645 : range_start = NaClIntervalRangeTreeNodeFactory(first_val, 1);
714 302645 : range_end = NaClIntervalRangeTreeNodeFactory(last_val, -1);
715 302645 : NaClIntervalRangeTreePrint(self->root);
716 302645 : (void) NaClAvlTreeInsert(&self->root, range_start);
717 302645 : NaClIntervalRangeTreePrint(self->root);
718 302645 : (void) NaClAvlTreeInsert(&self->root, range_end);
719 302645 : NaClIntervalRangeTreePrint(self->root);
720 302645 : }
721 :
722 302358 : void NaClIntervalRangeTreeRemoveInterval(struct NaClIntervalMultiset *vself,
723 302358 : uint32_t first_val,
724 302358 : uint32_t last_val) {
725 302358 : struct NaClIntervalRangeTree *self = (struct NaClIntervalRangeTree *) vself;
726 :
727 302358 : NaClIntervalRangeTreeRemoveVal(self, last_val, -1);
728 302358 : NaClIntervalRangeTreeRemoveVal(self, first_val, 1);
729 302358 : }
730 :
731 771811 : int NaClIntervalRangeTreeOverlapsWith(struct NaClIntervalMultiset *vself,
732 771811 : uint32_t first_val, uint32_t last_val) {
733 771811 : struct NaClIntervalRangeTree *self = (struct NaClIntervalRangeTree *) vself;
734 771811 : uint32_t gap_left_first;
735 771811 : uint32_t gap_left_last;
736 :
737 1543622 : NaCl_dprintf(("OverlapsWith [%u, %u]\n", first_val, last_val));
738 771811 : if (0 != NaClAvlTreeFindValue(self->root, 0, 0, first_val, &gap_left_first)) {
739 341562 : NaCl_dprintf(("left not in gap\n"));
740 170781 : return 1;
741 : }
742 601030 : if (0 != NaClAvlTreeFindValue(self->root, 0, 0, last_val, &gap_left_last)) {
743 159186 : NaCl_dprintf(("right not in gap\n"));
744 79593 : return 1;
745 : }
746 :
747 1042874 : NaCl_dprintf(("gap first %u gap last %u\n", gap_left_first, gap_left_last));
748 521437 : if (gap_left_first == gap_left_last) {
749 : /*
750 : * Both first_val and last_val had a containment count of zero,
751 : * and they are in the same gap.
752 : */
753 492005 : return 0;
754 : }
755 29432 : return 1;
756 771811 : }
757 :
758 : struct NaClIntervalMultisetVtbl const kNaClIntervalRangeTreeVtbl = {
759 : NaClIntervalRangeTreeDtor,
760 : NaClIntervalRangeTreeAddInterval,
761 : NaClIntervalRangeTreeRemoveInterval,
762 : NaClIntervalRangeTreeOverlapsWith,
763 : };
|
