name.cc 23.8 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Copyright (C) 2009  Internet Systems Consortium, Inc. ("ISC")
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided that the above
// copyright notice and this permission notice appear in all copies.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

15
16
#include <cctype>
#include <cassert>
JINMEI Tatuya's avatar
JINMEI Tatuya committed
17
#include <iterator>
JINMEI Tatuya's avatar
JINMEI Tatuya committed
18
#include <functional>
19
20
#include <vector>
#include <iostream>
21
22
#include <algorithm>

23
#include <util/buffer.h>
24
25
#include <dns/exceptions.h>
#include <dns/name.h>
26
#include <dns/name_internal.h>
27
#include <dns/messagerenderer.h>
28
#include <dns/labelsequence.h>
29

30
using namespace std;
31
using namespace isc::util;
32
using isc::dns::NameComparisonResult;
33
using namespace isc::dns::name::internal;
34
35
36
37
38
39
40
41
42

namespace isc {
namespace dns {

namespace {
///
/// These are shortcut arrays for efficient character conversion.
/// digitvalue converts a digit character to the corresponding integer.
/// maptolower convert uppercase alphabets to their lowercase counterparts.
43
/// We once used a helper non-local static object to avoid hardcoding the
44
45
46
47
/// array members, but we then realized it's susceptible to static
/// initialization order fiasco: Since these constants are used in a Name
/// constructor, a non-local static Name object defined in another translation
/// unit than this file may not be initialized correctly.
48
49
/// There are several ways to address this issue, but in this specific case
/// we chose the naive but simple hardcoding approach.
50
///
51
/// These definitions are derived from BIND 9's libdns module.
52
53
54
55
56
/// Note: we could use the standard tolower() function instead of the
/// maptolower array, but a benchmark indicated that the private array could
/// improve the performance of message rendering (which internally uses the
/// array heavily) about 27%.  Since we want to achieve very good performance
/// for message rendering in some cases, we'll keep using it.
57
const signed char digitvalue[256] = {
58
59
60
61
62
63
64
65
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 16
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 32
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 48
     0,  1,  2,  3,  4,  5,  6,  7,  8,  9, -1, -1, -1, -1, -1, -1, // 64
    -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 80
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 96
    -1, 10, 11, 12, 13, 14, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 112
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 128
66
67
68
69
70
71
72
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
73
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 256
74
};
75
}
76

77
78
namespace name {
namespace internal {
79
const uint8_t maptolower[] = {
80
81
82
83
84
85
86
87
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
    0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
    0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
    0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
88
89
90
91
    0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67, // ..., 'A' - 'G'
    0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f, // 'H' - 'O'
    0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77, // 'P' - 'W'
    0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f, // 'X' - 'Z', ...
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
    0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
    0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
    0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
    0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
    0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
    0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
    0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
    0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
    0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
    0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
    0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
    0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
    0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
    0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
    0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
    0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
    0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
    0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
    0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
    0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
112
};
113
114
} // end of internal
} // end of name
115

116
namespace {
117
118
119
///
/// Textual name parser states.
///
120
typedef enum {
121
122
123
124
125
    ft_init = 0,                // begin of the name
    ft_start,                   // begin of a label
    ft_ordinary,                // parsing an ordinary label
    ft_initialescape,           // just found '\'
    ft_escape,                  // begin of handling a '\'-escaped sequence
126
    ft_escdecimal               // parsing a '\DDD' octet.
127
128
} ft_state;

129
130
131
// The parser of name from a string. It is a template, because
// some parameters are used with two different types, while others
// are private type aliases.
132
template<class Iterator, class Offsets, class Data>
133
void
134
135
stringParse(Iterator s, Iterator send, bool downcase, Offsets& offsets,
            Data& ndata)
136
{
137
    const Iterator orig_s(s);
138
139
140
    //
    // Initialize things to make the compiler happy; they're not required.
    //
141
142
143
    unsigned int digits = 0;
    unsigned int value = 0;
    unsigned int count = 0;
144
145
146
147

    //
    // Set up the state machine.
    //
148
149
    bool done = false;
    bool is_root = false;
150
    const bool empty = s == send;
151
152
    ft_state state = ft_init;

153
    // Prepare the output buffers.
JINMEI Tatuya's avatar
JINMEI Tatuya committed
154
    offsets.reserve(Name::MAX_LABELS);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
155
156
157
    offsets.push_back(0);
    ndata.reserve(Name::MAX_WIRE);

158
159
160
161
162
    // should we refactor this code using, e.g, the state pattern?  Probably
    // not at this point, as this is based on proved code (derived from BIND9)
    // and it's less likely that we'll have more variations in the domain name
    // syntax.  If this ever happens next time, we should consider refactor
    // the code, rather than adding more states and cases below.
JINMEI Tatuya's avatar
JINMEI Tatuya committed
163
    while (ndata.size() < Name::MAX_WIRE && s != send && !done) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
164
        unsigned char c = *s++;
165
166
167

        switch (state) {
        case ft_init:
168
169
170
            //
            // Is this the root name?
            //
171
            if (c == '.') {
172
                if (s != send) {
173
                    isc_throw(EmptyLabel,
174
175
                              "non terminating empty label in " <<
                              string(orig_s, send));
176
177
178
179
180
181
182
183
                }
                is_root = true;
            } else if (c == '@' && s == send) {
                // handle a single '@' as the root name.
                is_root = true;
            }

            if (is_root) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
184
                ndata.push_back(0);
185
186
187
188
                done = true;
                break;
            }

189
            // FALLTHROUGH
190
        case ft_start:
JINMEI Tatuya's avatar
JINMEI Tatuya committed
191
            ndata.push_back(0); // placeholder for the label length field
192
193
194
195
196
197
            count = 0;
            if (c == '\\') {
                state = ft_initialescape;
                break;
            }
            state = ft_ordinary;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
198
            assert(ndata.size() < Name::MAX_WIRE);
199
            // FALLTHROUGH
200
        case ft_ordinary:
201
            if (c == '.') {
202
                if (count == 0) {
203
                    isc_throw(EmptyLabel,
204
                              "duplicate period in " << string(orig_s, send));
205
                }
JINMEI Tatuya's avatar
JINMEI Tatuya committed
206
207
                ndata.at(offsets.back()) = count;
                offsets.push_back(ndata.size());
208
                if (s == send) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
209
                    ndata.push_back(0);
210
211
212
213
214
215
                    done = true;
                }
                state = ft_start;
            } else if (c == '\\') {
                state = ft_escape;
            } else {
216
                if (++count > Name::MAX_LABELLEN) {
217
                    isc_throw(TooLongLabel,
218
                              "label is too long in " << string(orig_s, send));
219
                }
JINMEI Tatuya's avatar
JINMEI Tatuya committed
220
                ndata.push_back(downcase ? maptolower[c] : c);
221
222
            }
            break;
223
        case ft_initialescape:
224
            if (c == '[') {
225
226
                // This looks like a bitstring label, which was deprecated.
                // Intentionally drop it.
227
                isc_throw(BadLabelType,
228
                          "invalid label type in " << string(orig_s, send));
229
            }
230
            // FALLTHROUGH
231
        case ft_escape:
232
            if (!isdigit(c & 0xff)) {
233
                if (++count > Name::MAX_LABELLEN) {
234
                    isc_throw(TooLongLabel,
235
                              "label is too long in " << string(orig_s, send));
236
                }
JINMEI Tatuya's avatar
JINMEI Tatuya committed
237
                ndata.push_back(downcase ? maptolower[c] : c);
238
239
240
241
242
243
                state = ft_ordinary;
                break;
            }
            digits = 0;
            value = 0;
            state = ft_escdecimal;
244
            // FALLTHROUGH
245
        case ft_escdecimal:
246
            if (!isdigit(c & 0xff)) {
247
                isc_throw(BadEscape,
248
                          "mixture of escaped digit and non-digit in "
249
                          << string(orig_s, send));
250
            }
251
            value *= 10;
252
            value += digitvalue[c];
253
254
            digits++;
            if (digits == 3) {
255
                if (value > 255) {
256
                    isc_throw(BadEscape,
257
                              "escaped decimal is too large in "
258
                              << string(orig_s, send));
259
                }
260
                if (++count > Name::MAX_LABELLEN) {
261
                    isc_throw(TooLongLabel,
262
                              "label is too long in " << string(orig_s, send));
263
                }
JINMEI Tatuya's avatar
JINMEI Tatuya committed
264
                ndata.push_back(downcase ? maptolower[value] : value);
265
266
267
268
                state = ft_ordinary;
            }
            break;
        default:
269
270
            // impossible case
            assert(false);
271
272
273
        }
    }

274
    if (!done) {                // no trailing '.' was found.
JINMEI Tatuya's avatar
JINMEI Tatuya committed
275
        if (ndata.size() == Name::MAX_WIRE) {
276
            isc_throw(TooLongName,
277
278
                      "name is too long for termination in " <<
                      string(orig_s, send));
279
280
        }
        assert(s == send);
281
        if (state != ft_ordinary) {
282
283
            isc_throw(IncompleteName,
                      "incomplete textual name in " <<
284
                      (empty ? "<empty>" : string(orig_s, send)));
285
        }
286
        if (state == ft_ordinary) {
287
            assert(count != 0);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
288
            ndata.at(offsets.back()) = count;
289

JINMEI Tatuya's avatar
JINMEI Tatuya committed
290
            offsets.push_back(ndata.size());
291
            // add a trailing \0
JINMEI Tatuya's avatar
JINMEI Tatuya committed
292
            ndata.push_back('\0');
293
294
        }
    }
295
296
297
298
299
300
}

}

Name::Name(const std::string &namestring, bool downcase) {
    // Prepare inputs for the parser
301
302
    const std::string::const_iterator s = namestring.begin();
    const std::string::const_iterator send = namestring.end();
303
304
305
306
307
308

    // Prepare outputs
    NameOffsets offsets;
    NameString ndata;

    // To the parsing
309
    stringParse(s, send, downcase, offsets, ndata);
310

311
    // And get the output
312
313
    labelcount_ = offsets.size();
    assert(labelcount_ > 0 && labelcount_ <= Name::MAX_LABELS);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
314
    ndata_.assign(ndata.data(), ndata.size());
315
316
    length_ = ndata_.size();
    offsets_.assign(offsets.begin(), offsets.end());
317
318
}

319
320
321
Name::Name(const char* namedata, size_t data_len, const Name* origin,
           bool downcase)
{
322
323
324
325
326
    // Check validity of data
    if (namedata == NULL || data_len == 0) {
        isc_throw(isc::InvalidParameter,
                  "No data provided to Name constructor");
    }
327
328
329
330
331
332
333
334
    // If the last character is not a dot, it is a relative to origin.
    // It is safe to check now, we know there's at least one character.
    const bool absolute = (namedata[data_len - 1] == '.');
    // If we are not absolute, we need the origin to complete the name.
    if (!absolute && origin == NULL) {
        isc_throw(MissingNameOrigin,
                  "No origin available and name is relative");
    }
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
    // Prepare inputs for the parser
    const char* end = namedata + data_len;

    // Prepare outputs
    NameOffsets offsets;
    NameString ndata;

    // Do the actual parsing
    stringParse(namedata, end, downcase, offsets, ndata);

    // Get the output
    labelcount_ = offsets.size();
    assert(labelcount_ > 0 && labelcount_ <= Name::MAX_LABELS);
    ndata_.assign(ndata.data(), ndata.size());
    length_ = ndata_.size();
    offsets_.assign(offsets.begin(), offsets.end());
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381

    if (!absolute) {
        // Now, extend the data with the ones from origin. But eat the
        // last label (the empty one).

        // Drop the last character of the data (the \0) and append a copy of
        // the origin's data
        ndata_.erase(ndata_.end() - 1);
        ndata_.append(origin->ndata_);

        // Do a similar thing with offsets. However, we need to move them
        // so they point after the prefix we parsed before.
        size_t offset = offsets_.back();
        offsets_.pop_back();
        size_t offset_count = offsets_.size();
        offsets_.insert(offsets_.end(), origin->offsets_.begin(),
                        origin->offsets_.end());
        for (NameOffsets::iterator it(offsets_.begin() + offset_count);
             it != offsets_.end(); ++it) {
            *it += offset;
        }

        // Adjust sizes.
        length_ = ndata_.size();
        labelcount_ = offsets_.size();

        // And check the sizes are OK.
        if (labelcount_ > Name::MAX_LABELS || length_ > Name::MAX_WIRE) {
            isc_throw(TooLongName, "Combined name is too long");
        }
    }
382
383
}

384
385
386
387
namespace {
///
/// Wire-format name parser states.
///
388
typedef enum {
389
390
391
    fw_start = 0,               // beginning of a label
    fw_ordinary,                // inside an ordinary (non compressed) label
    fw_newcurrent               // beginning of a compression pointer
392
} fw_state;
393
}
394

395
Name::Name(InputBuffer& buffer, bool downcase) {
396
    NameOffsets offsets;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
397
    offsets.reserve(Name::MAX_LABELS);
398
399

    /*
400
     * Initialize things to make the compiler happy; they're not required.
401
     */
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
    unsigned int n = 0;

    //
    // Set up.
    //
    bool done = false;
    unsigned int nused = 0;
    bool seen_pointer = false;
    fw_state state = fw_start;

    unsigned int cused = 0;     // Bytes of compressed name data used
    unsigned int current = buffer.getPosition();
    unsigned int pos_begin = current;
    unsigned int biggest_pointer = current;

417
418
419
420
421
    // Make the compiler happy; this is not required.
    // XXX: bad style in that we initialize it with a dummy value and define
    // it far from where it's used.  But alternatives seemed even worse.
    unsigned int new_current = 0;

422
423
424
425
426
427
428
429
430
431
432
433
434
    //
    // Note:  The following code is not optimized for speed, but
    // rather for correctness.  Speed will be addressed in the future.
    //
    while (current < buffer.getLength() && !done) {
        unsigned int c = buffer.readUint8();
        current++;
        if (!seen_pointer) {
            cused++;
        }

        switch (state) {
        case fw_start:
435
            if (c <= MAX_LABELLEN) {
436
437
                offsets.push_back(nused);
                if (nused + c + 1 > Name::MAX_WIRE) {
438
439
                    isc_throw(DNSMessageFORMERR, "wire name is too long: "
                              << nused + c + 1 << " bytes");
440
441
442
443
444
445
446
447
                }
                nused += c + 1;
                ndata_.push_back(c);
                if (c == 0) {
                    done = true;
                }
                n = c;
                state = fw_ordinary;
448
            } else if ((c & COMPRESS_POINTER_MARK8) == COMPRESS_POINTER_MARK8) {
449
450
451
                //
                // Ordinary 14-bit pointer.
                //
452
                new_current = c & ~COMPRESS_POINTER_MARK8;
453
454
455
456
457
                n = 1;
                state = fw_newcurrent;
            } else {
                // this case includes local compression pointer, which hasn't
                // been standardized.
458
                isc_throw(DNSMessageFORMERR, "unknown label character: " << c);
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
            }
            break;
        case fw_ordinary:
            if (downcase) {
                c = maptolower[c];
            }
            ndata_.push_back(c);
            if (--n == 0) {
                state = fw_start;
            }
            break;
        case fw_newcurrent:
            new_current *= 256;
            new_current += c;
            if (--n != 0) {
                break;
            }
            if (new_current >= biggest_pointer) {
477
478
479
                isc_throw(DNSMessageFORMERR,
                          "bad compression pointer (out of range): " <<
                          new_current);
480
481
482
483
484
485
486
487
488
489
490
491
492
            }
            biggest_pointer = new_current;
            current = new_current;
            buffer.setPosition(current);
            seen_pointer = true;
            state = fw_start;
            break;
        default:
            assert(false);
        }
    }

    if (!done) {
493
        isc_throw(DNSMessageFORMERR, "incomplete wire-format name");
494
495
    }

496
    labelcount_ = offsets.size();
497
498
499
500
501
502
    length_ = nused;
    offsets_.assign(offsets.begin(), offsets.end());
    buffer.setPosition(pos_begin + cused);
}

void
503
Name::toWire(OutputBuffer& buffer) const {
504
505
506
507
    buffer.writeData(ndata_.data(), ndata_.size());
}

void
508
Name::toWire(AbstractMessageRenderer& renderer) const {
509
510
511
    renderer.writeName(*this);
}

512
513
std::string
Name::toText(bool omit_final_dot) const {
514
515
    LabelSequence ls(*this);
    return (ls.toText(omit_final_dot));
516
517
}

518
NameComparisonResult
519
Name::compare(const Name& other) const {
520
521
522
    const LabelSequence ls1(*this);
    const LabelSequence ls2(other);
    return (ls1.compare(ls2));
523
524
525
}

bool
526
Name::equals(const Name& other) const {
527
    if (length_ != other.length_ || labelcount_ != other.labelcount_) {
528
        return (false);
529
    }
530

531
    for (unsigned int l = labelcount_, pos = 0; l > 0; --l) {
532
        uint8_t count = ndata_[pos];
JINMEI Tatuya's avatar
JINMEI Tatuya committed
533
        if (count != other.ndata_[pos]) {
534
            return (false);
535
        }
JINMEI Tatuya's avatar
JINMEI Tatuya committed
536
        ++pos;
537

538
        while (count-- > 0) {
539
540
            uint8_t label1 = ndata_[pos];
            uint8_t label2 = other.ndata_[pos];
JINMEI Tatuya's avatar
JINMEI Tatuya committed
541
542

            if (maptolower[label1] != maptolower[label2]) {
543
                return (false);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
544
545
            }
            ++pos;
546
547
548
549
550
551
        }
    }

    return (true);
}

JINMEI Tatuya's avatar
JINMEI Tatuya committed
552
bool
553
Name::leq(const Name& other) const {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
554
555
556
557
    return (compare(other).getOrder() <= 0);
}

bool
558
Name::geq(const Name& other) const {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
559
560
561
562
    return (compare(other).getOrder() >= 0);
}

bool
563
Name::lthan(const Name& other) const {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
564
565
566
567
    return (compare(other).getOrder() < 0);
}

bool
568
Name::gthan(const Name& other) const {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
569
570
571
    return (compare(other).getOrder() > 0);
}

572
bool
573
Name::isWildcard() const {
574
    return (length_ >= 2 && ndata_[0] == 1 && ndata_[1] == '*');
575
576
}

JINMEI Tatuya's avatar
JINMEI Tatuya committed
577
Name
578
Name::concatenate(const Name& suffix) const {
579
580
    assert(length_ > 0 && suffix.length_ > 0);
    assert(labelcount_ > 0 && suffix.labelcount_ > 0);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
581

582
    unsigned int length = length_ + suffix.length_ - 1;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
583
    if (length > Name::MAX_WIRE) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
584
        isc_throw(TooLongName, "names are too long to concatenate");
JINMEI Tatuya's avatar
JINMEI Tatuya committed
585
586
587
588
    }

    Name retname;
    retname.ndata_.reserve(length);
589
    retname.ndata_.assign(ndata_, 0, length_ - 1);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
590
591
592
593
594
    retname.ndata_.insert(retname.ndata_.end(),
                          suffix.ndata_.begin(), suffix.ndata_.end());
    assert(retname.ndata_.size() == length);
    retname.length_ = length;

JINMEI Tatuya's avatar
JINMEI Tatuya committed
595
596
597
598
599
    //
    // Setup the offsets vector.  Copy the offsets of this (prefix) name,
    // excluding that for the trailing dot, and append the offsets of the
    // suffix name with the additional offset of the length of the prefix.
    //
600
    unsigned int labels = labelcount_ + suffix.labelcount_ - 1;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
601
602
    assert(labels <= Name::MAX_LABELS);
    retname.offsets_.reserve(labels);
603
    retname.offsets_.assign(&offsets_[0], &offsets_[0] + labelcount_ - 1);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
604
605
    transform(suffix.offsets_.begin(), suffix.offsets_.end(),
              back_inserter(retname.offsets_),
606
              bind2nd(plus<char>(), length_ - 1));
JINMEI Tatuya's avatar
JINMEI Tatuya committed
607
    assert(retname.offsets_.size() == labels);
608
    retname.labelcount_ = labels;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
609
610
611
612

    return (retname);
}

613
Name
614
Name::reverse() const {
615
616
617
618
619
620
621
622
623
    Name retname;
    //
    // Set up offsets: The size of the string and number of labels will
    // be the same in as in the original.
    //
    retname.offsets_.reserve(labelcount_);
    retname.ndata_.reserve(length_);

    // Copy the original name, label by label, from tail to head.
624
625
    NameOffsets::const_reverse_iterator rit0 = offsets_.rbegin();
    NameOffsets::const_reverse_iterator rit1 = rit0 + 1;
626
    NameString::const_iterator n0 = ndata_.begin();
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
    retname.offsets_.push_back(0);
    while (rit1 != offsets_.rend()) {
        retname.ndata_.append(n0 + *rit1, n0 + *rit0);
        retname.offsets_.push_back(retname.ndata_.size());
        ++rit0;
        ++rit1;
    }
    retname.ndata_.push_back(0);

    retname.labelcount_ = labelcount_;
    retname.length_ = length_;

    return (retname);
}

JINMEI Tatuya's avatar
JINMEI Tatuya committed
642
Name
643
Name::split(const unsigned int first, const unsigned int n) const {
644
    if (n == 0 || n > labelcount_ || first > labelcount_ - n) {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
645
        isc_throw(OutOfRange, "Name::split: invalid split range");
JINMEI Tatuya's avatar
JINMEI Tatuya committed
646
647
648
    }

    Name retname;
649
650
    // If the specified range doesn't include the trailing dot, we need one
    // more label for that.
651
    unsigned int newlabels = (first + n == labelcount_) ? n : n + 1;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
652

653
654
655
656
    //
    // Set up offsets: copy the corresponding range of the original offsets
    // with subtracting an offset of the prefix length.
    //
JINMEI Tatuya's avatar
JINMEI Tatuya committed
657
658
659
    retname.offsets_.reserve(newlabels);
    transform(offsets_.begin() + first, offsets_.begin() + first + newlabels,
              back_inserter(retname.offsets_),
660
              bind2nd(plus<char>(), -offsets_[first]));
JINMEI Tatuya's avatar
JINMEI Tatuya committed
661

662
663
664
665
666
667
    //
    // Set up the new name.  At this point the tail of the new offsets specifies
    // the position of the trailing dot, which should be equal to the length of
    // the extracted portion excluding the dot.  First copy that part from the
    // original name, and append the trailing dot explicitly.
    //
JINMEI Tatuya's avatar
JINMEI Tatuya committed
668
669
670
671
672
    retname.ndata_.reserve(retname.offsets_.back() + 1);
    retname.ndata_.assign(ndata_, offsets_[first], retname.offsets_.back());
    retname.ndata_.push_back(0);

    retname.length_ = retname.ndata_.size();
673
674
    retname.labelcount_ = retname.offsets_.size();
    assert(retname.labelcount_ == newlabels);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
675
676
677

    return (retname);
}
JINMEI Tatuya's avatar
JINMEI Tatuya committed
678

679
Name
680
Name::split(const unsigned int level) const {
681
682
683
684
685
686
687
688
    if (level >= getLabelCount()) {
        isc_throw(OutOfRange, "invalid level for name split (" << level
                  << ") for name " << *this);
    }

    return (split(level, getLabelCount() - level));
}

JINMEI Tatuya's avatar
JINMEI Tatuya committed
689
Name&
690
Name::downcase() {
JINMEI Tatuya's avatar
JINMEI Tatuya committed
691
    unsigned int nlen = length_;
692
    unsigned int labels = labelcount_;
JINMEI Tatuya's avatar
JINMEI Tatuya committed
693
694
695
696
697
698
699
700
701
    unsigned int pos = 0;

    while (labels > 0 && nlen > 0) {
        --labels;
        --nlen;

        // we assume a valid name, and do abort() if the assumption fails
        // rather than throwing an exception.
        unsigned int count = ndata_.at(pos++);
702
        assert(count <= MAX_LABELLEN);
JINMEI Tatuya's avatar
JINMEI Tatuya committed
703
704
705
706
        assert(nlen >= count);

        while (count > 0) {
            ndata_.at(pos) =
707
                maptolower[ndata_.at(pos)];
JINMEI Tatuya's avatar
JINMEI Tatuya committed
708
709
710
711
712
713
714
715
            ++pos;
            --nlen;
            --count;
        }
    }

    return (*this);
}
JINMEI Tatuya's avatar
JINMEI Tatuya committed
716

717
std::ostream&
718
operator<<(std::ostream& os, const Name& name) {
719
    os << name.toText();
720
721
    return (os);
}
722

723
724
}
}