String.subproj/CFCharacterSet.c

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