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