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