blob: 6f0e4461025254c1bb2e90a15628a32d22d3b936 [file] [log] [blame]
Junxiao Shicbba04c2014-01-26 14:21:22 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -07003 * Copyright (c) 2014 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 *
10 * This file is part of NFD (Named Data Networking Forwarding Daemon).
11 * See AUTHORS.md for complete list of NFD authors and contributors.
12 *
13 * NFD is free software: you can redistribute it and/or modify it under the terms
14 * of the GNU General Public License as published by the Free Software Foundation,
15 * either version 3 of the License, or (at your option) any later version.
16 *
17 * NFD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
18 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
19 * PURPOSE. See the GNU General Public License for more details.
20 *
21 * You should have received a copy of the GNU General Public License along with
22 * NFD, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
23 **/
Junxiao Shicbba04c2014-01-26 14:21:22 -070024
25#include "pit.hpp"
Junxiao Shicbba04c2014-01-26 14:21:22 -070026
Alexander Afanasyev18bbf812014-01-29 01:40:23 -080027namespace nfd {
Junxiao Shicbba04c2014-01-26 14:21:22 -070028
Junxiao Shi30d35992014-04-03 14:51:58 -070029Pit::Pit(NameTree& nameTree)
30 : m_nameTree(nameTree)
31 , m_nItems(0)
Junxiao Shicbba04c2014-01-26 14:21:22 -070032{
33}
34
35Pit::~Pit()
36{
37}
38
39static inline bool
Haowei Yuane1079fc2014-03-08 14:41:25 -060040predicate_NameTreeEntry_hasPitEntry(const name_tree::Entry& entry)
41{
42 return entry.hasPitEntries();
43}
44
45static inline bool
Junxiao Shicbba04c2014-01-26 14:21:22 -070046operator==(const Exclude& a, const Exclude& b)
47{
48 const Block& aBlock = a.wireEncode();
49 const Block& bBlock = b.wireEncode();
50 return aBlock.size() == bBlock.size() &&
51 0 == memcmp(aBlock.wire(), bBlock.wire(), aBlock.size());
52}
53
54static inline bool
55predicate_PitEntry_similar_Interest(shared_ptr<pit::Entry> entry,
56 const Interest& interest)
57{
58 const Interest& pi = entry->getInterest();
59 return pi.getName().equals(interest.getName()) &&
60 pi.getMinSuffixComponents() == interest.getMinSuffixComponents() &&
61 pi.getMaxSuffixComponents() == interest.getMaxSuffixComponents() &&
Junxiao Shi30d35992014-04-03 14:51:58 -070062 pi.getPublisherPublicKeyLocator() == interest.getPublisherPublicKeyLocator() &&
Junxiao Shicbba04c2014-01-26 14:21:22 -070063 pi.getExclude() == interest.getExclude() &&
64 pi.getChildSelector() == interest.getChildSelector() &&
65 pi.getMustBeFresh() == interest.getMustBeFresh();
66}
67
68std::pair<shared_ptr<pit::Entry>, bool>
69Pit::insert(const Interest& interest)
70{
Haowei Yuan78c84d12014-02-27 15:35:13 -060071 // - first lookup() the Interest Name in the NameTree, which will creates all
72 // the intermedia nodes, starting from the shortest prefix.
Haowei Yuane1079fc2014-03-08 14:41:25 -060073 // - if it is guaranteed that this Interest already has a NameTree Entry, we
Haowei Yuan78c84d12014-02-27 15:35:13 -060074 // could use findExactMatch() instead.
Haowei Yuane1079fc2014-03-08 14:41:25 -060075 // - Alternatively, we could try to do findExactMatch() first, if not found,
76 // then do lookup().
Haowei Yuan78c84d12014-02-27 15:35:13 -060077 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(interest.getName());
Haowei Yuan78c84d12014-02-27 15:35:13 -060078 BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
79
Junxiao Shi9f7455b2014-04-07 21:02:16 -070080 const std::vector<shared_ptr<pit::Entry> >& pitEntries = nameTreeEntry->getPitEntries();
Haowei Yuan78c84d12014-02-27 15:35:13 -060081
82 // then check if this Interest is already in the PIT entries
Junxiao Shi9f7455b2014-04-07 21:02:16 -070083 std::vector<shared_ptr<pit::Entry> >::const_iterator it =
84 std::find_if(pitEntries.begin(), pitEntries.end(),
Alexander Afanasyevf6980282014-05-13 18:28:40 -070085 bind(&predicate_PitEntry_similar_Interest, _1, cref(interest)));
Haowei Yuan78c84d12014-02-27 15:35:13 -060086
87 if (it != pitEntries.end())
88 {
89 return std::make_pair(*it, false);
90 }
91 else
92 {
93 shared_ptr<pit::Entry> entry = make_shared<pit::Entry>(interest);
94 nameTreeEntry->insertPitEntry(entry);
95
96 // Increase m_nItmes only if we create a new PIT Entry
97 m_nItems++;
98
99 return std::make_pair(entry, true);
100 }
Junxiao Shicbba04c2014-01-26 14:21:22 -0700101}
102
103shared_ptr<pit::DataMatchResult>
104Pit::findAllDataMatches(const Data& data) const
105{
106 shared_ptr<pit::DataMatchResult> result = make_shared<pit::DataMatchResult>();
Haowei Yuan78c84d12014-02-27 15:35:13 -0600107
Haowei Yuane1079fc2014-03-08 14:41:25 -0600108 for (NameTree::const_iterator it =
109 m_nameTree.findAllMatches(data.getName(), &predicate_NameTreeEntry_hasPitEntry);
110 it != m_nameTree.end(); it++)
Haowei Yuan78c84d12014-02-27 15:35:13 -0600111 {
Junxiao Shi9f7455b2014-04-07 21:02:16 -0700112 const std::vector<shared_ptr<pit::Entry> >& pitEntries = it->getPitEntries();
Haowei Yuan78c84d12014-02-27 15:35:13 -0600113 for (size_t i = 0; i < pitEntries.size(); i++)
114 {
Junxiao Shi30d35992014-04-03 14:51:58 -0700115 if (pitEntries[i]->getInterest().matchesData(data))
Haowei Yuan78c84d12014-02-27 15:35:13 -0600116 result->push_back(pitEntries[i]);
117 }
Junxiao Shicbba04c2014-01-26 14:21:22 -0700118 }
Haowei Yuan78c84d12014-02-27 15:35:13 -0600119
Junxiao Shicbba04c2014-01-26 14:21:22 -0700120 return result;
121}
122
123void
Haowei Yuan78c84d12014-02-27 15:35:13 -0600124Pit::erase(shared_ptr<pit::Entry> pitEntry)
Junxiao Shicbba04c2014-01-26 14:21:22 -0700125{
Junxiao Shi9f7455b2014-04-07 21:02:16 -0700126 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(*pitEntry);
Haowei Yuan78c84d12014-02-27 15:35:13 -0600127 BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
128
Junxiao Shi9f7455b2014-04-07 21:02:16 -0700129 nameTreeEntry->erasePitEntry(pitEntry);
130 m_nameTree.eraseEntryIfEmpty(nameTreeEntry);
Haowei Yuan78c84d12014-02-27 15:35:13 -0600131
Junxiao Shi9f7455b2014-04-07 21:02:16 -0700132 --m_nItems;
Junxiao Shicbba04c2014-01-26 14:21:22 -0700133}
134
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800135} // namespace nfd