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 14968540 : static INLINE void NaClIntervalRangeTreePrint(
96 : struct NaClIntervalRangeTreeNode *node) {
97 : if (!DEBUG_THIS) {
98 14968540 : 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 1213440 : static void NaClIntervalRangeTreeNodeInit(
108 : struct NaClIntervalRangeTreeNode *node,
109 : uint32_t value,
110 : int lr) {
111 1213440 : node->left = NULL;
112 1213440 : node->right = NULL;
113 1213440 : node->balance = 0;
114 1213440 : node->value = value;
115 1213440 : node->value_containment_delta = lr; /* 1 or -1 for L or R */
116 1213440 : node->refcount = 1; /* caller */
117 1213440 : node->range_left = value;
118 1213440 : node->range_right = value;
119 1213440 : node->subtree_containment_delta = lr;
120 1213440 : }
121 :
122 607528 : static struct NaClIntervalRangeTreeNode *NaClIntervalRangeTreeNodeFactory(
123 : uint32_t value,
124 : int lr) {
125 : struct NaClIntervalRangeTreeNode *obj;
126 607528 : obj = (struct NaClIntervalRangeTreeNode *) malloc(sizeof *obj);
127 607528 : if (NULL == obj) {
128 0 : NaClLog(LOG_FATAL, "NaClIntervalRangeTreeNodeFactory: out of memory!\n");
129 : }
130 607528 : NaClIntervalRangeTreeNodeInit(obj, value, lr);
131 607528 : 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 7981729 : static void NaClRangeStatsUpdate(struct NaClIntervalRangeTreeNode *node) {
140 7981729 : uint32_t range_left = node->value;
141 7981729 : uint32_t range_right = node->value;
142 7981729 : uint32_t cumulative_delta = node->value_containment_delta;
143 :
144 7981729 : if (NULL != node->left) {
145 7077628 : range_left = node->left->range_left;
146 7077628 : cumulative_delta += node->left->subtree_containment_delta;
147 : }
148 7981729 : if (NULL != node->right) {
149 7243623 : range_right = node->right->range_right;
150 7243623 : cumulative_delta += node->right->subtree_containment_delta;
151 : }
152 7981729 : node->range_left = range_left;
153 7981729 : node->range_right = range_right;
154 7981729 : node->subtree_containment_delta = cumulative_delta;
155 7981729 : }
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 4572913 : 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 4572913 : if (NULL == (tmp = *treep)) {
171 605972 : *treep = node;
172 605972 : return 1;
173 : }
174 3966941 : if (node->value == tmp->value) {
175 1556 : tmp->value_containment_delta += node->value_containment_delta;
176 1556 : tmp->subtree_containment_delta += node->value_containment_delta;
177 1556 : tmp->refcount++;
178 1556 : free(node);
179 1556 : return 0;
180 3965385 : } else if (node->value < tmp->value) {
181 : /* recurse left. */
182 1896084 : higher = NaClAvlTreeInsert(&tmp->left, node);
183 1896084 : if (!higher) {
184 1293809 : NaClRangeStatsUpdate(tmp);
185 1293809 : return 0;
186 : }
187 602275 : --tmp->balance;
188 602275 : if (0 == tmp->balance) {
189 : /* height unchanged */
190 119778 : NaClRangeStatsUpdate(tmp);
191 119778 : return 0;
192 : }
193 482497 : 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 366166 : NaClRangeStatsUpdate(tmp);
199 366166 : return 1;
200 : }
201 : /* pivot */
202 116331 : 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 48200 : *treep = tmp->left;
213 48200 : tmp->left = (*treep)->right;
214 48200 : (*treep)->right = tmp;
215 48200 : (*treep)->balance = 0;
216 48200 : tmp->balance = 0;
217 :
218 48200 : tmp = *treep; /* b */
219 48200 : NaClRangeStatsUpdate(tmp->right); /* d */
220 48200 : NaClRangeStatsUpdate(tmp);
221 48200 : 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 68131 : tmp = (*treep)->left->right;
234 68131 : tmp_l = tmp->left;
235 68131 : tmp_r = tmp->right;
236 68131 : tmp->left = (*treep)->left;
237 68131 : tmp->right = (*treep);
238 68131 : *treep = tmp;
239 68131 : tmp->left->right = tmp_l;
240 68131 : tmp->right->left = tmp_r;
241 68131 : tmp->left->balance = (tmp->balance <= 0) ? 0 : -1;
242 68131 : tmp->right->balance = (tmp->balance >= 0) ? 0 : 1;
243 68131 : tmp->balance = 0;
244 68131 : NaClRangeStatsUpdate(tmp->left);
245 68131 : NaClRangeStatsUpdate(tmp->right);
246 68131 : NaClRangeStatsUpdate(tmp);
247 68131 : return 0;
248 : }
249 : } else {
250 : /* node->value > tmp->value */
251 2069301 : higher = NaClAvlTreeInsert(&tmp->right, node);
252 2069301 : if (!higher) {
253 1297133 : NaClRangeStatsUpdate(tmp);
254 1297133 : return 0;
255 : }
256 772168 : ++tmp->balance;
257 772168 : if (0 == tmp->balance) {
258 : /* height unchanged */
259 107132 : NaClRangeStatsUpdate(tmp);
260 107132 : return 0;
261 : }
262 665036 : 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 537637 : NaClRangeStatsUpdate(tmp);
268 537637 : return 1;
269 : }
270 : /* pivot */
271 127399 : 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 90935 : *treep = tmp->right;
282 90935 : tmp->right = (*treep)->left;
283 90935 : (*treep)->left = tmp;
284 90935 : (*treep)->balance = 0;
285 90935 : tmp->balance = 0;
286 :
287 90935 : tmp = *treep;
288 90935 : NaClRangeStatsUpdate(tmp->left);
289 90935 : NaClRangeStatsUpdate(tmp);
290 90935 : 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 36464 : tmp = (*treep)->right->left;
303 36464 : tmp_l = tmp->left;
304 36464 : tmp_r = tmp->right;
305 36464 : tmp->right = (*treep)->right;
306 36464 : tmp->left = (*treep);
307 36464 : *treep = tmp;
308 36464 : tmp->right->left = tmp_r;
309 36464 : tmp->left->right = tmp_l;
310 36464 : tmp->right->balance = (tmp->balance >= 0) ? 0 : 1;
311 36464 : tmp->left->balance = (tmp->balance <= 0) ? 0 : -1;
312 36464 : tmp->balance = 0;
313 36464 : NaClRangeStatsUpdate(tmp->right);
314 36464 : NaClRangeStatsUpdate(tmp->left);
315 36464 : NaClRangeStatsUpdate(tmp);
316 36464 : return 0;
317 : }
318 : }
319 : }
320 :
321 : /*
322 : * NaClAvlTreeBalanceLeft -- left subtree shrunk. Adjust balance of
323 : * node, possibly rebalancing.
324 : */
325 403466 : 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 403466 : bal = ++(*treep)->balance;
334 403466 : if (0 == bal) {
335 127643 : return;
336 : }
337 275823 : if (1 == bal) {
338 217898 : *height_changed = 0;
339 217898 : return;
340 : }
341 : /* Rebalance needed. */
342 57925 : tmp = (*treep)->right;
343 57925 : 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 40742 : (*treep)->right = tmp->left;
354 40742 : tmp->left = (*treep);
355 40742 : *treep = tmp;
356 40742 : if (0 == tmp->balance) {
357 22738 : tmp->balance = -1;
358 22738 : tmp->left->balance = 1;
359 22738 : *height_changed = 0;
360 : } else {
361 18004 : tmp->balance = 0;
362 18004 : tmp->left->balance = 0;
363 : }
364 40742 : NaClRangeStatsUpdate(tmp->left);
365 40742 : 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 17183 : tmp = tmp->left; /* d */
378 17183 : tmp_l = tmp->left;
379 17183 : tmp_r = tmp->right;
380 17183 : tmp->left = *treep;
381 17183 : tmp->right = (*treep)->right;
382 17183 : *treep = tmp;
383 17183 : tmp->left->right = tmp_l;
384 17183 : tmp->right->left = tmp_r;
385 17183 : tmp->left->balance = (tmp->balance > 0) ? -1 : 0;
386 17183 : tmp->right->balance = (tmp->balance < 0) ? 1 : 0;
387 17183 : tmp->balance = 0;
388 : /*
389 : * *h == 1 remains true.
390 : */
391 17183 : NaClRangeStatsUpdate(tmp->left);
392 17183 : NaClRangeStatsUpdate(tmp->right);
393 17183 : NaClRangeStatsUpdate(tmp);
394 : }
395 : }
396 :
397 : /*
398 : * NaClAvlTreeBalanceRight -- right subtree shrunk. Adjust balance of
399 : * node, possibly rebalancing.
400 : */
401 505054 : 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 505054 : bal = --(*treep)->balance;
410 505054 : if (0 == bal) {
411 233126 : return;
412 : }
413 271928 : if (-1 == bal) {
414 205308 : *height_changed = 0;
415 205308 : return;
416 : }
417 : /* Rebalance needed. */
418 66620 : tmp = (*treep)->left;
419 66620 : 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 40168 : (*treep)->left = tmp->right;
431 40168 : tmp->right = (*treep);
432 40168 : *treep = tmp;
433 40168 : if (0 == tmp->balance) {
434 23116 : tmp->balance = 1;
435 23116 : tmp->right->balance = -1;
436 23116 : *height_changed = 0;
437 : } else {
438 17052 : tmp->balance = 0;
439 17052 : tmp->right->balance = 0;
440 : }
441 40168 : NaClRangeStatsUpdate(tmp->right);
442 40168 : 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 26452 : tmp = tmp->right; /* d */
455 26452 : tmp_l = tmp->left;
456 26452 : tmp_r = tmp->right;
457 26452 : tmp->left = (*treep)->left;
458 26452 : tmp->right = *treep;
459 26452 : *treep = tmp;
460 26452 : tmp->left->right = tmp_l;
461 26452 : tmp->right->left = tmp_r;
462 26452 : tmp->left->balance = (tmp->balance > 0) ? -1 : 0;
463 26452 : tmp->right->balance = (tmp->balance < 0) ? 1 : 0;
464 26452 : tmp->balance = 0;
465 : /*
466 : * *h == 1 remains true.
467 : */
468 26452 : NaClRangeStatsUpdate(tmp->left);
469 26452 : NaClRangeStatsUpdate(tmp->right);
470 26452 : NaClRangeStatsUpdate(tmp);
471 : }
472 : }
473 :
474 330134 : static struct NaClIntervalRangeTreeNode *NaClAvlFindRightMost(
475 : struct NaClIntervalRangeTreeNode **treep,
476 : int *height_changed) {
477 : struct NaClIntervalRangeTreeNode *tmp;
478 :
479 330134 : if (NULL != (*treep)->right) {
480 182220 : tmp = NaClAvlFindRightMost(&(*treep)->right, height_changed);
481 182220 : NaClRangeStatsUpdate(*treep);
482 182220 : if (*height_changed) {
483 121738 : NaClAvlTreeBalanceRight(treep, height_changed);
484 : }
485 182220 : return tmp;
486 : }
487 147914 : tmp = *treep;
488 147914 : *treep = tmp->left;
489 147914 : *height_changed = 1;
490 147914 : return tmp;
491 : }
492 :
493 92256 : static struct NaClIntervalRangeTreeNode *NaClAvlFindLeftMost(
494 : struct NaClIntervalRangeTreeNode **treep,
495 : int *height_changed) {
496 : struct NaClIntervalRangeTreeNode *tmp;
497 :
498 92256 : if (NULL != (*treep)->left) {
499 52478 : tmp = NaClAvlFindLeftMost(&(*treep)->left, height_changed);
500 52478 : NaClRangeStatsUpdate(*treep);
501 52478 : if (*height_changed) {
502 36212 : NaClAvlTreeBalanceLeft(treep, height_changed);
503 : }
504 52478 : return tmp;
505 : }
506 39778 : tmp = *treep;
507 39778 : *treep = tmp->right;
508 39778 : *height_changed = 1;
509 39778 : return tmp;
510 : }
511 :
512 3558816 : 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 3558816 : 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 3558816 : NaClIntervalRangeTreePrint(*treep);
525 3558816 : if (key->value < (*treep)->value) {
526 1417355 : p = NaClAvlTreeExtract(&(*treep)->left, key, height_changed);
527 1417355 : NaClRangeStatsUpdate(*treep);
528 1417355 : if (*height_changed) {
529 283767 : NaClAvlTreeBalanceLeft(treep, height_changed);
530 : }
531 1417355 : return p;
532 2141461 : } else if (key->value > (*treep)->value) {
533 1535549 : p = NaClAvlTreeExtract(&(*treep)->right, key, height_changed);
534 1535549 : NaClRangeStatsUpdate(*treep);
535 1535549 : if (*height_changed) {
536 361107 : NaClAvlTreeBalanceRight(treep, height_changed);
537 : }
538 1535549 : return p;
539 : } else {
540 : /*
541 : * found elt
542 : */
543 605912 : p = *treep;
544 605912 : if (0 != --p->refcount) {
545 1556 : p->value_containment_delta -= key->value_containment_delta;
546 1556 : p->subtree_containment_delta -= key->value_containment_delta;
547 1556 : return NULL;
548 : }
549 : /* zero refcount, should delete */
550 604356 : if (NULL == p->right) {
551 385251 : *treep = p->left;
552 385251 : *height_changed = 1;
553 219105 : } else if (NULL == p->left) {
554 31413 : *treep = p->right;
555 31413 : *height_changed = 1;
556 187692 : } else if (p->balance <= 0) {
557 147914 : tmp = NaClAvlFindRightMost(&p->left, height_changed);
558 147914 : tmp->left = p->left;
559 147914 : tmp->right = p->right;
560 147914 : tmp->balance = p->balance;
561 147914 : NaClRangeStatsUpdate(tmp);
562 147914 : *treep = tmp;
563 147914 : if (*height_changed) {
564 83487 : NaClAvlTreeBalanceLeft(treep, height_changed);
565 : }
566 : } else {
567 39778 : tmp = NaClAvlFindLeftMost(&p->right, height_changed);
568 39778 : tmp->left = p->left;
569 39778 : tmp->right = p->right;
570 39778 : tmp->balance = p->balance;
571 39778 : NaClRangeStatsUpdate(tmp);
572 39778 : *treep = tmp;
573 39778 : if (*height_changed) {
574 22209 : NaClAvlTreeBalanceRight(treep, height_changed);
575 : }
576 : }
577 604356 : p->left = NULL;
578 604356 : p->right = NULL;
579 604356 : return p;
580 : }
581 : }
582 :
583 605912 : static struct NaClIntervalRangeTreeNode *NaClIntervalRangeTreeExtract(
584 : struct NaClIntervalRangeTree *self,
585 : struct NaClIntervalRangeTreeNode *keyp) {
586 605912 : int height_changed = 0;
587 :
588 605912 : return NaClAvlTreeExtract(&self->root, keyp, &height_changed);
589 : }
590 :
591 605912 : 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 605912 : NaClIntervalRangeTreeNodeInit(&key, value, lr);
599 605912 : zero_ref_node = NaClIntervalRangeTreeExtract(self, &key);
600 605912 : if (NULL != zero_ref_node) {
601 604356 : free(zero_ref_node);
602 : }
603 : NaCl_dprintf(("result tree\n"));
604 605912 : NaClIntervalRangeTreePrint(self->root);
605 605912 : }
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 9892520 : 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 9892520 : NaClIntervalRangeTreePrint(tree);
635 9892520 : if (NULL == tree) {
636 1540363 : *gap_left = left_range;
637 1540363 : return left_delta;
638 : }
639 8352157 : if (value < tree->value) {
640 4235489 : return NaClAvlTreeFindValue(tree->left, left_delta, left_range, value,
641 : gap_left);
642 4116668 : } 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 4116636 : delta = left_delta;
667 4116636 : if (NULL != tree->left) {
668 3588828 : delta += tree->left->subtree_containment_delta;
669 : }
670 4116636 : delta += tree->value_containment_delta;
671 4116636 : left_range = tree->value + 1;
672 :
673 4116636 : return NaClAvlTreeFindValue(tree->right,
674 : delta,
675 : left_range,
676 : value,
677 : gap_left);
678 : }
679 : }
680 :
681 3228 : void NaClAvlTreeFree(struct NaClIntervalRangeTreeNode *t) {
682 3228 : if (NULL == t) {
683 4844 : return;
684 : }
685 1612 : NaClAvlTreeFree(t->left);
686 1612 : t->left = NULL;
687 1612 : NaClAvlTreeFree(t->right);
688 1612 : t->right = NULL;
689 1612 : free(t);
690 : }
691 :
692 316 : int NaClIntervalRangeTreeCtor(struct NaClIntervalRangeTree *self) {
693 316 : self->root = NULL;
694 316 : self->base.vtbl = &kNaClIntervalRangeTreeVtbl;
695 316 : 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 303764 : 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 303764 : self = (struct NaClIntervalRangeTree *) vself;
713 303764 : range_start = NaClIntervalRangeTreeNodeFactory(first_val, 1);
714 303764 : range_end = NaClIntervalRangeTreeNodeFactory(last_val, -1);
715 303764 : NaClIntervalRangeTreePrint(self->root);
716 303764 : (void) NaClAvlTreeInsert(&self->root, range_start);
717 303764 : NaClIntervalRangeTreePrint(self->root);
718 303764 : (void) NaClAvlTreeInsert(&self->root, range_end);
719 303764 : NaClIntervalRangeTreePrint(self->root);
720 303764 : }
721 :
722 302956 : void NaClIntervalRangeTreeRemoveInterval(struct NaClIntervalMultiset *vself,
723 : uint32_t first_val,
724 : uint32_t last_val) {
725 302956 : struct NaClIntervalRangeTree *self = (struct NaClIntervalRangeTree *) vself;
726 :
727 302956 : NaClIntervalRangeTreeRemoveVal(self, last_val, -1);
728 302956 : NaClIntervalRangeTreeRemoveVal(self, first_val, 1);
729 302956 : }
730 :
731 897474 : int NaClIntervalRangeTreeOverlapsWith(struct NaClIntervalMultiset *vself,
732 : uint32_t first_val, uint32_t last_val) {
733 897474 : 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 897474 : if (0 != NaClAvlTreeFindValue(self->root, 0, 0, first_val, &gap_left_first)) {
739 : NaCl_dprintf(("left not in gap\n"));
740 254553 : return 1;
741 : }
742 642921 : if (0 != NaClAvlTreeFindValue(self->root, 0, 0, last_val, &gap_left_last)) {
743 : NaCl_dprintf(("right not in gap\n"));
744 78706 : return 1;
745 : }
746 :
747 : NaCl_dprintf(("gap first %u gap last %u\n", gap_left_first, gap_left_last));
748 564215 : 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 541043 : return 0;
754 : }
755 23172 : return 1;
756 : }
757 :
758 : struct NaClIntervalMultisetVtbl const kNaClIntervalRangeTreeVtbl = {
759 : NaClIntervalRangeTreeDtor,
760 : NaClIntervalRangeTreeAddInterval,
761 : NaClIntervalRangeTreeRemoveInterval,
762 : NaClIntervalRangeTreeOverlapsWith,
763 : };
|
