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