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