blob: b5482cd69f175a86bec80c33597b0165e677f15f [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/**
Alexander Afanasyev74633892015-02-08 18:08:46 -08003 * Copyright (c) 2013-2015 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
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -070027#include <boost/range/adaptors.hpp>
28
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -070029namespace ndn {
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -080030
Junxiao Shic2b8d242014-11-04 08:35:29 -070031BOOST_CONCEPT_ASSERT((boost::EqualityComparable<Exclude>));
32BOOST_CONCEPT_ASSERT((WireEncodable<Exclude>));
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -070033BOOST_CONCEPT_ASSERT((WireEncodableWithEncodingBuffer<Exclude>));
Junxiao Shic2b8d242014-11-04 08:35:29 -070034BOOST_CONCEPT_ASSERT((WireDecodable<Exclude>));
35static_assert(std::is_base_of<tlv::Error, Exclude::Error>::value,
36 "Exclude::Error must inherit from tlv::Error");
Junxiao Shi7284a402014-09-12 13:42:16 -070037
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -070038Exclude::Exclude()
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -080039{
40}
41
Junxiao Shi75203022014-09-11 10:01:50 -070042Exclude::Exclude(const Block& wire)
43{
44 wireDecode(wire);
45}
46
Alexander Afanasyev74633892015-02-08 18:08:46 -080047template<encoding::Tag TAG>
Junxiao Shi75203022014-09-11 10:01:50 -070048size_t
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -070049Exclude::wireEncode(EncodingImpl<TAG>& encoder) const
Junxiao Shi75203022014-09-11 10:01:50 -070050{
Junxiao Shi7284a402014-09-12 13:42:16 -070051 if (m_exclude.empty()) {
52 throw Error("Exclude filter cannot be empty");
53 }
54
Junxiao Shi75203022014-09-11 10:01:50 -070055 size_t totalLength = 0;
56
57 // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (NameComponent (Any)?)+
58 // Any ::= ANY-TYPE TLV-LENGTH(=0)
59
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -070060 for (const auto& item : m_exclude) {
61 if (item.second) {
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -070062 totalLength += prependEmptyBlock(encoder, tlv::Any);
Junxiao Shi75203022014-09-11 10:01:50 -070063 }
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -070064 if (!item.first.empty() || !item.second) {
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -070065 totalLength += item.first.wireEncode(encoder);
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -070066 }
67 }
Junxiao Shi75203022014-09-11 10:01:50 -070068
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -070069 totalLength += encoder.prependVarNumber(totalLength);
70 totalLength += encoder.prependVarNumber(tlv::Exclude);
Junxiao Shi75203022014-09-11 10:01:50 -070071 return totalLength;
72}
73
74template size_t
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -070075Exclude::wireEncode<encoding::EncoderTag>(EncodingImpl<encoding::EncoderTag>& encoder) const;
Junxiao Shi75203022014-09-11 10:01:50 -070076
77template size_t
Alexander Afanasyevd5c48e02015-06-24 11:58:14 -070078Exclude::wireEncode<encoding::EstimatorTag>(EncodingImpl<encoding::EstimatorTag>& encoder) const;
Junxiao Shi75203022014-09-11 10:01:50 -070079
80const Block&
81Exclude::wireEncode() const
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
96void
97Exclude::wireDecode(const Block& wire)
98{
Alexander Afanasyevba096052014-09-19 15:36:37 -070099 clear();
100
Junxiao Shi7284a402014-09-12 13:42:16 -0700101 if (wire.type() != tlv::Exclude)
102 throw tlv::Error("Unexpected TLV type when decoding Exclude");
103
Junxiao Shi75203022014-09-11 10:01:50 -0700104 m_wire = wire;
105 m_wire.parse();
106
Junxiao Shi7284a402014-09-12 13:42:16 -0700107 if (m_wire.elements_size() == 0) {
108 throw Error("Exclude element cannot be empty");
109 }
110
Junxiao Shi75203022014-09-11 10:01:50 -0700111 // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (NameComponent (Any)?)+
112 // Any ::= ANY-TYPE TLV-LENGTH(=0)
113
114 Block::element_const_iterator i = m_wire.elements_begin();
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700115 if (i->type() == tlv::Any) {
116 appendExclude(name::Component(), true);
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 throw Error("Incorrect format of Exclude filter");
Junxiao Shi75203022014-09-11 10:01:50 -0700127 }
128
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700129 ++i;
Junxiao Shi75203022014-09-11 10:01:50 -0700130
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700131 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 }
Junxiao Shi75203022014-09-11 10:01:50 -0700139 }
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700140 else {
141 appendExclude(excludedComponent, false);
142 }
143 }
Junxiao Shi75203022014-09-11 10:01:50 -0700144}
145
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800146// example: ANY /b /d ANY /f
147//
148// ordered in map as:
149//
150// /f (false); /d (true); /b (false); / (true)
151//
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700152// 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
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800158bool
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700159Exclude::isExcluded(const name::Component& comp) const
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800160{
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700161 const_iterator lowerBound = m_exclude.lower_bound(comp);
162 if (lowerBound == end())
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800163 return false;
164
165 if (lowerBound->second)
166 return true;
167 else
168 return lowerBound->first == comp;
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800169}
170
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700171Exclude&
172Exclude::excludeOne(const name::Component& comp)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800173{
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700174 if (!isExcluded(comp)) {
175 m_exclude.insert(std::make_pair(comp, false));
176 m_wire.reset();
177 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800178 return *this;
179}
180
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800181// example: ANY /b0 /d0 ANY /f0
182//
183// ordered in map as:
184//
185// /f0 (false); /d0 (true); /b0 (false); / (true)
186//
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700187// 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
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800193
194
195// examples with desired outcomes
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700196// excludeRange(/, /f0) -> ANY /f0
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800197// /f0 (false); / (true)
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700198// excludeRange(/, /f1) -> ANY /f1
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800199// /f1 (false); / (true)
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700200// excludeRange(/a0, /e0) -> ANY /f0
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800201// /f0 (false); / (true)
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700202// excludeRange(/a0, /e0) -> ANY /f0
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800203// /f0 (false); / (true)
204
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700205// excludeRange(/b1, /c0) -> ANY /b0 /b1 ANY /c0 /d0 ANY /f0
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800206// /f0 (false); /d0 (true); /c0 (false); /b1 (true); /b0 (false); / (true)
207
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700208Exclude&
209Exclude::excludeRange(const name::Component& from, const name::Component& to)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800210{
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700211 if (from >= to) {
Alexander Afanasyev9c578182014-05-14 17:28:28 -0700212 throw Error("Invalid exclude range [" + from.toUri() + ", " + to.toUri() + "] "
213 "(for single name exclude use Exclude::excludeOne)");
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700214 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800215
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700216 iterator newFrom = m_exclude.lower_bound(from);
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700217 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;
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800223 }
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700224 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800225 // else
226 // nothing special if start of the range already exists with ANY flag set
227
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700228 iterator newTo = m_exclude.lower_bound(to); // !newTo cannot be end()
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700229 if (newTo == newFrom || !newTo->second) {
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700230 std::pair<iterator, bool> toResult = m_exclude.insert(std::make_pair(to, false));
231 newTo = toResult.first;
232 ++ newTo;
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700233 }
234 // else
235 // nothing to do really
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800236
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700237 m_exclude.erase(newTo, newFrom); // remove any intermediate node, since all of the are excluded
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800238
Alexander Afanasyevba096052014-09-19 15:36:37 -0700239 m_wire.reset();
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800240 return *this;
241}
242
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700243Exclude&
244Exclude::excludeAfter(const name::Component& from)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800245{
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700246 iterator newFrom = m_exclude.lower_bound(from);
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700247 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;
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800253 }
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700254 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800255 // else
256 // nothing special if start of the range already exists with ANY flag set
257
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700258 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 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800262
Alexander Afanasyevba096052014-09-19 15:36:37 -0700263 m_wire.reset();
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800264 return *this;
265}
266
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800267std::ostream&
Alexander Afanasyevff2d08f2014-04-07 18:28:25 -0700268operator<<(std::ostream& os, const Exclude& exclude)
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800269{
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700270 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;
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800277 }
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700278 if (item.second) {
279 if (!isFirst)
280 os << ",";
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700281 os << "*";
Alexander Afanasyevc076e6d2015-04-02 20:07:13 -0700282 isFirst = false;
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700283 }
284 }
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800285 return os;
286}
287
Alexander Afanasyevba096052014-09-19 15:36:37 -0700288std::string
289Exclude::toUri() const
290{
291 std::ostringstream os;
292 os << *this;
293 return os.str();
294}
295
296bool
297Exclude::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
Alexander Afanasyev3aeeaeb2014-04-22 23:34:23 -0700307} // namespace ndn