table: shortcuts between FIB, PIT, Measurements, StrategyChoice
refs #1202
Change-Id: Ie63ab792e840de7e0889d385d3e8ea8a112cb7e5
diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index 7397c60..940f604 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -10,7 +10,7 @@
namespace nfd {
-const shared_ptr<fib::Entry> Fib::m_emptyEntry = make_shared<fib::Entry>(Name());
+const shared_ptr<fib::Entry> Fib::s_emptyEntry = make_shared<fib::Entry>(Name());
Fib::Fib(NameTree& nameTree)
: m_nameTree(nameTree)
@@ -49,19 +49,41 @@
if (static_cast<bool>(nameTreeEntry)) {
return nameTreeEntry->getFibEntry();
}
- return m_emptyEntry;
+ return s_emptyEntry;
+}
+
+shared_ptr<fib::Entry>
+Fib::findLongestPrefixMatch(shared_ptr<name_tree::Entry> nameTreeEntry) const
+{
+ shared_ptr<fib::Entry> entry = nameTreeEntry->getFibEntry();
+ if (static_cast<bool>(entry))
+ return entry;
+ nameTreeEntry = m_nameTree.findLongestPrefixMatch(nameTreeEntry,
+ &predicate_NameTreeEntry_hasFibEntry);
+ if (static_cast<bool>(nameTreeEntry)) {
+ return nameTreeEntry->getFibEntry();
+ }
+ return s_emptyEntry;
}
shared_ptr<fib::Entry>
Fib::findLongestPrefixMatch(const pit::Entry& pitEntry) const
{
- return this->findLongestPrefixMatch(pitEntry.getName());
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(pitEntry);
+
+ BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
+
+ return findLongestPrefixMatch(nameTreeEntry);
}
shared_ptr<fib::Entry>
Fib::findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const
{
- return this->findLongestPrefixMatch(measurementsEntry.getName());
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(measurementsEntry);
+
+ BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
+
+ return findLongestPrefixMatch(nameTreeEntry);
}
shared_ptr<fib::Entry>
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 5e2e03d..0fbacea 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -69,6 +69,9 @@
void
erase(const fib::Entry& entry);
+ shared_ptr<fib::Entry>
+ findLongestPrefixMatch(shared_ptr<name_tree::Entry> nameTreeEntry) const;
+
private:
NameTree& m_nameTree;
size_t m_nItems;
@@ -79,7 +82,7 @@
* It is returned by findLongestPrefixMatch if nothing is matched.
*/
// Returning empty entry instead of nullptr makes forwarding and strategy implementation easier.
- static const shared_ptr<fib::Entry> m_emptyEntry;
+ static const shared_ptr<fib::Entry> s_emptyEntry;
};
inline size_t
diff --git a/daemon/table/measurements-entry.hpp b/daemon/table/measurements-entry.hpp
index c7145d7..60a428f 100644
--- a/daemon/table/measurements-entry.hpp
+++ b/daemon/table/measurements-entry.hpp
@@ -13,6 +13,12 @@
namespace nfd {
+class NameTree;
+
+namespace name_tree {
+class Entry;
+}
+
class Measurements;
namespace measurements {
@@ -35,8 +41,11 @@
private: // lifetime
time::Point m_expiry;
EventId m_cleanup;
+ shared_ptr<name_tree::Entry> m_nameTreeEntry;
- friend class ::nfd::Measurements;
+ friend class nfd::NameTree;
+ friend class nfd::name_tree::Entry;
+ friend class nfd::Measurements;
};
inline const Name&
diff --git a/daemon/table/measurements.cpp b/daemon/table/measurements.cpp
index a5b107e..c284efa 100644
--- a/daemon/table/measurements.cpp
+++ b/daemon/table/measurements.cpp
@@ -30,28 +30,42 @@
}
shared_ptr<measurements::Entry>
-Measurements::get(const Name& name)
+Measurements::get(shared_ptr<name_tree::Entry> nameTreeEntry)
{
- shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(name);
shared_ptr<measurements::Entry> entry = nameTreeEntry->getMeasurementsEntry();
if (static_cast<bool>(entry))
return entry;
- entry = make_shared<measurements::Entry>(name);
+ entry = make_shared<measurements::Entry>(nameTreeEntry->getPrefix());
nameTreeEntry->setMeasurementsEntry(entry);
m_nItems++;
return entry;
}
shared_ptr<measurements::Entry>
+Measurements::get(const Name& name)
+{
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(name);
+ return get(nameTreeEntry);
+}
+
+shared_ptr<measurements::Entry>
Measurements::get(const fib::Entry& fibEntry)
{
- return this->get(fibEntry.getPrefix());
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(fibEntry);
+
+ BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
+
+ return get(nameTreeEntry);
}
shared_ptr<measurements::Entry>
Measurements::get(const pit::Entry& pitEntry)
{
- return this->get(pitEntry.getName());
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(pitEntry);
+
+ BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
+
+ return get(nameTreeEntry);
}
shared_ptr<measurements::Entry>
@@ -110,11 +124,10 @@
shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(entry->getName());
if (static_cast<bool>(nameTreeEntry))
{
- nameTreeEntry->eraseMeasurementsEntry(
- nameTreeEntry->getMeasurementsEntry());
+ nameTreeEntry->setMeasurementsEntry(shared_ptr<measurements::Entry>());
m_nItems--;
}
-
+
}
} // namespace nfd
diff --git a/daemon/table/measurements.hpp b/daemon/table/measurements.hpp
index 794f4a6..561b301 100644
--- a/daemon/table/measurements.hpp
+++ b/daemon/table/measurements.hpp
@@ -74,6 +74,9 @@
void
cleanup(shared_ptr<measurements::Entry> entry);
+ shared_ptr<measurements::Entry>
+ get(shared_ptr<name_tree::Entry> nameTreeEntry);
+
private:
NameTree& m_nameTree;
size_t m_nItems;
diff --git a/daemon/table/name-tree-entry.cpp b/daemon/table/name-tree-entry.cpp
index dd7bf4b..60d570d 100644
--- a/daemon/table/name-tree-entry.cpp
+++ b/daemon/table/name-tree-entry.cpp
@@ -60,23 +60,27 @@
void
Entry::insertPitEntry(shared_ptr<pit::Entry> pit)
{
- m_pitEntries.push_back(pit);
+ if (static_cast<bool>(pit)) {
+ pit->m_nameTreeEntry = this->shared_from_this();
+ m_pitEntries.push_back(pit);
+ }
}
bool
Entry::erasePitEntry(shared_ptr<pit::Entry> pit)
{
- for (size_t i = 0; i < m_pitEntries.size(); i++)
- {
- if (m_pitEntries[i] == pit)
- {
+ for (size_t i = 0; i < m_pitEntries.size(); i++) {
+ if (m_pitEntries[i] == pit) {
+ BOOST_ASSERT(pit->m_nameTreeEntry);
+
+ pit->m_nameTreeEntry.reset();
// copy the last item to the current position
m_pitEntries[i] = m_pitEntries[m_pitEntries.size() - 1];
// then erase the last item
m_pitEntries.pop_back();
return true; // success
- }
- }
+ }
+ }
// not found this entry
return false; // failure
}
@@ -84,16 +88,13 @@
void
Entry::setMeasurementsEntry(shared_ptr<measurements::Entry> measurements)
{
+ if (static_cast<bool>(m_measurementsEntry)) {
+ m_measurementsEntry->m_nameTreeEntry.reset();
+ }
m_measurementsEntry = measurements;
-}
-
-bool
-Entry::eraseMeasurementsEntry(shared_ptr<measurements::Entry> measurements)
-{
- if (m_measurementsEntry != measurements)
- return false;
- m_measurementsEntry.reset();
- return true;
+ if (static_cast<bool>(m_measurementsEntry)) {
+ m_measurementsEntry->m_nameTreeEntry = this->shared_from_this();
+ }
}
void
diff --git a/daemon/table/name-tree-entry.hpp b/daemon/table/name-tree-entry.hpp
index e3c72f2..5661961 100644
--- a/daemon/table/name-tree-entry.hpp
+++ b/daemon/table/name-tree-entry.hpp
@@ -107,9 +107,6 @@
shared_ptr<measurements::Entry>
getMeasurementsEntry() const;
- bool
- eraseMeasurementsEntry(shared_ptr<measurements::Entry> measurements);
-
void
setStrategyChoiceEntry(shared_ptr<strategy_choice::Entry> strategyChoiceEntry);
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index 430ed3c..0820683 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -203,6 +203,19 @@
return shared_ptr<name_tree::Entry>();
}
+shared_ptr<name_tree::Entry>
+NameTree::findLongestPrefixMatch(shared_ptr<name_tree::Entry> entry,
+ const name_tree::EntrySelector& entrySelector) const
+{
+ while (static_cast<bool>(entry))
+ {
+ if (entrySelector(*entry))
+ return entry;
+ entry = entry->getParent();
+ }
+ return shared_ptr<name_tree::Entry>();
+}
+
// return {false: this entry is not empty, true: this entry is empty and erased}
bool
NameTree::eraseEntryIfEmpty(shared_ptr<name_tree::Entry> entry)
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 3d0de70..b51e033 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -125,6 +125,11 @@
const name_tree::EntrySelector& entrySelector =
name_tree::AnyEntry()) const;
+ shared_ptr<name_tree::Entry>
+ findLongestPrefixMatch(shared_ptr<name_tree::Entry> entry,
+ const name_tree::EntrySelector& entrySelector =
+ name_tree::AnyEntry()) const;
+
/**
* \brief Resize the hash table size when its load factor reaches a threshold.
* \details As we are currently using a hand-written hash table implementation
@@ -162,6 +167,18 @@
void
dump(std::ostream& output) const;
+ shared_ptr<name_tree::Entry>
+ get(const fib::Entry& fibEntry) const;
+
+ shared_ptr<name_tree::Entry>
+ get(const pit::Entry& pitEntry) const;
+
+ shared_ptr<name_tree::Entry>
+ get(const measurements::Entry& measurementsEntry) const;
+
+ shared_ptr<name_tree::Entry>
+ get(const strategy_choice::Entry& strategeChoiceEntry) const;
+
const_iterator
begin() const;
@@ -260,6 +277,30 @@
return fibEntry.m_nameTreeEntry;
}
+inline shared_ptr<name_tree::Entry>
+NameTree::get(const fib::Entry& fibEntry) const
+{
+ return fibEntry.m_nameTreeEntry;
+}
+
+inline shared_ptr<name_tree::Entry>
+NameTree::get(const pit::Entry& pitEntry) const
+{
+ return pitEntry.m_nameTreeEntry;
+}
+
+inline shared_ptr<name_tree::Entry>
+NameTree::get(const measurements::Entry& measurementsEntry) const
+{
+ return measurementsEntry.m_nameTreeEntry;
+}
+
+inline shared_ptr<name_tree::Entry>
+NameTree::get(const strategy_choice::Entry& strategeChoiceEntry) const
+{
+ return strategeChoiceEntry.m_nameTreeEntry;
+}
+
inline NameTree::const_iterator
NameTree::begin() const
{
diff --git a/daemon/table/pit-entry.hpp b/daemon/table/pit-entry.hpp
index c9cfdac..aeff8d8 100644
--- a/daemon/table/pit-entry.hpp
+++ b/daemon/table/pit-entry.hpp
@@ -12,6 +12,13 @@
#include "core/scheduler.hpp"
namespace nfd {
+
+class NameTree;
+
+namespace name_tree {
+class Entry;
+}
+
namespace pit {
/** \class InRecordCollection
@@ -95,6 +102,10 @@
const Interest m_interest;
InRecordCollection m_inRecords;
OutRecordCollection m_outRecords;
+ shared_ptr<name_tree::Entry> m_nameTreeEntry;
+
+ friend class nfd::NameTree;
+ friend class nfd::name_tree::Entry;
};
inline const Interest&
diff --git a/daemon/table/strategy-choice.cpp b/daemon/table/strategy-choice.cpp
index c24a5b0..9ce2c99 100644
--- a/daemon/table/strategy-choice.cpp
+++ b/daemon/table/strategy-choice.cpp
@@ -133,15 +133,35 @@
}
Strategy&
+StrategyChoice::findEffectiveStrategy(shared_ptr<name_tree::Entry> nameTreeEntry) const
+{
+ shared_ptr<strategy_choice::Entry> entry = nameTreeEntry->getStrategyChoiceEntry();
+ if (static_cast<bool>(entry))
+ return entry->getStrategy();
+ nameTreeEntry = m_nameTree.findLongestPrefixMatch(nameTreeEntry,
+ &predicate_NameTreeEntry_hasStrategyChoiceEntry);
+ BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
+ return nameTreeEntry->getStrategyChoiceEntry()->getStrategy();
+}
+
+Strategy&
StrategyChoice::findEffectiveStrategy(const pit::Entry& pitEntry) const
{
- return this->findEffectiveStrategy(pitEntry.getName());
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(pitEntry);
+
+ BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
+
+ return findEffectiveStrategy(nameTreeEntry);
}
Strategy&
StrategyChoice::findEffectiveStrategy(const measurements::Entry& measurementsEntry) const
{
- return this->findEffectiveStrategy(measurementsEntry.getName());
+ shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(measurementsEntry);
+
+ BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
+
+ return findEffectiveStrategy(nameTreeEntry);
}
shared_ptr<fw::Strategy>
diff --git a/daemon/table/strategy-choice.hpp b/daemon/table/strategy-choice.hpp
index 9d45f15..2e3a8fd 100644
--- a/daemon/table/strategy-choice.hpp
+++ b/daemon/table/strategy-choice.hpp
@@ -79,6 +79,9 @@
shared_ptr<fw::Strategy> oldStrategy,
shared_ptr<fw::Strategy> newStrategy);
+ fw::Strategy&
+ findEffectiveStrategy(shared_ptr<name_tree::Entry> nameTreeEntry) const;
+
private:
NameTree& m_nameTree;
size_t m_nItems;