stringtriebuilder.h
Go to the documentation of this file.
// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
*******************************************************************************
* Copyright (C) 2010-2012,2014, International Business Machines
* Corporation and others. All Rights Reserved.
*******************************************************************************
* file name: stringtriebuilder.h
* encoding: UTF-8
* 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"
#if U_SHOW_CPLUSPLUS_API
#include "unicode/uobject.h"
// Forward declaration.
struct UHashtable;
typedef struct UHashtable UHashtable;
enum UStringTrieBuildOption {
USTRINGTRIE_BUILD_FAST,
USTRINGTRIE_BUILD_SMALL
};
U_NAMESPACE_BEGIN
class U_COMMON_API StringTrieBuilder : public UObject {
public:
#ifndef U_HIDE_INTERNAL_API
static int32_t hashNode(const void *node);
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.
StringTrieBuilder();
virtual ~StringTrieBuilder();
#ifndef U_HIDE_INTERNAL_API
void createCompactBuilder(int32_t sizeGuess, UErrorCode &errorCode);
void deleteCompactBuilder();
void build(UStringTrieBuildOption buildOption, int32_t elementsLength, UErrorCode &errorCode);
int32_t writeNode(int32_t start, int32_t limit, int32_t unitIndex);
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
Node *makeNode(int32_t start, int32_t limit, int32_t unitIndex, UErrorCode &errorCode);
Node *makeBranchSubNode(int32_t start, int32_t limit, int32_t unitIndex,
int32_t length, UErrorCode &errorCode);
#endif /* U_HIDE_INTERNAL_API */
virtual int32_t getElementStringLength(int32_t i) const = 0;
virtual char16_t getElementUnit(int32_t i, int32_t unitIndex) const = 0;
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.
virtual int32_t getLimitOfLinearMatch(int32_t first, int32_t last, int32_t unitIndex) const = 0;
// Number of different units at unitIndex.
virtual int32_t countElementUnits(int32_t start, int32_t limit, int32_t unitIndex) const = 0;
virtual int32_t skipElementsBySomeUnits(int32_t i, int32_t unitIndex, int32_t count) const = 0;
virtual int32_t indexOfElementWithNextUnit(int32_t i, int32_t unitIndex, char16_t unit) const = 0;
virtual UBool matchNodesCanHaveValues() const = 0;
virtual int32_t getMaxBranchLinearSubNodeLength() const = 0;
virtual int32_t getMinLinearMatch() const = 0;
virtual int32_t getMaxLinearMatchLength() const = 0;
#ifndef U_HIDE_INTERNAL_API
// max(BytesTrie::kMaxBranchLinearSubNodeLength, UCharsTrie::kMaxBranchLinearSubNodeLength).
static const int32_t kMaxBranchLinearSubNodeLength=5;
// Maximum number of nested split-branch levels for a branch on all 2^16 possible char16_t units.
// log2(2^16/kMaxBranchLinearSubNodeLength) rounded up.
static const int32_t kMaxSplitBranchLevels=14;
Node *registerNode(Node *newNode, UErrorCode &errorCode);
Node *registerFinalValue(int32_t value, UErrorCode &errorCode);
#endif /* U_HIDE_INTERNAL_API */
/*
* 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 nullptr pointer, they will record a U_MEMORY_ALLOCATION_ERROR.
* If there is a failure, they return nullptr.
*
* nullptr Node pointers can be safely passed into other Nodes because
* they call the static Node::hashCode() which checks for a nullptr 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.
UHashtable *nodes;
// Do not conditionalize the following with #ifndef U_HIDE_INTERNAL_API,
// it is needed for layout of other objects.
class Node : public UObject {
public:
Node(int32_t initialHash) : hash(initialHash), offset(0) {}
inline int32_t hashCode() const { return hash; }
// Handles node==nullptr.
static inline int32_t hashCode(const Node *node) { return node==nullptr ? 0 : node->hashCode(); }
// Base class operator==() compares the actual class types.
virtual bool operator==(const Node &other) const;
inline bool operator!=(const Node &other) const { return !operator==(other); }
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;
};
#ifndef U_HIDE_INTERNAL_API
// 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.
class FinalValueNode : public Node {
public:
FinalValueNode(int32_t v) : Node(0x111111u*37u+v), value(v) {}
virtual bool operator==(const Node &other) const override;
virtual void write(StringTrieBuilder &builder) override;
protected:
int32_t value;
};
#endif /* U_HIDE_INTERNAL_API */
// Do not conditionalize the following with #ifndef U_HIDE_INTERNAL_API,
// it is needed for layout of other objects.
class ValueNode : public Node {
public:
ValueNode(int32_t initialHash) : Node(initialHash), hasValue(false), value(0) {}
virtual bool operator==(const Node &other) const override;
void setValue(int32_t v) {
hasValue=true;
value=v;
hash=hash*37u+v;
}
protected:
UBool hasValue;
int32_t value;
};
#ifndef U_HIDE_INTERNAL_API
class IntermediateValueNode : public ValueNode {
public:
IntermediateValueNode(int32_t v, Node *nextNode)
: ValueNode(0x222222u*37u+hashCode(nextNode)), next(nextNode) { setValue(v); }
virtual bool operator==(const Node &other) const override;
virtual int32_t markRightEdgesFirst(int32_t edgeNumber) override;
virtual void write(StringTrieBuilder &builder) override;
protected:
Node *next;
};
#endif /* U_HIDE_INTERNAL_API */
// Do not conditionalize the following with #ifndef U_HIDE_INTERNAL_API,
// it is needed for layout of other objects.
class LinearMatchNode : public ValueNode {
public:
LinearMatchNode(int32_t len, Node *nextNode)
: ValueNode((0x333333u*37u+len)*37u+hashCode(nextNode)),
length(len), next(nextNode) {}
virtual bool operator==(const Node &other) const override;
virtual int32_t markRightEdgesFirst(int32_t edgeNumber) override;
protected:
int32_t length;
Node *next;
};
#ifndef U_HIDE_INTERNAL_API
class BranchNode : public Node {
public:
BranchNode(int32_t initialHash) : Node(initialHash) {}
protected:
int32_t firstEdgeNumber;
};
class ListBranchNode : public BranchNode {
public:
ListBranchNode() : BranchNode(0x444444), length(0) {}
virtual bool operator==(const Node &other) const override;
virtual int32_t markRightEdgesFirst(int32_t edgeNumber) override;
virtual void write(StringTrieBuilder &builder) override;
// Adds a unit with a final value.
void add(int32_t c, int32_t value) {
units[length] = static_cast<char16_t>(c);
equal[length]=nullptr;
values[length]=value;
++length;
hash=(hash*37u+c)*37u+value;
}
// Adds a unit which leads to another match node.
void add(int32_t c, Node *node) {
units[length] = static_cast<char16_t>(c);
equal[length]=node;
values[length]=0;
++length;
hash=(hash*37u+c)*37u+hashCode(node);
}
protected:
Node *equal[kMaxBranchLinearSubNodeLength]; // nullptr means "has final value".
int32_t length;
int32_t values[kMaxBranchLinearSubNodeLength];
char16_t units[kMaxBranchLinearSubNodeLength];
};
class SplitBranchNode : public BranchNode {
public:
SplitBranchNode(char16_t middleUnit, Node *lessThanNode, Node *greaterOrEqualNode)
: BranchNode(((0x555555u*37u+middleUnit)*37u+
hashCode(lessThanNode))*37u+hashCode(greaterOrEqualNode)),
unit(middleUnit), lessThan(lessThanNode), greaterOrEqual(greaterOrEqualNode) {}
virtual bool operator==(const Node &other) const override;
virtual int32_t markRightEdgesFirst(int32_t edgeNumber) override;
virtual void write(StringTrieBuilder &builder) override;
protected:
char16_t unit;
Node *lessThan;
Node *greaterOrEqual;
};
// Branch head node, for writing the actual node lead unit.
class BranchHeadNode : public ValueNode {
public:
BranchHeadNode(int32_t len, Node *subNode)
: ValueNode((0x666666u*37u+len)*37u+hashCode(subNode)),
length(len), next(subNode) {}
virtual bool operator==(const Node &other) const override;
virtual int32_t markRightEdgesFirst(int32_t edgeNumber) override;
virtual void write(StringTrieBuilder &builder) override;
protected:
int32_t length;
Node *next; // A branch sub-node.
};
#endif /* U_HIDE_INTERNAL_API */
virtual Node *createLinearMatchNode(int32_t i, int32_t unitIndex, int32_t length,
Node *nextNode) const = 0;
virtual int32_t write(int32_t unit) = 0;
virtual int32_t writeElementUnits(int32_t i, int32_t unitIndex, int32_t length) = 0;
virtual int32_t writeValueAndFinal(int32_t i, UBool isFinal) = 0;
virtual int32_t writeValueAndType(UBool hasValue, int32_t value, int32_t node) = 0;
virtual int32_t writeDeltaTo(int32_t jumpTarget) = 0;
};
U_NAMESPACE_END
#endif /* U_SHOW_CPLUSPLUS_API */
#endif // __STRINGTRIEBUILDER_H__
UHashtable
struct UHashtable UHashtable
Definition msgfmt.h:43
icu::operator==
U_EXPORT UBool operator==(const StringPiece &x, const StringPiece &y)
Global operator == for StringPiece.
icu::operator!=
bool operator!=(const StringPiece &x, const StringPiece &y)
Global operator != for StringPiece.
Definition stringpiece.h:346
UStringTrieBuildOption
UStringTrieBuildOption
Build options for BytesTrieBuilder and CharsTrieBuilder.
Definition stringtriebuilder.h:41
USTRINGTRIE_BUILD_SMALL
@ USTRINGTRIE_BUILD_SMALL
Builds a trie more slowly, attempting to generate a shorter but equivalent serialization.
Definition stringtriebuilder.h:57
USTRINGTRIE_BUILD_FAST
@ USTRINGTRIE_BUILD_FAST
Builds a trie quickly.
Definition stringtriebuilder.h:46
UBool
int8_t UBool
The ICU boolean type, a signed-byte integer.
Definition umachine.h:247
uobject.h
C++ API: Common ICU base class UObject.
utypes.h
Basic definitions for ICU, for both C and C++ APIs.
UErrorCode
UErrorCode
Standard ICU4C error code type, a substitute for exceptions.
Definition utypes.h:430
U_COMMON_API
#define U_COMMON_API
Set to export library symbols from inside the common library, and to import them from outside.
Definition utypes.h:315