icuSources/common/bmpset.h

   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