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