| /* |
| ******************************************************************************* |
| * Copyright (C) 2010-2012, International Business Machines |
| * Corporation and others. All Rights Reserved. |
| ******************************************************************************* |
| * file name: stringtriebuilder.cpp |
| * encoding: US-ASCII |
| * tab size: 8 (not used) |
| * indentation:4 |
| * |
| * created on: 2010dec24 |
| * created by: Markus W. Scherer |
| */ |
| |
| #include "utypeinfo.h" // for 'typeid' to work |
| #include "unicode/utypes.h" |
| #include "unicode/stringtriebuilder.h" |
| #include "uassert.h" |
| #include "uhash.h" |
| |
| U_CDECL_BEGIN |
| |
| static int32_t U_CALLCONV |
| hashStringTrieNode(const UHashTok key) { |
| return icu::StringTrieBuilder::hashNode(key.pointer); |
| } |
| |
| static UBool U_CALLCONV |
| equalStringTrieNodes(const UHashTok key1, const UHashTok key2) { |
| return icu::StringTrieBuilder::equalNodes(key1.pointer, key2.pointer); |
| } |
| |
| U_CDECL_END |
| |
| U_NAMESPACE_BEGIN |
| |
| StringTrieBuilder::StringTrieBuilder() : nodes(NULL) {} |
| |
| StringTrieBuilder::~StringTrieBuilder() { |
| deleteCompactBuilder(); |
| } |
| |
| void |
| StringTrieBuilder::createCompactBuilder(int32_t sizeGuess, UErrorCode &errorCode) { |
| if(U_FAILURE(errorCode)) { |
| return; |
| } |
| nodes=uhash_openSize(hashStringTrieNode, equalStringTrieNodes, NULL, |
| sizeGuess, &errorCode); |
| if(U_SUCCESS(errorCode)) { |
| if(nodes==NULL) { |
| errorCode=U_MEMORY_ALLOCATION_ERROR; |
| } else { |
| uhash_setKeyDeleter(nodes, uprv_deleteUObject); |
| } |
| } |
| } |
| |
| void |
| StringTrieBuilder::deleteCompactBuilder() { |
| uhash_close(nodes); |
| nodes=NULL; |
| } |
| |
| void |
| StringTrieBuilder::build(UStringTrieBuildOption buildOption, int32_t elementsLength, |
| UErrorCode &errorCode) { |
| if(buildOption==USTRINGTRIE_BUILD_FAST) { |
| writeNode(0, elementsLength, 0); |
| } else /* USTRINGTRIE_BUILD_SMALL */ { |
| createCompactBuilder(2*elementsLength, errorCode); |
| Node *root=makeNode(0, elementsLength, 0, errorCode); |
| if(U_SUCCESS(errorCode)) { |
| root->markRightEdgesFirst(-1); |
| root->write(*this); |
| } |
| deleteCompactBuilder(); |
| } |
| } |
| |
| // Requires start<limit, |
| // and all strings of the [start..limit[ elements must be sorted and |
| // have a common prefix of length unitIndex. |
| int32_t |
| StringTrieBuilder::writeNode(int32_t start, int32_t limit, int32_t unitIndex) { |
| UBool hasValue=FALSE; |
| int32_t value=0; |
| int32_t type; |
| if(unitIndex==getElementStringLength(start)) { |
| // An intermediate or final value. |
| value=getElementValue(start++); |
| if(start==limit) { |
| return writeValueAndFinal(value, TRUE); // final-value node |
| } |
| hasValue=TRUE; |
| } |
| // Now all [start..limit[ strings are longer than unitIndex. |
| int32_t minUnit=getElementUnit(start, unitIndex); |
| int32_t maxUnit=getElementUnit(limit-1, unitIndex); |
| if(minUnit==maxUnit) { |
| // Linear-match node: All strings have the same character at unitIndex. |
| int32_t lastUnitIndex=getLimitOfLinearMatch(start, limit-1, unitIndex); |
| writeNode(start, limit, lastUnitIndex); |
| // Break the linear-match sequence into chunks of at most kMaxLinearMatchLength. |
| int32_t length=lastUnitIndex-unitIndex; |
| int32_t maxLinearMatchLength=getMaxLinearMatchLength(); |
| while(length>maxLinearMatchLength) { |
| lastUnitIndex-=maxLinearMatchLength; |
| length-=maxLinearMatchLength; |
| writeElementUnits(start, lastUnitIndex, maxLinearMatchLength); |
| write(getMinLinearMatch()+maxLinearMatchLength-1); |
| } |
| writeElementUnits(start, unitIndex, length); |
| type=getMinLinearMatch()+length-1; |
| } else { |
| // Branch node. |
| int32_t length=countElementUnits(start, limit, unitIndex); |
| // length>=2 because minUnit!=maxUnit. |
| writeBranchSubNode(start, limit, unitIndex, length); |
| if(--length<getMinLinearMatch()) { |
| type=length; |
| } else { |
| write(length); |
| type=0; |
| } |
| } |
| return writeValueAndType(hasValue, value, type); |
| } |
| |
| // start<limit && all strings longer than unitIndex && |
| // length different units at unitIndex |
| int32_t |
| StringTrieBuilder::writeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex, int32_t length) { |
| UChar middleUnits[kMaxSplitBranchLevels]; |
| int32_t lessThan[kMaxSplitBranchLevels]; |
| int32_t ltLength=0; |
| while(length>getMaxBranchLinearSubNodeLength()) { |
| // Branch on the middle unit. |
| // First, find the middle unit. |
| int32_t i=skipElementsBySomeUnits(start, unitIndex, length/2); |
| // Encode the less-than branch first. |
| middleUnits[ltLength]=getElementUnit(i, unitIndex); // middle unit |
| lessThan[ltLength]=writeBranchSubNode(start, i, unitIndex, length/2); |
| ++ltLength; |
| // Continue for the greater-or-equal branch. |
| start=i; |
| length=length-length/2; |
| } |
| // For each unit, find its elements array start and whether it has a final value. |
| int32_t starts[kMaxBranchLinearSubNodeLength]; |
| UBool isFinal[kMaxBranchLinearSubNodeLength-1]; |
| int32_t unitNumber=0; |
| do { |
| int32_t i=starts[unitNumber]=start; |
| UChar unit=getElementUnit(i++, unitIndex); |
| i=indexOfElementWithNextUnit(i, unitIndex, unit); |
| isFinal[unitNumber]= start==i-1 && unitIndex+1==getElementStringLength(start); |
| start=i; |
| } while(++unitNumber<length-1); |
| // unitNumber==length-1, and the maxUnit elements range is [start..limit[ |
| starts[unitNumber]=start; |
| |
| // Write the sub-nodes in reverse order: The jump lengths are deltas from |
| // after their own positions, so if we wrote the minUnit sub-node first, |
| // then its jump delta would be larger. |
| // Instead we write the minUnit sub-node last, for a shorter delta. |
| int32_t jumpTargets[kMaxBranchLinearSubNodeLength-1]; |
| do { |
| --unitNumber; |
| if(!isFinal[unitNumber]) { |
| jumpTargets[unitNumber]=writeNode(starts[unitNumber], starts[unitNumber+1], unitIndex+1); |
| } |
| } while(unitNumber>0); |
| // The maxUnit sub-node is written as the very last one because we do |
| // not jump for it at all. |
| unitNumber=length-1; |
| writeNode(start, limit, unitIndex+1); |
| int32_t offset=write(getElementUnit(start, unitIndex)); |
| // Write the rest of this node's unit-value pairs. |
| while(--unitNumber>=0) { |
| start=starts[unitNumber]; |
| int32_t value; |
| if(isFinal[unitNumber]) { |
| // Write the final value for the one string ending with this unit. |
| value=getElementValue(start); |
| } else { |
| // Write the delta to the start position of the sub-node. |
| value=offset-jumpTargets[unitNumber]; |
| } |
| writeValueAndFinal(value, isFinal[unitNumber]); |
| offset=write(getElementUnit(start, unitIndex)); |
| } |
| // Write the split-branch nodes. |
| while(ltLength>0) { |
| --ltLength; |
| writeDeltaTo(lessThan[ltLength]); |
| offset=write(middleUnits[ltLength]); |
| } |
| return offset; |
| } |
| |
| // Requires start<limit, |
| // and all strings of the [start..limit[ elements must be sorted and |
| // have a common prefix of length unitIndex. |
| StringTrieBuilder::Node * |
| StringTrieBuilder::makeNode(int32_t start, int32_t limit, int32_t unitIndex, UErrorCode &errorCode) { |
| if(U_FAILURE(errorCode)) { |
| return NULL; |
| } |
| UBool hasValue=FALSE; |
| int32_t value=0; |
| if(unitIndex==getElementStringLength(start)) { |
| // An intermediate or final value. |
| value=getElementValue(start++); |
| if(start==limit) { |
| return registerFinalValue(value, errorCode); |
| } |
| hasValue=TRUE; |
| } |
| Node *node; |
| // Now all [start..limit[ strings are longer than unitIndex. |
| int32_t minUnit=getElementUnit(start, unitIndex); |
| int32_t maxUnit=getElementUnit(limit-1, unitIndex); |
| if(minUnit==maxUnit) { |
| // Linear-match node: All strings have the same character at unitIndex. |
| int32_t lastUnitIndex=getLimitOfLinearMatch(start, limit-1, unitIndex); |
| Node *nextNode=makeNode(start, limit, lastUnitIndex, errorCode); |
| // Break the linear-match sequence into chunks of at most kMaxLinearMatchLength. |
| int32_t length=lastUnitIndex-unitIndex; |
| int32_t maxLinearMatchLength=getMaxLinearMatchLength(); |
| while(length>maxLinearMatchLength) { |
| lastUnitIndex-=maxLinearMatchLength; |
| length-=maxLinearMatchLength; |
| node=createLinearMatchNode(start, lastUnitIndex, maxLinearMatchLength, nextNode); |
| nextNode=registerNode(node, errorCode); |
| } |
| node=createLinearMatchNode(start, unitIndex, length, nextNode); |
| } else { |
| // Branch node. |
| int32_t length=countElementUnits(start, limit, unitIndex); |
| // length>=2 because minUnit!=maxUnit. |
| Node *subNode=makeBranchSubNode(start, limit, unitIndex, length, errorCode); |
| node=new BranchHeadNode(length, subNode); |
| } |
| if(hasValue && node!=NULL) { |
| if(matchNodesCanHaveValues()) { |
| ((ValueNode *)node)->setValue(value); |
| } else { |
| node=new IntermediateValueNode(value, registerNode(node, errorCode)); |
| } |
| } |
| return registerNode(node, errorCode); |
| } |
| |
| // start<limit && all strings longer than unitIndex && |
| // length different units at unitIndex |
| StringTrieBuilder::Node * |
| StringTrieBuilder::makeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex, |
| int32_t length, UErrorCode &errorCode) { |
| if(U_FAILURE(errorCode)) { |
| return NULL; |
| } |
| UChar middleUnits[kMaxSplitBranchLevels]; |
| Node *lessThan[kMaxSplitBranchLevels]; |
| int32_t ltLength=0; |
| while(length>getMaxBranchLinearSubNodeLength()) { |
| // Branch on the middle unit. |
| // First, find the middle unit. |
| int32_t i=skipElementsBySomeUnits(start, unitIndex, length/2); |
| // Create the less-than branch. |
| middleUnits[ltLength]=getElementUnit(i, unitIndex); // middle unit |
| lessThan[ltLength]=makeBranchSubNode(start, i, unitIndex, length/2, errorCode); |
| ++ltLength; |
| // Continue for the greater-or-equal branch. |
| start=i; |
| length=length-length/2; |
| } |
| if(U_FAILURE(errorCode)) { |
| return NULL; |
| } |
| ListBranchNode *listNode=new ListBranchNode(); |
| if(listNode==NULL) { |
| errorCode=U_MEMORY_ALLOCATION_ERROR; |
| return NULL; |
| } |
| // For each unit, find its elements array start and whether it has a final value. |
| int32_t unitNumber=0; |
| do { |
| int32_t i=start; |
| UChar unit=getElementUnit(i++, unitIndex); |
| i=indexOfElementWithNextUnit(i, unitIndex, unit); |
| if(start==i-1 && unitIndex+1==getElementStringLength(start)) { |
| listNode->add(unit, getElementValue(start)); |
| } else { |
| listNode->add(unit, makeNode(start, i, unitIndex+1, errorCode)); |
| } |
| start=i; |
| } while(++unitNumber<length-1); |
| // unitNumber==length-1, and the maxUnit elements range is [start..limit[ |
| UChar unit=getElementUnit(start, unitIndex); |
| if(start==limit-1 && unitIndex+1==getElementStringLength(start)) { |
| listNode->add(unit, getElementValue(start)); |
| } else { |
| listNode->add(unit, makeNode(start, limit, unitIndex+1, errorCode)); |
| } |
| Node *node=registerNode(listNode, errorCode); |
| // Create the split-branch nodes. |
| while(ltLength>0) { |
| --ltLength; |
| node=registerNode( |
| new SplitBranchNode(middleUnits[ltLength], lessThan[ltLength], node), errorCode); |
| } |
| return node; |
| } |
| |
| StringTrieBuilder::Node * |
| StringTrieBuilder::registerNode(Node *newNode, UErrorCode &errorCode) { |
| if(U_FAILURE(errorCode)) { |
| delete newNode; |
| return NULL; |
| } |
| if(newNode==NULL) { |
| errorCode=U_MEMORY_ALLOCATION_ERROR; |
| return NULL; |
| } |
| const UHashElement *old=uhash_find(nodes, newNode); |
| if(old!=NULL) { |
| delete newNode; |
| return (Node *)old->key.pointer; |
| } |
| // If uhash_puti() returns a non-zero value from an equivalent, previously |
| // registered node, then uhash_find() failed to find that and we will leak newNode. |
| #if U_DEBUG |
| int32_t oldValue= // Only in debug mode to avoid a compiler warning about unused oldValue. |
| #endif |
| uhash_puti(nodes, newNode, 1, &errorCode); |
| U_ASSERT(oldValue==0); |
| if(U_FAILURE(errorCode)) { |
| delete newNode; |
| return NULL; |
| } |
| return newNode; |
| } |
| |
| StringTrieBuilder::Node * |
| StringTrieBuilder::registerFinalValue(int32_t value, UErrorCode &errorCode) { |
| if(U_FAILURE(errorCode)) { |
| return NULL; |
| } |
| FinalValueNode key(value); |
| const UHashElement *old=uhash_find(nodes, &key); |
| if(old!=NULL) { |
| return (Node *)old->key.pointer; |
| } |
| Node *newNode=new FinalValueNode(value); |
| if(newNode==NULL) { |
| errorCode=U_MEMORY_ALLOCATION_ERROR; |
| return NULL; |
| } |
| // If uhash_puti() returns a non-zero value from an equivalent, previously |
| // registered node, then uhash_find() failed to find that and we will leak newNode. |
| #if U_DEBUG |
| int32_t oldValue= // Only in debug mode to avoid a compiler warning about unused oldValue. |
| #endif |
| uhash_puti(nodes, newNode, 1, &errorCode); |
| U_ASSERT(oldValue==0); |
| if(U_FAILURE(errorCode)) { |
| delete newNode; |
| return NULL; |
| } |
| return newNode; |
| } |
| |
| UBool |
| StringTrieBuilder::hashNode(const void *node) { |
| return ((const Node *)node)->hashCode(); |
| } |
| |
| UBool |
| StringTrieBuilder::equalNodes(const void *left, const void *right) { |
| return *(const Node *)left==*(const Node *)right; |
| } |
| |
| UBool |
| StringTrieBuilder::Node::operator==(const Node &other) const { |
| return this==&other || (typeid(*this)==typeid(other) && hash==other.hash); |
| } |
| |
| int32_t |
| StringTrieBuilder::Node::markRightEdgesFirst(int32_t edgeNumber) { |
| if(offset==0) { |
| offset=edgeNumber; |
| } |
| return edgeNumber; |
| } |
| |
| UBool |
| StringTrieBuilder::FinalValueNode::operator==(const Node &other) const { |
| if(this==&other) { |
| return TRUE; |
| } |
| if(!Node::operator==(other)) { |
| return FALSE; |
| } |
| const FinalValueNode &o=(const FinalValueNode &)other; |
| return value==o.value; |
| } |
| |
| void |
| StringTrieBuilder::FinalValueNode::write(StringTrieBuilder &builder) { |
| offset=builder.writeValueAndFinal(value, TRUE); |
| } |
| |
| UBool |
| StringTrieBuilder::ValueNode::operator==(const Node &other) const { |
| if(this==&other) { |
| return TRUE; |
| } |
| if(!Node::operator==(other)) { |
| return FALSE; |
| } |
| const ValueNode &o=(const ValueNode &)other; |
| return hasValue==o.hasValue && (!hasValue || value==o.value); |
| } |
| |
| UBool |
| StringTrieBuilder::IntermediateValueNode::operator==(const Node &other) const { |
| if(this==&other) { |
| return TRUE; |
| } |
| if(!ValueNode::operator==(other)) { |
| return FALSE; |
| } |
| const IntermediateValueNode &o=(const IntermediateValueNode &)other; |
| return next==o.next; |
| } |
| |
| int32_t |
| StringTrieBuilder::IntermediateValueNode::markRightEdgesFirst(int32_t edgeNumber) { |
| if(offset==0) { |
| offset=edgeNumber=next->markRightEdgesFirst(edgeNumber); |
| } |
| return edgeNumber; |
| } |
| |
| void |
| StringTrieBuilder::IntermediateValueNode::write(StringTrieBuilder &builder) { |
| next->write(builder); |
| offset=builder.writeValueAndFinal(value, FALSE); |
| } |
| |
| UBool |
| StringTrieBuilder::LinearMatchNode::operator==(const Node &other) const { |
| if(this==&other) { |
| return TRUE; |
| } |
| if(!ValueNode::operator==(other)) { |
| return FALSE; |
| } |
| const LinearMatchNode &o=(const LinearMatchNode &)other; |
| return length==o.length && next==o.next; |
| } |
| |
| int32_t |
| StringTrieBuilder::LinearMatchNode::markRightEdgesFirst(int32_t edgeNumber) { |
| if(offset==0) { |
| offset=edgeNumber=next->markRightEdgesFirst(edgeNumber); |
| } |
| return edgeNumber; |
| } |
| |
| UBool |
| StringTrieBuilder::ListBranchNode::operator==(const Node &other) const { |
| if(this==&other) { |
| return TRUE; |
| } |
| if(!Node::operator==(other)) { |
| return FALSE; |
| } |
| const ListBranchNode &o=(const ListBranchNode &)other; |
| for(int32_t i=0; i<length; ++i) { |
| if(units[i]!=o.units[i] || values[i]!=o.values[i] || equal[i]!=o.equal[i]) { |
| return FALSE; |
| } |
| } |
| return TRUE; |
| } |
| |
| int32_t |
| StringTrieBuilder::ListBranchNode::markRightEdgesFirst(int32_t edgeNumber) { |
| if(offset==0) { |
| firstEdgeNumber=edgeNumber; |
| int32_t step=0; |
| int32_t i=length; |
| do { |
| Node *edge=equal[--i]; |
| if(edge!=NULL) { |
| edgeNumber=edge->markRightEdgesFirst(edgeNumber-step); |
| } |
| // For all but the rightmost edge, decrement the edge number. |
| step=1; |
| } while(i>0); |
| offset=edgeNumber; |
| } |
| return edgeNumber; |
| } |
| |
| void |
| StringTrieBuilder::ListBranchNode::write(StringTrieBuilder &builder) { |
| // Write the sub-nodes in reverse order: The jump lengths are deltas from |
| // after their own positions, so if we wrote the minUnit sub-node first, |
| // then its jump delta would be larger. |
| // Instead we write the minUnit sub-node last, for a shorter delta. |
| int32_t unitNumber=length-1; |
| Node *rightEdge=equal[unitNumber]; |
| int32_t rightEdgeNumber= rightEdge==NULL ? firstEdgeNumber : rightEdge->getOffset(); |
| do { |
| --unitNumber; |
| if(equal[unitNumber]!=NULL) { |
| equal[unitNumber]->writeUnlessInsideRightEdge(firstEdgeNumber, rightEdgeNumber, builder); |
| } |
| } while(unitNumber>0); |
| // The maxUnit sub-node is written as the very last one because we do |
| // not jump for it at all. |
| unitNumber=length-1; |
| if(rightEdge==NULL) { |
| builder.writeValueAndFinal(values[unitNumber], TRUE); |
| } else { |
| rightEdge->write(builder); |
| } |
| offset=builder.write(units[unitNumber]); |
| // Write the rest of this node's unit-value pairs. |
| while(--unitNumber>=0) { |
| int32_t value; |
| UBool isFinal; |
| if(equal[unitNumber]==NULL) { |
| // Write the final value for the one string ending with this unit. |
| value=values[unitNumber]; |
| isFinal=TRUE; |
| } else { |
| // Write the delta to the start position of the sub-node. |
| U_ASSERT(equal[unitNumber]->getOffset()>0); |
| value=offset-equal[unitNumber]->getOffset(); |
| isFinal=FALSE; |
| } |
| builder.writeValueAndFinal(value, isFinal); |
| offset=builder.write(units[unitNumber]); |
| } |
| } |
| |
| UBool |
| StringTrieBuilder::SplitBranchNode::operator==(const Node &other) const { |
| if(this==&other) { |
| return TRUE; |
| } |
| if(!Node::operator==(other)) { |
| return FALSE; |
| } |
| const SplitBranchNode &o=(const SplitBranchNode &)other; |
| return unit==o.unit && lessThan==o.lessThan && greaterOrEqual==o.greaterOrEqual; |
| } |
| |
| int32_t |
| StringTrieBuilder::SplitBranchNode::markRightEdgesFirst(int32_t edgeNumber) { |
| if(offset==0) { |
| firstEdgeNumber=edgeNumber; |
| edgeNumber=greaterOrEqual->markRightEdgesFirst(edgeNumber); |
| offset=edgeNumber=lessThan->markRightEdgesFirst(edgeNumber-1); |
| } |
| return edgeNumber; |
| } |
| |
| void |
| StringTrieBuilder::SplitBranchNode::write(StringTrieBuilder &builder) { |
| // Encode the less-than branch first. |
| lessThan->writeUnlessInsideRightEdge(firstEdgeNumber, greaterOrEqual->getOffset(), builder); |
| // Encode the greater-or-equal branch last because we do not jump for it at all. |
| greaterOrEqual->write(builder); |
| // Write this node. |
| U_ASSERT(lessThan->getOffset()>0); |
| builder.writeDeltaTo(lessThan->getOffset()); // less-than |
| offset=builder.write(unit); |
| } |
| |
| UBool |
| StringTrieBuilder::BranchHeadNode::operator==(const Node &other) const { |
| if(this==&other) { |
| return TRUE; |
| } |
| if(!ValueNode::operator==(other)) { |
| return FALSE; |
| } |
| const BranchHeadNode &o=(const BranchHeadNode &)other; |
| return length==o.length && next==o.next; |
| } |
| |
| int32_t |
| StringTrieBuilder::BranchHeadNode::markRightEdgesFirst(int32_t edgeNumber) { |
| if(offset==0) { |
| offset=edgeNumber=next->markRightEdgesFirst(edgeNumber); |
| } |
| return edgeNumber; |
| } |
| |
| void |
| StringTrieBuilder::BranchHeadNode::write(StringTrieBuilder &builder) { |
| next->write(builder); |
| if(length<=builder.getMinLinearMatch()) { |
| offset=builder.writeValueAndType(hasValue, value, length-1); |
| } else { |
| builder.write(length-1); |
| offset=builder.writeValueAndType(hasValue, value, 0); |
| } |
| } |
| |
| U_NAMESPACE_END |
