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 6857 : Tree() : TreeBase() {
48 6857 : }
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 5485 : bool Insert(D * data) {
92 5485 : return InsertNode(DataToNode(data));
93 : }
94 :
95 5543 : bool Remove(D * data) {
96 5543 : return RemoveNode(DataToNode(data));
97 : }
98 :
99 18099 : D * Find(const D * data) {
100 18099 : 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 26036 : D * GetNext(D * data) {
112 26036 : 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 18276 : const Node *DataToNode (const D * data) {
125 18276 : if (data) {
126 18276 : return static_cast<const Node *>(&(data->*P));
127 : } else {
128 0 : return NULL;
129 : }
130 : }
131 :
132 37064 : Node *DataToNode (D * data) {
133 37064 : if (data) {
134 18807 : return static_cast<Node *>(&(data->*P));
135 : } else {
136 18257 : return NULL;
137 : }
138 : }
139 :
140 188211 : const D *NodeToData (const Node * node) {
141 188211 : if (node) {
142 188211 : return boost::intrusive::detail::parent_from_member<D, Node>(node, P);
143 : } else {
144 0 : return NULL;
145 : }
146 : }
147 :
148 97757 : D *NodeToData (Node * node) {
149 97757 : if (node) {
150 75115 : return boost::intrusive::detail::parent_from_member<D, Node>(node, P);
151 : } else {
152 22642 : return NULL;
153 : }
154 : }
155 :
156 5485 : bool InsertNode(Node *node) {
157 : Node * p, * x, *l;
158 :
159 : // Start at the root_
160 5485 : p = NULL;
161 5485 : x = root_;
162 13176 : while (x) {
163 10913 : if (x->bitpos_ >= K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
164 3207 : break;
165 : }
166 7706 : p = x;
167 7706 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
168 7706 : if (x && (p->bitpos_ >= x->bitpos_)) {
169 : /* no x to deal with */
170 15 : x = NULL;
171 15 : break;
172 : }
173 : }
174 :
175 5485 : std::size_t i = 0;
176 5485 : l = x ? x : p;
177 : // Find the first bit that does not match.
178 5485 : if (l) {
179 : /* if l is internal node pick the left_ node to compare */
180 3331 : if (Compare(node, l, 0, i)) {
181 : // The key already exists
182 290 : return false;
183 : }
184 :
185 3041 : if (i != K::BitLength(NodeToData(node)) || i != l->bitpos_) {
186 3041 : p = NULL;
187 3041 : x = root_;
188 8102 : while (x && x->bitpos_ <= i && x->bitpos_ < K::BitLength(NodeToData(node))) {
189 5076 : p = x;
190 5076 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
191 5076 : 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 5195 : nodes_++;
201 5195 : node->left_ = NULL;
202 5195 : node->right_ = NULL;
203 5195 : node->bitpos_ = K::BitLength(NodeToData(node));;
204 :
205 5195 : if (x) {
206 2926 : 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 2924 : 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 2902 : l = new Node;
230 2902 : int_nodes_++;
231 2902 : l->bitpos_ = i;
232 2902 : l->intnode_ = true;
233 2902 : if (GetBit(node, i)) {
234 2001 : l->left_ = x;
235 2001 : l->right_ = node;
236 : /* right_ most node of the left_ sub tree should point to l */
237 2001 : node->right_ = RewireRightMost(l, x);
238 : } else {
239 901 : l->left_ = node;
240 901 : l->right_ = x;
241 901 : node->right_ = l;
242 : }
243 : }
244 : }
245 : } else {
246 2269 : 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 2269 : l = node;
254 : }
255 :
256 5195 : if (p) {
257 1681 : if (GetBit(node, p->bitpos_)) {
258 1007 : p->right_ = l;
259 : } else {
260 674 : p->left_ = l;
261 : }
262 : } else {
263 3514 : root_ = l;
264 : }
265 :
266 5195 : return true;
267 : }
268 :
269 5543 : bool RemoveNode(Node * node) {
270 5543 : Node * pPrev = NULL;
271 5543 : Node * p = NULL;
272 5543 : Node * x = root_;
273 :
274 13181 : while (x) {
275 13167 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
276 41 : x = NULL;
277 41 : break;
278 13126 : } else if (x->bitpos_ == K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
279 5486 : break;
280 : }
281 7640 : pPrev = p;
282 7640 : p = x;
283 7640 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
284 7640 : if (x && (p->bitpos_ >= x->bitpos_)) {
285 : /* no x to deal with */
286 2 : x = NULL;
287 2 : break;
288 : }
289 : }
290 :
291 5543 : if(!x || !Compare(node, x)){
292 348 : return false;
293 : }
294 :
295 5195 : Node * t = NULL;
296 :
297 5195 : 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 5181 : } 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 5081 : } 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 5081 : if (!p) {
332 2154 : root_ = NULL;
333 2927 : } else if (IS_INT_NODE(p)) {
334 2914 : if (GetBit(x, p->bitpos_)){
335 922 : t = p->left_;
336 : //RewireRightMost((pPrev->left_ == p) ? pPrev : NULL, t);
337 922 : RewireRightMost(x->right_, t);
338 : } else {
339 1992 : t = p->right_;
340 : }
341 2914 : if (!pPrev) {
342 1343 : root_ = t;
343 1571 : } else if (GetBit(x, pPrev->bitpos_)) {
344 533 : pPrev->right_ = t;
345 : } else {
346 1038 : pPrev->left_ = t;
347 : }
348 2914 : delete p;
349 2914 : 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 5195 : nodes_--;
360 5195 : node->left_ = NULL;
361 5195 : node->right_ = NULL;
362 5195 : return true;
363 : }
364 :
365 18099 : Node * FindNode(const Node * node) {
366 : Node * p, * x;
367 :
368 18099 : p = NULL;
369 18099 : x = root_;
370 33642 : while (x) {
371 30004 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
372 1 : x = NULL;
373 1 : break;
374 30003 : } else if (x->bitpos_ == K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
375 14460 : break;
376 : }
377 15543 : p = x;
378 15543 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
379 15543 : if (x && (p->bitpos_ >= x->bitpos_)) {
380 : /* no x to deal with */
381 0 : x = NULL;
382 0 : break;
383 : }
384 : }
385 :
386 18099 : if(!x || !Compare(node, x)){
387 4699 : return NULL;
388 : }
389 :
390 13400 : 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 26124 : Node * GetNextNode(Node * node) {
511 : Node *x, *l;
512 :
513 26124 : if (!root_) {
514 17174 : return NULL;
515 : }
516 :
517 8950 : x = root_;
518 8950 : if (node || IS_INT_NODE(x)) {
519 8346 : if (node) {
520 7867 : x = node;
521 : }
522 8346 : l = x;
523 22802 : while (x) {
524 22034 : if (x->bitpos_ < l->bitpos_) {
525 6925 : l = x;
526 6925 : x = l->right_;
527 : } else {
528 15109 : l = x;
529 15109 : x = l->left_ ? l->left_ : l->right_;
530 : }
531 22034 : if (x && x->bitpos_ > l->bitpos_ &&
532 14341 : !IS_INT_NODE(x)) {
533 7578 : break;
534 : }
535 : }
536 : }
537 :
538 8950 : 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 79347 : bool GetBit(const Node * node, std::size_t pos) {
632 79347 : const D * data = NodeToData(node);
633 79347 : if (pos >= K::BitLength(data)) {
634 85 : return false;
635 : }
636 :
637 79262 : return K::ByteValue(data, pos >> 3) & (0x80 >> (pos & 7));
638 : }
639 :
640 20003 : bool Compare(const Node *node_left, const Node *node_right) {
641 20003 : const D * data_left = NodeToData(node_left);
642 20003 : const D * data_right = NodeToData(node_right);
643 20003 : if (K::BitLength(data_left) != K::BitLength(data_right)) {
644 0 : return false;
645 : }
646 :
647 20003 : std::size_t byteLen = K::BitLength(data_left) >> 3;
648 : std::size_t pos;
649 :
650 157917 : for (pos = 0; pos < byteLen; ++pos) {
651 139265 : if (K::ByteValue(data_left, pos) != K::ByteValue(data_right, pos)) {
652 1351 : return false;
653 : }
654 : }
655 :
656 18792 : 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 18652 : return true;
663 : }
664 :
665 3723 : bool Compare(const Node *node_left, const Node *node_right, std::size_t start, std::size_t& pos) {
666 3723 : const D * data_left = NodeToData(node_left);
667 3723 : const D * data_right = NodeToData(node_right);
668 : std::size_t shortLen;
669 :
670 : bool isEqual;
671 :
672 3723 : if (K::BitLength(data_left) < K::BitLength(data_right)) {
673 50 : shortLen = K::BitLength(data_left);
674 50 : isEqual = false;
675 : } else {
676 3673 : shortLen = K::BitLength(data_right);
677 3673 : isEqual = (K::BitLength(data_left) == K::BitLength(data_right));
678 : }
679 :
680 3723 : std::size_t byteLen = shortLen >> 3;
681 :
682 18218 : for (pos = start >> 3; pos < byteLen; ++pos) {
683 17435 : if (K::ByteValue(data_left, pos) != K::ByteValue(data_right, pos)) {
684 2940 : break;
685 : }
686 : }
687 :
688 3723 : pos <<= 3;
689 3723 : if (pos < start) {
690 1 : pos = start;
691 : }
692 :
693 16852 : for (; pos < shortLen; ++pos) {
694 16081 : if (GetBit(node_left, pos) != GetBit(node_right, pos)) {
695 2952 : return false;
696 : }
697 : }
698 :
699 771 : return isEqual;
700 : }
701 :
702 3061 : Node * RewireRightMost (Node *p, Node *x) {
703 : Node *pRight;
704 3061 : if (!x) {
705 0 : return NULL;
706 : }
707 :
708 4330 : while (x->right_ && x->right_->bitpos_ > x->bitpos_) {
709 1269 : x = x->right_;
710 : }
711 3061 : pRight = x->right_;
712 3061 : x->right_ = p;
713 3061 : return pRight;
714 : }
715 :
716 :
717 : };
718 :
719 : };
720 :
721 : #endif /* PATRICIA_H */
722 :
|
