blob: b48d245531c6f4e67a39cf2e9d38f04274573eee [file] [log] [blame]
Alexander Afanasyevc169a812014-05-20 20:37:29 -04001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -07002/**
Alexander Afanasyev74633892015-02-08 18:08:46 -08003 * Copyright (c) 2013-2015 Regents of the University of California.
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -08004 *
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -07005 * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -08006 *
Alexander Afanasyevc169a812014-05-20 20:37:29 -04007 * ndn-cxx library is free software: you can redistribute it and/or modify it under the
8 * terms of the GNU Lesser General Public License as published by the Free Software
9 * Foundation, either version 3 of the License, or (at your option) any later version.
10 *
11 * ndn-cxx library is distributed in the hope that it will be useful, but WITHOUT ANY
12 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
13 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
14 *
15 * You should have received copies of the GNU General Public License and GNU Lesser
16 * General Public License along with ndn-cxx, e.g., in COPYING.md file. If not, see
17 * <http://www.gnu.org/licenses/>.
18 *
19 * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
Alexander Afanasyevdfa52c42014-04-24 21:10:11 -070020 *
21 * @author Alexander Afanasyev <http://lasr.cs.ucla.edu/afanasyev/index.html>
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -080022 */
23
Alexander Afanasyev09c613f2014-01-29 00:23:58 -080024#include "exclude.hpp"
Junxiao Shic2b8d242014-11-04 08:35:29 -070025#include "util/concepts.hpp"
Junxiao Shi7284a402014-09-12 13:42:16 -070026
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -070027namespace ndn {
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -080028
Junxiao Shic2b8d242014-11-04 08:35:29 -070029BOOST_CONCEPT_ASSERT((boost::EqualityComparable<Exclude>));
30BOOST_CONCEPT_ASSERT((WireEncodable<Exclude>));
31BOOST_CONCEPT_ASSERT((WireDecodable<Exclude>));
32static_assert(std::is_base_of<tlv::Error, Exclude::Error>::value,
33 "Exclude::Error must inherit from tlv::Error");
Junxiao Shi7284a402014-09-12 13:42:16 -070034
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -070035Exclude::Exclude()
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -080036{
37}
38
Junxiao Shi75203022014-09-11 10:01:50 -070039Exclude::Exclude(const Block& wire)
40{
41 wireDecode(wire);
42}
43
Alexander Afanasyev74633892015-02-08 18:08:46 -080044template<encoding::Tag TAG>
Junxiao Shi75203022014-09-11 10:01:50 -070045size_t
Alexander Afanasyev74633892015-02-08 18:08:46 -080046Exclude::wireEncode(EncodingImpl<TAG>& block) const
Junxiao Shi75203022014-09-11 10:01:50 -070047{
Junxiao Shi7284a402014-09-12 13:42:16 -070048 if (m_exclude.empty()) {
49 throw Error("Exclude filter cannot be empty");
50 }
51
Junxiao Shi75203022014-09-11 10:01:50 -070052 size_t totalLength = 0;
53
54 // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (NameComponent (Any)?)+
55 // Any ::= ANY-TYPE TLV-LENGTH(=0)
56
57 for (Exclude::const_iterator i = m_exclude.begin(); i != m_exclude.end(); i++)
58 {
59 if (i->second)
60 {
61 totalLength += prependBooleanBlock(block, tlv::Any);
62 }
63 if (!i->first.empty())
64 {
65 totalLength += i->first.wireEncode(block);
66 }
67 }
68
69 totalLength += block.prependVarNumber(totalLength);
70 totalLength += block.prependVarNumber(tlv::Exclude);
71 return totalLength;
72}
73
74template size_t
Alexander Afanasyev74633892015-02-08 18:08:46 -080075Exclude::wireEncode<encoding::EncoderTag>(EncodingImpl<encoding::EncoderTag>& block) const;
Junxiao Shi75203022014-09-11 10:01:50 -070076
77template size_t
Alexander Afanasyev74633892015-02-08 18:08:46 -080078Exclude::wireEncode<encoding::EstimatorTag>(EncodingImpl<encoding::EstimatorTag>& block) const;
Junxiao Shi75203022014-09-11 10:01:50 -070079
80const Block&
81Exclude::wireEncode() const
82{
83 if (m_wire.hasWire())
84 return m_wire;
85
86 EncodingEstimator estimator;
87 size_t estimatedSize = wireEncode(estimator);
88
89 EncodingBuffer buffer(estimatedSize, 0);
90 wireEncode(buffer);
91
92 m_wire = buffer.block();
93 return m_wire;
94}
95
96void
97Exclude::wireDecode(const Block& wire)
98{
Alexander Afanasyevba096052014-09-19 15:36:37 -070099 clear();
100
Junxiao Shi7284a402014-09-12 13:42:16 -0700101 if (wire.type() != tlv::Exclude)
102 throw tlv::Error("Unexpected TLV type when decoding Exclude");
103
Junxiao Shi75203022014-09-11 10:01:50 -0700104 m_wire = wire;
105 m_wire.parse();
106
Junxiao Shi7284a402014-09-12 13:42:16 -0700107 if (m_wire.elements_size() == 0) {
108 throw Error("Exclude element cannot be empty");
109 }
110
Junxiao Shi75203022014-09-11 10:01:50 -0700111 // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (NameComponent (Any)?)+
112 // Any ::= ANY-TYPE TLV-LENGTH(=0)
113
114 Block::element_const_iterator i = m_wire.elements_begin();
115 if (i->type() == tlv::Any)
116 {
117 appendExclude(name::Component(), true);
118 ++i;
119 }
120
121 while (i != m_wire.elements_end())
122 {
123 if (i->type() != tlv::NameComponent)
124 throw Error("Incorrect format of Exclude filter");
125
126 name::Component excludedComponent(i->value(), i->value_size());
127 ++i;
128
129 if (i != m_wire.elements_end())
130 {
131 if (i->type() == tlv::Any)
132 {
133 appendExclude(excludedComponent, true);
134 ++i;
135 }
136 else
137 {
138 appendExclude(excludedComponent, false);
139 }
140 }
141 else
142 {
143 appendExclude(excludedComponent, false);
144 }
145 }
146}
147
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800148// example: ANY /b /d ANY /f
149//
150// ordered in map as:
151//
152// /f (false); /d (true); /b (false); / (true)
153//
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700154// lower_bound(/) -> / (true) <-- excluded (equal)
155// lower_bound(/a) -> / (true) <-- excluded (any)
156// lower_bound(/b) -> /b (false) <--- excluded (equal)
157// lower_bound(/c) -> /b (false) <--- not excluded (not equal and no ANY)
158// lower_bound(/d) -> /d (true) <- excluded
159// lower_bound(/e) -> /d (true) <- excluded
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800160bool
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700161Exclude::isExcluded(const name::Component& comp) const
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800162{
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700163 const_iterator lowerBound = m_exclude.lower_bound(comp);
164 if (lowerBound == end())
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800165 return false;
166
167 if (lowerBound->second)
168 return true;
169 else
170 return lowerBound->first == comp;
171
172 return false;
173}
174
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700175Exclude&
176Exclude::excludeOne(const name::Component& comp)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800177{
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700178 if (!isExcluded(comp))
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800179 {
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700180 m_exclude.insert(std::make_pair(comp, false));
Alexander Afanasyevba096052014-09-19 15:36:37 -0700181 m_wire.reset();
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800182 }
183 return *this;
184}
185
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800186// example: ANY /b0 /d0 ANY /f0
187//
188// ordered in map as:
189//
190// /f0 (false); /d0 (true); /b0 (false); / (true)
191//
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700192// lower_bound(/) -> / (true) <-- excluded (equal)
193// lower_bound(/a0) -> / (true) <-- excluded (any)
194// lower_bound(/b0) -> /b0 (false) <--- excluded (equal)
195// lower_bound(/c0) -> /b0 (false) <--- not excluded (not equal and no ANY)
196// lower_bound(/d0) -> /d0 (true) <- excluded
197// lower_bound(/e0) -> /d0 (true) <- excluded
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800198
199
200// examples with desired outcomes
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700201// excludeRange(/, /f0) -> ANY /f0
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800202// /f0 (false); / (true)
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700203// excludeRange(/, /f1) -> ANY /f1
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800204// /f1 (false); / (true)
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700205// excludeRange(/a0, /e0) -> ANY /f0
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800206// /f0 (false); / (true)
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700207// excludeRange(/a0, /e0) -> ANY /f0
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800208// /f0 (false); / (true)
209
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700210// excludeRange(/b1, /c0) -> ANY /b0 /b1 ANY /c0 /d0 ANY /f0
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800211// /f0 (false); /d0 (true); /c0 (false); /b1 (true); /b0 (false); / (true)
212
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700213Exclude&
214Exclude::excludeRange(const name::Component& from, const name::Component& to)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800215{
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700216 if (from >= to) {
Alexander Afanasyev9c578182014-05-14 17:28:28 -0700217 throw Error("Invalid exclude range [" + from.toUri() + ", " + to.toUri() + "] "
218 "(for single name exclude use Exclude::excludeOne)");
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700219 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800220
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700221 iterator newFrom = m_exclude.lower_bound(from);
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700222 if (newFrom == end() || !newFrom->second /*without ANY*/) {
223 std::pair<iterator, bool> fromResult = m_exclude.insert(std::make_pair(from, true));
224 newFrom = fromResult.first;
225 if (!fromResult.second) {
226 // this means that the lower bound is equal to the item itself. So, just update ANY flag
227 newFrom->second = true;
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800228 }
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700229 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800230 // else
231 // nothing special if start of the range already exists with ANY flag set
232
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700233 iterator newTo = m_exclude.lower_bound(to); // !newTo cannot be end()
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700234 if (newTo == newFrom || !newTo->second) {
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700235 std::pair<iterator, bool> toResult = m_exclude.insert(std::make_pair(to, false));
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800236 newTo = toResult.first;
237 ++ newTo;
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700238 }
239 // else
240 // nothing to do really
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800241
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700242 m_exclude.erase(newTo, newFrom); // remove any intermediate node, since all of the are excluded
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800243
Alexander Afanasyevba096052014-09-19 15:36:37 -0700244 m_wire.reset();
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800245 return *this;
246}
247
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700248Exclude&
249Exclude::excludeAfter(const name::Component& from)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800250{
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700251 iterator newFrom = m_exclude.lower_bound(from);
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700252 if (newFrom == end() || !newFrom->second /*without ANY*/) {
253 std::pair<iterator, bool> fromResult = m_exclude.insert(std::make_pair(from, true));
254 newFrom = fromResult.first;
255 if (!fromResult.second) {
256 // this means that the lower bound is equal to the item itself. So, just update ANY flag
257 newFrom->second = true;
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800258 }
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700259 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800260 // else
261 // nothing special if start of the range already exists with ANY flag set
262
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700263 if (newFrom != m_exclude.begin()) {
264 // remove any intermediate node, since all of the are excluded
265 m_exclude.erase(m_exclude.begin(), newFrom);
266 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800267
Alexander Afanasyevba096052014-09-19 15:36:37 -0700268 m_wire.reset();
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800269 return *this;
270}
271
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800272std::ostream&
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700273operator<<(std::ostream& os, const Exclude& exclude)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800274{
275 bool empty = true;
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700276 for (Exclude::const_reverse_iterator i = exclude.rbegin(); i != exclude.rend(); i++) {
277 if (!i->first.empty()) {
278 if (!empty) os << ",";
Alexander Afanasyev9c578182014-05-14 17:28:28 -0700279 os << i->first.toUri();
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700280 empty = false;
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800281 }
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700282 if (i->second) {
283 if (!empty) os << ",";
284 os << "*";
285 empty = false;
286 }
287 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800288 return os;
289}
290
Alexander Afanasyevba096052014-09-19 15:36:37 -0700291std::string
292Exclude::toUri() const
293{
294 std::ostringstream os;
295 os << *this;
296 return os.str();
297}
298
299bool
300Exclude::operator==(const Exclude& other) const
301{
302 if (empty() && other.empty())
303 return true;
304 if (empty() || other.empty())
305 return false;
306
307 return wireEncode() == other.wireEncode();
308}
309
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700310} // namespace ndn