← Back to branch summary

~ubuntu-branches/ubuntu/vivid/mozjs24/vivid

« back to all changes in this revision

Viewing changes to intl/icu/source/common/unicode/bytestrie.h

  • Committer: Package Import Robot
  • Author(s): Tim Lunn
  • Date: 2014-02-11 21:55:34 UTC
  • Revision ID: package-import@ubuntu.com-20140211215534-m1zyq5aj59md3y07
Tags: upstream-24.2.0
Import upstream version 24.2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
intl/icu/source/common/unicode/bytestrie.h
 
1
/*
 
2
*******************************************************************************
 
3
*   Copyright (C) 2010-2012, International Business Machines
 
4
*   Corporation and others.  All Rights Reserved.
 
5
*******************************************************************************
 
6
*   file name:  bytestrie.h
 
7
*   encoding:   US-ASCII
 
8
*   tab size:   8 (not used)
 
9
*   indentation:4
 
10
*
 
11
*   created on: 2010sep25
 
12
*   created by: Markus W. Scherer
 
13
*/
 
14
 
 
15
#ifndef __BYTESTRIE_H__
 
16
#define __BYTESTRIE_H__
 
17
 
 
18
/**
 
19
 * \file
 
20
 * \brief C++ API: Trie for mapping byte sequences to integer values.
 
21
 */
 
22
 
 
23
#include "unicode/utypes.h"
 
24
#include "unicode/stringpiece.h"
 
25
#include "unicode/uobject.h"
 
26
#include "unicode/ustringtrie.h"
 
27
 
 
28
U_NAMESPACE_BEGIN
 
29
 
 
30
class ByteSink;
 
31
class BytesTrieBuilder;
 
32
class CharString;
 
33
class UVector32;
 
34
 
 
35
/**
 
36
 * Light-weight, non-const reader class for a BytesTrie.
 
37
 * Traverses a byte-serialized data structure with minimal state,
 
38
 * for mapping byte sequences to non-negative integer values.
 
39
 *
 
40
 * This class owns the serialized trie data only if it was constructed by
 
41
 * the builder's build() method.
 
42
 * The public constructor and the copy constructor only alias the data (only copy the pointer).
 
43
 * There is no assignment operator.
 
44
 *
 
45
 * This class is not intended for public subclassing.
 
46
 * @stable ICU 4.8
 
47
 */
 
48
class U_COMMON_API BytesTrie : public UMemory {
 
49
public:
 
50
    /**
 
51
     * Constructs a BytesTrie reader instance.
 
52
     *
 
53
     * The trieBytes must contain a copy of a byte sequence from the BytesTrieBuilder,
 
54
     * starting with the first byte of that sequence.
 
55
     * The BytesTrie object will not read more bytes than
 
56
     * the BytesTrieBuilder generated in the corresponding build() call.
 
57
     *
 
58
     * The array is not copied/cloned and must not be modified while
 
59
     * the BytesTrie object is in use.
 
60
     *
 
61
     * @param trieBytes The byte array that contains the serialized trie.
 
62
     * @stable ICU 4.8
 
63
     */
 
64
    BytesTrie(const void *trieBytes)
 
65
            : ownedArray_(NULL), bytes_(static_cast<const uint8_t *>(trieBytes)),
 
66
              pos_(bytes_), remainingMatchLength_(-1) {}
 
67
 
 
68
    /**
 
69
     * Destructor.
 
70
     * @stable ICU 4.8
 
71
     */
 
72
    ~BytesTrie();
 
73
 
 
74
    /**
 
75
     * Copy constructor, copies the other trie reader object and its state,
 
76
     * but not the byte array which will be shared. (Shallow copy.)
 
77
     * @param other Another BytesTrie object.
 
78
     * @stable ICU 4.8
 
79
     */
 
80
    BytesTrie(const BytesTrie &other)
 
81
            : ownedArray_(NULL), bytes_(other.bytes_),
 
82
              pos_(other.pos_), remainingMatchLength_(other.remainingMatchLength_) {}
 
83
 
 
84
    /**
 
85
     * Resets this trie to its initial state.
 
86
     * @return *this
 
87
     * @stable ICU 4.8
 
88
     */
 
89
    BytesTrie &reset() {
 
90
        pos_=bytes_;
 
91
        remainingMatchLength_=-1;
 
92
        return *this;
 
93
    }
 
94
 
 
95
    /**
 
96
     * BytesTrie state object, for saving a trie's current state
 
97
     * and resetting the trie back to this state later.
 
98
     * @stable ICU 4.8
 
99
     */
 
100
    class State : public UMemory {
 
101
    public:
 
102
        /**
 
103
         * Constructs an empty State.
 
104
         * @stable ICU 4.8
 
105
         */
 
106
        State() { bytes=NULL; }
 
107
    private:
 
108
        friend class BytesTrie;
 
109
 
 
110
        const uint8_t *bytes;
 
111
        const uint8_t *pos;
 
112
        int32_t remainingMatchLength;
 
113
    };
 
114
 
 
115
    /**
 
116
     * Saves the state of this trie.
 
117
     * @param state The State object to hold the trie's state.
 
118
     * @return *this
 
119
     * @see resetToState
 
120
     * @stable ICU 4.8
 
121
     */
 
122
    const BytesTrie &saveState(State &state) const {
 
123
        state.bytes=bytes_;
 
124
        state.pos=pos_;
 
125
        state.remainingMatchLength=remainingMatchLength_;
 
126
        return *this;
 
127
    }
 
128
 
 
129
    /**
 
130
     * Resets this trie to the saved state.
 
131
     * If the state object contains no state, or the state of a different trie,
 
132
     * then this trie remains unchanged.
 
133
     * @param state The State object which holds a saved trie state.
 
134
     * @return *this
 
135
     * @see saveState
 
136
     * @see reset
 
137
     * @stable ICU 4.8
 
138
     */
 
139
    BytesTrie &resetToState(const State &state) {
 
140
        if(bytes_==state.bytes && bytes_!=NULL) {
 
141
            pos_=state.pos;
 
142
            remainingMatchLength_=state.remainingMatchLength;
 
143
        }
 
144
        return *this;
 
145
    }
 
146
 
 
147
    /**
 
148
     * Determines whether the byte sequence so far matches, whether it has a value,
 
149
     * and whether another input byte can continue a matching byte sequence.
 
150
     * @return The match/value Result.
 
151
     * @stable ICU 4.8
 
152
     */
 
153
    UStringTrieResult current() const;
 
154
 
 
155
    /**
 
156
     * Traverses the trie from the initial state for this input byte.
 
157
     * Equivalent to reset().next(inByte).
 
158
     * @param inByte Input byte value. Values -0x100..-1 are treated like 0..0xff.
 
159
     *               Values below -0x100 and above 0xff will never match.
 
160
     * @return The match/value Result.
 
161
     * @stable ICU 4.8
 
162
     */
 
163
    inline UStringTrieResult first(int32_t inByte) {
 
164
        remainingMatchLength_=-1;
 
165
        if(inByte<0) {
 
166
            inByte+=0x100;
 
167
        }
 
168
        return nextImpl(bytes_, inByte);
 
169
    }
 
170
 
 
171
    /**
 
172
     * Traverses the trie from the current state for this input byte.
 
173
     * @param inByte Input byte value. Values -0x100..-1 are treated like 0..0xff.
 
174
     *               Values below -0x100 and above 0xff will never match.
 
175
     * @return The match/value Result.
 
176
     * @stable ICU 4.8
 
177
     */
 
178
    UStringTrieResult next(int32_t inByte);
 
179
 
 
180
    /**
 
181
     * Traverses the trie from the current state for this byte sequence.
 
182
     * Equivalent to
 
183
     * \code
 
184
     * Result result=current();
 
185
     * for(each c in s)
 
186
     *   if(!USTRINGTRIE_HAS_NEXT(result)) return USTRINGTRIE_NO_MATCH;
 
187
     *   result=next(c);
 
188
     * return result;
 
189
     * \endcode
 
190
     * @param s A string or byte sequence. Can be NULL if length is 0.
 
191
     * @param length The length of the byte sequence. Can be -1 if NUL-terminated.
 
192
     * @return The match/value Result.
 
193
     * @stable ICU 4.8
 
194
     */
 
195
    UStringTrieResult next(const char *s, int32_t length);
 
196
 
 
197
    /**
 
198
     * Returns a matching byte sequence's value if called immediately after
 
199
     * current()/first()/next() returned USTRINGTRIE_INTERMEDIATE_VALUE or USTRINGTRIE_FINAL_VALUE.
 
200
     * getValue() can be called multiple times.
 
201
     *
 
202
     * Do not call getValue() after USTRINGTRIE_NO_MATCH or USTRINGTRIE_NO_VALUE!
 
203
     * @return The value for the byte sequence so far.
 
204
     * @stable ICU 4.8
 
205
     */
 
206
    inline int32_t getValue() const {
 
207
        const uint8_t *pos=pos_;
 
208
        int32_t leadByte=*pos++;
 
209
        // U_ASSERT(leadByte>=kMinValueLead);
 
210
        return readValue(pos, leadByte>>1);
 
211
    }
 
212
 
 
213
    /**
 
214
     * Determines whether all byte sequences reachable from the current state
 
215
     * map to the same value.
 
216
     * @param uniqueValue Receives the unique value, if this function returns TRUE.
 
217
     *                    (output-only)
 
218
     * @return TRUE if all byte sequences reachable from the current state
 
219
     *         map to the same value.
 
220
     * @stable ICU 4.8
 
221
     */
 
222
    inline UBool hasUniqueValue(int32_t &uniqueValue) const {
 
223
        const uint8_t *pos=pos_;
 
224
        // Skip the rest of a pending linear-match node.
 
225
        return pos!=NULL && findUniqueValue(pos+remainingMatchLength_+1, FALSE, uniqueValue);
 
226
    }
 
227
 
 
228
    /**
 
229
     * Finds each byte which continues the byte sequence from the current state.
 
230
     * That is, each byte b for which it would be next(b)!=USTRINGTRIE_NO_MATCH now.
 
231
     * @param out Each next byte is appended to this object.
 
232
     *            (Only uses the out.Append(s, length) method.)
 
233
     * @return the number of bytes which continue the byte sequence from here
 
234
     * @stable ICU 4.8
 
235
     */
 
236
    int32_t getNextBytes(ByteSink &out) const;
 
237
 
 
238
    /**
 
239
     * Iterator for all of the (byte sequence, value) pairs in a BytesTrie.
 
240
     * @stable ICU 4.8
 
241
     */
 
242
    class U_COMMON_API Iterator : public UMemory {
 
243
    public:
 
244
        /**
 
245
         * Iterates from the root of a byte-serialized BytesTrie.
 
246
         * @param trieBytes The trie bytes.
 
247
         * @param maxStringLength If 0, the iterator returns full strings/byte sequences.
 
248
         *                        Otherwise, the iterator returns strings with this maximum length.
 
249
         * @param errorCode Standard ICU error code. Its input value must
 
250
         *                  pass the U_SUCCESS() test, or else the function returns
 
251
         *                  immediately. Check for U_FAILURE() on output or use with
 
252
         *                  function chaining. (See User Guide for details.)
 
253
         * @stable ICU 4.8
 
254
         */
 
255
        Iterator(const void *trieBytes, int32_t maxStringLength, UErrorCode &errorCode);
 
256
 
 
257
        /**
 
258
         * Iterates from the current state of the specified BytesTrie.
 
259
         * @param trie The trie whose state will be copied for iteration.
 
260
         * @param maxStringLength If 0, the iterator returns full strings/byte sequences.
 
261
         *                        Otherwise, the iterator returns strings with this maximum length.
 
262
         * @param errorCode Standard ICU error code. Its input value must
 
263
         *                  pass the U_SUCCESS() test, or else the function returns
 
264
         *                  immediately. Check for U_FAILURE() on output or use with
 
265
         *                  function chaining. (See User Guide for details.)
 
266
         * @stable ICU 4.8
 
267
         */
 
268
        Iterator(const BytesTrie &trie, int32_t maxStringLength, UErrorCode &errorCode);
 
269
 
 
270
        /**
 
271
         * Destructor.
 
272
         * @stable ICU 4.8
 
273
         */
 
274
        ~Iterator();
 
275
 
 
276
        /**
 
277
         * Resets this iterator to its initial state.
 
278
         * @return *this
 
279
         * @stable ICU 4.8
 
280
         */
 
281
        Iterator &reset();
 
282
 
 
283
        /**
 
284
         * @return TRUE if there are more elements.
 
285
         * @stable ICU 4.8
 
286
         */
 
287
        UBool hasNext() const;
 
288
 
 
289
        /**
 
290
         * Finds the next (byte sequence, value) pair if there is one.
 
291
         *
 
292
         * If the byte sequence is truncated to the maximum length and does not
 
293
         * have a real value, then the value is set to -1.
 
294
         * In this case, this "not a real value" is indistinguishable from
 
295
         * a real value of -1.
 
296
         * @param errorCode Standard ICU error code. Its input value must
 
297
         *                  pass the U_SUCCESS() test, or else the function returns
 
298
         *                  immediately. Check for U_FAILURE() on output or use with
 
299
         *                  function chaining. (See User Guide for details.)
 
300
         * @return TRUE if there is another element.
 
301
         * @stable ICU 4.8
 
302
         */
 
303
        UBool next(UErrorCode &errorCode);
 
304
 
 
305
        /**
 
306
         * @return The NUL-terminated byte sequence for the last successful next().
 
307
         * @stable ICU 4.8
 
308
         */
 
309
        const StringPiece &getString() const { return sp_; }
 
310
        /**
 
311
         * @return The value for the last successful next().
 
312
         * @stable ICU 4.8
 
313
         */
 
314
        int32_t getValue() const { return value_; }
 
315
 
 
316
    private:
 
317
        UBool truncateAndStop();
 
318
 
 
319
        const uint8_t *branchNext(const uint8_t *pos, int32_t length, UErrorCode &errorCode);
 
320
 
 
321
        const uint8_t *bytes_;
 
322
        const uint8_t *pos_;
 
323
        const uint8_t *initialPos_;
 
324
        int32_t remainingMatchLength_;
 
325
        int32_t initialRemainingMatchLength_;
 
326
 
 
327
        CharString *str_;
 
328
        StringPiece sp_;
 
329
        int32_t maxLength_;
 
330
        int32_t value_;
 
331
 
 
332
        // The stack stores pairs of integers for backtracking to another
 
333
        // outbound edge of a branch node.
 
334
        // The first integer is an offset from bytes_.
 
335
        // The second integer has the str_->length() from before the node in bits 15..0,
 
336
        // and the remaining branch length in bits 24..16. (Bits 31..25 are unused.)
 
337
        // (We could store the remaining branch length minus 1 in bits 23..16 and not use bits 31..24,
 
338
        // but the code looks more confusing that way.)
 
339
        UVector32 *stack_;
 
340
    };
 
341
 
 
342
private:
 
343
    friend class BytesTrieBuilder;
 
344
 
 
345
    /**
 
346
     * Constructs a BytesTrie reader instance.
 
347
     * Unlike the public constructor which just aliases an array,
 
348
     * this constructor adopts the builder's array.
 
349
     * This constructor is only called by the builder.
 
350
     */
 
351
    BytesTrie(void *adoptBytes, const void *trieBytes)
 
352
            : ownedArray_(static_cast<uint8_t *>(adoptBytes)),
 
353
              bytes_(static_cast<const uint8_t *>(trieBytes)),
 
354
              pos_(bytes_), remainingMatchLength_(-1) {}
 
355
 
 
356
    // No assignment operator.
 
357
    BytesTrie &operator=(const BytesTrie &other);
 
358
 
 
359
    inline void stop() {
 
360
        pos_=NULL;
 
361
    }
 
362
 
 
363
    // Reads a compact 32-bit integer.
 
364
    // pos is already after the leadByte, and the lead byte is already shifted right by 1.
 
365
    static int32_t readValue(const uint8_t *pos, int32_t leadByte);
 
366
    static inline const uint8_t *skipValue(const uint8_t *pos, int32_t leadByte) {
 
367
        // U_ASSERT(leadByte>=kMinValueLead);
 
368
        if(leadByte>=(kMinTwoByteValueLead<<1)) {
 
369
            if(leadByte<(kMinThreeByteValueLead<<1)) {
 
370
                ++pos;
 
371
            } else if(leadByte<(kFourByteValueLead<<1)) {
 
372
                pos+=2;
 
373
            } else {
 
374
                pos+=3+((leadByte>>1)&1);
 
375
            }
 
376
        }
 
377
        return pos;
 
378
    }
 
379
    static inline const uint8_t *skipValue(const uint8_t *pos) {
 
380
        int32_t leadByte=*pos++;
 
381
        return skipValue(pos, leadByte);
 
382
    }
 
383
 
 
384
    // Reads a jump delta and jumps.
 
385
    static const uint8_t *jumpByDelta(const uint8_t *pos);
 
386
 
 
387
    static inline const uint8_t *skipDelta(const uint8_t *pos) {
 
388
        int32_t delta=*pos++;
 
389
        if(delta>=kMinTwoByteDeltaLead) {
 
390
            if(delta<kMinThreeByteDeltaLead) {
 
391
                ++pos;
 
392
            } else if(delta<kFourByteDeltaLead) {
 
393
                pos+=2;
 
394
            } else {
 
395
                pos+=3+(delta&1);
 
396
            }
 
397
        }
 
398
        return pos;
 
399
    }
 
400
 
 
401
    static inline UStringTrieResult valueResult(int32_t node) {
 
402
        return (UStringTrieResult)(USTRINGTRIE_INTERMEDIATE_VALUE-(node&kValueIsFinal));
 
403
    }
 
404
 
 
405
    // Handles a branch node for both next(byte) and next(string).
 
406
    UStringTrieResult branchNext(const uint8_t *pos, int32_t length, int32_t inByte);
 
407
 
 
408
    // Requires remainingLength_<0.
 
409
    UStringTrieResult nextImpl(const uint8_t *pos, int32_t inByte);
 
410
 
 
411
    // Helper functions for hasUniqueValue().
 
412
    // Recursively finds a unique value (or whether there is not a unique one)
 
413
    // from a branch.
 
414
    static const uint8_t *findUniqueValueFromBranch(const uint8_t *pos, int32_t length,
 
415
                                                    UBool haveUniqueValue, int32_t &uniqueValue);
 
416
    // Recursively finds a unique value (or whether there is not a unique one)
 
417
    // starting from a position on a node lead byte.
 
418
    static UBool findUniqueValue(const uint8_t *pos, UBool haveUniqueValue, int32_t &uniqueValue);
 
419
 
 
420
    // Helper functions for getNextBytes().
 
421
    // getNextBytes() when pos is on a branch node.
 
422
    static void getNextBranchBytes(const uint8_t *pos, int32_t length, ByteSink &out);
 
423
    static void append(ByteSink &out, int c);
 
424
 
 
425
    // BytesTrie data structure
 
426
    //
 
427
    // The trie consists of a series of byte-serialized nodes for incremental
 
428
    // string/byte sequence matching. The root node is at the beginning of the trie data.
 
429
    //
 
430
    // Types of nodes are distinguished by their node lead byte ranges.
 
431
    // After each node, except a final-value node, another node follows to
 
432
    // encode match values or continue matching further bytes.
 
433
    //
 
434
    // Node types:
 
435
    //  - Value node: Stores a 32-bit integer in a compact, variable-length format.
 
436
    //    The value is for the string/byte sequence so far.
 
437
    //    One node bit indicates whether the value is final or whether
 
438
    //    matching continues with the next node.
 
439
    //  - Linear-match node: Matches a number of bytes.
 
440
    //  - Branch node: Branches to other nodes according to the current input byte.
 
441
    //    The node byte is the length of the branch (number of bytes to select from)
 
442
    //    minus 1. It is followed by a sub-node:
 
443
    //    - If the length is at most kMaxBranchLinearSubNodeLength, then
 
444
    //      there are length-1 (key, value) pairs and then one more comparison byte.
 
445
    //      If one of the key bytes matches, then the value is either a final value for
 
446
    //      the string/byte sequence so far, or a "jump" delta to the next node.
 
447
    //      If the last byte matches, then matching continues with the next node.
 
448
    //      (Values have the same encoding as value nodes.)
 
449
    //    - If the length is greater than kMaxBranchLinearSubNodeLength, then
 
450
    //      there is one byte and one "jump" delta.
 
451
    //      If the input byte is less than the sub-node byte, then "jump" by delta to
 
452
    //      the next sub-node which will have a length of length/2.
 
453
    //      (The delta has its own compact encoding.)
 
454
    //      Otherwise, skip the "jump" delta to the next sub-node
 
455
    //      which will have a length of length-length/2.
 
456
 
 
457
    // Node lead byte values.
 
458
 
 
459
    // 00..0f: Branch node. If node!=0 then the length is node+1, otherwise
 
460
    // the length is one more than the next byte.
 
461
 
 
462
    // For a branch sub-node with at most this many entries, we drop down
 
463
    // to a linear search.
 
464
    static const int32_t kMaxBranchLinearSubNodeLength=5;
 
465
 
 
466
    // 10..1f: Linear-match node, match 1..16 bytes and continue reading the next node.
 
467
    static const int32_t kMinLinearMatch=0x10;
 
468
    static const int32_t kMaxLinearMatchLength=0x10;
 
469
 
 
470
    // 20..ff: Variable-length value node.
 
471
    // If odd, the value is final. (Otherwise, intermediate value or jump delta.)
 
472
    // Then shift-right by 1 bit.
 
473
    // The remaining lead byte value indicates the number of following bytes (0..4)
 
474
    // and contains the value's top bits.
 
475
    static const int32_t kMinValueLead=kMinLinearMatch+kMaxLinearMatchLength;  // 0x20
 
476
    // It is a final value if bit 0 is set.
 
477
    static const int32_t kValueIsFinal=1;
 
478
 
 
479
    // Compact value: After testing bit 0, shift right by 1 and then use the following thresholds.
 
480
    static const int32_t kMinOneByteValueLead=kMinValueLead/2;  // 0x10
 
481
    static const int32_t kMaxOneByteValue=0x40;  // At least 6 bits in the first byte.
 
482
 
 
483
    static const int32_t kMinTwoByteValueLead=kMinOneByteValueLead+kMaxOneByteValue+1;  // 0x51
 
484
    static const int32_t kMaxTwoByteValue=0x1aff;
 
485
 
 
486
    static const int32_t kMinThreeByteValueLead=kMinTwoByteValueLead+(kMaxTwoByteValue>>8)+1;  // 0x6c
 
487
    static const int32_t kFourByteValueLead=0x7e;
 
488
 
 
489
    // A little more than Unicode code points. (0x11ffff)
 
490
    static const int32_t kMaxThreeByteValue=((kFourByteValueLead-kMinThreeByteValueLead)<<16)-1;
 
491
 
 
492
    static const int32_t kFiveByteValueLead=0x7f;
 
493
 
 
494
    // Compact delta integers.
 
495
    static const int32_t kMaxOneByteDelta=0xbf;
 
496
    static const int32_t kMinTwoByteDeltaLead=kMaxOneByteDelta+1;  // 0xc0
 
497
    static const int32_t kMinThreeByteDeltaLead=0xf0;
 
498
    static const int32_t kFourByteDeltaLead=0xfe;
 
499
    static const int32_t kFiveByteDeltaLead=0xff;
 
500
 
 
501
    static const int32_t kMaxTwoByteDelta=((kMinThreeByteDeltaLead-kMinTwoByteDeltaLead)<<8)-1;  // 0x2fff
 
502
    static const int32_t kMaxThreeByteDelta=((kFourByteDeltaLead-kMinThreeByteDeltaLead)<<16)-1;  // 0xdffff
 
503
 
 
504
    uint8_t *ownedArray_;
 
505
 
 
506
    // Fixed value referencing the BytesTrie bytes.
 
507
    const uint8_t *bytes_;
 
508
 
 
509
    // Iterator variables.
 
510
 
 
511
    // Pointer to next trie byte to read. NULL if no more matches.
 
512
    const uint8_t *pos_;
 
513
    // Remaining length of a linear-match node, minus 1. Negative if not in such a node.
 
514
    int32_t remainingMatchLength_;
 
515
};
 
516
 
 
517
U_NAMESPACE_END
 
518
 
 
519
#endif  // __BYTESTRIE_H__