ICU 65.1: stringtriebuilder.h Source File

00001 // © 2016 and later: Unicode, Inc. and others.
00002 // License & terms of use: http://www.unicode.org/copyright.html
00003 /*
00004 *******************************************************************************
00005 *   Copyright (C) 2010-2012,2014, International Business Machines
00006 *   Corporation and others.  All Rights Reserved.
00007 *******************************************************************************
00008 *   file name:  stringtriebuilder.h
00009 *   encoding:   UTF-8
00010 *   tab size:   8 (not used)
00011 *   indentation:4
00012 *
00013 *   created on: 2010dec24
00014 *   created by: Markus W. Scherer
00015 */
00016 
00017 #ifndef __STRINGTRIEBUILDER_H__
00018 #define __STRINGTRIEBUILDER_H__
00019 
00020 #include "unicode/utypes.h"
00021 
00022 #if U_SHOW_CPLUSPLUS_API
00023 
00024 #include "unicode/uobject.h"
00025 
00031 // Forward declaration.
00033 struct UHashtable;
00034 typedef struct UHashtable UHashtable;
00036 
00041 enum UStringTrieBuildOption {
00046     USTRINGTRIE_BUILD_FAST,
00057     USTRINGTRIE_BUILD_SMALL
00058 };
00059 
00060 U_NAMESPACE_BEGIN
00061 
00068 class U_COMMON_API StringTrieBuilder : public UObject {
00069 public:
00070 #ifndef U_HIDE_INTERNAL_API
00071 
00072     static int32_t hashNode(const void *node);
00074     static UBool equalNodes(const void *left, const void *right);
00075 #endif  /* U_HIDE_INTERNAL_API */
00076 
00077 protected:
00078     // Do not enclose the protected default constructor with #ifndef U_HIDE_INTERNAL_API
00079     // or else the compiler will create a public default constructor.
00081     StringTrieBuilder();
00083     virtual ~StringTrieBuilder();
00084 
00085 #ifndef U_HIDE_INTERNAL_API
00086 
00087     void createCompactBuilder(int32_t sizeGuess, UErrorCode &errorCode);
00089     void deleteCompactBuilder();
00090 
00092     void build(UStringTrieBuildOption buildOption, int32_t elementsLength, UErrorCode &errorCode);
00093 
00095     int32_t writeNode(int32_t start, int32_t limit, int32_t unitIndex);
00097     int32_t writeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex, int32_t length);
00098 #endif  /* U_HIDE_INTERNAL_API */
00099 
00100     class Node;
00101 
00102 #ifndef U_HIDE_INTERNAL_API
00103 
00104     Node *makeNode(int32_t start, int32_t limit, int32_t unitIndex, UErrorCode &errorCode);
00106     Node *makeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex,
00107                             int32_t length, UErrorCode &errorCode);
00108 #endif  /* U_HIDE_INTERNAL_API */
00109 
00111     virtual int32_t getElementStringLength(int32_t i) const = 0;
00113     virtual char16_t getElementUnit(int32_t i, int32_t unitIndex) const = 0;
00115     virtual int32_t getElementValue(int32_t i) const = 0;
00116 
00117     // Finds the first unit index after this one where
00118     // the first and last element have different units again.
00120     virtual int32_t getLimitOfLinearMatch(int32_t first, int32_t last, int32_t unitIndex) const = 0;
00121 
00122     // Number of different units at unitIndex.
00124     virtual int32_t countElementUnits(int32_t start, int32_t limit, int32_t unitIndex) const = 0;
00126     virtual int32_t skipElementsBySomeUnits(int32_t i, int32_t unitIndex, int32_t count) const = 0;
00128     virtual int32_t indexOfElementWithNextUnit(int32_t i, int32_t unitIndex, char16_t unit) const = 0;
00129 
00131     virtual UBool matchNodesCanHaveValues() const = 0;
00132 
00134     virtual int32_t getMaxBranchLinearSubNodeLength() const = 0;
00136     virtual int32_t getMinLinearMatch() const = 0;
00138     virtual int32_t getMaxLinearMatchLength() const = 0;
00139 
00140 #ifndef U_HIDE_INTERNAL_API
00141     // max(BytesTrie::kMaxBranchLinearSubNodeLength, UCharsTrie::kMaxBranchLinearSubNodeLength).
00143     static const int32_t kMaxBranchLinearSubNodeLength=5;
00144 
00145     // Maximum number of nested split-branch levels for a branch on all 2^16 possible char16_t units.
00146     // log2(2^16/kMaxBranchLinearSubNodeLength) rounded up.
00148     static const int32_t kMaxSplitBranchLevels=14;
00149 
00160     Node *registerNode(Node *newNode, UErrorCode &errorCode);
00171     Node *registerFinalValue(int32_t value, UErrorCode &errorCode);
00172 #endif  /* U_HIDE_INTERNAL_API */
00173 
00174     /*
00175      * C++ note:
00176      * registerNode() and registerFinalValue() take ownership of their input nodes,
00177      * and only return owned nodes.
00178      * If they see a failure UErrorCode, they will delete the input node.
00179      * If they get a NULL pointer, they will record a U_MEMORY_ALLOCATION_ERROR.
00180      * If there is a failure, they return NULL.
00181      *
00182      * NULL Node pointers can be safely passed into other Nodes because
00183      * they call the static Node::hashCode() which checks for a NULL pointer first.
00184      *
00185      * Therefore, as long as builder functions register a new node,
00186      * they need to check for failures only before explicitly dereferencing
00187      * a Node pointer, or before setting a new UErrorCode.
00188      */
00189 
00190     // Hash set of nodes, maps from nodes to integer 1.
00192     UHashtable *nodes;
00193 
00194     // Do not conditionalize the following with #ifndef U_HIDE_INTERNAL_API,
00195     // it is needed for layout of other objects.
00200     class Node : public UObject {
00201     public:
00202         Node(int32_t initialHash) : hash(initialHash), offset(0) {}
00203         inline int32_t hashCode() const { return hash; }
00204         // Handles node==NULL.
00205         static inline int32_t hashCode(const Node *node) { return node==NULL ? 0 : node->hashCode(); }
00206         // Base class operator==() compares the actual class types.
00207         virtual UBool operator==(const Node &other) const;
00208         inline UBool operator!=(const Node &other) const { return !operator==(other); }
00236         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
00237         // write() must set the offset to a positive value.
00238         virtual void write(StringTrieBuilder &builder) = 0;
00239         // See markRightEdgesFirst.
00240         inline void writeUnlessInsideRightEdge(int32_t firstRight, int32_t lastRight,
00241                                                StringTrieBuilder &builder) {
00242             // Note: Edge numbers are negative, lastRight<=firstRight.
00243             // If offset>0 then this node and its sub-nodes have been written already
00244             // and we need not write them again.
00245             // If this node is part of the unwritten right branch edge,
00246             // then we wait until that is written.
00247             if(offset<0 && (offset<lastRight || firstRight<offset)) {
00248                 write(builder);
00249             }
00250         }
00251         inline int32_t getOffset() const { return offset; }
00252     protected:
00253         int32_t hash;
00254         int32_t offset;
00255     };
00256 
00257 #ifndef U_HIDE_INTERNAL_API
00258     // This class should not be overridden because
00259     // registerFinalValue() compares a stack-allocated FinalValueNode
00260     // (stack-allocated so that we don't unnecessarily create lots of duplicate nodes)
00261     // with the input node, and the
00262     // !Node::operator==(other) used inside FinalValueNode::operator==(other)
00263     // will be false if the typeid's are different.
00265     class FinalValueNode : public Node {
00266     public:
00267         FinalValueNode(int32_t v) : Node(0x111111u*37u+v), value(v) {}
00268         virtual UBool operator==(const Node &other) const;
00269         virtual void write(StringTrieBuilder &builder);
00270     protected:
00271         int32_t value;
00272     };
00273 #endif  /* U_HIDE_INTERNAL_API */
00274 
00275     // Do not conditionalize the following with #ifndef U_HIDE_INTERNAL_API,
00276     // it is needed for layout of other objects.
00280     class ValueNode : public Node {
00281     public:
00282         ValueNode(int32_t initialHash) : Node(initialHash), hasValue(FALSE), value(0) {}
00283         virtual UBool operator==(const Node &other) const;
00284         void setValue(int32_t v) {
00285             hasValue=TRUE;
00286             value=v;
00287             hash=hash*37u+v;
00288         }
00289     protected:
00290         UBool hasValue;
00291         int32_t value;
00292     };
00293 
00294 #ifndef U_HIDE_INTERNAL_API
00295 
00298     class IntermediateValueNode : public ValueNode {
00299     public:
00300         IntermediateValueNode(int32_t v, Node *nextNode)
00301                 : ValueNode(0x222222u*37u+hashCode(nextNode)), next(nextNode) { setValue(v); }
00302         virtual UBool operator==(const Node &other) const;
00303         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
00304         virtual void write(StringTrieBuilder &builder);
00305     protected:
00306         Node *next;
00307     };
00308 #endif  /* U_HIDE_INTERNAL_API */
00309 
00310     // Do not conditionalize the following with #ifndef U_HIDE_INTERNAL_API,
00311     // it is needed for layout of other objects.
00315     class LinearMatchNode : public ValueNode {
00316     public:
00317         LinearMatchNode(int32_t len, Node *nextNode)
00318                 : ValueNode((0x333333u*37u+len)*37u+hashCode(nextNode)),
00319                   length(len), next(nextNode) {}
00320         virtual UBool operator==(const Node &other) const;
00321         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
00322     protected:
00323         int32_t length;
00324         Node *next;
00325     };
00326 
00327 #ifndef U_HIDE_INTERNAL_API
00328 
00331     class BranchNode : public Node {
00332     public:
00333         BranchNode(int32_t initialHash) : Node(initialHash) {}
00334     protected:
00335         int32_t firstEdgeNumber;
00336     };
00337 
00341     class ListBranchNode : public BranchNode {
00342     public:
00343         ListBranchNode() : BranchNode(0x444444), length(0) {}
00344         virtual UBool operator==(const Node &other) const;
00345         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
00346         virtual void write(StringTrieBuilder &builder);
00347         // Adds a unit with a final value.
00348         void add(int32_t c, int32_t value) {
00349             units[length]=(char16_t)c;
00350             equal[length]=NULL;
00351             values[length]=value;
00352             ++length;
00353             hash=(hash*37u+c)*37u+value;
00354         }
00355         // Adds a unit which leads to another match node.
00356         void add(int32_t c, Node *node) {
00357             units[length]=(char16_t)c;
00358             equal[length]=node;
00359             values[length]=0;
00360             ++length;
00361             hash=(hash*37u+c)*37u+hashCode(node);
00362         }
00363     protected:
00364         Node *equal[kMaxBranchLinearSubNodeLength];  // NULL means "has final value".
00365         int32_t length;
00366         int32_t values[kMaxBranchLinearSubNodeLength];
00367         char16_t units[kMaxBranchLinearSubNodeLength];
00368     };
00369 
00373     class SplitBranchNode : public BranchNode {
00374     public:
00375         SplitBranchNode(char16_t middleUnit, Node *lessThanNode, Node *greaterOrEqualNode)
00376                 : BranchNode(((0x555555u*37u+middleUnit)*37u+
00377                               hashCode(lessThanNode))*37u+hashCode(greaterOrEqualNode)),
00378                   unit(middleUnit), lessThan(lessThanNode), greaterOrEqual(greaterOrEqualNode) {}
00379         virtual UBool operator==(const Node &other) const;
00380         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
00381         virtual void write(StringTrieBuilder &builder);
00382     protected:
00383         char16_t unit;
00384         Node *lessThan;
00385         Node *greaterOrEqual;
00386     };
00387 
00388     // Branch head node, for writing the actual node lead unit.
00390     class BranchHeadNode : public ValueNode {
00391     public:
00392         BranchHeadNode(int32_t len, Node *subNode)
00393                 : ValueNode((0x666666u*37u+len)*37u+hashCode(subNode)),
00394                   length(len), next(subNode) {}
00395         virtual UBool operator==(const Node &other) const;
00396         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
00397         virtual void write(StringTrieBuilder &builder);
00398     protected:
00399         int32_t length;
00400         Node *next;  // A branch sub-node.
00401     };
00402 
00403 #endif  /* U_HIDE_INTERNAL_API */
00405 
00406 
00407     virtual Node *createLinearMatchNode(int32_t i, int32_t unitIndex, int32_t length,
00408                                         Node *nextNode) const = 0;
00409 
00411     virtual int32_t write(int32_t unit) = 0;
00413     virtual int32_t writeElementUnits(int32_t i, int32_t unitIndex, int32_t length) = 0;
00415     virtual int32_t writeValueAndFinal(int32_t i, UBool isFinal) = 0;
00417     virtual int32_t writeValueAndType(UBool hasValue, int32_t value, int32_t node) = 0;
00419     virtual int32_t writeDeltaTo(int32_t jumpTarget) = 0;
00420 };
00421 
00422 U_NAMESPACE_END
00423 
00424 #endif /* U_SHOW_CPLUSPLUS_API */
00425 
00426 #endif  // __STRINGTRIEBUILDER_H__