NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.3: 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; -*- */
24 #include "exclude.hpp"
26 
27 #include <boost/range/adaptors.hpp>
28 
29 namespace ndn {
30 
32  : isNegInf(false)
33  , component(component1)
34 {
35 }
36 
38  : isNegInf(true)
39 {
40  BOOST_ASSERT(isNegInf1 == true);
41 }
42 
43 bool
45 {
46  return (a.isNegInf && b.isNegInf) ||
47  (a.isNegInf == b.isNegInf && a.component == b.component);
48 }
49 
50 bool
52 {
53  return a.isNegInf < b.isNegInf ||
54  (a.isNegInf == b.isNegInf && a.component > b.component);
55 }
56 
57 bool
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 
65 std::ostream&
66 operator<<(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 
91 BOOST_CONCEPT_ASSERT((boost::EqualityComparable<Exclude>));
92 BOOST_CONCEPT_ASSERT((WireEncodable<Exclude>));
94 BOOST_CONCEPT_ASSERT((WireDecodable<Exclude>));
95 static_assert(std::is_base_of<tlv::Error, Exclude::Error>::value,
96  "Exclude::Error must inherit from tlv::Error");
97 
98 Exclude::Exclude() = default;
99 
101 {
102  wireDecode(wire);
103 }
104 
105 template<encoding::Tag TAG>
106 size_t
108 {
109  if (m_entries.empty()) {
110  BOOST_THROW_EXCEPTION(Error("cannot encode empty Exclude selector"));
111  }
112 
113  size_t totalLength = 0;
114 
115  // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (NameComponent (Any)?)+
116  // Any ::= ANY-TYPE TLV-LENGTH(=0)
117 
118  for (const Entry& entry : m_entries) {
119  if (entry.second) {
120  totalLength += prependEmptyBlock(encoder, tlv::Any);
121  }
122  if (!entry.first.isNegInf) {
123  totalLength += entry.first.component.wireEncode(encoder);
124  }
125  }
126 
127  totalLength += encoder.prependVarNumber(totalLength);
128  totalLength += encoder.prependVarNumber(tlv::Exclude);
129  return totalLength;
130 }
131 
132 template size_t
133 Exclude::wireEncode<encoding::EncoderTag>(EncodingImpl<encoding::EncoderTag>& encoder) const;
134 
135 template size_t
136 Exclude::wireEncode<encoding::EstimatorTag>(EncodingImpl<encoding::EstimatorTag>& encoder) const;
137 
138 const Block&
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 
154 void
156 {
157  clear();
158 
159  if (wire.type() != tlv::Exclude)
160  BOOST_THROW_EXCEPTION(tlv::Error("Unexpected TLV type when decoding Exclude"));
161 
162  m_wire = wire;
163  m_wire.parse();
164 
165  if (m_wire.elements_size() == 0) {
166  BOOST_THROW_EXCEPTION(Error("Exclude element cannot be empty"));
167  }
168 
169  // 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();
173  if (i->type() == tlv::Any) {
174  this->appendEntry(true, true);
175  ++i;
176  }
177 
178  while (i != m_wire.elements_end()) {
180  try {
181  component = name::Component(*i);
182  }
183  catch (const name::Component::Error&) {
184  BOOST_THROW_EXCEPTION(Error("Incorrect format of Exclude filter"));
185  }
186  ++i;
187 
188  if (i != m_wire.elements_end() && i->type() == tlv::Any) {
189  this->appendEntry(component, true);
190  ++i;
191  }
192  else {
193  this->appendEntry(component, false);
194  }
195  }
196 }
197 
198 template<typename T>
199 void
200 Exclude::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)
209 //
210 // 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
216 bool
218 {
219  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
221  (lb->second || // comp matches an ANY range
222  (!lb->first.isNegInf && lb->first.component == comp)); // comp equals an exact excluded component
223 }
224 
225 Exclude&
227 {
228  if (!isExcluded(comp)) {
229  this->appendEntry(comp, false);
230  m_wire.reset();
231  }
232  return *this;
233 }
234 
235 Exclude&
237 {
238  return excludeRange(ExcludeComponent(true), to);
239 }
240 
241 Exclude&
243 {
244  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 
259 Exclude&
261 {
262  if (!from.isNegInf && from.component >= to) {
263  BOOST_THROW_EXCEPTION(Error("Invalid exclude range [" + from.component.toUri() + ", " + to.toUri() + "] "
264  "(for single name exclude use Exclude::excludeOne)"));
265  }
266 
267  ExcludeMap::iterator newFrom = m_entries.lower_bound(from);
268  if (newFrom == m_entries.end() || !newFrom->second /*without ANY*/) {
269  bool isNewEntry = false;
270  std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
271  if (!isNewEntry) {
272  // this means that the lower bound is equal to the item itself. So, just update ANY flag
273  newFrom->second = true;
274  }
275  }
276  // else
277  // nothing special if start of the range already exists with ANY flag set
278 
279  ExcludeMap::iterator newTo = m_entries.lower_bound(to);
280  BOOST_ASSERT(newTo != m_entries.end());
281  if (newTo == newFrom || !newTo->second) {
282  newTo = m_entries.emplace_hint(newTo, to, false);
283  ++newTo;
284  }
285  // else
286  // nothing to do really
287 
288  // remove any intermediate entries, since all of the are excluded
289  m_entries.erase(newTo, newFrom);
290 
291  m_wire.reset();
292  return *this;
293 }
294 
295 Exclude&
297 {
298  ExcludeMap::iterator newFrom = m_entries.lower_bound(from);
299  if (newFrom == m_entries.end() || !newFrom->second /*without ANY*/) {
300  bool isNewEntry = false;
301  std::tie(newFrom, isNewEntry) = m_entries.emplace(from, true);
302  if (!isNewEntry) {
303  // this means that the lower bound is equal to the item itself. So, just update ANY flag
304  newFrom->second = true;
305  }
306  }
307  // else
308  // nothing special if start of the range already exists with ANY flag set
309 
310  // remove any intermediate node, since all of the are excluded
311  m_entries.erase(m_entries.begin(), newFrom);
312 
313  m_wire.reset();
314  return *this;
315 }
316 
317 std::ostream&
318 operator<<(std::ostream& os, const Exclude& exclude)
319 {
320  bool isFirst = true;
321  for (const Exclude::Entry& entry : exclude.m_entries | boost::adaptors::reversed) {
322  if (!entry.first.isNegInf) {
323  if (!isFirst)
324  os << ",";
325  entry.first.component.toUri(os);
326  isFirst = false;
327  }
328  if (entry.second) {
329  if (!isFirst)
330  os << ",";
331  os << "*";
332  isFirst = false;
333  }
334  }
335  return os;
336 }
337 
338 std::string
340 {
341  std::ostringstream os;
342  os << *this;
343  return os.str();
344 }
345 
346 bool
347 Exclude::operator==(const Exclude& other) const
348 {
349  return m_entries == other.m_entries;
350 }
351 
352 size_t
354 {
355  return std::distance(begin(), end());
356 }
357 
358 void
360 {
361  m_entries.clear();
362  m_wire.reset();
363 }
364 
365 Exclude::const_iterator::const_iterator(ExcludeMap::const_reverse_iterator it,
366  ExcludeMap::const_reverse_iterator rend)
367  : m_it(it)
368  , m_rend(rend)
369 {
370  this->update();
371 }
372 
375 {
376  bool wasInRange = m_it->second;
377  ++m_it;
378  if (wasInRange && m_it != m_rend) {
379  BOOST_ASSERT(m_it->second == false); // consecutive ranges should have been combined
380  ++m_it; // skip over range high limit
381  }
382  this->update();
383  return *this;
384 }
385 
388 {
389  const_iterator i = *this;
390  this->operator++();
391  return i;
392 }
393 
394 void
395 Exclude::const_iterator::update()
396 {
397  if (m_it == m_rend) {
398  return;
399  }
400 
401  if (m_it->second) { // range
402  if (m_it->first.isNegInf) {
403  m_range.fromInfinity = true;
404  }
405  else {
406  m_range.fromInfinity = false;
407  m_range.from = m_it->first.component;
408  }
409 
410  auto next = std::next(m_it);
411  if (next == m_rend) {
412  m_range.toInfinity = true;
413  }
414  else {
415  m_range.toInfinity = false;
416  m_range.to = next->first.component;
417  }
418  }
419  else { // single
420  BOOST_ASSERT(!m_it->first.isNegInf);
421  m_range.fromInfinity = m_range.toInfinity = false;
422  m_range.from = m_range.to = m_it->first.component;
423  }
424 }
425 
426 } // namespace ndn
std::string toUri() const
Get escaped string representation (e.g., for use in URI) of the exclude filter.
Definition: exclude.cpp:339
bool operator==(const Exclude::Range &other) const
Definition: exclude.cpp:58
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:236
friend std::ostream & operator<<(std::ostream &os, const Exclude &name)
Definition: exclude.cpp:318
either a name::Component or "negative infinity"
Definition: exclude.hpp:140
represent an excluded component or range
Definition: exclude.hpp:177
EncodingImpl< EstimatorTag > EncodingEstimator
const_iterator & operator++()
Definition: exclude.cpp:374
name::Component from
from component (inclusive)
Definition: exclude.hpp:203
bool toInfinity
to positive infinity?
Definition: exclude.hpp:208
const_iterator end() const
Definition: exclude.hpp:311
void parse() const
Parse wire buffer into subblocks.
Definition: block.cpp:322
Class representing a wire element of NDN-TLV packet format.
Definition: block.hpp:43
void clear()
Definition: exclude.cpp:359
Exclude()
Constructs an empty Exclude.
bool operator>(const Exclude::ExcludeComponent &a, const Exclude::ExcludeComponent &b)
Definition: exclude.cpp:51
Table::const_iterator iterator
Definition: cs-internal.hpp:41
a concept check for TLV abstraction with .wireEncode method
Definition: concepts.hpp:50
void wireDecode(const Block &wire)
Decode from the wire format.
Definition: exclude.cpp:155
Exclude & excludeOne(const name::Component &comp)
Exclude specific name component.
Definition: exclude.cpp:226
const Block & wireEncode() const
Encode to a wire format.
Definition: exclude.cpp:139
ExcludeMap::value_type Entry
Definition: exclude.hpp:171
EncodingImpl< EncoderTag > EncodingBuffer
size_t prependEmptyBlock(EncodingImpl< TAG > &encoder, uint32_t type)
Helper to prepend TLV block type type containing no value (i.e., a boolean block) ...
size_t size() const
Definition: exclude.cpp:353
void toUri(std::ostream &os) const
Write *this to the output stream, escaping characters according to the NDN URI Scheme.
element_container::const_iterator element_const_iterator
Definition: block.hpp:48
bool fromInfinity
from negative infinity?
Definition: exclude.hpp:197
name::Component to
to component (inclusive)
Definition: exclude.hpp:214
Component holds a read-only name component value.
bool isSingular() const
Definition: exclude.hpp:329
Exclude & excludeAfter(const name::Component &from)
Exclude all components in range [from, +Inf)
Definition: exclude.cpp:296
bool isExcluded(const name::Component &comp) const
Check if name component is excluded.
Definition: exclude.cpp:217
Exclude & excludeRange(const name::Component &from, const name::Component &to)
Exclude components in range [from, to].
Definition: exclude.cpp:242
bool operator==(const Exclude &other) const
Definition: exclude.cpp:347
a concept check for TLV abstraction with .wireEncode method
Definition: concepts.hpp:34
const_iterator begin() const
Definition: exclude.hpp:305
a concept check for TLV abstraction with .wireDecode method and constructible from Block ...
Definition: concepts.hpp:70
ExcludeComponent(const name::Component &component)
implicitly construct a regular infinity ExcludeComponent
Definition: exclude.cpp:31
uint32_t type() const
Definition: block.hpp:324
represents an error in TLV encoding or decoding
Definition: tlv.hpp:50
Represents Exclude selector in NDN Interest.
Definition: exclude.hpp:38
Error that can be thrown from name::Component.