name.cc 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733
  1. // Copyright (C) 2009 Internet Systems Consortium, Inc. ("ISC")
  2. //
  3. // Permission to use, copy, modify, and/or distribute this software for any
  4. // purpose with or without fee is hereby granted, provided that the above
  5. // copyright notice and this permission notice appear in all copies.
  6. //
  7. // THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  8. // REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  9. // AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  10. // INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  11. // LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  12. // OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  13. // PERFORMANCE OF THIS SOFTWARE.
  14. #include <cctype>
  15. #include <cassert>
  16. #include <iterator>
  17. #include <functional>
  18. #include <vector>
  19. #include <iostream>
  20. #include <algorithm>
  21. #include <util/buffer.h>
  22. #include <dns/exceptions.h>
  23. #include <dns/name.h>
  24. #include <dns/name_internal.h>
  25. #include <dns/messagerenderer.h>
  26. #include <dns/labelsequence.h>
  27. using namespace std;
  28. using namespace isc::util;
  29. using isc::dns::NameComparisonResult;
  30. using namespace isc::dns::name::internal;
  31. namespace isc {
  32. namespace dns {
  33. namespace {
  34. ///
  35. /// These are shortcut arrays for efficient character conversion.
  36. /// digitvalue converts a digit character to the corresponding integer.
  37. /// maptolower convert uppercase alphabets to their lowercase counterparts.
  38. /// We once used a helper non-local static object to avoid hardcoding the
  39. /// array members, but we then realized it's susceptible to static
  40. /// initialization order fiasco: Since these constants are used in a Name
  41. /// constructor, a non-local static Name object defined in another translation
  42. /// unit than this file may not be initialized correctly.
  43. /// There are several ways to address this issue, but in this specific case
  44. /// we chose the naive but simple hardcoding approach.
  45. ///
  46. /// These definitions are derived from BIND 9's libdns module.
  47. /// Note: we could use the standard tolower() function instead of the
  48. /// maptolower array, but a benchmark indicated that the private array could
  49. /// improve the performance of message rendering (which internally uses the
  50. /// array heavily) about 27%. Since we want to achieve very good performance
  51. /// for message rendering in some cases, we'll keep using it.
  52. const char digitvalue[256] = {
  53. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 16
  54. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 32
  55. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 48
  56. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, // 64
  57. -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 80
  58. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 96
  59. -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 112
  60. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 128
  61. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  62. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  63. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  64. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  65. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  66. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  67. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
  68. -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 256
  69. };
  70. }
  71. namespace name {
  72. namespace internal {
  73. const uint8_t maptolower[] = {
  74. 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
  75. 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
  76. 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
  77. 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
  78. 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
  79. 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
  80. 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
  81. 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
  82. 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, // ..., 'A' - 'G'
  83. 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, // 'H' - 'O'
  84. 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, // 'P' - 'W'
  85. 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, // 'X' - 'Z', ...
  86. 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
  87. 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
  88. 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
  89. 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
  90. 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
  91. 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
  92. 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
  93. 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
  94. 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
  95. 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
  96. 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
  97. 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
  98. 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
  99. 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
  100. 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
  101. 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
  102. 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
  103. 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
  104. 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
  105. 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
  106. };
  107. } // end of internal
  108. } // end of name
  109. namespace {
  110. ///
  111. /// Textual name parser states.
  112. ///
  113. typedef enum {
  114. ft_init = 0, // begin of the name
  115. ft_start, // begin of a label
  116. ft_ordinary, // parsing an ordinary label
  117. ft_initialescape, // just found '\'
  118. ft_escape, // begin of handling a '\'-escaped sequence
  119. ft_escdecimal, // parsing a '\DDD' octet.
  120. // Unused at this moment. We'll revisit this when we support master file
  121. // parser where @ is used to mean an origin name.
  122. ft_at
  123. } ft_state;
  124. }
  125. Name::Name(const std::string &namestring, bool downcase) {
  126. //
  127. // Initialize things to make the compiler happy; they're not required.
  128. //
  129. unsigned int digits = 0;
  130. unsigned int value = 0;
  131. unsigned int count = 0;
  132. //
  133. // Set up the state machine.
  134. //
  135. std::string::const_iterator s = namestring.begin();
  136. std::string::const_iterator send = namestring.end();
  137. bool done = false;
  138. bool is_root = false;
  139. ft_state state = ft_init;
  140. NameOffsets offsets;
  141. offsets.reserve(Name::MAX_LABELS);
  142. offsets.push_back(0);
  143. NameString ndata;
  144. ndata.reserve(Name::MAX_WIRE);
  145. // should we refactor this code using, e.g, the state pattern? Probably
  146. // not at this point, as this is based on proved code (derived from BIND9)
  147. // and it's less likely that we'll have more variations in the domain name
  148. // syntax. If this ever happens next time, we should consider refactor
  149. // the code, rather than adding more states and cases below.
  150. while (ndata.size() < Name::MAX_WIRE && s != send && !done) {
  151. unsigned char c = *s++;
  152. switch (state) {
  153. case ft_init:
  154. //
  155. // Is this the root name?
  156. //
  157. if (c == '.') {
  158. if (s != send) {
  159. isc_throw(EmptyLabel,
  160. "non terminating empty label in " << namestring);
  161. }
  162. is_root = true;
  163. } else if (c == '@' && s == send) {
  164. // handle a single '@' as the root name.
  165. is_root = true;
  166. }
  167. if (is_root) {
  168. ndata.push_back(0);
  169. done = true;
  170. break;
  171. }
  172. // FALLTHROUGH
  173. case ft_start:
  174. ndata.push_back(0); // placeholder for the label length field
  175. count = 0;
  176. if (c == '\\') {
  177. state = ft_initialescape;
  178. break;
  179. }
  180. state = ft_ordinary;
  181. assert(ndata.size() < Name::MAX_WIRE);
  182. // FALLTHROUGH
  183. case ft_ordinary:
  184. if (c == '.') {
  185. if (count == 0) {
  186. isc_throw(EmptyLabel,
  187. "duplicate period in " << namestring);
  188. }
  189. ndata.at(offsets.back()) = count;
  190. offsets.push_back(ndata.size());
  191. if (s == send) {
  192. ndata.push_back(0);
  193. done = true;
  194. }
  195. state = ft_start;
  196. } else if (c == '\\') {
  197. state = ft_escape;
  198. } else {
  199. if (++count > MAX_LABELLEN) {
  200. isc_throw(TooLongLabel,
  201. "label is too long in " << namestring);
  202. }
  203. ndata.push_back(downcase ? maptolower[c] : c);
  204. }
  205. break;
  206. case ft_initialescape:
  207. if (c == '[') {
  208. // This looks like a bitstring label, which was deprecated.
  209. // Intentionally drop it.
  210. isc_throw(BadLabelType,
  211. "invalid label type in " << namestring);
  212. }
  213. state = ft_escape;
  214. // FALLTHROUGH
  215. case ft_escape:
  216. if (!isdigit(c & 0xff)) {
  217. if (++count > MAX_LABELLEN) {
  218. isc_throw(TooLongLabel,
  219. "label is too long in " << namestring);
  220. }
  221. ndata.push_back(downcase ? maptolower[c] : c);
  222. state = ft_ordinary;
  223. break;
  224. }
  225. digits = 0;
  226. value = 0;
  227. state = ft_escdecimal;
  228. // FALLTHROUGH
  229. case ft_escdecimal:
  230. if (!isdigit(c & 0xff)) {
  231. isc_throw(BadEscape,
  232. "mixture of escaped digit and non-digit in "
  233. << namestring);
  234. }
  235. value *= 10;
  236. value += digitvalue[c];
  237. digits++;
  238. if (digits == 3) {
  239. if (value > 255) {
  240. isc_throw(BadEscape,
  241. "escaped decimal is too large in "
  242. << namestring);
  243. }
  244. if (++count > MAX_LABELLEN) {
  245. isc_throw(TooLongLabel,
  246. "label is too long in " << namestring);
  247. }
  248. ndata.push_back(downcase ? maptolower[value] : value);
  249. state = ft_ordinary;
  250. }
  251. break;
  252. default:
  253. // impossible case
  254. assert(false);
  255. }
  256. }
  257. if (!done) { // no trailing '.' was found.
  258. if (ndata.size() == Name::MAX_WIRE) {
  259. isc_throw(TooLongName,
  260. "name is too long for termination in " << namestring);
  261. }
  262. assert(s == send);
  263. if (state != ft_ordinary && state != ft_at) {
  264. isc_throw(IncompleteName,
  265. "incomplete textual name in " <<
  266. (namestring.empty() ? "<empty>" : namestring));
  267. }
  268. if (state == ft_ordinary) {
  269. assert(count != 0);
  270. ndata.at(offsets.back()) = count;
  271. offsets.push_back(ndata.size());
  272. // add a trailing \0
  273. ndata.push_back('\0');
  274. }
  275. }
  276. labelcount_ = offsets.size();
  277. assert(labelcount_ > 0 && labelcount_ <= Name::MAX_LABELS);
  278. ndata_.assign(ndata.data(), ndata.size());
  279. length_ = ndata_.size();
  280. offsets_.assign(offsets.begin(), offsets.end());
  281. }
  282. namespace {
  283. ///
  284. /// Wire-format name parser states.
  285. ///
  286. typedef enum {
  287. fw_start = 0, // beginning of a label
  288. fw_ordinary, // inside an ordinary (non compressed) label
  289. fw_newcurrent // beginning of a compression pointer
  290. } fw_state;
  291. }
  292. Name::Name(InputBuffer& buffer, bool downcase) {
  293. NameOffsets offsets;
  294. offsets.reserve(Name::MAX_LABELS);
  295. /*
  296. * Initialize things to make the compiler happy; they're not required.
  297. */
  298. unsigned int n = 0;
  299. //
  300. // Set up.
  301. //
  302. bool done = false;
  303. unsigned int nused = 0;
  304. bool seen_pointer = false;
  305. fw_state state = fw_start;
  306. unsigned int cused = 0; // Bytes of compressed name data used
  307. unsigned int current = buffer.getPosition();
  308. unsigned int pos_begin = current;
  309. unsigned int biggest_pointer = current;
  310. // Make the compiler happy; this is not required.
  311. // XXX: bad style in that we initialize it with a dummy value and define
  312. // it far from where it's used. But alternatives seemed even worse.
  313. unsigned int new_current = 0;
  314. //
  315. // Note: The following code is not optimized for speed, but
  316. // rather for correctness. Speed will be addressed in the future.
  317. //
  318. while (current < buffer.getLength() && !done) {
  319. unsigned int c = buffer.readUint8();
  320. current++;
  321. if (!seen_pointer) {
  322. cused++;
  323. }
  324. switch (state) {
  325. case fw_start:
  326. if (c <= MAX_LABELLEN) {
  327. offsets.push_back(nused);
  328. if (nused + c + 1 > Name::MAX_WIRE) {
  329. isc_throw(DNSMessageFORMERR, "wire name is too long: "
  330. << nused + c + 1 << " bytes");
  331. }
  332. nused += c + 1;
  333. ndata_.push_back(c);
  334. if (c == 0) {
  335. done = true;
  336. }
  337. n = c;
  338. state = fw_ordinary;
  339. } else if ((c & COMPRESS_POINTER_MARK8) == COMPRESS_POINTER_MARK8) {
  340. //
  341. // Ordinary 14-bit pointer.
  342. //
  343. new_current = c & ~COMPRESS_POINTER_MARK8;
  344. n = 1;
  345. state = fw_newcurrent;
  346. } else {
  347. // this case includes local compression pointer, which hasn't
  348. // been standardized.
  349. isc_throw(DNSMessageFORMERR, "unknown label character: " << c);
  350. }
  351. break;
  352. case fw_ordinary:
  353. if (downcase) {
  354. c = maptolower[c];
  355. }
  356. ndata_.push_back(c);
  357. if (--n == 0) {
  358. state = fw_start;
  359. }
  360. break;
  361. case fw_newcurrent:
  362. new_current *= 256;
  363. new_current += c;
  364. if (--n != 0) {
  365. break;
  366. }
  367. if (new_current >= biggest_pointer) {
  368. isc_throw(DNSMessageFORMERR,
  369. "bad compression pointer (out of range): " <<
  370. new_current);
  371. }
  372. biggest_pointer = new_current;
  373. current = new_current;
  374. buffer.setPosition(current);
  375. seen_pointer = true;
  376. state = fw_start;
  377. break;
  378. default:
  379. assert(false);
  380. }
  381. }
  382. if (!done) {
  383. isc_throw(DNSMessageFORMERR, "incomplete wire-format name");
  384. }
  385. labelcount_ = offsets.size();
  386. length_ = nused;
  387. offsets_.assign(offsets.begin(), offsets.end());
  388. buffer.setPosition(pos_begin + cused);
  389. }
  390. void
  391. Name::toWire(OutputBuffer& buffer) const {
  392. buffer.writeData(ndata_.data(), ndata_.size());
  393. }
  394. void
  395. Name::toWire(AbstractMessageRenderer& renderer) const {
  396. renderer.writeName(*this);
  397. }
  398. std::string
  399. Name::toText(bool omit_final_dot) const {
  400. LabelSequence ls(*this);
  401. return (ls.toText(omit_final_dot));
  402. }
  403. NameComparisonResult
  404. Name::compare(const Name& other) const {
  405. return (compare(other, 0, 0, labelcount_, other.labelcount_));
  406. }
  407. NameComparisonResult
  408. Name::compare(const Name& other,
  409. unsigned int first_label,
  410. unsigned int first_label_other,
  411. unsigned int last_label,
  412. unsigned int last_label_other,
  413. bool case_sensitive) const {
  414. // Determine the relative ordering under the DNSSEC order relation of
  415. // 'this' and 'other', and also determine the hierarchical relationship
  416. // of the names.
  417. if ((first_label > last_label) ||
  418. (first_label_other > last_label_other)) {
  419. isc_throw(BadValue, "Bad label index ranges were passed");
  420. }
  421. if ((first_label > labelcount_) ||
  422. (first_label_other > other.labelcount_)) {
  423. isc_throw(BadValue, "Bad first label indices were passed");
  424. }
  425. unsigned int nlabels = 0;
  426. int l1 = last_label - first_label;
  427. int l2 = last_label_other - first_label_other;
  428. int ldiff = (int)l1 - (int)l2;
  429. unsigned int l = (ldiff < 0) ? l1 : l2;
  430. while (l > 0) {
  431. --l;
  432. --l1;
  433. --l2;
  434. size_t pos1 = offsets_[l1 + first_label];
  435. size_t pos2 = other.offsets_[l2 + first_label_other];
  436. unsigned int count1 = ndata_[pos1++];
  437. unsigned int count2 = other.ndata_[pos2++];
  438. // We don't support any extended label types including now-obsolete
  439. // bitstring labels.
  440. assert(count1 <= MAX_LABELLEN && count2 <= MAX_LABELLEN);
  441. int cdiff = (int)count1 - (int)count2;
  442. unsigned int count = (cdiff < 0) ? count1 : count2;
  443. while (count > 0) {
  444. uint8_t label1 = ndata_[pos1];
  445. uint8_t label2 = other.ndata_[pos2];
  446. int chdiff;
  447. if (case_sensitive) {
  448. chdiff = (int)label1 - (int)label2;
  449. } else {
  450. chdiff = (int)maptolower[label1] - (int)maptolower[label2];
  451. }
  452. if (chdiff != 0) {
  453. if ((nlabels == 0) &&
  454. ((last_label < labelcount_) ||
  455. (last_label_other < other.labelcount_))) {
  456. return (NameComparisonResult(0, 0,
  457. NameComparisonResult::NONE));
  458. } else {
  459. return (NameComparisonResult(chdiff, nlabels,
  460. NameComparisonResult::COMMONANCESTOR));
  461. }
  462. }
  463. --count;
  464. ++pos1;
  465. ++pos2;
  466. }
  467. if (cdiff != 0) {
  468. if ((nlabels == 0) &&
  469. ((last_label < labelcount_) ||
  470. (last_label_other < other.labelcount_))) {
  471. return (NameComparisonResult(0, 0,
  472. NameComparisonResult::NONE));
  473. } else {
  474. return (NameComparisonResult(cdiff, nlabels,
  475. NameComparisonResult::COMMONANCESTOR));
  476. }
  477. }
  478. ++nlabels;
  479. }
  480. if (ldiff < 0) {
  481. return (NameComparisonResult(ldiff, nlabels,
  482. NameComparisonResult::SUPERDOMAIN));
  483. } else if (ldiff > 0) {
  484. return (NameComparisonResult(ldiff, nlabels,
  485. NameComparisonResult::SUBDOMAIN));
  486. }
  487. return (NameComparisonResult(ldiff, nlabels, NameComparisonResult::EQUAL));
  488. }
  489. bool
  490. Name::equals(const Name& other) const {
  491. if (length_ != other.length_ || labelcount_ != other.labelcount_) {
  492. return (false);
  493. }
  494. for (unsigned int l = labelcount_, pos = 0; l > 0; --l) {
  495. uint8_t count = ndata_[pos];
  496. if (count != other.ndata_[pos]) {
  497. return (false);
  498. }
  499. ++pos;
  500. while (count-- > 0) {
  501. uint8_t label1 = ndata_[pos];
  502. uint8_t label2 = other.ndata_[pos];
  503. if (maptolower[label1] != maptolower[label2]) {
  504. return (false);
  505. }
  506. ++pos;
  507. }
  508. }
  509. return (true);
  510. }
  511. bool
  512. Name::leq(const Name& other) const {
  513. return (compare(other).getOrder() <= 0);
  514. }
  515. bool
  516. Name::geq(const Name& other) const {
  517. return (compare(other).getOrder() >= 0);
  518. }
  519. bool
  520. Name::lthan(const Name& other) const {
  521. return (compare(other).getOrder() < 0);
  522. }
  523. bool
  524. Name::gthan(const Name& other) const {
  525. return (compare(other).getOrder() > 0);
  526. }
  527. bool
  528. Name::isWildcard() const {
  529. return (length_ >= 2 && ndata_[0] == 1 && ndata_[1] == '*');
  530. }
  531. Name
  532. Name::concatenate(const Name& suffix) const {
  533. assert(length_ > 0 && suffix.length_ > 0);
  534. assert(labelcount_ > 0 && suffix.labelcount_ > 0);
  535. unsigned int length = length_ + suffix.length_ - 1;
  536. if (length > Name::MAX_WIRE) {
  537. isc_throw(TooLongName, "names are too long to concatenate");
  538. }
  539. Name retname;
  540. retname.ndata_.reserve(length);
  541. retname.ndata_.assign(ndata_, 0, length_ - 1);
  542. retname.ndata_.insert(retname.ndata_.end(),
  543. suffix.ndata_.begin(), suffix.ndata_.end());
  544. assert(retname.ndata_.size() == length);
  545. retname.length_ = length;
  546. //
  547. // Setup the offsets vector. Copy the offsets of this (prefix) name,
  548. // excluding that for the trailing dot, and append the offsets of the
  549. // suffix name with the additional offset of the length of the prefix.
  550. //
  551. unsigned int labels = labelcount_ + suffix.labelcount_ - 1;
  552. assert(labels <= Name::MAX_LABELS);
  553. retname.offsets_.reserve(labels);
  554. retname.offsets_.assign(&offsets_[0], &offsets_[0] + labelcount_ - 1);
  555. transform(suffix.offsets_.begin(), suffix.offsets_.end(),
  556. back_inserter(retname.offsets_),
  557. bind2nd(plus<char>(), length_ - 1));
  558. assert(retname.offsets_.size() == labels);
  559. retname.labelcount_ = labels;
  560. return (retname);
  561. }
  562. Name
  563. Name::reverse() const {
  564. Name retname;
  565. //
  566. // Set up offsets: The size of the string and number of labels will
  567. // be the same in as in the original.
  568. //
  569. retname.offsets_.reserve(labelcount_);
  570. retname.ndata_.reserve(length_);
  571. // Copy the original name, label by label, from tail to head.
  572. NameOffsets::const_reverse_iterator rit0 = offsets_.rbegin();
  573. NameOffsets::const_reverse_iterator rit1 = rit0 + 1;
  574. NameString::const_iterator n0 = ndata_.begin();
  575. retname.offsets_.push_back(0);
  576. while (rit1 != offsets_.rend()) {
  577. retname.ndata_.append(n0 + *rit1, n0 + *rit0);
  578. retname.offsets_.push_back(retname.ndata_.size());
  579. ++rit0;
  580. ++rit1;
  581. }
  582. retname.ndata_.push_back(0);
  583. retname.labelcount_ = labelcount_;
  584. retname.length_ = length_;
  585. return (retname);
  586. }
  587. Name
  588. Name::split(const unsigned int first, const unsigned int n) const {
  589. if (n == 0 || n > labelcount_ || first > labelcount_ - n) {
  590. isc_throw(OutOfRange, "Name::split: invalid split range");
  591. }
  592. Name retname;
  593. // If the specified range doesn't include the trailing dot, we need one
  594. // more label for that.
  595. unsigned int newlabels = (first + n == labelcount_) ? n : n + 1;
  596. //
  597. // Set up offsets: copy the corresponding range of the original offsets
  598. // with subtracting an offset of the prefix length.
  599. //
  600. retname.offsets_.reserve(newlabels);
  601. transform(offsets_.begin() + first, offsets_.begin() + first + newlabels,
  602. back_inserter(retname.offsets_),
  603. bind2nd(plus<char>(), -offsets_[first]));
  604. //
  605. // Set up the new name. At this point the tail of the new offsets specifies
  606. // the position of the trailing dot, which should be equal to the length of
  607. // the extracted portion excluding the dot. First copy that part from the
  608. // original name, and append the trailing dot explicitly.
  609. //
  610. retname.ndata_.reserve(retname.offsets_.back() + 1);
  611. retname.ndata_.assign(ndata_, offsets_[first], retname.offsets_.back());
  612. retname.ndata_.push_back(0);
  613. retname.length_ = retname.ndata_.size();
  614. retname.labelcount_ = retname.offsets_.size();
  615. assert(retname.labelcount_ == newlabels);
  616. return (retname);
  617. }
  618. Name
  619. Name::split(const unsigned int level) const {
  620. if (level >= getLabelCount()) {
  621. isc_throw(OutOfRange, "invalid level for name split (" << level
  622. << ") for name " << *this);
  623. }
  624. return (split(level, getLabelCount() - level));
  625. }
  626. Name&
  627. Name::downcase() {
  628. unsigned int nlen = length_;
  629. unsigned int labels = labelcount_;
  630. unsigned int pos = 0;
  631. while (labels > 0 && nlen > 0) {
  632. --labels;
  633. --nlen;
  634. // we assume a valid name, and do abort() if the assumption fails
  635. // rather than throwing an exception.
  636. unsigned int count = ndata_.at(pos++);
  637. assert(count <= MAX_LABELLEN);
  638. assert(nlen >= count);
  639. while (count > 0) {
  640. ndata_.at(pos) =
  641. maptolower[ndata_.at(pos)];
  642. ++pos;
  643. --nlen;
  644. --count;
  645. }
  646. }
  647. return (*this);
  648. }
  649. std::ostream&
  650. operator<<(std::ostream& os, const Name& name) {
  651. os << name.toText();
  652. return (os);
  653. }
  654. }
  655. }