[ONOS-6537] Add interface for IP RadixTree data structure
Change-Id: Ibd0427f07dc4a9b8be521781192aa6f3980700a3
diff --git a/protocols/lisp/ctl/pom.xml b/protocols/lisp/ctl/pom.xml
index 82df5d1..a838150 100644
--- a/protocols/lisp/ctl/pom.xml
+++ b/protocols/lisp/ctl/pom.xml
@@ -68,6 +68,11 @@
<classifier>tests</classifier>
<scope>test</scope>
</dependency>
+ <dependency>
+ <groupId>com.googlecode.concurrent-trees</groupId>
+ <artifactId>concurrent-trees</artifactId>
+ <version>2.6.0</version>
+ </dependency>
</dependencies>
diff --git a/protocols/lisp/ctl/src/main/java/org/onosproject/lisp/ctl/impl/tree/IpRadixTree.java b/protocols/lisp/ctl/src/main/java/org/onosproject/lisp/ctl/impl/tree/IpRadixTree.java
new file mode 100644
index 0000000..39cea03
--- /dev/null
+++ b/protocols/lisp/ctl/src/main/java/org/onosproject/lisp/ctl/impl/tree/IpRadixTree.java
@@ -0,0 +1,140 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.onosproject.lisp.ctl.impl.tree;
+
+import org.onlab.packet.IpAddress;
+import org.onlab.packet.IpAddress.Version;
+import org.onlab.packet.IpPrefix;
+
+import java.util.List;
+
+/**
+ * A radix tree that stores IP address as a key.
+ */
+public interface IpRadixTree<V> {
+
+ /**
+ * Associates the specified value with the specified IP address in this
+ * radix tree. If the radix tree previously contained a mapping for the
+ * address, the old value is replaced by the specified value.
+ *
+ * @param prefix prefix with which the specified value is to be associated
+ * @param value value to be associated with the specified IP address
+ * @return The previous value associated with the key,
+ * if there was one, otherwise null
+ */
+ V put(IpPrefix prefix, V value);
+
+ /**
+ * If a value is not already associated with the given address in the radix
+ * tree, associates the given value with the address; otherwise if an
+ * existing value is already associated, returns the existing value and
+ * does not overwrite it.
+ *
+ * This operation is performed atomically.
+ *
+ * @param prefix prefix with which the specified value is to be associated
+ * @param value value to be associated with the specified IP address
+ * @return The existing value associated with the address, if there was one;
+ * otherwise null in which case the new value was successfully associated
+ */
+ V putIfAbsent(IpPrefix prefix, V value);
+
+ /**
+ * Removes the mapping for a address from this radix tree if it is present
+ * (optional operation). More formally, if this radix tree contains a
+ * mapping from address <tt>address</tt> to value <tt>v</tt> such that
+ * <code>(address==null ? address==null : address.equals(k))</code>,
+ * that mapping is removed. (The radix tree can contain at most one
+ * such mapping.)
+ *
+ * @param prefix prefix whose mapping is to be removed from the radix tree
+ * @return True if a value was removed (and therefore was associated with
+ * the address), false if no value was associated/removed
+ */
+ boolean remove(IpPrefix prefix);
+
+ /**
+ * Returns the value associated with the given address (exact match),
+ * or returns null if no such value is associated with the address.
+ *
+ * @param prefix The prefix with which a sought value might be associated
+ * @return A value associated with the given address (exact match), or null
+ * if no value was associated with the address
+ */
+ V getValueForExactAddress(IpPrefix prefix);
+
+ /**
+ * Returns the value associated with the closest parent address,
+ * or returns null if no such value is associated with the address.
+ * This method simply tries the exact match at the first time, if there is
+ * no associated value, it tries the exact match with the parent IP prefix.
+ *
+ * @param prefix The prefix with which a sought value might be associated
+ * @return A value associated with the closest parent address, or
+ * null if no value was associated with the address
+ */
+ V getValueForClosestParentAddress(IpPrefix prefix);
+
+ /**
+ * Returns a lazy collection which returns the set of addresses in the radix
+ * tree which start with the given prefix.
+ *
+ * This is <i>inclusive</i> - if the given prefix is an exact match for a
+ * address in the tree, that address is also returned.
+ *
+ * @param prefix A prefix of sought addresses in the tree
+ * @return A set of addresses in the tree which start with the given prefix
+ */
+ List<IpAddress> getAddressesStartingWith(IpPrefix prefix);
+
+ /**
+ * Returns a lazy collection which returns the set of values associated with
+ * addresses in the radix tree which start with the given prefix.
+ *
+ * This is <i>inclusive</i> - if the given prefix is an exact match for a
+ * address in the tree, the value associated with that address is
+ * also returned.
+ *
+ * Note that although the same value might originally have been associated
+ * with multiple addresses, the set returned does not contain duplicates
+ * (as determined by the value objects' implementation of
+ * {@link Object#equals(Object)}).
+ *
+ * @param prefix A prefix of addresses in the tree for which associated
+ * values are sought
+ * @return The set of values associated with addresses in the tree which
+ * start with the given prefix
+ */
+ List<V> getValuesForAddressesStartingWith(IpPrefix prefix);
+
+ /**
+ * Counts the number of addresses/values stored in the radix tree.
+ *
+ * In the current implementation, <b>this is an expensive operation</b>,
+ * having O(n) time complexity.
+ *
+ * @param version The version of IP address
+ * @return The number of addresses/values stored in the radix tree
+ */
+ int size(Version version);
+
+ /**
+ * Removes all of the mappings from this radix tree (optional operation).
+ * The radix tree will be empty after this call returns.
+ */
+ void clear();
+}
diff --git a/protocols/lisp/ctl/src/main/java/org/onosproject/lisp/ctl/impl/tree/package-info.java b/protocols/lisp/ctl/src/main/java/org/onosproject/lisp/ctl/impl/tree/package-info.java
new file mode 100644
index 0000000..9973d92
--- /dev/null
+++ b/protocols/lisp/ctl/src/main/java/org/onosproject/lisp/ctl/impl/tree/package-info.java
@@ -0,0 +1,19 @@
+/*
+ * Copyright 2017-present Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+/**
+ * A package that contains IpRadixTree interface and implementation classes.
+ */
+package org.onosproject.lisp.ctl.impl.tree;
\ No newline at end of file