Add repository implementations
diff --git a/src/main/java/com/intel/jndn/utils/repository/DataNotFoundException.java b/src/main/java/com/intel/jndn/utils/repository/DataNotFoundException.java
new file mode 100644
index 0000000..732cc9c
--- /dev/null
+++ b/src/main/java/com/intel/jndn/utils/repository/DataNotFoundException.java
@@ -0,0 +1,23 @@
+/*
+ * jndn-utils
+ * Copyright (c) 2015, Intel Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU Lesser General Public License,
+ * version 3, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
+ * more details.
+ */
+package com.intel.jndn.utils.repository;
+
+/**
+ * Thrown when a {@link Repository} cannot retrieve a stored packet.
+ *
+ * @author Andrew Brown <andrew.brown@intel.com>
+ */
+public class DataNotFoundException extends Exception {
+
+}
diff --git a/src/main/java/com/intel/jndn/utils/repository/ForLoopRepository.java b/src/main/java/com/intel/jndn/utils/repository/ForLoopRepository.java
new file mode 100644
index 0000000..cb43655
--- /dev/null
+++ b/src/main/java/com/intel/jndn/utils/repository/ForLoopRepository.java
@@ -0,0 +1,110 @@
+/*
+ * jndn-utils
+ * Copyright (c) 2015, Intel Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU Lesser General Public License,
+ * version 3, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
+ * more details.
+ */
+package com.intel.jndn.utils.repository;
+
+import java.util.ArrayList;
+import java.util.List;
+import net.named_data.jndn.Data;
+import net.named_data.jndn.Interest;
+import net.named_data.jndn.Name;
+
+/**
+ * Store {@link Data} packets in a linked list and iterate over the list to find
+ * the best match; this is a subset of the functionality provided in
+ * {@link net.named_data.jndn.util.MemoryContentCache} and borrows the matching
+ * logic from there. Code for removing stale packets is not yet implemented.
+ *
+ * @author Andrew Brown <andrew.brown@intel.com>
+ */
+public class ForLoopRepository implements Repository {
+
+ private List<Data> storage = new ArrayList<>();
+
+ /**
+ * Helper data structure
+ */
+ private class Record {
+
+ public Name name;
+ public Data data;
+
+ public Record(Name name, Data data) {
+ this.name = name;
+ this.data = data;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public void put(Data data) {
+ storage.add(data);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public Data get(Interest interest) throws DataNotFoundException {
+ Name.Component selectedComponent = null;
+ Data selectedData = null;
+ for (Data content : storage) {
+ if (interest.matchesName(content.getName())) {
+ if (interest.getChildSelector() < 0) {
+ // No child selector, so send the first match that we have found.
+ return content;
+ } else {
+ // Update selectedEncoding based on the child selector.
+ Name.Component component;
+ if (content.getName().size() > interest.getName().size()) {
+ component = content.getName().get(interest.getName().size());
+ } else {
+ component = new Name.Component();
+ }
+
+ boolean gotBetterMatch = false;
+ if (selectedData == null) {
+ // Save the first match.
+ gotBetterMatch = true;
+ } else {
+ if (interest.getChildSelector() == 0) {
+ // Leftmost child.
+ if (component.compare(selectedComponent) < 0) {
+ gotBetterMatch = true;
+ }
+ } else {
+ // Rightmost child.
+ if (component.compare(selectedComponent) > 0) {
+ gotBetterMatch = true;
+ }
+ }
+ }
+
+ if (gotBetterMatch) {
+ selectedComponent = component;
+ selectedData = content;
+ }
+ }
+ }
+ }
+
+ if (selectedData != null) {
+ // We found the leftmost or rightmost child.
+ return selectedData;
+ } else {
+ throw new DataNotFoundException();
+ }
+ }
+}
diff --git a/src/main/java/com/intel/jndn/utils/repository/NavigableTreeRepository.java b/src/main/java/com/intel/jndn/utils/repository/NavigableTreeRepository.java
new file mode 100644
index 0000000..ec47190
--- /dev/null
+++ b/src/main/java/com/intel/jndn/utils/repository/NavigableTreeRepository.java
@@ -0,0 +1,146 @@
+/*
+ * jndn-utils
+ * Copyright (c) 2015, Intel Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU Lesser General Public License,
+ * version 3, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
+ * more details.
+ */
+package com.intel.jndn.utils.repository;
+
+import java.util.NavigableMap;
+import java.util.TreeMap;
+import net.named_data.jndn.Data;
+import net.named_data.jndn.Interest;
+import net.named_data.jndn.Name;
+
+/**
+ * Store {@link Data} packets in a {@link TreeMap}; this is an initial concept
+ * class and should not be used in production. In tests, see
+ * RepositoryTest.java, this class is faster on retrieval but not enough to make
+ * up for its slow put().
+ *
+ * @author Andrew Brown <andrew.brown@intel.com>
+ */
+public class NavigableTreeRepository implements Repository {
+
+ private NavigableMap<Name, PossibleData> storage = new TreeMap<>();
+
+ /**
+ * Helper data structure
+ */
+ private class PossibleData {
+
+ public PossibleData() {
+ // no data provided
+ }
+
+ public PossibleData(Data data) {
+ this.data = data;
+ }
+ public Data data;
+
+ public boolean hasData() {
+ return data != null;
+ }
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public void put(Data data) {
+ storage.put(data.getName(), new PossibleData(data));
+
+ Name name = data.getName();
+ do {
+ name = name.getPrefix(-1);
+ if (storage.get(name) == null) {
+ storage.put(name, new PossibleData());
+ }
+ } while (name.size() > 0);
+ }
+
+ /**
+ * {@inheritDoc}
+ */
+ @Override
+ public Data get(Interest interest) throws DataNotFoundException {
+ Data data;
+ if (interest.getChildSelector() == Interest.CHILD_SELECTOR_LEFT) {
+ data = getLowest(interest);
+ } else if (interest.getChildSelector() == Interest.CHILD_SELECTOR_RIGHT) {
+ data = getHighest(interest);
+ } else {
+ data = getFirstMatching(interest);
+ }
+ checkForNull(data);
+ return data;
+ }
+
+ /**
+ * @param interest the {@link Interest} to search with
+ * @return the lowest matching {@link Data} packet
+ */
+ private Data getLowest(Interest interest) {
+ PossibleData found = storage.get(interest.getName());
+
+ Name name = interest.getName();
+ while (found != null && interest.matchesName(name)) {
+ name = storage.lowerKey(name);
+ found = (name != null) ? storage.get(name) : null;
+ }
+
+ return found == null ? null : found.data;
+ }
+
+ /**
+ * @param interest the {@link Interest} to search with
+ * @return the highest matching {@link Data} packet
+ */
+ private Data getHighest(Interest interest) {
+ PossibleData found = storage.get(interest.getName());
+
+ if (found != null) {
+ Name name = interest.getName();
+ while (name != null && interest.matchesName(name)) {
+ found = storage.get(name);
+ name = storage.higherKey(name);
+ }
+ }
+
+ return found == null ? null : found.data;
+ }
+
+ /**
+ * @param interest the {@link Interest} to search with
+ * @return the first matching {@link Data} packet
+ */
+ private Data getFirstMatching(Interest interest) {
+ PossibleData found = storage.get(interest.getName());
+
+ Name name = interest.getName();
+ while (found != null && !found.hasData() && interest.matchesName(name)) {
+ name = storage.higherKey(name);
+ found = (name != null) ? storage.get(name) : null;
+ }
+
+ return found == null ? null : found.data;
+ }
+
+ /**
+ * @param data the {@link Data} packet to check
+ * @throws DataNotFoundException if data is null
+ */
+ private void checkForNull(Data data) throws DataNotFoundException {
+ if (data == null) {
+ throw new DataNotFoundException();
+ }
+ }
+
+}
diff --git a/src/main/java/com/intel/jndn/utils/repository/Repository.java b/src/main/java/com/intel/jndn/utils/repository/Repository.java
new file mode 100644
index 0000000..9444e24
--- /dev/null
+++ b/src/main/java/com/intel/jndn/utils/repository/Repository.java
@@ -0,0 +1,43 @@
+/*
+ * jndn-utils
+ * Copyright (c) 2015, Intel Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU Lesser General Public License,
+ * version 3, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
+ * more details.
+ */
+package com.intel.jndn.utils.repository;
+
+import com.intel.jndn.utils.repository.DataNotFoundException;
+import net.named_data.jndn.Data;
+import net.named_data.jndn.Interest;
+
+/**
+ * Define API for storing and retrieving NDN packets
+ *
+ * @author Andrew Brown <andrew.brown@intel.com>
+ */
+public interface Repository {
+
+ /**
+ * Put a {@link Data} packet in the repository.
+ *
+ * @param data a {@link Data} packet
+ */
+ public void put(Data data);
+
+ /**
+ * Retrieve a {@link Data} packet in the repository; this method should
+ * respect child selectors, exclude selectors, etc.
+ *
+ * @param interest the {@link Interest}
+ * @return a {@link Data} packet
+ * @throws DataNotFoundException if the packet is not found
+ */
+ public Data get(Interest interest) throws DataNotFoundException;
+}
diff --git a/src/test/java/com/intel/jndn/utils/repository/ForLoopRepositoryTest.java b/src/test/java/com/intel/jndn/utils/repository/ForLoopRepositoryTest.java
new file mode 100644
index 0000000..3071e95
--- /dev/null
+++ b/src/test/java/com/intel/jndn/utils/repository/ForLoopRepositoryTest.java
@@ -0,0 +1,51 @@
+/*
+ * jndn-utils
+ * Copyright (c) 2015, Intel Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU Lesser General Public License,
+ * version 3, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
+ * more details.
+ */
+package com.intel.jndn.utils.repository;
+
+import com.intel.jndn.utils.repository.Repository;
+import com.intel.jndn.utils.repository.DataNotFoundException;
+import com.intel.jndn.utils.repository.ForLoopRepository;
+import net.named_data.jndn.Data;
+import net.named_data.jndn.Interest;
+import net.named_data.jndn.Name;
+import org.junit.Test;
+import static org.junit.Assert.*;
+
+/**
+ * Test {@link ForLoopRepository}.
+ *
+ * @author Andrew Brown <andrew.brown@intel.com>
+ */
+public class ForLoopRepositoryTest {
+
+ @Test
+ public void testGetAndPut() throws DataNotFoundException {
+ Repository repo = new ForLoopRepository();
+ repo.put(RepositoryTest.buildData("/a/b/c"));
+ Data data = repo.get(RepositoryTest.buildInterest("/a/b/c"));
+ assertEquals("...", data.getContent().toString());
+ }
+
+ @Test
+ public void testForLoopChildSelectors() throws DataNotFoundException {
+ Repository repo = new ForLoopRepository();
+ RepositoryTest.assertChildSelectorsRetrieve(repo);
+ }
+
+ @Test(expected = DataNotFoundException.class)
+ public void testFailure() throws DataNotFoundException {
+ Repository repo = new ForLoopRepository();
+ repo.get(new Interest(new Name("/unknown/data")));
+ }
+}
diff --git a/src/test/java/com/intel/jndn/utils/repository/NavigableTreeRepositoryTest.java b/src/test/java/com/intel/jndn/utils/repository/NavigableTreeRepositoryTest.java
new file mode 100644
index 0000000..e3add4d
--- /dev/null
+++ b/src/test/java/com/intel/jndn/utils/repository/NavigableTreeRepositoryTest.java
@@ -0,0 +1,51 @@
+/*
+ * jndn-utils
+ * Copyright (c) 2015, Intel Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU Lesser General Public License,
+ * version 3, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
+ * more details.
+ */
+package com.intel.jndn.utils.repository;
+
+import com.intel.jndn.utils.repository.Repository;
+import com.intel.jndn.utils.repository.DataNotFoundException;
+import com.intel.jndn.utils.repository.NavigableTreeRepository;
+import net.named_data.jndn.Data;
+import net.named_data.jndn.Interest;
+import net.named_data.jndn.Name;
+import static org.junit.Assert.*;
+import org.junit.Test;
+
+/**
+ * Test {@link NavigableTreeRepository}.
+ *
+ * @author Andrew Brown <andrew.brown@intel.com>
+ */
+public class NavigableTreeRepositoryTest {
+
+ @Test
+ public void testNavigableTreeFunctionality() throws DataNotFoundException {
+ Repository repo = new NavigableTreeRepository();
+ repo.put(RepositoryTest.buildData("/a/b/c"));
+ Data data = repo.get(RepositoryTest.buildInterest("/a/b/c"));
+ assertEquals("...", data.getContent().toString());
+ }
+
+ @Test
+ public void testNavigableTreeChildSelectors() throws DataNotFoundException {
+ Repository repo = new NavigableTreeRepository();
+ RepositoryTest.assertChildSelectorsRetrieve(repo);
+ }
+
+ @Test(expected = DataNotFoundException.class)
+ public void testFailure() throws DataNotFoundException{
+ Repository repo = new NavigableTreeRepository();
+ repo.get(new Interest(new Name("/unknown/data")));
+ }
+}
diff --git a/src/test/java/com/intel/jndn/utils/repository/RepositoryTest.java b/src/test/java/com/intel/jndn/utils/repository/RepositoryTest.java
new file mode 100644
index 0000000..a077edd
--- /dev/null
+++ b/src/test/java/com/intel/jndn/utils/repository/RepositoryTest.java
@@ -0,0 +1,203 @@
+/*
+ * jndn-utils
+ * Copyright (c) 2015, Intel Corporation.
+ *
+ * This program is free software; you can redistribute it and/or modify it
+ * under the terms and conditions of the GNU Lesser General Public License,
+ * version 3, as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
+ * more details.
+ */
+package com.intel.jndn.utils.repository;
+
+import com.intel.jndn.utils.repository.Repository;
+import com.intel.jndn.utils.repository.DataNotFoundException;
+import com.intel.jndn.utils.repository.NavigableTreeRepository;
+import com.intel.jndn.utils.repository.ForLoopRepository;
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.logging.Logger;
+import net.named_data.jndn.Data;
+import net.named_data.jndn.Interest;
+import net.named_data.jndn.Name;
+import net.named_data.jndn.util.Blob;
+import static org.junit.Assert.*;
+import org.junit.Test;
+
+/**
+ * Test NDN repositories, including performance
+ *
+ * @author Andrew Brown <andrew.brown@intel.com>
+ */
+public class RepositoryTest {
+
+ private static final Logger logger = Logger.getLogger(RepositoryTest.class.getName());
+
+ @Test
+ public void testGenerator() {
+ List<Name> names = buildNames(100);
+ assertEquals(100, names.size());
+ assertNotSame(names.get(0), names.get(1));
+ assertNotSame(names.get(0), names.get(26));
+ }
+
+ /**
+ * Some conclusions: the tree is far, far slower to add but far, far faster on
+ * retrieval.
+ *
+ * @throws DataNotFoundException
+ */
+ @Test
+ public void testPerformance() throws DataNotFoundException {
+ double seconds = 1000000000.0;
+ List<Name> names = buildNames(1000);
+ List<Data> datas = buildDatas(names);
+ List<Interest> interests = buildInterests(names);
+
+ Repository repo1 = new ForLoopRepository();
+ long time1 = timeAddDatas(repo1, datas);
+ logger.info("Put in for-loop repo (sec): " + time1 / seconds);
+
+ Repository repo2 = new NavigableTreeRepository();
+ long time2 = timeAddDatas(repo2, datas);
+ logger.info("Put in tree repo (sec): " + time2 / seconds);
+
+ long time3 = timeFindDatas(repo1, interests);
+ logger.info("Get from for-loop repo (sec): " + time3 / seconds);
+
+ long time4 = timeFindDatas(repo2, interests);
+ logger.info("Get from tree repo (sec): " + time4 / seconds);
+
+ long time5 = timeFindChildSelectedDatas(repo1, interests);
+ logger.info("Get child-selected from for-loop repo (sec): " + time5 / seconds);
+
+ long time6 = timeFindChildSelectedDatas(repo2, interests);
+ logger.info("Get child-selected from tree repo (sec): " + time6 / seconds);
+ }
+
+ public static void assertChildSelectorsRetrieve(Repository repo) throws DataNotFoundException {
+ repo.put(buildData("/a/b/c"));
+ repo.put(buildData("/a/b/c/e"));
+ repo.put(buildData("/a/b/d"));
+
+ Interest interest = buildInterest("/a/b");
+ interest.setChildSelector(Interest.CHILD_SELECTOR_RIGHT);
+ Data data = repo.get(interest);
+ assertEquals("/a/b/d", data.getName().toUri());
+
+ Interest interest2 = buildInterest("/a/b/c");
+ interest2.setChildSelector(Interest.CHILD_SELECTOR_RIGHT);
+ Data data2 = repo.get(interest2);
+ assertEquals("/a/b/c/e", data2.getName().toUri());
+ }
+
+ public static List<Name> buildNames(int size) {
+ List<Name> names = new ArrayList<>();
+ for (Name name : new NameGenerator(size)) {
+ names.add(name);
+ }
+ return names;
+ }
+
+ public static List<Data> buildDatas(List<Name> names) {
+ List<Data> datas = new ArrayList<>();
+ for (Name name : names) {
+ datas.add(buildData(name.toUri()));
+ }
+ return datas;
+ }
+
+ public static List<Interest> buildInterests(List<Name> names) {
+ List<Interest> interests = new ArrayList<>();
+ for (Name name : names) {
+ interests.add(buildInterest(name.toUri()));
+ }
+ return interests;
+ }
+
+ public static long timeAddDatas(Repository repo, List<Data> datas) {
+ long start = System.nanoTime();
+ for (Data data : datas) {
+ repo.put(data);
+ }
+ return System.nanoTime() - start;
+ }
+
+ public static long timeFindDatas(Repository repo, List<Interest> interests) throws DataNotFoundException {
+ long start = System.nanoTime();
+ for (Interest interest : interests) {
+ Data data = repo.get(interest);
+ assertNotNull(data);
+ }
+ return System.nanoTime() - start;
+ }
+
+ public static long timeFindChildSelectedDatas(Repository repo, List<Interest> interests) throws DataNotFoundException {
+ long start = System.nanoTime();
+ for (Interest interest : interests) {
+ interest.setChildSelector(Interest.CHILD_SELECTOR_RIGHT);
+ Data data = repo.get(interest);
+ assertNotNull(data);
+ }
+ return System.nanoTime() - start;
+ }
+
+ public static Data buildData(String name) {
+ Data data = new Data(new Name(name));
+ data.setContent(new Blob("..."));
+ data.getMetaInfo().setFreshnessPeriod(2000);
+ return data;
+ }
+
+ public static Interest buildInterest(String name) {
+ Interest interest = new Interest(new Name(name));
+ interest.setInterestLifetimeMilliseconds(2000);
+ interest.getMustBeFresh();
+ return interest;
+ }
+
+ public static class NameGenerator implements Iterator<Name>, Iterable<Name> {
+
+ private int size;
+ private int count = 0;
+ private Name last = new Name();
+
+ public NameGenerator(int size) {
+ this.size = size;
+ }
+
+ @Override
+ public boolean hasNext() {
+ return count < size;
+ }
+
+ @Override
+ public Name next() {
+ int current = count % 26;
+ String letter = Character.toString((char) (current + 65));
+ if (current == 0) {
+ last.append(letter);
+ } else {
+ last = last.getPrefix(-1).append(letter);
+ }
+ count++;
+ return new Name(last);
+ }
+
+ @Override
+ public void remove() {
+ throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
+ }
+
+ @Override
+ public Iterator<Name> iterator() {
+ return this;
+ }
+
+ }
+
+}