Support alternative ordering specifications for DocumentTree primitive
Change-Id: I89a99435bff44f8d37d6b529fbf735940e7d7210
diff --git a/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java b/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java
index 162da9f..6b2a54c 100644
--- a/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java
+++ b/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java
@@ -27,6 +27,7 @@
import org.onosproject.store.service.AsyncDistributedSet;
import org.onosproject.store.service.AsyncDocumentTree;
import org.onosproject.store.service.AsyncLeaderElector;
+import org.onosproject.store.service.Ordering;
import org.onosproject.store.service.Serializer;
import org.onosproject.store.service.WorkQueue;
@@ -139,7 +140,20 @@
* @param serializer serializer
* @return document tree
*/
- <V> AsyncDocumentTree<V> newAsyncDocumentTree(String name, Serializer serializer);
+ default <V> AsyncDocumentTree<V> newAsyncDocumentTree(String name, Serializer serializer) {
+ return newAsyncDocumentTree(name, serializer, Ordering.NATURAL);
+ }
+
+ /**
+ * Creates a new {@code AsyncDocumentTree}.
+ *
+ * @param <V> document tree node value type
+ * @param name tree name
+ * @param serializer serializer
+ * @param ordering tree node ordering
+ * @return document tree
+ */
+ <V> AsyncDocumentTree<V> newAsyncDocumentTree(String name, Serializer serializer, Ordering ordering);
/**
* Returns the names of all created {@code AsyncConsistentMap} instances.
diff --git a/core/api/src/main/java/org/onosproject/store/service/DocumentTreeBuilder.java b/core/api/src/main/java/org/onosproject/store/service/DocumentTreeBuilder.java
index e0e0063..14ecd5c 100644
--- a/core/api/src/main/java/org/onosproject/store/service/DocumentTreeBuilder.java
+++ b/core/api/src/main/java/org/onosproject/store/service/DocumentTreeBuilder.java
@@ -25,6 +25,7 @@
extends DistributedPrimitiveBuilder<DocumentTreeBuilder<V>, AsyncDocumentTree<V>> {
private boolean purgeOnUninstall = false;
+ private Ordering ordering = Ordering.NATURAL;
public DocumentTreeBuilder() {
super(DistributedPrimitive.Type.DOCUMENT_TREE);
@@ -50,6 +51,32 @@
}
/**
+ * Sets the ordering of the tree nodes.
+ * <p>
+ * When {@link AsyncDocumentTree#getChildren(DocumentPath)} is called, children will be returned according to
+ * the specified sort order.
+ *
+ * @param ordering ordering of the tree nodes
+ * @return this builder
+ */
+ public DocumentTreeBuilder<V> withOrdering(Ordering ordering) {
+ this.ordering = ordering;
+ return this;
+ }
+
+ /**
+ * Returns the ordering of tree nodes.
+ * <p>
+ * When {@link AsyncDocumentTree#getChildren(DocumentPath)} is called, children will be returned according to
+ * the specified sort order.
+ *
+ * @return the ordering of tree nodes
+ */
+ public Ordering ordering() {
+ return ordering;
+ }
+
+ /**
* Builds the distributed Document tree based on the configuration options supplied
* to this builder.
*
diff --git a/core/api/src/main/java/org/onosproject/store/service/Ordering.java b/core/api/src/main/java/org/onosproject/store/service/Ordering.java
new file mode 100644
index 0000000..64f41ec
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/Ordering.java
@@ -0,0 +1,32 @@
+/*
+ * Copyright 2017-present Open Networking Foundation
+ *
+ * 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.store.service;
+
+/**
+ * Describes the order of a primitive data structure.
+ */
+public enum Ordering {
+
+ /**
+ * Indicates that items should be ordered in their natural order.
+ */
+ NATURAL,
+
+ /**
+ * Indicates that items should be ordered in insertion order.
+ */
+ INSERTION,
+}
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DefaultDocumentTreeBuilder.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DefaultDocumentTreeBuilder.java
index 9ea5e83..9db48b7 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DefaultDocumentTreeBuilder.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DefaultDocumentTreeBuilder.java
@@ -47,6 +47,6 @@
@Deprecated
@Override
public AsyncDocumentTree<V> build() {
- return primitiveCreator.newAsyncDocumentTree(name(), serializer());
+ return primitiveCreator.newAsyncDocumentTree(name(), serializer(), ordering());
}
}
\ No newline at end of file
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/FederatedDistributedPrimitiveCreator.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/FederatedDistributedPrimitiveCreator.java
index 4786fb4..8f45628 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/FederatedDistributedPrimitiveCreator.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/FederatedDistributedPrimitiveCreator.java
@@ -34,6 +34,7 @@
import org.onosproject.store.service.AsyncDistributedSet;
import org.onosproject.store.service.AsyncDocumentTree;
import org.onosproject.store.service.AsyncLeaderElector;
+import org.onosproject.store.service.Ordering;
import org.onosproject.store.service.Serializer;
import org.onosproject.store.service.WorkQueue;
@@ -139,8 +140,8 @@
}
@Override
- public <V> AsyncDocumentTree<V> newAsyncDocumentTree(String name, Serializer serializer) {
- return getCreator(name).newAsyncDocumentTree(name, serializer);
+ public <V> AsyncDocumentTree<V> newAsyncDocumentTree(String name, Serializer serializer, Ordering ordering) {
+ return getCreator(name).newAsyncDocumentTree(name, serializer, ordering);
}
@Override
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartition.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartition.java
index b988282..842e047 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartition.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartition.java
@@ -43,6 +43,7 @@
import org.onosproject.store.primitives.resources.impl.AtomixLeaderElectorService;
import org.onosproject.store.primitives.resources.impl.AtomixWorkQueueService;
import org.onosproject.store.service.DistributedPrimitive;
+import org.onosproject.store.service.Ordering;
import org.onosproject.store.service.PartitionInfo;
import org.onosproject.store.service.Serializer;
@@ -68,7 +69,12 @@
.put(DistributedPrimitive.Type.COUNTER.name(), AtomixCounterService::new)
.put(DistributedPrimitive.Type.LEADER_ELECTOR.name(), AtomixLeaderElectorService::new)
.put(DistributedPrimitive.Type.WORK_QUEUE.name(), AtomixWorkQueueService::new)
- .put(DistributedPrimitive.Type.DOCUMENT_TREE.name(), AtomixDocumentTreeService::new)
+ .put(DistributedPrimitive.Type.DOCUMENT_TREE.name(),
+ () -> new AtomixDocumentTreeService(Ordering.NATURAL))
+ .put(String.format("%s-%s", DistributedPrimitive.Type.DOCUMENT_TREE.name(), Ordering.NATURAL),
+ () -> new AtomixDocumentTreeService(Ordering.NATURAL))
+ .put(String.format("%s-%s", DistributedPrimitive.Type.DOCUMENT_TREE.name(), Ordering.INSERTION),
+ () -> new AtomixDocumentTreeService(Ordering.INSERTION))
.build();
public StoragePartition(Partition partition,
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartitionClient.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartitionClient.java
index a742d08..8f1ffa3 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartitionClient.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartitionClient.java
@@ -50,6 +50,7 @@
import org.onosproject.store.service.AsyncDocumentTree;
import org.onosproject.store.service.AsyncLeaderElector;
import org.onosproject.store.service.DistributedPrimitive;
+import org.onosproject.store.service.Ordering;
import org.onosproject.store.service.PartitionClientInfo;
import org.onosproject.store.service.Serializer;
import org.onosproject.store.service.WorkQueue;
@@ -242,10 +243,10 @@
}
@Override
- public <V> AsyncDocumentTree<V> newAsyncDocumentTree(String name, Serializer serializer) {
+ public <V> AsyncDocumentTree<V> newAsyncDocumentTree(String name, Serializer serializer, Ordering ordering) {
AtomixDocumentTree atomixDocumentTree = new AtomixDocumentTree(client.newProxyBuilder()
.withName(name)
- .withServiceType(DistributedPrimitive.Type.DOCUMENT_TREE.name())
+ .withServiceType(String.format("%s-%s", DistributedPrimitive.Type.DOCUMENT_TREE.name(), ordering))
.withReadConsistency(ReadConsistency.SEQUENTIAL)
.withCommunicationStrategy(CommunicationStrategy.ANY)
.withTimeout(Duration.ofSeconds(30))
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeOperations.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeOperations.java
index 726e1f1..718223e 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeOperations.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeOperations.java
@@ -16,6 +16,7 @@
package org.onosproject.store.primitives.resources.impl;
+import java.util.LinkedHashMap;
import java.util.Optional;
import com.google.common.base.MoreObjects;
@@ -59,6 +60,7 @@
public static final KryoNamespace NAMESPACE = KryoNamespace.newBuilder()
.register(KryoNamespaces.BASIC)
.nextId(KryoNamespaces.BEGIN_USER_CUSTOM_ID)
+ .register(LinkedHashMap.class)
.register(Listen.class)
.register(Unlisten.class)
.register(Get.class)
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeService.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeService.java
index 9ee352c..9e87325 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeService.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeService.java
@@ -55,6 +55,7 @@
import org.onosproject.store.service.DocumentTreeEvent.Type;
import org.onosproject.store.service.IllegalDocumentModificationException;
import org.onosproject.store.service.NoSuchDocumentPathException;
+import org.onosproject.store.service.Ordering;
import org.onosproject.store.service.Serializer;
import org.onosproject.store.service.Versioned;
@@ -91,6 +92,7 @@
.register(DocumentPath.class)
.register(new HashMap().keySet().getClass())
.register(TreeMap.class)
+ .register(Ordering.class)
.register(SessionListenCommits.class)
.register(new com.esotericsoftware.kryo.Serializer<DefaultDocumentTree>() {
@Override
@@ -110,7 +112,11 @@
private Map<Long, SessionListenCommits> listeners = new HashMap<>();
private AtomicLong versionCounter = new AtomicLong(0);
- private DocumentTree<byte[]> docTree = new DefaultDocumentTree<>(versionCounter::incrementAndGet);
+ private DocumentTree<byte[]> docTree;
+
+ public AtomixDocumentTreeService(Ordering ordering) {
+ this.docTree = new DefaultDocumentTree<>(versionCounter::incrementAndGet, ordering);
+ }
@Override
public void snapshot(SnapshotWriter writer) {
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/DefaultDocumentTree.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/DefaultDocumentTree.java
index 3ead9e6..31bd20c 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/DefaultDocumentTree.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/DefaultDocumentTree.java
@@ -27,6 +27,7 @@
import org.onosproject.store.service.DocumentTreeNode;
import org.onosproject.store.service.IllegalDocumentModificationException;
import org.onosproject.store.service.NoSuchDocumentPathException;
+import org.onosproject.store.service.Ordering;
import org.onosproject.store.service.Versioned;
import com.google.common.base.Preconditions;
@@ -47,11 +48,11 @@
public DefaultDocumentTree() {
AtomicLong versionCounter = new AtomicLong(0);
versionSupplier = versionCounter::incrementAndGet;
- root = new DefaultDocumentTreeNode<V>(ROOT_PATH, null, versionSupplier.get(), null);
+ root = new DefaultDocumentTreeNode<V>(ROOT_PATH, null, versionSupplier.get(), Ordering.NATURAL, null);
}
- public DefaultDocumentTree(Supplier<Long> versionSupplier) {
- root = new DefaultDocumentTreeNode<V>(ROOT_PATH, null, versionSupplier.get(), null);
+ public DefaultDocumentTree(Supplier<Long> versionSupplier, Ordering ordering) {
+ root = new DefaultDocumentTreeNode<V>(ROOT_PATH, null, versionSupplier.get(), ordering, null);
this.versionSupplier = versionSupplier;
}
@@ -74,7 +75,7 @@
public Map<String, Versioned<V>> getChildren(DocumentPath path) {
DocumentTreeNode<V> node = getNode(path);
if (node != null) {
- Map<String, Versioned<V>> childrenValues = Maps.newHashMap();
+ Map<String, Versioned<V>> childrenValues = Maps.newLinkedHashMap();
node.children().forEachRemaining(n -> childrenValues.put(simpleName(n.path()), n.value()));
return childrenValues;
}
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/DefaultDocumentTreeNode.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/DefaultDocumentTreeNode.java
index 2482f13..5623185 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/DefaultDocumentTreeNode.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/DefaultDocumentTreeNode.java
@@ -19,11 +19,12 @@
import static com.google.common.base.Preconditions.checkNotNull;
import java.util.Iterator;
+import java.util.Map;
import java.util.Objects;
-import java.util.TreeMap;
import org.onosproject.store.service.DocumentPath;
import org.onosproject.store.service.DocumentTreeNode;
+import org.onosproject.store.service.Ordering;
import org.onosproject.store.service.Versioned;
import com.google.common.base.MoreObjects;
@@ -37,16 +38,29 @@
public class DefaultDocumentTreeNode<V> implements DocumentTreeNode<V> {
private final DocumentPath key;
private Versioned<V> value;
- private final TreeMap<String, DocumentTreeNode<V>> children = Maps.newTreeMap();
+ private final Map<String, DocumentTreeNode<V>> children;
+ private final Ordering ordering;
private final DocumentTreeNode<V> parent;
public DefaultDocumentTreeNode(DocumentPath key,
V value,
long version,
+ Ordering ordering,
DocumentTreeNode<V> parent) {
this.key = checkNotNull(key);
this.value = new Versioned<>(value, version);
+ this.ordering = ordering;
this.parent = parent;
+
+ switch (ordering) {
+ case INSERTION:
+ children = Maps.newLinkedHashMap();
+ break;
+ case NATURAL:
+ default:
+ children = Maps.newTreeMap();
+ break;
+ }
}
@Override
@@ -87,7 +101,8 @@
if (child != null) {
return child.value();
}
- children.put(name, new DefaultDocumentTreeNode<>(new DocumentPath(name, path()), newValue, newVersion, this));
+ children.put(name, new DefaultDocumentTreeNode<>(
+ new DocumentPath(name, path()), newValue, newVersion, ordering, this));
return null;
}
diff --git a/core/store/primitives/src/test/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeServiceTest.java b/core/store/primitives/src/test/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeServiceTest.java
index c55888a..555b82b 100644
--- a/core/store/primitives/src/test/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeServiceTest.java
+++ b/core/store/primitives/src/test/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeServiceTest.java
@@ -30,6 +30,7 @@
import org.junit.Test;
import org.onlab.util.Match;
import org.onosproject.store.service.DocumentPath;
+import org.onosproject.store.service.Ordering;
import org.onosproject.store.service.Versioned;
import static org.easymock.EasyMock.mock;
@@ -42,15 +43,25 @@
* Document tree service test.
*/
public class AtomixDocumentTreeServiceTest {
+
@Test
- public void testSnapshot() throws Exception {
+ public void testNaturalOrderedSnapshot() throws Exception {
+ testSnapshot(Ordering.NATURAL);
+ }
+
+ @Test
+ public void testInsertionOrderedSnapshot() throws Exception {
+ testSnapshot(Ordering.INSERTION);
+ }
+
+ private void testSnapshot(Ordering ordering) throws Exception {
SnapshotStore store = new SnapshotStore(RaftStorage.newBuilder()
.withPrefix("test")
.withStorageLevel(StorageLevel.MEMORY)
.build());
Snapshot snapshot = store.newSnapshot(ServiceId.from(1), 2, new WallClockTimestamp());
- AtomixDocumentTreeService service = new AtomixDocumentTreeService();
+ AtomixDocumentTreeService service = new AtomixDocumentTreeService(ordering);
service.update(new DefaultCommit<>(
2,
UPDATE,
@@ -68,7 +79,7 @@
snapshot.complete();
- service = new AtomixDocumentTreeService();
+ service = new AtomixDocumentTreeService(ordering);
try (SnapshotReader reader = snapshot.openReader()) {
service.install(reader);
}
diff --git a/core/store/primitives/src/test/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeTest.java b/core/store/primitives/src/test/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeTest.java
index fd0501c..5117934 100644
--- a/core/store/primitives/src/test/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeTest.java
+++ b/core/store/primitives/src/test/java/org/onosproject/store/primitives/resources/impl/AtomixDocumentTreeTest.java
@@ -16,6 +16,7 @@
package org.onosproject.store.primitives.resources.impl;
+import java.util.Iterator;
import java.util.Map;
import java.util.UUID;
import java.util.concurrent.ArrayBlockingQueue;
@@ -30,6 +31,7 @@
import org.onosproject.store.service.DocumentTreeListener;
import org.onosproject.store.service.IllegalDocumentModificationException;
import org.onosproject.store.service.NoSuchDocumentPathException;
+import org.onosproject.store.service.Ordering;
import org.onosproject.store.service.Versioned;
import static org.junit.Assert.assertArrayEquals;
@@ -43,10 +45,11 @@
* Unit tests for {@link AtomixDocumentTree}.
*/
public class AtomixDocumentTreeTest extends AtomixTestBase<AtomixDocumentTree> {
+ private Ordering ordering = Ordering.NATURAL;
@Override
protected RaftService createService() {
- return new AtomixDocumentTreeService();
+ return new AtomixDocumentTreeService(ordering);
}
@Override
@@ -54,6 +57,16 @@
return new AtomixDocumentTree(proxy);
}
+ @Override
+ protected AtomixDocumentTree newPrimitive(String name) {
+ return newPrimitive(name, Ordering.NATURAL);
+ }
+
+ protected AtomixDocumentTree newPrimitive(String name, Ordering ordering) {
+ this.ordering = ordering;
+ return super.newPrimitive(name);
+ }
+
/**
* Tests queries (get and getChildren).
*/
@@ -106,6 +119,34 @@
}
/**
+ * Tests child node order.
+ */
+ @Test
+ public void testOrder() throws Throwable {
+ AtomixDocumentTree naturalTree = newPrimitive(UUID.randomUUID().toString(), Ordering.NATURAL);
+ naturalTree.create(path("root.c"), "foo".getBytes());
+ naturalTree.create(path("root.b"), "bar".getBytes());
+ naturalTree.create(path("root.a"), "baz".getBytes());
+
+ Iterator<Map.Entry<String, Versioned<byte[]>>> naturalIterator = naturalTree.getChildren(path("root"))
+ .join().entrySet().iterator();
+ assertEquals("a", naturalIterator.next().getKey());
+ assertEquals("b", naturalIterator.next().getKey());
+ assertEquals("c", naturalIterator.next().getKey());
+
+ AtomixDocumentTree insertionTree = newPrimitive(UUID.randomUUID().toString(), Ordering.INSERTION);
+ insertionTree.create(path("root.c"), "foo".getBytes());
+ insertionTree.create(path("root.b"), "bar".getBytes());
+ insertionTree.create(path("root.a"), "baz".getBytes());
+
+ Iterator<Map.Entry<String, Versioned<byte[]>>> insertionIterator = insertionTree.getChildren(path("root"))
+ .join().entrySet().iterator();
+ assertEquals("c", insertionIterator.next().getKey());
+ assertEquals("b", insertionIterator.next().getKey());
+ assertEquals("a", insertionIterator.next().getKey());
+ }
+
+ /**
* Tests set.
*/
@Test