labelsequence.h 16.8 KB
Newer Older
Jelte Jansen's avatar
Jelte Jansen committed
1
// Copyright (C) 2012  Internet Systems Consortium, Inc. ("ISC")
Jelte Jansen's avatar
Jelte Jansen committed
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//
// 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.

#ifndef __LABELSEQUENCE_H
#define __LABELSEQUENCE_H 1

#include <dns/name.h>
#include <util/buffer.h>

namespace isc {
namespace dns {

24
/// \brief Light-weight Accessor to Name data.
Jelte Jansen's avatar
Jelte Jansen committed
25
26
///
/// The purpose of this class is to easily match Names and parts of Names,
Jelte Jansen's avatar
Jelte Jansen committed
27
/// without needing to copy the underlying data on each label strip.
Jelte Jansen's avatar
Jelte Jansen committed
28
///
Jelte Jansen's avatar
Jelte Jansen committed
29
30
/// It can only work on existing Name objects, or data as provided by the
/// Name object or another LabelSequence, and the data or Name MUST
Jelte Jansen's avatar
Jelte Jansen committed
31
32
33
34
/// remain in scope during the entire lifetime of its associated
/// LabelSequence(s).
///
/// Upon creation of a LabelSequence, it records the offsets of the
Jelte Jansen's avatar
Jelte Jansen committed
35
36
/// labels in the wireformat data of the Name. When stripLeft() or
/// stripRight() is called on the LabelSequence, no changes in the
Jelte Jansen's avatar
Jelte Jansen committed
37
/// original data occur, but the internal pointers of the
Jelte Jansen's avatar
Jelte Jansen committed
38
/// LabelSequence are modified.
Jelte Jansen's avatar
Jelte Jansen committed
39
40
41
///
/// LabelSequences can be compared to other LabelSequences, and their
/// data can be requested (which then points to part of the original
Jelte Jansen's avatar
Jelte Jansen committed
42
/// data of the original Name object).
Jelte Jansen's avatar
Jelte Jansen committed
43
class LabelSequence {
44
45
46
    // Name calls the private toText(bool) method of LabelSequence.
    friend std::string Name::toText(bool) const;

Jelte Jansen's avatar
Jelte Jansen committed
47
public:
48
49
50
51
52
53
54
55
    /// \brief Max possible size of serialized image generated by \c serialize
    ///
    /// A fixed length buffer of this size can be always passed to
    /// \c serialize() safely.  (But the application shouldn't use the
    /// specific size value; it must use this constant variable).
    static const size_t MAX_SERIALIZED_LENGTH =
        Name::MAX_WIRE + Name::MAX_LABELS + 1;

Jelte Jansen's avatar
Jelte Jansen committed
56
57
58
59
60
61
62
63
    /// \brief Constructs a LabelSequence for the given name
    ///
    /// \note The associated Name MUST remain in scope during the lifetime
    /// of this LabelSequence, since getData() refers to data from the
    /// Name object (the only data the LabelSequence stores are pointers
    /// to the labels in the Name object).
    ///
    /// \param name The Name to construct a LabelSequence for
Jelte Jansen's avatar
Jelte Jansen committed
64
    explicit LabelSequence(const Name& name):
65
66
67
68
        data_(&name.ndata_[0]),
        offsets_(&name.offsets_[0]),
        first_label_(0),
        last_label_(name.getLabelCount() - 1)
Jelte Jansen's avatar
Jelte Jansen committed
69
    {}
Jelte Jansen's avatar
Jelte Jansen committed
70

71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
    /// \brief Constructor from serialized image.
    ///
    /// This constructor restores a \c LabelSequence object from a serialized
    /// binary image previously generated by \c serialize().  Any other input
    /// to this constructor will result in undefined behavior.
    ///
    /// The binary data passed to this constructor MUST remain in scope and
    /// MUST NOT be modified during the lifetime of this LabelSequence.
    ///
    /// As long as the data were previously generated by a call to
    /// \c serialize() on a valid \c LabelSequence object, this constructor
    /// should succeed.  While any other case is undefined, this constructor
    /// may perform some validity checks internally for safety.  Nevertheless,
    /// applications must not rely on such checks.
    ///
    /// \param buf Pointer to the serialized image generated by \c serialize().
    explicit LabelSequence(const void* buf);

89
90
91
92
93
94
    /// \brief Construct 'extendable' LabelSequence
    ///
    /// This form of LabelSequence copies the data from the given
    /// labelsequence into the given external buffer, which is subsequently
    /// extendable by calling extend()
    ///
95
96
97
98
99
100
101
102
103
104
105
    /// The data is placed into the given buffer as follows:
    /// - binary sequence of name data, starting at position 0,
    ///   length determined by source LabelSequence
    /// - offsets, starting at position Name::MAX_WIRE, length
    ///   determined by source LabelSequence
    /// The offsets are updated to be correct for the potentially partial
    /// name data (as stripLeft() and stripRight may have been called on
    /// the source LabelSequence).
    ///
    /// \note The given buf MUST remain in scope during the lifetime of
    /// the LabelSequence created here.
106
107
108
109
110
    /// \note The buffer should never be modified except through
    /// calls to extend().
    /// \note Also, only associate the buffer with at most one
    /// LabelSequence. Behaviour is undefined if two LabelSequences are
    /// using the same buffer.
111
    ///
112
113
114
115
    /// \param src LabelSequence to copy the initial data from
    /// \param buf external buffer to store this labelsequence's data in
    LabelSequence(const LabelSequence& src, uint8_t buf[MAX_SERIALIZED_LENGTH]);

116
117
118
119
120
121
122
123
124
125
    /// \brief Copy constructor.
    ///
    /// \note The associated data MUST remain in scope during the lifetime
    /// of this LabelSequence, since only the pointers are copied.
    ///
    /// \note No validation is done on the given data upon construction;
    ///       use with care.
    ///
    /// \param ls The LabelSequence to construct a LabelSequence from
    LabelSequence(const LabelSequence& ls):
126
127
128
129
        data_(ls.data_),
        offsets_(ls.offsets_),
        first_label_(ls.first_label_),
        last_label_(ls.last_label_)
130
131
    {}

Jelte Jansen's avatar
Jelte Jansen committed
132
133
    /// \brief Return the wire-format data for this LabelSequence
    ///
Jelte Jansen's avatar
Jelte Jansen committed
134
135
136
    /// The data is returned as a pointer to (the part of) the original
    /// wireformat data, from either the original Name object, or the
    /// raw data given in the constructor, and the given len value is
Jelte Jansen's avatar
Jelte Jansen committed
137
138
139
    /// set to the number of octets that match this labelsequence.
    ///
    /// \note The data pointed to is only valid if the original Name
Jelte Jansen's avatar
Jelte Jansen committed
140
    /// object or data is still in scope
Jelte Jansen's avatar
Jelte Jansen committed
141
142
    ///
    /// \param len Pointer to a size_t where the length of the data
Jelte Jansen's avatar
Jelte Jansen committed
143
    ///        will be stored (in number of octets)
Jelte Jansen's avatar
Jelte Jansen committed
144
    /// \return Pointer to the wire-format data of this label sequence
145
    const uint8_t* getData(size_t* len) const;
Jelte Jansen's avatar
Jelte Jansen committed
146

147
148
149
150
151
152
153
154
155
156
157
    /// \brief Return the length of the wire-format data of this LabelSequence
    ///
    /// This method returns the number of octets for the data that would
    /// be returned by the \c getData() method.
    ///
    /// Note that the return value of this method is always positive.
    /// Note also that if the return value of this method is 1, it means the
    /// sequence consists of the null label, i.e., a single "dot", and vice
    /// versa.
    ///
    /// \note The data pointed to is only valid if the original Name
Jelte Jansen's avatar
Jelte Jansen committed
158
    /// object or data is still in scope
159
160
161
162
    ///
    /// \return The length of the data of the label sequence in octets.
    size_t getDataLength() const;

163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
    /// \brief Return the size of serialized image of the \c LabelSequence.
    ///
    /// This method calculates the size of necessary storage to store
    /// serialized image of this \c LabelSequence (which would be dumped by
    /// \c serialize()) and returns it.  The size is in bytes.
    ///
    /// \throw none.
    ///
    /// \return The size of serialized image of the \c LabelSequence.
    size_t getSerializedLength() const;

    /// \brief Serialize the \c LabelSequence object in to a buffer.
    ///
    /// This method dumps a serialized image of this \c LabelSequence
    /// that would be restored by the corresponding constructor into the
    /// given buffer.  The buffer size must be at least equal to
    /// the value returned by getSerializedLength() (it can be larger than
    /// that).
    ///
    /// The serialized image would be as follows:
    /// - olen: number of offsets (1 byte)
    /// - binary sequence of offsets (olen bytes, verbatim copy of offsets_
    ///   of this size)
    /// - binary sequence of name data (length determined by itself, verbatim
    ///   copy of data_ of the corresponding size)
    ///
    /// Applications must use the resulting image opaque value and must not
    /// use it for other purposes than input to the corresponding constructor
    /// to restore it.  Application behavior that assumes the specific
    /// organization of the image is not guaranteed.
    ///
    /// \throw isc::BadValue buf_len is too short (this method never throws
    /// otherwise)
    ///
    /// \param buf Pointer to the placeholder to dump the serialized image
    /// \param buf_len The size of available region in \c buf
    void serialize(void* buf, size_t buf_len) const;

201
    /// \brief Compares two label sequences for equality.
Jelte Jansen's avatar
Jelte Jansen committed
202
    ///
203
    /// Performs a (optionally case-sensitive) comparison between this
204
    /// LabelSequence and another LabelSequence for equality.
Jelte Jansen's avatar
Jelte Jansen committed
205
206
207
208
209
    ///
    /// \param other The LabelSequence to compare with
    /// \param case_sensitive If true, comparison is case-insensitive
    /// \return true if The label sequences consist are the same length,
    ///         and contain the same data.
Jelte Jansen's avatar
Jelte Jansen committed
210
211
    bool equals(const LabelSequence& other, bool case_sensitive = false) const;

212
213
214
215
216
217
218
219
220
221
    /// \brief Compares two label sequences for equality (case ignored).
    ///
    /// This is equivalent to <code>this->equals(other)</code>.
    ///
    /// The operator version is convenient some specific cases such as in
    /// unit tests.
    bool operator==(const LabelSequence& other) const {
        return (equals(other));
    }

222
223
224
225
226
227
228
229
230
231
232
233
    /// \brief Compares two label sequences.
    ///
    /// Performs a (optionally case-insensitive) comparison between this
    /// LabelSequence and another LabelSequence.
    ///
    /// \param other The LabelSequence to compare with
    /// \param case_sensitive If true, comparison is case-insensitive
    /// \return a <code>NameComparisonResult</code> object representing the
    /// comparison result.
    NameComparisonResult compare(const LabelSequence& other,
                                 bool case_sensitive = false) const;

Jelte Jansen's avatar
Jelte Jansen committed
234
    /// \brief Remove labels from the front of this LabelSequence
Jelte Jansen's avatar
Jelte Jansen committed
235
    ///
Jelte Jansen's avatar
Jelte Jansen committed
236
237
238
    /// \note No actual memory is changed, this operation merely updates the
    /// internal pointers based on the offsets in the Name object.
    ///
239
    /// \exception OutOfRange if i is greater than or equal to the number
Jelte Jansen's avatar
Jelte Jansen committed
240
241
242
    ///           of labels currently pointed to by this LabelSequence
    ///
    /// \param i The number of labels to remove.
Jelte Jansen's avatar
Jelte Jansen committed
243
    void stripLeft(size_t i);
Jelte Jansen's avatar
Jelte Jansen committed
244
245

    /// \brief Remove labels from the end of this LabelSequence
Jelte Jansen's avatar
Jelte Jansen committed
246
247
    ///
    /// \note No actual memory is changed, this operation merely updates the
Jelte Jansen's avatar
Jelte Jansen committed
248
    /// internal pointers based on the offsets originally provided.
Jelte Jansen's avatar
Jelte Jansen committed
249
    ///
250
    /// \exception OutOfRange if i is greater than or equal to the number
Jelte Jansen's avatar
Jelte Jansen committed
251
    ///           of labels currently pointed to by this LabelSequence
Jelte Jansen's avatar
Jelte Jansen committed
252
    ///
Jelte Jansen's avatar
Jelte Jansen committed
253
    /// \param i The number of labels to remove.
Jelte Jansen's avatar
Jelte Jansen committed
254
    void stripRight(size_t i);
Jelte Jansen's avatar
Jelte Jansen committed
255

Jelte Jansen's avatar
Jelte Jansen committed
256
257
258
    /// \brief Returns the current number of labels for this LabelSequence
    ///
    /// \return The number of labels
259
260
261
    size_t getLabelCount() const {
        return (last_label_ - first_label_ + 1);
    }
262

263
264
265
266
    /// \brief Convert the LabelSequence to a string.
    ///
    /// This method returns a <code>std::string</code> object representing the
    /// LabelSequence as a string.  The returned string ends with a dot
267
    /// '.' if the label sequence is absolute.
268
    ///
Jelte Jansen's avatar
Jelte Jansen committed
269
    /// This function assumes the underlying data is in proper
270
271
272
273
274
    /// uncompressed wire format.  If it finds an unexpected label
    /// character including compression pointer, an exception of class
    /// \c BadLabelType will be thrown.  In addition, if resource
    /// allocation for the result string fails, a corresponding standard
    /// exception will be thrown.
Jelte Jansen's avatar
Jelte Jansen committed
275
    ///
276
    /// \return a string representation of the <code>LabelSequence</code>.
277
    std::string toText() const;
278

279
280
    /// \brief Extend this LabelSequence with the given labelsequence
    ///
Jelte Jansen's avatar
Jelte Jansen committed
281
282
    /// The given labels are appended to the name data, and internal
    /// offset data is updated accordingly.
283
    ///
284
285
    /// The data from the given LabelSequence is copied into the buffer
    /// associated with this LabelSequence; the appended LabelSequence
Jelte Jansen's avatar
Jelte Jansen committed
286
287
    /// (the 'labels' argument) can be released if it is not needed for
    /// other operations anymore.
288
    ///
289
290
291
292
293
294
295
    /// If this LabelSequence is absolute, its root label will be stripped
    /// before the given LabelSequence is appended; after extend(),
    /// this LabelSequence will be absolute if, and only if, the appended
    /// LabelSequence was. A side-effect of this property is that adding
    /// the root label to an absolute LabelSequence has no effect (the
    /// root label is stripped, then added again).
    ///
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
    /// Some minimal checking is done on the data, but internal integrity
    /// is not assumed. Do NOT modify the given buffer except through calls
    /// to this method, and do NOT call this method if the buffer is
    /// associated to another LabelSequence (behaviour of the other
    /// LabelSequence is undefined in that scenario).
    ///
    /// \exception BadValue If the buffer does not appear to be associated
    /// with this LabelSequence, or if the maximum wire length or maximum
    /// number of labels would be exceeded by this operation
    ///
    /// \param labels The labels to append to this LabelSequence
    /// \param buf The buffer associated with this LabelSequence
    void extend(const LabelSequence& labels,
                uint8_t buf[MAX_SERIALIZED_LENGTH]);

311
private:
312
313
    /// \brief Convert the LabelSequence to a string.
    ///
314
315
316
317
    /// This method is a version of the zero-argument toText() method,
    /// that accepts a <code>omit_final_dot</code> argument. The
    /// returned string ends with a dot '.' if
    /// <code>omit_final_dot</code> is <code>false</code>.
318
    ///
319
320
321
    /// This method is used as a helper for <code>Name::toText()</code>
    /// only.
    ///
322
    /// \param omit_final_dot whether to omit the trailing dot in the output.
323
    /// \return a string representation of the <code>LabelSequence</code>.
324
    std::string toText(bool omit_final_dot) const;
325

326
public:
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
    /// \brief Calculate a simple hash for the label sequence.
    ///
    /// This method calculates a hash value for the label sequence as binary
    /// data.  If \c case_sensitive is false, it ignores the case stored in
    /// the labels; specifically, it normalizes the labels by converting all
    /// upper case characters to lower case ones and calculates the hash value
    /// for the result.
    ///
    /// This method is intended to provide a lightweight way to store a
    /// relatively small number of label sequences in a hash table.
    /// For this reason it only takes into account data up to 16 octets
    /// (16 was derived from BIND 9's implementation).  Also, the function does
    /// not provide any unpredictability; a specific sequence will always have
    /// the same hash value.  It should therefore not be used in the context
    /// where an untrusted third party can mount a denial of service attack by
    /// forcing the application to create a very large number of label
    /// sequences that have the same hash value and expected to be stored in
    /// a hash table.
    ///
    /// \exception None
    ///
    /// \param case_sensitive
    /// \return A hash value for this label sequence.
    size_t getHash(bool case_sensitive) const;

Jelte Jansen's avatar
Jelte Jansen committed
352
353
354
355
356
    /// \brief Checks whether the label sequence is absolute
    ///
    /// \return true if the last label is the root label
    bool isAbsolute() const;

Jelte Jansen's avatar
Jelte Jansen committed
357
private:
358
359
360
361
362
363
    const uint8_t* data_;       // wire-format name data
    const uint8_t* offsets_;    // an array of offsets in data_ for the labels
    size_t first_label_;        // index of offsets_ for the first label
    size_t last_label_;         // index of offsets_ for the last label.
                                // can be equal to first_label_, but must not
                                // be smaller (the class ensures that)
Jelte Jansen's avatar
Jelte Jansen committed
364
365
366
};


367
368
369
370
371
372
373
374
375
376
377
///
/// \brief Insert the label sequence as a string into stream.
///
/// This method convert the \c label_sequence into a string and inserts
/// it into the output stream \c os.
///
/// This function overloads the global operator<< to behave as described in
/// ostream::operator<< but applied to \c LabelSequence objects.
///
/// \param os A \c std::ostream object on which the insertion operation is
/// performed.
Jelte Jansen's avatar
Jelte Jansen committed
378
/// \param label_sequence The \c LabelSequence object output by the operation.
379
380
381
382
383
/// \return A reference to the same \c std::ostream object referenced by
/// parameter \c os after the insertion operation.
std::ostream&
operator<<(std::ostream& os, const LabelSequence& label_sequence);

Jelte Jansen's avatar
Jelte Jansen committed
384
385
386
387
} // end namespace dns
} // end namespace isc

#endif
388
389
390
391

// Local Variables:
// mode: c++
// End: