LCOV - code coverage report
Current view: top level - root/contrail/src/contrail-common/base - patricia.h (source / functions) Hit Total Coverage
Test: OpenSDN C/C++ coverage (all TARGET_SET jobs) Lines: 373 400 93.2 %
Date: 2026-11-16 02:06:09 Functions: 142 146 97.3 %
Legend: Lines: hit not hit

          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       28381 :     Node() {
      20       28381 :         left_ = NULL;
      21       28381 :         right_ = NULL;
      22       28381 :         intnode_ = false;
      23       28381 :         bitpos_ = 0;
      24       28381 :     } 
      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        8580 :     bool Insert(D * data) {
      93        8580 :         return InsertNode(DataToNode(data));
      94             :     }
      95             : 
      96        7663 :     bool Remove(D * data) {
      97        7663 :         return RemoveNode(DataToNode(data));
      98             :     }
      99             : 
     100       19957 :     D * Find(const D * data) {
     101       19957 :         return NodeToData(FindNode(DataToNode(data)));
     102             :     }
     103             : 
     104         703 :     D * FindNext(const D * data) {
     105         703 :         return NodeToData(FindNextNode(DataToNode(data)));
     106             :     }
     107             : 
     108        6594 :     D * LPMFind(const D * data) {
     109        6594 :         return NodeToData(FindBestMatchNode(DataToNode(data)));
     110             :     }
     111             : 
     112       27156 :     D * GetNext(D * data) {
     113       27156 :         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       27311 :     const Node *DataToNode (const D * data) {
     126       27311 :         if (data) {
     127       27311 :             return static_cast<const Node *>(&(data->*P));
     128             :         } else {
     129           0 :             return NULL;
     130             :         }
     131             :     }
     132             : 
     133       43399 :     Node *DataToNode (D * data) {
     134       43399 :         if (data) {
     135       24026 :             return static_cast<Node *>(&(data->*P));
     136             :         } else {
     137       19373 :             return NULL;
     138             :         }
     139             :     }
     140             : 
     141      397649 :     const D *NodeToData (const Node * node) {
     142      397649 :         if (node) {
     143      397649 :             return boost::intrusive::detail::parent_from_member<D, Node>(node, P);
     144             :         } else {
     145           0 :             return NULL;
     146             :         }
     147             :     }
     148             : 
     149      143871 :     D *NodeToData (Node * node) {
     150      143871 :         if (node) {
     151      117216 :             return boost::intrusive::detail::parent_from_member<D, Node>(node, P);
     152             :         } else {
     153       26655 :             return NULL;
     154             :         }
     155             :     }
     156             : 
     157        8580 :     bool InsertNode(Node *node) {
     158             :         Node * p, * x, *l;
     159             : 
     160             :         // Start at the root_
     161        8580 :         p = NULL;
     162        8580 :         x = root_;
     163       23973 :         while (x) {
     164       21139 :             if (x->bitpos_ >= K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
     165        5629 :                 break;
     166             :             }
     167       15510 :             p = x;
     168       15510 :             x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
     169       15510 :             if (x && (p->bitpos_ >= x->bitpos_)) {
     170             :                 /* no x to deal with */
     171         117 :                 x = NULL;
     172         117 :                 break;
     173             :             }
     174             :         }
     175             : 
     176        8580 :         std::size_t i = 0;
     177        8580 :         l = x ? x : p;
     178             :         // Find the first bit that does not match.
     179        8580 :         if (l) {
     180             :             /* if l is internal node pick the left_ node to compare */
     181        6219 :             if (Compare(node, l, 0, i)) {
     182             :                 // The key already exists
     183        1265 :                 return false;
     184             :             }
     185             : 
     186        4954 :             if (i != K::BitLength(NodeToData(node)) || i != l->bitpos_) {
     187        4954 :                 p = NULL;
     188        4954 :                 x = root_;
     189       13441 :                 while (x && x->bitpos_ <= i && x->bitpos_ < K::BitLength(NodeToData(node))) {
     190        8559 :                     p = x;
     191        8559 :                     x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
     192        8559 :                     if (x && (p->bitpos_ >= x->bitpos_)) {
     193             :                         /* no x to deal with */
     194          72 :                         x = NULL;
     195          72 :                         break;
     196             :                     }
     197             :                 }
     198             :             }
     199             :         }
     200             : 
     201        7315 :         nodes_++;
     202        7315 :         node->left_ = NULL;
     203        7315 :         node->right_ = NULL;
     204        7315 :         node->bitpos_ = K::BitLength(NodeToData(node));;
     205             : 
     206        7315 :         if (x) {
     207        4509 :             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        4507 :                 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        4467 :                     l = new Node;
     231        4467 :                     int_nodes_++;
     232        4467 :                     l->bitpos_ = i;
     233        4467 :                     l->intnode_ = true;
     234        4467 :                     if (GetBit(node, i)) {
     235        3092 :                         l->left_ = x;
     236        3092 :                         l->right_ = node;
     237             :                         /* right_ most node of the left_ sub tree should point to l */
     238        3092 :                         node->right_ = RewireRightMost(l, x);
     239             :                     } else {
     240        1375 :                         l->left_ = node;
     241        1375 :                         l->right_ = x;
     242        1375 :                         node->right_ = l;
     243             :                     }
     244             :                 }
     245             :             }
     246             :         } else {
     247        2806 :             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        2806 :             l = node;
     255             :         }
     256             : 
     257        7315 :         if (p) {
     258        3225 :             if (GetBit(node, p->bitpos_)) {
     259        2035 :                 p->right_ = l;
     260             :             } else {
     261        1190 :                 p->left_ = l;
     262             :             }
     263             :         } else {
     264        4090 :             root_ = l;
     265             :         }
     266             : 
     267        7315 :         return true;
     268             :     }
     269             : 
     270        7663 :     bool RemoveNode(Node * node) {
     271        7663 :         Node * pPrev = NULL;
     272        7663 :         Node * p = NULL;
     273        7663 :         Node * x = root_;
     274             : 
     275       21498 :         while (x) {
     276       21484 :             if (x->bitpos_ > K::BitLength(NodeToData(node))) {
     277          41 :                 x = NULL;
     278          41 :                 break;
     279       21443 :             } else if (x->bitpos_ == K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
     280        7606 :                 break;
     281             :             }
     282       13837 :             pPrev = p;
     283       13837 :             p = x;
     284       13837 :             x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
     285       13837 :             if (x && (p->bitpos_ >= x->bitpos_)) {
     286             :                 /* no x to deal with */
     287           2 :                 x = NULL;
     288           2 :                 break;
     289             :             }
     290             :         }
     291             : 
     292        7663 :         if(!x || !Compare(node, x)){
     293         348 :             return false;
     294             :         }
     295             : 
     296        7315 :         Node * t = NULL;
     297             : 
     298        7315 :         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        7293 :         } 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        7159 :         } 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        7159 :             if (!p) {
     333        2361 :                 root_ = NULL;
     334        4798 :             } else if (IS_INT_NODE(p)) {
     335        4487 :                 if (GetBit(x, p->bitpos_)){
     336        1517 :                     t = p->left_;
     337             :                     //RewireRightMost((pPrev->left_ == p) ? pPrev : NULL, t);
     338        1517 :                     RewireRightMost(x->right_, t);
     339             :                 } else {
     340        2970 :                     t = p->right_;
     341             :                 }
     342        4487 :                 if (!pPrev) {
     343        1643 :                     root_ = t;
     344        2844 :                 } else if (GetBit(x, pPrev->bitpos_)) {
     345         909 :                     pPrev->right_ = t;
     346             :                 } else {
     347        1935 :                     pPrev->left_ = t;
     348             :                 }
     349        4487 :                 delete p;
     350        4487 :                 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        7315 :         nodes_--;
     361        7315 :         node->left_ = NULL;
     362        7315 :         node->right_ = NULL;
     363        7315 :         return true;
     364             :     }
     365             : 
     366       19957 :     Node * FindNode(const Node * node) {
     367             :         Node * p, * x;
     368             : 
     369       19957 :         p = NULL;
     370       19957 :         x = root_;
     371       40768 :         while (x) {
     372       36958 :             if (x->bitpos_ > K::BitLength(NodeToData(node))) {
     373           1 :                 x = NULL;
     374           1 :                 break;
     375       36957 :             } else if (x->bitpos_ == K::BitLength(NodeToData(node)) && !IS_INT_NODE(x)) {
     376       16146 :                 break;
     377             :             }
     378       20811 :             p = x;
     379       20811 :             x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
     380       20811 :             if (x && (p->bitpos_ >= x->bitpos_)) {
     381             :                 /* no x to deal with */
     382           0 :                 x = NULL;
     383           0 :                 break;
     384             :             }
     385             :         }
     386             : 
     387       19957 :         if(!x || !Compare(node, x)){
     388        4965 :             return NULL;
     389             :         }
     390             : 
     391       14992 :         return x;
     392             :     }
     393             : 
     394         703 :     Node * FindNextNode(const Node * node) {
     395             :         Node * p, * x, *l;
     396         703 :         std::size_t i = 0;
     397             : 
     398         703 :         p = NULL;
     399         703 :         l = NULL;
     400         703 :         x = root_;
     401        2371 :         while (x) {
     402        2370 :             if (!IS_INT_NODE(x)) {
     403        1184 :                 if (Compare(node, x, i, i)) {
     404         645 :                     return GetNextNode(x);
     405             :                 }
     406         539 :                 if (x->bitpos_ > K::BitLength(NodeToData(node)) || i != x->bitpos_) {
     407          56 :                     break;
     408             :                 }
     409         483 :                 l = x;
     410             :             }
     411        1669 :             p = x;
     412        1669 :             x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
     413        1669 :             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        6594 :     Node * FindBestMatchNode(const Node * node) {
     483             :         Node * p, * x, *l;
     484        6594 :         std::size_t i = 0;
     485             : 
     486        6594 :         l = NULL;
     487        6594 :         p = NULL;
     488        6594 :         x = root_;
     489       23067 :         while (x) {
     490       21532 :             if (!IS_INT_NODE(x)) {
     491       10812 :                 if (Compare(node, x, i, i)) {
     492        1043 :                     return x;
     493             :                 }
     494        9769 :                 if (i == x->bitpos_) {
     495        4121 :                     l = x;
     496             :                 }
     497             :             }
     498       20489 :             if (x->bitpos_ > K::BitLength(NodeToData(node))) {
     499        4012 :                 break;
     500             :             }
     501       16477 :             p = x;
     502       16477 :             x = GetBit(node, x->bitpos_) ? x->right_ : x->left_;
     503       16477 :             if (x && (p->bitpos_ >= x->bitpos_)) {
     504           4 :                 break;
     505             :             }
     506             :         }
     507             : 
     508        5551 :         return l;
     509             :     }
     510             : 
     511       27831 :     Node * GetNextNode(Node * node) {
     512             :         Node *x, *l;
     513             : 
     514       27831 :         if (!root_) {
     515       18288 :             return NULL;
     516             :         }
     517             : 
     518        9543 :         x = root_;
     519        9543 :         if (node || IS_INT_NODE(x)) {
     520        8937 :             if (node) {
     521        8458 :                 x = node;
     522             :             }
     523        8937 :             l = x;
     524       23980 :             while (x) {
     525       22951 :                 if (x->bitpos_ < l->bitpos_) {
     526        7182 :                     l = x;
     527        7182 :                     x = l->right_;
     528             :                 } else {
     529       15769 :                     l = x;
     530       15769 :                     x = l->left_ ? l->left_ : l->right_;
     531             :                 }
     532       22951 :                 if (x && x->bitpos_ > l->bitpos_ &&
     533       14740 :                     !IS_INT_NODE(x)) {
     534        7908 :                     break;
     535             :                 }
     536             :             }
     537             :         }
     538             : 
     539        9543 :         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      217603 :     bool GetBit(const Node * node, std::size_t pos) {
     633      217603 :         const D * data = NodeToData(node);
     634      217603 :         if (pos >= K::BitLength(data)) {
     635        1605 :             return false;
     636             :         }
     637             : 
     638      215998 :         return K::ByteValue(data, pos >> 3) & (0x80 >> (pos & 7));
     639             :     }
     640             : 
     641       23809 :     bool Compare(const Node *node_left, const Node *node_right) {
     642       23809 :         const D * data_left = NodeToData(node_left);
     643       23809 :         const D * data_right = NodeToData(node_right);
     644       23809 :         if (K::BitLength(data_left) != K::BitLength(data_right)) {
     645           0 :             return false;
     646             :         }
     647             : 
     648       23809 :         std::size_t byteLen = K::BitLength(data_left) >> 3;
     649             :         std::size_t pos;
     650             : 
     651      208272 :         for (pos = 0; pos < byteLen; ++pos) {
     652      185908 :             if (K::ByteValue(data_left, pos) != K::ByteValue(data_right, pos)) {
     653        1445 :                 return false;
     654             :             }
     655             :         }
     656             : 
     657       22504 :         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       22364 :         return true;
     664             :     }
     665             : 
     666       18215 :     bool Compare(const Node *node_left, const Node *node_right, std::size_t start, std::size_t& pos) {
     667       18215 :         const D * data_left = NodeToData(node_left);
     668       18215 :         const D * data_right = NodeToData(node_right);
     669             :         std::size_t shortLen;
     670             : 
     671             :         bool isEqual;
     672             : 
     673       18215 :         if (K::BitLength(data_left) < K::BitLength(data_right)) {
     674        4090 :             shortLen = K::BitLength(data_left);
     675        4090 :             isEqual = false;
     676             :         } else {
     677       14125 :             shortLen = K::BitLength(data_right);
     678       14125 :             isEqual = (K::BitLength(data_left) == K::BitLength(data_right));
     679             :         }
     680             : 
     681       18215 :         std::size_t byteLen = shortLen >> 3;
     682             : 
     683      107868 :         for (pos = start >> 3; pos < byteLen; ++pos) {
     684       95804 :             if (K::ByteValue(data_left, pos) != K::ByteValue(data_right, pos)) {
     685        6151 :                 break;
     686             :             }
     687             :         }
     688             : 
     689       18215 :         pos <<= 3;
     690       18215 :         if (pos < start) {
     691         593 :             pos = start;
     692             :         }
     693             : 
     694       73941 :         for (; pos < shortLen; ++pos) {
     695       61889 :             if (GetBit(node_left, pos) != GetBit(node_right, pos)) {
     696        6163 :                 return false;
     697             :             }
     698             :         }
     699             : 
     700       12052 :         return isEqual;
     701             :     }
     702             : 
     703        4807 :     Node * RewireRightMost (Node *p, Node *x) {
     704             :         Node *pRight;
     705        4807 :         if (!x) {
     706           0 :             return NULL;
     707             :         }
     708             : 
     709        7132 :         while (x->right_ && x->right_->bitpos_ > x->bitpos_) {
     710        2325 :             x = x->right_;
     711             :         }
     712        4807 :         pRight = x->right_;
     713        4807 :         x->right_ = p;
     714        4807 :         return pRight;
     715             :     }
     716             : 
     717             : 
     718             : };
     719             : 
     720             : };
     721             : 
     722             : #endif /* PATRICIA_H */
     723             : 

Generated by: LCOV version 1.14