blob: 11edd82ec7ee4d2cf9ffa31eeec2eeb6c6dcbd09 [file] [log] [blame]
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -08001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
2/*
3 * Copyright (c) 2013, Regents of the University of California
4 * Alexander Afanasyev
5 *
6 * BSD license, See the LICENSE file for more information
7 *
8 * Author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
9 */
10
Alexander Afanasyev09c613f2014-01-29 00:23:58 -080011#include "exclude.hpp"
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -080012
13namespace ndn
14{
15
16Exclude::Exclude ()
17{
18}
19
20// example: ANY /b /d ANY /f
21//
22// ordered in map as:
23//
24// /f (false); /d (true); /b (false); / (true)
25//
26// lower_bound (/) -> / (true) <-- excluded (equal)
27// lower_bound (/a) -> / (true) <-- excluded (any)
28// lower_bound (/b) -> /b (false) <--- excluded (equal)
29// lower_bound (/c) -> /b (false) <--- not excluded (not equal and no ANY)
30// lower_bound (/d) -> /d (true) <- excluded
31// lower_bound (/e) -> /d (true) <- excluded
32bool
33Exclude::isExcluded (const Name::Component &comp) const
34{
35 const_iterator lowerBound = m_exclude.lower_bound (comp);
36 if (lowerBound == end ())
37 return false;
38
39 if (lowerBound->second)
40 return true;
41 else
42 return lowerBound->first == comp;
43
44 return false;
45}
46
47Exclude &
48Exclude::excludeOne (const Name::Component &comp)
49{
50 if (!isExcluded (comp))
51 {
52 m_exclude.insert (std::make_pair (comp, false));
53 }
54 return *this;
55}
56
57
58// example: ANY /b0 /d0 ANY /f0
59//
60// ordered in map as:
61//
62// /f0 (false); /d0 (true); /b0 (false); / (true)
63//
64// lower_bound (/) -> / (true) <-- excluded (equal)
65// lower_bound (/a0) -> / (true) <-- excluded (any)
66// lower_bound (/b0) -> /b0 (false) <--- excluded (equal)
67// lower_bound (/c0) -> /b0 (false) <--- not excluded (not equal and no ANY)
68// lower_bound (/d0) -> /d0 (true) <- excluded
69// lower_bound (/e0) -> /d0 (true) <- excluded
70
71
72// examples with desired outcomes
73// excludeRange (/, /f0) -> ANY /f0
74// /f0 (false); / (true)
75// excludeRange (/, /f1) -> ANY /f1
76// /f1 (false); / (true)
77// excludeRange (/a0, /e0) -> ANY /f0
78// /f0 (false); / (true)
79// excludeRange (/a0, /e0) -> ANY /f0
80// /f0 (false); / (true)
81
82// excludeRange (/b1, /c0) -> ANY /b0 /b1 ANY /c0 /d0 ANY /f0
83// /f0 (false); /d0 (true); /c0 (false); /b1 (true); /b0 (false); / (true)
84
85Exclude &
86Exclude::excludeRange (const Name::Component &from, const Name::Component &to)
87{
88 if (from >= to)
89 {
Alexander Afanasyev993a0e12014-01-03 13:51:37 -080090 throw Error ("Invalid exclude range [" +
91 from.toEscapedString() + ", " +
92 to.toEscapedString() +
93 "] (for single name exclude use Exclude::excludeOne)");
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -080094 }
95
96 iterator newFrom = m_exclude.lower_bound (from);
97 if (newFrom == end () || !newFrom->second /*without ANY*/)
98 {
99 std::pair<iterator, bool> fromResult = m_exclude.insert (std::make_pair (from, true));
100 newFrom = fromResult.first;
101 if (!fromResult.second)
102 {
103 // this means that the lower bound is equal to the item itself. So, just update ANY flag
104 newFrom->second = true;
105 }
106 }
107 // else
108 // nothing special if start of the range already exists with ANY flag set
109
110 iterator newTo = m_exclude.lower_bound (to); // !newTo cannot be end ()
111 if (newTo == newFrom || !newTo->second)
112 {
113 std::pair<iterator, bool> toResult = m_exclude.insert (std::make_pair (to, false));
114 newTo = toResult.first;
115 ++ newTo;
116 }
117 else
118 {
119 // nothing to do really
120 }
121
122 m_exclude.erase (newTo, newFrom); // remove any intermediate node, since all of the are excluded
123
124 return *this;
125}
126
127Exclude &
128Exclude::excludeAfter (const Name::Component &from)
129{
130 iterator newFrom = m_exclude.lower_bound (from);
131 if (newFrom == end () || !newFrom->second /*without ANY*/)
132 {
133 std::pair<iterator, bool> fromResult = m_exclude.insert (std::make_pair (from, true));
134 newFrom = fromResult.first;
135 if (!fromResult.second)
136 {
137 // this means that the lower bound is equal to the item itself. So, just update ANY flag
138 newFrom->second = true;
139 }
140 }
141 // else
142 // nothing special if start of the range already exists with ANY flag set
143
144 if (newFrom != m_exclude.begin ())
145 {
146 m_exclude.erase (m_exclude.begin (), newFrom); // remove any intermediate node, since all of the are excluded
147 }
148
149 return *this;
150}
151
152
153std::ostream&
154operator << (std::ostream &os, const Exclude &exclude)
155{
156 bool empty = true;
157 for (Exclude::const_reverse_iterator i = exclude.rbegin (); i != exclude.rend (); i++)
158 {
159 if (!i->first.empty())
160 {
161 if (!empty) os << ",";
162 os << i->first.toEscapedString ();
163 empty = false;
164 }
165 if (i->second)
166 {
167 if (!empty) os << ",";
168 os << "*";
169 empty = false;
170 }
171 }
172 return os;
173}
174
Alexander Afanasyev993a0e12014-01-03 13:51:37 -0800175const Block&
176Exclude::wireEncode() const
177{
178 if (wire_.hasWire())
179 return wire_;
180
181 wire_ = Block(Tlv::Exclude);
182
183 for (Exclude::const_reverse_iterator i = m_exclude.rbegin (); i != m_exclude.rend (); i++)
184 {
185 if (!i->first.empty())
186 {
187 OBufferStream os;
188 Tlv::writeVarNumber(os, Tlv::NameComponent);
Alexander Afanasyev95e8c2f2014-02-06 17:29:30 -0800189 Tlv::writeVarNumber(os, i->first.value_size());
190 os.write(reinterpret_cast<const char *>(i->first.value()), i->first.value_size());
Alexander Afanasyev993a0e12014-01-03 13:51:37 -0800191
192 wire_.push_back(Block(os.buf()));
193
194 }
195 if (i->second)
196 {
197 OBufferStream os;
198 Tlv::writeVarNumber(os, Tlv::Any);
199 Tlv::writeVarNumber(os, 0);
200 wire_.push_back(Block(os.buf()));
201 }
202 }
203
204 wire_.encode();
205 return wire_;
206}
207
208void
209Exclude::wireDecode(const Block &wire)
210{
211 wire_ = wire;
212 wire_.parse();
213
214 Block::element_const_iterator i = wire_.getAll().begin();
215 if (i->type() == Tlv::Any)
216 {
217 appendExclude("/", true);
218 ++i;
219 }
220
221 while (i != wire_.getAll().end())
222 {
223 if (i->type() != Tlv::NameComponent)
224 throw Error("Incorrect format of Exclude filter");
225
226 Name::Component excludedComponent (i->value(), i->value_size());
227 ++i;
228
229 if (i != wire_.getAll().end())
230 {
231 if (i->type() == Tlv::Any)
232 {
233 appendExclude(excludedComponent, true);
234 ++i;
235 }
236 else
237 {
238 appendExclude(excludedComponent, false);
239 }
240 }
241 else
242 {
243 appendExclude(excludedComponent, false);
244 }
245 }
246}
247
Alexander Afanasyevb3a6af42014-01-03 13:08:28 -0800248
249} // ndn