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 3599 : Node() {
19 3599 : left_ = NULL;
20 3599 : right_ = NULL;
21 3599 : intnode_ = false;
22 3599 : bitpos_ = 0;
23 3599 : }
24 :
25 : Node *left_;
26 : Node *right_;
27 : bool intnode_;
28 : std::size_t bitpos_;
29 : };
30 :
31 : class TreeBase {
32 : public:
33 61 : TreeBase() {
34 61 : root_ = NULL;
35 61 : nodes_ = 0;
36 61 : int_nodes_ = 0;
37 61 : }
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 6897 : Tree() : TreeBase() {
48 6897 : }
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 5701 : bool Insert(D * data) {
92 5701 : return InsertNode(DataToNode(data));
93 : }
94 :
95 5686 : bool Remove(D * data) {
96 5686 : return RemoveNode(DataToNode(data));
97 : }
98 :
99 18206 : D * Find(const D * data) {
100 18206 : return NodeToData(FindNode(DataToNode(data)));
101 : }
102 :
103 140 : D * FindNext(const D * data) {
104 140 : return NodeToData(FindNextNode(DataToNode(data)));
105 : }
106 :
107 560 : D * LPMFind(const D * data) {
108 560 : return NodeToData(FindBestMatchNode(DataToNode(data)));
109 : }
110 :
111 26075 : D * GetNext(D * data) {
112 26075 : 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 18963 : const Node *DataToNode (const D * data) {
125 18963 : if (data) {
126 18963 : return static_cast<const Node *>(&(data->*P));
127 : } else {
128 0 : return NULL;
129 : }
130 : }
131 :
132 37462 : Node *DataToNode (D * data) {
133 37462 : if (data) {
134 19178 : return static_cast<Node *>(&(data->*P));
135 : } else {
136 18284 : return NULL;
137 : }
138 : }
139 :
140 201103 : const D *NodeToData (const Node * node) {
141 201103 : if (node) {
142 201103 : return boost::intrusive::detail::parent_from_member<D, Node>(node, P);
143 : } else {
144 0 : return NULL;
145 : }
146 : }
147 :
148 100439 : D *NodeToData (Node * node) {
149 100439 : if (node) {
150 77534 : return boost::intrusive::detail::parent_from_member<D, Node>(node, P);
151 : } else {
152 22905 : return NULL;
153 : }
154 : }
155 :
156 5701 : bool InsertNode(Node *node) {
157 : Node * p, * x, *l;
158 :
159 : // Start at the root_
160 5701 : p = NULL;
161 5701 : x = root_;
162 13776 : while (x) {
163 11458 : if (x->bitpos_ >= K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
164 3356 : break;
165 : }
166 8102 : p = x;
167 8102 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
168 8102 : if (x && (p->bitpos_ >= x->bitpos_)) {
169 : /* no x to deal with */
170 27 : x = NULL;
171 27 : break;
172 : }
173 : }
174 :
175 5701 : std::size_t i = 0;
176 5701 : l = x ? x : p;
177 : // Find the first bit that does not match.
178 5701 : if (l) {
179 : /* if l is internal node pick the left_ node to compare */
180 3524 : if (Compare(node, l, 0, i)) {
181 : // The key already exists
182 363 : return false;
183 : }
184 :
185 3161 : if (i != K::BitLength(NodeToData(node)) || i != l->bitpos_) {
186 3161 : p = NULL;
187 3161 : x = root_;
188 8383 : while (x && x->bitpos_ <= i && x->bitpos_ < K::BitLength(NodeToData(node))) {
189 5240 : p = x;
190 5240 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
191 5240 : if (x && (p->bitpos_ >= x->bitpos_)) {
192 : /* no x to deal with */
193 18 : x = NULL;
194 18 : break;
195 : }
196 : }
197 : }
198 : }
199 :
200 5338 : nodes_++;
201 5338 : node->left_ = NULL;
202 5338 : node->right_ = NULL;
203 5338 : node->bitpos_ = K::BitLength(NodeToData(node));;
204 :
205 5338 : if (x) {
206 3030 : 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 3028 : if (i == K::BitLength(NodeToData(node))) {
219 26 : if (GetBit(l, i)) {
220 0 : node->right_ = x;
221 : } else {
222 26 : node->left_ = x;
223 : /* right_ most node of the left_ sub tree should point to node */
224 26 : node->right_ = RewireRightMost(node, x);
225 : }
226 26 : l = node;
227 : } else {
228 : /* allocate internal node */
229 3002 : l = new Node;
230 3002 : int_nodes_++;
231 3002 : l->bitpos_ = i;
232 3002 : l->intnode_ = true;
233 3002 : if (GetBit(node, i)) {
234 2105 : l->left_ = x;
235 2105 : l->right_ = node;
236 : /* right_ most node of the left_ sub tree should point to l */
237 2105 : node->right_ = RewireRightMost(l, x);
238 : } else {
239 897 : l->left_ = node;
240 897 : l->right_ = x;
241 897 : node->right_ = l;
242 : }
243 : }
244 : }
245 : } else {
246 2308 : if (p) {
247 131 : if (GetBit(node, p->bitpos_)) {
248 21 : node->right_ = p->right_;
249 : } else {
250 110 : node->right_ = p;
251 : }
252 : }
253 2308 : l = node;
254 : }
255 :
256 5338 : if (p) {
257 1774 : if (GetBit(node, p->bitpos_)) {
258 1057 : p->right_ = l;
259 : } else {
260 717 : p->left_ = l;
261 : }
262 : } else {
263 3564 : root_ = l;
264 : }
265 :
266 5338 : return true;
267 : }
268 :
269 5686 : bool RemoveNode(Node * node) {
270 5686 : Node * pPrev = NULL;
271 5686 : Node * p = NULL;
272 5686 : Node * x = root_;
273 :
274 13621 : while (x) {
275 13607 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
276 41 : x = NULL;
277 41 : break;
278 13566 : } else if (x->bitpos_ == K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
279 5629 : break;
280 : }
281 7937 : pPrev = p;
282 7937 : p = x;
283 7937 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
284 7937 : if (x && (p->bitpos_ >= x->bitpos_)) {
285 : /* no x to deal with */
286 2 : x = NULL;
287 2 : break;
288 : }
289 : }
290 :
291 5686 : if(!x || !Compare(node, x)){
292 348 : return false;
293 : }
294 :
295 5338 : Node * t = NULL;
296 :
297 5338 : if (x->left_ && x->right_ && x->bitpos_ < x->right_->bitpos_) {
298 : /* need to allocate internal node to replace the going node */
299 18 : t = new Node;
300 18 : t->bitpos_ = x->bitpos_;
301 18 : t->intnode_ = true;
302 18 : int_nodes_++;
303 18 : t->left_ = x->left_;
304 18 : t->right_ = x->right_;
305 18 : RewireRightMost(t, x->left_);
306 18 : if (!p) {
307 1 : root_ =t ;
308 17 : } else if (GetBit(x, p->bitpos_)) {
309 0 : p->right_ = t;
310 : } else {
311 17 : p->left_ = t;
312 : }
313 5320 : } else if (x->left_) {
314 104 : if (!p) {
315 31 : root_ = x->left_;
316 73 : } else if (GetBit(x, p->bitpos_)) {
317 5 : p->right_ = x->left_;
318 : } else {
319 68 : p->left_ = x->left_;
320 : }
321 104 : RewireRightMost(x->right_, x->left_);
322 5216 : } 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 5216 : if (!p) {
332 2177 : root_ = NULL;
333 3039 : } else if (IS_INT_NODE(p)) {
334 3018 : if (GetBit(x, p->bitpos_)){
335 962 : t = p->left_;
336 : //RewireRightMost((pPrev->left_ == p) ? pPrev : NULL, t);
337 962 : RewireRightMost(x->right_, t);
338 : } else {
339 2056 : t = p->right_;
340 : }
341 3018 : if (!pPrev) {
342 1371 : root_ = t;
343 1647 : } else if (GetBit(x, pPrev->bitpos_)) {
344 549 : pPrev->right_ = t;
345 : } else {
346 1098 : pPrev->left_ = t;
347 : }
348 3018 : delete p;
349 3018 : int_nodes_--;
350 : } else {
351 21 : if (GetBit(x, p->bitpos_)) {
352 5 : p->right_ = x->right_;
353 : } else {
354 16 : p->left_ = NULL;
355 : }
356 : }
357 : }
358 :
359 5338 : nodes_--;
360 5338 : node->left_ = NULL;
361 5338 : node->right_ = NULL;
362 5338 : return true;
363 : }
364 :
365 18206 : Node * FindNode(const Node * node) {
366 : Node * p, * x;
367 :
368 18206 : p = NULL;
369 18206 : x = root_;
370 33837 : while (x) {
371 30186 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
372 1 : x = NULL;
373 1 : break;
374 30185 : } else if (x->bitpos_ == K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
375 14554 : break;
376 : }
377 15631 : p = x;
378 15631 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
379 15631 : if (x && (p->bitpos_ >= x->bitpos_)) {
380 : /* no x to deal with */
381 0 : x = NULL;
382 0 : break;
383 : }
384 : }
385 :
386 18206 : if(!x || !Compare(node, x)){
387 4712 : return NULL;
388 : }
389 :
390 13494 : return x;
391 : }
392 :
393 140 : Node * FindNextNode(const Node * node) {
394 : Node * p, * x, *l;
395 140 : std::size_t i = 0;
396 :
397 140 : p = NULL;
398 140 : l = NULL;
399 140 : x = root_;
400 1014 : while (x) {
401 1013 : if (!IS_INT_NODE(x)) {
402 409 : if (Compare(node, x, i, i)) {
403 82 : return GetNextNode(x);
404 : }
405 327 : if (x->bitpos_ > K::BitLength(NodeToData(node)) || i != x->bitpos_) {
406 56 : break;
407 : }
408 271 : l = x;
409 : }
410 875 : p = x;
411 875 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
412 875 : 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 560 : Node * FindBestMatchNode(const Node * node) {
482 : Node * p, * x, *l;
483 560 : std::size_t i = 0;
484 :
485 560 : l = NULL;
486 560 : p = NULL;
487 560 : x = root_;
488 1782 : while (x) {
489 1652 : if (!IS_INT_NODE(x)) {
490 859 : if (Compare(node, x, i, i)) {
491 206 : return x;
492 : }
493 653 : if (i == x->bitpos_) {
494 292 : l = x;
495 : }
496 : }
497 1446 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
498 222 : break;
499 : }
500 1224 : p = x;
501 1224 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
502 1224 : if (x && (p->bitpos_ >= x->bitpos_)) {
503 2 : break;
504 : }
505 : }
506 :
507 354 : return l;
508 : }
509 :
510 26187 : Node * GetNextNode(Node * node) {
511 : Node *x, *l;
512 :
513 26187 : if (!root_) {
514 17197 : return NULL;
515 : }
516 :
517 8990 : x = root_;
518 8990 : if (node || IS_INT_NODE(x)) {
519 8386 : if (node) {
520 7903 : x = node;
521 : }
522 8386 : l = x;
523 22881 : while (x) {
524 22089 : if (x->bitpos_ < l->bitpos_) {
525 6936 : l = x;
526 6936 : x = l->right_;
527 : } else {
528 15153 : l = x;
529 15153 : x = l->left_ ? l->left_ : l->right_;
530 : }
531 22089 : if (x && x->bitpos_ > l->bitpos_ &&
532 14361 : !IS_INT_NODE(x)) {
533 7594 : break;
534 : }
535 : }
536 : }
537 :
538 8990 : 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 87840 : bool GetBit(const Node * node, std::size_t pos) {
632 87840 : const D * data = NodeToData(node);
633 87840 : if (pos >= K::BitLength(data)) {
634 233 : return false;
635 : }
636 :
637 87607 : return K::ByteValue(data, pos >> 3) & (0x80 >> (pos & 7));
638 : }
639 :
640 20240 : bool Compare(const Node *node_left, const Node *node_right) {
641 20240 : const D * data_left = NodeToData(node_left);
642 20240 : const D * data_right = NodeToData(node_right);
643 20240 : if (K::BitLength(data_left) != K::BitLength(data_right)) {
644 0 : return false;
645 : }
646 :
647 20240 : std::size_t byteLen = K::BitLength(data_left) >> 3;
648 : std::size_t pos;
649 :
650 161141 : for (pos = 0; pos < byteLen; ++pos) {
651 142252 : if (K::ByteValue(data_left, pos) != K::ByteValue(data_right, pos)) {
652 1351 : return false;
653 : }
654 : }
655 :
656 19029 : 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 18889 : return true;
663 : }
664 :
665 4792 : bool Compare(const Node *node_left, const Node *node_right, std::size_t start, std::size_t& pos) {
666 4792 : const D * data_left = NodeToData(node_left);
667 4792 : const D * data_right = NodeToData(node_right);
668 : std::size_t shortLen;
669 :
670 : bool isEqual;
671 :
672 4792 : if (K::BitLength(data_left) < K::BitLength(data_right)) {
673 275 : shortLen = K::BitLength(data_left);
674 275 : isEqual = false;
675 : } else {
676 4517 : shortLen = K::BitLength(data_right);
677 4517 : isEqual = (K::BitLength(data_left) == K::BitLength(data_right));
678 : }
679 :
680 4792 : std::size_t byteLen = shortLen >> 3;
681 :
682 24730 : for (pos = start >> 3; pos < byteLen; ++pos) {
683 23117 : if (K::ByteValue(data_left, pos) != K::ByteValue(data_right, pos)) {
684 3179 : break;
685 : }
686 : }
687 :
688 4792 : pos <<= 3;
689 4792 : if (pos < start) {
690 34 : pos = start;
691 : }
692 :
693 20650 : for (; pos < shortLen; ++pos) {
694 19049 : if (GetBit(node_left, pos) != GetBit(node_right, pos)) {
695 3191 : return false;
696 : }
697 : }
698 :
699 1601 : return isEqual;
700 : }
701 :
702 3217 : Node * RewireRightMost (Node *p, Node *x) {
703 : Node *pRight;
704 3217 : if (!x) {
705 0 : return NULL;
706 : }
707 :
708 4474 : while (x->right_ && x->right_->bitpos_ > x->bitpos_) {
709 1257 : x = x->right_;
710 : }
711 3217 : pRight = x->right_;
712 3217 : x->right_ = p;
713 3217 : return pRight;
714 : }
715 :
716 :
717 : };
718 :
719 : };
720 :
721 : #endif /* PATRICIA_H */
722 :
|
