Junxiao Shi | cbba04c | 2014-01-26 14:21:22 -0700 | [diff] [blame] | 1 | /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
| 2 | /** |
| 3 | * Copyright (C) 2014 Named Data Networking Project |
| 4 | * See COPYING for copyright and distribution information. |
| 5 | */ |
| 6 | |
Haowei Yuan | 78c84d1 | 2014-02-27 15:35:13 -0600 | [diff] [blame^] | 7 | /** |
| 8 | * KNOWN ISSUES |
| 9 | * |
| 10 | * - To remove a PIT entry, we need to first perform a lookup on NameTree |
| 11 | * to locate its NameTree Entry, and then call NameTreeEntry->deletePitEntry() |
| 12 | * function. Alternatively, we could store a pointer at each PIT-Entry, which |
| 13 | * would speed up this procedure with the cost of additional memory space. Maybe |
| 14 | * this could also be part of the PIT/FIB/Measurement shortcut, where all of these |
| 15 | * entries have pointers to their NameTreeEntry. Which could be part of task |
| 16 | * #1202, shortcuts between FIB, PIT, Measurements. |
| 17 | * |
| 18 | */ |
| 19 | |
Junxiao Shi | cbba04c | 2014-01-26 14:21:22 -0700 | [diff] [blame] | 20 | #include "pit.hpp" |
Junxiao Shi | cbba04c | 2014-01-26 14:21:22 -0700 | [diff] [blame] | 21 | |
Alexander Afanasyev | 18bbf81 | 2014-01-29 01:40:23 -0800 | [diff] [blame] | 22 | namespace nfd { |
Junxiao Shi | cbba04c | 2014-01-26 14:21:22 -0700 | [diff] [blame] | 23 | |
Haowei Yuan | 78c84d1 | 2014-02-27 15:35:13 -0600 | [diff] [blame^] | 24 | Pit::Pit(NameTree& nameTree) : m_nameTree(nameTree), m_nItems(0) |
Junxiao Shi | cbba04c | 2014-01-26 14:21:22 -0700 | [diff] [blame] | 25 | { |
| 26 | } |
| 27 | |
| 28 | Pit::~Pit() |
| 29 | { |
| 30 | } |
| 31 | |
| 32 | static inline bool |
| 33 | operator==(const Exclude& a, const Exclude& b) |
| 34 | { |
| 35 | const Block& aBlock = a.wireEncode(); |
| 36 | const Block& bBlock = b.wireEncode(); |
| 37 | return aBlock.size() == bBlock.size() && |
| 38 | 0 == memcmp(aBlock.wire(), bBlock.wire(), aBlock.size()); |
| 39 | } |
| 40 | |
| 41 | static inline bool |
| 42 | predicate_PitEntry_similar_Interest(shared_ptr<pit::Entry> entry, |
| 43 | const Interest& interest) |
| 44 | { |
| 45 | const Interest& pi = entry->getInterest(); |
| 46 | return pi.getName().equals(interest.getName()) && |
| 47 | pi.getMinSuffixComponents() == interest.getMinSuffixComponents() && |
| 48 | pi.getMaxSuffixComponents() == interest.getMaxSuffixComponents() && |
| 49 | // TODO PublisherPublicKeyLocator (ndn-cpp-dev #1157) |
| 50 | pi.getExclude() == interest.getExclude() && |
| 51 | pi.getChildSelector() == interest.getChildSelector() && |
| 52 | pi.getMustBeFresh() == interest.getMustBeFresh(); |
| 53 | } |
| 54 | |
| 55 | std::pair<shared_ptr<pit::Entry>, bool> |
| 56 | Pit::insert(const Interest& interest) |
| 57 | { |
Haowei Yuan | 78c84d1 | 2014-02-27 15:35:13 -0600 | [diff] [blame^] | 58 | // - first lookup() the Interest Name in the NameTree, which will creates all |
| 59 | // the intermedia nodes, starting from the shortest prefix. |
| 60 | // - if it is guaranteed that this Interest already has a NameTree Entry, we |
| 61 | // could use findExactMatch() instead. |
| 62 | // - Alternatively, we could try to do findExactMatch() first, if not found, then |
| 63 | // do lookup(). |
| 64 | shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(interest.getName()); |
| 65 | |
| 66 | BOOST_ASSERT(static_cast<bool>(nameTreeEntry)); |
| 67 | |
| 68 | std::vector<shared_ptr<pit::Entry> >& pitEntries = nameTreeEntry->getPitEntries(); |
| 69 | |
| 70 | // then check if this Interest is already in the PIT entries |
| 71 | std::vector<shared_ptr<pit::Entry> >::iterator it = std::find_if(pitEntries.begin(), pitEntries.end(), bind(&predicate_PitEntry_similar_Interest, _1, interest)); |
| 72 | |
| 73 | if (it != pitEntries.end()) |
| 74 | { |
| 75 | return std::make_pair(*it, false); |
| 76 | } |
| 77 | else |
| 78 | { |
| 79 | shared_ptr<pit::Entry> entry = make_shared<pit::Entry>(interest); |
| 80 | nameTreeEntry->insertPitEntry(entry); |
| 81 | |
| 82 | // Increase m_nItmes only if we create a new PIT Entry |
| 83 | m_nItems++; |
| 84 | |
| 85 | return std::make_pair(entry, true); |
| 86 | } |
Junxiao Shi | cbba04c | 2014-01-26 14:21:22 -0700 | [diff] [blame] | 87 | } |
| 88 | |
| 89 | shared_ptr<pit::DataMatchResult> |
| 90 | Pit::findAllDataMatches(const Data& data) const |
| 91 | { |
| 92 | shared_ptr<pit::DataMatchResult> result = make_shared<pit::DataMatchResult>(); |
Haowei Yuan | 78c84d1 | 2014-02-27 15:35:13 -0600 | [diff] [blame^] | 93 | |
| 94 | shared_ptr<name_tree::Entry> nameTreeEntry; |
| 95 | |
| 96 | // NOTE: We are using findLongestPrefixMatch() here. |
| 97 | // The reason is that findLongestPrefixMatch() starts with the full name |
| 98 | // and then remove one component each time, which is the type of behavior we would like |
| 99 | // to use here. |
| 100 | // If it could be guranteed that the quering Data packet always has a Name Tree |
| 101 | // Entry, we could also use findExactMatch(). |
| 102 | for (nameTreeEntry = m_nameTree.findLongestPrefixMatch(data.getName()); |
| 103 | static_cast<bool>(nameTreeEntry); |
| 104 | nameTreeEntry = nameTreeEntry->getParent()) |
| 105 | { |
| 106 | std::vector<shared_ptr<pit::Entry> >& pitEntries = nameTreeEntry->getPitEntries(); |
| 107 | for (size_t i = 0; i < pitEntries.size(); i++) |
| 108 | { |
| 109 | if (pitEntries[i]->getInterest().matchesName(data.getName())) |
| 110 | result->push_back(pitEntries[i]); |
| 111 | } |
Junxiao Shi | cbba04c | 2014-01-26 14:21:22 -0700 | [diff] [blame] | 112 | } |
Haowei Yuan | 78c84d1 | 2014-02-27 15:35:13 -0600 | [diff] [blame^] | 113 | |
Junxiao Shi | cbba04c | 2014-01-26 14:21:22 -0700 | [diff] [blame] | 114 | return result; |
| 115 | } |
| 116 | |
| 117 | void |
Haowei Yuan | 78c84d1 | 2014-02-27 15:35:13 -0600 | [diff] [blame^] | 118 | Pit::erase(shared_ptr<pit::Entry> pitEntry) |
Junxiao Shi | cbba04c | 2014-01-26 14:21:22 -0700 | [diff] [blame] | 119 | { |
Haowei Yuan | 78c84d1 | 2014-02-27 15:35:13 -0600 | [diff] [blame^] | 120 | // first get the NPE |
| 121 | // If pit-entry.hpp stores a NameTree Entry for each PIT, we could also use the get() method |
| 122 | // directly, saving one hash computation. |
| 123 | shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(pitEntry->getName()); |
| 124 | |
| 125 | BOOST_ASSERT(static_cast<bool>(nameTreeEntry)); |
| 126 | |
| 127 | // erase this PIT entry |
| 128 | if (static_cast<bool>(nameTreeEntry)) |
| 129 | { |
| 130 | nameTreeEntry->erasePitEntry(pitEntry); |
| 131 | m_nameTree.eraseEntryIfEmpty(nameTreeEntry); |
| 132 | |
| 133 | m_nItems--; |
| 134 | } |
Junxiao Shi | cbba04c | 2014-01-26 14:21:22 -0700 | [diff] [blame] | 135 | } |
| 136 | |
Alexander Afanasyev | 18bbf81 | 2014-01-29 01:40:23 -0800 | [diff] [blame] | 137 | } // namespace nfd |