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 0 : static INLINE void indent(int depth) {
75 0 : while (depth != 0) {
76 0 : putchar(' ');
77 0 : --depth;
78 : }
79 0 : }
80 :
81 0 : static void TreePrint(struct NaClIntervalRangeTreeNode *node,
82 : int depth) {
83 0 : if (NULL == node) {
84 0 : return;
85 : }
86 : /* rotated head view */
87 0 : TreePrint(node->right, depth + 1);
88 0 : indent(depth);
89 0 : 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 0 : TreePrint(node->left, depth + 1);
93 : }
94 :
95 14738063 : static INLINE void NaClIntervalRangeTreePrint(
96 : struct NaClIntervalRangeTreeNode *node) {
97 : if (!DEBUG_THIS) {
98 14738063 : return;
99 : }
100 : putchar('\n');
101 : TreePrint(node, 0);
102 : putchar('\n');
103 : }
104 :
105 : #define NaCl_dprintf(alist) do { if (DEBUG_THIS) printf alist; } while (0)
106 :
107 1211934 : static void NaClIntervalRangeTreeNodeInit(
108 : struct NaClIntervalRangeTreeNode *node,
109 : uint32_t value,
110 : int lr) {
111 1211934 : node->left = NULL;
112 1211934 : node->right = NULL;
113 1211934 : node->balance = 0;
114 1211934 : node->value = value;
115 1211934 : node->value_containment_delta = lr; /* 1 or -1 for L or R */
116 1211934 : node->refcount = 1; /* caller */
117 1211934 : node->range_left = value;
118 1211934 : node->range_right = value;
119 1211934 : node->subtree_containment_delta = lr;
120 1211934 : }
121 :
122 606448 : static struct NaClIntervalRangeTreeNode *NaClIntervalRangeTreeNodeFactory(
123 : uint32_t value,
124 : int lr) {
125 : struct NaClIntervalRangeTreeNode *obj;
126 606448 : obj = (struct NaClIntervalRangeTreeNode *) malloc(sizeof *obj);
127 606448 : if (NULL == obj) {
128 0 : NaClLog(LOG_FATAL, "NaClIntervalRangeTreeNodeFactory: out of memory!\n");
129 : }
130 606448 : NaClIntervalRangeTreeNodeInit(obj, value, lr);
131 606448 : 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 8308098 : static void NaClRangeStatsUpdate(struct NaClIntervalRangeTreeNode *node) {
140 8308098 : uint32_t range_left = node->value;
141 8308098 : uint32_t range_right = node->value;
142 8308098 : uint32_t cumulative_delta = node->value_containment_delta;
143 :
144 8308098 : if (NULL != node->left) {
145 7414661 : range_left = node->left->range_left;
146 7414661 : cumulative_delta += node->left->subtree_containment_delta;
147 : }
148 8308098 : if (NULL != node->right) {
149 7567979 : range_right = node->right->range_right;
150 7567979 : cumulative_delta += node->right->subtree_containment_delta;
151 : }
152 8308098 : node->range_left = range_left;
153 8308098 : node->range_right = range_right;
154 8308098 : node->subtree_containment_delta = cumulative_delta;
155 8308098 : }
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 4729813 : static int NaClAvlTreeInsert(struct NaClIntervalRangeTreeNode **treep,
164 : struct NaClIntervalRangeTreeNode *node) {
165 : struct NaClIntervalRangeTreeNode *tmp;
166 : struct NaClIntervalRangeTreeNode *tmp_l;
167 : struct NaClIntervalRangeTreeNode *tmp_r;
168 : int higher;
169 :
170 4729813 : if (NULL == (tmp = *treep)) {
171 604900 : *treep = node;
172 604900 : return 1;
173 : }
174 4124913 : 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 4123365 : } else if (node->value < tmp->value) {
181 : /* recurse left. */
182 1981294 : higher = NaClAvlTreeInsert(&tmp->left, node);
183 1981294 : if (!higher) {
184 1373889 : NaClRangeStatsUpdate(tmp);
185 1373889 : return 0;
186 : }
187 607405 : --tmp->balance;
188 607405 : if (0 == tmp->balance) {
189 : /* height unchanged */
190 123690 : NaClRangeStatsUpdate(tmp);
191 123690 : return 0;
192 : }
193 483715 : 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 370244 : NaClRangeStatsUpdate(tmp);
199 370244 : return 1;
200 : }
201 : /* pivot */
202 113471 : 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 48786 : *treep = tmp->left;
213 48786 : tmp->left = (*treep)->right;
214 48786 : (*treep)->right = tmp;
215 48786 : (*treep)->balance = 0;
216 48786 : tmp->balance = 0;
217 :
218 48786 : tmp = *treep; /* b */
219 48786 : NaClRangeStatsUpdate(tmp->right); /* d */
220 48786 : NaClRangeStatsUpdate(tmp);
221 48786 : 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 64685 : tmp = (*treep)->left->right;
234 64685 : tmp_l = tmp->left;
235 64685 : tmp_r = tmp->right;
236 64685 : tmp->left = (*treep)->left;
237 64685 : tmp->right = (*treep);
238 64685 : *treep = tmp;
239 64685 : tmp->left->right = tmp_l;
240 64685 : tmp->right->left = tmp_r;
241 64685 : tmp->left->balance = (tmp->balance <= 0) ? 0 : -1;
242 64685 : tmp->right->balance = (tmp->balance >= 0) ? 0 : 1;
243 64685 : tmp->balance = 0;
244 64685 : NaClRangeStatsUpdate(tmp->left);
245 64685 : NaClRangeStatsUpdate(tmp->right);
246 64685 : NaClRangeStatsUpdate(tmp);
247 64685 : return 0;
248 : }
249 : } else {
250 : /* node->value > tmp->value */
251 2142071 : higher = NaClAvlTreeInsert(&tmp->right, node);
252 2142071 : if (!higher) {
253 1381711 : NaClRangeStatsUpdate(tmp);
254 1381711 : return 0;
255 : }
256 760360 : ++tmp->balance;
257 760360 : if (0 == tmp->balance) {
258 : /* height unchanged */
259 109226 : NaClRangeStatsUpdate(tmp);
260 109226 : return 0;
261 : }
262 651134 : 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 527188 : NaClRangeStatsUpdate(tmp);
268 527188 : return 1;
269 : }
270 : /* pivot */
271 123946 : 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 86208 : *treep = tmp->right;
282 86208 : tmp->right = (*treep)->left;
283 86208 : (*treep)->left = tmp;
284 86208 : (*treep)->balance = 0;
285 86208 : tmp->balance = 0;
286 :
287 86208 : tmp = *treep;
288 86208 : NaClRangeStatsUpdate(tmp->left);
289 86208 : NaClRangeStatsUpdate(tmp);
290 86208 : 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 37738 : tmp = (*treep)->right->left;
303 37738 : tmp_l = tmp->left;
304 37738 : tmp_r = tmp->right;
305 37738 : tmp->right = (*treep)->right;
306 37738 : tmp->left = (*treep);
307 37738 : *treep = tmp;
308 37738 : tmp->right->left = tmp_r;
309 37738 : tmp->left->right = tmp_l;
310 37738 : tmp->right->balance = (tmp->balance >= 0) ? 0 : 1;
311 37738 : tmp->left->balance = (tmp->balance <= 0) ? 0 : -1;
312 37738 : tmp->balance = 0;
313 37738 : NaClRangeStatsUpdate(tmp->right);
314 37738 : NaClRangeStatsUpdate(tmp->left);
315 37738 : NaClRangeStatsUpdate(tmp);
316 37738 : return 0;
317 : }
318 : }
319 : }
320 :
321 : /*
322 : * NaClAvlTreeBalanceLeft -- left subtree shrunk. Adjust balance of
323 : * node, possibly rebalancing.
324 : */
325 408272 : static void NaClAvlTreeBalanceLeft(
326 : struct NaClIntervalRangeTreeNode **treep,
327 : int *height_changed) {
328 : int bal;
329 : struct NaClIntervalRangeTreeNode *tmp;
330 : struct NaClIntervalRangeTreeNode *tmp_l;
331 : struct NaClIntervalRangeTreeNode *tmp_r;
332 :
333 408272 : bal = ++(*treep)->balance;
334 408272 : if (0 == bal) {
335 129560 : return;
336 : }
337 278712 : if (1 == bal) {
338 220940 : *height_changed = 0;
339 220940 : return;
340 : }
341 : /* Rebalance needed. */
342 57772 : tmp = (*treep)->right;
343 57772 : 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 39773 : (*treep)->right = tmp->left;
354 39773 : tmp->left = (*treep);
355 39773 : *treep = tmp;
356 39773 : if (0 == tmp->balance) {
357 21712 : tmp->balance = -1;
358 21712 : tmp->left->balance = 1;
359 21712 : *height_changed = 0;
360 : } else {
361 18061 : tmp->balance = 0;
362 18061 : tmp->left->balance = 0;
363 : }
364 39773 : NaClRangeStatsUpdate(tmp->left);
365 39773 : NaClRangeStatsUpdate(tmp);
366 : } 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 17999 : tmp = tmp->left; /* d */
378 17999 : tmp_l = tmp->left;
379 17999 : tmp_r = tmp->right;
380 17999 : tmp->left = *treep;
381 17999 : tmp->right = (*treep)->right;
382 17999 : *treep = tmp;
383 17999 : tmp->left->right = tmp_l;
384 17999 : tmp->right->left = tmp_r;
385 17999 : tmp->left->balance = (tmp->balance > 0) ? -1 : 0;
386 17999 : tmp->right->balance = (tmp->balance < 0) ? 1 : 0;
387 17999 : tmp->balance = 0;
388 : /*
389 : * *h == 1 remains true.
390 : */
391 17999 : NaClRangeStatsUpdate(tmp->left);
392 17999 : NaClRangeStatsUpdate(tmp->right);
393 17999 : NaClRangeStatsUpdate(tmp);
394 : }
395 : }
396 :
397 : /*
398 : * NaClAvlTreeBalanceRight -- right subtree shrunk. Adjust balance of
399 : * node, possibly rebalancing.
400 : */
401 501018 : static void NaClAvlTreeBalanceRight(
402 : struct NaClIntervalRangeTreeNode **treep,
403 : int *height_changed) {
404 : int bal;
405 : struct NaClIntervalRangeTreeNode *tmp;
406 : struct NaClIntervalRangeTreeNode *tmp_l;
407 : struct NaClIntervalRangeTreeNode *tmp_r;
408 :
409 501018 : bal = --(*treep)->balance;
410 501018 : if (0 == bal) {
411 228771 : return;
412 : }
413 272247 : if (-1 == bal) {
414 206187 : *height_changed = 0;
415 206187 : return;
416 : }
417 : /* Rebalance needed. */
418 66060 : tmp = (*treep)->left;
419 66060 : 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 37868 : (*treep)->left = tmp->right;
431 37868 : tmp->right = (*treep);
432 37868 : *treep = tmp;
433 37868 : if (0 == tmp->balance) {
434 20566 : tmp->balance = 1;
435 20566 : tmp->right->balance = -1;
436 20566 : *height_changed = 0;
437 : } else {
438 17302 : tmp->balance = 0;
439 17302 : tmp->right->balance = 0;
440 : }
441 37868 : NaClRangeStatsUpdate(tmp->right);
442 37868 : NaClRangeStatsUpdate(tmp);
443 : } 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 28192 : tmp = tmp->right; /* d */
455 28192 : tmp_l = tmp->left;
456 28192 : tmp_r = tmp->right;
457 28192 : tmp->left = (*treep)->left;
458 28192 : tmp->right = *treep;
459 28192 : *treep = tmp;
460 28192 : tmp->left->right = tmp_l;
461 28192 : tmp->right->left = tmp_r;
462 28192 : tmp->left->balance = (tmp->balance > 0) ? -1 : 0;
463 28192 : tmp->right->balance = (tmp->balance < 0) ? 1 : 0;
464 28192 : tmp->balance = 0;
465 : /*
466 : * *h == 1 remains true.
467 : */
468 28192 : NaClRangeStatsUpdate(tmp->left);
469 28192 : NaClRangeStatsUpdate(tmp->right);
470 28192 : NaClRangeStatsUpdate(tmp);
471 : }
472 : }
473 :
474 330452 : static struct NaClIntervalRangeTreeNode *NaClAvlFindRightMost(
475 : struct NaClIntervalRangeTreeNode **treep,
476 : int *height_changed) {
477 : struct NaClIntervalRangeTreeNode *tmp;
478 :
479 330452 : if (NULL != (*treep)->right) {
480 182230 : tmp = NaClAvlFindRightMost(&(*treep)->right, height_changed);
481 182230 : NaClRangeStatsUpdate(*treep);
482 182230 : if (*height_changed) {
483 121694 : NaClAvlTreeBalanceRight(treep, height_changed);
484 : }
485 182230 : return tmp;
486 : }
487 148222 : tmp = *treep;
488 148222 : *treep = tmp->left;
489 148222 : *height_changed = 1;
490 148222 : return tmp;
491 : }
492 :
493 90715 : static struct NaClIntervalRangeTreeNode *NaClAvlFindLeftMost(
494 : struct NaClIntervalRangeTreeNode **treep,
495 : int *height_changed) {
496 : struct NaClIntervalRangeTreeNode *tmp;
497 :
498 90715 : if (NULL != (*treep)->left) {
499 52595 : tmp = NaClAvlFindLeftMost(&(*treep)->left, height_changed);
500 52595 : NaClRangeStatsUpdate(*treep);
501 52595 : if (*height_changed) {
502 36387 : NaClAvlTreeBalanceLeft(treep, height_changed);
503 : }
504 52595 : return tmp;
505 : }
506 38120 : tmp = *treep;
507 38120 : *treep = tmp->right;
508 38120 : *height_changed = 1;
509 38120 : return tmp;
510 : }
511 :
512 3735357 : static struct NaClIntervalRangeTreeNode *NaClAvlTreeExtract(
513 : struct NaClIntervalRangeTreeNode **treep,
514 : struct NaClIntervalRangeTreeNode *key,
515 : int *height_changed) {
516 : struct NaClIntervalRangeTreeNode *p;
517 : struct NaClIntervalRangeTreeNode *tmp;
518 :
519 3735357 : if (NULL == *treep) {
520 0 : NaClLog(LOG_FATAL, "NaClAvlTreeExtract: node not found\n");
521 : }
522 : NaCl_dprintf(("TreeExtract k->v %u, k->d %d, h %d\n",
523 : key->value, key->value_containment_delta, *height_changed));
524 3735357 : NaClIntervalRangeTreePrint(*treep);
525 3735357 : if (key->value < (*treep)->value) {
526 1508047 : p = NaClAvlTreeExtract(&(*treep)->left, key, height_changed);
527 1508047 : NaClRangeStatsUpdate(*treep);
528 1508047 : if (*height_changed) {
529 287438 : NaClAvlTreeBalanceLeft(treep, height_changed);
530 : }
531 1508047 : return p;
532 2227310 : } else if (key->value > (*treep)->value) {
533 1621824 : p = NaClAvlTreeExtract(&(*treep)->right, key, height_changed);
534 1621824 : NaClRangeStatsUpdate(*treep);
535 1621824 : if (*height_changed) {
536 358771 : NaClAvlTreeBalanceRight(treep, height_changed);
537 : }
538 1621824 : return p;
539 : } else {
540 : /*
541 : * found elt
542 : */
543 605486 : p = *treep;
544 605486 : 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 603938 : if (NULL == p->right) {
551 386024 : *treep = p->left;
552 386024 : *height_changed = 1;
553 217914 : } else if (NULL == p->left) {
554 31572 : *treep = p->right;
555 31572 : *height_changed = 1;
556 186342 : } else if (p->balance <= 0) {
557 148222 : tmp = NaClAvlFindRightMost(&p->left, height_changed);
558 148222 : tmp->left = p->left;
559 148222 : tmp->right = p->right;
560 148222 : tmp->balance = p->balance;
561 148222 : NaClRangeStatsUpdate(tmp);
562 148222 : *treep = tmp;
563 148222 : if (*height_changed) {
564 84447 : NaClAvlTreeBalanceLeft(treep, height_changed);
565 : }
566 : } else {
567 38120 : tmp = NaClAvlFindLeftMost(&p->right, height_changed);
568 38120 : tmp->left = p->left;
569 38120 : tmp->right = p->right;
570 38120 : tmp->balance = p->balance;
571 38120 : NaClRangeStatsUpdate(tmp);
572 38120 : *treep = tmp;
573 38120 : if (*height_changed) {
574 20553 : NaClAvlTreeBalanceRight(treep, height_changed);
575 : }
576 : }
577 603938 : p->left = NULL;
578 603938 : p->right = NULL;
579 603938 : return p;
580 : }
581 : }
582 :
583 605486 : static struct NaClIntervalRangeTreeNode *NaClIntervalRangeTreeExtract(
584 : struct NaClIntervalRangeTree *self,
585 : struct NaClIntervalRangeTreeNode *keyp) {
586 605486 : int height_changed = 0;
587 :
588 605486 : return NaClAvlTreeExtract(&self->root, keyp, &height_changed);
589 : }
590 :
591 605486 : static void NaClIntervalRangeTreeRemoveVal(struct NaClIntervalRangeTree *self,
592 : uint32_t value,
593 : int lr) {
594 : struct NaClIntervalRangeTreeNode key;
595 : struct NaClIntervalRangeTreeNode *zero_ref_node;
596 :
597 : NaCl_dprintf(("RemoveVal %u %d\n", value, lr));
598 605486 : NaClIntervalRangeTreeNodeInit(&key, value, lr);
599 605486 : zero_ref_node = NaClIntervalRangeTreeExtract(self, &key);
600 605486 : if (NULL != zero_ref_node) {
601 603938 : free(zero_ref_node);
602 : }
603 : NaCl_dprintf(("result tree\n"));
604 605486 : NaClIntervalRangeTreePrint(self->root);
605 605486 : }
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 9487548 : static uint32_t NaClAvlTreeFindValue(
626 : struct NaClIntervalRangeTreeNode *tree,
627 : uint32_t left_delta,
628 : uint32_t left_range,
629 : uint32_t value,
630 : uint32_t *gap_left) {
631 : uint32_t delta;
632 :
633 : NaCl_dprintf(("TreeFind ld %u lr %u v %u\n", left_delta, left_range, value));
634 9487548 : NaClIntervalRangeTreePrint(tree);
635 9487548 : if (NULL == tree) {
636 1148916 : *gap_left = left_range;
637 1148916 : return left_delta;
638 : }
639 8338632 : if (value < tree->value) {
640 4217831 : return NaClAvlTreeFindValue(tree->left, left_delta, left_range, value,
641 : gap_left);
642 4120801 : } 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 : }
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 : }
662 :
663 : /* *gap_left undefined */
664 32 : return delta;
665 : } else {
666 4120769 : delta = left_delta;
667 4120769 : if (NULL != tree->left) {
668 3614734 : delta += tree->left->subtree_containment_delta;
669 : }
670 4120769 : delta += tree->value_containment_delta;
671 4120769 : left_range = tree->value + 1;
672 :
673 4120769 : return NaClAvlTreeFindValue(tree->right,
674 : delta,
675 : left_range,
676 : value,
677 : gap_left);
678 : }
679 : }
680 :
681 1920 : void NaClAvlTreeFree(struct NaClIntervalRangeTreeNode *t) {
682 1920 : if (NULL == t) {
683 2882 : return;
684 : }
685 958 : NaClAvlTreeFree(t->left);
686 958 : t->left = NULL;
687 958 : NaClAvlTreeFree(t->right);
688 958 : t->right = NULL;
689 958 : free(t);
690 : }
691 :
692 315 : int NaClIntervalRangeTreeCtor(struct NaClIntervalRangeTree *self) {
693 315 : self->root = NULL;
694 315 : self->base.vtbl = &kNaClIntervalRangeTreeVtbl;
695 315 : 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 303224 : void NaClIntervalRangeTreeAddInterval(struct NaClIntervalMultiset *vself,
707 : uint32_t first_val, uint32_t last_val) {
708 : struct NaClIntervalRangeTree *self;
709 : struct NaClIntervalRangeTreeNode *range_start;
710 : struct NaClIntervalRangeTreeNode *range_end;
711 :
712 303224 : self = (struct NaClIntervalRangeTree *) vself;
713 303224 : range_start = NaClIntervalRangeTreeNodeFactory(first_val, 1);
714 303224 : range_end = NaClIntervalRangeTreeNodeFactory(last_val, -1);
715 303224 : NaClIntervalRangeTreePrint(self->root);
716 303224 : (void) NaClAvlTreeInsert(&self->root, range_start);
717 303224 : NaClIntervalRangeTreePrint(self->root);
718 303224 : (void) NaClAvlTreeInsert(&self->root, range_end);
719 303224 : NaClIntervalRangeTreePrint(self->root);
720 303224 : }
721 :
722 302743 : void NaClIntervalRangeTreeRemoveInterval(struct NaClIntervalMultiset *vself,
723 : uint32_t first_val,
724 : uint32_t last_val) {
725 302743 : struct NaClIntervalRangeTree *self = (struct NaClIntervalRangeTree *) vself;
726 :
727 302743 : NaClIntervalRangeTreeRemoveVal(self, last_val, -1);
728 302743 : NaClIntervalRangeTreeRemoveVal(self, first_val, 1);
729 302743 : }
730 :
731 725709 : int NaClIntervalRangeTreeOverlapsWith(struct NaClIntervalMultiset *vself,
732 : uint32_t first_val, uint32_t last_val) {
733 725709 : struct NaClIntervalRangeTree *self = (struct NaClIntervalRangeTree *) vself;
734 : uint32_t gap_left_first;
735 : uint32_t gap_left_last;
736 :
737 : NaCl_dprintf(("OverlapsWith [%u, %u]\n", first_val, last_val));
738 725709 : if (0 != NaClAvlTreeFindValue(self->root, 0, 0, first_val, &gap_left_first)) {
739 : NaCl_dprintf(("left not in gap\n"));
740 302470 : return 1;
741 : }
742 423239 : if (0 != NaClAvlTreeFindValue(self->root, 0, 0, last_val, &gap_left_last)) {
743 : NaCl_dprintf(("right not in gap\n"));
744 81969 : return 1;
745 : }
746 :
747 : NaCl_dprintf(("gap first %u gap last %u\n", gap_left_first, gap_left_last));
748 341270 : 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 320076 : return 0;
754 : }
755 21194 : return 1;
756 : }
757 :
758 : struct NaClIntervalMultisetVtbl const kNaClIntervalRangeTreeVtbl = {
759 : NaClIntervalRangeTreeDtor,
760 : NaClIntervalRangeTreeAddInterval,
761 : NaClIntervalRangeTreeRemoveInterval,
762 : NaClIntervalRangeTreeOverlapsWith,
763 : };
|
