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-2019, 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 {
40 }
41 
42 std::pair<shared_ptr<Entry>, bool>
43 Pit::findOrInsert(const Interest& interest, bool allowInsert)
44 {
45  // determine which NameTree entry should the PIT entry be attached onto
46  const Name& name = interest.getName();
47  bool hasDigest = name.size() > 0 && name[-1].isImplicitSha256Digest();
48  size_t nteDepth = name.size() - static_cast<int>(hasDigest);
49  nteDepth = std::min(nteDepth, NameTree::getMaxDepth());
50 
51  // ensure NameTree entry exists
52  name_tree::Entry* nte = nullptr;
53  if (allowInsert) {
54  nte = &m_nameTree.lookup(name, nteDepth);
55  }
56  else {
57  nte = m_nameTree.findExactMatch(name, nteDepth);
58  if (nte == nullptr) {
59  return {nullptr, true};
60  }
61  }
62 
63  // check if PIT entry already exists
64  const auto& pitEntries = nte->getPitEntries();
65  auto it = std::find_if(pitEntries.begin(), pitEntries.end(),
66  [&interest, nteDepth] (const shared_ptr<Entry>& entry) {
67  // NameTree guarantees first nteDepth components are equal
68  return entry->canMatch(interest, nteDepth);
69  });
70  if (it != pitEntries.end()) {
71  return {*it, false};
72  }
73 
74  if (!allowInsert) {
75  BOOST_ASSERT(!nte->isEmpty()); // nte shouldn't be created in this call
76  return {nullptr, true};
77  }
78 
79  auto entry = make_shared<Entry>(interest);
80  nte->insertPitEntry(entry);
81  ++m_nItems;
82  return {entry, true};
83 }
84 
86 Pit::findAllDataMatches(const Data& data) const
87 {
88  auto&& ntMatches = m_nameTree.findAllMatches(data.getName(), &nteHasPitEntries);
89 
90  DataMatchResult matches;
91  for (const auto& nte : ntMatches) {
92  for (const auto& pitEntry : nte.getPitEntries()) {
93  if (pitEntry->getInterest().matchesData(data))
94  matches.emplace_back(pitEntry);
95  }
96  }
97 
98  return matches;
99 }
100 
101 void
102 Pit::erase(Entry* entry, bool canDeleteNte)
103 {
104  name_tree::Entry* nte = m_nameTree.getEntry(*entry);
105  BOOST_ASSERT(nte != nullptr);
106 
107  nte->erasePitEntry(entry);
108  if (canDeleteNte) {
109  m_nameTree.eraseIfEmpty(nte);
110  }
111  --m_nItems;
112 }
113 
114 void
115 Pit::deleteInOutRecords(Entry* entry, const Face& face)
116 {
117  BOOST_ASSERT(entry != nullptr);
118 
119  entry->deleteInRecord(face);
120  entry->deleteOutRecord(face);
121 
123 }
124 
126 Pit::begin() const
127 {
128  return const_iterator(m_nameTree.fullEnumerate(&nteHasPitEntries).begin());
129 }
130 
131 } // namespace pit
132 } // namespace nfd
void deleteInRecord(const Face &face)
delete the in-record for face if it exists
Definition: pit-entry.cpp:75
A common index structure for FIB, PIT, StrategyChoice, and Measurements.
Definition: name-tree.hpp:36
size_t eraseIfEmpty(Entry *entry, bool canEraseAncestors=true)
Delete the entry if it is empty.
Definition: name-tree.cpp:123
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:114
static constexpr size_t getMaxDepth()
Maximum depth of the name tree.
Definition: name-tree.hpp:51
Pit(NameTree &nameTree)
Definition: pit.cpp:37
const std::vector< shared_ptr< pit::Entry > > & getPitEntries() const
Entry * getEntry(const EntryT &tableEntry) const
Definition: name-tree.hpp:77
Range fullEnumerate(const EntrySelector &entrySelector=AnyEntry()) const
Enumerate all entries.
Definition: name-tree.cpp:226
DataMatchResult findAllDataMatches(const Data &data) const
Performs a Data match.
Definition: pit.cpp:86
Entry * findExactMatch(const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
Exact match lookup.
Definition: name-tree.cpp:150
An Interest table entry.
Definition: pit-entry.hpp:58
Iterator const_iterator
Definition: pit.hpp:102
Entry & lookup(const Name &name, size_t prefixLen)
Find or insert an entry by name.
Definition: name-tree.cpp:44
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-records and out-records for face.
Definition: pit.cpp:115
generalization of a network interface
Definition: face.hpp:54
bool isEmpty() const
An entry in the name tree.
static bool nteHasPitEntries(const name_tree::Entry &nte)
Definition: pit.cpp:32
const_iterator begin() const
Definition: pit.cpp:126
Range findAllMatches(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
All-prefixes match lookup.
Definition: name-tree.cpp:213
An unordered iterable of all PIT entries matching Data.
void erase(Entry *entry)
Deletes an entry.
Definition: pit.hpp:91
void insertPitEntry(shared_ptr< pit::Entry > pitEntry)
bool hasPitEntries() const