icuSources/common/unicode/stringtriebuilder.h

   1 // © 2016 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html
   3 /*
   4 *******************************************************************************
   5 *   Copyright (C) 2010-2012,2014, International Business Machines
   6 *   Corporation and others.  All Rights Reserved.
   7 *******************************************************************************
   8 *   file name:  stringtriebuilder.h
   9 *   encoding:   UTF-8
  10 *   tab size:   8 (not used)
  11 *   indentation:4
  12 *
  13 *   created on: 2010dec24
  14 *   created by: Markus W. Scherer
  15 */
  16
  17 #ifndef __STRINGTRIEBUILDER_H__
  18 #define __STRINGTRIEBUILDER_H__
  19
  20 #include "unicode/utypes.h"
  21 #include "unicode/uobject.h"
  22
  23 /**
  24  * \file
  25  * \brief C++ API: Builder API for trie builders
  26  */
  27
  28 // Forward declaration.
  29 struct UHashtable;
  30 typedef struct UHashtable UHashtable;
  31
  32 /**
  33  * Build options for BytesTrieBuilder and CharsTrieBuilder.
  34  * @stable ICU 4.8
  35  */
  36 enum UStringTrieBuildOption {
  37     /**
  38      * Builds a trie quickly.
  39      * @stable ICU 4.8
  40      */
  41     USTRINGTRIE_BUILD_FAST,
  42     /**
  43      * Builds a trie more slowly, attempting to generate
  44      * a shorter but equivalent serialization.
  45      * This build option also uses more memory.
  46      *
  47      * This option can be effective when many integer values are the same
  48      * and string/byte sequence suffixes can be shared.
  49      * Runtime speed is not expected to improve.
  50      * @stable ICU 4.8
  51      */
  52     USTRINGTRIE_BUILD_SMALL
  53 };
  54
  55 #if U_SHOW_CPLUSPLUS_API
  56 U_NAMESPACE_BEGIN
  57
  58 /**
  59  * Base class for string trie builder classes.
  60  *
  61  * This class is not intended for public subclassing.
  62  * @stable ICU 4.8
  63  */
  64 class U_COMMON_API StringTrieBuilder : public UObject {
  65 public:
  66 #ifndef U_HIDE_INTERNAL_API
  67     /** @internal */
  68     static UBool hashNode(const void *node);
  69     /** @internal */
  70     static UBool equalNodes(const void *left, const void *right);
  71 #endif  /* U_HIDE_INTERNAL_API */
  72
  73 protected:
  74     // Do not enclose the protected default constructor with #ifndef U_HIDE_INTERNAL_API
  75     // or else the compiler will create a public default constructor.
  76     /** @internal */
  77     StringTrieBuilder();
  78     /** @internal */
  79     virtual ~StringTrieBuilder();
  80
  81 #ifndef U_HIDE_INTERNAL_API
  82     /** @internal */
  83     void createCompactBuilder(int32_t sizeGuess, UErrorCode &errorCode);
  84     /** @internal */
  85     void deleteCompactBuilder();
  86
  87     /** @internal */
  88     void build(UStringTrieBuildOption buildOption, int32_t elementsLength, UErrorCode &errorCode);
  89
  90     /** @internal */
  91     int32_t writeNode(int32_t start, int32_t limit, int32_t unitIndex);
  92     /** @internal */
  93     int32_t writeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex, int32_t length);
  94 #endif  /* U_HIDE_INTERNAL_API */
  95
  96     class Node;
  97
  98 #ifndef U_HIDE_INTERNAL_API
  99     /** @internal */
 100     Node *makeNode(int32_t start, int32_t limit, int32_t unitIndex, UErrorCode &errorCode);
 101     /** @internal */
 102     Node *makeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex,
 103                             int32_t length, UErrorCode &errorCode);
 104 #endif  /* U_HIDE_INTERNAL_API */
 105
 106     /** @internal */
 107     virtual int32_t getElementStringLength(int32_t i) const = 0;
 108     /** @internal */
 109     virtual char16_t getElementUnit(int32_t i, int32_t unitIndex) const = 0;
 110     /** @internal */
 111     virtual int32_t getElementValue(int32_t i) const = 0;
 112
 113     // Finds the first unit index after this one where
 114     // the first and last element have different units again.
 115     /** @internal */
 116     virtual int32_t getLimitOfLinearMatch(int32_t first, int32_t last, int32_t unitIndex) const = 0;
 117
 118     // Number of different units at unitIndex.
 119     /** @internal */
 120     virtual int32_t countElementUnits(int32_t start, int32_t limit, int32_t unitIndex) const = 0;
 121     /** @internal */
 122     virtual int32_t skipElementsBySomeUnits(int32_t i, int32_t unitIndex, int32_t count) const = 0;
 123     /** @internal */
 124     virtual int32_t indexOfElementWithNextUnit(int32_t i, int32_t unitIndex, char16_t unit) const = 0;
 125
 126     /** @internal */
 127     virtual UBool matchNodesCanHaveValues() const = 0;
 128
 129     /** @internal */
 130     virtual int32_t getMaxBranchLinearSubNodeLength() const = 0;
 131     /** @internal */
 132     virtual int32_t getMinLinearMatch() const = 0;
 133     /** @internal */
 134     virtual int32_t getMaxLinearMatchLength() const = 0;
 135
 136 #ifndef U_HIDE_INTERNAL_API
 137     // max(BytesTrie::kMaxBranchLinearSubNodeLength, UCharsTrie::kMaxBranchLinearSubNodeLength).
 138     /** @internal */
 139     static const int32_t kMaxBranchLinearSubNodeLength=5;
 140
 141     // Maximum number of nested split-branch levels for a branch on all 2^16 possible char16_t units.
 142     // log2(2^16/kMaxBranchLinearSubNodeLength) rounded up.
 143     /** @internal */
 144     static const int32_t kMaxSplitBranchLevels=14;
 145
 146     /**
 147      * Makes sure that there is only one unique node registered that is
 148      * equivalent to newNode.
 149      * @param newNode Input node. The builder takes ownership.
 150      * @param errorCode ICU in/out UErrorCode.
 151                         Set to U_MEMORY_ALLOCATION_ERROR if it was success but newNode==NULL.
 152      * @return newNode if it is the first of its kind, or
 153      *         an equivalent node if newNode is a duplicate.
 154      * @internal
 155      */
 156     Node *registerNode(Node *newNode, UErrorCode &errorCode);
 157     /**
 158      * Makes sure that there is only one unique FinalValueNode registered
 159      * with this value.
 160      * Avoids creating a node if the value is a duplicate.
 161      * @param value A final value.
 162      * @param errorCode ICU in/out UErrorCode.
 163                         Set to U_MEMORY_ALLOCATION_ERROR if it was success but newNode==NULL.
 164      * @return A FinalValueNode with the given value.
 165      * @internal
 166      */
 167     Node *registerFinalValue(int32_t value, UErrorCode &errorCode);
 168 #endif  /* U_HIDE_INTERNAL_API */
 169
 170     /*
 171      * C++ note:
 172      * registerNode() and registerFinalValue() take ownership of their input nodes,
 173      * and only return owned nodes.
 174      * If they see a failure UErrorCode, they will delete the input node.
 175      * If they get a NULL pointer, they will record a U_MEMORY_ALLOCATION_ERROR.
 176      * If there is a failure, they return NULL.
 177      *
 178      * NULL Node pointers can be safely passed into other Nodes because
 179      * they call the static Node::hashCode() which checks for a NULL pointer first.
 180      *
 181      * Therefore, as long as builder functions register a new node,
 182      * they need to check for failures only before explicitly dereferencing
 183      * a Node pointer, or before setting a new UErrorCode.
 184      */
 185
 186     // Hash set of nodes, maps from nodes to integer 1.
 187     /** @internal */
 188     UHashtable *nodes;
 189
 190     // Do not conditionalize the following with #ifndef U_HIDE_INTERNAL_API,
 191     // it is needed for layout of other objects.
 192     /** @internal */
 193     class Node : public UObject {
 194     public:
 195         Node(int32_t initialHash) : hash(initialHash), offset(0) {}
 196         inline int32_t hashCode() const { return hash; }
 197         // Handles node==NULL.
 198         static inline int32_t hashCode(const Node *node) { return node==NULL ? 0 : node->hashCode(); }
 199         // Base class operator==() compares the actual class types.
 200         virtual UBool operator==(const Node &other) const;
 201         inline UBool operator!=(const Node &other) const { return !operator==(other); }
 202         /**
 203          * Traverses the Node graph and numbers branch edges, with rightmost edges first.
 204          * This is to avoid writing a duplicate node twice.
 205          *
 206          * Branch nodes in this trie data structure are not symmetric.
 207          * Most branch edges "jump" to other nodes but the rightmost branch edges
 208          * just continue without a jump.
 209          * Therefore, write() must write the rightmost branch edge last
 210          * (trie units are written backwards), and must write it at that point even if
 211          * it is a duplicate of a node previously written elsewhere.
 212          *
 213          * This function visits and marks right branch edges first.
 214          * Edges are numbered with increasingly negative values because we share the
 215          * offset field which gets positive values when nodes are written.
 216          * A branch edge also remembers the first number for any of its edges.
 217          *
 218          * When a further-left branch edge has a number in the range of the rightmost
 219          * edge's numbers, then it will be written as part of the required right edge
 220          * and we can avoid writing it first.
 221          *
 222          * After root.markRightEdgesFirst(-1) the offsets of all nodes are negative
 223          * edge numbers.
 224          *
 225          * @param edgeNumber The first edge number for this node and its sub-nodes.
 226          * @return An edge number that is at least the maximum-negative
 227          *         of the input edge number and the numbers of this node and all of its sub-nodes.
 228          */
 229         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
 230         // write() must set the offset to a positive value.
 231         virtual void write(StringTrieBuilder &builder) = 0;
 232         // See markRightEdgesFirst.
 233         inline void writeUnlessInsideRightEdge(int32_t firstRight, int32_t lastRight,
 234                                                StringTrieBuilder &builder) {
 235             // Note: Edge numbers are negative, lastRight<=firstRight.
 236             // If offset>0 then this node and its sub-nodes have been written already
 237             // and we need not write them again.
 238             // If this node is part of the unwritten right branch edge,
 239             // then we wait until that is written.
 240             if(offset<0 && (offset<lastRight || firstRight<offset)) {
 241                 write(builder);
 242             }
 243         }
 244         inline int32_t getOffset() const { return offset; }
 245     protected:
 246         int32_t hash;
 247         int32_t offset;
 248     };
 249
 250 #ifndef U_HIDE_INTERNAL_API
 251     // This class should not be overridden because
 252     // registerFinalValue() compares a stack-allocated FinalValueNode
 253     // (stack-allocated so that we don't unnecessarily create lots of duplicate nodes)
 254     // with the input node, and the
 255     // !Node::operator==(other) used inside FinalValueNode::operator==(other)
 256     // will be false if the typeid's are different.
 257     /** @internal */
 258     class FinalValueNode : public Node {
 259     public:
 260         FinalValueNode(int32_t v) : Node(0x111111u*37u+v), value(v) {}
 261         virtual UBool operator==(const Node &other) const;
 262         virtual void write(StringTrieBuilder &builder);
 263     protected:
 264         int32_t value;
 265     };
 266 #endif  /* U_HIDE_INTERNAL_API */
 267
 268     // Do not conditionalize the following with #ifndef U_HIDE_INTERNAL_API,
 269     // it is needed for layout of other objects.
 270     /**
 271      * @internal
 272      */
 273     class ValueNode : public Node {
 274     public:
 275         ValueNode(int32_t initialHash) : Node(initialHash), hasValue(FALSE), value(0) {}
 276         virtual UBool operator==(const Node &other) const;
 277         void setValue(int32_t v) {
 278             hasValue=TRUE;
 279             value=v;
 280             hash=hash*37u+v;
 281         }
 282     protected:
 283         UBool hasValue;
 284         int32_t value;
 285     };
 286
 287 #ifndef U_HIDE_INTERNAL_API
 288     /**
 289      * @internal
 290      */
 291     class IntermediateValueNode : public ValueNode {
 292     public:
 293         IntermediateValueNode(int32_t v, Node *nextNode)
 294                 : ValueNode(0x222222u*37u+hashCode(nextNode)), next(nextNode) { setValue(v); }
 295         virtual UBool operator==(const Node &other) const;
 296         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
 297         virtual void write(StringTrieBuilder &builder);
 298     protected:
 299         Node *next;
 300     };
 301 #endif  /* U_HIDE_INTERNAL_API */
 302
 303     // Do not conditionalize the following with #ifndef U_HIDE_INTERNAL_API,
 304     // it is needed for layout of other objects.
 305     /**
 306      * @internal
 307      */
 308     class LinearMatchNode : public ValueNode {
 309     public:
 310         LinearMatchNode(int32_t len, Node *nextNode)
 311                 : ValueNode((0x333333u*37u+len)*37u+hashCode(nextNode)),
 312                   length(len), next(nextNode) {}
 313         virtual UBool operator==(const Node &other) const;
 314         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
 315     protected:
 316         int32_t length;
 317         Node *next;
 318     };
 319
 320 #ifndef U_HIDE_INTERNAL_API
 321     /**
 322      * @internal
 323      */
 324     class BranchNode : public Node {
 325     public:
 326         BranchNode(int32_t initialHash) : Node(initialHash) {}
 327     protected:
 328         int32_t firstEdgeNumber;
 329     };
 330
 331     /**
 332      * @internal
 333      */
 334     class ListBranchNode : public BranchNode {
 335     public:
 336         ListBranchNode() : BranchNode(0x444444), length(0) {}
 337         virtual UBool operator==(const Node &other) const;
 338         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
 339         virtual void write(StringTrieBuilder &builder);
 340         // Adds a unit with a final value.
 341         void add(int32_t c, int32_t value) {
 342             units[length]=(char16_t)c;
 343             equal[length]=NULL;
 344             values[length]=value;
 345             ++length;
 346             hash=(hash*37u+c)*37u+value;
 347         }
 348         // Adds a unit which leads to another match node.
 349         void add(int32_t c, Node *node) {
 350             units[length]=(char16_t)c;
 351             equal[length]=node;
 352             values[length]=0;
 353             ++length;
 354             hash=(hash*37u+c)*37u+hashCode(node);
 355         }
 356     protected:
 357         Node *equal[kMaxBranchLinearSubNodeLength];  // NULL means "has final value".
 358         int32_t length;
 359         int32_t values[kMaxBranchLinearSubNodeLength];
 360         char16_t units[kMaxBranchLinearSubNodeLength];
 361     };
 362
 363     /**
 364      * @internal
 365      */
 366     class SplitBranchNode : public BranchNode {
 367     public:
 368         SplitBranchNode(char16_t middleUnit, Node *lessThanNode, Node *greaterOrEqualNode)
 369                 : BranchNode(((0x555555u*37u+middleUnit)*37u+
 370                               hashCode(lessThanNode))*37u+hashCode(greaterOrEqualNode)),
 371                   unit(middleUnit), lessThan(lessThanNode), greaterOrEqual(greaterOrEqualNode) {}
 372         virtual UBool operator==(const Node &other) const;
 373         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
 374         virtual void write(StringTrieBuilder &builder);
 375     protected:
 376         char16_t unit;
 377         Node *lessThan;
 378         Node *greaterOrEqual;
 379     };
 380
 381     // Branch head node, for writing the actual node lead unit.
 382     /** @internal */
 383     class BranchHeadNode : public ValueNode {
 384     public:
 385         BranchHeadNode(int32_t len, Node *subNode)
 386                 : ValueNode((0x666666u*37u+len)*37u+hashCode(subNode)),
 387                   length(len), next(subNode) {}
 388         virtual UBool operator==(const Node &other) const;
 389         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
 390         virtual void write(StringTrieBuilder &builder);
 391     protected:
 392         int32_t length;
 393         Node *next;  // A branch sub-node.
 394     };
 395 #endif  /* U_HIDE_INTERNAL_API */
 396
 397     /** @internal */
 398     virtual Node *createLinearMatchNode(int32_t i, int32_t unitIndex, int32_t length,
 399                                         Node *nextNode) const = 0;
 400
 401     /** @internal */
 402     virtual int32_t write(int32_t unit) = 0;
 403     /** @internal */
 404     virtual int32_t writeElementUnits(int32_t i, int32_t unitIndex, int32_t length) = 0;
 405     /** @internal */
 406     virtual int32_t writeValueAndFinal(int32_t i, UBool isFinal) = 0;
 407     /** @internal */
 408     virtual int32_t writeValueAndType(UBool hasValue, int32_t value, int32_t node) = 0;
 409     /** @internal */
 410     virtual int32_t writeDeltaTo(int32_t jumpTarget) = 0;
 411 };
 412
 413 U_NAMESPACE_END
 414 #endif // U_SHOW_CPLUSPLUS_API
 415
 416 #endif  // __STRINGTRIEBUILDER_H__