icuSources/common/utrie2_impl.h

   1 // © 2016 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html
   3 /*
   4 ******************************************************************************
   5 *
   6 *   Copyright (C) 2001-2008, International Business Machines
   7 *   Corporation and others.  All Rights Reserved.
   8 *
   9 ******************************************************************************
  10 *   file name:  utrie2_impl.h
  11 *   encoding:   UTF-8
  12 *   tab size:   8 (not used)
  13 *   indentation:4
  14 *
  15 *   created on: 2008sep26 (split off from utrie2.c)
  16 *   created by: Markus W. Scherer
  17 *
  18 *   Definitions needed for both runtime and builder code for UTrie2,
  19 *   used by utrie2.c and utrie2_builder.c.
  20 */
  21
  22 #ifndef __UTRIE2_IMPL_H__
  23 #define __UTRIE2_IMPL_H__
  24
  25 #ifdef UCPTRIE_DEBUG
  26 #include "unicode/umutablecptrie.h"
  27 #endif
  28 #include "utrie2.h"
  29
  30 /* Public UTrie2 API implementation ----------------------------------------- */
  31
  32 /*
  33  * These definitions are mostly needed by utrie2.cpp,
  34  * but also by utrie2_serialize() and utrie2_swap().
  35  */
  36
  37 // UTrie2 signature values, in platform endianness and opposite endianness.
  38 // The UTrie2 signature ASCII byte values spell "Tri2".
  39 #define UTRIE2_SIG      0x54726932
  40 #define UTRIE2_OE_SIG   0x32697254
  41
  42 /**
  43  * Trie data structure in serialized form:
  44  *
  45  * UTrie2Header header;
  46  * uint16_t index[header.index2Length];
  47  * uint16_t data[header.shiftedDataLength<<2];  -- or uint32_t data[...]
  48  * @internal
  49  */
  50 typedef struct UTrie2Header {
  51     /** "Tri2" in big-endian US-ASCII (0x54726932) */
  52     uint32_t signature;
  53
  54     /**
  55      * options bit field:
  56      * 15.. 4   reserved (0)
  57      *  3.. 0   UTrie2ValueBits valueBits
  58      */
  59     uint16_t options;
  60
  61     /** UTRIE2_INDEX_1_OFFSET..UTRIE2_MAX_INDEX_LENGTH */
  62     uint16_t indexLength;
  63
  64     /** (UTRIE2_DATA_START_OFFSET..UTRIE2_MAX_DATA_LENGTH)>>UTRIE2_INDEX_SHIFT */
  65     uint16_t shiftedDataLength;
  66
  67     /** Null index and data blocks, not shifted. */
  68     uint16_t index2NullOffset, dataNullOffset;
  69
  70     /**
  71      * First code point of the single-value range ending with U+10ffff,
  72      * rounded up and then shifted right by UTRIE2_SHIFT_1.
  73      */
  74     uint16_t shiftedHighStart;
  75 } UTrie2Header;
  76
  77 /**
  78  * Constants for use with UTrie2Header.options.
  79  * @internal
  80  */
  81 enum {
  82     /** Mask to get the UTrie2ValueBits valueBits from options. */
  83     UTRIE2_OPTIONS_VALUE_BITS_MASK=0xf
  84 };
  85
  86 /* Building a trie ---------------------------------------------------------- */
  87
  88 /*
  89  * These definitions are mostly needed by utrie2_builder.c, but also by
  90  * utrie2_get32() and utrie2_enum().
  91  */
  92
  93 enum {
  94     /**
  95      * At build time, leave a gap in the index-2 table,
  96      * at least as long as the maximum lengths of the 2-byte UTF-8 index-2 table
  97      * and the supplementary index-1 table.
  98      * Round up to UTRIE2_INDEX_2_BLOCK_LENGTH for proper compacting.
  99      */
 100     UNEWTRIE2_INDEX_GAP_OFFSET=UTRIE2_INDEX_2_BMP_LENGTH,
 101     UNEWTRIE2_INDEX_GAP_LENGTH=
 102         ((UTRIE2_UTF8_2B_INDEX_2_LENGTH+UTRIE2_MAX_INDEX_1_LENGTH)+UTRIE2_INDEX_2_MASK)&
 103         ~UTRIE2_INDEX_2_MASK,
 104
 105     /**
 106      * Maximum length of the build-time index-2 array.
 107      * Maximum number of Unicode code points (0x110000) shifted right by UTRIE2_SHIFT_2,
 108      * plus the part of the index-2 table for lead surrogate code points,
 109      * plus the build-time index gap,
 110      * plus the null index-2 block.
 111      */
 112     UNEWTRIE2_MAX_INDEX_2_LENGTH=
 113         (0x110000>>UTRIE2_SHIFT_2)+
 114         UTRIE2_LSCP_INDEX_2_LENGTH+
 115         UNEWTRIE2_INDEX_GAP_LENGTH+
 116         UTRIE2_INDEX_2_BLOCK_LENGTH,
 117
 118     UNEWTRIE2_INDEX_1_LENGTH=0x110000>>UTRIE2_SHIFT_1
 119 };
 120
 121 /**
 122  * Maximum length of the build-time data array.
 123  * One entry per 0x110000 code points, plus the illegal-UTF-8 block and the null block,
 124  * plus values for the 0x400 surrogate code units.
 125  */
 126 #define UNEWTRIE2_MAX_DATA_LENGTH (0x110000+0x40+0x40+0x400)
 127
 128 /*
 129  * Build-time trie structure.
 130  *
 131  * Just using a boolean flag for "repeat use" could lead to data array overflow
 132  * because we would not be able to detect when a data block becomes unused.
 133  * It also leads to orphan data blocks that are kept through serialization.
 134  *
 135  * Need to use reference counting for data blocks,
 136  * and allocDataBlock() needs to look for a free block before increasing dataLength.
 137  *
 138  * This scheme seems like overkill for index-2 blocks since the whole index array is
 139  * preallocated anyway (unlike the growable data array).
 140  * Just allocating multiple index-2 blocks as needed.
 141  */
 142 struct UNewTrie2 {
 143     int32_t index1[UNEWTRIE2_INDEX_1_LENGTH];
 144     int32_t index2[UNEWTRIE2_MAX_INDEX_2_LENGTH];
 145     uint32_t *data;
 146 #ifdef UCPTRIE_DEBUG
 147     UMutableCPTrie *t3;
 148 #endif
 149
 150     uint32_t initialValue, errorValue;
 151     int32_t index2Length, dataCapacity, dataLength;
 152     int32_t firstFreeBlock;
 153     int32_t index2NullOffset, dataNullOffset;
 154     UChar32 highStart;
 155     UBool isCompacted;
 156
 157     /**
 158      * Multi-purpose per-data-block table.
 159      *
 160      * Before compacting:
 161      *
 162      * Per-data-block reference counters/free-block list.
 163      *  0: unused
 164      * >0: reference counter (number of index-2 entries pointing here)
 165      * <0: next free data block in free-block list
 166      *
 167      * While compacting:
 168      *
 169      * Map of adjusted indexes, used in compactData() and compactIndex2().
 170      * Maps from original indexes to new ones.
 171      */
 172     int32_t map[UNEWTRIE2_MAX_DATA_LENGTH>>UTRIE2_SHIFT_2];
 173 };
 174
 175 #endif