NS-3 based Named Data Networking (NDN) simulator
ndnSIM 2.0: 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 
31 BOOST_CONCEPT_ASSERT((boost::EqualityComparable<Exclude>));
32 BOOST_CONCEPT_ASSERT((WireEncodable<Exclude>));
34 BOOST_CONCEPT_ASSERT((WireDecodable<Exclude>));
35 static_assert(std::is_base_of<tlv::Error, Exclude::Error>::value,
36  "Exclude::Error must inherit from tlv::Error");
37 
39 {
40 }
41 
42 Exclude::Exclude(const Block& wire)
43 {
44  wireDecode(wire);
45 }
46 
47 template<encoding::Tag TAG>
48 size_t
49 Exclude::wireEncode(EncodingImpl<TAG>& encoder) const
50 {
51  if (m_exclude.empty()) {
52  BOOST_THROW_EXCEPTION(Error("Exclude filter cannot be empty"));
53  }
54 
55  size_t totalLength = 0;
56 
57  // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (NameComponent (Any)?)+
58  // Any ::= ANY-TYPE TLV-LENGTH(=0)
59 
60  for (const auto& item : m_exclude) {
61  if (item.second) {
62  totalLength += prependEmptyBlock(encoder, tlv::Any);
63  }
64  if (!item.first.empty() || !item.second) {
65  totalLength += item.first.wireEncode(encoder);
66  }
67  }
68 
69  totalLength += encoder.prependVarNumber(totalLength);
70  totalLength += encoder.prependVarNumber(tlv::Exclude);
71  return totalLength;
72 }
73 
74 template size_t
75 Exclude::wireEncode<encoding::EncoderTag>(EncodingImpl<encoding::EncoderTag>& encoder) const;
76 
77 template size_t
78 Exclude::wireEncode<encoding::EstimatorTag>(EncodingImpl<encoding::EstimatorTag>& encoder) const;
79 
80 const Block&
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 
96 void
98 {
99  clear();
100 
101  if (wire.type() != tlv::Exclude)
102  BOOST_THROW_EXCEPTION(tlv::Error("Unexpected TLV type when decoding Exclude"));
103 
104  m_wire = wire;
105  m_wire.parse();
106 
107  if (m_wire.elements_size() == 0) {
108  BOOST_THROW_EXCEPTION(Error("Exclude element cannot be empty"));
109  }
110 
111  // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (NameComponent (Any)?)+
112  // Any ::= ANY-TYPE TLV-LENGTH(=0)
113 
115  if (i->type() == tlv::Any) {
117  ++i;
118  }
119 
120  while (i != m_wire.elements_end()) {
121  name::Component excludedComponent;
122  try {
123  excludedComponent = std::move(name::Component(*i));
124  }
125  catch (const name::Component::Error&) {
126  BOOST_THROW_EXCEPTION(Error("Incorrect format of Exclude filter"));
127  }
128 
129  ++i;
130 
131  if (i != m_wire.elements_end()) {
132  if (i->type() == tlv::Any) {
133  appendExclude(excludedComponent, true);
134  ++i;
135  }
136  else {
137  appendExclude(excludedComponent, false);
138  }
139  }
140  else {
141  appendExclude(excludedComponent, false);
142  }
143  }
144 }
145 
146 // example: ANY /b /d ANY /f
147 //
148 // ordered in map as:
149 //
150 // /f (false); /d (true); /b (false); / (true)
151 //
152 // lower_bound(/) -> / (true) <-- excluded (equal)
153 // lower_bound(/a) -> / (true) <-- excluded (any)
154 // lower_bound(/b) -> /b (false) <--- excluded (equal)
155 // lower_bound(/c) -> /b (false) <--- not excluded (not equal and no ANY)
156 // lower_bound(/d) -> /d (true) <- excluded
157 // lower_bound(/e) -> /d (true) <- excluded
158 bool
160 {
161  const_iterator lowerBound = m_exclude.lower_bound(comp);
162  if (lowerBound == end())
163  return false;
164 
165  if (lowerBound->second)
166  return true;
167  else
168  return lowerBound->first == comp;
169 }
170 
171 Exclude&
173 {
174  if (!isExcluded(comp)) {
175  m_exclude.insert(std::make_pair(comp, false));
176  m_wire.reset();
177  }
178  return *this;
179 }
180 
181 // example: ANY /b0 /d0 ANY /f0
182 //
183 // ordered in map as:
184 //
185 // /f0 (false); /d0 (true); /b0 (false); / (true)
186 //
187 // lower_bound(/) -> / (true) <-- excluded (equal)
188 // lower_bound(/a0) -> / (true) <-- excluded (any)
189 // lower_bound(/b0) -> /b0 (false) <--- excluded (equal)
190 // lower_bound(/c0) -> /b0 (false) <--- not excluded (not equal and no ANY)
191 // lower_bound(/d0) -> /d0 (true) <- excluded
192 // lower_bound(/e0) -> /d0 (true) <- excluded
193 
194 
195 // examples with desired outcomes
196 // excludeRange(/, /f0) -> ANY /f0
197 // /f0 (false); / (true)
198 // excludeRange(/, /f1) -> ANY /f1
199 // /f1 (false); / (true)
200 // excludeRange(/a0, /e0) -> ANY /f0
201 // /f0 (false); / (true)
202 // excludeRange(/a0, /e0) -> ANY /f0
203 // /f0 (false); / (true)
204 
205 // excludeRange(/b1, /c0) -> ANY /b0 /b1 ANY /c0 /d0 ANY /f0
206 // /f0 (false); /d0 (true); /c0 (false); /b1 (true); /b0 (false); / (true)
207 
208 Exclude&
210 {
211  if (from >= to) {
212  BOOST_THROW_EXCEPTION(Error("Invalid exclude range [" + from.toUri() + ", " + to.toUri() + "] "
213  "(for single name exclude use Exclude::excludeOne)"));
214  }
215 
216  iterator newFrom = m_exclude.lower_bound(from);
217  if (newFrom == end() || !newFrom->second /*without ANY*/) {
218  std::pair<iterator, bool> fromResult = m_exclude.insert(std::make_pair(from, true));
219  newFrom = fromResult.first;
220  if (!fromResult.second) {
221  // this means that the lower bound is equal to the item itself. So, just update ANY flag
222  newFrom->second = true;
223  }
224  }
225  // else
226  // nothing special if start of the range already exists with ANY flag set
227 
228  iterator newTo = m_exclude.lower_bound(to); // !newTo cannot be end()
229  if (newTo == newFrom || !newTo->second) {
230  std::pair<iterator, bool> toResult = m_exclude.insert(std::make_pair(to, false));
231  newTo = toResult.first;
232  ++ newTo;
233  }
234  // else
235  // nothing to do really
236 
237  m_exclude.erase(newTo, newFrom); // remove any intermediate node, since all of the are excluded
238 
239  m_wire.reset();
240  return *this;
241 }
242 
243 Exclude&
245 {
246  iterator newFrom = m_exclude.lower_bound(from);
247  if (newFrom == end() || !newFrom->second /*without ANY*/) {
248  std::pair<iterator, bool> fromResult = m_exclude.insert(std::make_pair(from, true));
249  newFrom = fromResult.first;
250  if (!fromResult.second) {
251  // this means that the lower bound is equal to the item itself. So, just update ANY flag
252  newFrom->second = true;
253  }
254  }
255  // else
256  // nothing special if start of the range already exists with ANY flag set
257 
258  if (newFrom != m_exclude.begin()) {
259  // remove any intermediate node, since all of the are excluded
260  m_exclude.erase(m_exclude.begin(), newFrom);
261  }
262 
263  m_wire.reset();
264  return *this;
265 }
266 
267 std::ostream&
268 operator<<(std::ostream& os, const Exclude& exclude)
269 {
270  bool isFirst = true;
271  for (const auto& item : exclude | boost::adaptors::reversed) {
272  if (!item.first.empty() || !item.second) {
273  if (!isFirst)
274  os << ",";
275  os << item.first.toUri();
276  isFirst = false;
277  }
278  if (item.second) {
279  if (!isFirst)
280  os << ",";
281  os << "*";
282  isFirst = false;
283  }
284  }
285  return os;
286 }
287 
288 std::string
290 {
291  std::ostringstream os;
292  os << *this;
293  return os.str();
294 }
295 
296 bool
297 Exclude::operator==(const Exclude& other) const
298 {
299  if (empty() && other.empty())
300  return true;
301  if (empty() || other.empty())
302  return false;
303 
304  return wireEncode() == other.wireEncode();
305 }
306 
307 } // namespace ndn
void appendExclude(const name::Component &name, bool any)
Method to directly append exclude element.
Definition: exclude.hpp:217
Copyright (c) 2011-2015 Regents of the University of California.
EncodingImpl< EstimatorTag > EncodingEstimator
std::ostream & operator<<(std::ostream &os, const Data &data)
Definition: data.cpp:340
exclude_type::const_iterator const_iterator
Definition: exclude.hpp:151
Class representing a wire element of NDN-TLV packet format.
Definition: block.hpp:43
void clear()
Clear the exclude filter.
Definition: exclude.hpp:229
Exclude()
Default constructor an empty exclude.
Definition: exclude.cpp:38
element_const_iterator elements_end() const
Definition: block.cpp:595
element_const_iterator elements_begin() const
Definition: block.cpp:589
a concept check for TLV abstraction with .wireEncode method
Definition: concepts.hpp:50
const Block & wireEncode() const
Encode to a wire format.
Definition: exclude.cpp:81
void wireDecode(const Block &wire)
Decode from the wire format.
Definition: exclude.cpp:97
Exclude & excludeOne(const name::Component &comp)
Exclude specific name component.
Definition: exclude.cpp:172
bool isExcluded(const name::Component &comp) const
Check if name component is excluded.
Definition: exclude.cpp:159
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) ...
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
size_t elements_size() const
Definition: block.cpp:601
void reset()
Reset wire buffer of the element.
Definition: block.cpp:302
void parse() const
Parse wire buffer into subblocks.
Definition: block.cpp:322
uint32_t type() const
Definition: block.hpp:346
Component holds a read-only name component value.
exclude_type::iterator iterator
Definition: exclude.hpp:150
bool empty() const
Check if exclude filter is empty.
Definition: exclude.hpp:223
size_t wireEncode(EncodingImpl< TAG > &encoder) const
Fast encoding or block size estimation.
Definition: exclude.cpp:49
std::string toUri() const
Get escaped string representation (e.g., for use in URI) of the exclude filter.
Definition: exclude.cpp:289
bool hasWire() const
Check if the Block has fully encoded wire.
Definition: block.cpp:471
Exclude & excludeAfter(const name::Component &from)
Exclude all components from range [from, +Inf].
Definition: exclude.cpp:244
Exclude & excludeRange(const name::Component &from, const name::Component &to)
Exclude components from range [from, to].
Definition: exclude.cpp:209
const_iterator end() const
Get end iterator of the exclude terms.
Definition: exclude.hpp:248
a concept check for TLV abstraction with .wireEncode method
Definition: concepts.hpp:34
bool operator==(const Exclude &other) const
Definition: exclude.cpp:297
a concept check for TLV abstraction with .wireDecode method and constructible from Block ...
Definition: concepts.hpp:70
represents an error in TLV encoding or decoding
Definition: tlv.hpp:50
Class to represent Exclude component in NDN interests.
Definition: exclude.hpp:38
Error that can be thrown from name::Component.