| 1 |
/* |
| 2 |
* ctrie.h - Compact Trie |
| 3 |
* |
| 4 |
* Copyright (c) 2009-2024 Shiro Kawai <[email protected]> |
| 5 |
* |
| 6 |
* Redistribution and use in source and binary forms, with or without |
| 7 |
* modification, are permitted provided that the following conditions |
| 8 |
* are met: |
| 9 |
* |
| 10 |
* 1. Redistributions of source code must retain the above copyright |
| 11 |
* notice, this list of conditions and the following disclaimer. |
| 12 |
* |
| 13 |
* 2. Redistributions in binary form must reproduce the above copyright |
| 14 |
* notice, this list of conditions and the following disclaimer in the |
| 15 |
* documentation and/or other materials provided with the distribution. |
| 16 |
* |
| 17 |
* 3. Neither the name of the authors nor the names of its contributors |
| 18 |
* may be used to endorse or promote products derived from this |
| 19 |
* software without specific prior written permission. |
| 20 |
* |
| 21 |
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 22 |
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 23 |
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 24 |
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 25 |
* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 26 |
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
| 27 |
* TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 28 |
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 29 |
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 30 |
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 31 |
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 32 |
*/ |
| 33 |
|
| 34 |
#ifndef GAUCHE_CTRIE_H |
| 35 |
#define GAUCHE_CTRIE_H |
| 36 |
|
| 37 |
#include <gauche.h> |
| 38 |
#include <gauche/extend.h> |
| 39 |
#include <gauche/bits_inline.h> |
| 40 |
|
| 41 |
/* CompactTrie is a structure to store data indexed by full 32bit integer. |
| 42 |
* It can be used as a space-efficient vector and as a back-end of sparse |
| 43 |
* hash table. Compact Trie itself is *not* an ScmObj. |
| 44 |
* |
| 45 |
* CompactTrie is not intended to be used outside of ext/sparse source tree, |
| 46 |
* hence we don't use 'Scm' prefix for data structures, for simplicity. |
| 47 |
*/ |
| 48 |
|
| 49 |
/* CompactTrie consists of NODEs and LEAFs. LEAF is application-dependent |
| 50 |
* structure whose header contains the key value that uniquely identifies |
| 51 |
* the leaf. |
| 52 |
* NODE is a variable length structure, whose first two words are bitmaps. |
| 53 |
* (NB: we may change the layout here, since full-word bitmap tends to become |
| 54 |
* false pointer and may have negative impact to our conservative GC.) |
| 55 |
* |
| 56 |
* NODE represents 32-way branch. The first bitmap, EMAP or entry map, |
| 57 |
* shows which logical index of this node is active. The second bitmap, |
| 58 |
* LMAP, shows which entry of logical index of this node is LEAF. |
| 59 |
* LMAP is always a strict subset of EMAP. If bit N of EMAP is 1 and |
| 60 |
* bit N of LMAP is 0, the N-th index points to the child node. |
| 61 |
* |
| 62 |
* Suppose EMAP is 0x00001809 and LMAP is 0x00001008. It means this |
| 63 |
* node has entries in index 0, 3, 11, 12. Entry #0 and #11 points to |
| 64 |
* child NODEs, and entry #3 and #12 are LEAFs. |
| 65 |
* |
| 66 |
* The actual entries follow the bitmaps in compact format. For the above |
| 67 |
* example, four intptr_t follows, corresponding to entry #0, #3, #11 and #12, |
| 68 |
* respectively. |
| 69 |
*/ |
| 70 |
|
| 71 |
#define MAX_NODE_SIZE 32 |
| 72 |
#define TRIE_SHIFT 5 |
| 73 |
#define TRIE_MASK (0x1f) |
| 74 |
|
| 75 |
typedef struct NodeRec { |
| 76 |
u_long emap; /* bitmap: 1 = has child */ |
| 77 |
u_long lmap; /* bitmap: 1 = child is leaf */ |
| 78 |
void *entries[2]; /* variable length; 2 is the minimum entries */ |
| 79 |
} Node; |
| 80 |
|
| 81 |
/* The leaf stores key bits. |
| 82 |
We split key into two words; a well distributed keys are hard to |
| 83 |
distinguish from pointers by our conserative GC, and sometimes lead |
| 84 |
to poor GC performance when we have very large table. */ |
| 85 |
typedef struct LeafRec { |
| 86 |
u_long key0; /* lower half word of the key + flags */ |
| 87 |
u_long key1; /* upper half word of the key */ |
| 88 |
} Leaf; |
| 89 |
|
| 90 |
#define LEAF(x) ((Leaf*)(x)) |
| 91 |
|
| 92 |
#if SIZEOF_LONG == 4 |
| 93 |
#define LEAF_KEY_BITS 16 |
| 94 |
#else /* SIZEOF_LONG >= 8 */ |
| 95 |
#define LEAF_KEY_BITS 32 |
| 96 |
#endif /* SIZEOF_LONG >= 8 */ |
| 97 |
|
| 98 |
#define LEAF_KEY_MASK ((1UL<<LEAF_KEY_BITS)-1) |
| 99 |
|
| 100 |
/* managing key in the leaf */ |
| 101 |
|
| 102 |
static inline u_long leaf_key(Leaf *leaf) |
| 103 |
{ |
| 104 |
return (((leaf->key1&LEAF_KEY_MASK) << LEAF_KEY_BITS) |
| 105 |
+ (leaf->key0&LEAF_KEY_MASK)); |
| 106 |
} |
| 107 |
|
| 108 |
static inline void leaf_key_set(Leaf *leaf, u_long key) |
| 109 |
{ |
| 110 |
leaf->key0 = key & LEAF_KEY_MASK; |
| 111 |
leaf->key1 = (key >> LEAF_KEY_BITS) & LEAF_KEY_MASK; |
| 112 |
} |
| 113 |
|
| 114 |
static inline u_long leaf_data(Leaf *leaf) |
| 115 |
{ |
| 116 |
return (leaf->key0 >> LEAF_KEY_BITS); |
| 117 |
} |
| 118 |
|
| 119 |
static inline void leaf_data_set(Leaf *leaf, u_long data) |
| 120 |
{ |
| 121 |
leaf->key0 = (leaf->key0 & LEAF_KEY_MASK) | (data << LEAF_KEY_BITS); |
| 122 |
} |
| 123 |
|
| 124 |
static inline int leaf_data_bit_test(Leaf *leaf, int bit) |
| 125 |
{ |
| 126 |
return !!(leaf->key0 & (1UL << (bit + LEAF_KEY_BITS))); |
| 127 |
} |
| 128 |
|
| 129 |
static inline void leaf_data_bit_set(Leaf *leaf, int bit) |
| 130 |
{ |
| 131 |
leaf->key0 |= (1UL << (bit + LEAF_KEY_BITS)); |
| 132 |
} |
| 133 |
|
| 134 |
static inline void leaf_data_bit_reset(Leaf *leaf, int bit) |
| 135 |
{ |
| 136 |
leaf->key0 &= ~(1UL << (bit + LEAF_KEY_BITS)); |
| 137 |
} |
| 138 |
|
| 139 |
/* |
| 140 |
* Anchor to hold the trie |
| 141 |
*/ |
| 142 |
typedef struct CompactTrieRec { |
| 143 |
u_int numEntries; |
| 144 |
Node *root; |
| 145 |
} CompactTrie; |
| 146 |
|
| 147 |
typedef struct CompactTrieIterRec { |
| 148 |
CompactTrie *trie; |
| 149 |
u_long key; |
| 150 |
char begin; |
| 151 |
char end; |
| 152 |
} CompactTrieIter; |
| 153 |
|
| 154 |
/* Create empty CompactTrie */ |
| 155 |
extern CompactTrie *MakeCompactTrie(void); |
| 156 |
extern void CompactTrieInit(CompactTrie *); |
| 157 |
extern void CompactTrieClear(CompactTrie *, |
| 158 |
void (*clearer)(Leaf*, void*), |
| 159 |
void *data); |
| 160 |
|
| 161 |
/* Search CompactTrie with KEY. */ |
| 162 |
extern Leaf *CompactTrieGet(CompactTrie *ct, u_long key); |
| 163 |
extern Leaf *CompactTrieAdd(CompactTrie *ct, u_long key, |
| 164 |
Leaf *(*creator)(void*), void *data); |
| 165 |
extern Leaf *CompactTrieDelete(CompactTrie *ct, u_long key); |
| 166 |
extern void CompactTrieCopy(CompactTrie *dst, |
| 167 |
const CompactTrie *src, |
| 168 |
Leaf *(*copy)(Leaf*, void*), void *data); |
| 169 |
|
| 170 |
extern Leaf *CompactTrieFirstLeaf(CompactTrie *ct); |
| 171 |
extern Leaf *CompactTrieLastLeaf(CompactTrie *ct); |
| 172 |
extern Leaf *CompactTrieNextLeaf(CompactTrie *ct, u_long key); |
| 173 |
|
| 174 |
|
| 175 |
/* Iterator */ |
| 176 |
extern void CompactTrieIterInit(CompactTrieIter *it, CompactTrie *ct); |
| 177 |
extern Leaf *CompactTrieIterNext(CompactTrieIter *it); |
| 178 |
|
| 179 |
/* For debug */ |
| 180 |
extern void CompactTrieDump(ScmPort *out, const CompactTrie *ct, |
| 181 |
void (*dumper)(ScmPort *, Leaf*, int, void*), |
| 182 |
void *data); |
| 183 |
extern void CompactTrieCheck(const CompactTrie *ct, ScmObj obj, |
| 184 |
void (*checker)(Leaf*, ScmObj)); |
| 185 |
|
| 186 |
#endif /*GAUCHE_CTRIE_H*/ |