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 3914 : Node() {
19 3914 : left_ = NULL;
20 3914 : right_ = NULL;
21 3914 : intnode_ = false;
22 3914 : bitpos_ = 0;
23 3914 : }
24 :
25 : Node *left_;
26 : Node *right_;
27 : bool intnode_;
28 : std::size_t bitpos_;
29 : };
30 :
31 : class TreeBase {
32 : public:
33 71 : TreeBase() {
34 71 : root_ = NULL;
35 71 : nodes_ = 0;
36 71 : int_nodes_ = 0;
37 71 : }
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 6538 : Tree() : TreeBase() {
48 6538 : }
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 33 : std::size_t Size() {
88 33 : return nodes_;
89 : }
90 :
91 5730 : bool Insert(D * data) {
92 5730 : return InsertNode(DataToNode(data));
93 : }
94 :
95 5703 : bool Remove(D * data) {
96 5703 : return RemoveNode(DataToNode(data));
97 : }
98 :
99 18055 : D * Find(const D * data) {
100 18055 : return NodeToData(FindNode(DataToNode(data)));
101 : }
102 :
103 148 : D * FindNext(const D * data) {
104 148 : return NodeToData(FindNextNode(DataToNode(data)));
105 : }
106 :
107 650 : D * LPMFind(const D * data) {
108 650 : return NodeToData(FindBestMatchNode(DataToNode(data)));
109 : }
110 :
111 25674 : D * GetNext(D * data) {
112 25674 : 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 18910 : const Node *DataToNode (const D * data) {
125 18910 : if (data) {
126 18910 : return static_cast<const Node *>(&(data->*P));
127 : } else {
128 0 : return NULL;
129 : }
130 : }
131 :
132 37107 : Node *DataToNode (D * data) {
133 37107 : if (data) {
134 19215 : return static_cast<Node *>(&(data->*P));
135 : } else {
136 17892 : return NULL;
137 : }
138 : }
139 :
140 201756 : const D *NodeToData (const Node * node) {
141 201756 : if (node) {
142 201756 : return boost::intrusive::detail::parent_from_member<D, Node>(node, P);
143 : } else {
144 0 : return NULL;
145 : }
146 : }
147 :
148 100048 : D *NodeToData (Node * node) {
149 100048 : if (node) {
150 77575 : return boost::intrusive::detail::parent_from_member<D, Node>(node, P);
151 : } else {
152 22473 : return NULL;
153 : }
154 : }
155 :
156 5730 : bool InsertNode(Node *node) {
157 : Node * p, * x, *l;
158 :
159 : // Start at the root_
160 5730 : p = NULL;
161 5730 : x = root_;
162 13810 : while (x) {
163 11481 : if (x->bitpos_ >= K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
164 3370 : break;
165 : }
166 8111 : p = x;
167 8111 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
168 8111 : if (x && (p->bitpos_ >= x->bitpos_)) {
169 : /* no x to deal with */
170 31 : x = NULL;
171 31 : break;
172 : }
173 : }
174 :
175 5730 : std::size_t i = 0;
176 5730 : l = x ? x : p;
177 : // Find the first bit that does not match.
178 5730 : if (l) {
179 : /* if l is internal node pick the left_ node to compare */
180 3547 : if (Compare(node, l, 0, i)) {
181 : // The key already exists
182 375 : return false;
183 : }
184 :
185 3172 : if (i != K::BitLength(NodeToData(node)) || i != l->bitpos_) {
186 3172 : p = NULL;
187 3172 : x = root_;
188 8377 : while (x && x->bitpos_ <= i && x->bitpos_ < K::BitLength(NodeToData(node))) {
189 5229 : p = x;
190 5229 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
191 5229 : if (x && (p->bitpos_ >= x->bitpos_)) {
192 : /* no x to deal with */
193 24 : x = NULL;
194 24 : break;
195 : }
196 : }
197 : }
198 : }
199 :
200 5355 : nodes_++;
201 5355 : node->left_ = NULL;
202 5355 : node->right_ = NULL;
203 5355 : node->bitpos_ = K::BitLength(NodeToData(node));;
204 :
205 5355 : if (x) {
206 3027 : 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 3025 : if (i == K::BitLength(NodeToData(node))) {
219 30 : if (GetBit(l, i)) {
220 0 : node->right_ = x;
221 : } else {
222 30 : node->left_ = x;
223 : /* right_ most node of the left_ sub tree should point to node */
224 30 : node->right_ = RewireRightMost(node, x);
225 : }
226 30 : l = node;
227 : } else {
228 : /* allocate internal node */
229 2995 : l = new Node;
230 2995 : int_nodes_++;
231 2995 : l->bitpos_ = i;
232 2995 : l->intnode_ = true;
233 2995 : if (GetBit(node, i)) {
234 2044 : l->left_ = x;
235 2044 : l->right_ = node;
236 : /* right_ most node of the left_ sub tree should point to l */
237 2044 : node->right_ = RewireRightMost(l, x);
238 : } else {
239 951 : l->left_ = node;
240 951 : l->right_ = x;
241 951 : node->right_ = l;
242 : }
243 : }
244 : }
245 : } else {
246 2328 : if (p) {
247 145 : if (GetBit(node, p->bitpos_)) {
248 29 : node->right_ = p->right_;
249 : } else {
250 116 : node->right_ = p;
251 : }
252 : }
253 2328 : l = node;
254 : }
255 :
256 5355 : if (p) {
257 1777 : if (GetBit(node, p->bitpos_)) {
258 1063 : p->right_ = l;
259 : } else {
260 714 : p->left_ = l;
261 : }
262 : } else {
263 3578 : root_ = l;
264 : }
265 :
266 5355 : return true;
267 : }
268 :
269 5703 : bool RemoveNode(Node * node) {
270 5703 : Node * pPrev = NULL;
271 5703 : Node * p = NULL;
272 5703 : Node * x = root_;
273 :
274 13634 : while (x) {
275 13620 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
276 41 : x = NULL;
277 41 : break;
278 13579 : } else if (x->bitpos_ == K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
279 5646 : break;
280 : }
281 7933 : pPrev = p;
282 7933 : p = x;
283 7933 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
284 7933 : if (x && (p->bitpos_ >= x->bitpos_)) {
285 : /* no x to deal with */
286 2 : x = NULL;
287 2 : break;
288 : }
289 : }
290 :
291 5703 : if(!x || !Compare(node, x)){
292 348 : return false;
293 : }
294 :
295 5355 : Node * t = NULL;
296 :
297 5355 : if (x->left_ && x->right_ && x->bitpos_ < x->right_->bitpos_) {
298 : /* need to allocate internal node to replace the going node */
299 26 : t = new Node;
300 26 : t->bitpos_ = x->bitpos_;
301 26 : t->intnode_ = true;
302 26 : int_nodes_++;
303 26 : t->left_ = x->left_;
304 26 : t->right_ = x->right_;
305 26 : RewireRightMost(t, x->left_);
306 26 : if (!p) {
307 3 : root_ =t ;
308 23 : } else if (GetBit(x, p->bitpos_)) {
309 0 : p->right_ = t;
310 : } else {
311 23 : p->left_ = t;
312 : }
313 5329 : } else if (x->left_) {
314 108 : if (!p) {
315 35 : 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 108 : RewireRightMost(x->right_, x->left_);
322 5221 : } 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 5221 : if (!p) {
332 2183 : root_ = NULL;
333 3038 : } else if (IS_INT_NODE(p)) {
334 3019 : if (GetBit(x, p->bitpos_)){
335 946 : t = p->left_;
336 : //RewireRightMost((pPrev->left_ == p) ? pPrev : NULL, t);
337 946 : RewireRightMost(x->right_, t);
338 : } else {
339 2073 : t = p->right_;
340 : }
341 3019 : if (!pPrev) {
342 1360 : root_ = t;
343 1659 : } else if (GetBit(x, pPrev->bitpos_)) {
344 564 : pPrev->right_ = t;
345 : } else {
346 1095 : pPrev->left_ = t;
347 : }
348 3019 : delete p;
349 3019 : int_nodes_--;
350 : } else {
351 19 : if (GetBit(x, p->bitpos_)) {
352 5 : p->right_ = x->right_;
353 : } else {
354 14 : p->left_ = NULL;
355 : }
356 : }
357 : }
358 :
359 5355 : nodes_--;
360 5355 : node->left_ = NULL;
361 5355 : node->right_ = NULL;
362 5355 : return true;
363 : }
364 :
365 18055 : Node * FindNode(const Node * node) {
366 : Node * p, * x;
367 :
368 18055 : p = NULL;
369 18055 : x = root_;
370 33543 : while (x) {
371 29946 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
372 1 : x = NULL;
373 1 : break;
374 29945 : } else if (x->bitpos_ == K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
375 14457 : break;
376 : }
377 15488 : p = x;
378 15488 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
379 15488 : if (x && (p->bitpos_ >= x->bitpos_)) {
380 : /* no x to deal with */
381 0 : x = NULL;
382 0 : break;
383 : }
384 : }
385 :
386 18055 : if(!x || !Compare(node, x)){
387 4658 : return NULL;
388 : }
389 :
390 13397 : return x;
391 : }
392 :
393 148 : Node * FindNextNode(const Node * node) {
394 : Node * p, * x, *l;
395 148 : std::size_t i = 0;
396 :
397 148 : p = NULL;
398 148 : l = NULL;
399 148 : x = root_;
400 1027 : while (x) {
401 1026 : if (!IS_INT_NODE(x)) {
402 422 : if (Compare(node, x, i, i)) {
403 90 : return GetNextNode(x);
404 : }
405 332 : if (x->bitpos_ > K::BitLength(NodeToData(node)) || i != x->bitpos_) {
406 56 : break;
407 : }
408 276 : l = x;
409 : }
410 880 : p = x;
411 880 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
412 880 : 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 650 : Node * FindBestMatchNode(const Node * node) {
482 : Node * p, * x, *l;
483 650 : std::size_t i = 0;
484 :
485 650 : l = NULL;
486 650 : p = NULL;
487 650 : x = root_;
488 1977 : while (x) {
489 1832 : if (!IS_INT_NODE(x)) {
490 1054 : if (Compare(node, x, i, i)) {
491 230 : return x;
492 : }
493 824 : if (i == x->bitpos_) {
494 422 : l = x;
495 : }
496 : }
497 1602 : if (x->bitpos_ > K::BitLength(NodeToData(node))) {
498 269 : break;
499 : }
500 1333 : p = x;
501 1333 : x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
502 1333 : if (x && (p->bitpos_ >= x->bitpos_)) {
503 6 : break;
504 : }
505 : }
506 :
507 420 : return l;
508 : }
509 :
510 25794 : Node * GetNextNode(Node * node) {
511 : Node *x, *l;
512 :
513 25794 : if (!root_) {
514 16807 : return NULL;
515 : }
516 :
517 8987 : x = root_;
518 8987 : if (node || IS_INT_NODE(x)) {
519 8381 : if (node) {
520 7902 : x = node;
521 : }
522 8381 : l = x;
523 22874 : while (x) {
524 22080 : if (x->bitpos_ < l->bitpos_) {
525 6934 : l = x;
526 6934 : x = l->right_;
527 : } else {
528 15146 : l = x;
529 15146 : x = l->left_ ? l->left_ : l->right_;
530 : }
531 22080 : if (x && x->bitpos_ > l->bitpos_ &&
532 14352 : !IS_INT_NODE(x)) {
533 7587 : break;
534 : }
535 : }
536 : }
537 :
538 8987 : 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 88510 : bool GetBit(const Node * node, std::size_t pos) {
632 88510 : const D * data = NodeToData(node);
633 88510 : if (pos >= K::BitLength(data)) {
634 231 : return false;
635 : }
636 :
637 88279 : return K::ByteValue(data, pos >> 3) & (0x80 >> (pos & 7));
638 : }
639 :
640 20160 : bool Compare(const Node *node_left, const Node *node_right) {
641 20160 : const D * data_left = NodeToData(node_left);
642 20160 : const D * data_right = NodeToData(node_right);
643 20160 : if (K::BitLength(data_left) != K::BitLength(data_right)) {
644 0 : return false;
645 : }
646 :
647 20160 : std::size_t byteLen = K::BitLength(data_left) >> 3;
648 : std::size_t pos;
649 :
650 160228 : for (pos = 0; pos < byteLen; ++pos) {
651 141419 : if (K::ByteValue(data_left, pos) != K::ByteValue(data_right, pos)) {
652 1351 : return false;
653 : }
654 : }
655 :
656 18949 : 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 18809 : return true;
663 : }
664 :
665 5023 : bool Compare(const Node *node_left, const Node *node_right, std::size_t start, std::size_t& pos) {
666 5023 : const D * data_left = NodeToData(node_left);
667 5023 : const D * data_right = NodeToData(node_right);
668 : std::size_t shortLen;
669 :
670 : bool isEqual;
671 :
672 5023 : if (K::BitLength(data_left) < K::BitLength(data_right)) {
673 326 : shortLen = K::BitLength(data_left);
674 326 : isEqual = false;
675 : } else {
676 4697 : shortLen = K::BitLength(data_right);
677 4697 : isEqual = (K::BitLength(data_left) == K::BitLength(data_right));
678 : }
679 :
680 5023 : std::size_t byteLen = shortLen >> 3;
681 :
682 25323 : for (pos = start >> 3; pos < byteLen; ++pos) {
683 23468 : if (K::ByteValue(data_left, pos) != K::ByteValue(data_right, pos)) {
684 3168 : break;
685 : }
686 : }
687 :
688 5023 : pos <<= 3;
689 5023 : if (pos < start) {
690 28 : pos = start;
691 : }
692 :
693 21229 : for (; pos < shortLen; ++pos) {
694 19386 : if (GetBit(node_left, pos) != GetBit(node_right, pos)) {
695 3180 : return false;
696 : }
697 : }
698 :
699 1843 : return isEqual;
700 : }
701 :
702 3156 : Node * RewireRightMost (Node *p, Node *x) {
703 : Node *pRight;
704 3156 : if (!x) {
705 0 : return NULL;
706 : }
707 :
708 4397 : while (x->right_ && x->right_->bitpos_ > x->bitpos_) {
709 1241 : x = x->right_;
710 : }
711 3156 : pRight = x->right_;
712 3156 : x->right_ = p;
713 3156 : return pRight;
714 : }
715 :
716 :
717 : };
718 :
719 : };
720 :
721 : #endif /* PATRICIA_H */
722 :
|
