Alexander Afanasyev | c169a81 | 2014-05-20 20:37:29 -0400 | [diff] [blame] | 1 | /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */ |
Alexander Afanasyev | dfa52c4 | 2014-04-24 21:10:11 -0700 | [diff] [blame] | 2 | /** |
Alexander Afanasyev | c169a81 | 2014-05-20 20:37:29 -0400 | [diff] [blame] | 3 | * Copyright (c) 2013-2014 Regents of the University of California. |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 4 | * |
Alexander Afanasyev | dfa52c4 | 2014-04-24 21:10:11 -0700 | [diff] [blame] | 5 | * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions). |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 6 | * |
Alexander Afanasyev | c169a81 | 2014-05-20 20:37:29 -0400 | [diff] [blame] | 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. |
Alexander Afanasyev | dfa52c4 | 2014-04-24 21:10:11 -0700 | [diff] [blame] | 20 | * |
| 21 | * @author Alexander Afanasyev <http://lasr.cs.ucla.edu/afanasyev/index.html> |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 22 | */ |
| 23 | |
Alexander Afanasyev | 09c613f | 2014-01-29 00:23:58 -0800 | [diff] [blame] | 24 | #include "exclude.hpp" |
Junxiao Shi | c2b8d24 | 2014-11-04 08:35:29 -0700 | [diff] [blame^] | 25 | #include "util/concepts.hpp" |
Junxiao Shi | 7284a40 | 2014-09-12 13:42:16 -0700 | [diff] [blame] | 26 | |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 27 | namespace ndn { |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 28 | |
Junxiao Shi | c2b8d24 | 2014-11-04 08:35:29 -0700 | [diff] [blame^] | 29 | BOOST_CONCEPT_ASSERT((boost::EqualityComparable<Exclude>)); |
| 30 | BOOST_CONCEPT_ASSERT((WireEncodable<Exclude>)); |
| 31 | BOOST_CONCEPT_ASSERT((WireDecodable<Exclude>)); |
| 32 | static_assert(std::is_base_of<tlv::Error, Exclude::Error>::value, |
| 33 | "Exclude::Error must inherit from tlv::Error"); |
Junxiao Shi | 7284a40 | 2014-09-12 13:42:16 -0700 | [diff] [blame] | 34 | |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 35 | Exclude::Exclude() |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 36 | { |
| 37 | } |
| 38 | |
Junxiao Shi | 7520302 | 2014-09-11 10:01:50 -0700 | [diff] [blame] | 39 | Exclude::Exclude(const Block& wire) |
| 40 | { |
| 41 | wireDecode(wire); |
| 42 | } |
| 43 | |
| 44 | template<bool T> |
| 45 | size_t |
| 46 | Exclude::wireEncode(EncodingImpl<T>& block) const |
| 47 | { |
Junxiao Shi | 7284a40 | 2014-09-12 13:42:16 -0700 | [diff] [blame] | 48 | if (m_exclude.empty()) { |
| 49 | throw Error("Exclude filter cannot be empty"); |
| 50 | } |
| 51 | |
Junxiao Shi | 7520302 | 2014-09-11 10:01:50 -0700 | [diff] [blame] | 52 | size_t totalLength = 0; |
| 53 | |
| 54 | // Exclude ::= EXCLUDE-TYPE TLV-LENGTH Any? (NameComponent (Any)?)+ |
| 55 | // Any ::= ANY-TYPE TLV-LENGTH(=0) |
| 56 | |
| 57 | for (Exclude::const_iterator i = m_exclude.begin(); i != m_exclude.end(); i++) |
| 58 | { |
| 59 | if (i->second) |
| 60 | { |
| 61 | totalLength += prependBooleanBlock(block, tlv::Any); |
| 62 | } |
| 63 | if (!i->first.empty()) |
| 64 | { |
| 65 | totalLength += i->first.wireEncode(block); |
| 66 | } |
| 67 | } |
| 68 | |
| 69 | totalLength += block.prependVarNumber(totalLength); |
| 70 | totalLength += block.prependVarNumber(tlv::Exclude); |
| 71 | return totalLength; |
| 72 | } |
| 73 | |
| 74 | template size_t |
| 75 | Exclude::wireEncode<true>(EncodingImpl<true>& block) const; |
| 76 | |
| 77 | template size_t |
| 78 | Exclude::wireEncode<false>(EncodingImpl<false>& block) const; |
| 79 | |
| 80 | const Block& |
| 81 | Exclude::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 | |
| 96 | void |
| 97 | Exclude::wireDecode(const Block& wire) |
| 98 | { |
Alexander Afanasyev | ba09605 | 2014-09-19 15:36:37 -0700 | [diff] [blame] | 99 | clear(); |
| 100 | |
Junxiao Shi | 7284a40 | 2014-09-12 13:42:16 -0700 | [diff] [blame] | 101 | if (wire.type() != tlv::Exclude) |
| 102 | throw tlv::Error("Unexpected TLV type when decoding Exclude"); |
| 103 | |
Junxiao Shi | 7520302 | 2014-09-11 10:01:50 -0700 | [diff] [blame] | 104 | m_wire = wire; |
| 105 | m_wire.parse(); |
| 106 | |
Junxiao Shi | 7284a40 | 2014-09-12 13:42:16 -0700 | [diff] [blame] | 107 | if (m_wire.elements_size() == 0) { |
| 108 | throw Error("Exclude element cannot be empty"); |
| 109 | } |
| 110 | |
Junxiao Shi | 7520302 | 2014-09-11 10:01:50 -0700 | [diff] [blame] | 111 | // 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(); |
| 115 | if (i->type() == tlv::Any) |
| 116 | { |
| 117 | appendExclude(name::Component(), true); |
| 118 | ++i; |
| 119 | } |
| 120 | |
| 121 | while (i != m_wire.elements_end()) |
| 122 | { |
| 123 | if (i->type() != tlv::NameComponent) |
| 124 | throw Error("Incorrect format of Exclude filter"); |
| 125 | |
| 126 | name::Component excludedComponent(i->value(), i->value_size()); |
| 127 | ++i; |
| 128 | |
| 129 | if (i != m_wire.elements_end()) |
| 130 | { |
| 131 | if (i->type() == tlv::Any) |
| 132 | { |
| 133 | appendExclude(excludedComponent, true); |
| 134 | ++i; |
| 135 | } |
| 136 | else |
| 137 | { |
| 138 | appendExclude(excludedComponent, false); |
| 139 | } |
| 140 | } |
| 141 | else |
| 142 | { |
| 143 | appendExclude(excludedComponent, false); |
| 144 | } |
| 145 | } |
| 146 | } |
| 147 | |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 148 | // example: ANY /b /d ANY /f |
| 149 | // |
| 150 | // ordered in map as: |
| 151 | // |
| 152 | // /f (false); /d (true); /b (false); / (true) |
| 153 | // |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 154 | // lower_bound(/) -> / (true) <-- excluded (equal) |
| 155 | // lower_bound(/a) -> / (true) <-- excluded (any) |
| 156 | // lower_bound(/b) -> /b (false) <--- excluded (equal) |
| 157 | // lower_bound(/c) -> /b (false) <--- not excluded (not equal and no ANY) |
| 158 | // lower_bound(/d) -> /d (true) <- excluded |
| 159 | // lower_bound(/e) -> /d (true) <- excluded |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 160 | bool |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 161 | Exclude::isExcluded(const name::Component& comp) const |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 162 | { |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 163 | const_iterator lowerBound = m_exclude.lower_bound(comp); |
| 164 | if (lowerBound == end()) |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 165 | return false; |
| 166 | |
| 167 | if (lowerBound->second) |
| 168 | return true; |
| 169 | else |
| 170 | return lowerBound->first == comp; |
| 171 | |
| 172 | return false; |
| 173 | } |
| 174 | |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 175 | Exclude& |
| 176 | Exclude::excludeOne(const name::Component& comp) |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 177 | { |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 178 | if (!isExcluded(comp)) |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 179 | { |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 180 | m_exclude.insert(std::make_pair(comp, false)); |
Alexander Afanasyev | ba09605 | 2014-09-19 15:36:37 -0700 | [diff] [blame] | 181 | m_wire.reset(); |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 182 | } |
| 183 | return *this; |
| 184 | } |
| 185 | |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 186 | // example: ANY /b0 /d0 ANY /f0 |
| 187 | // |
| 188 | // ordered in map as: |
| 189 | // |
| 190 | // /f0 (false); /d0 (true); /b0 (false); / (true) |
| 191 | // |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 192 | // lower_bound(/) -> / (true) <-- excluded (equal) |
| 193 | // lower_bound(/a0) -> / (true) <-- excluded (any) |
| 194 | // lower_bound(/b0) -> /b0 (false) <--- excluded (equal) |
| 195 | // lower_bound(/c0) -> /b0 (false) <--- not excluded (not equal and no ANY) |
| 196 | // lower_bound(/d0) -> /d0 (true) <- excluded |
| 197 | // lower_bound(/e0) -> /d0 (true) <- excluded |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 198 | |
| 199 | |
| 200 | // examples with desired outcomes |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 201 | // excludeRange(/, /f0) -> ANY /f0 |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 202 | // /f0 (false); / (true) |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 203 | // excludeRange(/, /f1) -> ANY /f1 |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 204 | // /f1 (false); / (true) |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 205 | // excludeRange(/a0, /e0) -> ANY /f0 |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 206 | // /f0 (false); / (true) |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 207 | // excludeRange(/a0, /e0) -> ANY /f0 |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 208 | // /f0 (false); / (true) |
| 209 | |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 210 | // excludeRange(/b1, /c0) -> ANY /b0 /b1 ANY /c0 /d0 ANY /f0 |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 211 | // /f0 (false); /d0 (true); /c0 (false); /b1 (true); /b0 (false); / (true) |
| 212 | |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 213 | Exclude& |
| 214 | Exclude::excludeRange(const name::Component& from, const name::Component& to) |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 215 | { |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 216 | if (from >= to) { |
Alexander Afanasyev | 9c57818 | 2014-05-14 17:28:28 -0700 | [diff] [blame] | 217 | throw Error("Invalid exclude range [" + from.toUri() + ", " + to.toUri() + "] " |
| 218 | "(for single name exclude use Exclude::excludeOne)"); |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 219 | } |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 220 | |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 221 | iterator newFrom = m_exclude.lower_bound(from); |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 222 | if (newFrom == end() || !newFrom->second /*without ANY*/) { |
| 223 | std::pair<iterator, bool> fromResult = m_exclude.insert(std::make_pair(from, true)); |
| 224 | newFrom = fromResult.first; |
| 225 | if (!fromResult.second) { |
| 226 | // this means that the lower bound is equal to the item itself. So, just update ANY flag |
| 227 | newFrom->second = true; |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 228 | } |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 229 | } |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 230 | // else |
| 231 | // nothing special if start of the range already exists with ANY flag set |
| 232 | |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 233 | iterator newTo = m_exclude.lower_bound(to); // !newTo cannot be end() |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 234 | if (newTo == newFrom || !newTo->second) { |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 235 | std::pair<iterator, bool> toResult = m_exclude.insert(std::make_pair(to, false)); |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 236 | newTo = toResult.first; |
| 237 | ++ newTo; |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 238 | } |
| 239 | // else |
| 240 | // nothing to do really |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 241 | |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 242 | m_exclude.erase(newTo, newFrom); // remove any intermediate node, since all of the are excluded |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 243 | |
Alexander Afanasyev | ba09605 | 2014-09-19 15:36:37 -0700 | [diff] [blame] | 244 | m_wire.reset(); |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 245 | return *this; |
| 246 | } |
| 247 | |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 248 | Exclude& |
| 249 | Exclude::excludeAfter(const name::Component& from) |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 250 | { |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 251 | iterator newFrom = m_exclude.lower_bound(from); |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 252 | if (newFrom == end() || !newFrom->second /*without ANY*/) { |
| 253 | std::pair<iterator, bool> fromResult = m_exclude.insert(std::make_pair(from, true)); |
| 254 | newFrom = fromResult.first; |
| 255 | if (!fromResult.second) { |
| 256 | // this means that the lower bound is equal to the item itself. So, just update ANY flag |
| 257 | newFrom->second = true; |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 258 | } |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 259 | } |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 260 | // else |
| 261 | // nothing special if start of the range already exists with ANY flag set |
| 262 | |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 263 | if (newFrom != m_exclude.begin()) { |
| 264 | // remove any intermediate node, since all of the are excluded |
| 265 | m_exclude.erase(m_exclude.begin(), newFrom); |
| 266 | } |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 267 | |
Alexander Afanasyev | ba09605 | 2014-09-19 15:36:37 -0700 | [diff] [blame] | 268 | m_wire.reset(); |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 269 | return *this; |
| 270 | } |
| 271 | |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 272 | std::ostream& |
Alexander Afanasyev | ff2d08f | 2014-04-07 18:28:25 -0700 | [diff] [blame] | 273 | operator<<(std::ostream& os, const Exclude& exclude) |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 274 | { |
| 275 | bool empty = true; |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 276 | for (Exclude::const_reverse_iterator i = exclude.rbegin(); i != exclude.rend(); i++) { |
| 277 | if (!i->first.empty()) { |
| 278 | if (!empty) os << ","; |
Alexander Afanasyev | 9c57818 | 2014-05-14 17:28:28 -0700 | [diff] [blame] | 279 | os << i->first.toUri(); |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 280 | empty = false; |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 281 | } |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 282 | if (i->second) { |
| 283 | if (!empty) os << ","; |
| 284 | os << "*"; |
| 285 | empty = false; |
| 286 | } |
| 287 | } |
Alexander Afanasyev | b3a6af4 | 2014-01-03 13:08:28 -0800 | [diff] [blame] | 288 | return os; |
| 289 | } |
| 290 | |
Alexander Afanasyev | ba09605 | 2014-09-19 15:36:37 -0700 | [diff] [blame] | 291 | std::string |
| 292 | Exclude::toUri() const |
| 293 | { |
| 294 | std::ostringstream os; |
| 295 | os << *this; |
| 296 | return os.str(); |
| 297 | } |
| 298 | |
| 299 | bool |
| 300 | Exclude::operator==(const Exclude& other) const |
| 301 | { |
| 302 | if (empty() && other.empty()) |
| 303 | return true; |
| 304 | if (empty() || other.empty()) |
| 305 | return false; |
| 306 | |
| 307 | return wireEncode() == other.wireEncode(); |
| 308 | } |
| 309 | |
Alexander Afanasyev | 3aeeaeb | 2014-04-22 23:34:23 -0700 | [diff] [blame] | 310 | } // namespace ndn |