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