blob: 0f339e03d4d0728f6ea5a62d9b850e39c18d3868 [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/**
Davide Pesaventocf415762017-02-25 23:46:47 -05003 * Copyright (c) 2013-2017 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"
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -070025#include "encoding/block-helpers.hpp"
Junxiao Shi7284a402014-09-12 13:42:16 -070026
Davide Pesaventocf415762017-02-25 23:46:47 -050027#include <boost/range/adaptor/reversed.hpp>
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -070028
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -070029namespace ndn {
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -080030
Junxiao Shidf4b24e2016-07-14 21:41:43 +000031Exclude::ExcludeComponent::ExcludeComponent(const name::Component& component1)
32 : isNegInf(false)
33 , component(component1)
34{
35}
36
37Exclude::ExcludeComponent::ExcludeComponent(bool isNegInf1)
38 : isNegInf(true)
39{
40 BOOST_ASSERT(isNegInf1 == true);
41}
42
43bool
Junxiao Shib80e9472016-07-20 13:45:24 +000044operator==(const Exclude::ExcludeComponent& a, const Exclude::ExcludeComponent& b)
45{
46 return (a.isNegInf && b.isNegInf) ||
47 (a.isNegInf == b.isNegInf && a.component == b.component);
48}
49
50bool
Junxiao Shidf4b24e2016-07-14 21:41:43 +000051operator>(const Exclude::ExcludeComponent& a, const Exclude::ExcludeComponent& b)
52{
53 return a.isNegInf < b.isNegInf ||
54 (a.isNegInf == b.isNegInf && a.component > b.component);
55}
56
Junxiao Shib80e9472016-07-20 13:45:24 +000057bool
58Exclude::Range::operator==(const Exclude::Range& other) const
59{
60 return this->fromInfinity == other.fromInfinity && this->toInfinity == other.toInfinity &&
61 (this->fromInfinity || this->from == other.from) &&
62 (this->toInfinity || this->to == other.to);
63}
64
65std::ostream&
66operator<<(std::ostream& os, const Exclude::Range& range)
67{
68 if (range.isSingular()) {
69 return os << '{' << range.from << '}';
70 }
71
72 if (range.fromInfinity) {
73 os << "(-∞";
74 }
75 else {
76 os << '[' << range.from;
77 }
78
79 os << ",";
80
81 if (range.toInfinity) {
82 os << "+∞)";
83 }
84 else {
85 os << range.to << ']';
86 }
87
88 return os;
89}
90
Junxiao Shic2b8d242014-11-04 08:35:29 -070091BOOST_CONCEPT_ASSERT((boost::EqualityComparable<Exclude>));
92BOOST_CONCEPT_ASSERT((WireEncodable<Exclude>));
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -070093BOOST_CONCEPT_ASSERT((WireEncodableWithEncodingBuffer<Exclude>));
Junxiao Shic2b8d242014-11-04 08:35:29 -070094BOOST_CONCEPT_ASSERT((WireDecodable<Exclude>));
95static_assert(std::is_base_of<tlv::Error, Exclude::Error>::value,
96 "Exclude::Error must inherit from tlv::Error");
Junxiao Shi7284a402014-09-12 13:42:16 -070097
Junxiao Shidf4b24e2016-07-14 21:41:43 +000098Exclude::Exclude() = default;
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -080099
Junxiao Shi75203022014-09-11 10:01:50 -0700100Exclude::Exclude(const Block& wire)
101{
102 wireDecode(wire);
103}
104
Alexander Afanasyev74633892015-02-08 18:08:46 -0800105template<encoding::Tag TAG>
Junxiao Shi75203022014-09-11 10:01:50 -0700106size_t
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -0700107Exclude::wireEncode(EncodingImpl<TAG>& encoder) const
Junxiao Shi75203022014-09-11 10:01:50 -0700108{
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000109 if (m_entries.empty()) {
110 BOOST_THROW_EXCEPTION(Error("cannot encode empty Exclude selector"));
Junxiao Shi7284a402014-09-12 13:42:16 -0700111 }
112
Junxiao Shi75203022014-09-11 10:01:50 -0700113 size_t totalLength = 0;
114
115 // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (NameComponent (Any)?)+
116 // Any ::= ANY-TYPE TLV-LENGTH(=0)
117
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000118 for (const Entry& entry : m_entries) {
119 if (entry.second) {
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -0700120 totalLength += prependEmptyBlock(encoder, tlv::Any);
Junxiao Shi75203022014-09-11 10:01:50 -0700121 }
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000122 if (!entry.first.isNegInf) {
123 totalLength += entry.first.component.wireEncode(encoder);
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700124 }
125 }
Junxiao Shi75203022014-09-11 10:01:50 -0700126
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -0700127 totalLength += encoder.prependVarNumber(totalLength);
128 totalLength += encoder.prependVarNumber(tlv::Exclude);
Junxiao Shi75203022014-09-11 10:01:50 -0700129 return totalLength;
130}
131
132template size_t
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -0700133Exclude::wireEncode<encoding::EncoderTag>(EncodingImpl<encoding::EncoderTag>& encoder) const;
Junxiao Shi75203022014-09-11 10:01:50 -0700134
135template size_t
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -0700136Exclude::wireEncode<encoding::EstimatorTag>(EncodingImpl<encoding::EstimatorTag>& encoder) const;
Junxiao Shi75203022014-09-11 10:01:50 -0700137
138const Block&
139Exclude::wireEncode() const
140{
141 if (m_wire.hasWire())
142 return m_wire;
143
144 EncodingEstimator estimator;
145 size_t estimatedSize = wireEncode(estimator);
146
147 EncodingBuffer buffer(estimatedSize, 0);
148 wireEncode(buffer);
149
150 m_wire = buffer.block();
151 return m_wire;
152}
153
154void
155Exclude::wireDecode(const Block& wire)
156{
Alexander Afanasyevba096052014-09-19 15:36:37 -0700157 clear();
158
Junxiao Shi7284a402014-09-12 13:42:16 -0700159 if (wire.type() != tlv::Exclude)
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700160 BOOST_THROW_EXCEPTION(tlv::Error("Unexpected TLV type when decoding Exclude"));
Junxiao Shi7284a402014-09-12 13:42:16 -0700161
Junxiao Shi75203022014-09-11 10:01:50 -0700162 m_wire = wire;
163 m_wire.parse();
164
Junxiao Shi7284a402014-09-12 13:42:16 -0700165 if (m_wire.elements_size() == 0) {
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700166 BOOST_THROW_EXCEPTION(Error("Exclude element cannot be empty"));
Junxiao Shi7284a402014-09-12 13:42:16 -0700167 }
168
Junxiao Shi75203022014-09-11 10:01:50 -0700169 // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (NameComponent (Any)?)+
170 // Any ::= ANY-TYPE TLV-LENGTH(=0)
171
172 Block::element_const_iterator i = m_wire.elements_begin();
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700173 if (i->type() == tlv::Any) {
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000174 this->appendEntry(true, true);
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700175 ++i;
176 }
177
178 while (i != m_wire.elements_end()) {
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000179 name::Component component;
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700180 try {
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000181 component = name::Component(*i);
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700182 }
183 catch (const name::Component::Error&) {
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700184 BOOST_THROW_EXCEPTION(Error("Incorrect format of Exclude filter"));
Junxiao Shi75203022014-09-11 10:01:50 -0700185 }
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700186 ++i;
Junxiao Shi75203022014-09-11 10:01:50 -0700187
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000188 if (i != m_wire.elements_end() && i->type() == tlv::Any) {
189 this->appendEntry(component, true);
190 ++i;
Junxiao Shi75203022014-09-11 10:01:50 -0700191 }
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700192 else {
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000193 this->appendEntry(component, false);
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700194 }
195 }
Junxiao Shi75203022014-09-11 10:01:50 -0700196}
197
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000198template<typename T>
199void
200Exclude::appendEntry(const T& component, bool hasAny)
201{
202 m_entries.emplace_hint(m_entries.begin(), std::piecewise_construct,
203 std::forward_as_tuple(component),
204 std::forward_as_tuple(hasAny));
205}
206
207// example: ANY "b" "d" ANY "f"
208// ordered in map as: "f" (false); "d" (true); "b" (false); -Inf (true)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800209//
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000210// lower_bound("") -> -Inf (true) <-- excluded (ANY)
211// lower_bound("a") -> -Inf (true) <-- excluded (ANY)
212// lower_bound("b") -> "b" (false) <--- excluded (equal)
213// lower_bound("c") -> "b" (false) <--- not excluded (not equal and no ANY)
214// lower_bound("d") -> "d" (true) <- excluded
215// lower_bound("e") -> "d" (true) <- excluded
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800216bool
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700217Exclude::isExcluded(const name::Component& comp) const
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800218{
Junxiao Shib80e9472016-07-20 13:45:24 +0000219 ExcludeMap::const_iterator lb = m_entries.lower_bound(comp);
220 return lb != m_entries.end() && // if false, comp is less than the first excluded component
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000221 (lb->second || // comp matches an ANY range
222 (!lb->first.isNegInf && lb->first.component == comp)); // comp equals an exact excluded component
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800223}
224
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700225Exclude&
226Exclude::excludeOne(const name::Component& comp)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800227{
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700228 if (!isExcluded(comp)) {
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000229 this->appendEntry(comp, false);
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700230 m_wire.reset();
231 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800232 return *this;
233}
234
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000235Exclude&
236Exclude::excludeBefore(const name::Component& to)
237{
238 return excludeRange(ExcludeComponent(true), to);
239}
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800240
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700241Exclude&
242Exclude::excludeRange(const name::Component& from, const name::Component& to)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800243{
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000244 return excludeRange(ExcludeComponent(from), to);
245}
246
247// example: ANY "b" "d" ANY "g"
248// ordered in map as: "f" (false); "d" (true); "b" (false); -Inf (true)
249// possible sequence of operations:
250// excludeBefore("a") -> excludeRange(-Inf, "a") -> ANY "a"
251// "a" (false); -Inf (true)
252// excludeBefore("b") -> excludeRange(-Inf, "b") -> ANY "b"
253// "b" (false); -Inf (true)
254// excludeRange("e", "g") -> ANY "b" "e" ANY "g"
255// "g" (false); "e" (true); "b" (false); -Inf (true)
256// excludeRange("d", "f") -> ANY "b" "d" ANY "g"
257// "g" (false); "d" (true); "b" (false); -Inf (true)
258
259Exclude&
260Exclude::excludeRange(const ExcludeComponent& from, const name::Component& to)
261{
262 if (!from.isNegInf && from.component >= to) {
263 BOOST_THROW_EXCEPTION(Error("Invalid exclude range [" + from.component.toUri() + ", " + to.toUri() + "] "
Spyridon Mastorakis0d2ed2e2015-07-27 19:09:12 -0700264 "(for single name exclude use Exclude::excludeOne)"));
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700265 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800266
Junxiao Shib80e9472016-07-20 13:45:24 +0000267 ExcludeMap::iterator newFrom = m_entries.lower_bound(from);
268 if (newFrom == m_entries.end() || !newFrom->second /*without ANY*/) {
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000269 bool isNewEntry = false;
270 std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
271 if (!isNewEntry) {
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700272 // this means that the lower bound is equal to the item itself. So, just update ANY flag
273 newFrom->second = true;
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800274 }
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700275 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800276 // else
277 // nothing special if start of the range already exists with ANY flag set
278
Junxiao Shib80e9472016-07-20 13:45:24 +0000279 ExcludeMap::iterator newTo = m_entries.lower_bound(to);
280 BOOST_ASSERT(newTo != m_entries.end());
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700281 if (newTo == newFrom || !newTo->second) {
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000282 newTo = m_entries.emplace_hint(newTo, to, false);
283 ++newTo;
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700284 }
285 // else
286 // nothing to do really
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800287
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000288 // remove any intermediate entries, since all of the are excluded
289 m_entries.erase(newTo, newFrom);
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800290
Alexander Afanasyevba096052014-09-19 15:36:37 -0700291 m_wire.reset();
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800292 return *this;
293}
294
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700295Exclude&
296Exclude::excludeAfter(const name::Component& from)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800297{
Junxiao Shib80e9472016-07-20 13:45:24 +0000298 ExcludeMap::iterator newFrom = m_entries.lower_bound(from);
299 if (newFrom == m_entries.end() || !newFrom->second /*without ANY*/) {
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000300 bool isNewEntry = false;
301 std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
302 if (!isNewEntry) {
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700303 // this means that the lower bound is equal to the item itself. So, just update ANY flag
304 newFrom->second = true;
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800305 }
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700306 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800307 // else
308 // nothing special if start of the range already exists with ANY flag set
309
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000310 // remove any intermediate node, since all of the are excluded
311 m_entries.erase(m_entries.begin(), newFrom);
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800312
Alexander Afanasyevba096052014-09-19 15:36:37 -0700313 m_wire.reset();
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800314 return *this;
315}
316
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800317std::ostream&
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700318operator<<(std::ostream& os, const Exclude& exclude)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800319{
Davide Pesaventocf415762017-02-25 23:46:47 -0500320 auto join = make_ostream_joiner(os, ',');
Junxiao Shib80e9472016-07-20 13:45:24 +0000321 for (const Exclude::Entry& entry : exclude.m_entries | boost::adaptors::reversed) {
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000322 if (!entry.first.isNegInf) {
Davide Pesaventocf415762017-02-25 23:46:47 -0500323 join = entry.first.component;
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800324 }
Junxiao Shidf4b24e2016-07-14 21:41:43 +0000325 if (entry.second) {
Davide Pesaventocf415762017-02-25 23:46:47 -0500326 join = '*';
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700327 }
328 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800329 return os;
330}
331
Alexander Afanasyevba096052014-09-19 15:36:37 -0700332std::string
333Exclude::toUri() const
334{
335 std::ostringstream os;
336 os << *this;
337 return os.str();
338}
339
340bool
341Exclude::operator==(const Exclude& other) const
342{
Junxiao Shib80e9472016-07-20 13:45:24 +0000343 return m_entries == other.m_entries;
344}
Alexander Afanasyevba096052014-09-19 15:36:37 -0700345
Junxiao Shib80e9472016-07-20 13:45:24 +0000346size_t
347Exclude::size() const
348{
349 return std::distance(begin(), end());
350}
351
352void
353Exclude::clear()
354{
355 m_entries.clear();
356 m_wire.reset();
357}
358
359Exclude::const_iterator::const_iterator(ExcludeMap::const_reverse_iterator it,
360 ExcludeMap::const_reverse_iterator rend)
361 : m_it(it)
362 , m_rend(rend)
363{
364 this->update();
365}
366
367Exclude::const_iterator&
368Exclude::const_iterator::operator++()
369{
370 bool wasInRange = m_it->second;
371 ++m_it;
372 if (wasInRange && m_it != m_rend) {
373 BOOST_ASSERT(m_it->second == false); // consecutive ranges should have been combined
374 ++m_it; // skip over range high limit
375 }
376 this->update();
377 return *this;
378}
379
380Exclude::const_iterator
381Exclude::const_iterator::operator++(int)
382{
383 const_iterator i = *this;
384 this->operator++();
385 return i;
386}
387
388void
389Exclude::const_iterator::update()
390{
391 if (m_it == m_rend) {
392 return;
393 }
394
395 if (m_it->second) { // range
396 if (m_it->first.isNegInf) {
397 m_range.fromInfinity = true;
398 }
399 else {
400 m_range.fromInfinity = false;
401 m_range.from = m_it->first.component;
402 }
403
404 auto next = std::next(m_it);
405 if (next == m_rend) {
406 m_range.toInfinity = true;
407 }
408 else {
409 m_range.toInfinity = false;
410 m_range.to = next->first.component;
411 }
412 }
413 else { // single
414 BOOST_ASSERT(!m_it->first.isNegInf);
415 m_range.fromInfinity = m_range.toInfinity = false;
416 m_range.from = m_range.to = m_it->first.component;
417 }
Alexander Afanasyevba096052014-09-19 15:36:37 -0700418}
419
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700420} // namespace ndn