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-2017 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 "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? (NameComponent (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? (NameComponent (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  ++i;
198 
199  if (i != m_wire.elements_end() && i->type() == tlv::Any) {
200  this->appendEntry(component, true);
201  ++i;
202  }
203  else {
204  this->appendEntry(component, false);
205  }
206  }
207 }
208 
209 template<typename T>
210 void
211 Exclude::appendEntry(const T& component, bool hasAny)
212 {
213  m_entries.emplace_hint(m_entries.begin(), std::piecewise_construct,
214  std::forward_as_tuple(component),
215  std::forward_as_tuple(hasAny));
216 }
217 
218 // example: ANY "b" "d" ANY "f"
219 // ordered in map as: "f" (false); "d" (true); "b" (false); -Inf (true)
220 //
221 // lower_bound("") -> -Inf (true) <-- excluded (ANY)
222 // lower_bound("a") -> -Inf (true) <-- excluded (ANY)
223 // lower_bound("b") -> "b" (false) <--- excluded (equal)
224 // lower_bound("c") -> "b" (false) <--- not excluded (not equal and no ANY)
225 // lower_bound("d") -> "d" (true) <- excluded
226 // lower_bound("e") -> "d" (true) <- excluded
227 bool
229 {
230  ExcludeMap::const_iterator lb = m_entries.lower_bound(comp);
231  return lb != m_entries.end() && // if false, comp is less than the first excluded component
232  (lb->second || // comp matches an ANY range
233  (!lb->first.isNegInf && lb->first.component == comp)); // comp equals an exact excluded component
234 }
235 
236 Exclude&
238 {
239  if (!isExcluded(comp)) {
240  this->appendEntry(comp, false);
241  m_wire.reset();
242  }
243  return *this;
244 }
245 
246 Exclude&
248 {
249  return excludeRange(ExcludeComponent(true), to);
250 }
251 
252 Exclude&
254 {
255  return excludeRange(ExcludeComponent(from), to);
256 }
257 
258 // example: ANY "b" "d" ANY "g"
259 // ordered in map as: "f" (false); "d" (true); "b" (false); -Inf (true)
260 // possible sequence of operations:
261 // excludeBefore("a") -> excludeRange(-Inf, "a") -> ANY "a"
262 // "a" (false); -Inf (true)
263 // excludeBefore("b") -> excludeRange(-Inf, "b") -> ANY "b"
264 // "b" (false); -Inf (true)
265 // excludeRange("e", "g") -> ANY "b" "e" ANY "g"
266 // "g" (false); "e" (true); "b" (false); -Inf (true)
267 // excludeRange("d", "f") -> ANY "b" "d" ANY "g"
268 // "g" (false); "d" (true); "b" (false); -Inf (true)
269 
270 Exclude&
271 Exclude::excludeRange(const ExcludeComponent& from, const name::Component& to)
272 {
273  if (!from.isNegInf && from.component >= to) {
274  BOOST_THROW_EXCEPTION(Error("Invalid exclude range [" + from.component.toUri() + ", " + to.toUri() + "] "
275  "(for single name exclude use Exclude::excludeOne)"));
276  }
277 
278  ExcludeMap::iterator newFrom = m_entries.lower_bound(from);
279  if (newFrom == m_entries.end() || !newFrom->second /*without ANY*/) {
280  bool isNewEntry = false;
281  std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
282  if (!isNewEntry) {
283  // this means that the lower bound is equal to the item itself. So, just update ANY flag
284  newFrom->second = true;
285  }
286  }
287  // else
288  // nothing special if start of the range already exists with ANY flag set
289 
290  ExcludeMap::iterator newTo = m_entries.lower_bound(to);
291  BOOST_ASSERT(newTo != m_entries.end());
292  if (newTo == newFrom || !newTo->second) {
293  newTo = m_entries.emplace_hint(newTo, to, false);
294  ++newTo;
295  }
296  // else
297  // nothing to do really
298 
299  // remove any intermediate entries, since all of the are excluded
300  m_entries.erase(newTo, newFrom);
301 
302  m_wire.reset();
303  return *this;
304 }
305 
306 Exclude&
308 {
309  ExcludeMap::iterator newFrom = m_entries.lower_bound(from);
310  if (newFrom == m_entries.end() || !newFrom->second /*without ANY*/) {
311  bool isNewEntry = false;
312  std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
313  if (!isNewEntry) {
314  // this means that the lower bound is equal to the item itself. So, just update ANY flag
315  newFrom->second = true;
316  }
317  }
318  // else
319  // nothing special if start of the range already exists with ANY flag set
320 
321  // remove any intermediate node, since all of the are excluded
322  m_entries.erase(m_entries.begin(), newFrom);
323 
324  m_wire.reset();
325  return *this;
326 }
327 
328 std::ostream&
329 operator<<(std::ostream& os, const Exclude& exclude)
330 {
331  auto join = make_ostream_joiner(os, ',');
332  for (const Exclude::Entry& entry : exclude.m_entries | boost::adaptors::reversed) {
333  if (!entry.first.isNegInf) {
334  join = entry.first.component;
335  }
336  if (entry.second) {
337  join = '*';
338  }
339  }
340  return os;
341 }
342 
343 std::string
345 {
346  std::ostringstream os;
347  os << *this;
348  return os.str();
349 }
350 
351 bool
352 Exclude::operator==(const Exclude& other) const
353 {
354  return m_entries == other.m_entries;
355 }
356 
357 size_t
359 {
360  return std::distance(begin(), end());
361 }
362 
363 void
365 {
366  m_entries.clear();
367  m_wire.reset();
368 }
369 
370 Exclude::const_iterator::const_iterator(ExcludeMap::const_reverse_iterator it,
371  ExcludeMap::const_reverse_iterator rend)
372  : m_it(it)
373  , m_rend(rend)
374 {
375  this->update();
376 }
377 
380 {
381  bool wasInRange = m_it->second;
382  ++m_it;
383  if (wasInRange && m_it != m_rend) {
384  BOOST_ASSERT(m_it->second == false); // consecutive ranges should have been combined
385  ++m_it; // skip over range high limit
386  }
387  this->update();
388  return *this;
389 }
390 
393 {
394  const_iterator i = *this;
395  this->operator++();
396  return i;
397 }
398 
399 void
400 Exclude::const_iterator::update()
401 {
402  if (m_it == m_rend) {
403  return;
404  }
405 
406  if (m_it->second) { // range
407  if (m_it->first.isNegInf) {
408  m_range.fromInfinity = true;
409  }
410  else {
411  m_range.fromInfinity = false;
412  m_range.from = m_it->first.component;
413  }
414 
415  auto next = std::next(m_it);
416  if (next == m_rend) {
417  m_range.toInfinity = true;
418  }
419  else {
420  m_range.toInfinity = false;
421  m_range.to = next->first.component;
422  }
423  }
424  else { // single
425  BOOST_ASSERT(!m_it->first.isNegInf);
426  m_range.fromInfinity = m_range.toInfinity = false;
427  m_range.from = m_range.to = m_it->first.component;
428  }
429 }
430 
431 } // namespace ndn
std::string toUri() const
Get escaped string representation (e.g., for use in URI) of the exclude filter.
Definition: exclude.cpp:344
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:251
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:247
friend std::ostream & operator<<(std::ostream &os, const Exclude &name)
Definition: exclude.cpp:329
either a name::Component or "negative infinity"
Definition: exclude.hpp:139
represent an excluded component or range
Definition: exclude.hpp:176
const_iterator & operator++()
Definition: exclude.cpp:379
name::Component from
from component (inclusive)
Definition: exclude.hpp:206
bool toInfinity
to positive infinity?
Definition: exclude.hpp:211
element_container::const_iterator element_const_iterator
Definition: block.hpp:47
const_iterator end() const
Definition: exclude.hpp:316
void parse() const
Parse TLV-VALUE into sub elements.
Definition: block.cpp:335
Represents a TLV element of NDN packet format.
Definition: block.hpp:42
void clear()
Definition: exclude.cpp:364
element_const_iterator elements_begin() const
Equivalent to elements().begin()
Definition: block.hpp:355
Exclude()
Constructs an empty Exclude.
ostream_joiner< typename std::decay< DelimT >::type, CharT, Traits > make_ostream_joiner(std::basic_ostream< CharT, Traits > &os, DelimT &&delimiter)
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:237
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:363
ExcludeMap::value_type Entry
Definition: exclude.hpp:170
size_t prependEmptyBlock(EncodingImpl< TAG > &encoder, uint32_t type)
Prepend an empty TLV element.
size_t size() const
Definition: exclude.cpp:358
void toUri(std::ostream &os) const
Write *this to the output stream, escaping characters according to the NDN URI Scheme.
NDN_CXX_DEFINE_WIRE_ENCODE_INSTANTIATIONS(Exclude)
void reset()
Reset wire buffer of the element.
Definition: block.cpp:257
size_t elements_size() const
Equivalent to elements().size()
Definition: block.hpp:371
bool fromInfinity
from negative infinity?
Definition: exclude.hpp:200
name::Component to
to component (inclusive)
Definition: exclude.hpp:217
bool operator>(const Delegation &lhs, const Delegation &rhs)
Definition: delegation.hpp:54
Component holds a read-only name component value.
bool isSingular() const
Definition: exclude.hpp:334
Exclude & excludeAfter(const name::Component &from)
Exclude all components in range [from, +Inf)
Definition: exclude.cpp:307
bool isExcluded(const name::Component &comp) const
Check if name component is excluded.
Definition: exclude.cpp:228
Exclude & excludeRange(const name::Component &from, const name::Component &to)
Exclude components in range [from, to].
Definition: exclude.cpp:253
bool operator==(const Exclude &other) const
Definition: exclude.cpp:352
a concept check for TLV abstraction with .wireEncode method
Definition: concepts.hpp:44
const_iterator begin() const
Definition: exclude.hpp:310
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:235
represents an error in TLV encoding or decoding
Definition: tlv.hpp:50
EncodingImpl< EstimatorTag > EncodingEstimator
Represents Exclude selector in NDN Interest.
Definition: exclude.hpp:37
Error that can be thrown from name::Component.