]> git.saurik.com Git - apple/cf.git/blob - CFBurstTrie.c
CF-744.tar.gz
[apple/cf.git] / 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