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