CFBurstTrie.c

   1 /*
   2  * Copyright (c) 2012 Apple 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
  24 /*  CFBurstTrie.c
  25     Copyright (c) 2008-2012, Apple Inc. All rights reserved.
  26     Responsibility: Jennifer Moore
  27 */
  28
  29 #include "CFInternal.h"
  30 #include "CFBurstTrie.h"
  31 #include "CFByteOrder.h"
  32 #include "CFNumber.h"
  33 #include <stdio.h>
  34 #include <string.h>
  35 #include <stdlib.h>
  36 #include <fcntl.h>
  37 #include <sys/stat.h>
  38 #include <limits.h>
  39 #if DEPLOYMENT_TARGET_MACOSX || DEPLOYMENT_TARGET_EMBEDDED || DEPLOYMENT_TARGET_EMBEDDED_MINI
  40 #include <unistd.h>
  41 #include <sys/param.h>
  42 #include <sys/mman.h>
  43 #endif
  44
  45 #include <errno.h>
  46 #include <assert.h>
  47
  48 #if DEPLOYMENT_TARGET_WINDOWS
  49 #define open _NS_open
  50 #define statinfo _stat
  51 #define stat(x,y) _NS_stat(x,y)
  52 #define __builtin_memcmp(x, y, z) memcmp(x, y, z)
  53 #define __builtin_popcountll(x) popcountll(x)
  54 #define bzero(dst, size)    ZeroMemory(dst, size)
  55 #define S_IWUSR 0
  56 #define S_IRUSR 0
  57
  58 static int pwrite(int fd, const void *buf, size_t nbyte, off_t offset) {
  59     // Get where we are
  60     long pos = _tell(fd);
  61
  62     // Move to new offset
  63     _lseek(fd, offset, SEEK_SET);
  64
  65     // Write data
  66     int res = _write(fd, buf, nbyte);
  67
  68     // Return to previous offset
  69     _lseek(fd, pos, SEEK_SET);
  70
  71     return res;
  72 }
  73
  74 #else
  75 #define statinfo stat
  76 #endif
  77
  78 #if 0
  79 #pragma mark Types and Utilities
  80 #endif
  81
  82 #define MAX_STRING_ALLOCATION_SIZE  342
  83 #define MAX_STRING_SIZE             1024
  84 #define MAX_KEY_LENGTH              MAX_STRING_SIZE * 4
  85 #define CHARACTER_SET_SIZE          256
  86 #define MAX_LIST_SIZE               256 // 64
  87 #define MAX_BITMAP_SIZE             200
  88 #define MAX_BUFFER_SIZE             (4096<<2)
  89
  90 #define NextTrie_GetPtr(p)  (p & ((~(uintptr_t)0)-3))
  91 #define NextTrie_GetKind(p) (p & 3)
  92 #define NextTrie_SetKind(p, kind) (p |= (3&kind))
  93
  94 #define DiskNextTrie_GetPtr(map,offset)  (((uintptr_t)map) + (uintptr_t)(offset & ((~(uintptr_t)0)-3)))
  95 #define DiskNextTrie_GetKind(p) (p & 3)
  96 #define DiskNextTrie_SetKind(p, kind) (p |= (3&kind))
  97
  98 // Use this macro to avoid forgetting to check the pointer before assigning value to it.
  99 #define SetPayload(pointer, value) do { if (pointer) *pointer = value; } while (0)
 100
 101 enum { Nothing = 0, TrieKind = 1, ListKind = 2, CompactTrieKind = 3 };
 102 typedef enum { FailedInsert = 0, NewTerm = 1, ExistingTerm = 2 } CFBTInsertCode;
 103
 104 #pragma pack (1)
 105 typedef uintptr_t NextTrie;
 106
 107 typedef struct _TrieLevel {
 108     NextTrie slots[CHARACTER_SET_SIZE];
 109     uint32_t weight;
 110     uint32_t payload;
 111 } TrieLevel;
 112 typedef TrieLevel *TrieLevelRef;
 113
 114 typedef struct _MapTrieLevel {
 115     uint32_t slots[CHARACTER_SET_SIZE];
 116     uint32_t payload;
 117 } MapTrieLevel;
 118 typedef MapTrieLevel *MapTrieLevelRef;
 119
 120 typedef struct _CompactMapTrieLevel {
 121     uint64_t bitmap[CHARACTER_SET_SIZE / 64];
 122     uint32_t payload;
 123     uint32_t slots[];
 124 } CompactMapTrieLevel;
 125 typedef CompactMapTrieLevel *CompactMapTrieLevelRef;
 126
 127 typedef struct _ListNode {
 128     struct _ListNode *next;
 129     uint32_t weight;
 130     uint32_t payload;
 131     uint16_t length;
 132     UInt8 string[];
 133 }* ListNodeRef;
 134
 135 typedef struct _Page {
 136     uint32_t length;
 137     char data[];
 138 } Page;
 139
 140 typedef struct _PageEntryPacked {
 141     uint8_t pfxLen;
 142     uint16_t strlen;
 143     uint32_t payload;
 144     UInt8 string[];
 145 } PageEntryPacked;
 146
 147 typedef struct _PageEntry {
 148     uint16_t strlen;
 149     uint32_t payload;
 150     UInt8 string[];
 151 } PageEntry;
 152
 153 typedef struct _TrieHeader {
 154     uint32_t signature;
 155     uint32_t rootOffset;
 156     uint32_t count;
 157     uint32_t size;
 158     uint32_t flags;
 159     uint64_t reserved[16];
 160 } TrieHeader;
 161
 162 typedef struct _TrieCursor {
 163     uint64_t signature;
 164     uint64_t counter;
 165     NextTrie next;
 166     uint32_t keylen;
 167     uint32_t prefixlen;
 168     const uint8_t *prefix;
 169     uint8_t key[MAX_KEY_LENGTH];
 170 } TrieCursor;
 171
 172 typedef struct _MapCursor {
 173     uint64_t signature;
 174     TrieHeader *header;
 175     uint32_t next;
 176     uint32_t prefixlen;
 177     uint32_t keylen;
 178     const uint8_t *prefix;
 179     uint8_t key[MAX_STRING_SIZE*4];
 180 } MapCursor;
 181
 182 typedef struct _CompactMapCursor {
 183     uint32_t next;
 184     uint32_t entryOffsetInPage;
 185     uint32_t offsetInEntry;
 186     uint32_t payload;
 187     // On a page, the first entry could has 0 strlen. So we need this variable to tell us whether
 188     // the cursor is merely pointing at the beginning of the page, or the first entry.
 189     // For example, if the trie contains "ab" and "abc", where "a" is stored on an array level,
 190     // while "b" and "bc" are stored on a page level. If we creat a cursor for string "a", this cursor
 191     // will point at the beginning of the page, but not at any particular key. The both entryOffsetInPage and
 192     // offsetInEntry fields of the cursor are set to 0 in this case. Now if we add "a" to the
 193     // trie. the page level will actually contains three entries. The first entry corresponds to string "a".
 194     // That entry has 0 strlen value. If we creat a cursor for string "a" again, this cursor will
 195     // point at the first entry on the page. But the entryOffsetInPage and offsetInEntry fields are still
 196     // set to 0s. So we need an additional variable to make distinction between these two situations.
 197     BOOL isOnPage;
 198 } CompactMapCursor;
 199 typedef struct _CompactMapCursor *MapCursorRef;
 200
 201 enum {
 202     _kCFBurstTrieCursorTrieType = 0,
 203     _kCFBurstTrieCursorMapType
 204 };
 205
 206 typedef struct _CFBurstTrieCursor {
 207     CompactMapCursor mapCursor;
 208     CFIndex cursorType;
 209     CFBurstTrieRef trie;
 210 } _CFBurstTrieCursor;
 211
 212 // ** Legacy
 213 typedef struct _DiskTrieLevel {
 214     uint32_t slots[CHARACTER_SET_SIZE];
 215     uint32_t weight;
 216     uint32_t payload;
 217 } DiskTrieLevel;
 218 typedef DiskTrieLevel *DiskTrieLevelRef;
 219
 220 typedef struct _CompactDiskTrieLevel {
 221     uint64_t bitmap[CHARACTER_SET_SIZE / 64]; // CHARACTER_SET_SIZE / 64bits per word
 222     uint32_t weight;
 223     uint32_t payload;
 224     uint32_t slots[];
 225 } CompactDiskTrieLevel;
 226 typedef CompactDiskTrieLevel *CompactDiskTrieLevelRef;
 227
 228 typedef struct _StringPage {
 229     uint32_t length;
 230     char data[];
 231 } StringPage;
 232
 233 typedef struct _StringPageEntryPacked {
 234     uint8_t pfxLen;
 235     uint16_t strlen;    // make uint8_t if possible
 236     uint32_t payload;
 237     char string[];
 238 } StringPageEntryPacked;
 239
 240 typedef struct _StringPageEntry {
 241     uint16_t strlen;    // make uint8_t if possible
 242     uint32_t payload;
 243     char string[];
 244 } StringPageEntry;
 245
 246 typedef struct _fileHeader {
 247     uint32_t signature;
 248     uint32_t rootOffset;
 249     uint32_t count;
 250     uint32_t size;
 251     uint32_t flags;
 252 } fileHeader;
 253 // **
 254 #pragma pack()
 255
 256 struct _CFBurstTrie {
 257     union {
 258         TrieLevel root;
 259         DiskTrieLevel diskRoot;
 260         MapTrieLevel maproot;
 261     };
 262     char *mapBase;
 263     uint32_t mapSize;
 264     uint32_t mapOffset;
 265     uint32_t cflags;
 266     uint32_t count;
 267     uint32_t containerSize;
 268     int retain;
 269 #if DEPLOYMENT_TARGET_WINDOWS
 270     HANDLE mapHandle;
 271     HANDLE mappedFileHandle;
 272 #endif
 273 };
 274
 275 #if 0
 276 #pragma mark -
 277 #pragma mark Forward declarations
 278 #endif
 279
 280 typedef struct _TraverseContext {
 281     void *context;
 282     void (*callback)(void*, const UInt8*, uint32_t, uint32_t);
 283 } TraverseContext;
 284
 285 bool foundKey(void *context, const uint8_t *key, uint32_t payload, bool exact)
 286 {
 287     if (context != NULL) {
 288         TraverseContext *ctx = (TraverseContext *)context;
 289         if (ctx->context && ctx->callback) {
 290             ctx->callback(ctx->context, key, 1, payload);
 291         }
 292     }
 293     return false;
 294 }
 295
 296 void CFBurstTrieTraverseWithCursor(CFBurstTrieRef trie, const uint8_t *prefix, uint32_t prefixLen, void **cursor, void *ctx, bool (*callback)(void *, const uint8_t *, uint32_t, bool));
 297
 298 static CFBTInsertCode addCFBurstTrieLevel(CFBurstTrieRef trie, TrieLevelRef root, const uint8_t *key, uint32_t keylen, uint32_t weight, uint32_t payload);
 299
 300 static void findCFBurstTrieLevel(CFBurstTrieRef trie, TrieCursor *cursor, bool exactmatch, void *ctx, bool (*callback)(void*, const uint8_t*, uint32_t, bool));
 301 static void findCFBurstTrieMappedLevel(CFBurstTrieRef trie, MapCursor *cursor, bool exactmatch, void *ctx, bool (*callback)(void*, const uint8_t*, uint32_t, bool));
 302 static void traverseCFBurstTrieLevel(CFBurstTrieRef trie, TrieLevelRef root, TrieCursor *cursor, bool exactmatch, void *ctx, bool (*callback)(void *, const uint8_t *, uint32_t, bool));
 303 static void traverseCFBurstTrieMappedLevel(CFBurstTrieRef trie, MapTrieLevelRef root, MapCursor *cursor, bool exactmatch, void *ctx, bool (*callback)(void *, const uint8_t *, uint32_t, bool));
 304 static void traverseCFBurstTrieCompactMappedLevel(CFBurstTrieRef trie, CompactMapTrieLevelRef root, MapCursor *cursor, bool exactmatch, void *ctx, bool (*callback)(void *, const uint8_t *, uint32_t, bool));
 305 static void traverseCFBurstTrieWithCursor(CFBurstTrieRef trie, const uint8_t *prefix, uint32_t prefixLen, void **cursor, bool exactmatch, void *ctx, bool (*callback)(void *, const uint8_t *, uint32_t, bool));
 306
 307 static size_t serializeCFBurstTrie(CFBurstTrieRef trie, size_t start_offset, int fd);
 308
 309 static Boolean burstTrieMappedFind(DiskTrieLevelRef trie, char *map, const UInt8 *key, uint32_t length, uint32_t *payload, bool prefix);
 310 static Boolean burstTrieMappedPageFind(StringPage *page, const UInt8 *key, uint32_t length, uint32_t *payload, bool prefix);
 311 static Boolean burstTrieCompactTrieMappedFind(CompactDiskTrieLevelRef trie, char *map, const UInt8 *key, uint32_t length, uint32_t *payload, bool prefix);
 312
 313 static void destroyCFBurstTrie(CFBurstTrieRef trie);
 314 static void finalizeCFBurstTrie(TrieLevelRef trie);
 315 static void finalizeCFBurstTrieList(ListNodeRef node);
 316
 317 static int nodeWeightCompare(const void *a, const void *b);
 318 static int nodeStringCompare(const void *a, const void *b);
 319
 320 bool foundKey(void *context, const uint8_t *key, uint32_t payload, bool exact);
 321 bool containsKey(void *context, const uint8_t *key, uint32_t payload, bool exact);
 322
 323 static CFIndex burstTrieConvertCharactersToUTF8(UniChar *chars, CFIndex numChars, UInt8 *buffer);
 324
 325 static Boolean advanceMapCursor(CFBurstTrieRef trie, CompactMapCursor *cursor, const UInt8* bytes, CFIndex length);
 326 static Boolean getMapCursorPayload(CFBurstTrieRef trie, const CompactMapCursor *cursor, uint32_t *payload);
 327 static void copyMapCursor(const CompactMapCursor *source, CompactMapCursor* destination);
 328 static Boolean areMapCursorsEqual(const CompactMapCursor *lhs, const CompactMapCursor *rhs);
 329 static void traverseFromMapCursor(CFBurstTrieRef trie, CompactMapCursor *cursor, UInt8* bytes, uint32_t capacity, uint32_t length, Boolean *stop, void *ctx, CFBurstTrieTraversalCallback callback);
 330 static Boolean getMapCursorPayloadFromPackedPageEntry(PageEntryPacked *entry, const CompactMapCursor *cursor, uint32_t *payload);
 331 static Boolean getMapCursorPayloadFromPageEntry(PageEntry *entry, const CompactMapCursor *cursor, uint32_t *payload);
 332
 333 #if 0
 334 #pragma mark -
 335 #pragma mark Core Foundation boilerplate
 336 #endif
 337
 338 static const void *_CFBurstTrieRetainCallback(CFAllocatorRef allocator, const void *value) {
 339     CFBurstTrieRetain((CFBurstTrieRef)value);
 340     return value;
 341 }
 342
 343 static void _CFBurstTrieReleaseCallback(CFAllocatorRef allocator, const void *value) {
 344     CFBurstTrieRelease((CFBurstTrieRef)value);
 345 }
 346
 347 const CFDictionaryValueCallBacks kCFBurstTrieValueCallbacks = {0, _CFBurstTrieRetainCallback, _CFBurstTrieReleaseCallback, NULL, NULL};
 348
 349 #if 0
 350 #pragma mark -
 351 #pragma mark Public Interface
 352 #endif
 353
 354 CFBurstTrieRef CFBurstTrieCreateWithOptions(CFDictionaryRef options) {
 355     CFBurstTrieRef trie = NULL;
 356     trie = (CFBurstTrieRef) calloc(1, sizeof(struct _CFBurstTrie));
 357     trie->containerSize = MAX_LIST_SIZE;
 358
 359     CFNumberRef valueAsCFNumber;
 360     if (CFDictionaryGetValueIfPresent(options, kCFBurstTrieCreationOptionNameContainerSize, (const void **)&valueAsCFNumber)) {
 361         int value;
 362         CFNumberGetValue(valueAsCFNumber, kCFNumberIntType, &value);
 363         trie->containerSize = value > 2 && value < 4096 ? value : MAX_LIST_SIZE;
 364     }
 365     trie->retain = 1;
 366     return trie;
 367 }
 368
 369 CFBurstTrieRef CFBurstTrieCreate() {
 370     CFBurstTrieRef trie = NULL;
 371     int listSize = MAX_LIST_SIZE;
 372     CFNumberRef value = CFNumberCreate(kCFAllocatorDefault, kCFNumberIntType, &listSize);
 373     CFMutableDictionaryRef options = CFDictionaryCreateMutable(kCFAllocatorDefault, 1, NULL, NULL);
 374     CFDictionarySetValue(options, kCFBurstTrieCreationOptionNameContainerSize, value);
 375     trie = CFBurstTrieCreateWithOptions(options);
 376     CFRelease(value);
 377     CFRelease(options);
 378     return trie;
 379 }
 380
 381 CFBurstTrieRef CFBurstTrieCreateFromFile(CFStringRef path) {
 382     struct statinfo sb;
 383     char filename[PATH_MAX];
 384     int fd;
 385
 386     /* Check valid path name */
 387     if (!CFStringGetCString(path, filename, PATH_MAX, kCFStringEncodingUTF8)) return NULL;
 388
 389     /* Check if file exists */
 390     if (stat(filename, &sb) != 0) return NULL;
 391
 392     /* Check if file can be opened */
 393     if ((fd=open(filename, CF_OPENFLGS|O_RDONLY)) < 0) return NULL;
 394
 395 #if DEPLOYMENT_TARGET_WINDOWS
 396     HANDLE mappedFileHandle = (HANDLE)_get_osfhandle(fd);
 397     if (!mappedFileHandle) return NULL;
 398
 399     HANDLE mapHandle = CreateFileMapping(mappedFileHandle, NULL, PAGE_READONLY, 0, 0, NULL);
 400     if (!mapHandle) return NULL;
 401
 402     char *map = (char *)MapViewOfFile(mapHandle, FILE_MAP_READ, 0, 0, sb.st_size);
 403     if (!map) return NULL;
 404 #else
 405     char *map = mmap(0, sb.st_size, PROT_READ, MAP_FILE|MAP_SHARED, fd, 0);
 406 #endif
 407
 408     CFBurstTrieRef trie = NULL;
 409     TrieHeader *header = (TrieHeader *)map;
 410
 411     if (((uint32_t*)map)[0] == 0xbabeface) {
 412         trie = (CFBurstTrieRef) calloc(1, sizeof(struct _CFBurstTrie));
 413         trie->mapBase = map;
 414         trie->mapSize = CFSwapInt32LittleToHost(sb.st_size);
 415         trie->mapOffset = CFSwapInt32LittleToHost(((fileHeader*)trie->mapBase)->rootOffset);
 416         trie->cflags = CFSwapInt32LittleToHost(((fileHeader*)trie->mapBase)->flags);
 417         trie->count = CFSwapInt32LittleToHost(((fileHeader*)trie->mapBase)->count);
 418         trie->retain = 1;
 419 #if DEPLOYMENT_TARGET_WINDOWS
 420         trie->mappedFileHandle = mappedFileHandle;
 421         trie->mapHandle = mapHandle;
 422 #else
 423         // On Windows, the file being mapped must stay open as long as the map exists. Don't close it early. Other platforms close it here.
 424         close(fd);
 425 #endif
 426     } else if (header->signature == 0xcafebabe || header->signature == 0x0ddba11) {
 427         trie = (CFBurstTrieRef) calloc(1, sizeof(struct _CFBurstTrie));
 428         trie->mapBase = map;
 429         trie->mapSize = CFSwapInt32LittleToHost(sb.st_size);
 430         trie->cflags = CFSwapInt32LittleToHost(header->flags);
 431         trie->count = CFSwapInt32LittleToHost(header->count);
 432         trie->retain = 1;
 433 #if DEPLOYMENT_TARGET_WINDOWS
 434         trie->mappedFileHandle = mappedFileHandle;
 435         trie->mapHandle = mapHandle;
 436 #else
 437         // On Windows, the file being mapped must stay open as long as the map exists. Don't close it early. Other platforms close it here.
 438         close(fd);
 439 #endif
 440     }
 441     return trie;
 442 }
 443
 444 CFBurstTrieRef CFBurstTrieCreateFromMapBytes(char *mapBase) {
 445     CFBurstTrieRef trie = NULL;
 446     TrieHeader *header = (TrieHeader *)mapBase;
 447
 448     if (mapBase && ((uint32_t*)mapBase)[0] == 0xbabeface) {
 449         trie = (CFBurstTrieRef) malloc(sizeof(struct _CFBurstTrie));
 450         trie->mapBase = mapBase;
 451         trie->mapSize = CFSwapInt32LittleToHost(((fileHeader*)trie->mapBase)->size);
 452         trie->mapOffset = CFSwapInt32LittleToHost(((fileHeader*)trie->mapBase)->rootOffset);
 453         trie->cflags = CFSwapInt32LittleToHost(((fileHeader*)trie->mapBase)->flags);
 454         trie->count = CFSwapInt32LittleToHost(((fileHeader*)trie->mapBase)->count);
 455         trie->retain = 1;
 456     } else if (mapBase && (header->signature == 0xcafebabe || header->signature == 0x0ddba11)) {
 457         trie = (CFBurstTrieRef) malloc(sizeof(struct _CFBurstTrie));
 458         trie->mapBase = mapBase;
 459         trie->mapSize = CFSwapInt32LittleToHost(header->size);
 460         trie->cflags = CFSwapInt32LittleToHost(header->flags);
 461         trie->count = CFSwapInt32LittleToHost(header->count);
 462         trie->retain = 1;
 463     }
 464     return trie;
 465 }
 466
 467 Boolean CFBurstTrieInsert(CFBurstTrieRef trie, CFStringRef term, CFRange termRange, CFIndex payload) {
 468     return CFBurstTrieAddWithWeight(trie, term, termRange, 1, (uint32_t)payload);
 469 }
 470
 471 Boolean CFBurstTrieAdd(CFBurstTrieRef trie, CFStringRef term, CFRange termRange, uint32_t payload) {
 472     return CFBurstTrieAddWithWeight(trie, term, termRange, 1, payload);
 473 }
 474
 475 Boolean CFBurstTrieInsertCharacters(CFBurstTrieRef trie, UniChar *chars, CFIndex numChars, CFIndex payload) {
 476     return CFBurstTrieAddCharactersWithWeight(trie, chars, numChars, 1, (uint32_t)payload);
 477 }
 478
 479 Boolean CFBurstTrieAddCharacters(CFBurstTrieRef trie, UniChar *chars, CFIndex numChars, uint32_t payload) {
 480     return CFBurstTrieAddCharactersWithWeight(trie, chars, numChars, 1, payload);
 481 }
 482
 483 Boolean CFBurstTrieInsertUTF8String(CFBurstTrieRef trie, UInt8 *chars, CFIndex numChars, CFIndex payload) {
 484     return CFBurstTrieAddUTF8StringWithWeight(trie, chars, numChars, 1, (uint32_t)payload);
 485 }
 486
 487 Boolean CFBurstTrieAddUTF8String(CFBurstTrieRef trie, UInt8 *chars, CFIndex numChars, uint32_t payload) {
 488     return CFBurstTrieAddUTF8StringWithWeight(trie, chars, numChars, 1, payload);
 489 }
 490
 491 Boolean CFBurstTrieInsertWithWeight(CFBurstTrieRef trie, CFStringRef term, CFRange termRange, CFIndex weight, CFIndex payload) {
 492     return CFBurstTrieAddWithWeight(trie, term, termRange, weight, (uint32_t)payload);
 493 }
 494
 495 Boolean CFBurstTrieAddWithWeight(CFBurstTrieRef trie, CFStringRef term, CFRange termRange, uint32_t weight, uint32_t payload) {
 496     Boolean success = false;
 497     CFIndex size = MAX_STRING_ALLOCATION_SIZE;
 498     CFIndex bytesize = termRange.length * 4; //** 4-byte max character size
 499     if (!trie->mapBase && termRange.length < MAX_STRING_SIZE && payload > 0) {
 500         CFIndex length;
 501         UInt8 buffer[MAX_STRING_ALLOCATION_SIZE + 1];
 502         UInt8 *key = buffer;
 503         if (bytesize >= size) {
 504             size = bytesize;
 505             key = (UInt8 *) malloc(sizeof(UInt8) * size + 1);
 506         }
 507         CFStringGetBytes(term, termRange, kCFStringEncodingUTF8, (UInt8)'-', (Boolean)0, key, size, &length);
 508         key[length] = 0;
 509
 510         success = CFBurstTrieAddUTF8StringWithWeight(trie, key, length, weight, payload);
 511         if (buffer != key) free(key);
 512     }
 513     return success;
 514 }
 515
 516 Boolean CFBurstTrieInsertCharactersWithWeight(CFBurstTrieRef trie, UniChar *chars, CFIndex numChars, CFIndex weight, CFIndex payload) {
 517     return CFBurstTrieAddCharactersWithWeight(trie, chars, numChars, weight, (uint32_t)payload);
 518 }
 519
 520 Boolean CFBurstTrieAddCharactersWithWeight(CFBurstTrieRef trie, UniChar *chars, CFIndex numChars, uint32_t weight, uint32_t payload) {
 521     Boolean success = false;
 522     CFIndex size = MAX_STRING_ALLOCATION_SIZE;
 523     CFIndex bytesize = numChars * 4; //** 4-byte max character size
 524     if (!trie->mapBase && numChars < MAX_STRING_SIZE && payload > 0) {
 525         CFIndex length;
 526         UInt8 buffer[MAX_STRING_ALLOCATION_SIZE + 1];
 527         UInt8 *key = buffer;
 528         if (bytesize >= size) {
 529             size = bytesize;
 530             key = (UInt8 *) malloc(sizeof(UInt8) * size + 1);
 531         }
 532         length = burstTrieConvertCharactersToUTF8(chars, numChars, key);
 533         key[length] = 0;
 534
 535         success = CFBurstTrieAddUTF8StringWithWeight(trie, key, length, weight, payload);
 536         if (buffer != key) free(key);
 537     }
 538     return success;
 539 }
 540
 541 Boolean CFBurstTrieInsertUTF8StringWithWeight(CFBurstTrieRef trie, UInt8 *chars, CFIndex numChars, CFIndex weight, CFIndex payload) {
 542     return CFBurstTrieAddUTF8StringWithWeight(trie, chars, numChars, weight, (uint32_t)payload);
 543 }
 544
 545 Boolean CFBurstTrieAddUTF8StringWithWeight(CFBurstTrieRef trie, UInt8 *chars, CFIndex numChars, uint32_t weight, uint32_t payload) {
 546     CFBTInsertCode code = FailedInsert;
 547
 548     if (!trie->mapBase && numChars < MAX_STRING_SIZE*4 && payload > 0) {
 549         code = addCFBurstTrieLevel(trie, &trie->root, chars, numChars, weight, payload);
 550         if (code == NewTerm) trie->count++;
 551     }
 552     return code > FailedInsert;
 553 }
 554
 555 Boolean CFBurstTrieFind(CFBurstTrieRef trie, CFStringRef term, CFRange termRange, CFIndex *payload) {
 556     uint32_t p;
 557     if (CFBurstTrieContains(trie, term, termRange, &p)) {
 558         SetPayload(payload, p);
 559         return true;
 560     }
 561     return false;
 562 }
 563
 564 Boolean CFBurstTrieContains(CFBurstTrieRef trie, CFStringRef term, CFRange termRange, uint32_t *payload) {
 565     Boolean success = false;
 566     CFIndex size = MAX_STRING_ALLOCATION_SIZE;
 567     CFIndex bytesize = termRange.length * 4; //** 4-byte max character size
 568     if (termRange.length < MAX_STRING_SIZE) {
 569         CFIndex length;
 570         UInt8 buffer[MAX_STRING_ALLOCATION_SIZE+1];
 571         UInt8 *key = buffer;
 572         if (bytesize >= size) {
 573             size = bytesize;
 574             key = (UInt8 *) malloc(sizeof(UInt8) * size + 1);
 575         }
 576         CFStringGetBytes(term, termRange, kCFStringEncodingUTF8, (UInt8)'-', (Boolean)0, key, size, &length);
 577         key[length] = 0;
 578
 579         success = CFBurstTrieContainsUTF8String(trie, key, length, payload);
 580         if (buffer != key) free(key);
 581     }
 582     return success;
 583 }
 584
 585 Boolean CFBurstTrieFindCharacters(CFBurstTrieRef trie, UniChar *chars, CFIndex numChars, CFIndex *payload) {
 586     uint32_t p;
 587     if (CFBurstTrieContainsCharacters(trie, chars, numChars, &p)) {
 588         SetPayload(payload, p);
 589         return true;
 590     }
 591     return false;
 592 }
 593
 594 Boolean CFBurstTrieContainsCharacters(CFBurstTrieRef trie, UniChar *chars, CFIndex numChars, uint32_t *payload) {
 595     Boolean success = false;
 596     CFIndex size = MAX_STRING_ALLOCATION_SIZE;
 597     CFIndex bytesize = numChars * 4; //** 4-byte max character size
 598     if (numChars < MAX_STRING_SIZE) {
 599         CFIndex length;
 600         UInt8 buffer[MAX_STRING_ALLOCATION_SIZE + 1];
 601         UInt8 *key = buffer;
 602         if (bytesize >= size) {
 603             size = bytesize;
 604             key = (UInt8 *) malloc(sizeof(UInt8) * size + 1);
 605         }
 606         length = burstTrieConvertCharactersToUTF8(chars, numChars, key);
 607         key[length] = 0;
 608
 609         success = CFBurstTrieContainsUTF8String(trie, key, length, payload);
 610         if (buffer != key) free(key);
 611     }
 612     return success;
 613 }
 614
 615 Boolean CFBurstTrieFindUTF8String(CFBurstTrieRef trie, UInt8 *key, CFIndex length, CFIndex *payload) {
 616     uint32_t p;
 617     if (CFBurstTrieContainsUTF8String(trie, key, length, &p)) {
 618         SetPayload(payload, p);
 619         return true;
 620     }
 621     return false;
 622 }
 623
 624 Boolean CFBurstTrieContainsUTF8String(CFBurstTrieRef trie, UInt8 *key, CFIndex length, uint32_t *payload) {
 625     Boolean success = false;
 626     if (length < MAX_STRING_SIZE) {
 627         if (trie->mapBase && ((fileHeader *)trie->mapBase)->signature == 0xbabeface) {
 628             bool prefix = (trie->cflags & kCFBurstTriePrefixCompression);
 629             success = burstTrieMappedFind((DiskTrieLevelRef)(trie->mapBase+CFSwapInt32LittleToHost((((uint32_t*)trie->mapBase)[1]))), trie->mapBase, key, length, payload, prefix);
 630         } else if (trie->mapBase && trie->cflags & (kCFBurstTriePrefixCompression | kCFBurstTrieSortByKey)) {
 631             _CFBurstTrieCursor cursor;
 632             if (!CFBurstTrieSetCursorForBytes(trie, &cursor, key, length))
 633                 return FALSE;
 634             return CFBurstTrieCursorGetPayload(&cursor, payload);
 635         } else {
 636             uint32_t found = 0;
 637             void *cursor = 0;
 638             traverseCFBurstTrieWithCursor(trie, key, length, &cursor, true, &found, containsKey);
 639             if (found) SetPayload(payload, found);
 640             success = found > 0;
 641         }
 642     }
 643     return success;
 644 }
 645
 646 Boolean CFBurstTrieSerialize(CFBurstTrieRef trie, CFStringRef path, CFBurstTrieOpts opts) {
 647     Boolean success = false;
 648     if (trie->mapBase) {
 649         return success;
 650     } else {
 651         int fd;
 652         char filename[PATH_MAX];
 653
 654         /* Check valid path name */
 655         if (!CFStringGetCString(path, filename, PATH_MAX, kCFStringEncodingUTF8)) return success;
 656
 657         /* Check if file can be opened */
 658         if ((fd=open(filename, CF_OPENFLGS|O_RDWR|O_CREAT|O_TRUNC, S_IRUSR|S_IWUSR)) < 0) return success;
 659
 660         if (CFBurstTrieSerializeWithFileDescriptor(trie, fd, opts)) success = true;
 661
 662         close(fd);
 663     }
 664     return success;
 665 }
 666
 667 Boolean CFBurstTrieSerializeWithFileDescriptor(CFBurstTrieRef trie, int fd, CFBurstTrieOpts opts) {
 668     Boolean success = false;
 669     if (!trie->mapBase && fd >= 0) {
 670         off_t start_offset = lseek(fd, 0, SEEK_END);
 671
 672         trie->cflags = opts;
 673         trie->mapSize = serializeCFBurstTrie(trie, start_offset, fd);
 674
 675 #if DEPLOYMENT_TARGET_WINDOWS
 676         HANDLE mappedFileHandle = (HANDLE)_get_osfhandle(fd);
 677         // We need to make sure we have our own handle to keep this file open as long as the mmap lasts
 678         DuplicateHandle(GetCurrentProcess(), mappedFileHandle, GetCurrentProcess(), &mappedFileHandle, 0, 0, DUPLICATE_SAME_ACCESS);
 679         HANDLE mapHandle = CreateFileMapping(mappedFileHandle, NULL, PAGE_READONLY, 0, 0, NULL);
 680         if (!mapHandle) return NULL;
 681         char *map = (char *)MapViewOfFile(mapHandle, FILE_MAP_READ, 0, start_offset, trie->mapSize);
 682         if (!map) return NULL;
 683         trie->mapBase = map;
 684         trie->mapHandle = mapHandle;
 685         trie->mappedFileHandle = mappedFileHandle;
 686 #else
 687         trie->mapBase = mmap(0, trie->mapSize, PROT_READ, MAP_FILE|MAP_SHARED, fd, start_offset);
 688 #endif
 689         success = true;
 690     }
 691
 692     return success;
 693 }
 694
 695 void CFBurstTrieTraverse(CFBurstTrieRef trie, void *ctx, void (*callback)(void*, const UInt8*, uint32_t, uint32_t)) {
 696     TrieHeader *header = (TrieHeader *)trie->mapBase;
 697     if (!trie->mapBase || (header->signature == 0xcafebabe || header->signature == 0x0ddba11)) {
 698         void *cursor = 0;
 699         TraverseContext context;
 700         context.context = ctx;
 701         context.callback = callback;
 702         traverseCFBurstTrieWithCursor(trie, (const uint8_t *)"", 0, &cursor, false, &context, foundKey);
 703     }
 704 }
 705
 706
 707 void CFBurstTrieTraverseWithCursor(CFBurstTrieRef trie, const uint8_t *prefix, uint32_t prefixLen, void **cursor, void *ctx, bool (*callback)(void *, const uint8_t *, uint32_t, bool))
 708 {
 709     traverseCFBurstTrieWithCursor(trie, prefix, prefixLen, cursor, false, ctx, callback);
 710 }
 711
 712 void CFBurstTriePrint(CFBurstTrieRef trie) {
 713
 714 }
 715
 716 CFIndex CFBurstTrieGetCount(CFBurstTrieRef trie) {
 717     return trie->count;
 718 }
 719
 720 CFBurstTrieRef CFBurstTrieRetain(CFBurstTrieRef trie) {
 721     trie->retain++;
 722     return trie;
 723 }
 724
 725 void CFBurstTrieRelease(CFBurstTrieRef trie) {
 726     trie->retain--;
 727     if (trie->retain == 0) destroyCFBurstTrie(trie);
 728     return;
 729 }
 730
 731 Boolean CFBurstTrieSetCursorForBytes(CFBurstTrieRef trie, CFBurstTrieCursorRef cursor, const UInt8* bytes, CFIndex length)
 732 {
 733     if (!trie->mapBase || !(trie->cflags & (kCFBurstTriePrefixCompression | kCFBurstTrieSortByKey))) {
 734         //fprintf(stderr, "CFBurstTrieCreateCursorForBytes() only support file based trie in prefix compression format.\n");
 735         return FALSE;
 736     }
 737
 738     TrieHeader *header = (TrieHeader*)trie->mapBase;
 739     if (length < 0 || !trie)
 740         return FALSE;
 741
 742     cursor->trie = trie;
 743     if (trie->mapBase) {
 744         cursor->cursorType = _kCFBurstTrieCursorMapType;
 745         cursor->mapCursor.next = header->rootOffset;
 746         cursor->mapCursor.isOnPage = FALSE;
 747         cursor->mapCursor.entryOffsetInPage = 0;
 748         cursor->mapCursor.offsetInEntry = 0;
 749         cursor->mapCursor.payload = 0;
 750     } else
 751         assert(false);
 752
 753     if (!bytes || length == 0)
 754         return TRUE;
 755
 756     return CFBurstTrieCursorAdvanceForBytes(cursor, bytes, length);
 757 }
 758
 759
 760 CFBurstTrieCursorRef CFBurstTrieCreateCursorForBytes(CFBurstTrieRef trie, const UInt8* bytes, CFIndex length)
 761 {
 762     CFBurstTrieCursorRef cursor = (CFBurstTrieCursorRef)calloc(sizeof(_CFBurstTrieCursor), 1);
 763     if (!CFBurstTrieSetCursorForBytes(trie, cursor, bytes, length)) {
 764         CFBurstTrieCursorRelease(cursor);
 765         return NULL;
 766     }
 767     return cursor;
 768 }
 769
 770 CFBurstTrieCursorRef CFBurstTrieCursorCreateByCopy(CFBurstTrieCursorRef cursor)
 771 {
 772     if (!cursor)
 773         return NULL;
 774
 775     CFBurstTrieCursorRef newCursor = (CFBurstTrieCursorRef)calloc(sizeof(_CFBurstTrieCursor), 1);
 776     switch (cursor->cursorType) {
 777         case _kCFBurstTrieCursorMapType:
 778             copyMapCursor(&cursor->mapCursor, &newCursor->mapCursor);
 779             break;
 780         case _kCFBurstTrieCursorTrieType:
 781             assert(false);
 782             break;
 783     }
 784     newCursor->cursorType = cursor->cursorType;
 785     newCursor->trie = cursor->trie;
 786     return newCursor;
 787 }
 788
 789 Boolean CFBurstTrieCursorIsEqual(CFBurstTrieCursorRef lhs, CFBurstTrieCursorRef rhs)
 790 {
 791     if (lhs->trie != rhs->trie || lhs->cursorType != rhs->cursorType)
 792         return FALSE;
 793
 794     if (lhs->cursorType == _kCFBurstTrieCursorMapType)
 795         return areMapCursorsEqual(&lhs->mapCursor, &rhs->mapCursor);
 796     else
 797         return FALSE;
 798 }
 799
 800 Boolean CFBurstTrieCursorAdvanceForBytes(CFBurstTrieCursorRef cursor, const UInt8* bytes, CFIndex length)
 801 {
 802     switch (cursor->cursorType) {
 803         case _kCFBurstTrieCursorMapType: {
 804             CompactMapCursor tempCursor;
 805             copyMapCursor(&cursor->mapCursor, &tempCursor);
 806             if (advanceMapCursor(cursor->trie, (CompactMapCursor*)&cursor->mapCursor, bytes, length))
 807                 return TRUE;
 808             else {
 809                 copyMapCursor(&tempCursor, &cursor->mapCursor);
 810                 return FALSE;
 811             }
 812         }
 813         case _kCFBurstTrieCursorTrieType:
 814             return FALSE;
 815     }
 816     return FALSE;
 817 }
 818
 819 Boolean CFBurstTrieCursorGetPayload(CFBurstTrieCursorRef cursor, uint32_t *payload)
 820 {
 821     switch (cursor->cursorType) {
 822         case _kCFBurstTrieCursorMapType:
 823             return getMapCursorPayload(cursor->trie, (CompactMapCursor*)&cursor->mapCursor, payload);
 824         case _kCFBurstTrieCursorTrieType:
 825             return FALSE;
 826     }
 827     return FALSE;
 828 }
 829
 830 void CFBurstTrieCursorRelease(CFBurstTrieCursorRef cursor)
 831 {
 832     if (!cursor)
 833         return;
 834     free(cursor);
 835 }
 836
 837 void CFBurstTrieTraverseFromCursor(CFBurstTrieCursorRef cursor, void *ctx, CFBurstTrieTraversalCallback callback)
 838 {
 839     if (!cursor)
 840         return;
 841
 842     UInt8 *bytes = (UInt8*)calloc(1, MAX_KEY_LENGTH);
 843     uint32_t capacity = MAX_KEY_LENGTH;
 844     uint32_t length = 0;
 845     Boolean stop = FALSE;
 846     switch (cursor->cursorType) {
 847         case _kCFBurstTrieCursorMapType: {
 848             CompactMapCursor tempCursor;
 849             copyMapCursor(&cursor->mapCursor, &tempCursor);
 850             traverseFromMapCursor(cursor->trie, &tempCursor, bytes, capacity,length, &stop, ctx, callback);
 851             break;
 852         }
 853         case _kCFBurstTrieCursorTrieType:
 854             break;
 855     }
 856     free(bytes);
 857 }
 858
 859 #if 0
 860 #pragma mark -
 861 #pragma mark Insertion
 862 #endif
 863
 864 static ListNodeRef makeCFBurstTrieListNode(const uint8_t *key, uint32_t keylen, uint32_t weight, uint32_t payload) {
 865     ListNodeRef node = (ListNodeRef) calloc(1, sizeof(*node) + keylen + 1);
 866     memcpy(node->string, key, keylen);
 867     node->string[keylen] = 0;
 868     node->next = 0;
 869     node->length = keylen;
 870     node->weight = weight;
 871     node->payload = payload;
 872     return node;
 873 }
 874
 875 static void addCFBurstTrieBurstLevel(CFBurstTrieRef trie, TrieLevelRef root, const uint8_t *key, uint32_t keylen, uint32_t weight, uint32_t payload) {
 876     if (keylen) {
 877         NextTrie next = root->slots[*key];
 878         ListNodeRef newNode = makeCFBurstTrieListNode(key+1, keylen-1, weight, payload);
 879         newNode->weight = weight;
 880         newNode->next = (ListNodeRef) NextTrie_GetPtr(next);
 881         next = (uintptr_t) newNode;
 882         NextTrie_SetKind(next, ListKind);
 883         root->slots[*key] = next;
 884     } else {
 885         // ** Handle payload.
 886         root->weight = weight;
 887         root->payload = payload;
 888     }
 889 }
 890
 891 static TrieLevelRef burstCFBurstTrieLevel(CFBurstTrieRef trie, ListNodeRef list, uint32_t listCount) {
 892     TrieLevelRef newLevel = (TrieLevelRef) calloc(1, sizeof(struct _TrieLevel));
 893     while (list) {
 894         addCFBurstTrieBurstLevel(trie, newLevel, list->string, list->length, list->weight, list->payload);
 895         ListNodeRef temp = list;
 896         list = list->next;
 897         free(temp);
 898     }
 899     return newLevel;
 900 }
 901
 902 static CFBTInsertCode addCFBurstTrieListNode(CFBurstTrieRef trie, ListNodeRef list, const uint8_t *key, uint32_t keylen, uint32_t weight, uint32_t payload, uint32_t *listCount)
 903 {
 904     CFBTInsertCode code = FailedInsert;
 905     uint32_t count = 1;
 906
 907     ListNodeRef last = list;
 908     while (list) {
 909         if (list->length == keylen && memcmp(key, list->string, keylen) == 0) {
 910             list->weight += weight;
 911             list->payload = payload;
 912             code = ExistingTerm;
 913             break;
 914         } else {
 915             count++;
 916             last = list;
 917             list = list->next;
 918         }
 919     }
 920
 921     if (!list) {
 922         last->next = makeCFBurstTrieListNode(key, keylen, weight, payload);
 923         code = NewTerm;
 924     }
 925
 926     *listCount = count;
 927     return code;
 928 }
 929
 930 static CFBTInsertCode addCFBurstTrieLevel(CFBurstTrieRef trie, TrieLevelRef root, const uint8_t *key, uint32_t keylen, uint32_t weight, uint32_t payload)
 931 {
 932     CFBTInsertCode code = FailedInsert;
 933     if (keylen) {
 934         NextTrie next = root->slots[*key];
 935         if (NextTrie_GetKind(next) == TrieKind) {
 936             TrieLevelRef nextLevel = (TrieLevelRef) NextTrie_GetPtr(next);
 937             code = addCFBurstTrieLevel(trie, nextLevel, key+1, keylen-1, weight, payload);
 938         } else {
 939             if (NextTrie_GetKind(next) == ListKind) {
 940                 uint32_t listCount;
 941                 ListNodeRef listNode = (ListNodeRef) NextTrie_GetPtr(next);
 942                 code = addCFBurstTrieListNode(trie, listNode, key+1, keylen-1, weight, payload, &listCount);
 943                 if (listCount > trie->containerSize) {
 944                     next = (uintptr_t) burstCFBurstTrieLevel(trie, listNode, listCount);
 945                     NextTrie_SetKind(next, TrieKind);
 946                 }
 947             } else {
 948                 // ** Make a new list node
 949                 next = (uintptr_t) makeCFBurstTrieListNode(key+1, keylen-1, weight, payload);
 950                 NextTrie_SetKind(next, ListKind);
 951                 code = NewTerm;
 952             }
 953             root->slots[*key] = next;
 954         }
 955     } else {
 956         // ** Handle payload
 957         if (!root->weight) code = NewTerm;
 958         else code = ExistingTerm;
 959         root->weight += weight;
 960         root->payload = payload;
 961     }
 962
 963     return code;
 964 }
 965 #if 0
 966 #pragma mark -
 967 #pragma mark Searching
 968 #endif
 969 static void findCFBurstTrieList(CFBurstTrieRef trie, TrieCursor *cursor, void *ctx, bool (*callback)(void*, const uint8_t*, uint32_t, bool))
 970 {
 971     ListNodeRef list = (ListNodeRef)NextTrie_GetPtr(cursor->next);
 972     int len = cursor->prefixlen-cursor->keylen;
 973     len = len <= 0 ? 0 : len;
 974     while (list) {
 975         int lencompare = list->length-len;
 976         if (list->length >= len &&
 977             (len == 0 || memcmp(list->string, cursor->prefix+cursor->keylen, len) == 0)) {
 978             memcpy(cursor->key+cursor->keylen, list->string, list->length);
 979             cursor->key[cursor->keylen+list->length] = 0;
 980             cursor->next = (NextTrie)list;
 981             if (list->payload && callback(ctx, cursor->key, list->payload, lencompare==0)) return;
 982         }
 983         list = list->next;
 984     }
 985 }
 986
 987 static void findCFBurstTrieMappedPage(CFBurstTrieRef trie, MapCursor *cursor, void *ctx, bool (*callback)(void*, const uint8_t*, uint32_t, bool))
 988 {
 989     Page *page = (Page *)DiskNextTrie_GetPtr(trie->mapBase, cursor->next);
 990     uint32_t end = page->length;
 991     uint32_t cur = 0;
 992     int len = cursor->prefixlen-cursor->keylen;
 993     len = len <= 0 ? 0 : len;
 994     if (trie->cflags & kCFBurstTriePrefixCompression) {
 995         uint8_t pfx[CHARACTER_SET_SIZE];
 996         PageEntryPacked *lastEntry = 0;
 997         while (cur < end) {
 998             PageEntryPacked *entry = (PageEntryPacked *)&page->data[cur];
 999             int lencompare = (entry->strlen+entry->pfxLen)-len;
1000             if (lastEntry && entry->pfxLen>lastEntry->pfxLen) memcpy(pfx+lastEntry->pfxLen, lastEntry->string, entry->pfxLen-lastEntry->pfxLen);
1001             if (lencompare >= 0 &&
1002                 (len == 0 || (__builtin_memcmp(pfx, cursor->prefix+cursor->keylen, entry->pfxLen) == 0 &&
1003                               __builtin_memcmp(entry->string, cursor->prefix+cursor->keylen+entry->pfxLen, cursor->prefixlen-cursor->keylen-entry->pfxLen) == 0))) {
1004                 memcpy(cursor->key+cursor->keylen, pfx, entry->pfxLen);
1005                 memcpy(cursor->key+cursor->keylen+entry->pfxLen, entry->string, entry->strlen);
1006                 cursor->key[cursor->keylen+entry->pfxLen+entry->strlen] = 0;
1007                 if (entry->payload && callback(ctx, (const uint8_t *)cursor->key, entry->payload, lencompare==0)) return;
1008             }
1009             lastEntry = entry;
1010             cur += sizeof(*entry) + entry->strlen;
1011         }
1012     } else {
1013         while (cur < end) {
1014             PageEntry *entry = (PageEntry *)&page->data[cur];
1015             int lencompare = entry->strlen-len;
1016             if (lencompare >= 0 && __builtin_memcmp(entry->string, cursor->prefix+cursor->keylen, len) == 0) {
1017                 memcpy(cursor->key+cursor->keylen, entry->string, entry->strlen);
1018                 cursor->key[cursor->keylen+entry->strlen] = 0;
1019                 if (entry->payload && callback(ctx, (const uint8_t *)cursor->key, entry->payload, lencompare==0)) return;
1020             }
1021             cur += sizeof(*entry) + entry->strlen;
1022         }
1023     }
1024 }
1025
1026
1027 static void findCFBurstTrieLevel(CFBurstTrieRef trie, TrieCursor *cursor, bool exactmatch, void *ctx, bool (*callback)(void*, const uint8_t*, uint32_t, bool))
1028 {
1029     if (cursor->keylen < cursor->prefixlen) {
1030         cursor->next = ((TrieLevelRef)NextTrie_GetPtr(cursor->next))->slots[cursor->prefix[cursor->keylen]];
1031         cursor->key[cursor->keylen++] = cursor->prefix[cursor->keylen];
1032
1033         if (NextTrie_GetKind(cursor->next) == TrieKind) {
1034             findCFBurstTrieLevel(trie, cursor, exactmatch, ctx, callback);
1035         } else if (NextTrie_GetKind(cursor->next) == ListKind) {
1036             findCFBurstTrieList(trie, cursor, ctx, callback);
1037         }
1038     } else {
1039         TrieLevelRef root = (TrieLevelRef)NextTrie_GetPtr(cursor->next);
1040         if (root->payload && callback(ctx, cursor->key, root->payload, cursor->prefixlen==cursor->keylen)) return;
1041         if (cursor->keylen == cursor->prefixlen && exactmatch) return;
1042         traverseCFBurstTrieLevel(trie, root, cursor, exactmatch, ctx, callback);
1043     }
1044 }
1045
1046 static void findCFBurstTrieCompactMappedLevel(CFBurstTrieRef trie, MapCursor *cursor, bool exactmatch, void *ctx, bool (*callback)(void*, const uint8_t*, uint32_t, bool))
1047 {
1048     CompactMapTrieLevelRef root = (CompactMapTrieLevelRef)DiskNextTrie_GetPtr(trie->mapBase, cursor->next);
1049     if (cursor->keylen < cursor->prefixlen) {
1050         uint8_t mykey = *(cursor->prefix+cursor->keylen);
1051         cursor->key[cursor->keylen++] = *(cursor->prefix+cursor->keylen);
1052
1053         uint8_t slot = mykey / 64;
1054         uint8_t bit = mykey % 64;
1055         uint32_t item = 0;
1056         uint64_t bword = root->bitmap[slot];
1057
1058         if (bword & (1ull << bit)) {
1059             // ** Count all the set bits up to this bit
1060             for (int i=0; i < slot; i++) item += __builtin_popcountll(root->bitmap[i]);
1061             item += __builtin_popcountll(bword & ((1ull << bit)-1));
1062             uint32_t offset = root->slots[item];
1063             cursor->next = offset;
1064
1065             if (DiskNextTrie_GetKind(offset) == TrieKind) {
1066                 findCFBurstTrieMappedLevel(trie, cursor, exactmatch, ctx, callback);
1067             } else if (DiskNextTrie_GetKind(offset) == CompactTrieKind) {
1068                 findCFBurstTrieCompactMappedLevel(trie, cursor, exactmatch, ctx, callback);
1069             } else if (DiskNextTrie_GetKind(offset) == ListKind) {
1070                 findCFBurstTrieMappedPage(trie, cursor, ctx, callback);
1071             }
1072         }
1073     } else {
1074         if(root->payload && callback(ctx, cursor->key, root->payload, cursor->prefixlen==cursor->keylen)) return;
1075         if (cursor->keylen == cursor->prefixlen && exactmatch) return;
1076         traverseCFBurstTrieCompactMappedLevel(trie, root, cursor,  exactmatch, ctx, callback);
1077     }
1078 }
1079
1080 static void findCFBurstTrieMappedLevel(CFBurstTrieRef trie, MapCursor *cursor, bool exactmatch, void *ctx, bool (*callback)(void*, const uint8_t*, uint32_t, bool))
1081 {
1082     MapTrieLevelRef root = (MapTrieLevelRef)DiskNextTrie_GetPtr(trie->mapBase, cursor->next);
1083     if (cursor->keylen < cursor->prefixlen) {
1084         uint8_t slot = *(cursor->prefix+cursor->keylen);
1085         cursor->next = root->slots[slot];
1086         cursor->key[cursor->keylen++] = slot;
1087
1088         if (DiskNextTrie_GetKind(cursor->next) == TrieKind) {
1089             findCFBurstTrieMappedLevel(trie, cursor, exactmatch, ctx, callback);
1090         } else if (DiskNextTrie_GetKind(cursor->next) == CompactTrieKind) {
1091             findCFBurstTrieCompactMappedLevel(trie, cursor, exactmatch, ctx, callback);
1092         } else if (DiskNextTrie_GetKind(cursor->next) == ListKind) {
1093             findCFBurstTrieMappedPage(trie, cursor, ctx, callback);
1094         }
1095     }  else {
1096         if (root->payload && callback(ctx, cursor->key, root->payload, cursor->prefixlen==cursor->keylen)) return;
1097         if (cursor->keylen == cursor->prefixlen && exactmatch) return;
1098         traverseCFBurstTrieMappedLevel(trie, root, cursor, exactmatch, ctx, callback);
1099     }
1100 }
1101
1102 static void traverseCFBurstTrieLevel(CFBurstTrieRef trie, TrieLevelRef root, TrieCursor *cursor, bool exactmatch, void *ctx, bool (*callback)(void *, const uint8_t *, uint32_t, bool))
1103 {
1104     cursor->key[cursor->keylen] = 0;
1105     uint32_t len = cursor->keylen;
1106     for (int i=0; i < CHARACTER_SET_SIZE; i++) {
1107         NextTrie next = root->slots[i];
1108         cursor->keylen = len;
1109         cursor->key[cursor->keylen++] = i;
1110
1111         if (NextTrie_GetKind(next) == TrieKind) {
1112             TrieLevelRef level = (TrieLevelRef)NextTrie_GetPtr(next);
1113             if (level->payload && callback(ctx, cursor->key, level->payload, cursor->prefixlen==cursor->keylen)) return;
1114             if (cursor->keylen == cursor->prefixlen && exactmatch) return;
1115             traverseCFBurstTrieLevel(trie, level, cursor, exactmatch, ctx, callback);
1116         } else if (NextTrie_GetKind(next) == ListKind) {
1117             cursor->next = next;
1118             cursor->key[cursor->keylen] = 0;
1119             findCFBurstTrieList(trie, cursor, ctx, callback);
1120         }
1121     }
1122 }
1123
1124 static void traverseCFBurstTrieMappedLevel(CFBurstTrieRef trie, MapTrieLevelRef root, MapCursor *cursor, bool exactmatch, void *ctx, bool (*callback)(void *, const uint8_t *, uint32_t, bool))
1125 {
1126     cursor->key[cursor->keylen] = 0;
1127     uint32_t len = cursor->keylen;
1128
1129     for (int i=0; i < CHARACTER_SET_SIZE; i++) {
1130         uint32_t offset = (uint32_t)root->slots[i];
1131         cursor->keylen = len;
1132         cursor->key[cursor->keylen++] = i;
1133
1134         if (DiskNextTrie_GetKind(offset) == TrieKind) {
1135             MapTrieLevelRef level = (MapTrieLevelRef)DiskNextTrie_GetPtr(trie->mapBase, offset);
1136             if (level->payload && callback(ctx, cursor->key, level->payload, cursor->prefixlen==cursor->keylen)) return;
1137             if (cursor->keylen == cursor->prefixlen && exactmatch) return;
1138             traverseCFBurstTrieMappedLevel(trie, level, cursor, exactmatch, ctx, callback);
1139         } else if (DiskNextTrie_GetKind(offset) == CompactTrieKind) {
1140             CompactMapTrieLevelRef level = (CompactMapTrieLevelRef)DiskNextTrie_GetPtr(trie->mapBase, offset);
1141             if (level->payload && callback(ctx, cursor->key, level->payload, cursor->prefixlen==cursor->keylen)) return;
1142             if (cursor->keylen == cursor->prefixlen && exactmatch) return;
1143             traverseCFBurstTrieCompactMappedLevel(trie, level, cursor, exactmatch, ctx, callback);
1144         } else if (DiskNextTrie_GetKind(offset) == ListKind) {
1145             cursor->next = offset;
1146             cursor->key[cursor->keylen] = 0;
1147             findCFBurstTrieMappedPage(trie, cursor, ctx, callback);
1148         }
1149     }
1150 }
1151
1152 static void traverseCFBurstTrieCompactMappedLevel(CFBurstTrieRef trie, CompactMapTrieLevelRef root, MapCursor *cursor, bool exactmatch, void *ctx, bool (*callback)(void *, const uint8_t *, uint32_t, bool))
1153 {
1154     cursor->key[cursor->keylen] = 0;
1155     uint32_t len = cursor->keylen;
1156     for (uint32_t c=0; c < CHARACTER_SET_SIZE; c++) {
1157         //** This could be optimized to remember what the last slot/item was and not count bits over and over.
1158         uint8_t mykey = c;
1159         uint32_t slot = mykey / 64;
1160         uint32_t bit = mykey % 64;
1161         uint32_t item = 0;
1162         uint64_t bword = root->bitmap[slot];
1163         cursor->keylen = len;
1164
1165         if (bword & (1ull << bit)) {
1166             // ** Count all the set bits up to this bit
1167             for (int i=0; i < slot; i++) item += __builtin_popcountll(root->bitmap[i]);
1168             item += __builtin_popcountll(bword & ((1ull << bit)-1));
1169             uint32_t offset = root->slots[item];
1170             cursor->key[cursor->keylen++] = mykey;
1171
1172             if(DiskNextTrie_GetKind(offset) == CompactTrieKind) {
1173                 CompactMapTrieLevelRef level = (CompactMapTrieLevelRef)DiskNextTrie_GetPtr(trie->mapBase, offset);
1174                 if (level->payload && callback(ctx, cursor->key, level->payload, cursor->prefixlen==cursor->keylen)) return;
1175                 if (cursor->keylen == cursor->prefixlen && exactmatch) return;
1176                 traverseCFBurstTrieCompactMappedLevel(trie, level, cursor, exactmatch, ctx, callback);
1177             } else if(DiskNextTrie_GetKind(offset) == TrieKind) {
1178                 traverseCFBurstTrieMappedLevel(trie, (MapTrieLevelRef)DiskNextTrie_GetPtr(trie->mapBase, offset), cursor, exactmatch, ctx, callback);
1179             } else if (DiskNextTrie_GetKind(offset) == ListKind) {
1180                 cursor->next = offset;
1181                 cursor->key[cursor->keylen] = 0;
1182                 findCFBurstTrieMappedPage(trie, cursor, ctx, callback);
1183             }
1184         }
1185     }
1186 }
1187
1188 static void traverseCFBurstTrieWithCursor(CFBurstTrieRef trie, const uint8_t *prefix, uint32_t prefixLen, void **cursor, bool exactmatch, void *ctx, bool (*callback)(void *, const uint8_t *, uint32_t, bool)) {
1189     if (trie->mapBase) {
1190         if (trie->cflags & kCFBurstTriePrefixCompression) {
1191             fprintf(stderr, "Please use CFBurstTrieCursorRef API for file based trie.\n");
1192             return;
1193         } else {
1194             TrieHeader *header = (TrieHeader *)trie->mapBase;
1195             MapCursor csr;
1196             csr.next = header->rootOffset;
1197             csr.prefix = prefix;
1198             csr.prefixlen = prefixLen;
1199             csr.key[0] = 0;
1200             csr.keylen = 0;
1201             findCFBurstTrieMappedLevel(trie, &csr, exactmatch, ctx, callback);
1202         }
1203     } else {
1204         TrieCursor csr;
1205         csr.next = ((unsigned long)&trie->root)|TrieKind;
1206         csr.prefix = prefix;
1207         csr.prefixlen = prefixLen;
1208         csr.key[0] = 0;
1209         csr.keylen = 0;
1210         findCFBurstTrieLevel(trie, &csr, exactmatch, ctx, callback);
1211     }
1212 }
1213
1214 CF_INLINE uint32_t getPackedPageEntrySize(PageEntryPacked *entry)
1215 {
1216     return sizeof(PageEntryPacked) + entry->strlen;
1217 }
1218
1219 CF_INLINE uint32_t getPageEntrySize(PageEntry *entry)
1220 {
1221     return sizeof(PageEntry) + entry->strlen;
1222 }
1223
1224 /*
1225 static void _printPageEntry(PageEntryPacked *entry) {
1226     printf("entry 0x%p:\n", entry);
1227     printf("pfxLen = %d, strLen = %d\n", entry->pfxLen, entry->strlen);
1228     if (entry->strlen > 0) {
1229         printf("string = ");
1230         for (int i = 0; i < entry->strlen; ++i)
1231             printf("%d ", entry->string[i]);
1232         printf("\n");
1233     }
1234     printf("\n");
1235 }
1236 */
1237 static Boolean advanceCursorOnMappedPageForByte(Page *page, CompactMapCursor *cursor, UInt8 byte) {
1238     PageEntryPacked *entry;
1239     Boolean found = FALSE;
1240     uint32_t minPrefixLength = 0;
1241
1242     if (cursor->isOnPage) {
1243         entry = (PageEntryPacked *)&page->data[cursor->entryOffsetInPage];
1244         //_printPageEntry(entry);
1245         BOOL shouldContinue = TRUE;
1246
1247         if (!(cursor->entryOffsetInPage  == 0 && entry->strlen == 0)) {
1248             if (cursor->entryOffsetInPage == entry->strlen - 1) {
1249                 minPrefixLength = entry->pfxLen + entry->strlen;
1250                 cursor->entryOffsetInPage += getPackedPageEntrySize(entry);
1251             } else {
1252                 cursor->offsetInEntry++;
1253                 if (entry->string[cursor->offsetInEntry] == byte)
1254                     found = TRUE;
1255                 else if (entry->string[cursor->offsetInEntry] > byte)
1256                     shouldContinue = FALSE;
1257                 else {
1258                     minPrefixLength = entry->pfxLen + cursor->offsetInEntry;
1259                     cursor->entryOffsetInPage += getPackedPageEntrySize(entry);
1260                 }
1261             }
1262         }
1263
1264         if (found) {
1265             cursor->isOnPage = TRUE;
1266             return TRUE;
1267         } else if (!shouldContinue)
1268             return FALSE;
1269     } else {
1270         cursor->entryOffsetInPage = 0;
1271     }
1272
1273     uint32_t pageSize = page->length - sizeof(Page);
1274     while (cursor->entryOffsetInPage < pageSize) {
1275         entry = (PageEntryPacked *)&page->data[cursor->entryOffsetInPage];
1276         //_printPageEntry(entry);
1277         if (minPrefixLength > entry->pfxLen)
1278             break;
1279         else if (minPrefixLength < entry->pfxLen)
1280             cursor->entryOffsetInPage += getPackedPageEntrySize(entry);
1281         else {
1282             if (entry->strlen == 0)
1283                 cursor->entryOffsetInPage += getPackedPageEntrySize(entry);
1284             else {
1285                 if (entry->string[0] > byte)
1286                     // Entries are sorted alphabetically
1287                     break;
1288                 else if (entry->string[0] < byte)
1289                     cursor->entryOffsetInPage += getPackedPageEntrySize(entry);
1290                 else {
1291                     cursor->offsetInEntry = 0;
1292                     found = TRUE;
1293                     break;
1294                 }
1295             }
1296         }
1297     }
1298
1299     if (found)
1300         cursor->isOnPage = TRUE;
1301
1302     return found;
1303 }
1304
1305 static Boolean advanceCursorMappedPageWithPerfixCompression(Page *page, CompactMapCursor *cursor, const UInt8* bytes, CFIndex length)
1306 {
1307     if (length == 0) {
1308         PageEntryPacked *entry = (PageEntryPacked*)&page->data[0];
1309         if (!cursor->isOnPage) {
1310             cursor->entryOffsetInPage = 0;
1311             cursor->offsetInEntry = 0;
1312             cursor->isOnPage = entry->pfxLen == 0 && entry->strlen == 0;
1313         }
1314         getMapCursorPayloadFromPackedPageEntry(entry, cursor, &cursor->payload);
1315         return TRUE;
1316     }
1317
1318     for (CFIndex i = 0; i < length; ++i) {
1319         if (!advanceCursorOnMappedPageForByte(page, cursor, bytes[i]))
1320             return FALSE;
1321     }
1322     PageEntryPacked *entry = (PageEntryPacked*)&page->data[cursor->entryOffsetInPage];
1323     getMapCursorPayloadFromPackedPageEntry(entry, cursor, &cursor->payload);
1324     return TRUE;
1325 }
1326
1327 static Boolean advanceCursorMappedPageSortedByKey(Page *page, CompactMapCursor *cursor, const UInt8* bytes, CFIndex length)
1328 {
1329     if (length == 0) {
1330         PageEntry*entry = (PageEntry*)&page->data[0];
1331         if (!cursor->isOnPage) {
1332             cursor->entryOffsetInPage = 0;
1333             cursor->offsetInEntry = 0;
1334             cursor->isOnPage = entry->strlen == 0;
1335         }
1336         getMapCursorPayloadFromPageEntry(entry, cursor, &cursor->payload);
1337         return TRUE;
1338     }
1339
1340     PageEntry *entry;
1341     uint32_t pageSize = page->length - sizeof(Page);
1342     const UInt8 * prefix = NULL;
1343     uint32_t prefixLength = 0;
1344
1345     if (cursor->isOnPage) {
1346         entry = (PageEntry*)&page->data[cursor->entryOffsetInPage];
1347         prefix = entry->string;
1348         prefixLength = cursor->offsetInEntry + 1;
1349     }
1350
1351     while (cursor->entryOffsetInPage < pageSize) {
1352         PageEntry *entry = (PageEntry*)&page->data[cursor->entryOffsetInPage];
1353         if (entry->strlen == 0) {
1354             cursor->entryOffsetInPage += getPageEntrySize(entry);
1355             continue;
1356         }
1357
1358         if (entry->strlen <= prefixLength)
1359             return FALSE;
1360         else {
1361             int cmpResult = 0;
1362             if (prefixLength > 0)
1363                 cmpResult = __builtin_memcmp(entry->string, prefix, prefixLength);
1364             if (cmpResult > 0)
1365                 return FALSE;
1366             else if (cmpResult == 0) {
1367                 if (entry->strlen < prefixLength + length) {
1368                     int cmpResult2 = __builtin_memcmp(entry->string + prefixLength, bytes, entry->strlen - prefixLength);
1369                     if (cmpResult2 > 0)
1370                         return FALSE;
1371                     else
1372                         cursor->entryOffsetInPage += getPageEntrySize(entry);
1373                 } else {
1374                     int cmpResult2 = __builtin_memcmp(entry->string + prefixLength, bytes, length);
1375                     if (cmpResult2 > 0)
1376                         return FALSE;
1377                     else if (cmpResult2 == 0) {
1378                         cursor->isOnPage = TRUE;
1379                         cursor->offsetInEntry = prefixLength + length - 1;
1380                         getMapCursorPayloadFromPageEntry(entry, cursor, &cursor->payload);
1381                         return TRUE;
1382                     } else
1383                         cursor->entryOffsetInPage += getPageEntrySize(entry);
1384                 }
1385             } else
1386                 cursor->entryOffsetInPage += getPageEntrySize(entry);
1387         }
1388     }
1389     return FALSE;
1390 }
1391
1392 static Boolean advanceCursorMappedPage(CFBurstTrieRef trie, CompactMapCursor *cursor, const UInt8* bytes, CFIndex length)
1393 {
1394     if (!bytes || length < 0)
1395         return FALSE;
1396
1397     Page *page = (Page *)DiskNextTrie_GetPtr(trie->mapBase, cursor->next);
1398     uint32_t pageSize = page->length - sizeof(Page);
1399     if (pageSize == 0)
1400         return FALSE;
1401
1402     if (trie->cflags & kCFBurstTrieSortByKey)
1403         return advanceCursorMappedPageSortedByKey(page, cursor, bytes, length);
1404     else if (trie->cflags & kCFBurstTriePrefixCompression)
1405         return advanceCursorMappedPageWithPerfixCompression(page, cursor, bytes, length);
1406     else
1407         return FALSE;
1408 }
1409
1410 static Boolean advanceCursorCompactMappedLevel(CFBurstTrieRef trie, CompactMapCursor *cursor, const UInt8* bytes, CFIndex length)
1411 {
1412     if (!bytes || length < 0)
1413         return FALSE;
1414
1415     CompactMapTrieLevelRef root = (CompactMapTrieLevelRef)DiskNextTrie_GetPtr(trie->mapBase, cursor->next);
1416     if (length == 0) {
1417         cursor->payload = root->payload;
1418         return TRUE;
1419     }
1420
1421     uint8_t slot = bytes[0] / 64;
1422     uint8_t bit = bytes[0] % 64;
1423     uint32_t item = 0;
1424     uint64_t bword = root->bitmap[slot];
1425     if (bword & (1ull << bit)) {
1426         // Count all the set bits up to this bit
1427         for (int i = 0; i < slot; ++i)
1428             item += __builtin_popcountll(root->bitmap[i]);
1429         item += __builtin_popcountll(bword & ((1ull << bit)-1));
1430         cursor->next = root->slots[item];
1431         return advanceMapCursor(trie, cursor, bytes + 1, length - 1);
1432     } else {
1433         return FALSE;
1434     }
1435 }
1436
1437 static Boolean advanceCursorMappedLevel(CFBurstTrieRef trie, CompactMapCursor *cursor, const UInt8* bytes, CFIndex length)
1438 {
1439     if (!bytes || length < 0)
1440         return FALSE;
1441
1442     MapTrieLevelRef root = (MapTrieLevelRef)DiskNextTrie_GetPtr(trie->mapBase, cursor->next);
1443     if (length == 0) {
1444         cursor->payload = root->payload;
1445         return TRUE;
1446     }
1447
1448     cursor->next = root->slots[bytes[0]];
1449     return advanceMapCursor(trie, cursor, bytes + 1, length - 1);
1450 }
1451
1452 static Boolean advanceMapCursor(CFBurstTrieRef trie, CompactMapCursor *cursor, const UInt8* bytes, CFIndex length)
1453 {
1454     bool result = FALSE;
1455     switch (DiskNextTrie_GetKind(cursor->next)) {
1456         case TrieKind:
1457             result = advanceCursorMappedLevel(trie, cursor, bytes, length);
1458             break;
1459         case CompactTrieKind:
1460             result = advanceCursorCompactMappedLevel(trie, cursor, bytes, length);
1461             break;
1462         case ListKind:
1463             result = advanceCursorMappedPage(trie, cursor, bytes, length);
1464             break;
1465         case Nothing: {
1466             TrieHeader *header = (TrieHeader*)trie->mapBase;
1467             if (cursor->next == header->rootOffset)
1468                 result = advanceCursorMappedLevel(trie, cursor, bytes, length);
1469         }
1470     }
1471
1472     return result;
1473 }
1474
1475 static void traverseFromMapCursorMappedLevel(CFBurstTrieRef trie, CompactMapCursor *cursor, UInt8* bytes, uint32_t capacity, uint32_t length, Boolean *stop, void *ctx, CFBurstTrieTraversalCallback callback)
1476 {
1477     MapTrieLevelRef root = (MapTrieLevelRef)DiskNextTrie_GetPtr(trie->mapBase, cursor->next);
1478     if (root->payload) {
1479         callback(ctx, bytes, length, root->payload, stop);
1480         if (*stop)
1481             return;
1482     }
1483
1484     if (length >= capacity)
1485         return;
1486
1487     for (int i = 0; i < CHARACTER_SET_SIZE; ++i) {i =
1488         bytes[length] = i;
1489         cursor->next = (uint32_t)root->slots[i];;
1490         cursor->isOnPage = FALSE;
1491         cursor->entryOffsetInPage = 0;
1492         cursor->offsetInEntry = 0;
1493         cursor->payload = 0;
1494         traverseFromMapCursor(trie, cursor, bytes, capacity - 1, length + 1, stop, ctx, callback);
1495         if (*stop)
1496             return;
1497     }
1498 }
1499
1500 static void traverseFromMapCursorCompactMappedLevel(CFBurstTrieRef trie, CompactMapCursor *cursor, UInt8* bytes, uint32_t capacity, uint32_t length, Boolean *stop, void *ctx, CFBurstTrieTraversalCallback callback)
1501 {
1502     CompactMapTrieLevelRef root = (CompactMapTrieLevelRef)DiskNextTrie_GetPtr(trie->mapBase, cursor->next);
1503     if (root->payload) {
1504         callback(ctx, bytes, length, root->payload, stop);
1505         if (*stop)
1506             return;
1507     }
1508
1509     if (length >= capacity)
1510         return;
1511     for (int c = 0; c < CHARACTER_SET_SIZE; ++c) {
1512         bytes[length] = c;
1513         //This could be optimized to remember what the last slot/item was and not count bits over and over.
1514         uint8_t slot = c / 64;
1515         uint8_t bit = c % 64;
1516         uint32_t item = 0;
1517         uint64_t bword = root->bitmap[slot];
1518         if (bword & (1ull << bit)) {
1519             // Count all the set bits up to this bit
1520             for (int i = 0; i < slot; ++i)
1521                 item += __builtin_popcountll(root->bitmap[i]);
1522             item += __builtin_popcountll(bword & ((1ull << bit)-1));
1523             cursor->next = root->slots[item];
1524             cursor->isOnPage = FALSE;
1525             cursor->entryOffsetInPage = 0;
1526             cursor->offsetInEntry = 0;
1527             cursor->payload = 0;
1528             traverseFromMapCursor(trie, cursor, bytes, capacity - 1, length + 1, stop, ctx, callback);
1529             if (*stop)
1530                 return;
1531         }
1532     }
1533 }
1534
1535 static void traverseFromMapCursorMappedPageWithPrefixCompression(Page *page, CompactMapCursor *cursor, UInt8* bytes, uint32_t capacity, uint32_t length, Boolean *stop, void *ctx, CFBurstTrieTraversalCallback callback)
1536 {
1537     uint32_t pageSize = page->length - sizeof(Page);
1538     uint32_t offset = cursor->entryOffsetInPage;
1539     uint32_t minPrefixLength = 0;
1540     if (cursor->isOnPage) {
1541         PageEntryPacked *entry = (PageEntryPacked*)&page->data[offset];
1542         int32_t remainingLength = entry->strlen - cursor->offsetInEntry - 1;
1543         if (remainingLength >= 0 && remainingLength <= capacity) {
1544             memcpy(bytes + length, entry->string + cursor->offsetInEntry + 1, remainingLength);
1545             callback(ctx, bytes, length + remainingLength, entry->payload, stop);
1546             if (*stop)
1547                 return;
1548         }
1549         minPrefixLength = entry->pfxLen + cursor->offsetInEntry;
1550         offset += getPackedPageEntrySize(entry);
1551     }
1552     PageEntryPacked *previousEntry = NULL;
1553     while (offset < pageSize) {
1554         PageEntryPacked *entry = (PageEntryPacked*)&page->data[offset];
1555         if (minPrefixLength > entry->pfxLen)
1556             break;
1557         else if (entry->payload && entry->strlen <= capacity) {
1558             if (previousEntry)
1559                 length -=   previousEntry->strlen + previousEntry->pfxLen - entry->pfxLen;
1560             memcpy(bytes + length, entry->string, entry->strlen);
1561             callback(ctx, bytes, length + entry->strlen, entry->payload, stop);
1562             length += entry->strlen;
1563             if (*stop)
1564                 return;
1565         }
1566         previousEntry = entry;
1567         offset += getPackedPageEntrySize(entry);
1568     }
1569 }
1570
1571 static void traverseFromMapCursorMappedPageSortedByKey(Page *page, CompactMapCursor *cursor, UInt8* bytes, uint32_t capacity, uint32_t length, Boolean *stop, void *ctx, CFBurstTrieTraversalCallback callback)
1572 {
1573     uint32_t pageSize = page->length - sizeof(Page);
1574     uint32_t offset = cursor->entryOffsetInPage;
1575     uint32_t prefixLength = 0;
1576     const UInt8 *prefix = NULL;
1577     if (cursor->isOnPage) {
1578         PageEntry *entry = (PageEntry*)&page->data[offset];
1579         int32_t remainingLength = entry->strlen - cursor->offsetInEntry - 1;
1580         if (remainingLength >= 0 && remainingLength <= capacity) {
1581             memcpy(bytes + length, entry->string + cursor->offsetInEntry, remainingLength);
1582             callback(ctx, bytes, length + remainingLength, entry->payload, stop);
1583             if (*stop)
1584                 return;
1585         }
1586         prefixLength = cursor->offsetInEntry + 1;
1587         prefix = entry->string;
1588         offset += getPageEntrySize(entry);
1589     }
1590
1591     while (offset < pageSize) {
1592         PageEntry *entry = (PageEntry*)&page->data[offset];
1593         if (entry->strlen < prefixLength)
1594             break;
1595         else {
1596             int cmpResult = __builtin_memcmp(entry->string, prefix, prefixLength);
1597             if (cmpResult > 0)
1598                 break;
1599             else if (entry->payload && entry->strlen <= capacity) {
1600                 if (entry->strlen > 0)
1601                     memcpy(bytes + length, entry->string + prefixLength, entry->strlen - prefixLength);
1602                 callback(ctx, bytes, length + entry->strlen - prefixLength, entry->payload, stop);
1603                 if (*stop)
1604                     return;
1605             }
1606             offset += getPageEntrySize(entry);
1607         }
1608     }
1609 }
1610
1611 static void traverseFromMapCursorMappedPage(CFBurstTrieRef trie, CompactMapCursor *cursor, UInt8* bytes, uint32_t capacity, uint32_t length, Boolean *stop, void *ctx, CFBurstTrieTraversalCallback callback)
1612 {
1613     Page *page = (Page *)DiskNextTrie_GetPtr(trie->mapBase, cursor->next);
1614     if (trie->cflags & kCFBurstTrieSortByKey)
1615         traverseFromMapCursorMappedPageSortedByKey(page, cursor, bytes, capacity, length, stop, ctx, callback);
1616     else if (trie->cflags & kCFBurstTriePrefixCompression)
1617         traverseFromMapCursorMappedPageWithPrefixCompression(page, cursor, bytes, capacity, length, stop, ctx, callback);
1618 }
1619
1620 void traverseFromMapCursor(CFBurstTrieRef trie, CompactMapCursor *cursor, UInt8* bytes, uint32_t capacity, uint32_t length, Boolean *stop, void *ctx, CFBurstTrieTraversalCallback callback)
1621 {
1622     switch (DiskNextTrie_GetKind(cursor->next)) {
1623         case TrieKind:
1624             traverseFromMapCursorMappedLevel(trie, cursor, bytes, capacity, length, stop, ctx, callback);
1625             break;
1626         case CompactTrieKind:
1627             traverseFromMapCursorCompactMappedLevel(trie, cursor, bytes, capacity, length, stop, ctx, callback);
1628             break;
1629         case ListKind:
1630             traverseFromMapCursorMappedPage(trie, cursor, bytes, capacity, length, stop, ctx, callback);
1631             break;
1632         case Nothing: {
1633             TrieHeader *header = (TrieHeader*)trie->mapBase;
1634             if (cursor->next == header->rootOffset) {
1635                 traverseFromMapCursorMappedLevel(trie, cursor, bytes, capacity, length, stop, ctx, callback);
1636             }
1637             break;
1638         }
1639     }
1640 }
1641
1642 void copyMapCursor(const CompactMapCursor *source, CompactMapCursor* destination)
1643 {
1644     destination->next = source->next;
1645     destination->entryOffsetInPage = source->entryOffsetInPage;
1646     destination->offsetInEntry = source->offsetInEntry;
1647     destination->isOnPage = source->isOnPage;
1648     destination->payload = source->payload;
1649 }
1650
1651 Boolean areMapCursorsEqual(const CompactMapCursor *lhs, const CompactMapCursor *rhs)
1652 {
1653     return lhs->entryOffsetInPage == rhs->entryOffsetInPage && lhs->isOnPage == rhs->isOnPage && lhs->next == rhs->next && lhs->offsetInEntry == rhs->offsetInEntry;
1654 }
1655
1656 static Boolean getMapCursorPayloadFromPackedPageEntry(PageEntryPacked *entry, const CompactMapCursor *cursor, uint32_t *payload)
1657 {
1658     if (payload)
1659         *payload = 0;
1660     if (cursor->entryOffsetInPage == 0 && cursor->offsetInEntry == 0 && entry->strlen == 0) {
1661         if (payload)
1662             *payload = entry->payload;
1663         return TRUE;
1664     } else if (cursor->offsetInEntry != entry->strlen - 1)
1665         return FALSE;
1666     else {
1667         if (payload)
1668             *payload = entry->payload;
1669         return TRUE;
1670     }
1671 }
1672
1673 static Boolean getMapCursorPayloadFromPageEntry(PageEntry *entry, const CompactMapCursor *cursor, uint32_t *payload)
1674 {
1675     if (payload)
1676         *payload = 0;
1677     if (cursor->entryOffsetInPage == 0 && cursor->offsetInEntry == 0 && entry->strlen == 0) {
1678         if (payload)
1679             *payload = entry->payload;
1680         return TRUE;
1681     } else if (cursor->offsetInEntry != entry->strlen - 1)
1682         return FALSE;
1683     else {
1684         if (payload)
1685             *payload = entry->payload;
1686         return TRUE;
1687     }
1688 }
1689
1690 Boolean getMapCursorPayload(CFBurstTrieRef trie, const CompactMapCursor *cursor, uint32_t *payload)
1691 {
1692     if (!cursor)
1693         return FALSE;
1694     if (cursor->payload) {
1695         if (payload)
1696             *payload  = cursor->payload;
1697         return TRUE;
1698     }
1699     return FALSE;
1700 }
1701
1702 // Legacy
1703
1704 static Boolean burstTrieMappedFind(DiskTrieLevelRef trie, char *map, const UInt8 *key, uint32_t length, uint32_t *payload, bool prefix) {
1705     Boolean success = false;
1706     if (length) {
1707         uint32_t offset = CFSwapInt32LittleToHost((uint32_t)trie->slots[*key]);
1708         if(DiskNextTrie_GetKind(offset) == TrieKind) {
1709             return burstTrieMappedFind((DiskTrieLevelRef)DiskNextTrie_GetPtr(map,offset), map, key+1, length-1, payload, prefix);
1710         } else if(DiskNextTrie_GetKind(offset) == CompactTrieKind) {
1711             return burstTrieCompactTrieMappedFind((CompactDiskTrieLevelRef)DiskNextTrie_GetPtr(map, offset), map, key+1, length-1, payload, prefix);
1712         } else {
1713             if(DiskNextTrie_GetKind(offset) == ListKind) {
1714                 return burstTrieMappedPageFind((StringPage *)DiskNextTrie_GetPtr(map, offset), key+1, length-1, payload, prefix);
1715             } else {
1716                 return success;
1717             }
1718         }
1719     } else {
1720         if (trie->weight) {
1721             SetPayload(payload, CFSwapInt32LittleToHost(trie->payload));
1722             success = true;
1723         }
1724     }
1725     return success;
1726 }
1727
1728 static Boolean burstTrieCompactTrieMappedFind(CompactDiskTrieLevelRef trie, char *map, const UInt8 *key, uint32_t length, uint32_t *payload, bool prefix) {
1729     Boolean success = false;
1730     if (length) {
1731         uint32_t mykey = *key;
1732         uint32_t slot = mykey / 64;
1733         uint32_t bit = mykey % 64;
1734         uint32_t item = 0;
1735         uint64_t bword = CFSwapInt64LittleToHost(trie->bitmap[slot]);
1736         if (bword & (1ull << bit)) {
1737             /* Count all the set bits up to this bit */
1738             for (int i=0; i < slot; i++) {
1739                 item += __builtin_popcountll(trie->bitmap[i]);
1740             }
1741             item += __builtin_popcountll(bword & ((1ull << bit)-1));
1742             uint32_t offset = CFSwapInt32LittleToHost((uint32_t)trie->slots[item]);
1743             if(DiskNextTrie_GetKind(offset) == TrieKind) {
1744                 return burstTrieMappedFind((DiskTrieLevelRef)DiskNextTrie_GetPtr(map, offset), map, key+1, length-1, payload, prefix);
1745             } else if(DiskNextTrie_GetKind(offset) == CompactTrieKind) {
1746                 return burstTrieCompactTrieMappedFind((CompactDiskTrieLevelRef)DiskNextTrie_GetPtr(map, offset), map, key+1, length-1, payload, prefix);
1747             }
1748             else {
1749                 if(DiskNextTrie_GetKind(offset) == ListKind) {
1750                     return burstTrieMappedPageFind((StringPage *)DiskNextTrie_GetPtr(map, offset), key+1, length-1, payload, prefix);
1751                 } else {
1752                     return success;
1753                 }
1754             }
1755         }
1756     } else {
1757         if (trie->weight) {
1758             SetPayload(payload, CFSwapInt32LittleToHost(trie->payload));
1759             success = true;
1760         }
1761     }
1762     return success;
1763 }
1764
1765 static Boolean burstTrieMappedPageFind(StringPage *page, const UInt8 *key, uint32_t length, uint32_t *payload, bool prefix) {
1766     Boolean success = false;
1767     uint32_t end = CFSwapInt32LittleToHost(page->length);
1768     uint32_t cur = 0;
1769     if (prefix) {
1770         uint8_t pfx[256];
1771         while (cur < end) {
1772             StringPageEntryPacked *entry = (StringPageEntryPacked *)&page->data[cur];
1773             uint16_t strlen = entry->pfxLen+CFSwapInt16LittleToHost(entry->strlen);
1774             if (strlen == length && __builtin_memcmp(pfx, key, entry->pfxLen) == 0 && __builtin_memcmp(entry->string, key+entry->pfxLen, length-entry->pfxLen) == 0) {
1775                 SetPayload(payload, CFSwapInt32LittleToHost(entry->payload));
1776                 success = true;
1777                 return success;
1778             } else {
1779                 memcpy(pfx+entry->pfxLen, entry->string, MIN(255-entry->pfxLen, length-entry->pfxLen));
1780                 cur += sizeof(*entry) + strlen - entry->pfxLen;
1781             }
1782         }
1783     } else {
1784         while (cur < end) {
1785             StringPageEntry *entry = (StringPageEntry *)&page->data[cur];
1786             uint16_t strlen = CFSwapInt16LittleToHost(entry->strlen);
1787             if (strlen == length && __builtin_memcmp(entry->string, key, length) == 0) {
1788                 SetPayload(payload, CFSwapInt32LittleToHost(entry->payload));
1789                 success = true;
1790                 return success;
1791             } else {
1792                 cur += sizeof(*entry) + strlen;
1793             }
1794         }
1795
1796     }
1797     return success;
1798 }
1799
1800
1801 #if 0
1802 #pragma mark -
1803 #pragma mark Serialization
1804 #endif
1805
1806 static bool serializeCFBurstTrieLevels(CFBurstTrieRef trie, TrieLevelRef root, uint32_t *offset, off_t start_offset, bool dispose, bool isroot, int fd)
1807 {
1808     bool dense = true;
1809     int count = 0;
1810
1811     for (int i=0; i < CHARACTER_SET_SIZE; i++) if (root->slots[i]) count++;
1812
1813     uint32_t this_offset = *offset;
1814
1815     if ((trie->cflags & kCFBurstTrieBitmapCompression) && count < MAX_BITMAP_SIZE && !isroot) {
1816         size_t size = sizeof(CompactMapTrieLevel) + sizeof(uint32_t) * count;
1817         int offsetSlot = 0;
1818
1819         CompactMapTrieLevel *maptrie = (CompactMapTrieLevel *)alloca(size);
1820         bzero(maptrie, size);
1821         *offset += size;
1822
1823         for (int i=0; i < CHARACTER_SET_SIZE; i++) {
1824             NextTrie next = root->slots[i];
1825             if (next) {
1826                 uint32_t slot = i / 64;
1827                 uint32_t bit = i % 64;
1828                 maptrie->bitmap[slot] |= 1ull<<bit;
1829                 if (NextTrie_GetKind(next) == TrieKind) {
1830                     TrieLevelRef nextLevel = (TrieLevelRef)NextTrie_GetPtr(next);
1831                     uint32_t childOffset = *offset;
1832                     if (serializeCFBurstTrieLevels(trie, nextLevel, offset, start_offset, true, false, fd)) {
1833                         maptrie->slots[offsetSlot] = (TrieKind|childOffset);
1834                     } else {
1835                         maptrie->slots[offsetSlot] = (CompactTrieKind|childOffset);
1836                     }
1837                 } else {
1838                     maptrie->slots[offsetSlot] = next;
1839                 }
1840                 offsetSlot++;
1841             }
1842         }
1843         maptrie->payload = root->payload;
1844
1845         int bitcount = 0;
1846         for (int i=0; i < 4; i++) bitcount += __builtin_popcountll(maptrie->bitmap[i]);
1847         assert(bitcount == count);
1848
1849         pwrite(fd, maptrie, size, this_offset+start_offset);
1850         dense = false;
1851     } else {
1852         MapTrieLevel maptrie;
1853         *offset += sizeof(maptrie);
1854
1855         for (int i=0; i < CHARACTER_SET_SIZE; i++) {
1856             NextTrie next = root->slots[i];
1857             if (NextTrie_GetKind(next) == TrieKind) {
1858                 TrieLevelRef nextLevel = (TrieLevelRef)NextTrie_GetPtr(next);
1859                 uint32_t childOffset = *offset;
1860                 if (serializeCFBurstTrieLevels(trie, nextLevel, offset, start_offset, true, false, fd)) {
1861                     maptrie.slots[i] = (TrieKind|childOffset);
1862                 } else {
1863                     maptrie.slots[i] = (CompactTrieKind|childOffset);
1864                 }
1865             } else {
1866                 maptrie.slots[i] = next;
1867             }
1868         }
1869         maptrie.payload = root->payload;
1870         pwrite(fd, &maptrie, sizeof(maptrie), this_offset+start_offset);
1871     }
1872
1873     if (dispose) free(root);
1874     return dense;
1875 }
1876
1877 static void serializeCFBurstTrieList(CFBurstTrieRef trie, ListNodeRef listNode, int fd)
1878 {
1879     uint32_t listCount;
1880     size_t size = trie->containerSize;
1881
1882     // ** Temp list of nodes to sort
1883     ListNodeRef *nodes = (ListNodeRef *)malloc(sizeof(ListNodeRef) * size);
1884     for (listCount = 0; listNode; listCount++) {
1885         if (listCount >= size) {
1886             size *= 2;
1887             nodes = (ListNodeRef *)realloc(nodes, sizeof(ListNodeRef) * size);
1888         }
1889         nodes[listCount] = listNode;
1890         listNode = listNode->next;
1891     }
1892
1893     char _buffer[MAX_BUFFER_SIZE];
1894     char bufferSize = (sizeof(Page) + size * (sizeof(PageEntryPacked) + MAX_STRING_SIZE));
1895     char *buffer = bufferSize < MAX_BUFFER_SIZE ? _buffer : (char *) malloc(bufferSize);
1896
1897     Page *page = (Page *)buffer;
1898     uint32_t current = 0;
1899
1900     if (trie->cflags & kCFBurstTriePrefixCompression) {
1901         qsort(nodes, listCount, sizeof(ListNodeRef), nodeStringCompare);
1902
1903         ListNodeRef last = 0;
1904         for (int i=0; i < listCount; i++) {
1905             listNode = nodes[i];
1906             uint8_t pfxLen = 0;
1907             if (last) {
1908                 for ( ;
1909                      pfxLen < CHARACTER_SET_SIZE-1 &&
1910                      pfxLen < listNode->length &&
1911                      pfxLen < last->length &&
1912                      listNode->string[pfxLen] == last->string[pfxLen];
1913                      pfxLen++);
1914             }
1915
1916             PageEntryPacked *entry = (PageEntryPacked *)(&page->data[current]);
1917             entry->strlen = listNode->length - pfxLen;
1918             entry->payload = listNode->payload;
1919             entry->pfxLen = pfxLen;
1920             memcpy(entry->string, listNode->string+pfxLen, listNode->length-pfxLen);
1921             current += listNode->length - pfxLen + sizeof(PageEntryPacked);
1922             last = listNode;
1923         }
1924     } else {
1925         if (trie->cflags & kCFBurstTrieSortByKey)
1926             qsort(nodes, listCount, sizeof(ListNodeRef), nodeStringCompare);
1927         else
1928             qsort(nodes, listCount, sizeof(ListNodeRef), nodeWeightCompare);
1929
1930         for (int i=0; i < listCount; i++) {
1931             listNode = nodes[i];
1932             PageEntry *entry = (PageEntry *)(&page->data[current]);
1933             entry->strlen = listNode->length;
1934             entry->payload = listNode->payload;
1935             memcpy(entry->string, listNode->string, listNode->length);
1936             current += listNode->length + sizeof(PageEntry);
1937         }
1938     }
1939
1940     size_t len = (sizeof(Page) + current + 3) & ~3;
1941     page->length = current;
1942     write(fd, page, len);
1943
1944     free(nodes);
1945     if (buffer != _buffer) free(buffer);
1946 }
1947
1948 static void serializeCFBurstTrieLists(CFBurstTrieRef trie, TrieLevelRef root, off_t start_offset, int fd)
1949 {
1950     for (int i=0; i < CHARACTER_SET_SIZE; i++) {
1951         NextTrie next = root->slots[i];
1952         uint32_t offset;
1953         if (NextTrie_GetKind(next) == TrieKind) {
1954             TrieLevelRef nextLevel = (TrieLevelRef)NextTrie_GetPtr(next);
1955             serializeCFBurstTrieLists(trie, nextLevel, start_offset, fd);
1956         } else {
1957             if (NextTrie_GetKind(next) == ListKind) {
1958                 ListNodeRef listNode = (ListNodeRef)NextTrie_GetPtr(next);
1959                 offset = lseek(fd, 0, SEEK_CUR) - start_offset;
1960                 serializeCFBurstTrieList(trie, listNode, fd);
1961                 finalizeCFBurstTrieList(listNode);
1962                 //assert((offset & 3)==0);
1963                 root->slots[i] = (offset|ListKind);
1964             }
1965         }
1966     }
1967 }
1968
1969 static size_t serializeCFBurstTrie(CFBurstTrieRef trie, size_t start_offset, int fd)
1970 {
1971     TrieHeader header;
1972     header.signature = 0x0ddba11;
1973     header.rootOffset = 0;
1974     header.count = trie->count;
1975     header.size = 0;
1976     header.flags = trie->cflags;
1977     header.reserved[0] = 0;
1978
1979     uint32_t offset;
1980     lseek(fd, start_offset, SEEK_SET);
1981
1982     size_t header_size = sizeof(header);
1983     write(fd, &header, header_size);
1984
1985     serializeCFBurstTrieLists(trie, &trie->root, start_offset, fd);
1986
1987     offset = lseek(fd, 0, SEEK_CUR) - start_offset;
1988     size_t off = offsetof(TrieHeader, rootOffset);
1989     size_t offsize = sizeof(offset);
1990     pwrite(fd, &offset, offsize, off+start_offset);
1991
1992     serializeCFBurstTrieLevels(trie, &trie->root, &offset, start_offset, false, true, fd);
1993
1994     size_t off2 = offsetof(TrieHeader, size);
1995     offsize = sizeof(offset);
1996     pwrite(fd, &offset, offsize, off2+start_offset);
1997
1998     offset = lseek(fd, 0, SEEK_END);
1999     return (size_t)(offset-start_offset);
2000 }
2001
2002 #if 0
2003 #pragma mark -
2004 #pragma mark Release
2005 #endif
2006
2007 static void destroyCFBurstTrie(CFBurstTrieRef trie) {
2008     if (trie->mapBase) {
2009 #if DEPLOYMENT_TARGET_WINDOWS
2010         UnmapViewOfFile(trie->mapBase);
2011         CloseHandle(trie->mapHandle);
2012         CloseHandle(trie->mappedFileHandle);
2013 #else
2014         munmap(trie->mapBase, trie->mapSize);
2015 #endif
2016     } else {
2017         finalizeCFBurstTrie(&trie->root);
2018     }
2019     free(trie);
2020     return;
2021 }
2022
2023 static void finalizeCFBurstTrie(TrieLevelRef trie) {
2024     for (int i=0; i < CHARACTER_SET_SIZE; i++) {
2025         if (NextTrie_GetKind(trie->slots[i]) == TrieKind) {
2026             finalizeCFBurstTrie((TrieLevelRef)NextTrie_GetPtr(trie->slots[i]));
2027             free((void *)NextTrie_GetPtr(trie->slots[i]));
2028         } else if (NextTrie_GetKind(trie->slots[i]) == ListKind) {
2029             finalizeCFBurstTrieList((ListNodeRef)NextTrie_GetPtr(trie->slots[i]));
2030         }
2031     }
2032 }
2033
2034 static void finalizeCFBurstTrieList(ListNodeRef node) {
2035     do {
2036         ListNodeRef next = node->next;
2037         free(node);
2038         node = next;
2039     } while(node);
2040 }
2041
2042 #if 0
2043 #pragma mark -
2044 #pragma mark Helpers
2045 #endif
2046
2047 static int nodeWeightCompare(const void *a, const void *b) {
2048     ListNodeRef nodeA = *(ListNodeRef *)a;
2049     ListNodeRef nodeB = *(ListNodeRef *)b;
2050     return (nodeB->weight - nodeA->weight);
2051 }
2052
2053 static int nodeStringCompare(const void *a, const void *b) {
2054     ListNodeRef nodeA = *(ListNodeRef *)a;
2055     ListNodeRef nodeB = *(ListNodeRef *)b;
2056     int result = memcmp((char *)nodeA->string, (char *)nodeB->string, MIN(nodeA->length, nodeB->length));
2057     if (result == 0) result = nodeA->length-nodeB->length;
2058     return result;
2059 }
2060
2061 bool containsKey(void *context, const uint8_t *key, uint32_t payload, bool exact)
2062 {
2063     uint32_t *ctx = (uint32_t *)context;
2064     if (exact) *ctx = payload;
2065     return exact;
2066 }
2067
2068 static CFIndex burstTrieConvertCharactersToUTF8(UniChar *chars, CFIndex numChars, UInt8 *buffer) {
2069     uint32_t i, j;
2070     for (i = j = 0; i < numChars; i++) {
2071         UniChar c = chars[i];
2072         if (CFStringIsSurrogateHighCharacter(c) && i + 1 < numChars && CFStringIsSurrogateLowCharacter(chars[i + 1])) {
2073             UTF32Char lc = CFStringGetLongCharacterForSurrogatePair(c, chars[i + 1]);
2074             buffer[j++] = 0xf0 + (lc >> 18);
2075             buffer[j++] = 0x80 + ((lc & 0x3ffff) >> 12);
2076             buffer[j++] = 0x80 + ((lc & 0xfff) >> 6);
2077             buffer[j++] = 0x80 + (lc & 0x3f);
2078             i++;
2079         } else {
2080             if (c < 0x80) {
2081                 buffer[j++] = c;
2082             } else if (c < 0x800) {
2083                 buffer[j++] = 0xc0 + (c >> 6);
2084                 buffer[j++] = 0x80 + (c & 0x3f);
2085             } else {
2086                 buffer[j++] = 0xe0 + (c >> 12);
2087                 buffer[j++] = 0x80 + ((c & 0xfff) >> 6);
2088                 buffer[j++] = 0x80 + (c & 0x3f);
2089             }
2090         }
2091     }
2092     buffer[j] = 0;
2093     return j;
2094 }
2095