NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
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-2018, 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 hasDigest = name.size() > 0 && name[-1].isImplicitSha256Digest();
49  size_t nteDepth = name.size() - static_cast<int>(hasDigest);
50  nteDepth = std::min(nteDepth, NameTree::getMaxDepth());
51 
52  // ensure NameTree entry exists
53  name_tree::Entry* nte = nullptr;
54  if (allowInsert) {
55  nte = &m_nameTree.lookup(name, nteDepth);
56  }
57  else {
58  nte = m_nameTree.findExactMatch(name, nteDepth);
59  if (nte == nullptr) {
60  return {nullptr, true};
61  }
62  }
63 
64  // check if PIT entry already exists
65  const auto& pitEntries = nte->getPitEntries();
66  auto it = std::find_if(pitEntries.begin(), pitEntries.end(),
67  [&interest, nteDepth] (const shared_ptr<Entry>& entry) {
68  // NameTree guarantees first nteDepth components are equal
69  return entry->canMatch(interest, nteDepth);
70  });
71  if (it != pitEntries.end()) {
72  return {*it, false};
73  }
74 
75  if (!allowInsert) {
76  BOOST_ASSERT(!nte->isEmpty()); // nte shouldn't be created in this call
77  return {nullptr, true};
78  }
79 
80  auto entry = make_shared<Entry>(interest);
81  nte->insertPitEntry(entry);
82  ++m_nItems;
83  return {entry, true};
84 }
85 
87 Pit::findAllDataMatches(const Data& data) const
88 {
89  auto&& ntMatches = m_nameTree.findAllMatches(data.getName(), &nteHasPitEntries);
90 
91  DataMatchResult matches;
92  for (const name_tree::Entry& nte : ntMatches) {
93  for (const shared_ptr<Entry>& pitEntry : nte.getPitEntries()) {
94  if (pitEntry->getInterest().matchesData(data))
95  matches.emplace_back(pitEntry);
96  }
97  }
98 
99  return matches;
100 }
101 
102 void
103 Pit::erase(Entry* entry, bool canDeleteNte)
104 {
105  name_tree::Entry* nte = m_nameTree.getEntry(*entry);
106  BOOST_ASSERT(nte != nullptr);
107 
108  nte->erasePitEntry(entry);
109  if (canDeleteNte) {
110  m_nameTree.eraseIfEmpty(nte);
111  }
112  --m_nItems;
113 }
114 
115 void
116 Pit::deleteInOutRecords(Entry* entry, const Face& face)
117 {
118  BOOST_ASSERT(entry != nullptr);
119 
120  entry->deleteInRecord(face);
121  entry->deleteOutRecord(face);
122 
124 }
125 
127 Pit::begin() const
128 {
129  return const_iterator(m_nameTree.fullEnumerate(&nteHasPitEntries).begin());
130 }
131 
132 } // namespace pit
133 } // namespace nfd
void insertPitEntry(shared_ptr< pit::Entry > pitEntry)
void erase(Entry *entry)
deletes an entry
Definition: pit.hpp:91
const Name & getName() const
Get name.
Definition: data.hpp:124
generalization of a network interface
Definition: face.hpp:67
void deleteInOutRecords(Entry *entry, const Face &face)
deletes in-record and out-record for face
Definition: pit.cpp:116
const std::vector< shared_ptr< pit::Entry > > & getPitEntries() const
PIT iterator.
void erasePitEntry(pit::Entry *pitEntry)
Represents an Interest packet.
Definition: interest.hpp:44
Iterator const_iterator
Definition: pit.hpp:102
DataMatchResult findAllDataMatches(const Data &data) const
performs a Data match
Definition: pit.cpp:87
Entry & lookup(const Name &name, size_t prefixLen)
find or insert an entry by name
Definition: name-tree.cpp:44
std::vector< shared_ptr< Entry > > DataMatchResult
Definition: pit.hpp:43
Range findAllMatches(const Name &name, const EntrySelector &entrySelector=AnyEntry()) const
all-prefixes match lookup
Definition: name-tree.cpp:213
Copyright (c) 2011-2015 Regents of the University of California.
Definition: ndn-common.hpp:40
an Interest table entry
Definition: pit-entry.hpp:59
Entry * getEntry(const EntryT &tableEntry) const
Definition: name-tree.hpp:79
void deleteOutRecord(const Face &face)
delete the out-record for face if it exists
Definition: pit-entry.cpp:115
Represents an absolute name.
Definition: name.hpp:43
Range fullEnumerate(const EntrySelector &entrySelector=AnyEntry()) const
enumerate all entries
Definition: name-tree.cpp:226
void deleteInRecord(const Face &face)
delete the in-record for face if it exists
Definition: pit-entry.cpp:76
static bool nteHasPitEntries(const name_tree::Entry &nte)
Definition: pit.cpp:32
size_t eraseIfEmpty(Entry *entry, bool canEraseAncestors=true)
delete the entry if it is empty
Definition: name-tree.cpp:123
a common index structure for FIB, PIT, StrategyChoice, and Measurements
Definition: name-tree.hpp:38
An unordered iterable of all PIT entries matching Data.
const_iterator begin() const
Definition: pit.cpp:127
Entry * findExactMatch(const Name &name, size_t prefixLen=std::numeric_limits< size_t >::max()) const
exact match lookup
Definition: name-tree.cpp:150
Pit(NameTree &nameTree)
Definition: pit.cpp:37
Represents a Data packet.
Definition: data.hpp:35
an entry in the name tree
const Name & getName() const
Definition: interest.hpp:134
static constexpr size_t getMaxDepth()
maximum depth of the name tree
Definition: name-tree.hpp:53