pit.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2014-2017, Regents of the University of California,
4  * Arizona Board of Regents,
5  * Colorado State University,
6  * University Pierre & Marie Curie, Sorbonne University,
7  * Washington University in St. Louis,
8  * Beijing Institute of Technology,
9  * The University of Memphis.
10  *
11  * This file is part of NFD (Named Data Networking Forwarding Daemon).
12  * See AUTHORS.md for complete list of NFD authors and contributors.
13  *
14  * NFD is free software: you can redistribute it and/or modify it under the terms
15  * of the GNU General Public License as published by the Free Software Foundation,
16  * either version 3 of the License, or (at your option) any later version.
17  *
18  * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
19  * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
20  * PURPOSE. See the GNU General Public License for more details.
21  *
22  * You should have received a copy of the GNU General Public License along with
23  * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
24  */
25 
26 #include "pit.hpp"
27 
28 namespace nfd {
29 namespace pit {
30 
31 static inline bool
33 {
34  return nte.hasPitEntries();
35 }
36 
37 Pit::Pit(NameTree& nameTree)
38  : m_nameTree(nameTree)
39  , m_nItems(0)
40 {
41 }
42 
43 std::pair<shared_ptr<Entry>, bool>
44 Pit::findOrInsert(const Interest& interest, bool allowInsert)
45 {
46  // determine which NameTree entry should the PIT entry be attached onto
47  const Name& name = interest.getName();
48  bool isEndWithDigest = name.size() > 0 && name[-1].isImplicitSha256Digest();
49  const Name& nteName = isEndWithDigest ? name.getPrefix(-1) : name;
50 
51  // ensure NameTree entry exists
52  name_tree::Entry* nte = nullptr;
53  if (allowInsert) {
54  nte = &m_nameTree.lookup(nteName, true);
55  }
56  else {
57  nte = m_nameTree.findExactMatch(nteName);
58  if (nte == nullptr) {
59  return {nullptr, true};
60  }
61  }
62 
63  // check if PIT entry already exists
64  size_t nteNameLen = nte->getName().size();
65  const std::vector<shared_ptr<Entry>>& pitEntries = nte->getPitEntries();
66  auto it = std::find_if(pitEntries.begin(), pitEntries.end(),
67  [&interest, nteNameLen] (const shared_ptr<Entry>& entry) {
68  // initial part of name is guaranteed to be equal by NameTree
69  // check implicit digest (or its absence) only
70  return entry->canMatch(interest, nteNameLen);
71  });
72  if (it != pitEntries.end()) {
73  return {*it, false};
74  }
75 
76  if (!allowInsert) {
77  BOOST_ASSERT(!nte->isEmpty()); // nte shouldn't be created in this call
78  return {nullptr, true};
79  }
80 
81  auto entry = make_shared<Entry>(interest);
82  nte->insertPitEntry(entry);
83  ++m_nItems;
84  return {entry, true};
85 }
86 
88 Pit::findAllDataMatches(const Data& data) const
89 {
90  auto&& ntMatches = m_nameTree.findAllMatches(data.getName(), &nteHasPitEntries);
91 
92  DataMatchResult matches;
93  for (const name_tree::Entry& nte : ntMatches) {
94  for (const shared_ptr<Entry>& pitEntry : nte.getPitEntries()) {
95  if (pitEntry->getInterest().matchesData(data))
96  matches.emplace_back(pitEntry);
97  }
98  }
99 
100  return matches;
101 }
102 
103 void
104 Pit::erase(Entry* entry, bool canDeleteNte)
105 {
106  name_tree::Entry* nte = m_nameTree.getEntry(*entry);
107  BOOST_ASSERT(nte != nullptr);
108 
109  nte->erasePitEntry(entry);
110  if (canDeleteNte) {
111  m_nameTree.eraseIfEmpty(nte);
112  }
113  --m_nItems;
114 }
115 
116 void
117 Pit::deleteInOutRecords(Entry* entry, const Face& face)
118 {
119  BOOST_ASSERT(entry != nullptr);
120 
121  entry->deleteInRecord(face);
122  entry->deleteOutRecord(face);
123 
125 }
126 
128 Pit::begin() const
129 {
130  return const_iterator(m_nameTree.fullEnumerate(&nteHasPitEntries).begin());
131 }
132 
133 } // namespace pit
134 } // namespace nfd
const_iterator begin() const
Definition: pit.cpp:128
void deleteInRecord(const Face &face)
delete the in-record for face if it exists
Definition: pit-entry.cpp:74
bool isEmpty() const
void erasePitEntry(pit::Entry *pitEntry)
PIT iterator.
void deleteOutRecord(const Face &face)
delete the out-record for face if it exists
Definition: pit-entry.cpp:113
Pit(NameTree &nameTree)
Definition: pit.cpp:37
const std::vector< shared_ptr< pit::Entry > > & getPitEntries() const
an Interest table entry
Definition: pit-entry.hpp:57
Iterator const_iterator
Definition: pit.hpp:101
bool hasPitEntries() const
Copyright (c) 2014-2015, Regents of the University of California, Arizona Board of Regents...
Definition: algorithm.hpp:32
void deleteInOutRecords(Entry *entry, const Face &face)
deletes in-record and out-record for face
Definition: pit.cpp:117
an entry in the name tree
static bool nteHasPitEntries(const name_tree::Entry &nte)
Definition: pit.cpp:32
DataMatchResult findAllDataMatches(const Data &data) const
performs a Data match
Definition: pit.cpp:88
void erase(Entry *entry)
deletes an entry
Definition: pit.hpp:90
std::vector< shared_ptr< Entry > > DataMatchResult
Definition: pit.hpp:42
const Name & getName() const
void insertPitEntry(shared_ptr< pit::Entry > pitEntry)