blob: 3672b66f57aee09b1c501a77be1d32b1264970e5 [file] [log] [blame]
Junxiao Shic1e12362014-01-24 20:03:26 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2/**
Junxiao Shiee5a4442014-07-27 17:13:43 -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 * The University of Memphis
Alexander Afanasyev9bcbc7c2014-04-06 19:37:37 -070010 *
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/>.
Junxiao Shiee5a4442014-07-27 17:13:43 -070024 */
Junxiao Shic1e12362014-01-24 20:03:26 -070025
26#include "fib.hpp"
Junxiao Shidbe71732014-02-21 22:23:28 -070027#include "pit-entry.hpp"
28#include "measurements-entry.hpp"
Junxiao Shic1e12362014-01-24 20:03:26 -070029
Alexander Afanasyev18bbf812014-01-29 01:40:23 -080030namespace nfd {
Junxiao Shi40631842014-03-01 13:52:37 -070031
HangZhangcb4fc832014-03-11 16:57:11 +080032const shared_ptr<fib::Entry> Fib::s_emptyEntry = make_shared<fib::Entry>(Name());
Junxiao Shi40631842014-03-01 13:52:37 -070033
HangZhangad4afd12014-03-01 11:03:08 +080034Fib::Fib(NameTree& nameTree)
35 : m_nameTree(nameTree)
36 , m_nItems(0)
Junxiao Shic1e12362014-01-24 20:03:26 -070037{
Junxiao Shic1e12362014-01-24 20:03:26 -070038}
39
40Fib::~Fib()
41{
42}
43
Junxiao Shi40631842014-03-01 13:52:37 -070044static inline bool
45predicate_NameTreeEntry_hasFibEntry(const name_tree::Entry& entry)
46{
47 return static_cast<bool>(entry.getFibEntry());
48}
49
Junxiao Shic1e12362014-01-24 20:03:26 -070050std::pair<shared_ptr<fib::Entry>, bool>
51Fib::insert(const Name& prefix)
52{
HangZhangad4afd12014-03-01 11:03:08 +080053 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(prefix);
54 shared_ptr<fib::Entry> entry = nameTreeEntry->getFibEntry();
55 if (static_cast<bool>(entry))
56 return std::make_pair(entry, false);
57 entry = make_shared<fib::Entry>(prefix);
58 nameTreeEntry->setFibEntry(entry);
Junxiao Shiefceadc2014-03-09 18:52:57 -070059 ++m_nItems;
Junxiao Shic1e12362014-01-24 20:03:26 -070060 return std::make_pair(entry, true);
61}
62
Junxiao Shic1e12362014-01-24 20:03:26 -070063shared_ptr<fib::Entry>
64Fib::findLongestPrefixMatch(const Name& prefix) const
65{
Junxiao Shi40631842014-03-01 13:52:37 -070066 shared_ptr<name_tree::Entry> nameTreeEntry =
67 m_nameTree.findLongestPrefixMatch(prefix, &predicate_NameTreeEntry_hasFibEntry);
68 if (static_cast<bool>(nameTreeEntry)) {
69 return nameTreeEntry->getFibEntry();
HangZhangad4afd12014-03-01 11:03:08 +080070 }
HangZhangcb4fc832014-03-11 16:57:11 +080071 return s_emptyEntry;
72}
73
74shared_ptr<fib::Entry>
75Fib::findLongestPrefixMatch(shared_ptr<name_tree::Entry> nameTreeEntry) const
76{
77 shared_ptr<fib::Entry> entry = nameTreeEntry->getFibEntry();
78 if (static_cast<bool>(entry))
79 return entry;
80 nameTreeEntry = m_nameTree.findLongestPrefixMatch(nameTreeEntry,
81 &predicate_NameTreeEntry_hasFibEntry);
82 if (static_cast<bool>(nameTreeEntry)) {
83 return nameTreeEntry->getFibEntry();
84 }
85 return s_emptyEntry;
Junxiao Shic1e12362014-01-24 20:03:26 -070086}
87
Steve DiBenedettod5f87932014-02-05 15:11:39 -070088shared_ptr<fib::Entry>
Junxiao Shidbe71732014-02-21 22:23:28 -070089Fib::findLongestPrefixMatch(const pit::Entry& pitEntry) const
90{
HangZhangcb4fc832014-03-11 16:57:11 +080091 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(pitEntry);
92
93 BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
94
95 return findLongestPrefixMatch(nameTreeEntry);
Junxiao Shidbe71732014-02-21 22:23:28 -070096}
97
98shared_ptr<fib::Entry>
99Fib::findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const
100{
HangZhangcb4fc832014-03-11 16:57:11 +0800101 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(measurementsEntry);
102
103 BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
104
105 return findLongestPrefixMatch(nameTreeEntry);
Junxiao Shidbe71732014-02-21 22:23:28 -0700106}
107
108shared_ptr<fib::Entry>
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700109Fib::findExactMatch(const Name& prefix) const
110{
HangZhangad4afd12014-03-01 11:03:08 +0800111 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
112 if (static_cast<bool>(nameTreeEntry))
113 return nameTreeEntry->getFibEntry();
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700114 return shared_ptr<fib::Entry>();
115}
116
117void
Junxiao Shiee5a4442014-07-27 17:13:43 -0700118Fib::erase(shared_ptr<name_tree::Entry> nameTreeEntry)
119{
120 nameTreeEntry->setFibEntry(shared_ptr<fib::Entry>());
121 m_nameTree.eraseEntryIfEmpty(nameTreeEntry);
122 --m_nItems;
123}
124
125void
HangZhangad4afd12014-03-01 11:03:08 +0800126Fib::erase(const Name& prefix)
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700127{
HangZhangad4afd12014-03-01 11:03:08 +0800128 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
Junxiao Shiee5a4442014-07-27 17:13:43 -0700129 if (static_cast<bool>(nameTreeEntry)) {
130 this->erase(nameTreeEntry);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700131 }
132}
133
134void
135Fib::erase(const fib::Entry& entry)
136{
Junxiao Shiee5a4442014-07-27 17:13:43 -0700137 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(entry);
138 if (static_cast<bool>(nameTreeEntry)) {
139 this->erase(nameTreeEntry);
HangZhangad4afd12014-03-01 11:03:08 +0800140 }
Junxiao Shic1e12362014-01-24 20:03:26 -0700141}
142
143void
144Fib::removeNextHopFromAllEntries(shared_ptr<Face> face)
145{
Junxiao Shiefceadc2014-03-09 18:52:57 -0700146 for (NameTree::const_iterator it = m_nameTree.fullEnumerate(
147 &predicate_NameTreeEntry_hasFibEntry); it != m_nameTree.end(); ++it) {
Haowei Yuane1079fc2014-03-08 14:41:25 -0600148 shared_ptr<fib::Entry> entry = it->getFibEntry();
Junxiao Shi40631842014-03-01 13:52:37 -0700149 entry->removeNextHop(face);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700150 if (!entry->hasNextHops()) {
151 this->erase(*entry);
152 }
HangZhangad4afd12014-03-01 11:03:08 +0800153 }
Junxiao Shic1e12362014-01-24 20:03:26 -0700154}
155
HangZhang5d469422014-03-12 09:26:26 +0800156Fib::const_iterator
157Fib::begin() const
158{
159 return const_iterator(m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry));
160}
161
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800162} // namespace nfd