[apple/icu.git] / icuSources / common / ucharstriebuilder.cpp

// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
*******************************************************************************
*   Copyright (C) 2010-2012, International Business Machines
*   Corporation and others.  All Rights Reserved.
*******************************************************************************
*   file name:  ucharstriebuilder.h
*   encoding:   UTF-8
*   tab size:   8 (not used)
*   indentation:4
*
*   created on: 2010nov14
*   created by: Markus W. Scherer
*/

#include "unicode/utypes.h"
#include "unicode/ucharstrie.h"
#include "unicode/ucharstriebuilder.h"
#include "unicode/unistr.h"
#include "unicode/ustring.h"
#include "cmemory.h"
#include "uarrsort.h"
#include "uassert.h"
#include "uhash.h"
#include "ustr_imp.h"

U_NAMESPACE_BEGIN

/*
 * Note: This builder implementation stores (string, value) pairs with full copies
 * of the 16-bit-unit sequences, until the UCharsTrie is built.
 * It might(!) take less memory if we collected the data in a temporary, dynamic trie.
 */

class UCharsTrieElement : public UMemory {
public:
    // Use compiler's default constructor, initializes nothing.

    void setTo(const UnicodeString &s, int32_t val, UnicodeString &strings, UErrorCode &errorCode);

    UnicodeString getString(const UnicodeString &strings) const {
        int32_t length=strings[stringOffset];
        return strings.tempSubString(stringOffset+1, length);
    }
    int32_t getStringLength(const UnicodeString &strings) const {
        return strings[stringOffset];
    }

    UChar charAt(int32_t index, const UnicodeString &strings) const {
        return strings[stringOffset+1+index];
    }

    int32_t getValue() const { return value; }

    int32_t compareStringTo(const UCharsTrieElement &o, const UnicodeString &strings) const;

private:
    // The first strings unit contains the string length.
    // (Compared with a stringLength field here, this saves 2 bytes per string.)
    int32_t stringOffset;
    int32_t value;
};

void
UCharsTrieElement::setTo(const UnicodeString &s, int32_t val,
                         UnicodeString &strings, UErrorCode &errorCode) {
    if(U_FAILURE(errorCode)) {
        return;
    }
    int32_t length=s.length();
    if(length>0xffff) {
        // Too long: We store the length in 1 unit.
        errorCode=U_INDEX_OUTOFBOUNDS_ERROR;
        return;
    }
    stringOffset=strings.length();
    strings.append((UChar)length);
    value=val;
    strings.append(s);
}

int32_t
UCharsTrieElement::compareStringTo(const UCharsTrieElement &other, const UnicodeString &strings) const {
    return getString(strings).compare(other.getString(strings));
}

UCharsTrieBuilder::UCharsTrieBuilder(UErrorCode & /*errorCode*/)
        : elements(NULL), elementsCapacity(0), elementsLength(0),
          uchars(NULL), ucharsCapacity(0), ucharsLength(0) {}

UCharsTrieBuilder::~UCharsTrieBuilder() {
    delete[] elements;
    uprv_free(uchars);
}

UCharsTrieBuilder &
UCharsTrieBuilder::add(const UnicodeString &s, int32_t value, UErrorCode &errorCode) {
    if(U_FAILURE(errorCode)) {
        return *this;
    }
    if(ucharsLength>0) {
        // Cannot add elements after building.
        errorCode=U_NO_WRITE_PERMISSION;
        return *this;
    }
    if(elementsLength==elementsCapacity) {
        int32_t newCapacity;
        if(elementsCapacity==0) {
            newCapacity=1024;
        } else {
            newCapacity=4*elementsCapacity;
        }
        UCharsTrieElement *newElements=new UCharsTrieElement[newCapacity];
        if(newElements==NULL) {
            errorCode=U_MEMORY_ALLOCATION_ERROR;
            return *this;
        }
        if(elementsLength>0) {
            uprv_memcpy(newElements, elements, (size_t)elementsLength*sizeof(UCharsTrieElement));
        }
        delete[] elements;
        elements=newElements;
        elementsCapacity=newCapacity;
    }
    elements[elementsLength++].setTo(s, value, strings, errorCode);
    if(U_SUCCESS(errorCode) && strings.isBogus()) {
        errorCode=U_MEMORY_ALLOCATION_ERROR;
    }
    return *this;
}

U_CDECL_BEGIN

static int32_t U_CALLCONV
compareElementStrings(const void *context, const void *left, const void *right) {
    const UnicodeString *strings=static_cast<const UnicodeString *>(context);
    const UCharsTrieElement *leftElement=static_cast<const UCharsTrieElement *>(left);
    const UCharsTrieElement *rightElement=static_cast<const UCharsTrieElement *>(right);
    return leftElement->compareStringTo(*rightElement, *strings);
}

U_CDECL_END

UCharsTrie *
UCharsTrieBuilder::build(UStringTrieBuildOption buildOption, UErrorCode &errorCode) {
    buildUChars(buildOption, errorCode);
    UCharsTrie *newTrie=NULL;
    if(U_SUCCESS(errorCode)) {
        newTrie=new UCharsTrie(uchars, uchars+(ucharsCapacity-ucharsLength));
        if(newTrie==NULL) {
            errorCode=U_MEMORY_ALLOCATION_ERROR;
        } else {
            uchars=NULL;  // The new trie now owns the array.
            ucharsCapacity=0;
        }
    }
    return newTrie;
}

UnicodeString &
UCharsTrieBuilder::buildUnicodeString(UStringTrieBuildOption buildOption, UnicodeString &result,
                                      UErrorCode &errorCode) {
    buildUChars(buildOption, errorCode);
    if(U_SUCCESS(errorCode)) {
        result.setTo(FALSE, uchars+(ucharsCapacity-ucharsLength), ucharsLength);
    }
    return result;
}

void
UCharsTrieBuilder::buildUChars(UStringTrieBuildOption buildOption, UErrorCode &errorCode) {
    if(U_FAILURE(errorCode)) {
        return;
    }
    if(uchars!=NULL && ucharsLength>0) {
        // Already built.
        return;
    }
    if(ucharsLength==0) {
        if(elementsLength==0) {
            errorCode=U_INDEX_OUTOFBOUNDS_ERROR;
            return;
        }
        if(strings.isBogus()) {
            errorCode=U_MEMORY_ALLOCATION_ERROR;
            return;
        }
        uprv_sortArray(elements, elementsLength, (int32_t)sizeof(UCharsTrieElement),
                      compareElementStrings, &strings,
                      FALSE,  // need not be a stable sort
                      &errorCode);
        if(U_FAILURE(errorCode)) {
            return;
        }
        // Duplicate strings are not allowed.
        UnicodeString prev=elements[0].getString(strings);
        for(int32_t i=1; i<elementsLength; ++i) {
            UnicodeString current=elements[i].getString(strings);
            if(prev==current) {
                errorCode=U_ILLEGAL_ARGUMENT_ERROR;
                return;
            }
            prev.fastCopyFrom(current);
        }
    }
    // Create and UChar-serialize the trie for the elements.
    ucharsLength=0;
    int32_t capacity=strings.length();
    if(capacity<1024) {
        capacity=1024;
    }
    if(ucharsCapacity<capacity) {
        uprv_free(uchars);
        uchars=static_cast<UChar *>(uprv_malloc(capacity*2));
        if(uchars==NULL) {
            errorCode=U_MEMORY_ALLOCATION_ERROR;
            ucharsCapacity=0;
            return;
        }
        ucharsCapacity=capacity;
    }
    StringTrieBuilder::build(buildOption, elementsLength, errorCode);
    if(uchars==NULL) {
        errorCode=U_MEMORY_ALLOCATION_ERROR;
    }
}

int32_t
UCharsTrieBuilder::getElementStringLength(int32_t i) const {
    return elements[i].getStringLength(strings);
}

UChar
UCharsTrieBuilder::getElementUnit(int32_t i, int32_t unitIndex) const {
    return elements[i].charAt(unitIndex, strings);
}

int32_t
UCharsTrieBuilder::getElementValue(int32_t i) const {
    return elements[i].getValue();
}

int32_t
UCharsTrieBuilder::getLimitOfLinearMatch(int32_t first, int32_t last, int32_t unitIndex) const {
    const UCharsTrieElement &firstElement=elements[first];
    const UCharsTrieElement &lastElement=elements[last];
    int32_t minStringLength=firstElement.getStringLength(strings);
    while(++unitIndex<minStringLength &&
            firstElement.charAt(unitIndex, strings)==
            lastElement.charAt(unitIndex, strings)) {}
    return unitIndex;
}

int32_t
UCharsTrieBuilder::countElementUnits(int32_t start, int32_t limit, int32_t unitIndex) const {
    int32_t length=0;  // Number of different units at unitIndex.
    int32_t i=start;
    do {
        UChar unit=elements[i++].charAt(unitIndex, strings);
        while(i<limit && unit==elements[i].charAt(unitIndex, strings)) {
            ++i;
        }
        ++length;
    } while(i<limit);
    return length;
}

int32_t
UCharsTrieBuilder::skipElementsBySomeUnits(int32_t i, int32_t unitIndex, int32_t count) const {
    do {
        UChar unit=elements[i++].charAt(unitIndex, strings);
        while(unit==elements[i].charAt(unitIndex, strings)) {
            ++i;
        }
    } while(--count>0);
    return i;
}

int32_t
UCharsTrieBuilder::indexOfElementWithNextUnit(int32_t i, int32_t unitIndex, UChar unit) const {
    while(unit==elements[i].charAt(unitIndex, strings)) {
        ++i;
    }
    return i;
}

UCharsTrieBuilder::UCTLinearMatchNode::UCTLinearMatchNode(const UChar *units, int32_t len, Node *nextNode)
        : LinearMatchNode(len, nextNode), s(units) {
    hash=hash*37+ustr_hashUCharsN(units, len);
}

UBool
UCharsTrieBuilder::UCTLinearMatchNode::operator==(const Node &other) const {
    if(this==&other) {
        return TRUE;
    }
    if(!LinearMatchNode::operator==(other)) {
        return FALSE;
    }
    const UCTLinearMatchNode &o=(const UCTLinearMatchNode &)other;
    return 0==u_memcmp(s, o.s, length);
}

void
UCharsTrieBuilder::UCTLinearMatchNode::write(StringTrieBuilder &builder) {
    UCharsTrieBuilder &b=(UCharsTrieBuilder &)builder;
    next->write(builder);
    b.write(s, length);
    offset=b.writeValueAndType(hasValue, value, b.getMinLinearMatch()+length-1);
}

StringTrieBuilder::Node *
UCharsTrieBuilder::createLinearMatchNode(int32_t i, int32_t unitIndex, int32_t length,
                                         Node *nextNode) const {
    return new UCTLinearMatchNode(
            elements[i].getString(strings).getBuffer()+unitIndex,
            length,
            nextNode);
}

UBool
UCharsTrieBuilder::ensureCapacity(int32_t length) {
    if(uchars==NULL) {
        return FALSE;  // previous memory allocation had failed
    }
    if(length>ucharsCapacity) {
        int32_t newCapacity=ucharsCapacity;
        do {
            newCapacity*=2;
        } while(newCapacity<=length);
        UChar *newUChars=static_cast<UChar *>(uprv_malloc(newCapacity*2));
        if(newUChars==NULL) {
            // unable to allocate memory
            uprv_free(uchars);
            uchars=NULL;
            ucharsCapacity=0;
            return FALSE;
        }
        u_memcpy(newUChars+(newCapacity-ucharsLength),
                 uchars+(ucharsCapacity-ucharsLength), ucharsLength);
        uprv_free(uchars);
        uchars=newUChars;
        ucharsCapacity=newCapacity;
    }
    return TRUE;
}

int32_t
UCharsTrieBuilder::write(int32_t unit) {
    int32_t newLength=ucharsLength+1;
    if(ensureCapacity(newLength)) {
        ucharsLength=newLength;
        uchars[ucharsCapacity-ucharsLength]=(UChar)unit;
    }
    return ucharsLength;
}

int32_t
UCharsTrieBuilder::write(const UChar *s, int32_t length) {
    int32_t newLength=ucharsLength+length;
    if(ensureCapacity(newLength)) {
        ucharsLength=newLength;
        u_memcpy(uchars+(ucharsCapacity-ucharsLength), s, length);
    }
    return ucharsLength;
}

int32_t
UCharsTrieBuilder::writeElementUnits(int32_t i, int32_t unitIndex, int32_t length) {
    return write(elements[i].getString(strings).getBuffer()+unitIndex, length);
}

int32_t
UCharsTrieBuilder::writeValueAndFinal(int32_t i, UBool isFinal) {
    if(0<=i && i<=UCharsTrie::kMaxOneUnitValue) {
        return write(i|(isFinal<<15));
    }
    UChar intUnits[3];
    int32_t length;
    if(i<0 || i>UCharsTrie::kMaxTwoUnitValue) {
        intUnits[0]=(UChar)(UCharsTrie::kThreeUnitValueLead);
        intUnits[1]=(UChar)((uint32_t)i>>16);
        intUnits[2]=(UChar)i;
        length=3;
    // } else if(i<=UCharsTrie::kMaxOneUnitValue) {
    //     intUnits[0]=(UChar)(i);
    //     length=1;
    } else {
        intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitValueLead+(i>>16));
        intUnits[1]=(UChar)i;
        length=2;
    }
    intUnits[0]=(UChar)(intUnits[0]|(isFinal<<15));
    return write(intUnits, length);
}

int32_t
UCharsTrieBuilder::writeValueAndType(UBool hasValue, int32_t value, int32_t node) {
    if(!hasValue) {
        return write(node);
    }
    UChar intUnits[3];
    int32_t length;
    if(value<0 || value>UCharsTrie::kMaxTwoUnitNodeValue) {
        intUnits[0]=(UChar)(UCharsTrie::kThreeUnitNodeValueLead);
        intUnits[1]=(UChar)((uint32_t)value>>16);
        intUnits[2]=(UChar)value;
        length=3;
    } else if(value<=UCharsTrie::kMaxOneUnitNodeValue) {
        intUnits[0]=(UChar)((value+1)<<6);
        length=1;
    } else {
        intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitNodeValueLead+((value>>10)&0x7fc0));
        intUnits[1]=(UChar)value;
        length=2;
    }
    intUnits[0]|=(UChar)node;
    return write(intUnits, length);
}

int32_t
UCharsTrieBuilder::writeDeltaTo(int32_t jumpTarget) {
    int32_t i=ucharsLength-jumpTarget;
    U_ASSERT(i>=0);
    if(i<=UCharsTrie::kMaxOneUnitDelta) {
        return write(i);
    }
    UChar intUnits[3];
    int32_t length;
    if(i<=UCharsTrie::kMaxTwoUnitDelta) {
        intUnits[0]=(UChar)(UCharsTrie::kMinTwoUnitDeltaLead+(i>>16));
        length=1;
    } else {
        intUnits[0]=(UChar)(UCharsTrie::kThreeUnitDeltaLead);
        intUnits[1]=(UChar)(i>>16);
        length=2;
    }
    intUnits[length++]=(UChar)i;
    return write(intUnits, length);
}

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