Check in the pristine copy of ICU 4.6...

icu46/source/common/utrie2_impl.h

+/*
+******************************************************************************
+*
+*   Copyright (C) 2001-2008, International Business Machines
+*   Corporation and others.  All Rights Reserved.
+*
+******************************************************************************
+*   file name:  utrie2_impl.h
+*   encoding:   US-ASCII
+*   tab size:   8 (not used)
+*   indentation:4
+*
+*   created on: 2008sep26 (split off from utrie2.c)
+*   created by: Markus W. Scherer
+*
+*   Definitions needed for both runtime and builder code for UTrie2,
+*   used by utrie2.c and utrie2_builder.c.
+*/
+
+#ifndef __UTRIE2_IMPL_H__
+#define __UTRIE2_IMPL_H__
+
+#include "utrie2.h"
+
+/* Public UTrie2 API implementation ----------------------------------------- */
+
+/*
+ * These definitions are mostly needed by utrie2.c,
+ * but also by utrie2_serialize() and utrie2_swap().
+ */
+
+/*
+ * UTrie and UTrie2 signature values,
+ * in platform endianness and opposite endianness.
+ */
+#define UTRIE_SIG       0x54726965
+#define UTRIE_OE_SIG    0x65697254
+
+#define UTRIE2_SIG      0x54726932
+#define UTRIE2_OE_SIG   0x32697254
+
+/**
+ * Trie data structure in serialized form:
+ *
+ * UTrie2Header header;
+ * uint16_t index[header.index2Length];
+ * uint16_t data[header.shiftedDataLength<<2];  -- or uint32_t data[...]
+ * @internal
+ */
+typedef struct UTrie2Header {
+    /** "Tri2" in big-endian US-ASCII (0x54726932) */
+    uint32_t signature;
+
+    /**
+     * options bit field:
+     * 15.. 4   reserved (0)
+     *  3.. 0   UTrie2ValueBits valueBits
+     */
+    uint16_t options;
+
+    /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH */
+    uint16_t indexLength;
+
+    /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT */
+    uint16_t shiftedDataLength;
+
+    /** Null index and data blocks, not shifted. */
+    uint16_t index2NullOffset, dataNullOffset;
+
+    /**
+     * First code point of the single-value range ending with U+10ffff,
+     * rounded up and then shifted right by UTRIE2_SHIFT_1.
+     */
+    uint16_t shiftedHighStart;
+} UTrie2Header;
+
+/**
+ * Constants for use with UTrie2Header.options.
+ * @internal
+ */
+enum {
+    /** Mask to get the UTrie2ValueBits valueBits from options. */
+    UTRIE2_OPTIONS_VALUE_BITS_MASK=0xf
+};
+
+/* Building a trie ---------------------------------------------------------- */
+
+/*
+ * These definitions are mostly needed by utrie2_builder.c, but also by
+ * utrie2_get32() and utrie2_enum().
+ */
+
+enum {
+    /**
+     * At build time, leave a gap in the index-2 table,
+     * at least as long as the maximum lengths of the 2-byte UTF-8 index-2 table
+     * and the supplementary index-1 table.
+     * Round up to UTRIE2_INDEX_2_BLOCK_LENGTH for proper compacting.
+     */
+    UNEWTRIE2_INDEX_GAP_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH,
+    UNEWTRIE2_INDEX_GAP_LENGTH=
+        ((UTRIE2_UTF8_2B_INDEX_2_LENGTH+UTRIE2_MAX_INDEX_1_LENGTH)+UTRIE2_INDEX_2_MASK)&
+        ~UTRIE2_INDEX_2_MASK,
+
+    /**
+     * Maximum length of the build-time index-2 array.
+     * Maximum number of Unicode code points (0x110000) shifted right by UTRIE2_SHIFT_2,
+     * plus the part of the index-2 table for lead surrogate code points,
+     * plus the build-time index gap,
+     * plus the null index-2 block.
+     */
+    UNEWTRIE2_MAX_INDEX_2_LENGTH=
+        (0x110000>>UTRIE2_SHIFT_2)+
+        UTRIE2_LSCP_INDEX_2_LENGTH+
+        UNEWTRIE2_INDEX_GAP_LENGTH+
+        UTRIE2_INDEX_2_BLOCK_LENGTH,
+
+    UNEWTRIE2_INDEX_1_LENGTH=0x110000>>UTRIE2_SHIFT_1
+};
+
+/**
+ * Maximum length of the build-time data array.
+ * One entry per 0x110000 code points, plus the illegal-UTF-8 block and the null block,
+ * plus values for the 0x400 surrogate code units.
+ */
+#define UNEWTRIE2_MAX_DATA_LENGTH (0x110000+0x40+0x40+0x400)
+
+/*
+ * Build-time trie structure.
+ *
+ * Just using a boolean flag for "repeat use" could lead to data array overflow
+ * because we would not be able to detect when a data block becomes unused.
+ * It also leads to orphan data blocks that are kept through serialization.
+ *
+ * Need to use reference counting for data blocks,
+ * and allocDataBlock() needs to look for a free block before increasing dataLength.
+ *
+ * This scheme seems like overkill for index-2 blocks since the whole index array is
+ * preallocated anyway (unlike the growable data array).
+ * Just allocating multiple index-2 blocks as needed.
+ */
+struct UNewTrie2 {
+    int32_t index1[UNEWTRIE2_INDEX_1_LENGTH];
+    int32_t index2[UNEWTRIE2_MAX_INDEX_2_LENGTH];
+    uint32_t *data;
+
+    uint32_t initialValue, errorValue;
+    int32_t index2Length, dataCapacity, dataLength;
+    int32_t firstFreeBlock;
+    int32_t index2NullOffset, dataNullOffset;
+    UChar32 highStart;
+    UBool isCompacted;
+
+    /**
+     * Multi-purpose per-data-block table.
+     *
+     * Before compacting:
+     *
+     * Per-data-block reference counters/free-block list.
+     *  0: unused
+     * >0: reference counter (number of index-2 entries pointing here)
+     * <0: next free data block in free-block list
+     *
+     * While compacting:
+     *
+     * Map of adjusted indexes, used in compactData() and compactIndex2().
+     * Maps from original indexes to new ones.
+     */
+    int32_t map[UNEWTRIE2_MAX_DATA_LENGTH>>UTRIE2_SHIFT_2];
+};
+
+#endif