blob: 44e6039a88fa03b793c1462ef334aee519b8906a [file] [log] [blame]
Jeff Thompson25b4e612013-10-10 16:03:24 -07001/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil -*- */
Jeff Thompson47eecfc2013-07-07 22:56:46 -07002/**
Jeff Thompson7687dc02013-09-13 11:54:07 -07003 * Copyright (C) 2013 Regents of the University of California.
4 * @author: Jeff Thompson <jefft0@remap.ucla.edu>
Jeff Thompsona98000c2013-12-16 14:40:09 -08005 * @author: Alexander Afanasyev <alexander.afanasyev@ucla.edu>
Jeff Thompson47eecfc2013-07-07 22:56:46 -07006 * See COPYING for copyright and distribution information.
Jeff Thompson9c41dfe2013-06-27 12:10:25 -07007 */
8
Jeff Thompson54909772013-07-07 22:38:57 -07009#include <stdexcept>
Jeff Thompsonb8f1b132013-08-13 11:07:43 -070010#include <algorithm>
Jeff Thompsond8e53e62013-10-29 16:59:49 -070011#include <string.h>
Jeff Thompson25b4e612013-10-10 16:03:24 -070012#include <ndn-cpp/name.hpp>
Jeff Thompsona98000c2013-12-16 14:40:09 -080013#include "c/util/ndn_memory.h"
Jeff Thompson9c41dfe2013-06-27 12:10:25 -070014
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080015#include "util/string-helper.hpp"
16
Jeff Thompson9c41dfe2013-06-27 12:10:25 -070017using namespace std;
18
19namespace ndn {
20
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080021uint64_t
22Name::Component::toNumberWithMarker(uint8_t marker) const
Jeff Thompson26c63d62013-07-02 18:00:26 -070023{
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080024 if (empty() || *getValue().begin() != marker)
25 throw runtime_error("Name component does not begin with the expected marker");
Jeff Thompson26c63d62013-07-02 18:00:26 -070026
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080027 uint64_t result = 0;
28 for (Buffer::const_iterator i = getValue().begin()+1; i != getValue().end(); ++i) {
29 result <<= 8;
30 result |= *i;
Jeff Thompson26c63d62013-07-02 18:00:26 -070031 }
32
Jeff Thompson27cae532013-10-08 12:52:41 -070033 return result;
34}
35
Jeff Thompsond129ac12013-10-11 14:30:12 -070036Name::Component
Jeff Thompsond129ac12013-10-11 14:30:12 -070037Name::Component::fromNumber(uint64_t number)
Jeff Thompson8aac1992013-08-12 17:26:02 -070038{
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080039 ptr_lib::shared_ptr<Buffer> value(new Buffer);
Jeff Thompson8aac1992013-08-12 17:26:02 -070040
Jeff Thompsond129ac12013-10-11 14:30:12 -070041 // First encode in little endian.
42 while (number != 0) {
43 value->push_back(number & 0xff);
44 number >>= 8;
45 }
46
47 // Make it big endian.
48 reverse(value->begin(), value->end());
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080049 return Component(value);
Jeff Thompsond129ac12013-10-11 14:30:12 -070050}
51
Alexander Afanasyev848c61a2014-01-03 13:52:04 -080052Name::Component
Jeff Thompsond129ac12013-10-11 14:30:12 -070053Name::Component::fromNumberWithMarker(uint64_t number, uint8_t marker)
54{
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080055 ptr_lib::shared_ptr<Buffer> value(new Buffer);
Jeff Thompsond129ac12013-10-11 14:30:12 -070056
57 // Add the leading marker.
58 value->push_back(marker);
Jeff Thompsonb8f1b132013-08-13 11:07:43 -070059
Jeff Thompson8aac1992013-08-12 17:26:02 -070060 // First encode in little endian.
Jeff Thompsond129ac12013-10-11 14:30:12 -070061 while (number != 0) {
62 value->push_back(number & 0xff);
63 number >>= 8;
Jeff Thompson8aac1992013-08-12 17:26:02 -070064 }
65
Jeff Thompson8aac1992013-08-12 17:26:02 -070066 // Make it big endian.
Jeff Thompson995aba52013-09-12 12:04:52 -070067 reverse(value->begin() + 1, value->end());
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080068 return Component(value);
Jeff Thompson25b4e612013-10-10 16:03:24 -070069}
70
71uint64_t
72Name::Component::toNumber() const
73{
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080074 uint64_t result = 0;
75 for (Buffer::const_iterator i = getValue().begin(); i != getValue().end(); ++i) {
76 result <<= 8;
77 result |= *i;
78 }
79
80 return result;
Jeff Thompson25b4e612013-10-10 16:03:24 -070081}
82
Jeff Thompsona98000c2013-12-16 14:40:09 -080083int
84Name::Component::compare(const Name::Component& other) const
85{
86 // Imitate ndn_Exclude_compareComponents.
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080087 if (getValue().size() < other.getValue().size())
Jeff Thompsona98000c2013-12-16 14:40:09 -080088 return -1;
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080089 if (getValue().size() > other.getValue().size())
Jeff Thompsona98000c2013-12-16 14:40:09 -080090 return 1;
91
92 // The components are equal length. Just do a byte compare.
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080093 return ndn_memcmp(getValue().buf(), other.getValue().buf(), getValue().size());
Jeff Thompsona98000c2013-12-16 14:40:09 -080094}
95
Alexander Afanasyevaf283d82014-01-03 13:23:34 -080096// const Block &
97// Name::wireEncode() const
98// {
99
100// }
101
Jeff Thompson25b4e612013-10-10 16:03:24 -0700102void
Jeff Thompson0050abe2013-09-17 12:50:25 -0700103Name::set(const char *uri_cstr)
Jeff Thompson443398d2013-07-02 19:45:46 -0700104{
Jeff Thompson67515bd2013-08-15 17:43:22 -0700105 components_.clear();
106
Jeff Thompson443398d2013-07-02 19:45:46 -0700107 string uri = uri_cstr;
108 trim(uri);
109 if (uri.size() == 0)
110 return;
111
112 size_t iColon = uri.find(':');
113 if (iColon != string::npos) {
114 // Make sure the colon came before a '/'.
115 size_t iFirstSlash = uri.find('/');
116 if (iFirstSlash == string::npos || iColon < iFirstSlash) {
117 // Omit the leading protocol such as ndn:
118 uri.erase(0, iColon + 1);
119 trim(uri);
120 }
121 }
122
123 // Trim the leading slash and possibly the authority.
124 if (uri[0] == '/') {
125 if (uri.size() >= 2 && uri[1] == '/') {
126 // Strip the authority following "//".
127 size_t iAfterAuthority = uri.find('/', 2);
128 if (iAfterAuthority == string::npos)
129 // Unusual case: there was only an authority.
130 return;
131 else {
132 uri.erase(0, iAfterAuthority + 1);
133 trim(uri);
134 }
135 }
136 else {
137 uri.erase(0, 1);
138 trim(uri);
139 }
140 }
141
142 size_t iComponentStart = 0;
143
144 // Unescape the components.
145 while (iComponentStart < uri.size()) {
146 size_t iComponentEnd = uri.find("/", iComponentStart);
147 if (iComponentEnd == string::npos)
148 iComponentEnd = uri.size();
149
Jeff Thompsond8e53e62013-10-29 16:59:49 -0700150 Component component(fromEscapedString(&uri[0], iComponentStart, iComponentEnd));
Jeff Thompson46411c92013-09-13 19:31:25 -0700151 // Ignore illegal components. This also gets rid of a trailing '/'.
Alexander Afanasyevaf283d82014-01-03 13:23:34 -0800152 if (!component.empty())
Jeff Thompson46411c92013-09-13 19:31:25 -0700153 components_.push_back(Component(component));
Jeff Thompson443398d2013-07-02 19:45:46 -0700154
155 iComponentStart = iComponentEnd + 1;
156 }
157}
158
Jeff Thompson26b0d792013-09-23 16:19:01 -0700159Name&
160Name::append(const Name& name)
161{
162 if (&name == this)
163 // Copying from this name, so need to make a copy first.
164 return append(Name(name));
165
166 for (size_t i = 0; i < name.components_.size(); ++i)
167 components_.push_back(name.components_[i]);
168
169 return *this;
170}
171
Jeff Thompsond0159d72013-09-23 13:34:15 -0700172Name
173Name::getSubName(size_t iStartComponent, size_t nComponents) const
174{
175 Name result;
176
Jeff Thompson97223af2013-09-24 17:01:27 -0700177 size_t iEnd = iStartComponent + nComponents;
178 for (size_t i = iStartComponent; i < iEnd && i < components_.size(); ++i)
Jeff Thompsond0159d72013-09-23 13:34:15 -0700179 result.components_.push_back(components_[i]);
180
181 return result;
182}
183
184Name
185Name::getSubName(size_t iStartComponent) const
186{
187 Name result;
188
Jeff Thompson97223af2013-09-24 17:01:27 -0700189 for (size_t i = iStartComponent; i < components_.size(); ++i)
Jeff Thompsond0159d72013-09-23 13:34:15 -0700190 result.components_.push_back(components_[i]);
191
192 return result;
193}
194
Jeff Thompson0050abe2013-09-17 12:50:25 -0700195bool
Jeff Thompson3c2ab012013-10-02 14:18:16 -0700196Name::equals(const Name& name) const
197{
Jeff Thompsone589c3f2013-10-12 17:30:50 -0700198 if (components_.size() != name.components_.size())
Jeff Thompson3c2ab012013-10-02 14:18:16 -0700199 return false;
200
201 for (size_t i = 0; i < components_.size(); ++i) {
Alexander Afanasyevaf283d82014-01-03 13:23:34 -0800202 if (components_[i].getValue() != name.components_[i].getValue())
Jeff Thompson3c2ab012013-10-02 14:18:16 -0700203 return false;
204 }
205
Jeff Thompsone589c3f2013-10-12 17:30:50 -0700206 return true;
Jeff Thompson3c2ab012013-10-02 14:18:16 -0700207}
208
209bool
Alexander Afanasyevaf283d82014-01-03 13:23:34 -0800210Name::isPrefixOf(const Name& name) const
Jeff Thompsoncc35cd42013-08-20 12:23:14 -0700211{
212 // Imitate ndn_Name_match.
213
Jeff Thompsone589c3f2013-10-12 17:30:50 -0700214 // This name is longer than the name we are checking it against.
215 if (components_.size() > name.components_.size())
Jeff Thompson3c2ab012013-10-02 14:18:16 -0700216 return false;
Jeff Thompsoncc35cd42013-08-20 12:23:14 -0700217
Jeff Thompsone589c3f2013-10-12 17:30:50 -0700218 // Check if at least one of given components doesn't match.
Jeff Thompson3c2ab012013-10-02 14:18:16 -0700219 for (size_t i = 0; i < components_.size(); ++i) {
Alexander Afanasyevaf283d82014-01-03 13:23:34 -0800220 if (components_[i].getValue() != name.components_[i].getValue())
Jeff Thompsoncc35cd42013-08-20 12:23:14 -0700221 return false;
222 }
223
Jeff Thompsone589c3f2013-10-12 17:30:50 -0700224 return true;
Jeff Thompsoncc35cd42013-08-20 12:23:14 -0700225}
226
Alexander Afanasyevaf283d82014-01-03 13:23:34 -0800227Name::Component
Jeff Thompsond8e53e62013-10-29 16:59:49 -0700228Name::fromEscapedString(const char *escapedString, size_t beginOffset, size_t endOffset)
229{
230 string trimmedString(escapedString + beginOffset, escapedString + endOffset);
231 trim(trimmedString);
232 string value = unescape(trimmedString);
233
234 if (value.find_first_not_of(".") == string::npos) {
235 // Special case for component of only periods.
236 if (value.size() <= 2)
237 // Zero, one or two periods is illegal. Ignore this component.
Alexander Afanasyevaf283d82014-01-03 13:23:34 -0800238 return Component();
Jeff Thompsond8e53e62013-10-29 16:59:49 -0700239 else
240 // Remove 3 periods.
Alexander Afanasyevaf283d82014-01-03 13:23:34 -0800241 return Component((const uint8_t *)&value[3], value.size() - 3);
Jeff Thompsond8e53e62013-10-29 16:59:49 -0700242 }
243 else
Alexander Afanasyevaf283d82014-01-03 13:23:34 -0800244 return Component((const uint8_t *)&value[0], value.size());
Jeff Thompsond8e53e62013-10-29 16:59:49 -0700245}
246
Alexander Afanasyevaf283d82014-01-03 13:23:34 -0800247Name::Component
Jeff Thompsond8e53e62013-10-29 16:59:49 -0700248Name::fromEscapedString(const char *escapedString)
249{
250 return fromEscapedString(escapedString, 0, ::strlen(escapedString));
251}
252
Alexander Afanasyevaf283d82014-01-03 13:23:34 -0800253void
254Name::toEscapedString(const vector<uint8_t>& value, std::ostream& result)
Jeff Thompsonec7789a2013-08-21 11:08:36 -0700255{
256 bool gotNonDot = false;
257 for (unsigned i = 0; i < value.size(); ++i) {
258 if (value[i] != 0x2e) {
259 gotNonDot = true;
260 break;
261 }
262 }
263 if (!gotNonDot) {
264 // Special case for component of zero or more periods. Add 3 periods.
265 result << "...";
Jeff Thompson97223af2013-09-24 17:01:27 -0700266 for (size_t i = 0; i < value.size(); ++i)
Jeff Thompsonec7789a2013-08-21 11:08:36 -0700267 result << '.';
268 }
269 else {
270 // In case we need to escape, set to upper case hex and save the previous flags.
271 ios::fmtflags saveFlags = result.flags(ios::hex | ios::uppercase);
272
Jeff Thompson97223af2013-09-24 17:01:27 -0700273 for (size_t i = 0; i < value.size(); ++i) {
Jeff Thompson10ad12a2013-09-24 16:19:11 -0700274 uint8_t x = value[i];
Jeff Thompsonec7789a2013-08-21 11:08:36 -0700275 // Check for 0-9, A-Z, a-z, (+), (-), (.), (_)
Jeff Thompsonf68a74a2013-11-20 15:16:11 -0800276 if ((x >= 0x30 && x <= 0x39) || (x >= 0x41 && x <= 0x5a) ||
277 (x >= 0x61 && x <= 0x7a) || x == 0x2b || x == 0x2d ||
278 x == 0x2e || x == 0x5f)
Jeff Thompsonec7789a2013-08-21 11:08:36 -0700279 result << x;
280 else {
281 result << '%';
282 if (x < 16)
283 result << '0';
284 result << (unsigned int)x;
285 }
286 }
287
288 // Restore.
289 result.flags(saveFlags);
290 }
291}
292
Jeff Thompson6653b0b2013-09-23 12:32:39 -0700293string
Jeff Thompson10ad12a2013-09-24 16:19:11 -0700294Name::toEscapedString(const vector<uint8_t>& value)
Jeff Thompson6653b0b2013-09-23 12:32:39 -0700295{
296 ostringstream result;
297 toEscapedString(value, result);
298 return result.str();
299}
300
Jeff Thompson82568ad2013-12-17 15:17:40 -0800301bool
302Name::breadthFirstLess(const Name& name1, const Name& name2)
303{
304 for (size_t i = 0; i < name1.size() && i < name2.size(); ++i) {
305 if (name1[i] == name2[i])
306 // The components at this index are equal, so check the next components.
307 continue;
308
309 // Otherwise, the result is based on the components at this index.
310 return name1[i] < name2[i];
311 }
312
313 // The components up to min(name1.size(), name2.size()) are equal, so sort on the shorter name.
314 return name1.size() < name2.size();
315}
316
Alexander Afanasyevaf283d82014-01-03 13:23:34 -0800317std::ostream&
318operator << (std::ostream& os, const Name& name)
319{
320 if (name.empty())
321 {
322 os << "/";
323 }
324 else
325 {
326 for (Name::const_iterator i = name.begin(); i != name.end(); i++) {
327 os << "/";
328 i->toEscapedString(os);
329 }
330 }
331
332 return os;
333}
Jeff Thompson82568ad2013-12-17 15:17:40 -0800334
Alexander Afanasyev848c61a2014-01-03 13:52:04 -0800335const Block &
336Name::wireEncode() const
337{
338 if (wire_.hasWire())
339 return wire_;
340
341 wire_ = Block(Tlv::Name);
342 for (Name::const_iterator i = begin(); i != end(); i++) {
343 OBufferStream os;
344 Tlv::writeVarNumber(os, Tlv::NameComponent);
345 Tlv::writeVarNumber(os, i->getValue().size());
346 os.write(reinterpret_cast<const char*>(i->getValue().buf()), i->getValue().size());
347
348 wire_.push_back(Block(os.buf()));
349 }
350
351 wire_.encode();
352 return wire_;
353}
354
355void
356Name::wireDecode(const Block &wire)
357{
358 wire_ = wire;
359 wire_.parse();
360
361 for (Block::element_const_iterator i = wire_.getAll().begin();
362 i != wire_.getAll().end();
363 ++i)
364 {
365 append(i->value(), i->value_size());
366 }
367}
368
369
Jeff Thompson9c41dfe2013-06-27 12:10:25 -0700370}