Upgrade Repository with cleanup()
diff --git a/src/main/java/com/intel/jndn/utils/repository/ForLoopRepository.java b/src/main/java/com/intel/jndn/utils/repository/ForLoopRepository.java
index cb43655..1563c24 100644
--- a/src/main/java/com/intel/jndn/utils/repository/ForLoopRepository.java
+++ b/src/main/java/com/intel/jndn/utils/repository/ForLoopRepository.java
@@ -29,28 +29,14 @@
*/
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;
- }
- }
+ private List<Record> storage = new ArrayList<>();
/**
* {@inheritDoc}
*/
@Override
public void put(Data data) {
- storage.add(data);
+ storage.add(new Record(data));
}
/**
@@ -60,26 +46,19 @@
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;
+ for (Record record : storage) {
+ if (interest.matchesName(record.data.getName())) {
+ if (hasNoChildSelector(interest) && hasAcceptableFreshness(interest, record)) {
+ selectedData = record.data;
} 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();
- }
+ Name.Component component = getNextComponentAfterLastInterestComponent(record.data, interest);
boolean gotBetterMatch = false;
if (selectedData == null) {
// Save the first match.
gotBetterMatch = true;
} else {
- if (interest.getChildSelector() == 0) {
+ if (interest.getChildSelector() == Interest.CHILD_SELECTOR_LEFT) {
// Leftmost child.
if (component.compare(selectedComponent) < 0) {
gotBetterMatch = true;
@@ -92,9 +71,9 @@
}
}
- if (gotBetterMatch) {
+ if (gotBetterMatch && hasAcceptableFreshness(interest, record)) {
selectedComponent = component;
- selectedData = content;
+ selectedData = record.data;
}
}
}
@@ -107,4 +86,74 @@
throw new DataNotFoundException();
}
}
+
+ /**
+ * @param content the content to check (e.g. /a/b/c)
+ * @param interest the interest to check from (e.g. /a/b)
+ * @return the next component from a Data packet after specified Interest
+ * components (e.g. c); if the Data is not longer than the Interest, return an
+ * empty component.
+ */
+ private Name.Component getNextComponentAfterLastInterestComponent(Data content, Interest interest) {
+ if (content.getName().size() > interest.getName().size()) {
+ return content.getName().get(interest.getName().size());
+ } else {
+ return new Name.Component();
+ }
+ }
+
+ private static boolean hasNoChildSelector(Interest interest) {
+ return interest.getChildSelector() < 0;
+ }
+
+ @Override
+ public void cleanup() {
+ for (int i = storage.size() - 1; i >= 0; i--) {
+ if (!isFresh(storage.get(i))) {
+ storage.remove(i);
+ }
+ }
+ }
+
+ /**
+ * Check if a record is fresh.
+ *
+ * @param record the record to check
+ * @return true if the record is fresh
+ */
+ private boolean isFresh(Record record) {
+ double period = record.data.getMetaInfo().getFreshnessPeriod();
+ return period < 0 || record.addedAt + period > System.currentTimeMillis();
+ }
+
+ /**
+ * Based on an Interest's requested freshness, determine if the record has an
+ * acceptable freshness.
+ *
+ * @param interest the Interest, with mustBeFresh set to true/false
+ * @param record the record to check
+ * @return true if the Interest does not require a fresh record or if the
+ * record is fresh
+ */
+ private boolean hasAcceptableFreshness(Interest interest, Record record) {
+ if (!interest.getMustBeFresh()) {
+ return true;
+ } else {
+ return isFresh(record);
+ }
+ }
+
+ /**
+ * Helper data structure
+ */
+ private class Record {
+
+ public final Data data;
+ public final long addedAt;
+
+ public Record(Data data) {
+ this.data = data;
+ this.addedAt = System.currentTimeMillis();
+ }
+ }
}
diff --git a/src/main/java/com/intel/jndn/utils/repository/Repository.java b/src/main/java/com/intel/jndn/utils/repository/Repository.java
index 9444e24..4647b9f 100644
--- a/src/main/java/com/intel/jndn/utils/repository/Repository.java
+++ b/src/main/java/com/intel/jndn/utils/repository/Repository.java
@@ -24,20 +24,25 @@
*/
public interface Repository {
- /**
- * Put a {@link Data} packet in the repository.
- *
- * @param data a {@link Data} packet
- */
- public void put(Data data);
+ /**
+ * 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;
+ /**
+ * 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;
+
+ /**
+ * Remove all stale {@link Data} packets from the repository.
+ */
+ public void cleanup();
}
diff --git a/src/test/java/com/intel/jndn/utils/repository/ForLoopRepositoryTest.java b/src/test/java/com/intel/jndn/utils/repository/ForLoopRepositoryTest.java
index 3071e95..1a73a01 100644
--- a/src/test/java/com/intel/jndn/utils/repository/ForLoopRepositoryTest.java
+++ b/src/test/java/com/intel/jndn/utils/repository/ForLoopRepositoryTest.java
@@ -13,39 +13,14 @@
*/
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 {
+public class ForLoopRepositoryTest extends RepositoryTest {
- @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")));
+ public ForLoopRepositoryTest() {
+ instance = new ForLoopRepository();
}
}
diff --git a/src/test/java/com/intel/jndn/utils/repository/RepoHelper.java b/src/test/java/com/intel/jndn/utils/repository/RepoHelper.java
new file mode 100644
index 0000000..7a624b0
--- /dev/null
+++ b/src/test/java/com/intel/jndn/utils/repository/RepoHelper.java
@@ -0,0 +1,52 @@
+/*
+ * 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 net.named_data.jndn.Data;
+import net.named_data.jndn.Interest;
+import net.named_data.jndn.Name;
+import net.named_data.jndn.util.Blob;
+
+/**
+ * Helper methods for testing.
+ *
+ * @author Andrew Brown <andrew.brown@intel.com>
+ */
+public class RepoHelper {
+
+ 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);
+ return interest;
+ }
+
+ public static Data buildAlmostStaleData(String staledata) {
+ Data data = RepoHelper.buildData(staledata);
+ data.getMetaInfo().setFreshnessPeriod(0);
+ return data;
+ }
+
+ public static Data buildFreshData(String staledata) {
+ Data data = RepoHelper.buildData(staledata);
+ data.getMetaInfo().setFreshnessPeriod(-1);
+ return data;
+ }
+}
diff --git a/src/test/java/com/intel/jndn/utils/repository/RepositoryPerformanceTest.java b/src/test/java/com/intel/jndn/utils/repository/RepositoryPerformanceTest.java
new file mode 100644
index 0000000..fa9ad07
--- /dev/null
+++ b/src/test/java/com/intel/jndn/utils/repository/RepositoryPerformanceTest.java
@@ -0,0 +1,168 @@
+/*
+ * 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 static com.intel.jndn.utils.repository.RepoHelper.*;
+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 static org.junit.Assert.*;
+import org.junit.Test;
+
+/**
+ * Test NDN repositories, including performance
+ *
+ * @author Andrew Brown <andrew.brown@intel.com>
+ */
+public class RepositoryPerformanceTest {
+
+ private static final Logger logger = Logger.getLogger(RepositoryPerformanceTest.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 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 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;
+ }
+ }
+}
diff --git a/src/test/java/com/intel/jndn/utils/repository/RepositoryTest.java b/src/test/java/com/intel/jndn/utils/repository/RepositoryTest.java
index a077edd..36fed91 100644
--- a/src/test/java/com/intel/jndn/utils/repository/RepositoryTest.java
+++ b/src/test/java/com/intel/jndn/utils/repository/RepositoryTest.java
@@ -13,191 +13,71 @@
*/
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 static com.intel.jndn.utils.repository.RepoHelper.*;
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;
+import static org.junit.Assert.*;
/**
- * Test NDN repositories, including performance
+ * Extend this in descendant tests.
*
* @author Andrew Brown <andrew.brown@intel.com>
*/
-public class RepositoryTest {
+public abstract class RepositoryTest {
- private static final Logger logger = Logger.getLogger(RepositoryTest.class.getName());
+ Repository instance;
@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));
+ public void testGetAndPut() throws DataNotFoundException {
+ instance.put(buildData("/a/b/c"));
+ Data data = instance.get(buildInterest("/a/b/c"));
+ assertEquals("...", data.getContent().toString());
}
- /**
- * 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"));
+ public void testThatChildSelectorsRetrieve() throws DataNotFoundException {
+ instance.put(buildData("/a/b/c"));
+ instance.put(buildData("/a/b/c/e"));
+ instance.put(buildData("/a/b/d"));
Interest interest = buildInterest("/a/b");
+ interest.setMustBeFresh(false);
interest.setChildSelector(Interest.CHILD_SELECTOR_RIGHT);
- Data data = repo.get(interest);
+ Data data = instance.get(interest);
assertEquals("/a/b/d", data.getName().toUri());
Interest interest2 = buildInterest("/a/b/c");
+ interest.setMustBeFresh(false);
interest2.setChildSelector(Interest.CHILD_SELECTOR_RIGHT);
- Data data2 = repo.get(interest2);
+ Data data2 = instance.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;
+ @Test(expected = DataNotFoundException.class)
+ public void testFailure() throws DataNotFoundException {
+ instance.get(new Interest(new Name("/unknown/data")));
}
- public static List<Data> buildDatas(List<Name> names) {
- List<Data> datas = new ArrayList<>();
- for (Name name : names) {
- datas.add(buildData(name.toUri()));
- }
- return datas;
+ @Test(expected = DataNotFoundException.class)
+ public void testCleanup() throws DataNotFoundException, InterruptedException {
+ instance.put(RepoHelper.buildAlmostStaleData("/stale/data"));
+ instance.put(RepoHelper.buildFreshData("/fresh/data"));
+
+ Thread.sleep(10);
+ instance.cleanup();
+
+ assertNotNull(instance.get(buildInterest("/fresh/data")));
+ instance.get(buildInterest("/stale/data"));
}
- public static List<Interest> buildInterests(List<Name> names) {
- List<Interest> interests = new ArrayList<>();
- for (Name name : names) {
- interests.add(buildInterest(name.toUri()));
- }
- return interests;
+ @Test(expected = DataNotFoundException.class)
+ public void testFreshnessFlag() throws InterruptedException, DataNotFoundException {
+ instance.put(buildAlmostStaleData("/stale/data"));
+ Thread.sleep(10);
+ Interest interest = buildInterest("/stale/data");
+ interest.setMustBeFresh(true);
+ instance.get(interest);
}
-
- 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;
- }
-
- }
-
}