1b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho/*
2b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*******************************************************************************
354dcd9b6a06071f647dac967e9e267abb9410720Craig Cornelius*   Copyright (C) 2010-2012, International Business Machines
4b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*   Corporation and others.  All Rights Reserved.
5b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*******************************************************************************
6b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*   file name:  ucharstriebuilder.h
7b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*   encoding:   US-ASCII
8b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*   tab size:   8 (not used)
9b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*   indentation:4
10b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*
11b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*   created on: 2010nov14
12b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*   created by: Markus W. Scherer
13b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho*/
14b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
15b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "unicode/utypes.h"
16b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "unicode/ucharstrie.h"
17b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "unicode/ucharstriebuilder.h"
18b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "unicode/unistr.h"
19b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "unicode/ustring.h"
20b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "cmemory.h"
21b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "uarrsort.h"
22b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "uassert.h"
23b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho#include "uhash.h"
24103e9ffba2cba345d0078eb8b8db33249f81840aCraig Cornelius#include "ustr_imp.h"
25b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
26b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoU_NAMESPACE_BEGIN
27b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
28b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho/*
29b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho * Note: This builder implementation stores (string, value) pairs with full copies
30b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho * of the 16-bit-unit sequences, until the UCharsTrie is built.
31b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho * It might(!) take less memory if we collected the data in a temporary, dynamic trie.
32b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho */
33b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
34b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoclass UCharsTrieElement : public UMemory {
35b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehopublic:
36b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    // Use compiler's default constructor, initializes nothing.
37b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
38b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    void setTo(const UnicodeString &s, int32_t val, UnicodeString &strings, UErrorCode &errorCode);
39b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
40b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    UnicodeString getString(const UnicodeString &strings) const {
41b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        int32_t length=strings[stringOffset];
42b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return strings.tempSubString(stringOffset+1, length);
43b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
44b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t getStringLength(const UnicodeString &strings) const {
45b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return strings[stringOffset];
46b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
47b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
48b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    UChar charAt(int32_t index, const UnicodeString &strings) const {
49b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return strings[stringOffset+1+index];
50b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
51b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
52b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t getValue() const { return value; }
53b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
54b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t compareStringTo(const UCharsTrieElement &o, const UnicodeString &strings) const;
55b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
56b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoprivate:
57b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    // The first strings unit contains the string length.
58b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    // (Compared with a stringLength field here, this saves 2 bytes per string.)
59b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t stringOffset;
60b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t value;
61b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho};
62b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
63b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid
64b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieElement::setTo(const UnicodeString &s, int32_t val,
65b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho                         UnicodeString &strings, UErrorCode &errorCode) {
66b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(U_FAILURE(errorCode)) {
67b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return;
68b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
69b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t length=s.length();
70b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(length>0xffff) {
71b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        // Too long: We store the length in 1 unit.
72b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        errorCode=U_INDEX_OUTOFBOUNDS_ERROR;
73b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return;
74b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
75b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    stringOffset=strings.length();
76b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    strings.append((UChar)length);
77b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    value=val;
78b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    strings.append(s);
79b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
80b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
81b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
82b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieElement::compareStringTo(const UCharsTrieElement &other, const UnicodeString &strings) const {
83b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return getString(strings).compare(other.getString(strings));
84b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
85b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
86b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::UCharsTrieBuilder(UErrorCode & /*errorCode*/)
87b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        : elements(NULL), elementsCapacity(0), elementsLength(0),
88b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho          uchars(NULL), ucharsCapacity(0), ucharsLength(0) {}
89b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
90b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::~UCharsTrieBuilder() {
91b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    delete[] elements;
92b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    uprv_free(uchars);
93b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
94b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
95b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder &
96b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::add(const UnicodeString &s, int32_t value, UErrorCode &errorCode) {
97b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(U_FAILURE(errorCode)) {
98b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return *this;
99b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
100b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(ucharsLength>0) {
101b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        // Cannot add elements after building.
102b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        errorCode=U_NO_WRITE_PERMISSION;
103b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return *this;
104b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
105b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(elementsLength==elementsCapacity) {
106b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        int32_t newCapacity;
107b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        if(elementsCapacity==0) {
108b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            newCapacity=1024;
109b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        } else {
110b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            newCapacity=4*elementsCapacity;
111b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
112b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        UCharsTrieElement *newElements=new UCharsTrieElement[newCapacity];
113b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        if(newElements==NULL) {
114b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            errorCode=U_MEMORY_ALLOCATION_ERROR;
115103e9ffba2cba345d0078eb8b8db33249f81840aCraig Cornelius            return *this;
116b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
117b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        if(elementsLength>0) {
118b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            uprv_memcpy(newElements, elements, elementsLength*sizeof(UCharsTrieElement));
119b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
120b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        delete[] elements;
121b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        elements=newElements;
122b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        elementsCapacity=newCapacity;
123b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
124b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    elements[elementsLength++].setTo(s, value, strings, errorCode);
125b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(U_SUCCESS(errorCode) && strings.isBogus()) {
126b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        errorCode=U_MEMORY_ALLOCATION_ERROR;
127b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
128b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return *this;
129b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
130b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
131b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoU_CDECL_BEGIN
132b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
133b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehostatic int32_t U_CALLCONV
134b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehocompareElementStrings(const void *context, const void *left, const void *right) {
13554dcd9b6a06071f647dac967e9e267abb9410720Craig Cornelius    const UnicodeString *strings=static_cast<const UnicodeString *>(context);
13654dcd9b6a06071f647dac967e9e267abb9410720Craig Cornelius    const UCharsTrieElement *leftElement=static_cast<const UCharsTrieElement *>(left);
13754dcd9b6a06071f647dac967e9e267abb9410720Craig Cornelius    const UCharsTrieElement *rightElement=static_cast<const UCharsTrieElement *>(right);
138b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return leftElement->compareStringTo(*rightElement, *strings);
139b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
140b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
141b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoU_CDECL_END
142b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
143b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrie *
144b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::build(UStringTrieBuildOption buildOption, UErrorCode &errorCode) {
145b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    buildUChars(buildOption, errorCode);
146b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    UCharsTrie *newTrie=NULL;
147b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(U_SUCCESS(errorCode)) {
148b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        newTrie=new UCharsTrie(uchars, uchars+(ucharsCapacity-ucharsLength));
149b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        if(newTrie==NULL) {
150b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            errorCode=U_MEMORY_ALLOCATION_ERROR;
151b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        } else {
152b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            uchars=NULL;  // The new trie now owns the array.
153b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            ucharsCapacity=0;
154b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
155b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
156b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return newTrie;
157b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
158b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
159b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUnicodeString &
160b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::buildUnicodeString(UStringTrieBuildOption buildOption, UnicodeString &result,
161b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho                                      UErrorCode &errorCode) {
162b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    buildUChars(buildOption, errorCode);
163b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(U_SUCCESS(errorCode)) {
164b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        result.setTo(FALSE, uchars+(ucharsCapacity-ucharsLength), ucharsLength);
165b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
166b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return result;
167b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
168b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
169b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid
170b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::buildUChars(UStringTrieBuildOption buildOption, UErrorCode &errorCode) {
171b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(U_FAILURE(errorCode)) {
172b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return;
173b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
174b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(uchars!=NULL && ucharsLength>0) {
175b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        // Already built.
176b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return;
177b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
178b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(ucharsLength==0) {
179b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        if(elementsLength==0) {
180b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            errorCode=U_INDEX_OUTOFBOUNDS_ERROR;
181b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            return;
182b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
183b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        if(strings.isBogus()) {
184b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            errorCode=U_MEMORY_ALLOCATION_ERROR;
185b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            return;
186b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
187b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        uprv_sortArray(elements, elementsLength, (int32_t)sizeof(UCharsTrieElement),
188b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho                      compareElementStrings, &strings,
189b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho                      FALSE,  // need not be a stable sort
190b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho                      &errorCode);
191b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        if(U_FAILURE(errorCode)) {
192b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            return;
193b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
194b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        // Duplicate strings are not allowed.
195b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        UnicodeString prev=elements[0].getString(strings);
196b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        for(int32_t i=1; i<elementsLength; ++i) {
197b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            UnicodeString current=elements[i].getString(strings);
198b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            if(prev==current) {
199b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho                errorCode=U_ILLEGAL_ARGUMENT_ERROR;
200b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho                return;
201b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            }
202b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            prev.fastCopyFrom(current);
203b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
204b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
205b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    // Create and UChar-serialize the trie for the elements.
206b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    ucharsLength=0;
207b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t capacity=strings.length();
208b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(capacity<1024) {
209b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        capacity=1024;
210b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
211b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(ucharsCapacity<capacity) {
212b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        uprv_free(uchars);
21354dcd9b6a06071f647dac967e9e267abb9410720Craig Cornelius        uchars=static_cast<UChar *>(uprv_malloc(capacity*2));
214b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        if(uchars==NULL) {
215b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            errorCode=U_MEMORY_ALLOCATION_ERROR;
216b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            ucharsCapacity=0;
217b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            return;
218b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
219b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        ucharsCapacity=capacity;
220b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
221b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    StringTrieBuilder::build(buildOption, elementsLength, errorCode);
222b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(uchars==NULL) {
223b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        errorCode=U_MEMORY_ALLOCATION_ERROR;
224b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
225b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
226b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
227b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
228b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::getElementStringLength(int32_t i) const {
229b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return elements[i].getStringLength(strings);
230b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
231b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
232b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUChar
233b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::getElementUnit(int32_t i, int32_t unitIndex) const {
234b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return elements[i].charAt(unitIndex, strings);
235b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
236b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
237b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
238b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::getElementValue(int32_t i) const {
239b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return elements[i].getValue();
240b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
241b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
242b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
243b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::getLimitOfLinearMatch(int32_t first, int32_t last, int32_t unitIndex) const {
244b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    const UCharsTrieElement &firstElement=elements[first];
245b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    const UCharsTrieElement &lastElement=elements[last];
246b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t minStringLength=firstElement.getStringLength(strings);
247b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    while(++unitIndex<minStringLength &&
248b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            firstElement.charAt(unitIndex, strings)==
249b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            lastElement.charAt(unitIndex, strings)) {}
250b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return unitIndex;
251b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
252b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
253b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
254b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::countElementUnits(int32_t start, int32_t limit, int32_t unitIndex) const {
255b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t length=0;  // Number of different units at unitIndex.
256b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t i=start;
257b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    do {
258b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        UChar unit=elements[i++].charAt(unitIndex, strings);
259b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        while(i<limit && unit==elements[i].charAt(unitIndex, strings)) {
260b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            ++i;
261b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
262b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        ++length;
263b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    } while(i<limit);
264b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return length;
265b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
266b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
267b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
268b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::skipElementsBySomeUnits(int32_t i, int32_t unitIndex, int32_t count) const {
269b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    do {
270b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        UChar unit=elements[i++].charAt(unitIndex, strings);
271b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        while(unit==elements[i].charAt(unitIndex, strings)) {
272b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            ++i;
273b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
274b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    } while(--count>0);
275b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return i;
276b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
277b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
278b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
279b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::indexOfElementWithNextUnit(int32_t i, int32_t unitIndex, UChar unit) const {
280b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    while(unit==elements[i].charAt(unitIndex, strings)) {
281b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        ++i;
282b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
283b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return i;
284b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
285b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
286b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::UCTLinearMatchNode::UCTLinearMatchNode(const UChar *units, int32_t len, Node *nextNode)
287b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        : LinearMatchNode(len, nextNode), s(units) {
288103e9ffba2cba345d0078eb8b8db33249f81840aCraig Cornelius    hash=hash*37+ustr_hashUCharsN(units, len);
289b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
290b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
291b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool
292b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::UCTLinearMatchNode::operator==(const Node &other) const {
293b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(this==&other) {
294b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return TRUE;
295b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
296b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(!LinearMatchNode::operator==(other)) {
297b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return FALSE;
298b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
299b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    const UCTLinearMatchNode &o=(const UCTLinearMatchNode &)other;
300b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return 0==u_memcmp(s, o.s, length);
301b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
302b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
303b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehovoid
304b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::UCTLinearMatchNode::write(StringTrieBuilder &builder) {
305b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    UCharsTrieBuilder &b=(UCharsTrieBuilder &)builder;
306b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    next->write(builder);
307b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    b.write(s, length);
308b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    offset=b.writeValueAndType(hasValue, value, b.getMinLinearMatch()+length-1);
309b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
310b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
311b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoStringTrieBuilder::Node *
312b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::createLinearMatchNode(int32_t i, int32_t unitIndex, int32_t length,
313b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho                                         Node *nextNode) const {
314b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return new UCTLinearMatchNode(
315b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            elements[i].getString(strings).getBuffer()+unitIndex,
316b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            length,
317b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            nextNode);
318b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
319b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
320b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUBool
321b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::ensureCapacity(int32_t length) {
322b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(uchars==NULL) {
323b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return FALSE;  // previous memory allocation had failed
324b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
325b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(length>ucharsCapacity) {
326b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        int32_t newCapacity=ucharsCapacity;
327b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        do {
328b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            newCapacity*=2;
329b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        } while(newCapacity<=length);
33054dcd9b6a06071f647dac967e9e267abb9410720Craig Cornelius        UChar *newUChars=static_cast<UChar *>(uprv_malloc(newCapacity*2));
331b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        if(newUChars==NULL) {
332b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            // unable to allocate memory
333b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            uprv_free(uchars);
334b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            uchars=NULL;
335b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            ucharsCapacity=0;
336b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho            return FALSE;
337b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        }
338b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        u_memcpy(newUChars+(newCapacity-ucharsLength),
339b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho                 uchars+(ucharsCapacity-ucharsLength), ucharsLength);
340b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        uprv_free(uchars);
341b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        uchars=newUChars;
342b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        ucharsCapacity=newCapacity;
343b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
344b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return TRUE;
345b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
346b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
347b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
348b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::write(int32_t unit) {
349b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t newLength=ucharsLength+1;
350b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(ensureCapacity(newLength)) {
351b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        ucharsLength=newLength;
352b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        uchars[ucharsCapacity-ucharsLength]=(UChar)unit;
353b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
354b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return ucharsLength;
355b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
356b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
357b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
358b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::write(const UChar *s, int32_t length) {
359b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t newLength=ucharsLength+length;
360b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(ensureCapacity(newLength)) {
361b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        ucharsLength=newLength;
362b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        u_memcpy(uchars+(ucharsCapacity-ucharsLength), s, length);
363b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
364b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return ucharsLength;
365b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
366b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
367b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
368b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::writeElementUnits(int32_t i, int32_t unitIndex, int32_t length) {
369b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return write(elements[i].getString(strings).getBuffer()+unitIndex, length);
370b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
371b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
372b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
373b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::writeValueAndFinal(int32_t i, UBool isFinal) {
374b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(0<=i && i<=UCharsTrie::kMaxOneUnitValue) {
375b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return write(i|(isFinal<<15));
376b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
377b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    UChar intUnits[3];
378b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t length;
379b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(i<0 || i>UCharsTrie::kMaxTwoUnitValue) {
380b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[0]=(UChar)(UCharsTrie::kThreeUnitValueLead);
38154dcd9b6a06071f647dac967e9e267abb9410720Craig Cornelius        intUnits[1]=(UChar)((uint32_t)i>>16);
382b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[2]=(UChar)i;
383b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        length=3;
384b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    // } else if(i<=UCharsTrie::kMaxOneUnitValue) {
385b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    //     intUnits[0]=(UChar)(i);
386b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    //     length=1;
387b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    } else {
388b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitValueLead+(i>>16));
389b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[1]=(UChar)i;
390b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        length=2;
391b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
392b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    intUnits[0]=(UChar)(intUnits[0]|(isFinal<<15));
393b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return write(intUnits, length);
394b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
395b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
396b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
397b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::writeValueAndType(UBool hasValue, int32_t value, int32_t node) {
398b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(!hasValue) {
399b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return write(node);
400b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
401b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    UChar intUnits[3];
402b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t length;
403b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(value<0 || value>UCharsTrie::kMaxTwoUnitNodeValue) {
404b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[0]=(UChar)(UCharsTrie::kThreeUnitNodeValueLead);
40554dcd9b6a06071f647dac967e9e267abb9410720Craig Cornelius        intUnits[1]=(UChar)((uint32_t)value>>16);
406b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[2]=(UChar)value;
407b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        length=3;
408b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    } else if(value<=UCharsTrie::kMaxOneUnitNodeValue) {
409b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[0]=(UChar)((value+1)<<6);
410b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        length=1;
411b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    } else {
412b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitNodeValueLead+((value>>10)&0x7fc0));
413b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[1]=(UChar)value;
414b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        length=2;
415b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
416b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    intUnits[0]|=(UChar)node;
417b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return write(intUnits, length);
418b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
419b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
420b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoint32_t
421b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoUCharsTrieBuilder::writeDeltaTo(int32_t jumpTarget) {
422b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t i=ucharsLength-jumpTarget;
423b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    U_ASSERT(i>=0);
424b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(i<=UCharsTrie::kMaxOneUnitDelta) {
425b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        return write(i);
426b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
427b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    UChar intUnits[3];
428b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    int32_t length;
429b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    if(i<=UCharsTrie::kMaxTwoUnitDelta) {
430b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitDeltaLead+(i>>16));
431b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        length=1;
432b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    } else {
433b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[0]=(UChar)(UCharsTrie::kThreeUnitDeltaLead);
434b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        intUnits[1]=(UChar)(i>>16);
435b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho        length=2;
436b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    }
437b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    intUnits[length++]=(UChar)i;
438b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho    return write(intUnits, length);
439b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho}
440b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho
441b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2clairehoU_NAMESPACE_END
442