Debian Codegraph @

ext/sparse/ctrie.h

raw
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*/