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);
 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      * Given an EID, lookup the longest prefix match, then return its parent node.
 184      *
 185      * @param prefix Prefix looked up.
 186      * @param preflen Prefix length.
 187      * @return Parent node of longest prefix match or null if nothing is found.
 188      */
 189     public TrieNode lookupParent(byte[] prefix, int preflen) {
 190         TrieNode node = lookupBest(prefix, preflen);
 191
 192         if (node == null) {
 193             return null;
 194         } else {
 195             node = node.up;
 196         }
 197
 198         while (node != null && node.prefix == null) {
 199             node = node.up;
 200         }
 201
 202         return node;
 203     }
 204
 205     /**
 206      * Given an EID, lookup the longest prefix match, then return its sibling node.
 207      *
 208      * @param prefix Prefix looked up.
 209      * @param preflen Prefix length.
 210      * @return Sibling node of longest prefix match or null if nothing is found.
 211      */
 212     public TrieNode lookupSibling(byte[] prefix, int preflen) {
 213         TrieNode node = lookupBest(prefix, preflen);
 214         TrieNode sibling = node.sibling();
 215
 216         if (sibling.prefix != null) {
 217             return sibling;
 218         }
 219         return null;
 220     }
 221
 222
 223     /**
 224      * Given an EID, lookup the longest prefix match, then return its direct parent's sibling node, if the parent is a
 225      * virtual node.
 226      *
 227      * @param prefix Prefix looked up.
 228      * @param preflen Prefix length.
 229      * @return The longest prefix match node's virtual parent's sibling or null if nothing is found.
 230      */
 231     public TrieNode lookupVirtualParentSibling(byte[] prefix, int preflen) {
 232         TrieNode node = lookupBest(prefix, preflen);
 233
 234         if (node == null || node.up == null) {
 235             return null;
 236         }
 237
 238         // Parent is not a virtual node
 239         if (node.up.prefix != null) {
 240             return null;
 241         }
 242
 243         return node.up.sibling();
 244     }
 245
 246     /**
 247      * Lookup widest negative (i.e., overlapping but not present in trie) prefix for given prefix and prefix length.
 248      *
 249      * @param prefix Prefix looked up.
 250      * @param preflen Prefix length.
 251      * @return Node containing the widest negative prefix.
 252      */
 253     public TrieNode lookupWidestNegative(byte [] prefix, int preflen) {
 254         if (root == null || preflen > maxBits) {
 255             return null;
 256         }
 257
 258         TrieNode node = root.findClosest(prefix, preflen);
 259
 260         // not a negative match
 261         if (node.prefix != null && node.prefixLength() <= preflen && node.comparePrefix(prefix)) {
 262             return null;
 263         }
 264         int diffbit = node.firstDifferentBit(prefix, preflen);
 265         return new TrieNode(maskPrefix(prefix, diffbit), diffbit + 1, null);
 266     }
 267
 268     /**
 269      * Exact prefix match of prefix/preflen.
 270      *
 271      * @param prefix Big endian byte array representation of the prefix to be looked up.
 272      * @param preflen Prefix length
 273      * @return Node with exact prefix match or null
 274      */
 275     public TrieNode lookupExact(byte[] prefix, int preflen) {
 276         if (root == null || preflen > maxBits) {
 277             return null;
 278         }
 279
 280         TrieNode node = root.findClosest(prefix, preflen);
 281
 282         // if no node is found or if node not a prefix or if mask is not the same
 283         if (node == null || node.prefix == null || node.bit != preflen) {
 284             return null;
 285         }
 286
 287         // check that we have exact match
 288         if (node.comparePrefix(prefix)) {
 289             return node;
 290         }
 291
 292         return null;
 293     }
 294
 295     /**
 296      * Return the subtree for a prefix, including the prefix itself if present, excluding virtual nodes.
 297      *
 298      * @param prefix Big endian byte array representation of the prefix to be looked up.
 299      * @param preflen Prefix length
 300      * @return Subtree from the prefix
 301      */
 302     public Set<TrieNode> lookupSubtree(byte[] prefix, int preflen) {
 303         if (root == null || preflen > maxBits) {
 304             return Collections.emptySet();
 305         }
 306
 307         TrieNode node = root.findClosest(prefix, preflen);
 308
 309         // if no node is found or if node not a prefix
 310         if (node == null || node.prefix == null) {
 311             return Collections.emptySet();
 312         }
 313
 314         Set<TrieNode> children = new HashSet<>();
 315         children.add(node);
 316         Iterator<TrieNode> it = node.iterator();
 317         while (it.hasNext()) {
 318             node = it.next();
 319             if (node.prefix != null) {
 320                 children.add(node);
 321             }
 322         }
 323
 324         return children;
 325     }
 326
 327     /**
 328      * Remove prefix from radix trie.
 329      *
 330      * @param prefix Big endian byte array representation of the prefix to be removed.
 331      * @param preflen Prefix length.
 332      */
 333     public void remove(byte[] prefix, int preflen) {
 334         TrieNode node = lookupExact(prefix, preflen);
 335         if (node != null) {
 336             node.erase();
 337         }
 338     }
 339
 340     /**
 341      * Remove node's subtree.
 342      *
 343      * @param node Node who's subtree is to be removed
 344      */
 345     public void removeSubtree(TrieNode node) {
 346         TrieNode itNode;
 347         Iterator<TrieNode> it = node.iterator();
 348
 349         while (it.hasNext()) {
 350             itNode = it.next();
 351             itNode.erase();
 352         }
 353     }
 354
 355     /**
 356      * Remove subtree for longest match.
 357      *
 358      * @param prefix Prefix to be looked up
 359      * @param preflen Prefix length
 360      */
 361     public void removeSubtree(byte[] prefix, int preflen) {
 362         TrieNode itNode = lookupBest(prefix, preflen);
 363
 364         if (itNode == null) {
 365             return;
 366         }
 367
 368         Iterator<TrieNode> it = itNode.iterator();
 369
 370         while (it.hasNext()) {
 371             itNode = it.next();
 372             itNode.erase();
 373         }
 374     }
 375
 376     /**
 377      * Remove all entries in the trie.
 378      */
 379     public void removeAll() {
 380         Iterator<TrieNode> it = root.iterator();
 381         while (it.hasNext()) {
 382             TrieNode node = it.next();
 383             node.erase();
 384         }
 385     }
 386
 387     /**
 388      * Trie node definition.
 389      */
 390     public class TrieNode implements Iterable<TrieNode> {
 391         // since bits are counted from 0, bit and prefix length are equal
 392         int bit;
 393         byte[] prefix;
 394         TrieNode left;
 395         TrieNode right;
 396         TrieNode up;
 397         T data;
 398
 399         TrieNode(byte[] prefix, int prefixlen, T data) {
 400             this.bit = prefixlen;
 401             this.prefix = prefix;
 402             this.data = data;
 403             left = null;
 404             right = null;
 405         }
 406
 407         public byte[] prefix() {
 408             return prefix;
 409         }
 410
 411         public int prefixLength() {
 412             return bit;
 413         }
 414
 415         public T data() {
 416             return data;
 417         }
 418
 419         /**
 420          * Finds closest prefix NOT the longest prefix match.
 421          *
 422          * @param pref Searched prefix
 423          * @param preflen Searched prefix length
 424          * @return The node found
 425          */
 426         public TrieNode findClosest(byte[] pref, int preflen) {
 427             TrieNode node = this;
 428
 429             while (node.prefix == null || node.bit < preflen) {
 430                 if (testBitInPrefixByte(pref, node.bit)) {
 431                     if (node.right == null) {
 432                         break;
 433                     }
 434                     node = node.right;
 435                 } else {
 436                     if (node.left == null) {
 437                         break;
 438                     }
 439                     node = node.left;
 440                 }
 441             }
 442             return node;
 443         }
 444
 445
 446         private int toUnsignedInt(byte byteToConvert) {
 447             return 0xFF & byteToConvert;
 448         }
 449
 450         /**
 451          * Compares prefix to node's prefix and returns position of first different bit.
 452          *
 453          * @param pref Prefix to be compared.
 454          * @param preflen Prefix length.
 455          * @return Position of first different bit.
 456          */
 457         public int firstDifferentBit(byte[] pref, int preflen) {
 458             int bitxor;
 459
 460             int maxbit = (bit < preflen) ? bit : preflen;
 461             int diffbit = 0;
 462             for (int i = 0; i * 8 < maxbit; i++) {
 463                 bitxor = ((toUnsignedInt(this.prefix[i])) ^ toUnsignedInt(pref[i]));
 464                 // if match, move to next byte
 465                 if (bitxor == 0) {
 466                     diffbit = (i + 1) * 8;
 467                     continue;
 468                 }
 469                 // if not matched, find first diff bit (0 to 7)
 470                 diffbit = i * 8 + Integer.numberOfLeadingZeros(bitxor) - 24;
 471                 break;
 472             }
 473
 474             diffbit = (diffbit > maxbit) ? maxbit : diffbit;
 475             return diffbit;
 476         }
 477
 478         /**
 479          * Find parent with bit less than given value.
 480          *
 481          * @param bitlen Bit value
 482          * @return Parent with bit less than given value
 483          */
 484         public TrieNode parentWithBitLessThan(int bitlen) {
 485             TrieNode node = this;
 486             TrieNode parent = node.up;
 487             while (parent != null && parent.bit >= bitlen) {
 488                 node = parent;
 489                 parent = node.up;
 490             }
 491             return node;
 492         }
 493
 494         /**
 495          * Return sibling node.
 496          *
 497          * @return Sibling node, if there is a parent, else null
 498          */
 499         public TrieNode sibling() {
 500             TrieNode node = this;
 501             if (node == null || node.up == null) {
 502                 return null;
 503             }
 504
 505             TrieNode sibling = null;
 506             if (node.up.left == node) {
 507                 sibling = node.up.right;
 508             } else {
 509                 sibling = node.up.left;
 510             }
 511             return sibling;
 512         }
 513
 514         /**
 515          * Inserts node in trie near this node with prefix that has the first bit difference at diffbit.
 516          *
 517          * @param pref Prefix to be inserted.
 518          * @param preflen Prefix length of the prefix to be inserted.
 519          * @param diffbit Bit index of the first different bit between prefix and current node
 520          * @param prefdata Data to be stored together with the prefix
 521          * @return The trie node created or current node if it's an overwrite.
 522          */
 523         public TrieNode insert(byte[] pref, int preflen, int diffbit, T prefdata, byte[] closest) {
 524             TrieNode parent;
 525
 526             // same node, check if prefix needs saving
 527             if (diffbit == preflen && bit == preflen) {
 528                 if (prefix != null) {
 529                     return this;
 530                 }
 531                 this.prefix = pref;
 532                 this.data = prefdata;
 533                 nbActiveNodes++;
 534                 return this;
 535             }
 536
 537             TrieNode newNode = new TrieNode(pref, preflen, prefdata);
 538
 539             // node is more specific, add new prefix as parent
 540             if (preflen == diffbit) {
 541                 if (prefix == null ? testBitInPrefixByte(closest, preflen) : testBitInPrefixByte(prefix, preflen)) {
 542                     newNode.right = this;
 543                 } else {
 544                     newNode.left = this;
 545                 }
 546                 newNode.up = up;
 547
 548                 if (up == null) {
 549                     setRoot(newNode);
 550                 } else if (this.equals(up.right)) {
 551                     up.right = newNode;
 552                 } else {
 553                     up.left = newNode;
 554                 }
 555
 556                 up = newNode;
 557             // new prefix is more specific than node, add as child
 558             } else if (bit == diffbit) {
 559                 newNode.up = this;
 560                 if (testBitInPrefixByte(pref, bit)) {
 561                     right = newNode;
 562                 } else {
 563                     left = newNode;
 564                 }
 565             // new prefix is a sibling of/on a different branch from node, add common parent
 566             } else {
 567                 parent = new TrieNode(null, diffbit, null);
 568                 parent.up = up;
 569                 if (testBitInPrefixByte(pref, diffbit)) {
 570                     parent.right = newNode;
 571                     parent.left = this;
 572                 } else {
 573                     parent.right = this;
 574                     parent.left = newNode;
 575                 }
 576                 newNode.up = parent;
 577                 if (up == null) {
 578                     setRoot(parent);
 579                 } else if (this.equals(up.right)) {
 580                     up.right = parent;
 581                 } else {
 582                     up.left = parent;
 583                 }
 584                 up = parent;
 585             }
 586             nbActiveNodes++;
 587             return newNode;
 588         }
 589
 590         /**
 591          * Erase node.
 592          */
 593         public void erase() {
 594             TrieNode cur = this;
 595             boolean isRoot = false;
 596
 597             if (this.equals(root)) {
 598                 isRoot = true;
 599             }
 600
 601             if (prefix != null) {
 602                 resetData();
 603             }
 604
 605             // as long as one of the children is null and this is an intermediary node
 606             // link parent to child. If parent null, child becomes the root.
 607             while (cur != null && cur.prefix == null && (cur.left == null || cur.right == null)) {
 608                 TrieNode parent = cur.up;
 609                 TrieNode child = cur.left != null ? cur.left : cur.right;
 610
 611                 if (parent == null) {
 612                     if (child != null) {
 613                         if (!rootZero) {
 614                             child.up = null;
 615                             setRoot(child);
 616                         }
 617                     } else {
 618                         isRoot = true;
 619                     }
 620                 } else {
 621                     if (parent.left != null && parent.left.equals(cur)) {
 622                         parent.left = child;
 623                     } else {
 624                         parent.right = child;
 625                     }
 626                     if (child != null) {
 627                         child.up = parent;
 628                     }
 629                 }
 630
 631                 cur.resetData();
 632                 cur = parent;
 633             }
 634
 635             if (isRoot) {
 636                 setRoot((rootZero ? new TrieNode(null, 0, null) : null));
 637             }
 638
 639             nbActiveNodes--;
 640         }
 641
 642         /**
 643          * Clear node data.
 644          */
 645         public void resetData() {
 646             prefix = null;
 647             data = null;
 648         }
 649
 650         /**
 651          * Compare node prefix with prefix.
 652          *
 653          * @param pref Prefix to be compared
 654          * @return True if prefixes are equal, false otherwise
 655          */
 656         public boolean comparePrefix(byte[] pref) {
 657             int iterator;
 658             int remainder;
 659
 660             for (iterator = 0; iterator < bit / 8; iterator++) {
 661                 if (prefix[iterator] != pref[iterator]) {
 662                     return false;
 663                 }
 664             }
 665
 666             remainder = bit % 8;
 667             if (remainder != 0) {
 668                 int mask = (0xFF << (8 - remainder)) & 0xFF;
 669                 return ((prefix[iterator] & mask) == (pref[iterator] & mask));
 670             }
 671             return true;
 672         }
 673
 674         /**
 675          * Helper method that converts prefix and prefix length to dotted decimal, string, representation.
 676          *
 677          * @return String representation of prefix.
 678          */
 679         public String asIpPrefix() {
 680             try {
 681                 return InetAddress.getByAddress(prefix).getHostAddress() + "/" + bit;
 682             } catch (UnknownHostException e) {
 683                 return "NaA/" + bit;
 684             }
 685         }
 686
 687         /**
 688          * Retrieve iterator.
 689          */
 690         @Override
 691         public Iterator<RadixTrie<T>.TrieNode> iterator() {
 692             return new TriePostOrderIterator(this);
 693         }
 694
 695         /**
 696          * Post order iterator implementation for prefix trie. It's safe to use it to remove nodes.
 697          */
 698         private class TriePostOrderIterator implements Iterator<RadixTrie<T>.TrieNode> {
 699             private TrieNode current;
 700             private TrieNode lastNodeVisited;
 701             private Deque<RadixTrie<T>.TrieNode> stack;
 702
 703             TriePostOrderIterator(TrieNode node) {
 704                 stack = new ArrayDeque<>();
 705                 current = node;
 706                 lastNodeVisited = null;
 707             }
 708
 709             @Override
 710             public boolean hasNext() {
 711                 TrieNode peekNode;
 712                 TrieNode last = lastNodeVisited;
 713                 if (current != null && (current.left != null || current.right != null)) {
 714                     return true;
 715                 } else {
 716                     Iterator<TrieNode> it = stack.iterator();
 717                     while (it.hasNext()) {
 718                         peekNode = it.next();
 719                         if (peekNode.right != null && !peekNode.right.equals(last)) {
 720                             return true;
 721                         } else {
 722                             last = peekNode;
 723                             if (peekNode.prefix != null) {
 724                                 return true;
 725                             }
 726                         }
 727                     }
 728                 }
 729                 return false;
 730             }
 731
 732             @Override
 733             public RadixTrie<T>.TrieNode next() {
 734                 TrieNode peekNode;
 735                 TrieNode next = current;
 736                 while (!stack.isEmpty() || next != null) {
 737                     if (next != null) {
 738                         stack.push(next);
 739                         next = next.left;
 740                     } else {
 741                         peekNode = stack.peek();
 742                         if (peekNode.right != null && !peekNode.right.equals(lastNodeVisited)) {
 743                             next = peekNode.right;
 744                         } else {
 745                             lastNodeVisited = stack.pop();
 746                             if (peekNode.prefix != null) {
 747                                 current = null;
 748                                 return peekNode;
 749                             }
 750                         }
 751                     }
 752                 }
 753                 return null;
 754             }
 755         }
 756     }
 757 }