Line data Source code
1 : /*
2 : * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
3 : */
4 :
5 : #ifndef PATRICIA_H
6 : #define PATRICIA_H
7 :
8 : #include <string>
9 : #include <cstring>
10 : #include <boost/intrusive/detail/parent_from_member.hpp>
11 : #include <boost/iterator/iterator_facade.hpp>
12 :
13 : #define IS_INT_NODE(node) (node->intnode_)
14 :
15 : namespace Patricia {
16 : class Node {
17 : public:
18 1495 : Node() {
19 1495 : left_ = NULL;
20 1495 : right_ = NULL;
21 1495 : intnode_ = false;
22 1495 : bitpos_ = 0;
23 1495 : }
24 :
25 : Node *left_;
26 : Node *right_;
27 : bool intnode_;
28 : std::size_t bitpos_;
29 : };
30 :
31 : class TreeBase {
32 : public:
33 12 : TreeBase() {
34 12 : root_ = NULL;
35 12 : nodes_ = 0;
36 12 : int_nodes_ = 0;
37 12 : }
38 :
39 : int nodes_;
40 : int int_nodes_;
41 : Node *root_;
42 : };
43 :
44 : template <class D, Node D::* P, class K>
45 : class Tree : private TreeBase {
46 : public:
47 6848 : Tree() : TreeBase() {
48 6848 : }
49 :
50 : class Iterator : public boost::iterator_facade<Iterator,
51 : D *,
52 : boost::forward_traversal_tag,
53 : D *> {
54 : public:
55 120 : Iterator() : data_(NULL) {}
56 3 : explicit Iterator(Tree<D, P, K> *tree, D *data) : tree_(tree), data_(data) {
57 3 : }
58 :
59 : private:
60 : friend class boost::iterator_core_access;
61 :
62 116 : void increment() {
63 116 : data_ = tree_->GetNext(data_);
64 116 : }
65 119 : bool equal(const Iterator &it) const {
66 119 : return data_ == it.data_;
67 : }
68 116 : D * dereference() const {
69 116 : return data_;
70 : }
71 : Tree<D, P, K> *tree_;
72 : D *data_;
73 : };
74 :
75 3 : Iterator begin() {
76 3 : return Iterator(this, GetNext(NULL));
77 : }
78 :
79 119 : Iterator end() {
80 119 : return Iterator();
81 : }
82 :
83 : Iterator LowerBound(D * data) {
84 : return Iterator(this, FindNext(data));
85 : }
86 :
87 1497 : std::size_t Size() {
88 1497 : return nodes_;
89 : }
90 :
91 5478 : bool Insert(D * data) {
92 5478 : return InsertNode(DataToNode(data));
93 : }
94 :
95 5536 : bool Remove(D * data) {
96 5536 : return RemoveNode(DataToNode(data));
97 : }
98 :
99 17850 : D * Find(const D * data) {
100 17850 : return NodeToData(FindNode(DataToNode(data)));
101 : }
102 :
103 116 : D * FindNext(const D * data) {
104 116 : return NodeToData(FindNextNode(DataToNode(data)));
105 : }
106 :
107 4 : D * LPMFind(const D * data) {
108 4 : return NodeToData(FindBestMatchNode(DataToNode(data)));
109 : }
110 :
111 26016 : D * GetNext(D * data) {
112 26016 : return NodeToData(GetNextNode(DataToNode(data)));
113 : }
114 :
115 58 : D * GetPrev(const D * data) {
116 58 : return NodeToData(GetPrevNode(DataToNode(data)));
117 : }
118 :
119 1 : D * GetLast() {
120 1 : return NodeToData(GetLastNode());
121 : }
122 :
123 : private:
124 18027 : const Node *DataToNode (const D * data) {
125 18027 : if (data) {
126 18027 : return static_cast<const Node *>(&(data->*P));
127 : } else {
128 0 : return NULL;
129 : }
130 : }
131 :
132 37030 : Node *DataToNode (D * data) {
133 37030 : if (data) {
134 18796 : return static_cast<Node *>(&(data->*P));
135 : } else {
136 18234 : return NULL;
137 : }
138 : }
139 :
140 186407 : const D *NodeToData (const Node * node) {
141 186407 : if (node) {
142 186407 : return boost::intrusive::detail::parent_from_member<D, Node>(node, P);
143 : } else {
144 0 : return NULL;
145 : }
146 : }
147 :
148 97469 : D *NodeToData (Node * node) {
149 97469 : if (node) {
150 74934 : return boost::intrusive::detail::parent_from_member<D, Node>(node, P);
151 : } else {
152 22535 : return NULL;
153 : }
154 : }
155 :
156 5478 : bool InsertNode(Node *node) {
157 : Node * p, * x, *l;
158 :
159 : // Start at the root_
160 5478 : p = NULL;
161 5478 : x = root_;
162 13150 : while (x) {
163 10895 : if (x->bitpos_ >= K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
164 3208 : break;
165 : }
166 7687 : p = x;
167 7687 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
168 7687 : if (x && (p->bitpos_ >= x->bitpos_)) {
169 : /* no x to deal with */
170 15 : x = NULL;
171 15 : break;
172 : }
173 : }
174 :
175 5478 : std::size_t i = 0;
176 5478 : l = x ? x : p;
177 : // Find the first bit that does not match.
178 5478 : if (l) {
179 : /* if l is internal node pick the left_ node to compare */
180 3332 : if (Compare(node, l, 0, i)) {
181 : // The key already exists
182 290 : return false;
183 : }
184 :
185 3042 : if (i != K::BitLength(NodeToData(node)) || i != l->bitpos_) {
186 3042 : p = NULL;
187 3042 : x = root_;
188 8085 : while (x && x->bitpos_ <= i && x->bitpos_ < K::BitLength(NodeToData(node))) {
189 5058 : p = x;
190 5058 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
191 5058 : if (x && (p->bitpos_ >= x->bitpos_)) {
192 : /* no x to deal with */
193 15 : x = NULL;
194 15 : break;
195 : }
196 : }
197 : }
198 : }
199 :
200 5188 : nodes_++;
201 5188 : node->left_ = NULL;
202 5188 : node->right_ = NULL;
203 5188 : node->bitpos_ = K::BitLength(NodeToData(node));;
204 :
205 5188 : if (x) {
206 2927 : if (x->bitpos_ == i) {
207 : /* has to be an internal node */
208 2 : node->right_ = x->right_;
209 2 : node->left_ = x->left_;
210 : /* rightmost guy of the left_ subtree will be pointing to x that needs to point to node now. */
211 : //node->right_ = RewireRightMost(node, x->left_);
212 2 : RewireRightMost(node, x->left_);
213 2 : delete x;
214 2 : int_nodes_--;
215 2 : l = node;
216 : } else {
217 : /* key BitLength of x has to be greater than node key BitLength */
218 2925 : if (i == K::BitLength(NodeToData(node))) {
219 22 : if (GetBit(l, i)) {
220 0 : node->right_ = x;
221 : } else {
222 22 : node->left_ = x;
223 : /* right_ most node of the left_ sub tree should point to node */
224 22 : node->right_ = RewireRightMost(node, x);
225 : }
226 22 : l = node;
227 : } else {
228 : /* allocate internal node */
229 2903 : l = new Node;
230 2903 : int_nodes_++;
231 2903 : l->bitpos_ = i;
232 2903 : l->intnode_ = true;
233 2903 : if (GetBit(node, i)) {
234 2050 : l->left_ = x;
235 2050 : l->right_ = node;
236 : /* right_ most node of the left_ sub tree should point to l */
237 2050 : node->right_ = RewireRightMost(l, x);
238 : } else {
239 853 : l->left_ = node;
240 853 : l->right_ = x;
241 853 : node->right_ = l;
242 : }
243 : }
244 : }
245 : } else {
246 2261 : if (p) {
247 115 : if (GetBit(node, p->bitpos_)) {
248 15 : node->right_ = p->right_;
249 : } else {
250 100 : node->right_ = p;
251 : }
252 : }
253 2261 : l = node;
254 : }
255 :
256 5188 : if (p) {
257 1691 : if (GetBit(node, p->bitpos_)) {
258 1027 : p->right_ = l;
259 : } else {
260 664 : p->left_ = l;
261 : }
262 : } else {
263 3497 : root_ = l;
264 : }
265 :
266 5188 : return true;
267 : }
268 :
269 5536 : bool RemoveNode(Node * node) {
270 5536 : Node * pPrev = NULL;
271 5536 : Node * p = NULL;
272 5536 : Node * x = root_;
273 :
274 13192 : while (x) {
275 13178 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
276 41 : x = NULL;
277 41 : break;
278 13137 : } else if (x->bitpos_ == K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
279 5479 : break;
280 : }
281 7658 : pPrev = p;
282 7658 : p = x;
283 7658 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
284 7658 : if (x && (p->bitpos_ >= x->bitpos_)) {
285 : /* no x to deal with */
286 2 : x = NULL;
287 2 : break;
288 : }
289 : }
290 :
291 5536 : if(!x || !Compare(node, x)){
292 348 : return false;
293 : }
294 :
295 5188 : Node * t = NULL;
296 :
297 5188 : if (x->left_ && x->right_ && x->bitpos_ < x->right_->bitpos_) {
298 : /* need to allocate internal node to replace the going node */
299 14 : t = new Node;
300 14 : t->bitpos_ = x->bitpos_;
301 14 : t->intnode_ = true;
302 14 : int_nodes_++;
303 14 : t->left_ = x->left_;
304 14 : t->right_ = x->right_;
305 14 : RewireRightMost(t, x->left_);
306 14 : if (!p) {
307 0 : root_ =t ;
308 14 : } else if (GetBit(x, p->bitpos_)) {
309 0 : p->right_ = t;
310 : } else {
311 14 : p->left_ = t;
312 : }
313 5174 : } else if (x->left_) {
314 100 : if (!p) {
315 28 : root_ = x->left_;
316 72 : } else if (GetBit(x, p->bitpos_)) {
317 4 : p->right_ = x->left_;
318 : } else {
319 68 : p->left_ = x->left_;
320 : }
321 100 : RewireRightMost(x->right_, x->left_);
322 5074 : } else if (x->right_ && x->bitpos_ < x->right_->bitpos_) {
323 0 : if (!p) {
324 0 : root_ = x->right_;
325 0 : } else if (GetBit(x, p->bitpos_)) {
326 0 : p->right_ = x->right_;
327 : } else {
328 0 : p->left_ = x->right_;
329 : }
330 : } else {
331 5074 : if (!p) {
332 2146 : root_ = NULL;
333 2928 : } else if (IS_INT_NODE(p)) {
334 2915 : if (GetBit(x, p->bitpos_)){
335 886 : t = p->left_;
336 : //RewireRightMost((pPrev->left_ == p) ? pPrev : NULL, t);
337 886 : RewireRightMost(x->right_, t);
338 : } else {
339 2029 : t = p->right_;
340 : }
341 2915 : if (!pPrev) {
342 1307 : root_ = t;
343 1608 : } else if (GetBit(x, pPrev->bitpos_)) {
344 531 : pPrev->right_ = t;
345 : } else {
346 1077 : pPrev->left_ = t;
347 : }
348 2915 : delete p;
349 2915 : int_nodes_--;
350 : } else {
351 13 : if (GetBit(x, p->bitpos_)) {
352 3 : p->right_ = x->right_;
353 : } else {
354 10 : p->left_ = NULL;
355 : }
356 : }
357 : }
358 :
359 5188 : nodes_--;
360 5188 : node->left_ = NULL;
361 5188 : node->right_ = NULL;
362 5188 : return true;
363 : }
364 :
365 17850 : Node * FindNode(const Node * node) {
366 : Node * p, * x;
367 :
368 17850 : p = NULL;
369 17850 : x = root_;
370 33087 : while (x) {
371 29532 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
372 1 : x = NULL;
373 1 : break;
374 29531 : } else if (x->bitpos_ == K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
375 14294 : break;
376 : }
377 15237 : p = x;
378 15237 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
379 15237 : if (x && (p->bitpos_ >= x->bitpos_)) {
380 : /* no x to deal with */
381 0 : x = NULL;
382 0 : break;
383 : }
384 : }
385 :
386 17850 : if(!x || !Compare(node, x)){
387 4616 : return NULL;
388 : }
389 :
390 13234 : return x;
391 : }
392 :
393 116 : Node * FindNextNode(const Node * node) {
394 : Node * p, * x, *l;
395 116 : std::size_t i = 0;
396 :
397 116 : p = NULL;
398 116 : l = NULL;
399 116 : x = root_;
400 978 : while (x) {
401 977 : if (!IS_INT_NODE(x)) {
402 378 : if (Compare(node, x, i, i)) {
403 58 : return GetNextNode(x);
404 : }
405 320 : if (x->bitpos_ > K::BitLength(NodeToData(node)) || i != x->bitpos_) {
406 56 : break;
407 : }
408 264 : l = x;
409 : }
410 863 : p = x;
411 863 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
412 863 : if (x && (p->bitpos_ >= x->bitpos_)) {
413 1 : break;
414 : }
415 : }
416 :
417 58 : if (l) {
418 57 : x = l;
419 247 : while (x && x->bitpos_ <= i) {
420 191 : l = x;
421 191 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
422 191 : if (x && (l->bitpos_ >= x->bitpos_)) {
423 1 : break;
424 : }
425 : }
426 57 : if (K::BitLength(NodeToData(node)) != l->bitpos_) {
427 56 : if (GetBit(node, l->bitpos_)) {
428 27 : if (!x) {
429 0 : return NULL;
430 : }
431 27 : if (l->bitpos_ > x->bitpos_) {
432 2 : while (x && l->bitpos_ > x->bitpos_) {
433 1 : l = x;
434 1 : x = x->right_;
435 : }
436 1 : l = x;
437 26 : } else if (GetBit(node, i)) {
438 : /* x is on left */
439 18 : while (x->right_ &&
440 18 : x->bitpos_ < x->right_->bitpos_) {
441 4 : x = x->right_;
442 : }
443 14 : l = x;
444 14 : x = x->right_;
445 33 : while (x && l->bitpos_ > x->bitpos_) {
446 19 : l = x;
447 19 : x = x->right_;
448 : }
449 14 : l = x;
450 : } else {
451 12 : l = x;
452 : }
453 : } else {
454 29 : if (!x || GetBit(node, i)) {
455 10 : x = l->right_;
456 10 : while (x && l->bitpos_ > x->bitpos_) {
457 0 : l = x;
458 0 : x = x->right_;
459 : }
460 10 : l = x;
461 : } else {
462 19 : l = x;
463 : }
464 : }
465 :
466 56 : if (x && !IS_INT_NODE(x)) {
467 27 : return x;
468 : }
469 : }
470 30 : return GetNextNode(l);
471 : } else {
472 1 : if (!GetBit(node, i)) {
473 : /* all elements of the tree are on right */
474 1 : return x;
475 : }
476 : }
477 :
478 0 : return NULL;
479 : }
480 :
481 4 : Node * FindBestMatchNode(const Node * node) {
482 : Node * p, * x, *l;
483 4 : std::size_t i = 0;
484 :
485 4 : l = NULL;
486 4 : p = NULL;
487 4 : x = root_;
488 33 : while (x) {
489 31 : if (!IS_INT_NODE(x)) {
490 14 : if (Compare(node, x, i, i)) {
491 1 : return x;
492 : }
493 13 : if (i == x->bitpos_) {
494 10 : l = x;
495 : }
496 : }
497 30 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
498 1 : break;
499 : }
500 29 : p = x;
501 29 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
502 29 : if (x && (p->bitpos_ >= x->bitpos_)) {
503 0 : break;
504 : }
505 : }
506 :
507 3 : return l;
508 : }
509 :
510 26104 : Node * GetNextNode(Node * node) {
511 : Node *x, *l;
512 :
513 26104 : if (!root_) {
514 17147 : return NULL;
515 : }
516 :
517 8957 : x = root_;
518 8957 : if (node || IS_INT_NODE(x)) {
519 8349 : if (node) {
520 7870 : x = node;
521 : }
522 8349 : l = x;
523 22808 : while (x) {
524 22037 : if (x->bitpos_ < l->bitpos_) {
525 6925 : l = x;
526 6925 : x = l->right_;
527 : } else {
528 15112 : l = x;
529 15112 : x = l->left_ ? l->left_ : l->right_;
530 : }
531 22037 : if (x && x->bitpos_ > l->bitpos_ &&
532 14341 : !IS_INT_NODE(x)) {
533 7578 : break;
534 : }
535 : }
536 : }
537 :
538 8957 : return x;
539 : }
540 :
541 58 : Node * GetPrevNode(const Node * node) {
542 : Node * p, * x, *l, *r, *right_turn, *greatest_partial;
543 :
544 58 : p = NULL;
545 58 : l = NULL;
546 58 : x = root_;
547 58 : right_turn = NULL;
548 58 : greatest_partial = NULL;
549 501 : while (x) {
550 501 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
551 0 : x = NULL;
552 0 : break;
553 501 : } else if (x->bitpos_ == K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
554 58 : break;
555 : }
556 443 : p = x;
557 443 : if (GetBit(node, x->bitpos_)) {
558 161 : right_turn = x;
559 161 : x = x->right_;
560 : } else {
561 282 : if (!IS_INT_NODE(x)) {
562 131 : greatest_partial = x;
563 : }
564 282 : x = x->left_;
565 : }
566 443 : if (x && (p->bitpos_ >= x->bitpos_)) {
567 0 : x = NULL;
568 0 : break;
569 : }
570 : }
571 :
572 58 : if (!x || !Compare(node, x)) {
573 0 : return NULL;
574 : }
575 :
576 58 : if (right_turn && greatest_partial) {
577 54 : if (greatest_partial->bitpos_ > right_turn->bitpos_) {
578 5 : return greatest_partial;
579 : }
580 : }
581 :
582 53 : if (!right_turn) {
583 4 : return greatest_partial;
584 : }
585 :
586 49 : x = right_turn->left_;
587 98 : while (x) {
588 98 : l = x->left_;
589 98 : r = x->right_;
590 98 : if (r && r->bitpos_ > x->bitpos_) {
591 44 : x = r;
592 54 : } else if (l) {
593 5 : x = l;
594 : } else {
595 49 : return x;
596 : }
597 : }
598 :
599 0 : return x;
600 : }
601 :
602 1 : Node * GetLastNode() {
603 : Node *x;
604 :
605 1 : if (!root_) {
606 0 : return NULL;
607 : }
608 :
609 1 : x = root_;
610 8 : while (x) {
611 8 : if (x->right_) {
612 7 : if (x->right_->bitpos_ < x->bitpos_) {
613 2 : if (!x->left_) {
614 1 : return x;
615 : }
616 1 : x = x->left_;
617 : } else {
618 5 : x = x->right_;
619 : }
620 : } else {
621 1 : if (!x->left_) {
622 0 : return x;
623 : }
624 1 : x = x->left_;
625 : }
626 : }
627 :
628 0 : return x;
629 : }
630 :
631 78831 : bool GetBit(const Node * node, std::size_t pos) {
632 78831 : const D * data = NodeToData(node);
633 78831 : if (pos >= K::BitLength(data)) {
634 85 : return false;
635 : }
636 :
637 78746 : return K::ByteValue(data, pos >> 3) & (0x80 >> (pos & 7));
638 : }
639 :
640 19830 : bool Compare(const Node *node_left, const Node *node_right) {
641 19830 : const D * data_left = NodeToData(node_left);
642 19830 : const D * data_right = NodeToData(node_right);
643 19830 : if (K::BitLength(data_left) != K::BitLength(data_right)) {
644 0 : return false;
645 : }
646 :
647 19830 : std::size_t byteLen = K::BitLength(data_left) >> 3;
648 : std::size_t pos;
649 :
650 156361 : for (pos = 0; pos < byteLen; ++pos) {
651 137882 : if (K::ByteValue(data_left, pos) != K::ByteValue(data_right, pos)) {
652 1351 : return false;
653 : }
654 : }
655 :
656 18619 : for (pos <<= 3; pos < K::BitLength(data_left); ++pos) {
657 140 : if (GetBit(node_left, pos) != GetBit(node_right, pos)) {
658 0 : return false;
659 : }
660 : }
661 :
662 18479 : return true;
663 : }
664 :
665 3724 : bool Compare(const Node *node_left, const Node *node_right, std::size_t start, std::size_t& pos) {
666 3724 : const D * data_left = NodeToData(node_left);
667 3724 : const D * data_right = NodeToData(node_right);
668 : std::size_t shortLen;
669 :
670 : bool isEqual;
671 :
672 3724 : if (K::BitLength(data_left) < K::BitLength(data_right)) {
673 50 : shortLen = K::BitLength(data_left);
674 50 : isEqual = false;
675 : } else {
676 3674 : shortLen = K::BitLength(data_right);
677 3674 : isEqual = (K::BitLength(data_left) == K::BitLength(data_right));
678 : }
679 :
680 3724 : std::size_t byteLen = shortLen >> 3;
681 :
682 18224 : for (pos = start >> 3; pos < byteLen; ++pos) {
683 17441 : if (K::ByteValue(data_left, pos) != K::ByteValue(data_right, pos)) {
684 2941 : break;
685 : }
686 : }
687 :
688 3724 : pos <<= 3;
689 3724 : if (pos < start) {
690 1 : pos = start;
691 : }
692 :
693 16732 : for (; pos < shortLen; ++pos) {
694 15961 : if (GetBit(node_left, pos) != GetBit(node_right, pos)) {
695 2953 : return false;
696 : }
697 : }
698 :
699 771 : return isEqual;
700 : }
701 :
702 3074 : Node * RewireRightMost (Node *p, Node *x) {
703 : Node *pRight;
704 3074 : if (!x) {
705 0 : return NULL;
706 : }
707 :
708 4324 : while (x->right_ && x->right_->bitpos_ > x->bitpos_) {
709 1250 : x = x->right_;
710 : }
711 3074 : pRight = x->right_;
712 3074 : x->right_ = p;
713 3074 : return pRight;
714 : }
715 :
716 :
717 : };
718 :
719 : };
720 :
721 : #endif /* PATRICIA_H */
722 :
|
