blob: 99a1bf91dfe9f84a4bb3e067d06e6b84971a3db0 [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 -070050shared_ptr<fib::Entry>
51Fib::findLongestPrefixMatch(const Name& prefix) const
52{
Junxiao Shi40631842014-03-01 13:52:37 -070053 shared_ptr<name_tree::Entry> nameTreeEntry =
54 m_nameTree.findLongestPrefixMatch(prefix, &predicate_NameTreeEntry_hasFibEntry);
55 if (static_cast<bool>(nameTreeEntry)) {
56 return nameTreeEntry->getFibEntry();
HangZhangad4afd12014-03-01 11:03:08 +080057 }
HangZhangcb4fc832014-03-11 16:57:11 +080058 return s_emptyEntry;
59}
60
61shared_ptr<fib::Entry>
62Fib::findLongestPrefixMatch(shared_ptr<name_tree::Entry> nameTreeEntry) const
63{
64 shared_ptr<fib::Entry> entry = nameTreeEntry->getFibEntry();
65 if (static_cast<bool>(entry))
66 return entry;
67 nameTreeEntry = m_nameTree.findLongestPrefixMatch(nameTreeEntry,
68 &predicate_NameTreeEntry_hasFibEntry);
69 if (static_cast<bool>(nameTreeEntry)) {
70 return nameTreeEntry->getFibEntry();
71 }
72 return s_emptyEntry;
Junxiao Shic1e12362014-01-24 20:03:26 -070073}
74
Steve DiBenedettod5f87932014-02-05 15:11:39 -070075shared_ptr<fib::Entry>
Junxiao Shidbe71732014-02-21 22:23:28 -070076Fib::findLongestPrefixMatch(const pit::Entry& pitEntry) const
77{
HangZhangcb4fc832014-03-11 16:57:11 +080078 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(pitEntry);
79
80 BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
81
82 return findLongestPrefixMatch(nameTreeEntry);
Junxiao Shidbe71732014-02-21 22:23:28 -070083}
84
85shared_ptr<fib::Entry>
86Fib::findLongestPrefixMatch(const measurements::Entry& measurementsEntry) const
87{
HangZhangcb4fc832014-03-11 16:57:11 +080088 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.get(measurementsEntry);
89
90 BOOST_ASSERT(static_cast<bool>(nameTreeEntry));
91
92 return findLongestPrefixMatch(nameTreeEntry);
Junxiao Shidbe71732014-02-21 22:23:28 -070093}
94
95shared_ptr<fib::Entry>
Steve DiBenedettod5f87932014-02-05 15:11:39 -070096Fib::findExactMatch(const Name& prefix) const
97{
HangZhangad4afd12014-03-01 11:03:08 +080098 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.findExactMatch(prefix);
99 if (static_cast<bool>(nameTreeEntry))
100 return nameTreeEntry->getFibEntry();
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700101 return shared_ptr<fib::Entry>();
102}
103
Junxiao Shi56a21bf2014-11-02 21:11:50 -0700104std::pair<shared_ptr<fib::Entry>, bool>
105Fib::insert(const Name& prefix)
106{
107 shared_ptr<name_tree::Entry> nameTreeEntry = m_nameTree.lookup(prefix);
108 shared_ptr<fib::Entry> entry = nameTreeEntry->getFibEntry();
109 if (static_cast<bool>(entry))
110 return std::make_pair(entry, false);
111 entry = make_shared<fib::Entry>(prefix);
112 nameTreeEntry->setFibEntry(entry);
113 ++m_nItems;
114 return std::make_pair(entry, true);
115}
116
Steve DiBenedettod5f87932014-02-05 15:11:39 -0700117void
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 Shi60607c72014-11-26 22:40:36 -0700146 shared_ptr<fib::Entry> toErase;
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700147
Junxiao Shi60607c72014-11-26 22:40:36 -0700148 auto&& enumerable = m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry);
149 for (const name_tree::Entry& nte : enumerable) {
150 if (toErase != nullptr) {
151 this->erase(*toErase);
152 toErase.reset();
153 }
Alexander Afanasyevb3033242014-08-04 11:09:05 -0700154
Junxiao Shi60607c72014-11-26 22:40:36 -0700155 shared_ptr<fib::Entry> entry = nte.getFibEntry();
Junxiao Shi40631842014-03-01 13:52:37 -0700156 entry->removeNextHop(face);
Junxiao Shiefceadc2014-03-09 18:52:57 -0700157 if (!entry->hasNextHops()) {
Junxiao Shi60607c72014-11-26 22:40:36 -0700158 toErase = entry;
159 // entry needs to be erased, but we must wait until next iteration
160 // to erase it because otherwise it would invalidate the iterator
Junxiao Shiefceadc2014-03-09 18:52:57 -0700161 }
HangZhangad4afd12014-03-01 11:03:08 +0800162 }
Junxiao Shi60607c72014-11-26 22:40:36 -0700163
164 if (toErase != nullptr) {
165 this->erase(*toErase);
166 }
Junxiao Shic1e12362014-01-24 20:03:26 -0700167}
168
HangZhang5d469422014-03-12 09:26:26 +0800169Fib::const_iterator
170Fib::begin() const
171{
Junxiao Shi60607c72014-11-26 22:40:36 -0700172 return const_iterator(m_nameTree.fullEnumerate(&predicate_NameTreeEntry_hasFibEntry).begin());
HangZhang5d469422014-03-12 09:26:26 +0800173}
174
Alexander Afanasyev18bbf812014-01-29 01:40:23 -0800175} // namespace nfd