The Tor Browser / annotate

intl/icu/source/common/utrie2_impl.h@fc2d59ddac77 (annotated)

intl/icu/source/common/utrie2_impl.h

Wed, 31 Dec 2014 07:22:50 +0100

author
Michael Schloh von Bennewitz <michael@schloh.com>
date
Wed, 31 Dec 2014 07:22:50 +0100
branch
TOR_BUG_3246
changeset 4
fc2d59ddac77
permissions
-rw-r--r--

Correct previous dual key logic pending first delivery installment.

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

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial