Jonathan Hart | 8f6dc09 | 2014-04-18 15:56:43 -0700 | [diff] [blame] | 1 | package net.onrc.onos.apps.sdnip; |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 2 | |
| 3 | import java.util.Iterator; |
| 4 | |
Jonathan Hart | 31e15f1 | 2014-04-10 10:33:00 -0700 | [diff] [blame] | 5 | /** |
| 6 | * A PATRICIA tree is data structure for storing data where entries aggregate |
| 7 | * based on shared prefixes. They provide lookups in O(k) where k is the |
| 8 | * maximum length of the strings in the tree. They work well for storing IP |
| 9 | * addresses. |
| 10 | * <p/> |
| 11 | * SDN-IP uses a patricia tree to store routes learnt from BGPd. BGPd sends |
| 12 | * route updates in the form: |
| 13 | * {@code <prefix, next_hop>}, |
| 14 | * e.g. {@code <192.168.1.0/24, 10.0.0.1>} |
| 15 | * <p/> |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 16 | * These updates are stored in the patricia tree, which acts as a map from |
Jonathan Hart | 31e15f1 | 2014-04-10 10:33:00 -0700 | [diff] [blame] | 17 | * {@code prefix} to {@code next_hop}. {@code next_hop} values can be looked up |
| 18 | * by prefix. |
| 19 | * |
| 20 | * @param <V> The class of the data to stored in the patricia tree |
| 21 | * |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 22 | * @see <a href="http://en.wikipedia.org/wiki/Patricia_tree">Patricia tree</a> |
Jonathan Hart | 31e15f1 | 2014-04-10 10:33:00 -0700 | [diff] [blame] | 23 | */ |
Jonathan Hart | 5e54f2e | 2014-04-17 13:43:40 -0700 | [diff] [blame] | 24 | public interface IPatriciaTree<V> { |
Jonathan Hart | 31e15f1 | 2014-04-10 10:33:00 -0700 | [diff] [blame] | 25 | /** |
| 26 | * Puts a new mapping into the patricia tree. |
| 27 | * |
| 28 | * @param prefix the Prefix which is the key for this entry |
| 29 | * @param value the value that maps to the Prefix |
| 30 | * @return the old value that was mapped to the Prefix, or null if there |
| 31 | * was no such mapping |
| 32 | */ |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 33 | public V put(Prefix prefix, V value); |
| 34 | |
Jonathan Hart | 31e15f1 | 2014-04-10 10:33:00 -0700 | [diff] [blame] | 35 | /** |
| 36 | * Searches the tree for a prefix that exactly matches the argument. If an |
| 37 | * exact match for the prefix is found in the tree, the value it maps to is |
| 38 | * returned. Otherwise, null is returned. |
| 39 | * |
| 40 | * @param prefix the prefix to look up in the tree |
| 41 | * @return the value if the prefix was found, otherwise null |
| 42 | */ |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 43 | public V lookup(Prefix prefix); |
| 44 | |
Jonathan Hart | 31e15f1 | 2014-04-10 10:33:00 -0700 | [diff] [blame] | 45 | /** |
| 46 | * Searches the tree for the closest containing prefix of the supplied |
| 47 | * argument. If an exact match is found, that will be returned. Otherwise, |
| 48 | * the value of the most specific prefix that contains the argument prefix |
| 49 | * will be returned. If no such prefix is found, null is returned. |
| 50 | * |
| 51 | * @param prefix the prefix to find the closest containing match for in the |
| 52 | * tree |
| 53 | * @return the value of the match if one was found, otherwise null |
| 54 | */ |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 55 | public V match(Prefix prefix); |
| 56 | |
Jonathan Hart | 31e15f1 | 2014-04-10 10:33:00 -0700 | [diff] [blame] | 57 | /** |
| 58 | * Removes a prefix to value mapping from the tree. The prefix argument is |
| 59 | * first looked up in the same way as the {@link #lookup(Prefix)} method. |
| 60 | * If an exact match to the prefix is found in the tree, its value is |
| 61 | * is checked to see if it matches the supplied argument value. The prefix |
| 62 | * and value will be removed only if both the prefix and value arguments |
| 63 | * match a mapping in the tree. |
| 64 | * |
| 65 | * @param prefix the prefix to remove from the tree |
| 66 | * @param value the value that must be mapped to the prefix for it to be |
| 67 | * removed |
| 68 | * @return true if a mapping was removed, otherwise false |
| 69 | */ |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 70 | public boolean remove(Prefix prefix, V value); |
| 71 | |
Jonathan Hart | 31e15f1 | 2014-04-10 10:33:00 -0700 | [diff] [blame] | 72 | /** |
| 73 | * Gets an iterator over all mappings in the tree. |
| 74 | * |
| 75 | * @return an iterator that will iterate over all entries in the tree |
| 76 | */ |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 77 | public Iterator<Entry<V>> iterator(); |
| 78 | |
Jonathan Hart | 31e15f1 | 2014-04-10 10:33:00 -0700 | [diff] [blame] | 79 | /** |
| 80 | * Represents an entry in the patricia tree. The {@code Entry} is a mapping |
| 81 | * from {@link Prefix} to a {@link V} value object. |
| 82 | * |
| 83 | * @param <V> the class of objects stored in the tree |
| 84 | */ |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 85 | interface Entry<V> { |
Jonathan Hart | 31e15f1 | 2014-04-10 10:33:00 -0700 | [diff] [blame] | 86 | /** |
| 87 | * Gets the {@link Prefix} object for this entry. |
| 88 | * |
| 89 | * @return the prefix for this entry |
| 90 | */ |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 91 | public Prefix getPrefix(); |
| 92 | |
Jonathan Hart | 31e15f1 | 2014-04-10 10:33:00 -0700 | [diff] [blame] | 93 | /** |
| 94 | * Gets the value of this entry. |
| 95 | * |
| 96 | * @return the value object of this entry |
| 97 | */ |
Ray Milkey | 269ffb9 | 2014-04-03 14:43:30 -0700 | [diff] [blame] | 98 | public V getValue(); |
| 99 | } |
Jonathan Hart | 8f5f468 | 2013-08-07 22:13:39 +1200 | [diff] [blame] | 100 | } |