NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.5: NDN, CCN, CCNx, content centric networks
API Documentation
exclude.cpp
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2013-2018 Regents of the University of California.
4  *
5  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
6  *
7  * 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.
20  *
21  * @author Alexander Afanasyev <http://lasr.cs.ucla.edu/afanasyev/index.html>
22  */
23 
24 #include "ndn-cxx/exclude.hpp"
26 
27 #include <boost/range/adaptor/reversed.hpp>
28 #include <sstream>
29 
30 namespace ndn {
31 
33  : isNegInf(false)
34  , component(component1)
35 {
36 }
37 
39  : isNegInf(true)
40 {
41  BOOST_ASSERT(isNegInf1 == true);
42 }
43 
44 bool
46 {
47  return (a.isNegInf && b.isNegInf) ||
48  (a.isNegInf == b.isNegInf && a.component == b.component);
49 }
50 
51 bool
53 {
54  return a.isNegInf < b.isNegInf ||
55  (a.isNegInf == b.isNegInf && a.component > b.component);
56 }
57 
59  : fromInfinity(false)
60  , toInfinity(false)
61 {
62 }
63 
64 Exclude::Range::Range(bool fromInfinity, const name::Component& from, bool toInfinity, const name::Component& to)
65  : fromInfinity(fromInfinity)
66  , from(from)
67  , toInfinity(toInfinity)
68  , to(to)
69 {
70 }
71 
72 bool
74 {
75  return this->fromInfinity == other.fromInfinity && this->toInfinity == other.toInfinity &&
76  (this->fromInfinity || this->from == other.from) &&
77  (this->toInfinity || this->to == other.to);
78 }
79 
80 std::ostream&
81 operator<<(std::ostream& os, const Exclude::Range& range)
82 {
83  if (range.isSingular()) {
84  return os << '{' << range.from << '}';
85  }
86 
87  if (range.fromInfinity) {
88  os << "(-∞";
89  }
90  else {
91  os << '[' << range.from;
92  }
93 
94  os << ",";
95 
96  if (range.toInfinity) {
97  os << "+∞)";
98  }
99  else {
100  os << range.to << ']';
101  }
102 
103  return os;
104 }
105 
106 BOOST_CONCEPT_ASSERT((boost::EqualityComparable<Exclude>));
107 BOOST_CONCEPT_ASSERT((WireEncodable<Exclude>));
109 BOOST_CONCEPT_ASSERT((WireDecodable<Exclude>));
110 static_assert(std::is_base_of<tlv::Error, Exclude::Error>::value,
111  "Exclude::Error must inherit from tlv::Error");
112 
113 Exclude::Exclude() = default;
114 
116 {
117  wireDecode(wire);
118 }
119 
120 template<encoding::Tag TAG>
121 size_t
123 {
124  if (m_entries.empty()) {
125  BOOST_THROW_EXCEPTION(Error("cannot encode empty Exclude selector"));
126  }
127 
128  size_t totalLength = 0;
129 
130  // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (GenericNameComponent (Any)?)+
131  // Any ::= ANY-TYPE TLV-LENGTH(=0)
132 
133  for (const Entry& entry : m_entries) {
134  if (entry.second) {
135  totalLength += prependEmptyBlock(encoder, tlv::Any);
136  }
137  if (!entry.first.isNegInf) {
138  totalLength += entry.first.component.wireEncode(encoder);
139  }
140  }
141 
142  totalLength += encoder.prependVarNumber(totalLength);
143  totalLength += encoder.prependVarNumber(tlv::Exclude);
144  return totalLength;
145 }
146 
148 
149 const Block&
151 {
152  if (m_wire.hasWire())
153  return m_wire;
154 
155  EncodingEstimator estimator;
156  size_t estimatedSize = wireEncode(estimator);
157 
158  EncodingBuffer buffer(estimatedSize, 0);
159  wireEncode(buffer);
160 
161  m_wire = buffer.block();
162  return m_wire;
163 }
164 
165 void
167 {
168  clear();
169 
170  if (wire.type() != tlv::Exclude)
171  BOOST_THROW_EXCEPTION(tlv::Error("Unexpected TLV type when decoding Exclude"));
172 
173  m_wire = wire;
174  m_wire.parse();
175 
176  if (m_wire.elements_size() == 0) {
177  BOOST_THROW_EXCEPTION(Error("Exclude element cannot be empty"));
178  }
179 
180  // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (GenericNameComponent (Any)?)+
181  // Any ::= ANY-TYPE TLV-LENGTH(=0)
182 
184  if (i->type() == tlv::Any) {
185  this->appendEntry(true, true);
186  ++i;
187  }
188 
189  while (i != m_wire.elements_end()) {
190  name::Component component;
191  try {
192  component = name::Component(*i);
193  }
194  catch (const name::Component::Error&) {
195  BOOST_THROW_EXCEPTION(Error("Incorrect format of Exclude filter"));
196  }
197  if (!component.isGeneric() && !component.isImplicitSha256Digest()) {
198  BOOST_THROW_EXCEPTION(Error("Excluded component must be generic or ImplicitSha256Digest"));
199  }
200  ++i;
201 
202  if (i != m_wire.elements_end() && i->type() == tlv::Any) {
203  this->appendEntry(component, true);
204  ++i;
205  }
206  else {
207  this->appendEntry(component, false);
208  }
209  }
210 }
211 
212 template<typename T>
213 void
214 Exclude::appendEntry(const T& component, bool hasAny)
215 {
216  m_entries.emplace_hint(m_entries.begin(), std::piecewise_construct,
217  std::forward_as_tuple(component),
218  std::forward_as_tuple(hasAny));
219 }
220 
221 // example: ANY "b" "d" ANY "f"
222 // ordered in map as: "f" (false); "d" (true); "b" (false); -Inf (true)
223 //
224 // lower_bound("") -> -Inf (true) <-- excluded (ANY)
225 // lower_bound("a") -> -Inf (true) <-- excluded (ANY)
226 // lower_bound("b") -> "b" (false) <--- excluded (equal)
227 // lower_bound("c") -> "b" (false) <--- not excluded (not equal and no ANY)
228 // lower_bound("d") -> "d" (true) <- excluded
229 // lower_bound("e") -> "d" (true) <- excluded
230 bool
232 {
233  ExcludeMap::const_iterator lb = m_entries.lower_bound(comp);
234  return lb != m_entries.end() && // if false, comp is less than the first excluded component
235  (lb->second || // comp matches an ANY range
236  (!lb->first.isNegInf && lb->first.component == comp)); // comp equals an exact excluded component
237 }
238 
239 Exclude&
241 {
242  if (!isExcluded(comp)) {
243  this->appendEntry(comp, false);
244  m_wire.reset();
245  }
246  return *this;
247 }
248 
249 Exclude&
251 {
252  return excludeRange(ExcludeComponent(true), to);
253 }
254 
255 Exclude&
257 {
258  return excludeRange(ExcludeComponent(from), to);
259 }
260 
261 // example: ANY "b" "d" ANY "g"
262 // ordered in map as: "f" (false); "d" (true); "b" (false); -Inf (true)
263 // possible sequence of operations:
264 // excludeBefore("a") -> excludeRange(-Inf, "a") -> ANY "a"
265 // "a" (false); -Inf (true)
266 // excludeBefore("b") -> excludeRange(-Inf, "b") -> ANY "b"
267 // "b" (false); -Inf (true)
268 // excludeRange("e", "g") -> ANY "b" "e" ANY "g"
269 // "g" (false); "e" (true); "b" (false); -Inf (true)
270 // excludeRange("d", "f") -> ANY "b" "d" ANY "g"
271 // "g" (false); "d" (true); "b" (false); -Inf (true)
272 
273 Exclude&
274 Exclude::excludeRange(const ExcludeComponent& from, const name::Component& to)
275 {
276  if (!from.isNegInf && from.component >= to) {
277  BOOST_THROW_EXCEPTION(Error("Invalid exclude range [" + from.component.toUri() + ", " + to.toUri() + "] "
278  "(for single name exclude use Exclude::excludeOne)"));
279  }
280 
281  ExcludeMap::iterator newFrom = m_entries.lower_bound(from);
282  if (newFrom == m_entries.end() || !newFrom->second /*without ANY*/) {
283  bool isNewEntry = false;
284  std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
285  if (!isNewEntry) {
286  // this means that the lower bound is equal to the item itself. So, just update ANY flag
287  newFrom->second = true;
288  }
289  }
290  // else
291  // nothing special if start of the range already exists with ANY flag set
292 
293  ExcludeMap::iterator newTo = m_entries.lower_bound(to);
294  BOOST_ASSERT(newTo != m_entries.end());
295  if (newTo == newFrom || !newTo->second) {
296  newTo = m_entries.emplace_hint(newTo, to, false);
297  ++newTo;
298  }
299  // else
300  // nothing to do really
301 
302  // remove any intermediate entries, since all of the are excluded
303  m_entries.erase(newTo, newFrom);
304 
305  m_wire.reset();
306  return *this;
307 }
308 
309 Exclude&
311 {
312  ExcludeMap::iterator newFrom = m_entries.lower_bound(from);
313  if (newFrom == m_entries.end() || !newFrom->second /*without ANY*/) {
314  bool isNewEntry = false;
315  std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
316  if (!isNewEntry) {
317  // this means that the lower bound is equal to the item itself. So, just update ANY flag
318  newFrom->second = true;
319  }
320  }
321  // else
322  // nothing special if start of the range already exists with ANY flag set
323 
324  // remove any intermediate node, since all of the are excluded
325  m_entries.erase(m_entries.begin(), newFrom);
326 
327  m_wire.reset();
328  return *this;
329 }
330 
331 std::ostream&
332 operator<<(std::ostream& os, const Exclude& exclude)
333 {
334  auto join = make_ostream_joiner(os, ',');
335  for (const Exclude::Entry& entry : exclude.m_entries | boost::adaptors::reversed) {
336  if (!entry.first.isNegInf) {
337  join = entry.first.component;
338  }
339  if (entry.second) {
340  join = '*';
341  }
342  }
343  return os;
344 }
345 
346 std::string
348 {
349  std::ostringstream os;
350  os << *this;
351  return os.str();
352 }
353 
354 bool
355 Exclude::operator==(const Exclude& other) const
356 {
357  return m_entries == other.m_entries;
358 }
359 
360 size_t
362 {
363  return std::distance(begin(), end());
364 }
365 
366 void
368 {
369  m_entries.clear();
370  m_wire.reset();
371 }
372 
373 Exclude::const_iterator::const_iterator(ExcludeMap::const_reverse_iterator it,
374  ExcludeMap::const_reverse_iterator rend)
375  : m_it(it)
376  , m_rend(rend)
377 {
378  this->update();
379 }
380 
383 {
384  bool wasInRange = m_it->second;
385  ++m_it;
386  if (wasInRange && m_it != m_rend) {
387  BOOST_ASSERT(m_it->second == false); // consecutive ranges should have been combined
388  ++m_it; // skip over range high limit
389  }
390  this->update();
391  return *this;
392 }
393 
396 {
397  const_iterator i = *this;
398  this->operator++();
399  return i;
400 }
401 
402 void
403 Exclude::const_iterator::update()
404 {
405  if (m_it == m_rend) {
406  return;
407  }
408 
409  if (m_it->second) { // range
410  if (m_it->first.isNegInf) {
411  m_range.fromInfinity = true;
412  }
413  else {
414  m_range.fromInfinity = false;
415  m_range.from = m_it->first.component;
416  }
417 
418  auto next = std::next(m_it);
419  if (next == m_rend) {
420  m_range.toInfinity = true;
421  }
422  else {
423  m_range.toInfinity = false;
424  m_range.to = next->first.component;
425  }
426  }
427  else { // single
428  BOOST_ASSERT(!m_it->first.isNegInf);
429  m_range.fromInfinity = m_range.toInfinity = false;
430  m_range.from = m_range.to = m_it->first.component;
431  }
432 }
433 
434 } // namespace ndn
std::string toUri() const
Get escaped string representation (e.g., for use in URI) of the exclude filter.
Definition: exclude.cpp:347
bool operator==(const Exclude::Range &other) const
Definition: exclude.cpp:73
bool hasWire() const
Check if the Block has fully encoded wire.
Definition: block.cpp:249
Copyright (c) 2011-2015 Regents of the University of California.
Exclude & excludeBefore(const name::Component &to)
Exclude all components in range (-Inf, to].
Definition: exclude.cpp:250
friend std::ostream & operator<<(std::ostream &os, const Exclude &name)
Definition: exclude.cpp:332
either a name::Component or "negative infinity"
Definition: exclude.hpp:141
represent an excluded component or range
Definition: exclude.hpp:178
const_iterator & operator++()
Definition: exclude.cpp:382
name::Component from
from component (inclusive)
Definition: exclude.hpp:208
bool toInfinity
to positive infinity?
Definition: exclude.hpp:213
element_container::const_iterator element_const_iterator
Definition: block.hpp:47
const_iterator end() const
Definition: exclude.hpp:324
void parse() const
Parse TLV-VALUE into sub elements.
Definition: block.cpp:333
Represents a TLV element of NDN packet format.
Definition: block.hpp:42
void clear()
Definition: exclude.cpp:367
element_const_iterator elements_begin() const
Equivalent to elements().begin()
Definition: block.hpp:369
Exclude()
Constructs an empty Exclude.
Table::const_iterator iterator
Definition: cs-internal.hpp:41
a concept check for TLV abstraction with .wireEncode method
Definition: concepts.hpp:60
void wireDecode(const Block &wire)
Decode from the wire format.
Definition: exclude.cpp:166
Exclude & excludeOne(const name::Component &comp)
Exclude specific name component.
Definition: exclude.cpp:240
const Block & wireEncode() const
Encode to a wire format.
Definition: exclude.cpp:150
element_const_iterator elements_end() const
Equivalent to elements().end()
Definition: block.hpp:377
ExcludeMap::value_type Entry
Definition: exclude.hpp:172
size_t prependEmptyBlock(EncodingImpl< TAG > &encoder, uint32_t type)
Prepend an empty TLV element.
size_t size() const
Definition: exclude.cpp:361
void toUri(std::ostream &os) const
Write *this to the output stream, escaping characters according to the NDN URI Scheme.
ostream_joiner< std::decay_t< DelimT >, CharT, Traits > make_ostream_joiner(std::basic_ostream< CharT, Traits > &os, DelimT &&delimiter)
NDN_CXX_DEFINE_WIRE_ENCODE_INSTANTIATIONS(Exclude)
bool isImplicitSha256Digest() const
Check if the component is ImplicitSha256DigestComponent.
void reset()
Reset wire buffer of the element.
Definition: block.cpp:255
size_t elements_size() const
Equivalent to elements().size()
Definition: block.hpp:385
bool fromInfinity
from negative infinity?
Definition: exclude.hpp:202
name::Component to
to component (inclusive)
Definition: exclude.hpp:219
bool operator>(const Delegation &lhs, const Delegation &rhs)
Definition: delegation.hpp:54
Represents a name component.
bool isSingular() const
Definition: exclude.hpp:342
Exclude & excludeAfter(const name::Component &from)
Exclude all components in range [from, +Inf)
Definition: exclude.cpp:310
bool isExcluded(const name::Component &comp) const
Check if name component is excluded.
Definition: exclude.cpp:231
bool isGeneric() const
Check if the component is GenericComponent.
Exclude & excludeRange(const name::Component &from, const name::Component &to)
Exclude components in range [from, to].
Definition: exclude.cpp:256
bool operator==(const Exclude &other) const
Definition: exclude.cpp:355
a concept check for TLV abstraction with .wireEncode method
Definition: concepts.hpp:44
const_iterator begin() const
Definition: exclude.hpp:318
a concept check for TLV abstraction with .wireDecode method and constructible from Block
Definition: concepts.hpp:80
EncodingImpl< EncoderTag > EncodingBuffer
ExcludeComponent(const name::Component &component)
implicitly construct a regular infinity ExcludeComponent
Definition: exclude.cpp:32
uint32_t type() const
Get TLV-TYPE.
Definition: block.hpp:249
represents an error in TLV encoding or decoding
Definition: tlv.hpp:52
EncodingImpl< EstimatorTag > EncodingEstimator
Represents Exclude selector in NDN Interest.
Definition: exclude.hpp:43