bmpset.h (5797B)
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) 2007, International Business Machines 7 * Corporation and others. All Rights Reserved. 8 * 9 ****************************************************************************** 10 * file name: bmpset.h 11 * encoding: UTF-8 12 * tab size: 8 (not used) 13 * indentation:4 14 * 15 * created on: 2007jan29 16 * created by: Markus W. Scherer 17 */ 18 19 #ifndef __BMPSET_H__ 20 #define __BMPSET_H__ 21 22 #include "unicode/utypes.h" 23 #include "unicode/uniset.h" 24 25 U_NAMESPACE_BEGIN 26 27 /* 28 * Helper class for frozen UnicodeSets, implements contains() and span() 29 * optimized for BMP code points. Structured to be UTF-8-friendly. 30 * 31 * Latin-1: Look up bytes. 32 * 2-byte characters: Bits organized vertically. 33 * 3-byte characters: Use zero/one/mixed data per 64-block in U+0000..U+FFFF, 34 * with mixed for illegal ranges. 35 * Supplementary characters: Binary search over 36 * the supplementary part of the parent set's inversion list. 37 */ 38 class BMPSet : public UMemory { 39 public: 40 BMPSet(const int32_t *parentList, int32_t parentListLength); 41 BMPSet(const BMPSet &otherBMPSet, const int32_t *newParentList, int32_t newParentListLength); 42 virtual ~BMPSet(); 43 44 virtual UBool contains(UChar32 c) const; 45 46 /* 47 * Span the initial substring for which each character c has spanCondition==contains(c). 48 * It must be s<limit and spanCondition==0 or 1. 49 * @return The string pointer which limits the span. 50 */ 51 const char16_t *span(const char16_t *s, const char16_t *limit, USetSpanCondition spanCondition) const; 52 53 /* 54 * Span the trailing substring for which each character c has spanCondition==contains(c). 55 * It must be s<limit and spanCondition==0 or 1. 56 * @return The string pointer which starts the span. 57 */ 58 const char16_t *spanBack(const char16_t *s, const char16_t *limit, USetSpanCondition spanCondition) const; 59 60 /* 61 * Span the initial substring for which each character c has spanCondition==contains(c). 62 * It must be length>0 and spanCondition==0 or 1. 63 * @return The string pointer which limits the span. 64 */ 65 const uint8_t *spanUTF8(const uint8_t *s, int32_t length, USetSpanCondition spanCondition) const; 66 67 /* 68 * Span the trailing substring for which each character c has spanCondition==contains(c). 69 * It must be length>0 and spanCondition==0 or 1. 70 * @return The start of the span. 71 */ 72 int32_t spanBackUTF8(const uint8_t *s, int32_t length, USetSpanCondition spanCondition) const; 73 74 private: 75 void initBits(); 76 void overrideIllegal(); 77 78 /** 79 * Same as UnicodeSet::findCodePoint(UChar32 c) const except that the 80 * binary search is restricted for finding code points in a certain range. 81 * 82 * For restricting the search for finding in the range start..end, 83 * pass in 84 * lo=findCodePoint(start) and 85 * hi=findCodePoint(end) 86 * with 0<=lo<=hi<len. 87 * findCodePoint(c) defaults to lo=0 and hi=len-1. 88 * 89 * @param c a character in a subrange of MIN_VALUE..MAX_VALUE 90 * @param lo The lowest index to be returned. 91 * @param hi The highest index to be returned. 92 * @return the smallest integer i in the range lo..hi, 93 * inclusive, such that c < list[i] 94 */ 95 int32_t findCodePoint(UChar32 c, int32_t lo, int32_t hi) const; 96 97 inline UBool containsSlow(UChar32 c, int32_t lo, int32_t hi) const; 98 99 /* 100 * One byte 0 or 1 per Latin-1 character. 101 */ 102 UBool latin1Contains[0x100]; 103 104 /* true if contains(U+FFFD). */ 105 UBool containsFFFD; 106 107 /* 108 * One bit per code point from U+0000..U+07FF. 109 * The bits are organized vertically; consecutive code points 110 * correspond to the same bit positions in consecutive table words. 111 * With code point parts 112 * lead=c{10..6} 113 * trail=c{5..0} 114 * it is set.contains(c)==(table7FF[trail] bit lead) 115 * 116 * Bits for 0..7F (non-shortest forms) are set to the result of contains(FFFD) 117 * for faster validity checking at runtime. 118 */ 119 uint32_t table7FF[64]; 120 121 /* 122 * One bit per 64 BMP code points. 123 * The bits are organized vertically; consecutive 64-code point blocks 124 * correspond to the same bit position in consecutive table words. 125 * With code point parts 126 * lead=c{15..12} 127 * t1=c{11..6} 128 * test bits (lead+16) and lead in bmpBlockBits[t1]. 129 * If the upper bit is 0, then the lower bit indicates if contains(c) 130 * for all code points in the 64-block. 131 * If the upper bit is 1, then the block is mixed and set.contains(c) 132 * must be called. 133 * 134 * Bits for 0..7FF (non-shortest forms) and D800..DFFF are set to 135 * the result of contains(FFFD) for faster validity checking at runtime. 136 */ 137 uint32_t bmpBlockBits[64]; 138 139 /* 140 * Inversion list indexes for restricted binary searches in 141 * findCodePoint(), from 142 * findCodePoint(U+0800, U+1000, U+2000, .., U+F000, U+10000). 143 * U+0800 is the first 3-byte-UTF-8 code point. Code points below U+0800 are 144 * always looked up in the bit tables. 145 * The last pair of indexes is for finding supplementary code points. 146 */ 147 int32_t list4kStarts[18]; 148 149 /* 150 * The inversion list of the parent set, for the slower contains() implementation 151 * for mixed BMP blocks and for supplementary code points. 152 * The list is terminated with list[listLength-1]=0x110000. 153 */ 154 const int32_t *list; 155 int32_t listLength; 156 }; 157 158 inline UBool BMPSet::containsSlow(UChar32 c, int32_t lo, int32_t hi) const { 159 return findCodePoint(c, lo, hi) & 1; 160 } 161 162 U_NAMESPACE_END 163 164 #endif