String.subproj/CFCharacterSet.c

   1 /*
   2  * Copyright (c) 2003 Apple Computer, Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
   7  *
   8  * This file contains Original Code and/or Modifications of Original Code
   9  * as defined in and that are subject to the Apple Public Source License
  10  * Version 2.0 (the 'License'). You may not use this file except in
  11  * compliance with the License. Please obtain a copy of the License at
  12  * http://www.opensource.apple.com/apsl/ and read it before using this
  13  * file.
  14  *
  15  * The Original Code and all software distributed under the License are
  16  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  17  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  18  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  20  * Please see the License for the specific language governing rights and
  21  * limitations under the License.
  22  *
  23  * @APPLE_LICENSE_HEADER_END@
  24  */
  25 /*      CFCharacterSet.c
  26         Copyright 1999-2002, Apple, Inc. All rights reserved.
  27         Responsibility: Aki Inoue
  28 */
  29
  30 #include <CoreFoundation/CFCharacterSet.h>
  31 #include <CoreFoundation/CFByteOrder.h>
  32 #include "CFCharacterSetPriv.h"
  33 #include <CoreFoundation/CFData.h>
  34 #include <CoreFoundation/CFString.h>
  35 #include "CFInternal.h"
  36 #include "CFUniChar.h"
  37 #include "CFUniCharPriv.h"
  38 #include <stdlib.h>
  39 #include <string.h>
  40
  41 #if !defined(__MACOS8__)
  42 #define __MACOS8__ 0
  43 #endif
  44
  45 #define BITSPERBYTE     8       /* (CHAR_BIT * sizeof(unsigned char)) */
  46 #define LOG_BPB         3
  47 #define LOG_BPLW        5
  48 #define NUMCHARACTERS   65536
  49
  50 #define MAX_ANNEX_PLANE (16)
  51
  52 /* Number of things in the array keeping the bits.
  53 */
  54 #define __kCFBitmapSize         (NUMCHARACTERS / BITSPERBYTE)
  55
  56 /* How many elements max can be in an __kCFCharSetClassString CFCharacterSet
  57 */
  58 #define __kCFStringCharSetMax 64
  59
  60 /* The last builtin set ID number
  61 */
  62 #define __kCFLastBuiltinSetID kCFCharacterSetSymbol
  63
  64 /* How many elements in the "singles" array before we use binary search.
  65 */
  66 #define __kCFSetBreakeven 10
  67
  68 /* This tells us, within 1k or so, whether a thing is POTENTIALLY in the set (in the bitmap blob of the private structure) before we bother to do specific checking.
  69 */
  70 #define __CFCSetBitsInRange(n, i)       (i[n>>15] & (1L << ((n>>10) % 32)))
  71
  72 /* Compact bitmap params
  73 */
  74 #define __kCFCompactBitmapNumPages (256)
  75
  76 #define __kCFCompactBitmapMaxPages (128) // the max pages allocated
  77
  78 #define __kCFCompactBitmapPageSize (__kCFBitmapSize / __kCFCompactBitmapNumPages)
  79
  80 typedef struct {
  81     CFCharacterSetRef *_nonBMPPlanes;
  82     unsigned int _validEntriesBitmap;
  83     unsigned char _numOfAllocEntries;
  84     unsigned char _isAnnexInverted;
  85     unsigned short _padding;
  86 } CFCharSetAnnexStruct;
  87
  88 struct __CFCharacterSet {
  89     CFRuntimeBase _base;
  90     CFHashCode _hashValue;
  91     union {
  92         struct {
  93             CFIndex _type;
  94         } _builtin;
  95         struct {
  96             UInt32 _firstChar;
  97             CFIndex _length;
  98         } _range;
  99         struct {
 100             UniChar *_buffer;
 101             CFIndex _length;
 102         } _string;
 103         struct {
 104             uint8_t *_bits;
 105         } _bitmap;
 106         struct {
 107             uint8_t *_cBits;
 108         } _compactBitmap;
 109    } _variants;
 110    CFCharSetAnnexStruct *_annex;
 111 };
 112
 113 /* _base._info values interesting for CFCharacterSet
 114 */
 115 enum {
 116     __kCFCharSetClassTypeMask = 0x0070,
 117       __kCFCharSetClassBuiltin = 0x0000,
 118       __kCFCharSetClassRange = 0x0010,
 119       __kCFCharSetClassString = 0x0020,
 120       __kCFCharSetClassBitmap = 0x0030,
 121       __kCFCharSetClassSet = 0x0040,
 122       __kCFCharSetClassCompactBitmap = 0x0040,
 123
 124     __kCFCharSetIsInvertedMask = 0x0008,
 125       __kCFCharSetIsInverted = 0x0008,
 126
 127     __kCFCharSetHasHashValueMask = 0x00004,
 128       __kCFCharSetHasHashValue = 0x0004,
 129
 130     /* Generic CFBase values */
 131     __kCFCharSetIsMutableMask = 0x0001,
 132       __kCFCharSetIsMutable = 0x0001,
 133 };
 134
 135 /* Inline accessor macros for _base._info
 136 */
 137 CF_INLINE Boolean __CFCSetIsMutable(CFCharacterSetRef cset) {return (cset->_base._info & __kCFCharSetIsMutableMask) == __kCFCharSetIsMutable;}
 138 CF_INLINE Boolean __CFCSetIsBuiltin(CFCharacterSetRef cset) {return (cset->_base._info & __kCFCharSetClassTypeMask) == __kCFCharSetClassBuiltin;}
 139 CF_INLINE Boolean __CFCSetIsRange(CFCharacterSetRef cset) {return (cset->_base._info & __kCFCharSetClassTypeMask) == __kCFCharSetClassRange;}
 140 CF_INLINE Boolean __CFCSetIsString(CFCharacterSetRef cset) {return (cset->_base._info & __kCFCharSetClassTypeMask) == __kCFCharSetClassString;}
 141 CF_INLINE Boolean __CFCSetIsBitmap(CFCharacterSetRef cset) {return (cset->_base._info & __kCFCharSetClassTypeMask) == __kCFCharSetClassBitmap;}
 142 CF_INLINE Boolean __CFCSetIsCompactBitmap(CFCharacterSetRef cset) {return (cset->_base._info & __kCFCharSetClassTypeMask) == __kCFCharSetClassCompactBitmap;}
 143 CF_INLINE Boolean __CFCSetIsInverted(CFCharacterSetRef cset) {return (cset->_base._info & __kCFCharSetIsInvertedMask) == __kCFCharSetIsInverted;}
 144 CF_INLINE Boolean __CFCSetHasHashValue(CFCharacterSetRef cset) {return (cset->_base._info & __kCFCharSetHasHashValueMask) == __kCFCharSetHasHashValue;}
 145 CF_INLINE UInt32 __CFCSetClassType(CFCharacterSetRef cset) {return (cset->_base._info & __kCFCharSetClassTypeMask);}
 146
 147 CF_INLINE void __CFCSetPutIsMutable(CFMutableCharacterSetRef cset, Boolean isMutable) {(isMutable ? (cset->_base._info |= __kCFCharSetIsMutable) : (cset->_base._info &= ~ __kCFCharSetIsMutable));}
 148 CF_INLINE void __CFCSetPutIsInverted(CFMutableCharacterSetRef cset, Boolean isInverted) {(isInverted ? (cset->_base._info |= __kCFCharSetIsInverted) : (cset->_base._info &= ~__kCFCharSetIsInverted));}
 149 CF_INLINE void __CFCSetPutHasHashValue(CFMutableCharacterSetRef cset, Boolean hasHash) {(hasHash ? (cset->_base._info |= __kCFCharSetHasHashValue) : (cset->_base._info &= ~__kCFCharSetHasHashValue));}
 150 CF_INLINE void __CFCSetPutClassType(CFMutableCharacterSetRef cset, UInt32 classType) {cset->_base._info &= ~__kCFCharSetClassTypeMask;  cset->_base._info |= classType;}
 151
 152
 153 /* Inline contents accessor macros
 154 */
 155 CF_INLINE CFCharacterSetPredefinedSet __CFCSetBuiltinType(CFCharacterSetRef cset) {return cset->_variants._builtin._type;}
 156 CF_INLINE UInt32 __CFCSetRangeFirstChar(CFCharacterSetRef cset) {return cset->_variants._range._firstChar;}
 157 CF_INLINE CFIndex __CFCSetRangeLength(CFCharacterSetRef cset) {return cset->_variants._range._length;}
 158 CF_INLINE UniChar *__CFCSetStringBuffer(CFCharacterSetRef cset) {return (UniChar*)(cset->_variants._string._buffer);}
 159 CF_INLINE CFIndex __CFCSetStringLength(CFCharacterSetRef cset) {return cset->_variants._string._length;}
 160 CF_INLINE uint8_t *__CFCSetBitmapBits(CFCharacterSetRef cset) {return cset->_variants._bitmap._bits;}
 161 CF_INLINE uint8_t *__CFCSetCompactBitmapBits(CFCharacterSetRef cset) {return cset->_variants._compactBitmap._cBits;}
 162
 163 CF_INLINE void __CFCSetPutBuiltinType(CFMutableCharacterSetRef cset, CFCharacterSetPredefinedSet type) {cset->_variants._builtin._type = type;}
 164 CF_INLINE void __CFCSetPutRangeFirstChar(CFMutableCharacterSetRef cset, UInt32 first) {cset->_variants._range._firstChar = first;}
 165 CF_INLINE void __CFCSetPutRangeLength(CFMutableCharacterSetRef cset, CFIndex length) {cset->_variants._range._length = length;}
 166 CF_INLINE void __CFCSetPutStringBuffer(CFMutableCharacterSetRef cset, UniChar *theBuffer) {cset->_variants._string._buffer = theBuffer;}
 167 CF_INLINE void __CFCSetPutStringLength(CFMutableCharacterSetRef cset, CFIndex length) {cset->_variants._string._length = length;}
 168 CF_INLINE void __CFCSetPutBitmapBits(CFMutableCharacterSetRef cset, uint8_t *bits) {cset->_variants._bitmap._bits = bits;}
 169 CF_INLINE void __CFCSetPutCompactBitmapBits(CFMutableCharacterSetRef cset, uint8_t *bits) {cset->_variants._compactBitmap._cBits = bits;}
 170
 171 /* Validation funcs
 172 */
 173 #if defined(CF_ENABLE_ASSERTIONS)
 174 CF_INLINE void __CFCSetValidateBuiltinType(CFCharacterSetPredefinedSet type, const char *func) {
 175     CFAssert2(type > 0 && type <= __kCFLastBuiltinSetID, __kCFLogAssertion, "%s: Unknowen builtin type %d", func, type);
 176 }
 177 CF_INLINE void __CFCSetValidateRange(CFRange theRange, const char *func) {
 178     CFAssert3(theRange.location >= 0 && theRange.location + theRange.length <= 0x1FFFFF, __kCFLogAssertion, "%s: Range out of Unicode range (location -> %d length -> %d)", func, theRange.location, theRange.length);
 179 }
 180 CF_INLINE void __CFCSetValidateTypeAndMutability(CFCharacterSetRef cset, const char *func) {
 181     __CFGenericValidateType(cset, __kCFCharacterSetTypeID);
 182     CFAssert1(__CFCSetIsMutable(cset), __kCFLogAssertion, "%s: Immutable character set passed to mutable function", func);
 183 }
 184 #else
 185 #define __CFCSetValidateBuiltinType(t,f)
 186 #define __CFCSetValidateRange(r,f)
 187 #define __CFCSetValidateTypeAndMutability(r,f)
 188 #endif
 189
 190 /* Inline utility funcs
 191 */
 192 static Boolean __CFCSetIsEqualBitmap(const UInt32 *bits1, const UInt32 *bits2) {
 193     CFIndex length = __kCFBitmapSize / sizeof(UInt32);
 194
 195     if (bits1 == bits2) {
 196         return true;
 197     } else if (bits1 && bits2) {
 198         if (bits1 == (const UInt32 *)-1) {
 199             while (length--) if ((UInt32)-1 != *bits2++) return false;
 200         } else if (bits2 == (const UInt32 *)-1) {
 201             while (length--) if ((UInt32)-1 != *bits1++) return false;
 202         } else {
 203             while (length--) if (*bits1++ != *bits2++) return false;
 204         }
 205         return true;
 206     } else if (!bits1 && !bits2) { // empty set
 207         return true;
 208     } else {
 209         if (bits2) bits1 = bits2;
 210         if (bits1 == (const UInt32 *)-1) return false;
 211         while (length--) if (*bits1++) return false;
 212         return true;
 213     }
 214 }
 215
 216 CF_INLINE Boolean __CFCSetIsEqualBitmapInverted(const UInt32 *bits1, const UInt32 *bits2) {
 217     CFIndex length = __kCFBitmapSize / sizeof(UInt32);
 218
 219     while (length--) if (*bits1++ != ~(*(bits2++))) return false;
 220     return true;
 221 }
 222
 223 static Boolean __CFCSetIsBitmapEqualToRange(const UInt32 *bits, UniChar firstChar, UniChar lastChar, Boolean isInverted) {
 224     CFIndex firstCharIndex = firstChar >> LOG_BPB;
 225     CFIndex lastCharIndex = lastChar >> LOG_BPB;
 226     CFIndex length;
 227     UInt32 value;
 228
 229     if (firstCharIndex == lastCharIndex) {
 230         value = ((((UInt32)0xFF) << (firstChar & (BITSPERBYTE - 1))) & (((UInt32)0xFF) >> ((BITSPERBYTE - 1) - (lastChar & (BITSPERBYTE - 1))))) << (((sizeof(UInt32) - 1) - (firstCharIndex % sizeof(UInt32))) * BITSPERBYTE);
 231         value = CFSwapInt32HostToBig(value);
 232         firstCharIndex = lastCharIndex = firstChar >> LOG_BPLW;
 233         if (*(bits + firstCharIndex) != (isInverted ? ~value : value)) return FALSE;
 234     } else {
 235         UInt32 firstCharMask;
 236         UInt32 lastCharMask;
 237
 238         length = firstCharIndex % sizeof(UInt32);
 239         firstCharMask = ((((UInt32)0xFF) << (firstChar & (BITSPERBYTE - 1))) << (((sizeof(UInt32) - 1) - length) * BITSPERBYTE)) | (0xFFFFFFFF >> ((length + 1) * BITSPERBYTE));
 240
 241         length = lastCharIndex % sizeof(UInt32);
 242         lastCharMask = ((((UInt32)0xFF) >> ((BITSPERBYTE - 1) - (lastChar & (BITSPERBYTE - 1)))) << (((sizeof(UInt32) - 1) - length) * BITSPERBYTE)) | (0xFFFFFFFF << ((sizeof(UInt32) - length) * BITSPERBYTE));
 243
 244         firstCharIndex = firstChar >> LOG_BPLW;
 245         lastCharIndex = lastChar >> LOG_BPLW;
 246
 247         if (firstCharIndex == lastCharIndex) {
 248             firstCharMask &= lastCharMask;
 249             value = CFSwapInt32HostToBig(firstCharMask & lastCharMask);
 250             if (*(bits + firstCharIndex) != (isInverted ? ~value : value)) return FALSE;
 251         } else {
 252             value = CFSwapInt32HostToBig(firstCharMask);
 253             if (*(bits + firstCharIndex) != (isInverted ? ~value : value)) return FALSE;
 254
 255             value = CFSwapInt32HostToBig(lastCharMask);
 256             if (*(bits + lastCharIndex) != (isInverted ? ~value : value)) return FALSE;
 257         }
 258     }
 259
 260     length = firstCharIndex;
 261     value = (isInverted ? 0xFFFFFFFF : 0);
 262     while (length--) {
 263         if (*(bits++) != value) return FALSE;
 264     }
 265
 266     ++bits; // Skip firstCharIndex
 267     length = (lastCharIndex - (firstCharIndex + 1));
 268     value = (isInverted ? 0 : 0xFFFFFFFF);
 269     while (length-- > 0) {
 270         if (*(bits++) != value) return FALSE;
 271     }
 272     if (firstCharIndex != lastCharIndex) ++bits;
 273
 274     length = (0xFFFF >> LOG_BPLW) - lastCharIndex;
 275     value = (isInverted ? 0xFFFFFFFF : 0);
 276     while (length--) {
 277         if (*(bits++) != value) return FALSE;
 278     }
 279
 280     return TRUE;
 281 }
 282
 283 CF_INLINE Boolean __CFCSetIsBitmapSupersetOfBitmap(const UInt32 *bits1, const UInt32 *bits2, Boolean isInverted1, Boolean isInverted2) {
 284     CFIndex length = __kCFBitmapSize / sizeof(UInt32);
 285     UInt32 val1, val2;
 286
 287     while (length--) {
 288         val2 = (isInverted2 ? ~(*(bits2++)) : *(bits2++));
 289         val1 = (isInverted1 ? ~(*(bits1++)) : *(bits1++)) & val2;
 290         if (val1 != val2) return false;
 291     }
 292
 293     return true;
 294 }
 295
 296 CF_INLINE Boolean __CFCSetHasNonBMPPlane(CFCharacterSetRef cset) { return ((cset)->_annex && (cset)->_annex->_validEntriesBitmap ? true : false); }
 297 CF_INLINE Boolean __CFCSetAnnexIsInverted (CFCharacterSetRef cset) { return ((cset)->_annex && (cset)->_annex->_isAnnexInverted ? true : false); }
 298 CF_INLINE UInt32 __CFCSetAnnexValidEntriesBitmap(CFCharacterSetRef cset) { return ((cset)->_annex && (cset)->_annex->_validEntriesBitmap ? (cset)->_annex->_validEntriesBitmap : 0); }
 299
 300 CF_INLINE Boolean __CFCSetIsEmpty(CFCharacterSetRef cset) {
 301     if (__CFCSetHasNonBMPPlane(cset) || __CFCSetAnnexIsInverted(cset)) return false;
 302
 303     switch (__CFCSetClassType(cset)) {
 304         case __kCFCharSetClassRange: if (!__CFCSetRangeLength(cset)) return true; break;
 305         case __kCFCharSetClassString: if (!__CFCSetStringLength(cset)) return true; break;
 306         case __kCFCharSetClassBitmap: if (!__CFCSetBitmapBits(cset)) return true; break;
 307         case __kCFCharSetClassCompactBitmap: if (!__CFCSetCompactBitmapBits(cset)) return true; break;
 308     }
 309     return false;
 310 }
 311
 312 CF_INLINE void __CFCSetBitmapAddCharacter(uint8_t *bitmap, UniChar theChar) {
 313     bitmap[(theChar) >> LOG_BPB] |= (((unsigned)1) << (theChar & (BITSPERBYTE - 1)));
 314 }
 315
 316 CF_INLINE void __CFCSetBitmapRemoveCharacter(uint8_t *bitmap, UniChar theChar) {
 317     bitmap[(theChar) >> LOG_BPB] &= ~(((unsigned)1) << (theChar & (BITSPERBYTE - 1)));
 318 }
 319
 320 CF_INLINE Boolean __CFCSetIsMemberBitmap(const uint8_t *bitmap, UniChar theChar) {
 321     return ((bitmap[(theChar) >> LOG_BPB] & (((unsigned)1) << (theChar & (BITSPERBYTE - 1)))) ? true : false);
 322 }
 323
 324 #define NUM_32BIT_SLOTS (NUMCHARACTERS / 32)
 325
 326 CF_INLINE void __CFCSetBitmapFastFillWithValue(UInt32 *bitmap, uint8_t value) {
 327     UInt32 mask = (value << 24) | (value << 16) | (value << 8) | value;
 328     UInt32 numSlots = NUMCHARACTERS / 32;
 329
 330     while (numSlots--) *(bitmap++) = mask;
 331 }
 332
 333 CF_INLINE void __CFCSetBitmapAddCharactersInRange(uint8_t *bitmap, UniChar firstChar, UniChar lastChar) {
 334     if (firstChar == lastChar) {
 335         bitmap[firstChar >> LOG_BPB] |= (((unsigned)1) << (firstChar & (BITSPERBYTE - 1)));
 336     } else {
 337         UInt32 idx = firstChar >> LOG_BPB;
 338         UInt32 max = lastChar >> LOG_BPB;
 339
 340         if (idx == max) {
 341             bitmap[idx] |= (((unsigned)0xFF) << (firstChar & (BITSPERBYTE - 1))) & (((unsigned)0xFF) >> ((BITSPERBYTE - 1) - (lastChar & (BITSPERBYTE - 1))));
 342         } else {
 343             bitmap[idx] |= (((unsigned)0xFF) << (firstChar & (BITSPERBYTE - 1)));
 344             bitmap[max] |= (((unsigned)0xFF) >> ((BITSPERBYTE - 1) - (lastChar & (BITSPERBYTE - 1))));
 345
 346             ++idx;
 347             while (idx < max) bitmap[idx++] = 0xFF;
 348         }
 349     }
 350 }
 351
 352 CF_INLINE void __CFCSetBitmapRemoveCharactersInRange(uint8_t *bitmap, UniChar firstChar, UniChar lastChar) {
 353     UInt32 idx = firstChar >> LOG_BPB;
 354     UInt32 max = lastChar >> LOG_BPB;
 355
 356     if (idx == max) {
 357         bitmap[idx] &= ~((((unsigned)0xFF) << (firstChar & (BITSPERBYTE - 1))) & (((unsigned)0xFF) >> ((BITSPERBYTE - 1) - (lastChar & (BITSPERBYTE - 1)))));
 358     } else {
 359         bitmap[idx] &= ~(((unsigned)0xFF) << (firstChar & (BITSPERBYTE - 1)));
 360         bitmap[max] &= ~(((unsigned)0xFF) >> ((BITSPERBYTE - 1) - (lastChar & (BITSPERBYTE - 1))));
 361
 362         ++idx;
 363         while (idx < max) bitmap[idx++] = 0;
 364     }
 365 }
 366
 367 #define __CFCSetAnnexBitmapSetPlane(bitmap,plane)       ((bitmap) |= (1 << (plane)))
 368 #define __CFCSetAnnexBitmapClearPlane(bitmap,plane)     ((bitmap) &= (~(1 << (plane))))
 369 #define __CFCSetAnnexBitmapGetPlane(bitmap,plane)       ((bitmap) & (1 << (plane)))
 370
 371 CF_INLINE void __CFCSetAnnexSetIsInverted(CFCharacterSetRef cset, Boolean flag) {
 372     if (cset->_annex) ((CFMutableCharacterSetRef)cset)->_annex->_isAnnexInverted = flag;
 373 }
 374
 375 CF_INLINE void __CFCSetAllocateAnnexForPlane(CFCharacterSetRef cset, int plane) {
 376     if (cset->_annex == NULL) {
 377         ((CFMutableCharacterSetRef)cset)->_annex = (CFCharSetAnnexStruct *)CFAllocatorAllocate(CFGetAllocator(cset), sizeof(CFCharSetAnnexStruct), 0);
 378         cset->_annex->_numOfAllocEntries = plane;
 379         cset->_annex->_isAnnexInverted = false;
 380         cset->_annex->_validEntriesBitmap = 0;
 381         cset->_annex->_nonBMPPlanes = (CFCharacterSetRef*)CFAllocatorAllocate(CFGetAllocator(cset), sizeof(CFCharacterSetRef) * plane, 0);
 382     } else if (cset->_annex->_numOfAllocEntries < plane) {
 383         cset->_annex->_numOfAllocEntries = plane;
 384         cset->_annex->_nonBMPPlanes = (CFCharacterSetRef*)CFAllocatorReallocate(CFGetAllocator(cset), (void *)cset->_annex->_nonBMPPlanes, sizeof(CFCharacterSetRef) * plane, 0);
 385     }
 386 }
 387
 388 CF_INLINE void __CFCSetPutCharacterSetToAnnexPlane(CFCharacterSetRef cset, CFCharacterSetRef annexCSet, int plane) {
 389     __CFCSetAllocateAnnexForPlane(cset, plane);
 390     if (__CFCSetAnnexBitmapGetPlane(cset->_annex->_validEntriesBitmap, plane)) CFRelease(cset->_annex->_nonBMPPlanes[plane - 1]);
 391     if (annexCSet) {
 392         cset->_annex->_nonBMPPlanes[plane - 1] = CFRetain(annexCSet);
 393         __CFCSetAnnexBitmapSetPlane(cset->_annex->_validEntriesBitmap, plane);
 394     } else {
 395         __CFCSetAnnexBitmapClearPlane(cset->_annex->_validEntriesBitmap, plane);
 396     }
 397 }
 398
 399 CF_INLINE CFCharacterSetRef __CFCSetGetAnnexPlaneCharacterSet(CFCharacterSetRef cset, int plane) {
 400     __CFCSetAllocateAnnexForPlane(cset, plane);
 401     if (!__CFCSetAnnexBitmapGetPlane(cset->_annex->_validEntriesBitmap, plane)) {
 402         cset->_annex->_nonBMPPlanes[plane - 1] = (CFCharacterSetRef)CFCharacterSetCreateMutable(CFGetAllocator(cset));
 403         __CFCSetAnnexBitmapSetPlane(cset->_annex->_validEntriesBitmap, plane);
 404     }
 405     return cset->_annex->_nonBMPPlanes[plane - 1];
 406 }
 407
 408 CF_INLINE CFCharacterSetRef __CFCSetGetAnnexPlaneCharacterSetNoAlloc(CFCharacterSetRef cset, int plane) {
 409     return (cset->_annex && __CFCSetAnnexBitmapGetPlane(cset->_annex->_validEntriesBitmap, plane) ? cset->_annex->_nonBMPPlanes[plane - 1] : NULL);
 410 }
 411
 412 CF_INLINE void __CFCSetDeallocateAnnexPlane(CFCharacterSetRef cset) {
 413     if (cset->_annex) {
 414         int idx;
 415
 416         for (idx = 0;idx < MAX_ANNEX_PLANE;idx++) {
 417             if (__CFCSetAnnexBitmapGetPlane(cset->_annex->_validEntriesBitmap, idx + 1)) {
 418                 CFRelease(cset->_annex->_nonBMPPlanes[idx]);
 419             }
 420         }
 421         CFAllocatorDeallocate(CFGetAllocator(cset), cset->_annex->_nonBMPPlanes);
 422         CFAllocatorDeallocate(CFGetAllocator(cset), cset->_annex);
 423         ((CFMutableCharacterSetRef)cset)->_annex = NULL;
 424     }
 425 }
 426
 427 CF_INLINE uint8_t __CFCSetGetHeaderValue(const uint8_t *bitmap, int *numPages) {
 428     uint8_t value = *bitmap;
 429
 430     if ((value == 0) || (value == UINT8_MAX)) {
 431         int numBytes = __kCFCompactBitmapPageSize - 1;
 432
 433         while (numBytes > 0) {
 434             if (*(++bitmap) != value) break;
 435             --numBytes;
 436         }
 437         if (numBytes == 0) return value;
 438     }
 439     return (uint8_t)(++(*numPages));
 440 }
 441
 442 CF_INLINE bool __CFCSetIsMemberInCompactBitmap(const uint8_t *compactBitmap, UTF16Char character) {
 443     uint8_t value = compactBitmap[(character >> 8)]; // Assuming __kCFCompactBitmapNumPages == 256
 444
 445     if (value == 0) {
 446         return false;
 447     } else if (value == UINT8_MAX) {
 448         return true;
 449     } else {
 450         compactBitmap += (__kCFCompactBitmapNumPages + (__kCFCompactBitmapPageSize * (value - 1)));
 451         character &= 0xFF; // Assuming __kCFCompactBitmapNumPages == 256
 452         return ((compactBitmap[(character / BITSPERBYTE)] & (1 << (character % BITSPERBYTE))) ? true : false);
 453     }
 454 }
 455
 456 CF_INLINE uint32_t __CFCSetGetCompactBitmapSize(const uint8_t *compactBitmap) {
 457     uint32_t length = __kCFCompactBitmapNumPages;
 458     uint32_t size = __kCFCompactBitmapNumPages;
 459     uint8_t value;
 460
 461     while (length-- > 0) {
 462         value = *(compactBitmap++);
 463         if ((value != 0) && (value != UINT8_MAX)) size += __kCFCompactBitmapPageSize;
 464     }
 465     return size;
 466 }
 467
 468 /* Take a private "set" structure and make a bitmap from it.  Return the bitmap.  THE CALLER MUST RELEASE THE RETURNED MEMORY as necessary.
 469 */
 470
 471 CF_INLINE void __CFCSetBitmapProcessManyCharacters(unsigned char *map, unsigned n, unsigned m, Boolean isInverted) {
 472     if (isInverted) {
 473         __CFCSetBitmapRemoveCharactersInRange(map, n, m);
 474     } else {
 475         __CFCSetBitmapAddCharactersInRange(map, n, m);
 476     }
 477 }
 478
 479 CF_INLINE void __CFExpandCompactBitmap(const uint8_t *src, uint8_t *dst) {
 480     const uint8_t *srcBody = src + __kCFCompactBitmapNumPages;
 481     int i;
 482     uint8_t value;
 483
 484     for (i = 0;i < __kCFCompactBitmapNumPages;i++) {
 485         value = *(src++);
 486         if ((value == 0) || (value == UINT8_MAX)) {
 487             memset(dst, value, __kCFCompactBitmapPageSize);
 488         } else {
 489             memmove(dst, srcBody, __kCFCompactBitmapPageSize);
 490             srcBody += __kCFCompactBitmapPageSize;
 491         }
 492         dst += __kCFCompactBitmapPageSize;
 493     }
 494 }
 495
 496
 497 static void __CFCheckForExpandedSet(CFCharacterSetRef cset) {
 498     static int8_t __CFNumberOfPlanesForLogging = -1;
 499     static bool warnedOnce = false;
 500
 501     if (0 > __CFNumberOfPlanesForLogging) {
 502         const char *envVar = getenv("CFCharacterSetCheckForExpandedSet");
 503         long value = (envVar ? strtol(envVar, NULL, 0) : 0);
 504         __CFNumberOfPlanesForLogging = (((value > 0) && (value <= 16)) ? value : 0);
 505     }
 506
 507     if (__CFNumberOfPlanesForLogging) {
 508         uint32_t entries = __CFCSetAnnexValidEntriesBitmap(cset);
 509         int count = 0;
 510
 511         while (entries) {
 512             if ((entries & 1) && (++count >= __CFNumberOfPlanesForLogging)) {
 513                 if (!warnedOnce) {
 514                     CFLog(0, CFSTR("An expanded CFMutableCharacter has been detected.  Recommend to compact with CFCharacterSetCreateCopy"));
 515                     warnedOnce = true;
 516                 }
 517                 break;
 518             }
 519             entries >>= 1;
 520         }
 521     }
 522 }
 523
 524 static void __CFCSetGetBitmap(CFCharacterSetRef cset, uint8_t *bits) {
 525     uint8_t *bitmap;
 526     CFIndex length = __kCFBitmapSize;
 527
 528     if (__CFCSetIsBitmap(cset) && (bitmap = __CFCSetBitmapBits(cset))) {
 529         memmove(bits, bitmap, __kCFBitmapSize);
 530     } else {
 531         Boolean isInverted = __CFCSetIsInverted(cset);
 532         uint8_t value = (isInverted ? (uint8_t)-1 : 0);
 533
 534         bitmap = bits;
 535         while (length--) *bitmap++ = value; // Initialize the buffer
 536
 537         if (!__CFCSetIsEmpty(cset)) {
 538             switch (__CFCSetClassType(cset)) {
 539                 case __kCFCharSetClassBuiltin: {
 540                     UInt8 result = CFUniCharGetBitmapForPlane(__CFCSetBuiltinType(cset), 0, bits, isInverted);
 541                     if (result == kCFUniCharBitmapEmpty && isInverted) {
 542                         length = __kCFBitmapSize;
 543                         bitmap = bits;
 544                         while (length--) *bitmap++ = 0;
 545                     } else if (result == kCFUniCharBitmapAll && !isInverted) {
 546                         length = __kCFBitmapSize;
 547                         bitmap = bits;
 548                         while (length--) *bitmap++ = (UInt8)0xFF;
 549                     }
 550                 }
 551                     break;
 552
 553                 case __kCFCharSetClassRange: {
 554                     UInt32 theChar = __CFCSetRangeFirstChar(cset);
 555                     if (theChar < NUMCHARACTERS) { // the range starts in BMP
 556                         length = __CFCSetRangeLength(cset);
 557                         if (theChar + length >= NUMCHARACTERS) length = NUMCHARACTERS - theChar;
 558                         if (isInverted) {
 559                             __CFCSetBitmapRemoveCharactersInRange(bits, theChar, (theChar + length) - 1);
 560                         } else {
 561                             __CFCSetBitmapAddCharactersInRange(bits, theChar, (theChar + length) - 1);
 562                         }
 563                     }
 564                 }
 565                     break;
 566
 567                 case __kCFCharSetClassString: {
 568                     const UniChar *buffer = __CFCSetStringBuffer(cset);
 569                     length = __CFCSetStringLength(cset);
 570                     while (length--) (isInverted ? __CFCSetBitmapRemoveCharacter(bits, *buffer++) : __CFCSetBitmapAddCharacter(bits, *buffer++));
 571                 }
 572                     break;
 573
 574                 case __kCFCharSetClassCompactBitmap:
 575                     __CFExpandCompactBitmap(__CFCSetCompactBitmapBits(cset), bits);
 576                     break;
 577             }
 578         }
 579     }
 580 }
 581
 582 static Boolean __CFCharacterSetEqual(CFTypeRef cf1, CFTypeRef cf2);
 583
 584 static Boolean __CFCSetIsEqualAnnex(CFCharacterSetRef cf1, CFCharacterSetRef cf2) {
 585     CFCharacterSetRef subSet1;
 586     CFCharacterSetRef subSet2;
 587     Boolean isAnnexInvertStateIdentical = (__CFCSetAnnexIsInverted(cf1) == __CFCSetAnnexIsInverted(cf2) ? true: false);
 588     int idx;
 589
 590     if (isAnnexInvertStateIdentical) {
 591         if (__CFCSetAnnexValidEntriesBitmap(cf1) != __CFCSetAnnexValidEntriesBitmap(cf2)) return false;
 592         for (idx = 1;idx <= MAX_ANNEX_PLANE;idx++) {
 593             subSet1 = __CFCSetGetAnnexPlaneCharacterSetNoAlloc(cf1, idx);
 594             subSet2 = __CFCSetGetAnnexPlaneCharacterSetNoAlloc(cf2, idx);
 595
 596             if (subSet1 && !__CFCharacterSetEqual(subSet1, subSet2)) return false;
 597         }
 598     } else {
 599         uint8_t bitsBuf[__kCFBitmapSize];
 600 #if __MACOS8__
 601         uint8_t *bitsBuf2 = NULL;
 602 #else __MACOS8__
 603         uint8_t bitsBuf2[__kCFBitmapSize];
 604 #endif __MACOS8__
 605
 606         for (idx = 1;idx <= MAX_ANNEX_PLANE;idx++) {
 607             subSet1 = __CFCSetGetAnnexPlaneCharacterSetNoAlloc(cf1, idx);
 608             subSet2 = __CFCSetGetAnnexPlaneCharacterSetNoAlloc(cf2, idx);
 609
 610             if (subSet1 == NULL && subSet2 == NULL) {
 611 #if __MACOS8__
 612                 if (bitsBuf2) CFAllocatorDeallocate(NULL, bitsBuf2);
 613 #endif __MACOS8__
 614                 return false;
 615             } else if (subSet1 == NULL) {
 616                 if (__CFCSetIsBitmap(subSet2)) {
 617                     if (!__CFCSetIsEqualBitmap((const UInt32 *)__CFCSetBitmapBits(subSet2), (const UInt32 *)-1)) {
 618 #if __MACOS8__
 619                         if (bitsBuf2) CFAllocatorDeallocate(NULL, bitsBuf2);
 620 #endif __MACOS8__
 621                         return false;
 622                     }
 623                 } else {
 624                     __CFCSetGetBitmap(subSet2, bitsBuf);
 625                     if (!__CFCSetIsEqualBitmap((const UInt32 *)bitsBuf, (const UInt32 *)-1)) {
 626 #if __MACOS8__
 627                         if (bitsBuf2) CFAllocatorDeallocate(NULL, bitsBuf2);
 628 #endif __MACOS8__
 629                         return false;
 630                     }
 631                 }
 632             } else if (subSet2 == NULL) {
 633                 if (__CFCSetIsBitmap(subSet1)) {
 634                     if (!__CFCSetIsEqualBitmap((const UInt32 *)__CFCSetBitmapBits(subSet1), (const UInt32 *)-1)) {
 635 #if __MACOS8__
 636                         if (bitsBuf2) CFAllocatorDeallocate(NULL, bitsBuf2);
 637 #endif __MACOS8__
 638                         return false;
 639                     }
 640                 } else {
 641                     __CFCSetGetBitmap(subSet1, bitsBuf);
 642                     if (!__CFCSetIsEqualBitmap((const UInt32 *)bitsBuf, (const UInt32 *)-1)) {
 643 #if __MACOS8__
 644                         if (bitsBuf2) CFAllocatorDeallocate(NULL, bitsBuf2);
 645 #endif __MACOS8__
 646                         return false;
 647                     }
 648                 }
 649             } else {
 650                 Boolean isBitmap1 = __CFCSetIsBitmap(subSet1);
 651                 Boolean isBitmap2 = __CFCSetIsBitmap(subSet2);
 652
 653                 if (isBitmap1 && isBitmap2) {
 654                     if (!__CFCSetIsEqualBitmapInverted((const UInt32 *)__CFCSetBitmapBits(subSet1), (const UInt32 *)__CFCSetBitmapBits(subSet2))) {
 655 #if __MACOS8__
 656                         if (bitsBuf2) CFAllocatorDeallocate(NULL, bitsBuf2);
 657 #endif __MACOS8__
 658                         return false;
 659                     }
 660                 } else if (!isBitmap1 && !isBitmap2) {
 661                     __CFCSetGetBitmap(subSet1, bitsBuf);
 662 #if __MACOS8__
 663                     if (bitsBuf2 == NULL) bitsBuf2 = (UInt32 *)CFAllocatorAllocate(NULL, __kCFBitmapSize, 0);
 664 #endif __MACOS8__
 665                     __CFCSetGetBitmap(subSet2, bitsBuf2);
 666                     if (!__CFCSetIsEqualBitmapInverted((const UInt32 *)bitsBuf, (const UInt32 *)bitsBuf2)) {
 667 #if __MACOS8__
 668                         CFAllocatorDeallocate(NULL, bitsBuf2);
 669 #endif __MACOS8__
 670                         return false;
 671                     }
 672                 } else {
 673                     if (isBitmap2) {
 674                         CFCharacterSetRef tmp = subSet2;
 675                         subSet2 = subSet1;
 676                         subSet1 = tmp;
 677                     }
 678                     __CFCSetGetBitmap(subSet2, bitsBuf);
 679                     if (!__CFCSetIsEqualBitmapInverted((const UInt32 *)__CFCSetBitmapBits(subSet1), (const UInt32 *)bitsBuf)) {
 680 #if __MACOS8__
 681                         if (bitsBuf2) CFAllocatorDeallocate(NULL, bitsBuf2);
 682 #endif __MACOS8__
 683                         return false;
 684                     }
 685                 }
 686             }
 687         }
 688     }
 689     return true;
 690 }
 691
 692 /* Compact bitmap
 693 */
 694 static uint8_t *__CFCreateCompactBitmap(CFAllocatorRef allocator, const uint8_t *bitmap) {
 695     const uint8_t *src;
 696     uint8_t *dst;
 697     int i;
 698     int numPages = 0;
 699     uint8_t header[__kCFCompactBitmapNumPages];
 700
 701     src = bitmap;
 702     for (i = 0;i < __kCFCompactBitmapNumPages;i++) {
 703         header[i] = __CFCSetGetHeaderValue(src, &numPages);
 704
 705         // Allocating more pages is probably not interesting enough to be compact
 706         if (numPages > __kCFCompactBitmapMaxPages) return NULL;
 707         src += __kCFCompactBitmapPageSize;
 708     }
 709
 710     dst = (uint8_t *)CFAllocatorAllocate(allocator, __kCFCompactBitmapNumPages + (__kCFCompactBitmapPageSize * numPages), 0);
 711
 712     if (numPages > 0) {
 713         uint8_t *dstBody = dst + __kCFCompactBitmapNumPages;
 714
 715         src = bitmap;
 716         for (i = 0;i < __kCFCompactBitmapNumPages;i++) {
 717             dst[i] = header[i];
 718
 719             if ((dst[i] != 0) && (dst[i] != UINT8_MAX)) {
 720                 memmove(dstBody, src, __kCFCompactBitmapPageSize);
 721                 dstBody += __kCFCompactBitmapPageSize;
 722             }
 723             src += __kCFCompactBitmapPageSize;
 724         }
 725     } else {
 726         memmove(dst, header, __kCFCompactBitmapNumPages);
 727     }
 728
 729     return dst;
 730 }
 731
 732 static void __CFCSetMakeCompact(CFMutableCharacterSetRef cset) {
 733     if (__CFCSetIsBitmap(cset) && __CFCSetBitmapBits(cset)) {
 734         uint8_t *bitmap = __CFCSetBitmapBits(cset);
 735         uint8_t *cBitmap = __CFCreateCompactBitmap(CFGetAllocator(cset), bitmap);
 736
 737         if (cBitmap) {
 738             CFAllocatorDeallocate(CFGetAllocator(cset), bitmap);
 739             __CFCSetPutClassType(cset, __kCFCharSetClassCompactBitmap);
 740             __CFCSetPutCompactBitmapBits(cset, cBitmap);
 741         }
 742     }
 743 }
 744
 745 static void __CFCSetAddNonBMPPlanesInRange(CFMutableCharacterSetRef cset, CFRange range) {
 746     int firstChar = (range.location & 0xFFFF);
 747     int maxChar = range.location + range.length;
 748     int idx = range.location >> 16; // first plane
 749     int maxPlane = (maxChar - 1) >> 16; // last plane
 750     CFRange planeRange;
 751     CFMutableCharacterSetRef annexPlane;
 752
 753     maxChar &= 0xFFFF;
 754
 755     for (idx = (idx ? idx : 1);idx <= maxPlane;idx++) {
 756         planeRange.location = __CFMax(firstChar, 0);
 757         planeRange.length = (idx == maxPlane && maxChar ? maxChar : 0x10000) - planeRange.location;
 758         if (__CFCSetAnnexIsInverted(cset)) {
 759             if ((annexPlane = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSetNoAlloc(cset, idx))) {
 760                 CFCharacterSetRemoveCharactersInRange(annexPlane, planeRange);
 761                 if (__CFCSetIsEmpty(annexPlane) && !__CFCSetIsInverted(annexPlane)) {
 762                     CFRelease(annexPlane);
 763                     __CFCSetAnnexBitmapClearPlane(cset->_annex->_validEntriesBitmap, idx);
 764                 }
 765             }
 766         } else {
 767             CFCharacterSetAddCharactersInRange((CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSet(cset, idx), planeRange);
 768         }
 769     }
 770     if (!__CFCSetHasNonBMPPlane(cset) && !__CFCSetAnnexIsInverted(cset)) __CFCSetDeallocateAnnexPlane(cset);
 771 }
 772
 773 static void __CFCSetRemoveNonBMPPlanesInRange(CFMutableCharacterSetRef cset, CFRange range) {
 774     int firstChar = (range.location & 0xFFFF);
 775     int maxChar = range.location + range.length;
 776     int idx = range.location >> 16; // first plane
 777     int maxPlane = (maxChar - 1) >> 16; // last plane
 778     CFRange planeRange;
 779     CFMutableCharacterSetRef annexPlane;
 780
 781     maxChar &= 0xFFFF;
 782
 783     for (idx = (idx ? idx : 1);idx <= maxPlane;idx++) {
 784         planeRange.location = __CFMax(firstChar, 0);
 785         planeRange.length = (idx == maxPlane && maxChar ? maxChar : 0x10000) - planeRange.location;
 786         if (__CFCSetAnnexIsInverted(cset)) {
 787             CFCharacterSetAddCharactersInRange((CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSet(cset, idx), planeRange);
 788         } else {
 789             if ((annexPlane = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSetNoAlloc(cset, idx))) {
 790                 CFCharacterSetRemoveCharactersInRange(annexPlane, planeRange);
 791                 if(__CFCSetIsEmpty(annexPlane) && !__CFCSetIsInverted(annexPlane)) {
 792                     CFRelease(annexPlane);
 793                     __CFCSetAnnexBitmapClearPlane(cset->_annex->_validEntriesBitmap, idx);
 794                 }
 795             }
 796         }
 797     }
 798     if (!__CFCSetHasNonBMPPlane(cset) && !__CFCSetAnnexIsInverted(cset)) __CFCSetDeallocateAnnexPlane(cset);
 799 }
 800
 801 static void __CFCSetMakeBitmap(CFMutableCharacterSetRef cset) {
 802     if (!__CFCSetIsBitmap(cset) || !__CFCSetBitmapBits(cset)) {
 803         uint8_t *bitmap = CFAllocatorAllocate(CFGetAllocator(cset), __kCFBitmapSize, 0);
 804         __CFCSetGetBitmap(cset, bitmap);
 805
 806         if (__CFCSetIsBuiltin(cset)) {
 807             CFIndex numPlanes = CFUniCharGetNumberOfPlanes(__CFCSetBuiltinType(cset));
 808
 809             if (numPlanes > 1) {
 810                 CFMutableCharacterSetRef annexSet;
 811                 uint8_t *annexBitmap = NULL;
 812                 int idx;
 813                 UInt8 result;
 814
 815                 __CFCSetAllocateAnnexForPlane(cset, numPlanes - 1);
 816                 for (idx = 1;idx < numPlanes;idx++) {
 817                     if (NULL == annexBitmap) annexBitmap = CFAllocatorAllocate(CFGetAllocator(cset), __kCFBitmapSize, 0);
 818                     result = CFUniCharGetBitmapForPlane(__CFCSetBuiltinType(cset), idx, annexBitmap, false);
 819                     if (result == kCFUniCharBitmapEmpty) continue;
 820                     if (result == kCFUniCharBitmapAll) {
 821                         CFIndex bitmapLength = __kCFBitmapSize;
 822                         uint8_t *bytes = annexBitmap;
 823                         while (bitmapLength-- > 0) *(bytes++) = (uint8_t)0xFF;
 824                     }
 825                     annexSet = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSet(cset, idx);
 826                     __CFCSetPutClassType(annexSet, __kCFCharSetClassBitmap);
 827                     __CFCSetPutBitmapBits(annexSet, annexBitmap);
 828                     __CFCSetPutIsInverted(annexSet, false);
 829                     __CFCSetPutHasHashValue(annexSet, false);
 830                     annexBitmap = NULL;
 831                 }
 832                 if (annexBitmap) CFAllocatorDeallocate(CFGetAllocator(cset), annexBitmap);
 833             }
 834         } else if (__CFCSetIsCompactBitmap(cset) && __CFCSetCompactBitmapBits(cset)) {
 835             CFAllocatorDeallocate(CFGetAllocator(cset), __CFCSetCompactBitmapBits(cset));
 836             __CFCSetPutCompactBitmapBits(cset, NULL);
 837         } else if (__CFCSetIsString(cset) && __CFCSetStringBuffer(cset)) {
 838             CFAllocatorDeallocate(CFGetAllocator(cset), __CFCSetStringBuffer(cset));
 839             __CFCSetPutStringBuffer(cset, NULL);
 840         } else if (__CFCSetIsRange(cset)) { // We may have to allocate annex here
 841             Boolean needsToInvert = (!__CFCSetHasNonBMPPlane(cset) && __CFCSetIsInverted(cset) ? true : false);
 842             __CFCSetAddNonBMPPlanesInRange(cset, CFRangeMake(__CFCSetRangeFirstChar(cset), __CFCSetRangeLength(cset)));
 843             if (needsToInvert) __CFCSetAnnexSetIsInverted(cset, true);
 844         }
 845         __CFCSetPutClassType(cset, __kCFCharSetClassBitmap);
 846         __CFCSetPutBitmapBits(cset, bitmap);
 847         __CFCSetPutIsInverted(cset, false);
 848     }
 849 }
 850
 851 CF_INLINE CFMutableCharacterSetRef __CFCSetGenericCreate(CFAllocatorRef allocator, UInt32 flags) {
 852     CFMutableCharacterSetRef cset;
 853     CFIndex size = sizeof(struct __CFCharacterSet) - sizeof(CFRuntimeBase);
 854
 855     cset = (CFMutableCharacterSetRef)_CFRuntimeCreateInstance(allocator, CFCharacterSetGetTypeID(), size, NULL);
 856     if (NULL == cset) return NULL;
 857
 858     cset->_base._info |= flags;
 859     cset->_hashValue = 0;
 860     cset->_annex = NULL;
 861
 862     return cset;
 863 }
 864
 865 /* Bsearch theChar for __kCFCharSetClassString
 866 */
 867 CF_INLINE Boolean __CFCSetBsearchUniChar(const UniChar *theTable, CFIndex length, UniChar theChar) {
 868     const UniChar *p, *q, *divider;
 869
 870     if ((theChar < theTable[0]) || (theChar > theTable[length - 1])) return false;
 871
 872     p = theTable;
 873     q = p + (length - 1);
 874     while (p <= q) {
 875         divider = p + ((q - p) >> 1);   /* divide by 2 */
 876         if (theChar < *divider) q = divider - 1;
 877         else if (theChar > *divider) p = divider + 1;
 878         else return true;
 879     }
 880     return false;
 881 }
 882
 883 /* Predefined cset names
 884  Need to add entry here for new builtin types
 885 */
 886 CONST_STRING_DECL(__kCFCSetNameControl, "<CFCharacterSet Predefined Control Set>")
 887 CONST_STRING_DECL(__kCFCSetNameWhitespace, "<CFCharacterSet Predefined Whitespace Set>")
 888 CONST_STRING_DECL(__kCFCSetNameWhitespaceAndNewline, "<CFCharacterSet Predefined WhitespaceAndNewline Set>")
 889 CONST_STRING_DECL(__kCFCSetNameDecimalDigit, "<CFCharacterSet Predefined DecimalDigit Set>")
 890 CONST_STRING_DECL(__kCFCSetNameLetter, "<CFCharacterSet Predefined Letter Set>")
 891 CONST_STRING_DECL(__kCFCSetNameLowercaseLetter, "<CFCharacterSet Predefined LowercaseLetter Set>")
 892 CONST_STRING_DECL(__kCFCSetNameUppercaseLetter, "<CFCharacterSet Predefined UppercaseLetter Set>")
 893 CONST_STRING_DECL(__kCFCSetNameNonBase, "<CFCharacterSet Predefined NonBase Set>")
 894 CONST_STRING_DECL(__kCFCSetNameDecomposable, "<CFCharacterSet Predefined Decomposable Set>")
 895 CONST_STRING_DECL(__kCFCSetNameAlphaNumeric, "<CFCharacterSet Predefined AlphaNumeric Set>")
 896 CONST_STRING_DECL(__kCFCSetNamePunctuation, "<CFCharacterSet Predefined Punctuation Set>")
 897 CONST_STRING_DECL(__kCFCSetNameIllegal, "<CFCharacterSet Predefined Illegal Set>")
 898 CONST_STRING_DECL(__kCFCSetNameCapitalizedLetter, "<CFCharacterSet Predefined CapitalizedLetter Set>")
 899 CONST_STRING_DECL(__kCFCSetNameSymbol, "<CFCharacterSet Predefined Symbol Set>")
 900
 901 CONST_STRING_DECL(__kCFCSetNameStringTypeFormat, "<CFCharacterSet Items(")
 902
 903 /* Array of instantiated builtin set. Note builtin set ID starts with 1 so the array index is ID - 1
 904 */
 905 static CFCharacterSetRef *__CFBuiltinSets = NULL;
 906
 907 /* Global lock for character set
 908 */
 909 static CFSpinLock_t __CFCharacterSetLock = 0;
 910
 911 /* CFBase API functions
 912 */
 913 static Boolean __CFCharacterSetEqual(CFTypeRef cf1, CFTypeRef cf2) {
 914     Boolean isInvertStateIdentical = (__CFCSetIsInverted(cf1) == __CFCSetIsInverted(cf2) ? true: false);
 915     Boolean isAnnexInvertStateIdentical = (__CFCSetAnnexIsInverted(cf1) == __CFCSetAnnexIsInverted(cf2) ? true: false);
 916     CFIndex idx;
 917     CFCharacterSetRef subSet1;
 918     uint8_t bitsBuf[__kCFBitmapSize];
 919     uint8_t *bits;
 920     Boolean isBitmap1;
 921     Boolean isBitmap2;
 922
 923     if (__CFCSetHasHashValue(cf1) && __CFCSetHasHashValue(cf2) && ((CFCharacterSetRef)cf1)->_hashValue != ((CFCharacterSetRef)cf2)->_hashValue) return false;
 924     if (__CFCSetIsEmpty(cf1) && __CFCSetIsEmpty(cf2) && !isInvertStateIdentical) return false;
 925
 926     if (__CFCSetClassType(cf1) == __CFCSetClassType(cf2)) { // Types are identical, we can do it fast
 927         switch (__CFCSetClassType(cf1)) {
 928             case __kCFCharSetClassBuiltin:
 929                 return (__CFCSetBuiltinType(cf1) == __CFCSetBuiltinType(cf2) && isInvertStateIdentical ? true : false);
 930
 931             case __kCFCharSetClassRange:
 932                 return (__CFCSetRangeFirstChar(cf1) == __CFCSetRangeFirstChar(cf2) && __CFCSetRangeLength(cf1) && __CFCSetRangeLength(cf2) && isInvertStateIdentical ? true : false);
 933
 934             case __kCFCharSetClassString:
 935                 if (__CFCSetStringLength(cf1) == __CFCSetStringLength(cf2) && isInvertStateIdentical) {
 936                     const UniChar *buf1 = __CFCSetStringBuffer(cf1);
 937                     const UniChar *buf2 = __CFCSetStringBuffer(cf2);
 938                     CFIndex length = __CFCSetStringLength(cf1);
 939
 940                     while (length--) if (*buf1++ != *buf2++) return false;
 941                 } else {
 942                     return false;
 943                 }
 944                 break;
 945
 946             case __kCFCharSetClassBitmap:
 947                 if (!__CFCSetIsEqualBitmap((const UInt32 *)__CFCSetBitmapBits(cf1), (const UInt32 *)__CFCSetBitmapBits(cf2))) return false;
 948                 break;
 949         }
 950         return __CFCSetIsEqualAnnex(cf1, cf2);
 951     }
 952
 953     // Check for easy empty cases
 954     if (__CFCSetIsEmpty(cf1) || __CFCSetIsEmpty(cf2)) {
 955         CFCharacterSetRef emptySet = (__CFCSetIsEmpty(cf1) ? cf1 : cf2);
 956         CFCharacterSetRef nonEmptySet = (emptySet == cf1 ? cf2 : cf1);
 957
 958         if (__CFCSetIsBuiltin(nonEmptySet)) {
 959             return false;
 960         } else if (__CFCSetIsRange(nonEmptySet)) {
 961             if (isInvertStateIdentical) {
 962                 return (__CFCSetRangeLength(nonEmptySet) ? false : true);
 963             } else {
 964                 return (__CFCSetRangeLength(nonEmptySet) == 0x110000 ? true : false);
 965             }
 966         } else {
 967             if (__CFCSetAnnexIsInverted(nonEmptySet)) {
 968                 if (__CFCSetAnnexValidEntriesBitmap(nonEmptySet) != 0x1FFFE) return false;
 969             } else {
 970                 if (__CFCSetAnnexValidEntriesBitmap(nonEmptySet)) return false;
 971             }
 972
 973             if (__CFCSetIsBitmap(nonEmptySet)) {
 974                 bits = __CFCSetBitmapBits(nonEmptySet);
 975             } else {
 976                 bits = bitsBuf;
 977                 __CFCSetGetBitmap(nonEmptySet, bitsBuf);
 978             }
 979
 980             if (__CFCSetIsEqualBitmap(NULL, (const UInt32 *)bits)) {
 981                 if (!__CFCSetAnnexIsInverted(nonEmptySet)) return true;
 982             } else {
 983                 return false;
 984             }
 985
 986             // Annex set has to be CFRangeMake(0x10000, 0xfffff)
 987             for (idx = 1;idx < MAX_ANNEX_PLANE;idx++) {
 988                 if (__CFCSetIsBitmap(nonEmptySet)) {
 989                     if (!__CFCSetIsEqualBitmap((__CFCSetAnnexIsInverted(nonEmptySet) ? NULL : (const UInt32 *)-1), (const UInt32 *)bitsBuf)) return false;
 990                 } else {
 991                     __CFCSetGetBitmap(__CFCSetGetAnnexPlaneCharacterSetNoAlloc(nonEmptySet, idx), bitsBuf);
 992                     if (!__CFCSetIsEqualBitmap((const UInt32 *)-1, (const UInt32 *)bitsBuf)) return false;
 993                 }
 994             }
 995             return true;
 996         }
 997     }
 998
 999     if (__CFCSetIsBuiltin(cf1) || __CFCSetIsBuiltin(cf2)) {
1000         CFCharacterSetRef builtinSet = (__CFCSetIsBuiltin(cf1) ? cf1 : cf2);
1001         CFCharacterSetRef nonBuiltinSet = (builtinSet == cf1 ? cf2 : cf1);
1002
1003
1004         if (__CFCSetIsRange(nonBuiltinSet)) {
1005             UTF32Char firstChar = __CFCSetRangeFirstChar(nonBuiltinSet);
1006             UTF32Char lastChar = (firstChar + __CFCSetRangeLength(nonBuiltinSet) - 1);
1007             uint8_t firstPlane = (firstChar >> 16) & 0xFF;
1008             uint8_t lastPlane = (lastChar >> 16) & 0xFF;
1009             uint8_t result;
1010
1011             for (idx = 0;idx < MAX_ANNEX_PLANE;idx++) {
1012                 result = CFUniCharGetBitmapForPlane(__CFCSetBuiltinType(builtinSet), idx, bitsBuf, isInvertStateIdentical);
1013
1014                 if (idx < firstPlane || idx > lastPlane) {
1015                     if (result == kCFUniCharBitmapAll) {
1016                         return false;
1017                     } else if (result == kCFUniCharBitmapFilled) {
1018                         if (!__CFCSetIsEqualBitmap(NULL, (const UInt32 *)bitsBuf)) return false;
1019                     }
1020                 } else if (idx > firstPlane && idx < lastPlane) {
1021                     if (result == kCFUniCharBitmapEmpty) {
1022                         return false;
1023                     } else if (result == kCFUniCharBitmapFilled) {
1024                         if (!__CFCSetIsEqualBitmap((const UInt32 *)-1, (const UInt32 *)bitsBuf)) return false;
1025                     }
1026                 } else {
1027                     if (result == kCFUniCharBitmapEmpty) {
1028                         return false;
1029                     } else if (result == kCFUniCharBitmapAll) {
1030                         if (idx == firstPlane) {
1031                             if (((firstChar & 0xFFFF) != 0) || (firstPlane == lastPlane && ((lastChar & 0xFFFF) != 0xFFFF))) return false;
1032                         } else {
1033                             if (((lastChar & 0xFFFF) != 0xFFFF) || (firstPlane == lastPlane && ((firstChar & 0xFFFF) != 0))) return false;
1034                         }
1035                     } else {
1036                         if (idx == firstPlane) {
1037                             if (!__CFCSetIsBitmapEqualToRange((const UInt32 *)bitsBuf, firstChar & 0xFFFF, (firstPlane == lastPlane ? lastChar & 0xFFFF : 0xFFFF), false)) return false;
1038                         } else {
1039                             if (!__CFCSetIsBitmapEqualToRange((const UInt32 *)bitsBuf, (firstPlane == lastPlane ? firstChar & 0xFFFF : 0), lastChar & 0xFFFF, false)) return false;
1040                         }
1041                     }
1042                 }
1043             }
1044             return true;
1045         } else  {
1046 #if __MACOS8__
1047             uint8_t *bitsBuf2 = NULL;
1048 #else __MACOS8__
1049             uint8_t bitsBuf2[__kCFBitmapSize];
1050 #endif __MACOS8__
1051             uint8_t result;
1052
1053             result = CFUniCharGetBitmapForPlane(__CFCSetBuiltinType(builtinSet), 0, bitsBuf, __CFCSetIsInverted(builtinSet));
1054             if (result == kCFUniCharBitmapFilled) {
1055                 if (__CFCSetIsBitmap(nonBuiltinSet)) {
1056                     if (!__CFCSetIsEqualBitmap((const UInt32 *)bitsBuf, (const UInt32 *)__CFCSetBitmapBits(nonBuiltinSet))) return false;
1057                 } else {
1058 #if __MACOS8__
1059                     bitsBuf2 = CFAllocatorAllocate(CFGetAllocator(nonBuiltinSet), __kCFBitmapSize, 0);
1060 #endif __MACOS8__
1061
1062                     __CFCSetGetBitmap(nonBuiltinSet, bitsBuf2);
1063                     if (!__CFCSetIsEqualBitmap((const UInt32 *)bitsBuf, (const UInt32 *)bitsBuf2)) {
1064 #if __MACOS8__
1065                         CFAllocatorDeallocate(CFGetAllocator(nonBuiltinSet), bitsBuf2);
1066 #endif __MACOS8__
1067                         return false;
1068                     }
1069                 }
1070             } else {
1071                 if (__CFCSetIsBitmap(nonBuiltinSet)) {
1072                     if (!__CFCSetIsEqualBitmap((result == kCFUniCharBitmapAll ? (const UInt32*)-1 : NULL), (const UInt32 *)__CFCSetBitmapBits(nonBuiltinSet))) return false;
1073                 } else {
1074                     __CFCSetGetBitmap(nonBuiltinSet, bitsBuf);
1075                     if (!__CFCSetIsEqualBitmap((result == kCFUniCharBitmapAll ? (const UInt32*)-1: NULL), (const UInt32 *)bitsBuf)) return false;
1076                 }
1077             }
1078
1079             isInvertStateIdentical = (__CFCSetIsInverted(builtinSet) == __CFCSetAnnexIsInverted(nonBuiltinSet) ? true : false);
1080
1081             for (idx = 1;idx < MAX_ANNEX_PLANE;idx++) {
1082                 result = CFUniCharGetBitmapForPlane(__CFCSetBuiltinType(builtinSet), idx, bitsBuf, !isInvertStateIdentical);
1083                 subSet1 = __CFCSetGetAnnexPlaneCharacterSetNoAlloc(nonBuiltinSet, idx);
1084
1085                 if (result == kCFUniCharBitmapFilled) {
1086                     if (NULL == subSet1) {
1087 #if __MACOS8__
1088                         if (bitsBuf2) CFAllocatorDeallocate(CFGetAllocator(nonBuiltinSet), bitsBuf2);
1089 #endif __MACOS8__
1090                         return false;
1091                     } else if (__CFCSetIsBitmap(subSet1)) {
1092                         if (!__CFCSetIsEqualBitmap((const UInt32*)bitsBuf, (const UInt32*)__CFCSetBitmapBits(subSet1))) {
1093 #if __MACOS8__
1094                             if (bitsBuf2) CFAllocatorDeallocate(CFGetAllocator(nonBuiltinSet), bitsBuf2);
1095 #endif __MACOS8__
1096                             return false;
1097                         }
1098                     } else {
1099 #if __MACOS8__
1100                         if (NULL == bitsBuf2) bitsBuf2 = CFAllocatorAllocate(CFGetAllocator(nonBuiltinSet), __kCFBitmapSize, 0);
1101 #endif __MACOS8__
1102
1103                         __CFCSetGetBitmap(subSet1, bitsBuf2);
1104                         if (!__CFCSetIsEqualBitmap((const UInt32*)bitsBuf, (const UInt32*)bitsBuf2)) {
1105 #if __MACOS8__
1106                             CFAllocatorDeallocate(CFGetAllocator(nonBuiltinSet), bitsBuf2);
1107 #endif __MACOS8__
1108                             return false;
1109                         }
1110                     }
1111                 } else {
1112                     if (NULL == subSet1) {
1113                         if (result == kCFUniCharBitmapAll) {
1114 #if __MACOS8__
1115                             if (bitsBuf2) CFAllocatorDeallocate(CFGetAllocator(nonBuiltinSet), bitsBuf2);
1116 #endif __MACOS8__
1117                             return false;
1118                         }
1119                     } else if (__CFCSetIsBitmap(subSet1)) {
1120                         if (!__CFCSetIsEqualBitmap((result == kCFUniCharBitmapAll ? (const UInt32*)-1: NULL), (const UInt32*)__CFCSetBitmapBits(subSet1))) {
1121 #if __MACOS8__
1122                             if (bitsBuf2) CFAllocatorDeallocate(CFGetAllocator(nonBuiltinSet), bitsBuf2);
1123 #endif __MACOS8__
1124                             return false;
1125                         }
1126                     } else {
1127                         __CFCSetGetBitmap(subSet1, bitsBuf);
1128                         if (!__CFCSetIsEqualBitmap((result == kCFUniCharBitmapAll ? (const UInt32*)-1: NULL), (const UInt32*)bitsBuf)) {
1129 #if __MACOS8__
1130                             if (bitsBuf2) CFAllocatorDeallocate(CFGetAllocator(nonBuiltinSet), bitsBuf2);
1131 #endif __MACOS8__
1132                             return false;
1133                         }
1134                     }
1135                 }
1136             }
1137 #if __MACOS8__
1138             if (bitsBuf2) CFAllocatorDeallocate(CFGetAllocator(nonBuiltinSet), bitsBuf2);
1139 #endif __MACOS8__
1140             return true;
1141         }
1142     }
1143
1144     if (__CFCSetIsRange(cf1) || __CFCSetIsRange(cf2)) {
1145         CFCharacterSetRef rangeSet = (__CFCSetIsRange(cf1) ? cf1 : cf2);
1146         CFCharacterSetRef nonRangeSet = (rangeSet == cf1 ? cf2 : cf1);
1147         UTF32Char firstChar = __CFCSetRangeFirstChar(rangeSet);
1148         UTF32Char lastChar = (firstChar + __CFCSetRangeLength(rangeSet) - 1);
1149         uint8_t firstPlane = (firstChar >> 16) & 0xFF;
1150         uint8_t lastPlane = (lastChar >> 16) & 0xFF;
1151         Boolean isRangeSetInverted = __CFCSetIsInverted(rangeSet);
1152
1153         if (__CFCSetIsBitmap(nonRangeSet)) {
1154             bits = __CFCSetBitmapBits(nonRangeSet);
1155         } else {
1156             bits = bitsBuf;
1157             __CFCSetGetBitmap(nonRangeSet, bitsBuf);
1158         }
1159         if (firstPlane == 0) {
1160             if (!__CFCSetIsBitmapEqualToRange((const UInt32*)bits, firstChar, (lastPlane == 0 ? lastChar : 0xFFFF), isRangeSetInverted)) return false;
1161             firstPlane = 1;
1162             firstChar = 0;
1163         } else {
1164             if (!__CFCSetIsEqualBitmap((const UInt32*)bits, (isRangeSetInverted ? (const UInt32 *)-1 : NULL))) return false;
1165             firstChar &= 0xFFFF;
1166         }
1167
1168         lastChar &= 0xFFFF;
1169
1170         isAnnexInvertStateIdentical = (isRangeSetInverted == __CFCSetAnnexIsInverted(nonRangeSet) ? true : false);
1171
1172         for (idx = 1;idx < MAX_ANNEX_PLANE;idx++) {
1173             subSet1 = __CFCSetGetAnnexPlaneCharacterSetNoAlloc(nonRangeSet, idx);
1174             if (NULL == subSet1) {
1175                 if (idx < firstPlane || idx > lastPlane) {
1176                     if (!isAnnexInvertStateIdentical) return false;
1177                 } else if (idx > firstPlane && idx < lastPlane) {
1178                     if (isAnnexInvertStateIdentical) return false;
1179                 } else if (idx == firstPlane) {
1180                     if (isAnnexInvertStateIdentical || firstChar || (idx == lastPlane && lastChar != 0xFFFF)) return false;
1181                 } else if (idx == lastPlane) {
1182                     if (isAnnexInvertStateIdentical || (idx == firstPlane && firstChar) || (lastChar != 0xFFFF)) return false;
1183                 }
1184             } else {
1185                 if (__CFCSetIsBitmap(subSet1)) {
1186                     bits = __CFCSetBitmapBits(subSet1);
1187                 } else {
1188                     __CFCSetGetBitmap(subSet1, bitsBuf);
1189                     bits = bitsBuf;
1190                 }
1191
1192                 if (idx < firstPlane || idx > lastPlane) {
1193                     if (!__CFCSetIsEqualBitmap((const UInt32*)bits, (isAnnexInvertStateIdentical ? NULL : (const UInt32 *)-1))) return false;
1194                 } else if (idx > firstPlane && idx < lastPlane) {
1195                     if (!__CFCSetIsEqualBitmap((const UInt32*)bits, (isAnnexInvertStateIdentical ? (const UInt32 *)-1 : NULL))) return false;
1196                 } else if (idx == firstPlane) {
1197                     if (!__CFCSetIsBitmapEqualToRange((const UInt32*)bits, firstChar, (idx == lastPlane ? lastChar : 0xFFFF), !isAnnexInvertStateIdentical)) return false;
1198                 } else if (idx == lastPlane) {
1199                     if (!__CFCSetIsBitmapEqualToRange((const UInt32*)bits, (idx == firstPlane ? firstChar : 0), lastChar, !isAnnexInvertStateIdentical)) return false;
1200                 }
1201             }
1202         }
1203         return true;
1204     }
1205
1206     isBitmap1 = __CFCSetIsBitmap(cf1);
1207     isBitmap2 = __CFCSetIsBitmap(cf2);
1208
1209     if (isBitmap1 && isBitmap2) {
1210         if (!__CFCSetIsEqualBitmap((const UInt32*)__CFCSetBitmapBits(cf1), (const UInt32*)__CFCSetBitmapBits(cf2))) return false;
1211     } else if (!isBitmap1 && !isBitmap2) {
1212 #if __MACOS8__
1213         uint8_t *bitsBuf2 = (uint8_t *)CFAllocatorAllocate(NULL, __kCFBitmapSize, 0);
1214 #else __MACOS8__
1215         uint8_t bitsBuf2[__kCFBitmapSize];
1216 #endif __MACOS8__
1217
1218         __CFCSetGetBitmap(cf1, bitsBuf);
1219         __CFCSetGetBitmap(cf2, bitsBuf2);
1220
1221         if (!__CFCSetIsEqualBitmap((const UInt32*)bitsBuf, (const UInt32*)bitsBuf2)) {
1222 #if __MACOS8__
1223             CFAllocatorDeallocate(NULL, bitsBuf2);
1224 #endif __MACOS8__
1225             return false;
1226         }
1227 #if __MACOS8__
1228         CFAllocatorDeallocate(NULL, bitsBuf2);
1229 #endif __MACOS8__
1230     } else {
1231         if (isBitmap2) {
1232             CFCharacterSetRef tmp = cf2;
1233             cf2 = cf1;
1234             cf1 = tmp;
1235         }
1236
1237         __CFCSetGetBitmap(cf2, bitsBuf);
1238
1239         if (!__CFCSetIsEqualBitmap((const UInt32*)__CFCSetBitmapBits(cf1), (const UInt32*)bitsBuf)) return false;
1240     }
1241     return __CFCSetIsEqualAnnex(cf1, cf2);
1242 }
1243
1244 static CFHashCode __CFCharacterSetHash(CFTypeRef cf) {
1245     if (!__CFCSetHasHashValue(cf)) {
1246         if (__CFCSetIsEmpty(cf)) {
1247             ((CFMutableCharacterSetRef)cf)->_hashValue = (__CFCSetIsInverted(cf) ? 0xFFFFFFFF : 0);
1248         } else if (__CFCSetIsBitmap(cf)) {
1249             ((CFMutableCharacterSetRef)cf)->_hashValue = CFHashBytes(__CFCSetBitmapBits(cf), __kCFBitmapSize);
1250         } else {
1251             uint8_t bitsBuf[__kCFBitmapSize];
1252             __CFCSetGetBitmap(cf, bitsBuf);
1253             ((CFMutableCharacterSetRef)cf)->_hashValue = CFHashBytes(bitsBuf, __kCFBitmapSize);
1254         }
1255         __CFCSetPutHasHashValue((CFMutableCharacterSetRef)cf, true);
1256     }
1257     return ((CFCharacterSetRef)cf)->_hashValue;
1258 }
1259
1260 static CFStringRef  __CFCharacterSetCopyDescription(CFTypeRef cf) {
1261     CFMutableStringRef string;
1262     CFIndex idx;
1263     CFIndex length;
1264
1265     if (__CFCSetIsEmpty(cf)) {
1266         return (__CFCSetIsInverted(cf) ? CFRetain(CFSTR("<CFCharacterSet All>")) : CFRetain(CFSTR("<CFCharacterSet Empty>")));
1267     }
1268
1269     switch (__CFCSetClassType(cf)) {
1270         case __kCFCharSetClassBuiltin:
1271             switch (__CFCSetBuiltinType(cf)) {
1272                 case kCFCharacterSetControl: return CFRetain(__kCFCSetNameControl);
1273                 case kCFCharacterSetWhitespace : return CFRetain(__kCFCSetNameWhitespace);
1274                 case kCFCharacterSetWhitespaceAndNewline: return CFRetain(__kCFCSetNameWhitespaceAndNewline);
1275                 case kCFCharacterSetDecimalDigit: return CFRetain(__kCFCSetNameDecimalDigit);
1276                 case kCFCharacterSetLetter: return CFRetain(__kCFCSetNameLetter);
1277                 case kCFCharacterSetLowercaseLetter: return CFRetain(__kCFCSetNameLowercaseLetter);
1278                 case kCFCharacterSetUppercaseLetter: return CFRetain(__kCFCSetNameUppercaseLetter);
1279                 case kCFCharacterSetNonBase: return CFRetain(__kCFCSetNameNonBase);
1280                 case kCFCharacterSetDecomposable: return CFRetain(__kCFCSetNameDecomposable);
1281                 case kCFCharacterSetAlphaNumeric: return CFRetain(__kCFCSetNameAlphaNumeric);
1282                 case kCFCharacterSetPunctuation: return CFRetain(__kCFCSetNamePunctuation);
1283                 case kCFCharacterSetIllegal: return CFRetain(__kCFCSetNameIllegal);
1284                 case kCFCharacterSetCapitalizedLetter: return CFRetain(__kCFCSetNameCapitalizedLetter);
1285                 case kCFCharacterSetSymbol: return CFRetain(__kCFCSetNameSymbol);
1286             }
1287             break;
1288
1289         case __kCFCharSetClassRange:
1290             return CFStringCreateWithFormat(CFGetAllocator(cf), NULL, CFSTR("<CFCharacterSet Range(%d, %d)>"), __CFCSetRangeFirstChar(cf), __CFCSetRangeLength(cf));
1291
1292         case __kCFCharSetClassString:
1293             length = __CFCSetStringLength(cf);
1294             string = CFStringCreateMutable(CFGetAllocator(cf), CFStringGetLength(__kCFCSetNameStringTypeFormat) + 7 * length + 2); // length of__kCFCSetNameStringTypeFormat + "U+XXXX "(7) * length + ")>"(2)
1295             CFStringAppend(string, __kCFCSetNameStringTypeFormat);
1296             for (idx = 0;idx < length;idx++) {
1297                 CFStringAppendFormat(string, NULL, CFSTR("%sU+%04X"), (idx > 0 ? " " : ""), (UInt32)((__CFCSetStringBuffer(cf))[idx]));
1298             }
1299             CFStringAppend(string, CFSTR(")>"));
1300             return string;
1301
1302         case __kCFCharSetClassBitmap:
1303         case __kCFCharSetClassCompactBitmap:
1304             return CFRetain(CFSTR("<CFCharacterSet Bitmap>")); // ??? Should generate description for 8k bitmap ?
1305     }
1306     CFAssert1(0, __kCFLogAssertion, "%s: Internal inconsistency error: unknown character set type", __PRETTY_FUNCTION__); // We should never come here
1307     return NULL;
1308 }
1309
1310 static void __CFCharacterSetDeallocate(CFTypeRef cf) {
1311     CFAllocatorRef allocator = CFGetAllocator(cf);
1312
1313     if (__CFCSetIsBuiltin(cf) && !__CFCSetIsMutable(cf) && !__CFCSetIsInverted(cf)) {
1314         CFCharacterSetRef sharedSet = CFCharacterSetGetPredefined(__CFCSetBuiltinType(cf));
1315         if (sharedSet == cf) { // We're trying to dealloc the builtin set
1316             CFAssert1(0, __kCFLogAssertion, "%s: Trying to deallocate predefined set", __PRETTY_FUNCTION__);
1317             return; // We never deallocate builtin set
1318         }
1319     }
1320
1321     if (__CFCSetIsString(cf) && __CFCSetStringBuffer(cf)) CFAllocatorDeallocate(allocator, __CFCSetStringBuffer(cf));
1322     else if (__CFCSetIsBitmap(cf) && __CFCSetBitmapBits(cf)) CFAllocatorDeallocate(allocator, __CFCSetBitmapBits(cf));
1323     else if (__CFCSetIsCompactBitmap(cf) && __CFCSetCompactBitmapBits(cf)) CFAllocatorDeallocate(allocator, __CFCSetCompactBitmapBits(cf));
1324     __CFCSetDeallocateAnnexPlane(cf);
1325 }
1326
1327 static CFTypeID __kCFCharacterSetTypeID = _kCFRuntimeNotATypeID;
1328
1329 static const CFRuntimeClass __CFCharacterSetClass = {
1330     0,
1331     "CFCharacterSet",
1332     NULL,      // init
1333     NULL,      // copy
1334     __CFCharacterSetDeallocate,
1335     __CFCharacterSetEqual,
1336     __CFCharacterSetHash,
1337     NULL,      //
1338     __CFCharacterSetCopyDescription
1339 };
1340
1341 static bool __CFCheckForExapendedSet = false;
1342
1343 __private_extern__ void __CFCharacterSetInitialize(void) {
1344     const char *checkForExpandedSet = getenv("__CF_DEBUG_EXPANDED_SET");
1345
1346     __kCFCharacterSetTypeID = _CFRuntimeRegisterClass(&__CFCharacterSetClass);
1347
1348     if (checkForExpandedSet && (*checkForExpandedSet == 'Y')) __CFCheckForExapendedSet = true;
1349 }
1350
1351 /* Public functions
1352 */
1353 #if defined(__MACOS8__)
1354 CFTypeID CFCharacterSetTypeID(void) {
1355 #ifdef DEBUG
1356     CFLog(__kCFLogAssertion, CFSTR("CFCharacterSetTypeID should be CFCharacterSetGetTypeID"));
1357 #endif /* DEBUG */
1358     return __kCFCharacterSetTypeID;
1359 }
1360 #endif /* __MACOS8__ */
1361
1362 CFTypeID CFCharacterSetGetTypeID(void) {
1363     return __kCFCharacterSetTypeID;
1364 }
1365
1366 /*** CharacterSet creation ***/
1367 /* Functions to create basic immutable characterset.
1368 */
1369 CFCharacterSetRef CFCharacterSetGetPredefined(CFCharacterSetPredefinedSet theSetIdentifier) {
1370     CFMutableCharacterSetRef cset;
1371
1372     __CFCSetValidateBuiltinType(theSetIdentifier, __PRETTY_FUNCTION__);
1373
1374     if (__CFBuiltinSets && __CFBuiltinSets[theSetIdentifier - 1]) return __CFBuiltinSets[theSetIdentifier - 1];
1375
1376     if (!(cset = __CFCSetGenericCreate(kCFAllocatorSystemDefault, __kCFCharSetClassBuiltin))) return NULL;
1377     __CFCSetPutBuiltinType(cset, theSetIdentifier);
1378
1379     if (!__CFBuiltinSets) {
1380         __CFSpinLock(&__CFCharacterSetLock);
1381         __CFBuiltinSets = (CFCharacterSetRef *)CFAllocatorAllocate(CFRetain(__CFGetDefaultAllocator()), sizeof(CFCharacterSetRef) * __kCFLastBuiltinSetID, 0);
1382         memset(__CFBuiltinSets, 0, sizeof(CFCharacterSetRef) * __kCFLastBuiltinSetID);
1383         __CFSpinUnlock(&__CFCharacterSetLock);
1384     }
1385
1386     __CFBuiltinSets[theSetIdentifier - 1] = cset;
1387
1388     return cset;
1389 }
1390
1391 CFCharacterSetRef CFCharacterSetCreateWithCharactersInRange(CFAllocatorRef allocator, CFRange theRange) {
1392     CFMutableCharacterSetRef cset;
1393
1394     __CFCSetValidateRange(theRange, __PRETTY_FUNCTION__);
1395
1396     if (theRange.length) {
1397         if (!(cset = __CFCSetGenericCreate(allocator, __kCFCharSetClassRange))) return NULL;
1398         __CFCSetPutRangeFirstChar(cset, theRange.location);
1399         __CFCSetPutRangeLength(cset, theRange.length);
1400     } else {
1401         if (!(cset = __CFCSetGenericCreate(allocator, __kCFCharSetClassBitmap))) return NULL;
1402         __CFCSetPutBitmapBits(cset, NULL);
1403         __CFCSetPutHasHashValue(cset, true); // _hashValue is 0
1404     }
1405
1406     return cset;
1407 }
1408
1409 static int chcompar(const void *a, const void *b) {
1410     return -(int)(*(UniChar *)b - *(UniChar *)a);
1411 }
1412
1413 CFCharacterSetRef CFCharacterSetCreateWithCharactersInString(CFAllocatorRef allocator, CFStringRef theString) {
1414     CFIndex length;
1415
1416     length = CFStringGetLength(theString);
1417     if (length < __kCFStringCharSetMax) {
1418         CFMutableCharacterSetRef cset;
1419
1420         if (!(cset = __CFCSetGenericCreate(allocator, __kCFCharSetClassString))) return NULL;
1421         __CFCSetPutStringBuffer(cset, CFAllocatorAllocate(CFGetAllocator(cset), __kCFStringCharSetMax * sizeof(UniChar), 0));
1422         __CFCSetPutStringLength(cset, length);
1423         CFStringGetCharacters(theString, CFRangeMake(0, length), __CFCSetStringBuffer(cset));
1424         qsort(__CFCSetStringBuffer(cset), length, sizeof(UniChar), chcompar);
1425         if (!length) __CFCSetPutHasHashValue(cset, true); // _hashValue is 0
1426         return cset;
1427     } else {
1428         CFMutableCharacterSetRef mcset = CFCharacterSetCreateMutable(allocator);
1429         CFCharacterSetAddCharactersInString(mcset, theString);
1430         __CFCSetMakeCompact(mcset);
1431         __CFCSetPutIsMutable(mcset, false);
1432         return mcset;
1433     }
1434 }
1435
1436 #if defined(__MACOS8__)
1437 CFCharacterSetRef CFCharacterSetCreateWithBitmapReresentation(CFAllocatorRef allocator, CFDataRef theData) {
1438 #ifdef DEBUG
1439     CFLog(__kCFLogAssertion, CFSTR("CFCharacterSetCreateWithBitmapReresentation should be CFCharacterSetCreateWithBitmapRepresentation"));
1440 #endif /* DEBUG */
1441     return CFCharacterSetCreateWithBitmapRepresentation(allocator, theData);
1442 }
1443 #endif /* __MACOS8__ */
1444
1445 CFCharacterSetRef CFCharacterSetCreateWithBitmapRepresentation(CFAllocatorRef allocator, CFDataRef theData) {
1446     CFMutableCharacterSetRef cset;
1447     CFIndex length;
1448
1449     if (!(cset = __CFCSetGenericCreate(allocator, __kCFCharSetClassBitmap))) return NULL;
1450
1451     if (theData && (length = CFDataGetLength(theData)) > 0) {
1452         uint8_t *bitmap;
1453         uint8_t *cBitmap;
1454
1455         if (length < __kCFBitmapSize) {
1456             bitmap = (uint8_t *)CFAllocatorAllocate(allocator, __kCFBitmapSize, 0);
1457             memmove(bitmap, CFDataGetBytePtr(theData), length);
1458             memset(bitmap + length, 0, __kCFBitmapSize - length);
1459
1460             cBitmap = __CFCreateCompactBitmap(allocator, bitmap);
1461
1462             if (cBitmap == NULL) {
1463                 __CFCSetPutBitmapBits(cset, bitmap);
1464             } else {
1465                 CFAllocatorDeallocate(allocator, bitmap);
1466                 __CFCSetPutCompactBitmapBits(cset, cBitmap);
1467                 __CFCSetPutClassType(cset, __kCFCharSetClassCompactBitmap);
1468             }
1469         } else {
1470             cBitmap = __CFCreateCompactBitmap(allocator, CFDataGetBytePtr(theData));
1471
1472             if (cBitmap == NULL) {
1473                 bitmap = (uint8_t *)CFAllocatorAllocate(allocator, __kCFBitmapSize, 0);
1474                 memmove(bitmap, CFDataGetBytePtr(theData), __kCFBitmapSize);
1475
1476                 __CFCSetPutBitmapBits(cset, bitmap);
1477             } else {
1478                 __CFCSetPutCompactBitmapBits(cset, cBitmap);
1479                 __CFCSetPutClassType(cset, __kCFCharSetClassCompactBitmap);
1480             }
1481
1482             if (length > __kCFBitmapSize) {
1483                 CFMutableCharacterSetRef annexSet;
1484                 const char *bytes = CFDataGetBytePtr(theData) + __kCFBitmapSize;
1485
1486                 length -= __kCFBitmapSize;
1487
1488                 while (length > 1) {
1489                     annexSet = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSet(cset, *(bytes++));
1490                     --length; // Decrement the plane no byte
1491
1492                     if (length < __kCFBitmapSize) {
1493                         bitmap = (uint8_t *)CFAllocatorAllocate(allocator, __kCFBitmapSize, 0);
1494                         memmove(bitmap, bytes, length);
1495                         memset(bitmap + length, 0, __kCFBitmapSize - length);
1496
1497                         cBitmap = __CFCreateCompactBitmap(allocator, bitmap);
1498
1499                         if (cBitmap == NULL) {
1500                             __CFCSetPutBitmapBits(annexSet, bitmap);
1501                         } else {
1502                             CFAllocatorDeallocate(allocator, bitmap);
1503                             __CFCSetPutCompactBitmapBits(annexSet, cBitmap);
1504                             __CFCSetPutClassType(annexSet, __kCFCharSetClassCompactBitmap);
1505                         }
1506                     } else {
1507                         cBitmap = __CFCreateCompactBitmap(allocator, bytes);
1508
1509                         if (cBitmap == NULL) {
1510                             bitmap = (uint8_t *)CFAllocatorAllocate(allocator, __kCFBitmapSize, 0);
1511                             memmove(bitmap, bytes, __kCFBitmapSize);
1512
1513                             __CFCSetPutBitmapBits(annexSet, bitmap);
1514                         } else {
1515                             __CFCSetPutCompactBitmapBits(annexSet, cBitmap);
1516                             __CFCSetPutClassType(annexSet, __kCFCharSetClassCompactBitmap);
1517                         }
1518                     }
1519                     length -= __kCFBitmapSize;
1520                     bytes += __kCFBitmapSize;
1521                 }
1522             }
1523         }
1524     } else {
1525         __CFCSetPutBitmapBits(cset, NULL);
1526         __CFCSetPutHasHashValue(cset, true); // Hash value is 0
1527     }
1528
1529     return cset;
1530 }
1531
1532 CFCharacterSetRef CFCharacterSetCreateInvertedSet(CFAllocatorRef alloc, CFCharacterSetRef theSet) {
1533     CFMutableCharacterSetRef cset;
1534
1535     CF_OBJC_FUNCDISPATCH0(__kCFCharacterSetTypeID, CFCharacterSetRef , theSet, "invertedSet");
1536
1537     cset = CFCharacterSetCreateMutableCopy(alloc, theSet);
1538     CFCharacterSetInvert(cset);
1539     __CFCSetPutIsMutable(cset, false);
1540
1541     return cset;
1542 }
1543
1544 /* Functions to create mutable characterset.
1545 */
1546 CFMutableCharacterSetRef CFCharacterSetCreateMutable(CFAllocatorRef allocator) {
1547     CFMutableCharacterSetRef cset;
1548
1549     if (!(cset = __CFCSetGenericCreate(allocator, __kCFCharSetClassBitmap| __kCFCharSetIsMutable))) return NULL;
1550     __CFCSetPutBitmapBits(cset, NULL);
1551     __CFCSetPutHasHashValue(cset, true); // Hash value is 0
1552
1553     return cset;
1554 }
1555
1556 CFMutableCharacterSetRef __CFCharacterSetCreateCopy(CFAllocatorRef alloc, CFCharacterSetRef theSet, bool isMutable) {
1557     CFMutableCharacterSetRef cset;
1558
1559     CF_OBJC_FUNCDISPATCH0(__kCFCharacterSetTypeID, CFMutableCharacterSetRef , theSet, "mutableCopy");
1560
1561     __CFGenericValidateType(theSet, __kCFCharacterSetTypeID);
1562
1563     if (!isMutable && !__CFCSetIsMutable(theSet)) {
1564         return (CFMutableCharacterSetRef)CFRetain(theSet);
1565     }
1566
1567     cset = CFCharacterSetCreateMutable(alloc);
1568
1569     __CFCSetPutClassType(cset, __CFCSetClassType(theSet));
1570     __CFCSetPutHasHashValue(cset, __CFCSetHasHashValue(theSet));
1571     __CFCSetPutIsInverted(cset, __CFCSetIsInverted(theSet));
1572     cset->_hashValue = theSet->_hashValue;
1573
1574     switch (__CFCSetClassType(theSet)) {
1575         case __kCFCharSetClassBuiltin:
1576             __CFCSetPutBuiltinType(cset, __CFCSetBuiltinType(theSet));
1577             break;
1578
1579         case __kCFCharSetClassRange:
1580             __CFCSetPutRangeFirstChar(cset, __CFCSetRangeFirstChar(theSet));
1581             __CFCSetPutRangeLength(cset, __CFCSetRangeLength(theSet));
1582             break;
1583
1584         case __kCFCharSetClassString:
1585             __CFCSetPutStringBuffer(cset, CFAllocatorAllocate(alloc, __kCFStringCharSetMax * sizeof(UniChar), 0));
1586             __CFCSetPutStringLength(cset, __CFCSetStringLength(theSet));
1587             memmove(__CFCSetStringBuffer(cset), __CFCSetStringBuffer(theSet), __CFCSetStringLength(theSet) * sizeof(UniChar));
1588             break;
1589
1590         case __kCFCharSetClassBitmap:
1591             if (__CFCSetBitmapBits(theSet)) {
1592                 uint8_t * bitmap = (isMutable ? NULL : __CFCreateCompactBitmap(alloc, __CFCSetBitmapBits(theSet)));
1593
1594                 if (bitmap == NULL) {
1595                     bitmap = (uint8_t *)CFAllocatorAllocate(alloc, sizeof(uint8_t) * __kCFBitmapSize, 0);
1596                     memmove(bitmap, __CFCSetBitmapBits(theSet), __kCFBitmapSize);
1597                     __CFCSetPutBitmapBits(cset, bitmap);
1598                 } else {
1599                     __CFCSetPutCompactBitmapBits(cset, bitmap);
1600                     __CFCSetPutClassType(cset, __kCFCharSetClassCompactBitmap);
1601                 }
1602             } else {
1603                 __CFCSetPutBitmapBits(cset, NULL);
1604             }
1605             break;
1606
1607         case __kCFCharSetClassCompactBitmap: {
1608             const uint8_t *compactBitmap = __CFCSetCompactBitmapBits(theSet);
1609
1610             if (compactBitmap) {
1611                 uint32_t size = __CFCSetGetCompactBitmapSize(compactBitmap);
1612                 uint8_t *newBitmap = (uint8_t *)CFAllocatorAllocate(alloc, size, 0);
1613
1614                 memmove(newBitmap, compactBitmap, size);
1615                 __CFCSetPutCompactBitmapBits(cset, newBitmap);
1616             }
1617         }
1618             break;
1619
1620         default:
1621             CFAssert1(0, __kCFLogAssertion, "%s: Internal inconsistency error: unknown character set type", __PRETTY_FUNCTION__); // We should never come here
1622     }
1623     if (__CFCSetHasNonBMPPlane(theSet)) {
1624         CFMutableCharacterSetRef annexPlane;
1625         int idx;
1626
1627         for (idx = 1;idx <= MAX_ANNEX_PLANE;idx++) {
1628             if ((annexPlane = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSetNoAlloc(theSet, idx))) {
1629                 annexPlane = __CFCharacterSetCreateCopy(alloc, annexPlane, isMutable);
1630                 __CFCSetPutCharacterSetToAnnexPlane(cset, annexPlane, idx);
1631                 CFRelease(annexPlane);
1632             }
1633         }
1634         __CFCSetAnnexSetIsInverted(cset, __CFCSetAnnexIsInverted(theSet));
1635     } else if (__CFCSetAnnexIsInverted(theSet)) {
1636         __CFCSetAllocateAnnexForPlane(cset, 0); // We need to alloc annex to invert
1637         __CFCSetAnnexSetIsInverted(cset, true);
1638     }
1639
1640     return cset;
1641 }
1642
1643 CFCharacterSetRef CFCharacterSetCreateCopy(CFAllocatorRef alloc, CFCharacterSetRef theSet) {
1644     return __CFCharacterSetCreateCopy(alloc, theSet, false);
1645 }
1646
1647 CFMutableCharacterSetRef CFCharacterSetCreateMutableCopy(CFAllocatorRef alloc, CFCharacterSetRef theSet) {
1648     return __CFCharacterSetCreateCopy(alloc, theSet, true);
1649 }
1650
1651 /*** Basic accessors ***/
1652 Boolean CFCharacterSetIsCharacterMember(CFCharacterSetRef theSet, UniChar theChar) {
1653     return CFCharacterSetIsLongCharacterMember(theSet, theChar);
1654 }
1655
1656 Boolean CFCharacterSetIsLongCharacterMember(CFCharacterSetRef theSet, UTF32Char theChar) {
1657     CFIndex length;
1658     UInt32 plane = (theChar >> 16);
1659     Boolean isAnnexInverted = false;
1660     Boolean isInverted;
1661     Boolean result = false;
1662
1663     CF_OBJC_FUNCDISPATCH1(__kCFCharacterSetTypeID, Boolean, theSet, "longCharacterIsMember:", theChar);
1664
1665     __CFGenericValidateType(theSet, __kCFCharacterSetTypeID);
1666
1667     if (plane) {
1668         CFCharacterSetRef annexPlane;
1669
1670         if (__CFCSetIsBuiltin(theSet)) {
1671             isInverted = __CFCSetIsInverted(theSet);
1672             return (CFUniCharIsMemberOf(theChar, __CFCSetBuiltinType(theSet)) ? !isInverted : isInverted);
1673         }
1674
1675         isAnnexInverted = __CFCSetAnnexIsInverted(theSet);
1676
1677         if ((annexPlane = __CFCSetGetAnnexPlaneCharacterSetNoAlloc(theSet, plane)) == NULL) {
1678             if (!__CFCSetHasNonBMPPlane(theSet) && __CFCSetIsRange(theSet)) {
1679                 isInverted = __CFCSetIsInverted(theSet);
1680                 length = __CFCSetRangeLength(theSet);
1681                 return (length && __CFCSetRangeFirstChar(theSet) <= theChar && theChar < __CFCSetRangeFirstChar(theSet) + length ? !isInverted : isInverted);
1682             } else {
1683                 return (isAnnexInverted ? true : false);
1684             }
1685         } else {
1686             theSet = annexPlane;
1687             theChar &= 0xFFFF;
1688         }
1689     }
1690
1691     isInverted = __CFCSetIsInverted(theSet);
1692
1693     switch (__CFCSetClassType(theSet)) {
1694         case __kCFCharSetClassBuiltin:
1695             result = (CFUniCharIsMemberOf(theChar, __CFCSetBuiltinType(theSet)) ? !isInverted : isInverted);
1696             break;
1697
1698         case __kCFCharSetClassRange:
1699             length = __CFCSetRangeLength(theSet);
1700             result = (length && __CFCSetRangeFirstChar(theSet) <= theChar && theChar < __CFCSetRangeFirstChar(theSet) + length ? !isInverted : isInverted);
1701             break;
1702
1703         case __kCFCharSetClassString:
1704             result = ((length = __CFCSetStringLength(theSet)) ? (__CFCSetBsearchUniChar(__CFCSetStringBuffer(theSet), length, theChar) ? !isInverted : isInverted) : isInverted);
1705             break;
1706
1707         case __kCFCharSetClassBitmap:
1708             result = (__CFCSetCompactBitmapBits(theSet) ? (__CFCSetIsMemberBitmap(__CFCSetBitmapBits(theSet), theChar) ? true : false) : isInverted);
1709             break;
1710
1711         case __kCFCharSetClassCompactBitmap:
1712             result = (__CFCSetCompactBitmapBits(theSet) ? (__CFCSetIsMemberInCompactBitmap(__CFCSetCompactBitmapBits(theSet), theChar) ? true : false) : isInverted);
1713             break;
1714
1715         default:
1716             CFAssert1(0, __kCFLogAssertion, "%s: Internal inconsistency error: unknown character set type", __PRETTY_FUNCTION__); // We should never come here
1717             return false; // To make compiler happy
1718     }
1719
1720     return (result ? !isAnnexInverted : isAnnexInverted);
1721 }
1722
1723 Boolean CFCharacterSetIsSurrogatePairMember(CFCharacterSetRef theSet, UniChar surrogateHigh, UniChar surrogateLow) {
1724     return CFCharacterSetIsLongCharacterMember(theSet, CFCharacterSetGetLongCharacterForSurrogatePair(surrogateHigh, surrogateLow));
1725 }
1726
1727
1728 static CFCharacterSetRef __CFCharacterSetGetExpandedSetForNSCharacterSet(const void *characterSet) {
1729     CF_OBJC_FUNCDISPATCH0(__kCFCharacterSetTypeID, CFCharacterSetRef , characterSet, "_expandedCFCharacterSet");
1730     return NULL;
1731 }
1732
1733 Boolean CFCharacterSetIsSupersetOfSet(CFCharacterSetRef theSet, CFCharacterSetRef theOtherSet) {
1734     CFMutableCharacterSetRef copy;
1735     CFCharacterSetRef expandedSet = NULL;
1736     CFCharacterSetRef expandedOtherSet = NULL;
1737     Boolean result;
1738
1739     if ((!CF_IS_OBJC(__kCFCharacterSetTypeID, theSet) || (expandedSet = __CFCharacterSetGetExpandedSetForNSCharacterSet(theSet))) && (!CF_IS_OBJC(__kCFCharacterSetTypeID, theOtherSet) || (expandedOtherSet = __CFCharacterSetGetExpandedSetForNSCharacterSet(theOtherSet)))) { // Really CF, we can do some trick here
1740         if (expandedSet) theSet = expandedSet;
1741         if (expandedOtherSet) theOtherSet = expandedOtherSet;
1742
1743         __CFGenericValidateType(theSet, __kCFCharacterSetTypeID);
1744         __CFGenericValidateType(theOtherSet, __kCFCharacterSetTypeID);
1745
1746         if (__CFCSetIsEmpty(theSet)) {
1747             if (__CFCSetIsInverted(theSet)) {
1748                 return TRUE; // Inverted empty set covers all range
1749             } else if (!__CFCSetIsEmpty(theOtherSet) || __CFCSetIsInverted(theOtherSet)) {
1750                 return FALSE;
1751             }
1752         } else if (__CFCSetIsEmpty(theOtherSet) && !__CFCSetIsInverted(theOtherSet)) {
1753             return TRUE;
1754         } else {
1755             if (__CFCSetIsBuiltin(theSet) || __CFCSetIsBuiltin(theOtherSet)) {
1756                 if (__CFCSetClassType(theSet) == __CFCSetClassType(theOtherSet) && __CFCSetBuiltinType(theSet) == __CFCSetBuiltinType(theOtherSet) && !__CFCSetIsInverted(theSet) && !__CFCSetIsInverted(theOtherSet)) return TRUE;
1757             } else if (__CFCSetIsRange(theSet) || __CFCSetIsRange(theOtherSet)) {
1758                 if (__CFCSetClassType(theSet) == __CFCSetClassType(theOtherSet)) {
1759                     if (__CFCSetIsInverted(theSet)) {
1760                         if (__CFCSetIsInverted(theOtherSet)) {
1761                             return (__CFCSetRangeFirstChar(theOtherSet) > __CFCSetRangeFirstChar(theSet) || (__CFCSetRangeFirstChar(theSet) + __CFCSetRangeLength(theSet)) > (__CFCSetRangeFirstChar(theOtherSet) + __CFCSetRangeLength(theOtherSet)) ? FALSE : TRUE);
1762                         } else {
1763                             return ((__CFCSetRangeFirstChar(theOtherSet) + __CFCSetRangeLength(theOtherSet)) <= __CFCSetRangeFirstChar(theSet) || (__CFCSetRangeFirstChar(theSet) + __CFCSetRangeLength(theSet)) <= __CFCSetRangeFirstChar(theOtherSet) ? TRUE : FALSE);
1764                         }
1765                     } else {
1766                         if (__CFCSetIsInverted(theOtherSet)) {
1767                             return ((__CFCSetRangeFirstChar(theSet) == 0 && __CFCSetRangeLength(theSet) == 0x110000) || (__CFCSetRangeFirstChar(theOtherSet) == 0 && (UInt32)__CFCSetRangeLength(theOtherSet) <= __CFCSetRangeFirstChar(theSet)) || ((__CFCSetRangeFirstChar(theSet) + __CFCSetRangeLength(theSet)) <= __CFCSetRangeFirstChar(theOtherSet) && (__CFCSetRangeFirstChar(theOtherSet) + __CFCSetRangeLength(theOtherSet)) == 0x110000) ? TRUE : FALSE);
1768                         } else {
1769                             return (__CFCSetRangeFirstChar(theOtherSet) < __CFCSetRangeFirstChar(theSet) || (__CFCSetRangeFirstChar(theSet) + __CFCSetRangeLength(theSet)) < (__CFCSetRangeFirstChar(theOtherSet) + __CFCSetRangeLength(theOtherSet)) ? FALSE : TRUE);
1770                         }
1771                     }
1772                 }
1773             } else {
1774                 UInt32 theSetAnnexMask = __CFCSetAnnexValidEntriesBitmap(theSet);
1775                 UInt32 theOtherSetAnnexMask = __CFCSetAnnexValidEntriesBitmap(theOtherSet);
1776                 Boolean isTheSetAnnexInverted = __CFCSetAnnexIsInverted(theSet);
1777                 Boolean isTheOtherSetAnnexInverted = __CFCSetAnnexIsInverted(theOtherSet);
1778                 uint8_t theSetBuffer[__kCFBitmapSize];
1779                 uint8_t theOtherSetBuffer[__kCFBitmapSize];
1780
1781                 // We mask plane 1 to plane 16
1782                 if (isTheSetAnnexInverted) theSetAnnexMask = (~theSetAnnexMask) & (0xFFFF < 1);
1783                 if (isTheOtherSetAnnexInverted) theOtherSetAnnexMask = (~theOtherSetAnnexMask) & (0xFFFF < 1);
1784
1785                 __CFCSetGetBitmap(theSet, theSetBuffer);
1786                 __CFCSetGetBitmap(theOtherSet, theOtherSetBuffer);
1787
1788                 if (!__CFCSetIsBitmapSupersetOfBitmap((const UInt32 *)theSetBuffer, (const UInt32 *)theOtherSetBuffer, FALSE, FALSE)) return FALSE;
1789
1790                 if (theOtherSetAnnexMask) {
1791                     CFCharacterSetRef theSetAnnex;
1792                     CFCharacterSetRef theOtherSetAnnex;
1793                     uint32_t idx;
1794
1795                     if ((theSetAnnexMask & theOtherSetAnnexMask) != theOtherSetAnnexMask) return FALSE;
1796
1797                     for (idx = 1;idx <= 16;idx++) {
1798                         theSetAnnex = __CFCSetGetAnnexPlaneCharacterSetNoAlloc(theSet, idx);
1799                         if (NULL == theSetAnnex) continue; // This case is already handled by the mask above
1800
1801                         theOtherSetAnnex = __CFCSetGetAnnexPlaneCharacterSetNoAlloc(theOtherSet, idx);
1802
1803                         if (NULL == theOtherSetAnnex) {
1804                             if (isTheOtherSetAnnexInverted) {
1805                                 __CFCSetGetBitmap(theSetAnnex, theSetBuffer);
1806                                 if (!__CFCSetIsEqualBitmap((const UInt32 *)theSetBuffer, (isTheSetAnnexInverted ? NULL : (const UInt32 *)-1))) return FALSE;
1807                             }
1808                         } else {
1809                             __CFCSetGetBitmap(theSetAnnex, theSetBuffer);
1810                             __CFCSetGetBitmap(theOtherSetAnnex, theOtherSetBuffer);
1811                             if (!__CFCSetIsBitmapSupersetOfBitmap((const UInt32 *)theSetBuffer, (const UInt32 *)theOtherSetBuffer, isTheSetAnnexInverted, isTheOtherSetAnnexInverted)) return FALSE;
1812                         }
1813                     }
1814                 }
1815
1816                 return TRUE;
1817             }
1818         }
1819     }
1820
1821     copy = CFCharacterSetCreateMutableCopy(NULL, theSet);
1822     CFCharacterSetIntersect(copy, theOtherSet);
1823     result = __CFCharacterSetEqual(copy, theOtherSet);
1824     CFRelease(copy);
1825
1826     return result;
1827 }
1828
1829 Boolean CFCharacterSetHasMemberInPlane(CFCharacterSetRef theSet, CFIndex thePlane) {
1830     Boolean isInverted = __CFCSetIsInverted(theSet);
1831
1832     CF_OBJC_FUNCDISPATCH1(__kCFCharacterSetTypeID, Boolean, theSet, "hasMemberInPlane:", thePlane);
1833
1834     if (__CFCSetIsEmpty(theSet)) {
1835         return (isInverted ? TRUE : FALSE);
1836     } else if (__CFCSetIsBuiltin(theSet)) {
1837         CFCharacterSetPredefinedSet type = __CFCSetBuiltinType(theSet);
1838
1839         if (type == kCFCharacterSetControl) {
1840             if (isInverted || (thePlane == 14)) {
1841                 return TRUE; // There is no plane that covers all values || Plane 14 has language tags
1842             } else {
1843                 return (CFUniCharGetBitmapPtrForPlane(type, thePlane) ? TRUE : FALSE);
1844             }
1845         } else if (type < kCFCharacterSetDecimalDigit) {
1846             return (thePlane && !isInverted ? FALSE : TRUE);
1847         } else if (__CFCSetBuiltinType(theSet) == kCFCharacterSetIllegal) {
1848             return (isInverted ? (thePlane < 3 || thePlane > 13 ? TRUE : FALSE) : TRUE); // This is according to Unicode 3.1
1849         } else {
1850             if (isInverted) {
1851                 return TRUE; // There is no plane that covers all values
1852             } else {
1853                 return (CFUniCharGetBitmapPtrForPlane(type, thePlane) ? TRUE : FALSE);
1854             }
1855         }
1856     } else if (__CFCSetIsRange(theSet)) {
1857         UTF32Char firstChar = __CFCSetRangeFirstChar(theSet);
1858         UTF32Char lastChar = (firstChar + __CFCSetRangeLength(theSet) - 1);
1859         CFIndex firstPlane = firstChar >> 16;
1860         CFIndex lastPlane = lastChar >> 16;
1861
1862         if (isInverted) {
1863             if (thePlane < firstPlane || thePlane > lastPlane) {
1864                 return TRUE;
1865             } else if (thePlane > firstPlane && thePlane < lastPlane) {
1866                 return FALSE;
1867             } else {
1868                 firstChar &= 0xFFFF;
1869                 lastChar &= 0xFFFF;
1870                 if (thePlane == firstPlane) {
1871                     return (firstChar || (firstPlane == lastPlane && lastChar != 0xFFFF) ? TRUE : FALSE);
1872                 } else {
1873                     return (lastChar != 0xFFFF || (firstPlane == lastPlane && firstChar) ? TRUE : FALSE);
1874                 }
1875             }
1876         } else {
1877             return (thePlane < firstPlane || thePlane > lastPlane ? FALSE : TRUE);
1878         }
1879     } else {
1880         if (thePlane == 0) {
1881             switch (__CFCSetClassType(theSet)) {
1882                 case __kCFCharSetClassString: if (!__CFCSetStringLength(theSet)) return isInverted; break;
1883                 case __kCFCharSetClassCompactBitmap: return (__CFCSetCompactBitmapBits(theSet) ? TRUE : FALSE); break;
1884                 case __kCFCharSetClassBitmap: return (__CFCSetBitmapBits(theSet) ? TRUE : FALSE); break;
1885             }
1886             return TRUE;
1887         } else {
1888             CFCharacterSetRef annex = __CFCSetGetAnnexPlaneCharacterSetNoAlloc(theSet, thePlane);
1889             if (annex) {
1890                 if (__CFCSetIsRange(annex)) {
1891                     return (__CFCSetAnnexIsInverted(theSet) && (__CFCSetRangeFirstChar(annex) == 0) && (__CFCSetRangeLength(annex) == 0x10000) ? FALSE : TRUE);
1892                 } else if (__CFCSetIsBitmap(annex)) {
1893                     return (__CFCSetAnnexIsInverted(theSet) && __CFCSetIsEqualBitmap((const UInt32 *)__CFCSetBitmapBits(annex), (const UInt32 *)-1) ? FALSE : TRUE);
1894                 } else {
1895                     uint8_t bitsBuf[__kCFBitmapSize];
1896                     __CFCSetGetBitmap(annex, bitsBuf);
1897                     return (__CFCSetAnnexIsInverted(theSet) && __CFCSetIsEqualBitmap((const UInt32 *)bitsBuf, (const UInt32 *)-1) ? FALSE : TRUE);
1898                 }
1899             } else {
1900                 return __CFCSetAnnexIsInverted(theSet);
1901             }
1902         }
1903     }
1904
1905     return FALSE;
1906 }
1907
1908
1909 CFDataRef CFCharacterSetCreateBitmapRepresentation(CFAllocatorRef alloc, CFCharacterSetRef theSet) {
1910     CFMutableDataRef data;
1911     int numNonBMPPlanes = 0;
1912     int planeIndices[MAX_ANNEX_PLANE];
1913     int idx;
1914     int length;
1915     bool isAnnexInverted;
1916
1917     CF_OBJC_FUNCDISPATCH0(__kCFCharacterSetTypeID, CFDataRef , theSet, "_retainedBitmapRepresentation");
1918
1919     __CFGenericValidateType(theSet, __kCFCharacterSetTypeID);
1920
1921     isAnnexInverted = __CFCSetAnnexIsInverted(theSet);
1922
1923     if (__CFCSetHasNonBMPPlane(theSet)) {
1924         for (idx = 1;idx <= MAX_ANNEX_PLANE;idx++) {
1925             if (isAnnexInverted || __CFCSetGetAnnexPlaneCharacterSetNoAlloc(theSet, idx)) {
1926                 planeIndices[numNonBMPPlanes++] = idx;
1927             }
1928         }
1929     } else if (__CFCSetIsBuiltin(theSet)) {
1930         numNonBMPPlanes = (__CFCSetIsInverted(theSet) ? MAX_ANNEX_PLANE : CFUniCharGetNumberOfPlanes(__CFCSetBuiltinType(theSet)) - 1);
1931     } else if (__CFCSetIsRange(theSet)) {
1932         UInt32 firstChar = __CFCSetRangeFirstChar(theSet);
1933         UInt32 lastChar = __CFCSetRangeFirstChar(theSet) + __CFCSetRangeLength(theSet) - 1;
1934         int firstPlane = (firstChar >> 16);
1935         int lastPlane = (lastChar >> 16);
1936         bool isInverted = __CFCSetIsInverted(theSet);
1937
1938         if (lastPlane > 0) {
1939             if (firstPlane == 0) {
1940                 firstPlane = 1;
1941                 firstChar = 0x10000;
1942             }
1943             numNonBMPPlanes = (lastPlane - firstPlane) + 1;
1944             if (isInverted) {
1945                 numNonBMPPlanes = MAX_ANNEX_PLANE - numNonBMPPlanes;
1946                 if (firstPlane == lastPlane) {
1947                     if (((firstChar & 0xFFFF) > 0) || ((lastChar & 0xFFFF) < 0xFFFF)) ++numNonBMPPlanes;
1948                 } else {
1949                     if ((firstChar & 0xFFFF) > 0) ++numNonBMPPlanes;
1950                     if ((lastChar & 0xFFFF) < 0xFFFF) ++numNonBMPPlanes;
1951                 }
1952             }
1953         } else if (isInverted) {
1954             numNonBMPPlanes = MAX_ANNEX_PLANE;
1955         }
1956     } else if (isAnnexInverted) {
1957         numNonBMPPlanes = MAX_ANNEX_PLANE;
1958     }
1959
1960     length = __kCFBitmapSize + ((__kCFBitmapSize + 1) * numNonBMPPlanes);
1961     data = CFDataCreateMutable(alloc, length);
1962     CFDataSetLength(data, length);
1963     __CFCSetGetBitmap(theSet, CFDataGetMutableBytePtr(data));
1964
1965     if (numNonBMPPlanes > 0) {
1966         char *bytes = CFDataGetMutableBytePtr(data) + __kCFBitmapSize;
1967
1968         if (__CFCSetHasNonBMPPlane(theSet)) {
1969             CFCharacterSetRef subset;
1970
1971             for (idx = 0;idx < numNonBMPPlanes;idx++) {
1972                 *(bytes++) = planeIndices[idx];
1973                 if ((subset = __CFCSetGetAnnexPlaneCharacterSetNoAlloc(theSet, planeIndices[idx])) == NULL) {
1974                     __CFCSetBitmapFastFillWithValue((UInt32 *)bytes, (isAnnexInverted ? 0xFF : 0));
1975                 } else {
1976                     __CFCSetGetBitmap(subset, bytes);
1977                     if (isAnnexInverted) {
1978                         uint32_t count = __kCFBitmapSize / sizeof(uint32_t);
1979                         uint32_t *bits = (uint32_t *)bytes;
1980
1981                         while (count-- > 0) {
1982                             *bits = ~(*bits);
1983                             ++bits;
1984                         }
1985                     }
1986                 }
1987                 bytes += __kCFBitmapSize;
1988             }
1989         } else if (__CFCSetIsBuiltin(theSet)) {
1990             UInt8 result;
1991             Boolean isInverted = __CFCSetIsInverted(theSet);
1992
1993             for (idx = 0;idx < numNonBMPPlanes;idx++) {
1994                 if ((result = CFUniCharGetBitmapForPlane(__CFCSetBuiltinType(theSet), idx + 1, bytes + 1,  isInverted)) == kCFUniCharBitmapEmpty) continue;
1995                 *(bytes++) = idx + 1;
1996                 if (result == kCFUniCharBitmapAll) {
1997                     CFIndex bitmapLength = __kCFBitmapSize;
1998                     while (bitmapLength-- > 0) *(bytes++) = (uint8_t)0xFF;
1999                 } else {
2000                     bytes += __kCFBitmapSize;
2001                 }
2002             }
2003             if (bytes - (const char *)CFDataGetBytePtr(data) < length) CFDataSetLength(data, bytes - (const char *)CFDataGetBytePtr(data));
2004         } else if (__CFCSetIsRange(theSet)) {
2005             UInt32 firstChar = __CFCSetRangeFirstChar(theSet);
2006             UInt32 lastChar = __CFCSetRangeFirstChar(theSet) + __CFCSetRangeLength(theSet) - 1;
2007             int firstPlane = (firstChar >> 16);
2008             int lastPlane = (lastChar >> 16);
2009
2010             if (firstPlane == 0) {
2011                 firstPlane = 1;
2012                 firstChar = 0x10000;
2013             }
2014             if (__CFCSetIsInverted(theSet)) {
2015                 // Mask out the plane byte
2016                 firstChar &= 0xFFFF;
2017                 lastChar &= 0xFFFF;
2018
2019                 for (idx = 1;idx < firstPlane;idx++) { // Fill up until the first plane
2020                     *(bytes++) = idx;
2021                     __CFCSetBitmapFastFillWithValue((UInt32 *)bytes, 0xFF);
2022                     bytes += __kCFBitmapSize;
2023                 }
2024                 if (firstPlane == lastPlane) {
2025                     if ((firstChar > 0) || (lastChar < 0xFFFF)) {
2026                         *(bytes++) = idx;
2027                         __CFCSetBitmapFastFillWithValue((UInt32 *)bytes, 0xFF);
2028                         __CFCSetBitmapRemoveCharactersInRange(bytes, firstChar, lastChar);
2029                         bytes += __kCFBitmapSize;
2030                     }
2031                 } else if (firstPlane < lastPlane) {
2032                     if (firstChar > 0) {
2033                         *(bytes++) = idx;
2034                         __CFCSetBitmapFastFillWithValue((UInt32 *)bytes, 0);
2035                         __CFCSetBitmapAddCharactersInRange(bytes, 0, firstChar - 1);
2036                         bytes += __kCFBitmapSize;
2037                     }
2038                     if (lastChar < 0xFFFF) {
2039                         *(bytes++) = idx;
2040                         __CFCSetBitmapFastFillWithValue((UInt32 *)bytes, 0);
2041                         __CFCSetBitmapAddCharactersInRange(bytes, lastChar, 0xFFFF);
2042                         bytes += __kCFBitmapSize;
2043                     }
2044                 }
2045                 for (idx = lastPlane + 1;idx <= MAX_ANNEX_PLANE;idx++) {
2046                     *(bytes++) = idx;
2047                     __CFCSetBitmapFastFillWithValue((UInt32 *)bytes, 0xFF);
2048                     bytes += __kCFBitmapSize;
2049                 }
2050             } else {
2051                 for (idx = firstPlane;idx <= lastPlane;idx++) {
2052                     *(bytes++) = idx;
2053                     __CFCSetBitmapAddCharactersInRange(bytes, (idx == firstPlane ? firstChar : 0), (idx == lastPlane ? lastChar : 0xFFFF));
2054                     bytes += __kCFBitmapSize;
2055                 }
2056             }
2057         } else if (isAnnexInverted) {
2058             for (idx = 1;idx <= MAX_ANNEX_PLANE;idx++) {
2059                 *(bytes++) = idx;
2060                 __CFCSetBitmapFastFillWithValue((UInt32 *)bytes, 0xFF);
2061                 bytes += __kCFBitmapSize;
2062             }
2063         }
2064     }
2065
2066     return data;
2067 }
2068
2069 /*** MutableCharacterSet functions ***/
2070 void CFCharacterSetAddCharactersInRange(CFMutableCharacterSetRef theSet, CFRange theRange) {
2071     CF_OBJC_FUNCDISPATCH1(__kCFCharacterSetTypeID, void, theSet, "addCharactersInRange:", theRange);
2072
2073     __CFCSetValidateTypeAndMutability(theSet, __PRETTY_FUNCTION__);
2074     __CFCSetValidateRange(theRange, __PRETTY_FUNCTION__);
2075
2076     if (!theRange.length || (__CFCSetIsInverted(theSet) && __CFCSetIsEmpty(theSet))) return; // Inverted && empty set contains all char
2077
2078     if (!__CFCSetIsInverted(theSet)) {
2079         if (__CFCSetIsEmpty(theSet)) {
2080             __CFCSetPutClassType(theSet, __kCFCharSetClassRange);
2081             __CFCSetPutRangeFirstChar(theSet, theRange.location);
2082             __CFCSetPutRangeLength(theSet, theRange.length);
2083             __CFCSetPutHasHashValue(theSet, false);
2084             return;
2085        } else if (__CFCSetIsRange(theSet)) {
2086             CFIndex firstChar = __CFCSetRangeFirstChar(theSet);
2087             CFIndex length = __CFCSetRangeLength(theSet);
2088
2089             if (firstChar == theRange.location) {
2090                 __CFCSetPutRangeLength(theSet, __CFMin(length, theRange.length));
2091                 __CFCSetPutHasHashValue(theSet, false);
2092                 return;
2093             } else if (firstChar < theRange.location && theRange.location <= firstChar + length) {
2094                 if (firstChar + length < theRange.location + theRange.length) __CFCSetPutRangeLength(theSet, theRange.length + (theRange.location - firstChar));
2095                 __CFCSetPutHasHashValue(theSet, false);
2096                 return;
2097             } else if (theRange.location < firstChar && firstChar <= theRange.location + theRange.length) {
2098                 __CFCSetPutRangeFirstChar(theSet, theRange.location);
2099                 __CFCSetPutRangeLength(theSet, length + (firstChar - theRange.location));
2100                 __CFCSetPutHasHashValue(theSet, false);
2101                 return;
2102             }
2103         } else if (__CFCSetIsString(theSet) && __CFCSetStringLength(theSet) + theRange.length < __kCFStringCharSetMax) {
2104             UniChar *buffer;
2105             if (!__CFCSetStringBuffer(theSet))
2106                 __CFCSetPutStringBuffer(theSet, CFAllocatorAllocate(CFGetAllocator(theSet), __kCFStringCharSetMax * sizeof(UniChar), 0));
2107             buffer = __CFCSetStringBuffer(theSet) + __CFCSetStringLength(theSet);
2108             __CFCSetPutStringLength(theSet, __CFCSetStringLength(theSet) + theRange.length);
2109             while (theRange.length--) *buffer++ = theRange.location++;
2110             qsort(__CFCSetStringBuffer(theSet), __CFCSetStringLength(theSet), sizeof(UniChar), chcompar);
2111             __CFCSetPutHasHashValue(theSet, false);
2112             return;
2113         }
2114     }
2115
2116     // OK, I have to be a bitmap
2117     __CFCSetMakeBitmap(theSet);
2118     __CFCSetAddNonBMPPlanesInRange(theSet, theRange);
2119     if (theRange.location < 0x10000) { // theRange is in BMP
2120         if (theRange.location + theRange.length >= NUMCHARACTERS) theRange.length = NUMCHARACTERS - theRange.location;
2121         __CFCSetBitmapAddCharactersInRange(__CFCSetBitmapBits(theSet), theRange.location, theRange.location + theRange.length - 1);
2122     }
2123     __CFCSetPutHasHashValue(theSet, false);
2124
2125     if (__CFCheckForExapendedSet) __CFCheckForExpandedSet(theSet);
2126 }
2127
2128 void CFCharacterSetRemoveCharactersInRange(CFMutableCharacterSetRef theSet, CFRange theRange) {
2129     CF_OBJC_FUNCDISPATCH1(__kCFCharacterSetTypeID, void, theSet, "removeCharactersInRange:", theRange);
2130
2131     __CFCSetValidateTypeAndMutability(theSet, __PRETTY_FUNCTION__);
2132     __CFCSetValidateRange(theRange, __PRETTY_FUNCTION__);
2133
2134     if (!theRange.length || (!__CFCSetIsInverted(theSet) && __CFCSetIsEmpty(theSet))) return; // empty set
2135
2136     if (__CFCSetIsInverted(theSet)) {
2137         if (__CFCSetIsEmpty(theSet)) {
2138             __CFCSetPutClassType(theSet, __kCFCharSetClassRange);
2139             __CFCSetPutRangeFirstChar(theSet, theRange.location);
2140             __CFCSetPutRangeLength(theSet, theRange.length);
2141             __CFCSetPutHasHashValue(theSet, false);
2142             return;
2143        } else if (__CFCSetIsRange(theSet)) {
2144             CFIndex firstChar = __CFCSetRangeFirstChar(theSet);
2145             CFIndex length = __CFCSetRangeLength(theSet);
2146
2147             if (firstChar == theRange.location) {
2148                 __CFCSetPutRangeLength(theSet, __CFMin(length, theRange.length));
2149                 __CFCSetPutHasHashValue(theSet, false);
2150                 return;
2151             } else if (firstChar < theRange.location && theRange.location <= firstChar + length) {
2152                 if (firstChar + length < theRange.location + theRange.length) __CFCSetPutRangeLength(theSet, theRange.length + (theRange.location - firstChar));
2153                 __CFCSetPutHasHashValue(theSet, false);
2154                 return;
2155             } else if (theRange.location < firstChar && firstChar <= theRange.location + theRange.length) {
2156                 __CFCSetPutRangeFirstChar(theSet, theRange.location);
2157                 __CFCSetPutRangeLength(theSet, length + (firstChar - theRange.location));
2158                 __CFCSetPutHasHashValue(theSet, false);
2159                 return;
2160             }
2161         } else if (__CFCSetIsString(theSet) && __CFCSetStringLength(theSet) + theRange.length < __kCFStringCharSetMax) {
2162             UniChar *buffer;
2163             if (!__CFCSetStringBuffer(theSet))
2164                 __CFCSetPutStringBuffer(theSet, CFAllocatorAllocate(CFGetAllocator(theSet), __kCFStringCharSetMax * sizeof(UniChar), 0));
2165             buffer = __CFCSetStringBuffer(theSet) + __CFCSetStringLength(theSet);
2166             __CFCSetPutStringLength(theSet, __CFCSetStringLength(theSet) + theRange.length);
2167             while (theRange.length--) *buffer++ = theRange.location++;
2168             qsort(__CFCSetStringBuffer(theSet), __CFCSetStringLength(theSet), sizeof(UniChar), chcompar);
2169             __CFCSetPutHasHashValue(theSet, false);
2170             return;
2171         }
2172     }
2173
2174     // OK, I have to be a bitmap
2175     __CFCSetMakeBitmap(theSet);
2176     __CFCSetRemoveNonBMPPlanesInRange(theSet, theRange);
2177     if (theRange.location < 0x10000) { // theRange is in BMP
2178         if (theRange.location + theRange.length > NUMCHARACTERS) theRange.length = NUMCHARACTERS - theRange.location;
2179         if (theRange.location == 0 && theRange.length == NUMCHARACTERS) { // Remove all
2180             CFAllocatorDeallocate(CFGetAllocator(theSet), __CFCSetBitmapBits(theSet));
2181             __CFCSetPutBitmapBits(theSet, NULL);
2182         } else {
2183             __CFCSetBitmapRemoveCharactersInRange(__CFCSetBitmapBits(theSet), theRange.location, theRange.location + theRange.length - 1);
2184         }
2185     }
2186
2187     __CFCSetPutHasHashValue(theSet, false);
2188     if (__CFCheckForExapendedSet) __CFCheckForExpandedSet(theSet);
2189 }
2190
2191 void CFCharacterSetAddCharactersInString(CFMutableCharacterSetRef theSet,  CFStringRef theString) {
2192     const UniChar *buffer;
2193     CFIndex length;
2194
2195     CF_OBJC_FUNCDISPATCH1(__kCFCharacterSetTypeID, void, theSet, "addCharactersInString:", theString);
2196
2197     __CFCSetValidateTypeAndMutability(theSet, __PRETTY_FUNCTION__);
2198
2199     if ((__CFCSetIsEmpty(theSet) && __CFCSetIsInverted(theSet)) || !(length = CFStringGetLength(theString))) return;
2200
2201     if (!__CFCSetIsInverted(theSet)) {
2202         CFIndex newLength = length + (__CFCSetIsEmpty(theSet) ? 0 : (__CFCSetIsString(theSet) ? __CFCSetStringLength(theSet) : __kCFStringCharSetMax));
2203
2204         if (newLength < __kCFStringCharSetMax) {
2205             if (__CFCSetIsEmpty(theSet)) __CFCSetPutStringLength(theSet, 0); // Make sure to reset this
2206
2207             if (!__CFCSetStringBuffer(theSet))
2208                 __CFCSetPutStringBuffer(theSet, CFAllocatorAllocate(CFGetAllocator(theSet), __kCFStringCharSetMax * sizeof(UniChar), 0));
2209             buffer = __CFCSetStringBuffer(theSet) + __CFCSetStringLength(theSet);
2210
2211             __CFCSetPutClassType(theSet, __kCFCharSetClassString);
2212             __CFCSetPutStringLength(theSet, newLength);
2213             CFStringGetCharacters(theString, CFRangeMake(0, length), (UniChar*)buffer);
2214             qsort(__CFCSetStringBuffer(theSet), newLength, sizeof(UniChar), chcompar);
2215             __CFCSetPutHasHashValue(theSet, false);
2216             return;
2217         }
2218     }
2219
2220     // OK, I have to be a bitmap
2221     __CFCSetMakeBitmap(theSet);
2222     if ((buffer = CFStringGetCharactersPtr(theString))) {
2223         while (length--) __CFCSetBitmapAddCharacter(__CFCSetBitmapBits(theSet), *buffer++);
2224     } else {
2225         CFStringInlineBuffer inlineBuffer;
2226         CFIndex idx;
2227
2228         CFStringInitInlineBuffer(theString, &inlineBuffer, CFRangeMake(0, length));
2229         for (idx = 0;idx < length;idx++) __CFCSetBitmapAddCharacter(__CFCSetBitmapBits(theSet), __CFStringGetCharacterFromInlineBufferQuick(&inlineBuffer, idx));
2230     }
2231     __CFCSetPutHasHashValue(theSet, false);
2232     if (__CFCheckForExapendedSet) __CFCheckForExpandedSet(theSet);
2233 }
2234
2235 void CFCharacterSetRemoveCharactersInString(CFMutableCharacterSetRef theSet, CFStringRef theString) {
2236     const UniChar *buffer;
2237     CFIndex length;
2238
2239     CF_OBJC_FUNCDISPATCH1(__kCFCharacterSetTypeID, void, theSet, "removeCharactersInString:", theString);
2240
2241     __CFCSetValidateTypeAndMutability(theSet, __PRETTY_FUNCTION__);
2242
2243     if ((__CFCSetIsEmpty(theSet) && !__CFCSetIsInverted(theSet)) || !(length = CFStringGetLength(theString))) return;
2244
2245     if (__CFCSetIsInverted(theSet)) {
2246         CFIndex newLength = length + (__CFCSetIsEmpty(theSet) ? 0 : (__CFCSetIsString(theSet) ? __CFCSetStringLength(theSet) : __kCFStringCharSetMax));
2247
2248         if (newLength < __kCFStringCharSetMax) {
2249             if (__CFCSetIsEmpty(theSet)) __CFCSetPutStringLength(theSet, 0); // Make sure to reset this
2250
2251             if (!__CFCSetStringBuffer(theSet))
2252                 __CFCSetPutStringBuffer(theSet, CFAllocatorAllocate(CFGetAllocator(theSet), __kCFStringCharSetMax * sizeof(UniChar), 0));
2253             buffer = __CFCSetStringBuffer(theSet) + __CFCSetStringLength(theSet);
2254
2255             __CFCSetPutClassType(theSet, __kCFCharSetClassString);
2256             __CFCSetPutStringLength(theSet, newLength);
2257             CFStringGetCharacters(theString, CFRangeMake(0, length), (UniChar *)buffer);
2258             qsort(__CFCSetStringBuffer(theSet), newLength, sizeof(UniChar), chcompar);
2259             __CFCSetPutHasHashValue(theSet, false);
2260             return;
2261         }
2262     }
2263
2264     // OK, I have to be a bitmap
2265     __CFCSetMakeBitmap(theSet);
2266     if ((buffer = CFStringGetCharactersPtr(theString))) {
2267         while (length--) __CFCSetBitmapRemoveCharacter(__CFCSetBitmapBits(theSet), *buffer++);
2268     } else {
2269         CFStringInlineBuffer inlineBuffer;
2270         CFIndex idx;
2271
2272         CFStringInitInlineBuffer(theString, &inlineBuffer, CFRangeMake(0, length));
2273         for (idx = 0;idx < length;idx++) __CFCSetBitmapRemoveCharacter(__CFCSetBitmapBits(theSet), __CFStringGetCharacterFromInlineBufferQuick(&inlineBuffer, idx));
2274     }
2275     __CFCSetPutHasHashValue(theSet, false);
2276     if (__CFCheckForExapendedSet) __CFCheckForExpandedSet(theSet);
2277 }
2278
2279 void CFCharacterSetUnion(CFMutableCharacterSetRef theSet, CFCharacterSetRef theOtherSet) {
2280     CFCharacterSetRef expandedSet = NULL;
2281
2282     CF_OBJC_FUNCDISPATCH1(__kCFCharacterSetTypeID, void, theSet, "formUnionWithCharacterSet:", theOtherSet);
2283
2284     __CFCSetValidateTypeAndMutability(theSet, __PRETTY_FUNCTION__);
2285
2286     if (__CFCSetIsEmpty(theSet) && __CFCSetIsInverted(theSet)) return; // Inverted empty set contains all char
2287
2288     if (!CF_IS_OBJC(__kCFCharacterSetTypeID, theOtherSet) || (expandedSet = __CFCharacterSetGetExpandedSetForNSCharacterSet(theOtherSet))) { // Really CF, we can do some trick here
2289         if (expandedSet) theOtherSet = expandedSet;
2290
2291         if (__CFCSetIsEmpty(theOtherSet)) {
2292             if (__CFCSetIsInverted(theOtherSet)) {
2293                 if (__CFCSetIsString(theSet) && __CFCSetStringBuffer(theSet)) {
2294                     CFAllocatorDeallocate(CFGetAllocator(theSet), __CFCSetStringBuffer(theSet));
2295                 } else if (__CFCSetIsBitmap(theSet) && __CFCSetBitmapBits(theSet)) {
2296                     CFAllocatorDeallocate(CFGetAllocator(theSet), __CFCSetBitmapBits(theSet));
2297                 } else if (__CFCSetIsCompactBitmap(theSet) && __CFCSetCompactBitmapBits(theSet)) {
2298                     CFAllocatorDeallocate(CFGetAllocator(theSet), __CFCSetCompactBitmapBits(theSet));
2299                 }
2300                 __CFCSetPutClassType(theSet, __kCFCharSetClassRange);
2301                 __CFCSetPutRangeLength(theSet, 0);
2302                 __CFCSetPutIsInverted(theSet, true);
2303                 __CFCSetPutHasHashValue(theSet, false);
2304                 __CFCSetDeallocateAnnexPlane(theSet);
2305             } else {
2306                 return; // Nothing to do here
2307             }
2308         }
2309
2310         if (__CFCSetIsBuiltin(theOtherSet) && __CFCSetIsEmpty(theSet)) { // theSet can be builtin set
2311             __CFCSetPutClassType(theSet, __kCFCharSetClassBuiltin);
2312             __CFCSetPutBuiltinType(theSet, __CFCSetBuiltinType(theOtherSet));
2313             __CFCSetPutHasHashValue(theSet, false);
2314         } else if (__CFCSetIsRange(theOtherSet)) {
2315             if (__CFCSetIsInverted(theOtherSet)) {
2316                 UTF32Char firstChar = __CFCSetRangeFirstChar(theOtherSet);
2317                 CFIndex length = __CFCSetRangeLength(theOtherSet);
2318
2319                 if (firstChar > 0) CFCharacterSetAddCharactersInRange(theSet, CFRangeMake(0, firstChar));
2320                 firstChar += length;
2321                 length = 0x110000 - firstChar;
2322                 CFCharacterSetAddCharactersInRange(theSet, CFRangeMake(firstChar, length));
2323             } else {
2324                 CFCharacterSetAddCharactersInRange(theSet, CFRangeMake(__CFCSetRangeFirstChar(theOtherSet), __CFCSetRangeLength(theOtherSet)));
2325             }
2326         } else if (__CFCSetIsString(theOtherSet)) {
2327             CFStringRef string = CFStringCreateWithCharactersNoCopy(CFGetAllocator(theSet), __CFCSetStringBuffer(theOtherSet), __CFCSetStringLength(theOtherSet), kCFAllocatorNull);
2328             CFCharacterSetAddCharactersInString(theSet, string);
2329             CFRelease(string);
2330         } else {
2331             __CFCSetMakeBitmap(theSet);
2332             if (__CFCSetIsBitmap(theOtherSet)) {
2333                 UInt32 *bitmap1 = (UInt32*)__CFCSetBitmapBits(theSet);
2334                 UInt32 *bitmap2 = (UInt32*)__CFCSetBitmapBits(theOtherSet);
2335                 CFIndex length = __kCFBitmapSize / sizeof(UInt32);
2336                 while (length--) *bitmap1++ |= *bitmap2++;
2337             } else {
2338                 UInt32 *bitmap1 = (UInt32*)__CFCSetBitmapBits(theSet);
2339                 UInt32 *bitmap2;
2340                 CFIndex length = __kCFBitmapSize / sizeof(UInt32);
2341                 uint8_t bitmapBuffer[__kCFBitmapSize];
2342                 __CFCSetGetBitmap(theOtherSet, bitmapBuffer);
2343                 bitmap2 = (UInt32*)bitmapBuffer;
2344                 while (length--) *bitmap1++ |= *bitmap2++;
2345             }
2346             __CFCSetPutHasHashValue(theSet, false);
2347         }
2348         if (__CFCSetHasNonBMPPlane(theOtherSet)) {
2349             CFMutableCharacterSetRef otherSetPlane;
2350             int idx;
2351
2352             for (idx = 1;idx <= MAX_ANNEX_PLANE;idx++) {
2353                 if ((otherSetPlane = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSetNoAlloc(theOtherSet, idx))) {
2354                     CFCharacterSetUnion((CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSet(theSet, idx), otherSetPlane);
2355                 }
2356             }
2357         } else if (__CFCSetIsBuiltin(theOtherSet)) {
2358             CFMutableCharacterSetRef annexPlane;
2359             uint8_t bitmapBuffer[__kCFBitmapSize];
2360             uint8_t result;
2361             int planeIndex;
2362             Boolean isOtherAnnexPlaneInverted = __CFCSetAnnexIsInverted(theOtherSet);
2363             UInt32 *bitmap1;
2364             UInt32 *bitmap2;
2365             CFIndex length;
2366
2367             for (planeIndex = 1;planeIndex <= MAX_ANNEX_PLANE;planeIndex++) {
2368                 result = CFUniCharGetBitmapForPlane(__CFCSetBuiltinType(theOtherSet), planeIndex, bitmapBuffer, isOtherAnnexPlaneInverted);
2369                 if (result != kCFUniCharBitmapEmpty) {
2370                     annexPlane = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSet(theSet, planeIndex);
2371                     if (result == kCFUniCharBitmapAll) {
2372                         CFCharacterSetAddCharactersInRange(annexPlane, CFRangeMake(0x0000, 0x10000));
2373                     } else {
2374                         __CFCSetMakeBitmap(annexPlane);
2375                         bitmap1 = (UInt32 *)__CFCSetBitmapBits(annexPlane);
2376                         length = __kCFBitmapSize / sizeof(UInt32);
2377                         bitmap2 = (UInt32*)bitmapBuffer;
2378                         while (length--) *bitmap1++ |= *bitmap2++;
2379                     }
2380                 }
2381             }
2382         }
2383         if (__CFCheckForExapendedSet) __CFCheckForExpandedSet(theSet);
2384     } else { // It's NSCharacterSet
2385         CFDataRef bitmapRep = CFCharacterSetCreateBitmapRepresentation(NULL, theOtherSet);
2386         const UInt32 *bitmap2 = (bitmapRep && CFDataGetLength(bitmapRep) ? (const UInt32 *)CFDataGetBytePtr(bitmapRep) : NULL);
2387         if (bitmap2) {
2388             UInt32 *bitmap1;
2389             CFIndex length = __kCFBitmapSize / sizeof(UInt32);
2390             __CFCSetMakeBitmap(theSet);
2391             bitmap1 = (UInt32*)__CFCSetBitmapBits(theSet);
2392             while (length--) *bitmap1++ |= *bitmap2++;
2393             __CFCSetPutHasHashValue(theSet, false);
2394         }
2395         CFRelease(bitmapRep);
2396     }
2397 }
2398
2399 void CFCharacterSetIntersect(CFMutableCharacterSetRef theSet, CFCharacterSetRef theOtherSet) {
2400     CFCharacterSetRef expandedSet = NULL;
2401
2402     CF_OBJC_FUNCDISPATCH1(__kCFCharacterSetTypeID, void, theSet, "formIntersectionWithCharacterSet:", theOtherSet);
2403
2404     __CFCSetValidateTypeAndMutability(theSet, __PRETTY_FUNCTION__);
2405
2406     if (__CFCSetIsEmpty(theSet) && !__CFCSetIsInverted(theSet)) return; // empty set
2407
2408     if (!CF_IS_OBJC(__kCFCharacterSetTypeID, theOtherSet) || (expandedSet = __CFCharacterSetGetExpandedSetForNSCharacterSet(theOtherSet))) { // Really CF, we can do some trick here
2409         if (expandedSet) theOtherSet = expandedSet;
2410
2411         if (__CFCSetIsEmpty(theOtherSet)) {
2412            if (!__CFCSetIsInverted(theOtherSet)) {
2413                 if (__CFCSetIsString(theSet) && __CFCSetStringBuffer(theSet)) {
2414                     CFAllocatorDeallocate(CFGetAllocator(theSet), __CFCSetStringBuffer(theSet));
2415                 } else if (__CFCSetIsBitmap(theSet) && __CFCSetBitmapBits(theSet)) {
2416                     CFAllocatorDeallocate(CFGetAllocator(theSet), __CFCSetBitmapBits(theSet));
2417                 } else if (__CFCSetIsCompactBitmap(theSet) && __CFCSetCompactBitmapBits(theSet)) {
2418                     CFAllocatorDeallocate(CFGetAllocator(theSet), __CFCSetCompactBitmapBits(theSet));
2419                 }
2420                 __CFCSetPutClassType(theSet, __kCFCharSetClassBitmap);
2421                 __CFCSetPutBitmapBits(theSet, NULL);
2422                 __CFCSetPutIsInverted(theSet, false);
2423                 theSet->_hashValue = 0;
2424                 __CFCSetPutHasHashValue(theSet, true);
2425                 __CFCSetDeallocateAnnexPlane(theSet);
2426             }
2427         } else if (__CFCSetIsEmpty(theSet)) { // non inverted empty set contains all character
2428             __CFCSetPutClassType(theSet, __CFCSetClassType(theOtherSet));
2429             __CFCSetPutHasHashValue(theSet, __CFCSetHasHashValue(theOtherSet));
2430             __CFCSetPutIsInverted(theSet, __CFCSetIsInverted(theOtherSet));
2431             theSet->_hashValue = theOtherSet->_hashValue;
2432             if (__CFCSetHasNonBMPPlane(theOtherSet)) {
2433                 CFMutableCharacterSetRef otherSetPlane;
2434                 int idx;
2435                 for (idx = 1;idx <= MAX_ANNEX_PLANE;idx++) {
2436                     if ((otherSetPlane = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSetNoAlloc(theOtherSet, idx))) {
2437                         otherSetPlane = (CFMutableCharacterSetRef)CFCharacterSetCreateMutableCopy(CFGetAllocator(theSet), otherSetPlane);
2438                         __CFCSetPutCharacterSetToAnnexPlane(theSet, otherSetPlane, idx);
2439                         CFRelease(otherSetPlane);
2440                     }
2441                 }
2442                 __CFCSetAnnexSetIsInverted(theSet, __CFCSetAnnexIsInverted(theOtherSet));
2443             }
2444
2445             switch (__CFCSetClassType(theOtherSet)) {
2446                 case __kCFCharSetClassBuiltin:
2447                     __CFCSetPutBuiltinType(theSet, __CFCSetBuiltinType(theOtherSet));
2448                     break;
2449
2450                 case __kCFCharSetClassRange:
2451                     __CFCSetPutRangeFirstChar(theSet, __CFCSetRangeFirstChar(theOtherSet));
2452                     __CFCSetPutRangeLength(theSet, __CFCSetRangeLength(theOtherSet));
2453                     break;
2454
2455                 case __kCFCharSetClassString:
2456                     __CFCSetPutStringLength(theSet, __CFCSetStringLength(theOtherSet));
2457                     if (!__CFCSetStringBuffer(theSet))
2458                         __CFCSetPutStringBuffer(theSet, CFAllocatorAllocate(CFGetAllocator(theSet), __kCFStringCharSetMax * sizeof(UniChar), 0));
2459                    memmove(__CFCSetStringBuffer(theSet), __CFCSetStringBuffer(theOtherSet), __CFCSetStringLength(theSet) * sizeof(UniChar));
2460                     break;
2461
2462                 case __kCFCharSetClassBitmap:
2463                     __CFCSetPutBitmapBits(theSet, CFAllocatorAllocate(CFGetAllocator(theSet), sizeof(uint8_t) * __kCFBitmapSize, 0));
2464                     memmove(__CFCSetBitmapBits(theSet), __CFCSetBitmapBits(theOtherSet), __kCFBitmapSize);
2465                     break;
2466
2467                 case __kCFCharSetClassCompactBitmap: {
2468                     const uint8_t *cBitmap = __CFCSetCompactBitmapBits(theOtherSet);
2469                     uint8_t *newBitmap;
2470                     uint32_t size = __CFCSetGetCompactBitmapSize(cBitmap);
2471                     newBitmap = (uint8_t *)CFAllocatorAllocate(CFGetAllocator(theSet), sizeof(uint8_t) * size, 0);
2472                     __CFCSetPutBitmapBits(theSet, newBitmap);
2473                     memmove(newBitmap, cBitmap, size);
2474                     }
2475                     break;
2476
2477                 default:
2478                     CFAssert1(0, __kCFLogAssertion, "%s: Internal inconsistency error: unknown character set type", __PRETTY_FUNCTION__); // We should never come here
2479             }
2480         } else {
2481             __CFCSetMakeBitmap(theSet);
2482             if (__CFCSetIsBitmap(theOtherSet)) {
2483                 UInt32 *bitmap1 = (UInt32*)__CFCSetBitmapBits(theSet);
2484                 UInt32 *bitmap2 = (UInt32*)__CFCSetBitmapBits(theOtherSet);
2485                 CFIndex length = __kCFBitmapSize / sizeof(UInt32);
2486                 while (length--) *bitmap1++ &= *bitmap2++;
2487             } else {
2488                 UInt32 *bitmap1 = (UInt32*)__CFCSetBitmapBits(theSet);
2489                 UInt32 *bitmap2;
2490                 CFIndex length = __kCFBitmapSize / sizeof(UInt32);
2491                 uint8_t bitmapBuffer[__kCFBitmapSize];
2492                 __CFCSetGetBitmap(theOtherSet, bitmapBuffer);
2493                 bitmap2 = (UInt32*)bitmapBuffer;
2494                 while (length--) *bitmap1++ &= *bitmap2++;
2495             }
2496             __CFCSetPutHasHashValue(theSet, false);
2497             if (__CFCSetHasNonBMPPlane(theOtherSet)) {
2498                 CFMutableCharacterSetRef annexPlane;
2499                 CFMutableCharacterSetRef otherSetPlane;
2500                 int idx;
2501                 for (idx = 1;idx <= MAX_ANNEX_PLANE;idx++) {
2502                     if ((otherSetPlane = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSetNoAlloc(theOtherSet, idx))) {
2503                         annexPlane = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSet(theSet, idx);
2504                         CFCharacterSetIntersect(annexPlane, otherSetPlane);
2505                         if (__CFCSetIsEmpty(annexPlane) && !__CFCSetIsInverted(annexPlane)) __CFCSetPutCharacterSetToAnnexPlane(theSet, NULL, idx);
2506                     } else if (__CFCSetGetAnnexPlaneCharacterSetNoAlloc(theSet, idx)) {
2507                         __CFCSetPutCharacterSetToAnnexPlane(theSet, NULL, idx);
2508                     }
2509                 }
2510                 if (!__CFCSetHasNonBMPPlane(theSet)) __CFCSetDeallocateAnnexPlane(theSet);
2511             } else if (__CFCSetIsBuiltin(theOtherSet)) {
2512                 CFMutableCharacterSetRef annexPlane;
2513                 uint8_t bitmapBuffer[__kCFBitmapSize];
2514                 uint8_t result;
2515                 int planeIndex;
2516                 Boolean isOtherAnnexPlaneInverted = __CFCSetAnnexIsInverted(theOtherSet);
2517                 UInt32 *bitmap1;
2518                 UInt32 *bitmap2;
2519                 CFIndex length;
2520
2521                 for (planeIndex = 1;planeIndex <= MAX_ANNEX_PLANE;planeIndex++) {
2522                     annexPlane = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSetNoAlloc(theSet, planeIndex);
2523                     if (annexPlane) {
2524                         result = CFUniCharGetBitmapForPlane(__CFCSetBuiltinType(theOtherSet), planeIndex, bitmapBuffer, isOtherAnnexPlaneInverted);
2525                         if (result == kCFUniCharBitmapEmpty) {
2526                             __CFCSetPutCharacterSetToAnnexPlane(theSet, NULL, planeIndex);
2527                         } else if (result == kCFUniCharBitmapFilled) {
2528                             Boolean isEmpty = true;
2529
2530                             __CFCSetMakeBitmap(annexPlane);
2531                             bitmap1 = (UInt32 *)__CFCSetBitmapBits(annexPlane);
2532                             length = __kCFBitmapSize / sizeof(UInt32);
2533                             bitmap2 = (UInt32*)bitmapBuffer;
2534
2535                             while (length--) {
2536                                 if ((*bitmap1++ &= *bitmap2++)) isEmpty = false;
2537                             }
2538                             if (isEmpty) __CFCSetPutCharacterSetToAnnexPlane(theSet, NULL, planeIndex);
2539                         }
2540                     }
2541                 }
2542                 if (!__CFCSetHasNonBMPPlane(theSet)) __CFCSetDeallocateAnnexPlane(theSet);
2543             } else if (__CFCSetIsRange(theOtherSet)) {
2544                 CFMutableCharacterSetRef tempOtherSet = CFCharacterSetCreateMutable(CFGetAllocator(theSet));
2545                 CFMutableCharacterSetRef annexPlane;
2546                 CFMutableCharacterSetRef otherSetPlane;
2547                 int idx;
2548
2549                 __CFCSetAddNonBMPPlanesInRange(tempOtherSet, CFRangeMake(__CFCSetRangeFirstChar(theOtherSet), __CFCSetRangeLength(theOtherSet)));
2550
2551                 for (idx = 1;idx <= MAX_ANNEX_PLANE;idx++) {
2552                     if ((otherSetPlane = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSetNoAlloc(tempOtherSet, idx))) {
2553                         annexPlane = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSet(theSet, idx);
2554                         CFCharacterSetIntersect(annexPlane, otherSetPlane);
2555                         if (__CFCSetIsEmpty(annexPlane) && !__CFCSetIsInverted(annexPlane)) __CFCSetPutCharacterSetToAnnexPlane(theSet, NULL, idx);
2556                     } else if (__CFCSetGetAnnexPlaneCharacterSetNoAlloc(theSet, idx)) {
2557                         __CFCSetPutCharacterSetToAnnexPlane(theSet, NULL, idx);
2558                     }
2559                 }
2560                 if (!__CFCSetHasNonBMPPlane(theSet)) __CFCSetDeallocateAnnexPlane(theSet);
2561                 CFRelease(tempOtherSet);
2562             } else if (__CFCSetHasNonBMPPlane(theSet)) {
2563                 __CFCSetDeallocateAnnexPlane(theSet);
2564             }
2565         }
2566         if (__CFCheckForExapendedSet) __CFCheckForExpandedSet(theSet);
2567     } else { // It's NSCharacterSet
2568         CFDataRef bitmapRep = CFCharacterSetCreateBitmapRepresentation(NULL, theOtherSet);
2569         const UInt32 *bitmap2 = (bitmapRep && CFDataGetLength(bitmapRep) ? (const UInt32 *)CFDataGetBytePtr(bitmapRep) : NULL);
2570         if (bitmap2) {
2571             UInt32 *bitmap1;
2572             CFIndex length = __kCFBitmapSize / sizeof(UInt32);
2573             __CFCSetMakeBitmap(theSet);
2574             bitmap1 = (UInt32*)__CFCSetBitmapBits(theSet);
2575             while (length--) *bitmap1++ &= *bitmap2++;
2576             __CFCSetPutHasHashValue(theSet, false);
2577         }
2578         CFRelease(bitmapRep);
2579     }
2580 }
2581
2582 void CFCharacterSetInvert(CFMutableCharacterSetRef theSet) {
2583
2584     CF_OBJC_FUNCDISPATCH0(__kCFCharacterSetTypeID, void, theSet, "invert");
2585
2586     __CFCSetValidateTypeAndMutability(theSet, __PRETTY_FUNCTION__);
2587
2588     __CFCSetPutHasHashValue(theSet, false);
2589
2590     if (__CFCSetClassType(theSet) == __kCFCharSetClassBitmap) {
2591         CFIndex idx;
2592         CFIndex count = __kCFBitmapSize / sizeof(UInt32);
2593         UInt32 *bitmap = (UInt32*) __CFCSetBitmapBits(theSet);
2594
2595         if (NULL == bitmap) {
2596             bitmap =  (UInt32 *)CFAllocatorAllocate(CFGetAllocator(theSet), __kCFBitmapSize, 0);
2597             __CFCSetPutBitmapBits(theSet, (uint8_t *)bitmap);
2598             for (idx = 0;idx < count;idx++) bitmap[idx] = 0xFFFFFFFF;
2599         } else {
2600             for (idx = 0;idx < count;idx++) bitmap[idx] = ~(bitmap[idx]);
2601         }
2602         __CFCSetAllocateAnnexForPlane(theSet, 0); // We need to alloc annex to invert
2603     } else if (__CFCSetClassType(theSet) == __kCFCharSetClassCompactBitmap) {
2604         uint8_t *bitmap = __CFCSetCompactBitmapBits(theSet);
2605         int idx;
2606         int length = 0;
2607         uint8_t value;
2608
2609         for (idx = 0;idx < __kCFCompactBitmapNumPages;idx++) {
2610             value = bitmap[idx];
2611
2612             if (value == 0) {
2613                 bitmap[idx] = UINT8_MAX;
2614             } else if (value == UINT8_MAX) {
2615                 bitmap[idx] = 0;
2616             } else {
2617                 length += __kCFCompactBitmapPageSize;
2618             }
2619         }
2620         bitmap += __kCFCompactBitmapNumPages;
2621         for (idx = 0;idx < length;idx++) bitmap[idx] = ~(bitmap[idx]);
2622         __CFCSetAllocateAnnexForPlane(theSet, 0); // We need to alloc annex to invert
2623     } else {
2624         __CFCSetPutIsInverted(theSet, !__CFCSetIsInverted(theSet));
2625     }
2626     __CFCSetAnnexSetIsInverted(theSet, !__CFCSetAnnexIsInverted(theSet));
2627 }
2628
2629 void CFCharacterSetCompact(CFMutableCharacterSetRef theSet) {
2630     if (__CFCSetIsBitmap(theSet) && __CFCSetBitmapBits(theSet)) __CFCSetMakeCompact(theSet);
2631     if (__CFCSetHasNonBMPPlane(theSet)) {
2632         CFMutableCharacterSetRef annex;
2633         int idx;
2634
2635         for (idx = 1;idx <= MAX_ANNEX_PLANE;idx++) {
2636             if ((annex = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSetNoAlloc(theSet, idx)) && __CFCSetIsBitmap(annex) && __CFCSetBitmapBits(annex)) {
2637                 __CFCSetMakeCompact(annex);
2638             }
2639         }
2640     }
2641 }
2642
2643 void CFCharacterSetFast(CFMutableCharacterSetRef theSet) {
2644     if (__CFCSetIsCompactBitmap(theSet) && __CFCSetCompactBitmapBits(theSet)) __CFCSetMakeBitmap(theSet);
2645     if (__CFCSetHasNonBMPPlane(theSet)) {
2646         CFMutableCharacterSetRef annex;
2647         int idx;
2648
2649         for (idx = 1;idx <= MAX_ANNEX_PLANE;idx++) {
2650             if ((annex = (CFMutableCharacterSetRef)__CFCSetGetAnnexPlaneCharacterSetNoAlloc(theSet, idx)) && __CFCSetIsCompactBitmap(annex) && __CFCSetCompactBitmapBits(annex)) {
2651                 __CFCSetMakeBitmap(annex);
2652             }
2653         }
2654     }
2655 }
2656
2657 /* Keyed-coding support
2658 */
2659 CFCharacterSetKeyedCodingType _CFCharacterSetGetKeyedCodingType(CFCharacterSetRef cset) {
2660     switch (__CFCSetClassType(cset)) {
2661         case __kCFCharSetClassBuiltin: return ((__CFCSetBuiltinType(cset) < kCFCharacterSetSymbol) ? kCFCharacterSetKeyedCodingTypeBuiltin : kCFCharacterSetKeyedCodingTypeBitmap);
2662         case __kCFCharSetClassRange: return kCFCharacterSetKeyedCodingTypeRange;
2663
2664         case __kCFCharSetClassString: // We have to check if we have non-BMP here
2665             if (!__CFCSetHasNonBMPPlane(cset)) return kCFCharacterSetKeyedCodingTypeString; // BMP only. we can archive the string
2666         /* fallthrough */
2667
2668         default:
2669             return kCFCharacterSetKeyedCodingTypeBitmap;
2670     }
2671 }
2672
2673 bool _CFCharacterSetIsMutable(CFCharacterSetRef cset) { return __CFCSetIsMutable(cset); }
2674 CFCharacterSetPredefinedSet _CFCharacterSetGetKeyedCodingBuiltinType(CFCharacterSetRef cset) { return __CFCSetBuiltinType(cset); }
2675 CFRange _CFCharacterSetGetKeyedCodingRange(CFCharacterSetRef cset) { return CFRangeMake(__CFCSetRangeFirstChar(cset), __CFCSetRangeLength(cset)); }
2676 CFStringRef _CFCharacterSetCreateKeyedCodingString(CFCharacterSetRef cset) { return CFStringCreateWithCharacters(NULL, __CFCSetStringBuffer(cset), __CFCSetStringLength(cset)); }
2677
2678 bool _CFCharacterSetIsInverted(CFCharacterSetRef cset) { return __CFCSetIsInverted(cset); }
2679 void _CFCharacterSetSetIsInverted(CFCharacterSetRef cset, bool flag) { __CFCSetPutIsInverted((CFMutableCharacterSetRef)cset, flag); }
2680
2681