mappingservice/inmemorydb/src/main/java/org/opendaylight/lispflowmapping/inmemorydb/radixtrie/RadixTrie.java

   1 /*
   2  * Copyright (c) 2016 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8
   9 package org.opendaylight.lispflowmapping.inmemorydb.radixtrie;
  10
  11 import java.net.InetAddress;
  12 import java.net.UnknownHostException;
  13 import java.util.ArrayDeque;
  14 import java.util.ArrayList;
  15 import java.util.Collections;
  16 import java.util.Deque;
  17 import java.util.HashSet;
  18 import java.util.Iterator;
  19 import java.util.ListIterator;
  20 import java.util.Set;
  21
  22 /**
  23  * Radix trie/tree (also known as Patricia tree) implementation. Supports CRD operations for
  24  * generic, big endian (network byte order) prefixes. It can do exact and longest prefix matching,
  25  * post order iteration over the entries in the tree and can lookup widest negative prefixes (i.e.,
  26  * shortest overlapping prefix not registered in the tree).
  27  *
  28  * @author Florin Coras
  29  *
  30  * @param <T> Data type stored in each tree node
  31  */
  32 public class RadixTrie<T> {
  33     private int maxBits;
  34     private TrieNode root;
  35     private long nbActiveNodes;
  36     private boolean rootZero;
  37
  38     /**
  39      * RadixTrie constructor.
  40      *
  41      * @param bits Maximum prefix length supported.
  42      */
  43     public RadixTrie(int bits) {
  44         maxBits = bits;
  45         root = null;
  46         nbActiveNodes = 0;
  47     }
  48
  49     /**
  50      * Radix trie constructors.
  51      *
  52      * @param bits Maximum prefix length supported
  53      * @param rootZero Flag that decides if 0/0 should be inserted as a non-prefix root node or not
  54      */
  55     public RadixTrie(int bits, boolean rootZero) {
  56         maxBits = bits;
  57         root = rootZero ? new TrieNode(null, 0, null) : null;
  58         nbActiveNodes = 0;
  59         this.rootZero = rootZero;
  60     }
  61
  62     public TrieNode getRoot() {
  63         return root;
  64     }
  65
  66     private void setRoot(TrieNode root) {
  67         this.root = root;
  68     }
  69
  70     public int getMaxbits() {
  71         return maxBits;
  72     }
  73
  74     public long getSize() {
  75         return nbActiveNodes;
  76     }
  77
  78     /**
  79      * Test bit in byte. Assumes bits are numbered from 0 to 7
  80      * @param byteArg byte
  81      * @param bitPosition the position to be tested
  82      * @return 1 if bit at position is 1, 0 otherwise.
  83      */
  84     private boolean testBitInByte(byte byteArg, int bitPosition) {
  85         return (byteArg & (0x80 >> bitPosition)) != 0;
  86     }
  87
  88     private boolean testBitInPrefixByte(byte[] prefix, int bitPosition) {
  89         return testBitInByte(prefix[bitPosition / 8], bitPosition & 0x07);
  90     }
  91
  92     /**
  93      * Mask prefix.
  94      *
  95      * @param prefix Prefix to be masked
  96      * @param prefLen Prefix length
  97      * @return Prefix after masking
  98      */
  99     private byte [] maskPrefix(byte[] prefix, int prefLen) {
 100         byte[] res = prefix.clone();
 101         res[prefLen / 8] = (byte) (res[prefLen / 8] & (0xFF << (7 - (prefLen & 0x07))));
 102         for (int i = prefLen / 8 + 1; i < maxBits / 8; i++) {
 103             res[i] = 0;
 104         }
 105         return res;
 106     }
 107
 108     /**
 109      * Insert prefix-data tuple into radix trie.
 110      *
 111      * @param prefix Big endian (network order) byte array representation of the prefix
 112      * @param preflen Prefix length
 113      * @param data Data to be stored in the tree
 114      * @return Newly inserted TrieNode
 115      */
 116     public TrieNode insert(byte[] prefix, int preflen, T data) {
 117         if (preflen > maxBits) {
 118             return null;
 119         }
 120
 121         // trie is empty
 122         if (root == null) {
 123             root = new TrieNode(prefix, preflen, data);
 124             return root;
 125         }
 126
 127         // find closest prefix starting at ROOT
 128         TrieNode closest = root.findClosest(prefix, preflen, false);
 129
 130         // find first different bit <= min(closestNode.preflen, preflen)
 131         int diffbit = closest.firstDifferentBit(prefix, preflen);
 132
 133         // find the first node with bit less than diffbit
 134         TrieNode node = closest.parentWithBitLessThan(diffbit);
 135
 136         // insert new prefix
 137         return node.insert(prefix, preflen, diffbit, data, closest.prefix());
 138     }
 139
 140     /**
 141      * Longest prefix match of prefix/preflen.
 142      *
 143      * @param prefix Big endian byte array representation of the prefix to be looked up.
 144      * @param preflen Prefix length
 145      * @return Node with longest prefix match or null if nothing is found.
 146      */
 147     public TrieNode lookupBest(byte[] prefix, int preflen) {
 148         if (root == null || preflen > maxBits) {
 149             return null;
 150         }
 151
 152         TrieNode node = root;
 153         ArrayList<TrieNode> candidates = new ArrayList<>();
 154
 155         while (node != null && node.bit < preflen) {
 156             if (node.prefix != null) {
 157                 candidates.add(node);
 158             }
 159
 160             if (testBitInPrefixByte(prefix, node.bit)) {
 161                 node = node.right;
 162             } else {
 163                 node = node.left;
 164             }
 165         }
 166
 167         if (node != null && node.prefix != null) {
 168             candidates.add(node);
 169         }
 170
 171         ListIterator<TrieNode> it = candidates.listIterator(candidates.size());
 172         while (it.hasPrevious()) {
 173             node = it.previous();
 174             if (node.comparePrefix(prefix)) {
 175                 return node;
 176             }
 177         }
 178
 179         return null;
 180     }
 181
 182     /**
 183      * Look up the covering prefix for the argument, but exclude the argument itself, so the result is always less
 184      * specific than the lookup key.
 185      *
 186      * @param prefix Big endian byte array representation of the prefix argument
 187      * @param preflen Prefix length
 188      * @return Covering node
 189      */
 190     public TrieNode lookupCoveringLessSpecific(byte[] prefix, int preflen) {
 191         if (root == null || preflen > maxBits) {
 192             return null;
 193         }
 194
 195         TrieNode node = root.findClosest(prefix, preflen, true);
 196
 197         if (node == null) {
 198             return null;
 199         } else if (node.bit < preflen && node.prefix != null) {
 200             // If the current node is not virtual and is less specific than the query, we can return it directly
 201             return node;
 202         }
 203
 204         // Else, we need to find a non-virtual parent
 205         node = node.up;
 206
 207         while (node != null && node.prefix == null) {
 208             node = node.up;
 209         }
 210
 211         return node;
 212     }
 213
 214     /**
 215      * Given an EID, lookup the longest prefix match, then return its parent node.
 216      *
 217      * @param prefix Prefix looked up.
 218      * @param preflen Prefix length.
 219      * @return Parent node of longest prefix match or null if nothing is found.
 220      */
 221     public TrieNode lookupParent(byte[] prefix, int preflen) {
 222         TrieNode node = lookupBest(prefix, preflen);
 223
 224         if (node == null) {
 225             return null;
 226         }
 227
 228         node = node.up;
 229
 230         while (node != null && node.prefix == null) {
 231             node = node.up;
 232         }
 233
 234         return node;
 235     }
 236
 237     /**
 238      * Given an EID, lookup the longest prefix match, then return its sibling node.
 239      *
 240      * @param prefix Prefix looked up.
 241      * @param preflen Prefix length.
 242      * @return Sibling node of longest prefix match or null if nothing is found.
 243      */
 244     public TrieNode lookupSibling(byte[] prefix, int preflen) {
 245         TrieNode node = lookupBest(prefix, preflen);
 246         TrieNode sibling = node.sibling();
 247
 248         if (sibling.prefix != null) {
 249             return sibling;
 250         }
 251         return null;
 252     }
 253
 254
 255     /**
 256      * Given an EID, lookup the longest prefix match, then return its direct parent's sibling node, if the parent is a
 257      * virtual node.
 258      *
 259      * @param prefix Prefix looked up.
 260      * @param preflen Prefix length.
 261      * @return The longest prefix match node's virtual parent's sibling or null if nothing is found.
 262      */
 263     public TrieNode lookupVirtualParentSibling(byte[] prefix, int preflen) {
 264         TrieNode node = lookupBest(prefix, preflen);
 265
 266         if (node == null || node.up == null) {
 267             return null;
 268         }
 269
 270         // Parent is not a virtual node
 271         if (node.up.prefix != null) {
 272             return null;
 273         }
 274
 275         return node.up.sibling();
 276     }
 277
 278     /**
 279      * Lookup widest negative (i.e., overlapping but not present in trie) prefix for given prefix and prefix length.
 280      *
 281      * @param prefix Prefix looked up.
 282      * @param preflen Prefix length.
 283      * @return Node containing the widest negative prefix.
 284      */
 285     public TrieNode lookupWidestNegative(byte [] prefix, int preflen) {
 286         if (root == null || preflen > maxBits) {
 287             return null;
 288         }
 289
 290         TrieNode node = root.findClosest(prefix, preflen, false);
 291
 292         // not a negative match
 293         if (node.prefix != null && node.prefixLength() <= preflen && node.comparePrefix(prefix)) {
 294             return null;
 295         }
 296         int diffbit = node.firstDifferentBit(prefix, preflen);
 297         return new TrieNode(maskPrefix(prefix, diffbit), diffbit + 1, null);
 298     }
 299
 300     /**
 301      * Exact prefix match of prefix/preflen.
 302      *
 303      * @param prefix Big endian byte array representation of the prefix to be looked up.
 304      * @param preflen Prefix length
 305      * @return Node with exact prefix match or null
 306      */
 307     public TrieNode lookupExact(byte[] prefix, int preflen) {
 308         if (root == null || preflen > maxBits) {
 309             return null;
 310         }
 311
 312         TrieNode node = root.findClosest(prefix, preflen, false);
 313
 314         // if no node is found or if node not a prefix or if mask is not the same
 315         if (node == null || node.prefix == null || node.bit != preflen) {
 316             return null;
 317         }
 318
 319         // check that we have exact match
 320         if (node.comparePrefix(prefix)) {
 321             return node;
 322         }
 323
 324         return null;
 325     }
 326
 327     /**
 328      * Return the subtree for a prefix, including the prefix itself if present, excluding virtual nodes.
 329      *
 330      * @param prefix Big endian byte array representation of the prefix to be looked up.
 331      * @param preflen Prefix length
 332      * @return Subtree from the prefix
 333      */
 334     public Set<TrieNode> lookupSubtree(byte[] prefix, int preflen) {
 335         if (root == null || preflen > maxBits) {
 336             return Collections.emptySet();
 337         }
 338
 339         TrieNode node = root.findClosest(prefix, preflen, true);
 340
 341         Set<TrieNode> children = new HashSet<>();
 342         if (node.prefix != null && node.bit >= preflen) {
 343             children.add(node);
 344         }
 345         Iterator<TrieNode> it = node.iterator();
 346         while (it.hasNext()) {
 347             node = it.next();
 348             if (node.prefix != null && node.bit >= preflen) {
 349                 children.add(node);
 350             }
 351         }
 352
 353         return children;
 354     }
 355
 356     /**
 357      * Remove prefix from radix trie.
 358      *
 359      * @param prefix Big endian byte array representation of the prefix to be removed.
 360      * @param preflen Prefix length.
 361      */
 362     public void remove(byte[] prefix, int preflen) {
 363         TrieNode node = lookupExact(prefix, preflen);
 364         if (node != null) {
 365             node.erase();
 366         }
 367     }
 368
 369     /**
 370      * Remove all entries in the trie.
 371      */
 372     public void removeAll() {
 373         Iterator<TrieNode> it = root.iterator();
 374         while (it.hasNext()) {
 375             TrieNode node = it.next();
 376             node.erase();
 377         }
 378     }
 379
 380     /**
 381      * Trie node definition.
 382      */
 383     public class TrieNode implements Iterable<TrieNode> {
 384         // since bits are counted from 0, bit and prefix length are equal
 385         int bit;
 386         byte[] prefix;
 387         TrieNode left;
 388         TrieNode right;
 389         TrieNode up;
 390         T data;
 391
 392         TrieNode(byte[] prefix, int prefixlen, T data) {
 393             this.bit = prefixlen;
 394             this.prefix = prefix;
 395             this.data = data;
 396             left = null;
 397             right = null;
 398         }
 399
 400         public byte[] prefix() {
 401             return prefix;
 402         }
 403
 404         public int prefixLength() {
 405             return bit;
 406         }
 407
 408         public T data() {
 409             return data;
 410         }
 411
 412         /**
 413          * Finds closest prefix NOT the longest prefix match.
 414          *
 415          * @param pref Searched prefix
 416          * @param preflen Searched prefix length
 417          * @param virtual Include virtual nodes in search
 418          * @return The node found
 419          */
 420         public TrieNode findClosest(byte[] pref, int preflen, boolean virtual) {
 421             TrieNode node = this;
 422
 423             while ((!virtual && node.prefix == null) || node.bit < preflen) {
 424                 if (testBitInPrefixByte(pref, node.bit)) {
 425                     if (node.right == null) {
 426                         break;
 427                     }
 428                     node = node.right;
 429                 } else {
 430                     if (node.left == null) {
 431                         break;
 432                     }
 433                     node = node.left;
 434                 }
 435             }
 436             return node;
 437         }
 438
 439
 440         private int toUnsignedInt(byte byteToConvert) {
 441             return 0xFF & byteToConvert;
 442         }
 443
 444         /**
 445          * Compares prefix to node's prefix and returns position of first different bit.
 446          *
 447          * @param pref Prefix to be compared.
 448          * @param preflen Prefix length.
 449          * @return Position of first different bit.
 450          */
 451         public int firstDifferentBit(byte[] pref, int preflen) {
 452             int bitxor;
 453
 454             int maxbit = (bit < preflen) ? bit : preflen;
 455             int diffbit = 0;
 456             for (int i = 0; i * 8 < maxbit; i++) {
 457                 bitxor = ((toUnsignedInt(this.prefix[i])) ^ toUnsignedInt(pref[i]));
 458                 // if match, move to next byte
 459                 if (bitxor == 0) {
 460                     diffbit = (i + 1) * 8;
 461                     continue;
 462                 }
 463                 // if not matched, find first diff bit (0 to 7)
 464                 diffbit = i * 8 + Integer.numberOfLeadingZeros(bitxor) - 24;
 465                 break;
 466             }
 467
 468             diffbit = (diffbit > maxbit) ? maxbit : diffbit;
 469             return diffbit;
 470         }
 471
 472         /**
 473          * Find parent with bit less than given value.
 474          *
 475          * @param bitlen Bit value
 476          * @return Parent with bit less than given value
 477          */
 478         public TrieNode parentWithBitLessThan(int bitlen) {
 479             TrieNode node = this;
 480             TrieNode parent = node.up;
 481             while (parent != null && parent.bit >= bitlen) {
 482                 node = parent;
 483                 parent = node.up;
 484             }
 485             return node;
 486         }
 487
 488         /**
 489          * Return sibling node.
 490          *
 491          * @return Sibling node, if there is a parent, else null
 492          */
 493         public TrieNode sibling() {
 494             TrieNode node = this;
 495             if (node == null || node.up == null) {
 496                 return null;
 497             }
 498
 499             TrieNode sibling = null;
 500             if (node.up.left == node) {
 501                 sibling = node.up.right;
 502             } else {
 503                 sibling = node.up.left;
 504             }
 505             return sibling;
 506         }
 507
 508         /**
 509          * Inserts node in trie near this node with prefix that has the first bit difference at diffbit.
 510          *
 511          * @param pref Prefix to be inserted.
 512          * @param preflen Prefix length of the prefix to be inserted.
 513          * @param diffbit Bit index of the first different bit between prefix and current node
 514          * @param prefdata Data to be stored together with the prefix
 515          * @return The trie node created or current node if it's an overwrite.
 516          */
 517         public TrieNode insert(byte[] pref, int preflen, int diffbit, T prefdata, byte[] closest) {
 518             TrieNode parent;
 519
 520             // same node, check if prefix needs saving
 521             if (diffbit == preflen && bit == preflen) {
 522                 if (prefix != null) {
 523                     return this;
 524                 }
 525                 this.prefix = pref;
 526                 this.data = prefdata;
 527                 nbActiveNodes++;
 528                 return this;
 529             }
 530
 531             TrieNode newNode = new TrieNode(pref, preflen, prefdata);
 532
 533             // node is more specific, add new prefix as parent
 534             if (preflen == diffbit) {
 535                 if (prefix == null ? testBitInPrefixByte(closest, preflen) : testBitInPrefixByte(prefix, preflen)) {
 536                     newNode.right = this;
 537                 } else {
 538                     newNode.left = this;
 539                 }
 540                 newNode.up = up;
 541
 542                 if (up == null) {
 543                     setRoot(newNode);
 544                 } else if (this.equals(up.right)) {
 545                     up.right = newNode;
 546                 } else {
 547                     up.left = newNode;
 548                 }
 549
 550                 up = newNode;
 551             // new prefix is more specific than node, add as child
 552             } else if (bit == diffbit) {
 553                 newNode.up = this;
 554                 if (testBitInPrefixByte(pref, bit)) {
 555                     right = newNode;
 556                 } else {
 557                     left = newNode;
 558                 }
 559             // new prefix is a sibling of/on a different branch from node, add common parent
 560             } else {
 561                 parent = new TrieNode(null, diffbit, null);
 562                 parent.up = up;
 563                 if (testBitInPrefixByte(pref, diffbit)) {
 564                     parent.right = newNode;
 565                     parent.left = this;
 566                 } else {
 567                     parent.right = this;
 568                     parent.left = newNode;
 569                 }
 570                 newNode.up = parent;
 571                 if (up == null) {
 572                     setRoot(parent);
 573                 } else if (this.equals(up.right)) {
 574                     up.right = parent;
 575                 } else {
 576                     up.left = parent;
 577                 }
 578                 up = parent;
 579             }
 580             nbActiveNodes++;
 581             return newNode;
 582         }
 583
 584         /**
 585          * Erase node.
 586          */
 587         public void erase() {
 588             TrieNode cur = this;
 589             boolean isRoot = false;
 590
 591             if (this.equals(root)) {
 592                 isRoot = true;
 593             }
 594
 595             if (prefix != null) {
 596                 resetData();
 597             }
 598
 599             // as long as one of the children is null and this is an intermediary node
 600             // link parent to child. If parent null, child becomes the root.
 601             while (cur != null && cur.prefix == null && (cur.left == null || cur.right == null)) {
 602                 TrieNode parent = cur.up;
 603                 TrieNode child = cur.left != null ? cur.left : cur.right;
 604
 605                 if (parent == null) {
 606                     if (child != null) {
 607                         if (!rootZero) {
 608                             child.up = null;
 609                             setRoot(child);
 610                         }
 611                     } else {
 612                         isRoot = true;
 613                     }
 614                 } else {
 615                     if (parent.left != null && parent.left.equals(cur)) {
 616                         parent.left = child;
 617                     } else {
 618                         parent.right = child;
 619                     }
 620                     if (child != null) {
 621                         child.up = parent;
 622                     }
 623                 }
 624
 625                 cur.resetData();
 626                 cur = parent;
 627             }
 628
 629             if (isRoot) {
 630                 setRoot((rootZero ? new TrieNode(null, 0, null) : null));
 631             }
 632
 633             nbActiveNodes--;
 634         }
 635
 636         /**
 637          * Clear node data.
 638          */
 639         public void resetData() {
 640             prefix = null;
 641             data = null;
 642         }
 643
 644         /**
 645          * Compare node prefix with prefix.
 646          *
 647          * @param pref Prefix to be compared
 648          * @return True if prefixes are equal, false otherwise
 649          */
 650         public boolean comparePrefix(byte[] pref) {
 651             int iterator;
 652             int remainder;
 653
 654             for (iterator = 0; iterator < bit / 8; iterator++) {
 655                 if (prefix[iterator] != pref[iterator]) {
 656                     return false;
 657                 }
 658             }
 659
 660             remainder = bit % 8;
 661             if (remainder != 0) {
 662                 int mask = (0xFF << (8 - remainder)) & 0xFF;
 663                 return ((prefix[iterator] & mask) == (pref[iterator] & mask));
 664             }
 665             return true;
 666         }
 667
 668         /**
 669          * Helper method that converts prefix and prefix length to dotted decimal, string, representation.
 670          *
 671          * @return String representation of prefix.
 672          */
 673         public String asIpPrefix() {
 674             try {
 675                 return InetAddress.getByAddress(prefix).getHostAddress() + "/" + bit;
 676             } catch (UnknownHostException e) {
 677                 return "NaA/" + bit;
 678             }
 679         }
 680
 681         /**
 682          * Retrieve iterator.
 683          */
 684         @Override
 685         public Iterator<RadixTrie<T>.TrieNode> iterator() {
 686             return new TriePostOrderIterator(this);
 687         }
 688
 689         @Override
 690         public String toString() {
 691             StringBuilder sb = new StringBuilder();
 692             sb.append(printPrefixAndMask());
 693             if (up != null) {
 694                 sb.append(", parent: ");
 695                 sb.append(up.printPrefixAndMask());
 696             }
 697             if (left != null) {
 698                 sb.append(", left child: ");
 699                 sb.append(left.printPrefixAndMask());
 700             }
 701             if (right != null) {
 702                 sb.append(", right child: ");
 703                 sb.append(right.printPrefixAndMask());
 704             }
 705             if (data != null) {
 706                 sb.append(", data: ");
 707                 sb.append(data);
 708             }
 709             return sb.toString();
 710         }
 711
 712         private String printPrefixAndMask() {
 713             if (prefix == null) {
 714                 return "Virtual @ bit " + bit;
 715             }
 716             StringBuilder sb = new StringBuilder();
 717             try {
 718                 sb.append(InetAddress.getByAddress(prefix));
 719                 sb.append("/");
 720                 sb.append(bit);
 721             } catch (UnknownHostException e) {
 722                 return "NaP";
 723             }
 724             return sb.toString();
 725         }
 726
 727         /**
 728          * Post order iterator implementation for prefix trie. It's safe to use it to remove nodes.
 729          */
 730         private class TriePostOrderIterator implements Iterator<RadixTrie<T>.TrieNode> {
 731             private TrieNode current;
 732             private TrieNode lastNodeVisited;
 733             private Deque<RadixTrie<T>.TrieNode> stack;
 734
 735             TriePostOrderIterator(TrieNode node) {
 736                 stack = new ArrayDeque<>();
 737                 current = node;
 738                 lastNodeVisited = null;
 739             }
 740
 741             @Override
 742             public boolean hasNext() {
 743                 TrieNode peekNode;
 744                 TrieNode last = lastNodeVisited;
 745                 if (current != null && (current.left != null || current.right != null)) {
 746                     return true;
 747                 } else {
 748                     Iterator<TrieNode> it = stack.iterator();
 749                     while (it.hasNext()) {
 750                         peekNode = it.next();
 751                         if (peekNode.right != null && !peekNode.right.equals(last)) {
 752                             return true;
 753                         } else {
 754                             last = peekNode;
 755                             if (peekNode.prefix != null) {
 756                                 return true;
 757                             }
 758                         }
 759                     }
 760                 }
 761                 return false;
 762             }
 763
 764             @Override
 765             public RadixTrie<T>.TrieNode next() {
 766                 TrieNode peekNode;
 767                 TrieNode next = current;
 768                 while (!stack.isEmpty() || next != null) {
 769                     if (next != null) {
 770                         stack.push(next);
 771                         next = next.left;
 772                     } else {
 773                         peekNode = stack.peek();
 774                         if (peekNode.right != null && !peekNode.right.equals(lastNodeVisited)) {
 775                             next = peekNode.right;
 776                         } else {
 777                             lastNodeVisited = stack.pop();
 778                             if (peekNode.prefix != null) {
 779                                 current = null;
 780                                 return peekNode;
 781                             }
 782                         }
 783                     }
 784                 }
 785                 return null;
 786             }
 787         }
 788     }
 789 }