The Tor Browser: intl/icu/source/common/unicode/stringtriebuilder.h@6474c204b198 (annotated)

intl/icu/source/common/unicode/stringtriebuilder.h@6474c204b198 (annotated)

intl/icu/source/common/unicode/stringtriebuilder.h

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /*
 *******************************************************************************
 *   Copyright (C) 2010-2012, International Business Machines
 *   Corporation and others.  All Rights Reserved.
 *******************************************************************************
 *   file name:  stringtriebuilder.h
 *   encoding:   US-ASCII
 *   tab size:   8 (not used)
 *   indentation:4
 *
 *   created on: 2010dec24
 *   created by: Markus W. Scherer
 */
 #ifndef __STRINGTRIEBUILDER_H__
 #define __STRINGTRIEBUILDER_H__
 #include "unicode/utypes.h"
 #include "unicode/uobject.h"
 /**
  * \file
  * \brief C++ API: Builder API for trie builders
  */
 // Forward declaration.
 struct UHashtable;
 typedef struct UHashtable UHashtable;
 /**
  * Build options for BytesTrieBuilder and CharsTrieBuilder.
  * @stable ICU 4.8
  */
 enum UStringTrieBuildOption {
     /**
      * Builds a trie quickly.
      * @stable ICU 4.8
      */
     USTRINGTRIE_BUILD_FAST,
     /**
      * Builds a trie more slowly, attempting to generate
      * a shorter but equivalent serialization.
      * This build option also uses more memory.
      *
      * This option can be effective when many integer values are the same
      * and string/byte sequence suffixes can be shared.
      * Runtime speed is not expected to improve.
      * @stable ICU 4.8
      */
     USTRINGTRIE_BUILD_SMALL
 };
 U_NAMESPACE_BEGIN
 /**
  * Base class for string trie builder classes.
  *
  * This class is not intended for public subclassing.
  * @stable ICU 4.8
  */
 class U_COMMON_API StringTrieBuilder : public UObject {
 public:
 #ifndef U_HIDE_INTERNAL_API
     /** @internal */
     static UBool hashNode(const void *node);
     /** @internal */
     static UBool equalNodes(const void *left, const void *right);
 #endif  /* U_HIDE_INTERNAL_API */
 protected:
     // Do not enclose the protected default constructor with #ifndef U_HIDE_INTERNAL_API
     // or else the compiler will create a public default constructor.
     /** @internal */
     StringTrieBuilder();
     /** @internal */
     virtual ~StringTrieBuilder();
 #ifndef U_HIDE_INTERNAL_API
     /** @internal */
     void createCompactBuilder(int32_t sizeGuess, UErrorCode &errorCode);
     /** @internal */
     void deleteCompactBuilder();
     /** @internal */
     void build(UStringTrieBuildOption buildOption, int32_t elementsLength, UErrorCode &errorCode);
     /** @internal */
     int32_t writeNode(int32_t start, int32_t limit, int32_t unitIndex);
     /** @internal */
     int32_t writeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex, int32_t length);
 #endif  /* U_HIDE_INTERNAL_API */
     class Node;
 #ifndef U_HIDE_INTERNAL_API
     /** @internal */
     Node *makeNode(int32_t start, int32_t limit, int32_t unitIndex, UErrorCode &errorCode);
     /** @internal */
     Node *makeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex,
                             int32_t length, UErrorCode &errorCode);
 #endif  /* U_HIDE_INTERNAL_API */
     /** @internal */
     virtual int32_t getElementStringLength(int32_t i) const = 0;
     /** @internal */
     virtual UChar getElementUnit(int32_t i, int32_t unitIndex) const = 0;
     /** @internal */
     virtual int32_t getElementValue(int32_t i) const = 0;
     // Finds the first unit index after this one where
     // the first and last element have different units again.
     /** @internal */
     virtual int32_t getLimitOfLinearMatch(int32_t first, int32_t last, int32_t unitIndex) const = 0;
     // Number of different units at unitIndex.
     /** @internal */
     virtual int32_t countElementUnits(int32_t start, int32_t limit, int32_t unitIndex) const = 0;
     /** @internal */
     virtual int32_t skipElementsBySomeUnits(int32_t i, int32_t unitIndex, int32_t count) const = 0;
     /** @internal */
     virtual int32_t indexOfElementWithNextUnit(int32_t i, int32_t unitIndex, UChar unit) const = 0;
     /** @internal */
     virtual UBool matchNodesCanHaveValues() const = 0;
     /** @internal */
     virtual int32_t getMaxBranchLinearSubNodeLength() const = 0;
     /** @internal */
     virtual int32_t getMinLinearMatch() const = 0;
     /** @internal */
     virtual int32_t getMaxLinearMatchLength() const = 0;
 #ifndef U_HIDE_INTERNAL_API
     // max(BytesTrie::kMaxBranchLinearSubNodeLength, UCharsTrie::kMaxBranchLinearSubNodeLength).
     /** @internal */
     static const int32_t kMaxBranchLinearSubNodeLength=5;
     // Maximum number of nested split-branch levels for a branch on all 2^16 possible UChar units.
     // log2(2^16/kMaxBranchLinearSubNodeLength) rounded up.
     /** @internal */
     static const int32_t kMaxSplitBranchLevels=14;
     /**
      * Makes sure that there is only one unique node registered that is
      * equivalent to newNode.
      * @param newNode Input node. The builder takes ownership.
      * @param errorCode ICU in/out UErrorCode.
                         Set to U_MEMORY_ALLOCATION_ERROR if it was success but newNode==NULL.
      * @return newNode if it is the first of its kind, or
      *         an equivalent node if newNode is a duplicate.
      * @internal
      */
     Node *registerNode(Node *newNode, UErrorCode &errorCode);
     /**
      * Makes sure that there is only one unique FinalValueNode registered
      * with this value.
      * Avoids creating a node if the value is a duplicate.
      * @param value A final value.
      * @param errorCode ICU in/out UErrorCode.
                         Set to U_MEMORY_ALLOCATION_ERROR if it was success but newNode==NULL.
      * @return A FinalValueNode with the given value.
      * @internal
      */
     Node *registerFinalValue(int32_t value, UErrorCode &errorCode);
     /*
      * C++ note:
      * registerNode() and registerFinalValue() take ownership of their input nodes,
      * and only return owned nodes.
      * If they see a failure UErrorCode, they will delete the input node.
      * If they get a NULL pointer, they will record a U_MEMORY_ALLOCATION_ERROR.
      * If there is a failure, they return NULL.
      *
      * NULL Node pointers can be safely passed into other Nodes because
      * they call the static Node::hashCode() which checks for a NULL pointer first.
      *
      * Therefore, as long as builder functions register a new node,
      * they need to check for failures only before explicitly dereferencing
      * a Node pointer, or before setting a new UErrorCode.
      */
     // Hash set of nodes, maps from nodes to integer 1.
     /** @internal */
     UHashtable *nodes;
     /** @internal */
     class Node : public UObject {
     public:
         Node(int32_t initialHash) : hash(initialHash), offset(0) {}
         inline int32_t hashCode() const { return hash; }
         // Handles node==NULL.
         static inline int32_t hashCode(const Node *node) { return node==NULL ? 0 : node->hashCode(); }
         // Base class operator==() compares the actual class types.
         virtual UBool operator==(const Node &other) const;
         inline UBool operator!=(const Node &other) const { return !operator==(other); }
         /**
          * Traverses the Node graph and numbers branch edges, with rightmost edges first.
          * This is to avoid writing a duplicate node twice.
          *
          * Branch nodes in this trie data structure are not symmetric.
          * Most branch edges "jump" to other nodes but the rightmost branch edges
          * just continue without a jump.
          * Therefore, write() must write the rightmost branch edge last
          * (trie units are written backwards), and must write it at that point even if
          * it is a duplicate of a node previously written elsewhere.
          *
          * This function visits and marks right branch edges first.
          * Edges are numbered with increasingly negative values because we share the
          * offset field which gets positive values when nodes are written.
          * A branch edge also remembers the first number for any of its edges.
          *
          * When a further-left branch edge has a number in the range of the rightmost
          * edge's numbers, then it will be written as part of the required right edge
          * and we can avoid writing it first.
          *
          * After root.markRightEdgesFirst(-1) the offsets of all nodes are negative
          * edge numbers.
          *
          * @param edgeNumber The first edge number for this node and its sub-nodes.
          * @return An edge number that is at least the maximum-negative
          *         of the input edge number and the numbers of this node and all of its sub-nodes.
          */
         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
         // write() must set the offset to a positive value.
         virtual void write(StringTrieBuilder &builder) = 0;
         // See markRightEdgesFirst.
         inline void writeUnlessInsideRightEdge(int32_t firstRight, int32_t lastRight,
                                                StringTrieBuilder &builder) {
             // Note: Edge numbers are negative, lastRight<=firstRight.
             // If offset>0 then this node and its sub-nodes have been written already
             // and we need not write them again.
             // If this node is part of the unwritten right branch edge,
             // then we wait until that is written.
             if(offset<0 && (offset<lastRight || firstRight<offset)) {
                 write(builder);
             }
         }
         inline int32_t getOffset() const { return offset; }
     protected:
         int32_t hash;
         int32_t offset;
     };
     // This class should not be overridden because
     // registerFinalValue() compares a stack-allocated FinalValueNode
     // (stack-allocated so that we don't unnecessarily create lots of duplicate nodes)
     // with the input node, and the
     // !Node::operator==(other) used inside FinalValueNode::operator==(other)
     // will be false if the typeid's are different.
     /** @internal */
     class FinalValueNode : public Node {
     public:
         FinalValueNode(int32_t v) : Node(0x111111*37+v), value(v) {}
         virtual UBool operator==(const Node &other) const;
         virtual void write(StringTrieBuilder &builder);
     protected:
         int32_t value;
     };
     /**
      * @internal
      */
     class ValueNode : public Node {
     public:
         ValueNode(int32_t initialHash) : Node(initialHash), hasValue(FALSE), value(0) {}
         virtual UBool operator==(const Node &other) const;
         void setValue(int32_t v) {
             hasValue=TRUE;
             value=v;
             hash=hash*37+v;
         }
     protected:
         UBool hasValue;
         int32_t value;
     };
     /**
      * @internal
      */
     class IntermediateValueNode : public ValueNode {
     public:
         IntermediateValueNode(int32_t v, Node *nextNode)
                 : ValueNode(0x222222*37+hashCode(nextNode)), next(nextNode) { setValue(v); }
         virtual UBool operator==(const Node &other) const;
         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
         virtual void write(StringTrieBuilder &builder);
     protected:
         Node *next;
     };
     /**
      * @internal
      */
     class LinearMatchNode : public ValueNode {
     public:
         LinearMatchNode(int32_t len, Node *nextNode)
                 : ValueNode((0x333333*37+len)*37+hashCode(nextNode)),
                   length(len), next(nextNode) {}
         virtual UBool operator==(const Node &other) const;
         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
     protected:
         int32_t length;
         Node *next;
     };
     /**
      * @internal
      */
     class BranchNode : public Node {
     public:
         BranchNode(int32_t initialHash) : Node(initialHash) {}
     protected:
         int32_t firstEdgeNumber;
     };
     /**
      * @internal
      */
     class ListBranchNode : public BranchNode {
     public:
         ListBranchNode() : BranchNode(0x444444), length(0) {}
         virtual UBool operator==(const Node &other) const;
         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
         virtual void write(StringTrieBuilder &builder);
         // Adds a unit with a final value.
         void add(int32_t c, int32_t value) {
             units[length]=(UChar)c;
             equal[length]=NULL;
             values[length]=value;
             ++length;
             hash=(hash*37+c)*37+value;
         }
         // Adds a unit which leads to another match node.
         void add(int32_t c, Node *node) {
             units[length]=(UChar)c;
             equal[length]=node;
             values[length]=0;
             ++length;
             hash=(hash*37+c)*37+hashCode(node);
         }
     protected:
         Node *equal[kMaxBranchLinearSubNodeLength];  // NULL means "has final value".
         int32_t length;
         int32_t values[kMaxBranchLinearSubNodeLength];
         UChar units[kMaxBranchLinearSubNodeLength];
     };
     /**
      * @internal
      */
     class SplitBranchNode : public BranchNode {
     public:
         SplitBranchNode(UChar middleUnit, Node *lessThanNode, Node *greaterOrEqualNode)
                 : BranchNode(((0x555555*37+middleUnit)*37+
                               hashCode(lessThanNode))*37+hashCode(greaterOrEqualNode)),
                   unit(middleUnit), lessThan(lessThanNode), greaterOrEqual(greaterOrEqualNode) {}
         virtual UBool operator==(const Node &other) const;
         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
         virtual void write(StringTrieBuilder &builder);
     protected:
         UChar unit;
         Node *lessThan;
         Node *greaterOrEqual;
     };
     // Branch head node, for writing the actual node lead unit.
     /** @internal */
     class BranchHeadNode : public ValueNode {
     public:
         BranchHeadNode(int32_t len, Node *subNode)
                 : ValueNode((0x666666*37+len)*37+hashCode(subNode)),
                   length(len), next(subNode) {}
         virtual UBool operator==(const Node &other) const;
         virtual int32_t markRightEdgesFirst(int32_t edgeNumber);
         virtual void write(StringTrieBuilder &builder);
     protected:
         int32_t length;
         Node *next;  // A branch sub-node.
     };
 #endif  /* U_HIDE_INTERNAL_API */
     /** @internal */
     virtual Node *createLinearMatchNode(int32_t i, int32_t unitIndex, int32_t length,
                                         Node *nextNode) const = 0;
     /** @internal */
     virtual int32_t write(int32_t unit) = 0;
     /** @internal */
     virtual int32_t writeElementUnits(int32_t i, int32_t unitIndex, int32_t length) = 0;
     /** @internal */
     virtual int32_t writeValueAndFinal(int32_t i, UBool isFinal) = 0;
     /** @internal */
     virtual int32_t writeValueAndType(UBool hasValue, int32_t value, int32_t node) = 0;
     /** @internal */
     virtual int32_t writeDeltaTo(int32_t jumpTarget) = 0;
 };
 U_NAMESPACE_END
 #endif  // __STRINGTRIEBUILDER_H__

The Tor Browser / annotate

intl/icu/source/common/unicode/stringtriebuilder.h@6474c204b198 (annotated)

intl/icu/source/common/unicode/stringtriebuilder.h