SameBoy | Accurate GB/GBC emulator |
| download: https://git.y1.nz/archives/sameboy.tar.gz | |
| README | Files | Log | Refs | LICENSE |
HexFiend/HFGlyphTrie.m
1 #import "HFGlyphTrie.h"
2 #import <objc/objc-auto.h>
3
4 /* If branchingDepth is 1, then this is a leaf and there's nothing to free (a parent frees its children). If branchingDepth is 2, then this is a branch whose children are leaves, so we have to free the leaves but we do not recurse. If branchingDepth is greater than 2, we do have to recurse. */
5 static void freeTrie(struct HFGlyphTrieBranch_t *branch, uint8_t branchingDepth) {
6 HFASSERT(branchingDepth >= 1);
7 NSUInteger i;
8 if (branchingDepth > 2) {
9 /* Recurse */
10 for (i=0; i < kHFGlyphTrieBranchCount; i++) {
11 if (branch->children[i]) {
12 freeTrie(branch->children[i], branchingDepth - 1);
13 }
14 }
15 }
16 if (branchingDepth > 1) {
17 /* Free our children */
18 for (i=0; i < kHFGlyphTrieBranchCount; i++) {
19 free(branch->children[i]);
20 }
21 }
22 }
23
24 static void insertTrie(void *node, uint8_t branchingDepth, NSUInteger key, struct HFGlyph_t value) {
25 HFASSERT(node != NULL);
26 HFASSERT(branchingDepth >= 1);
27 if (branchingDepth == 1) {
28 /* Leaf */
29 HFASSERT(key < kHFGlyphTrieBranchCount);
30 ((struct HFGlyphTrieLeaf_t *)node)->glyphs[key] = value;
31 } else {
32 /* Branch */
33 struct HFGlyphTrieBranch_t *branch = node;
34 NSUInteger keySlice = key & ((1 << kHFGlyphTrieBranchFactor) - 1), keyRemainder = key >> kHFGlyphTrieBranchFactor;
35 __strong void *child = branch->children[keySlice];
36 if (child == NULL) {
37 if (branchingDepth == 2) {
38 child = calloc(1, sizeof(struct HFGlyphTrieLeaf_t));
39 } else {
40 child = calloc(1, sizeof(struct HFGlyphTrieBranch_t));
41 }
42 /* We just zeroed out a block of memory and we are about to write its address somewhere where another thread could read it, so we need a memory barrier. */
43 OSMemoryBarrier();
44 branch->children[keySlice] = child;
45 }
46 insertTrie(child, branchingDepth - 1, keyRemainder, value);
47 }
48 }
49
50 static struct HFGlyph_t getTrie(const void *node, uint8_t branchingDepth, NSUInteger key) {
51 HFASSERT(node != NULL);
52 HFASSERT(branchingDepth >= 1);
53 if (branchingDepth == 1) {
54 /* Leaf */
55 HFASSERT(key < kHFGlyphTrieBranchCount);
56 return ((const struct HFGlyphTrieLeaf_t *)node)->glyphs[key];
57 } else {
58 /* Branch */
59 const struct HFGlyphTrieBranch_t *branch = node;
60 NSUInteger keySlice = key & ((1 << kHFGlyphTrieBranchFactor) - 1), keyRemainder = key >> kHFGlyphTrieBranchFactor;
61 if (branch->children[keySlice] == NULL) {
62 /* Not found */
63 return (struct HFGlyph_t){0, 0};
64 } else {
65 /* This dereference requires a data dependency barrier */
66 return getTrie(branch->children[keySlice], branchingDepth - 1, keyRemainder);
67 }
68 }
69 }
70
71 void HFGlyphTrieInsert(struct HFGlyphTrie_t *trie, NSUInteger key, struct HFGlyph_t value) {
72 insertTrie(&trie->root, trie->branchingDepth, key, value);
73 }
74
75 struct HFGlyph_t HFGlyphTrieGet(const struct HFGlyphTrie_t *trie, NSUInteger key) {
76 struct HFGlyph_t result = getTrie(&trie->root, trie->branchingDepth, key);
77 return result;
78 }
79
80 void HFGlyphTrieInitialize(struct HFGlyphTrie_t *trie, uint8_t keySize) {
81 /* If the branch factor is 4 (bits) and the key size is 2 bytes = 16 bits, initialize branching depth to 16/4 = 4 */
82 uint8_t keyBits = keySize * CHAR_BIT;
83 HFASSERT(keyBits % kHFGlyphTrieBranchFactor == 0);
84 trie->branchingDepth = keyBits / kHFGlyphTrieBranchFactor;
85 memset(&trie->root, 0, sizeof(trie->root));
86 }
87
88 void HFGlyphTreeFree(struct HFGlyphTrie_t * trie) {
89 /* Don't try to free under GC. And don't free if it's never been initialized. */
90 if (trie->branchingDepth > 0) {
91 freeTrie(&trie->root, trie->branchingDepth);
92 }
93 }
This webpage is intended to be an accessible preview of this repository. To get a fuller picture, clone it and use the git CLI.