YAP 7.1.0
core_tries.h
1/*********************************************
2 File: core_tries.h
3 Author: Ricardo Rocha
4 Comments: Tries core module for Yap Prolog
5 version: $ID$
6*********************************************/
7
8/* -------------------------------------- */
9/* Yap Tagging Scheme */
10/* -------------------------------------- */
11
12#include "YapInterface.h"
13#if SIZEOF_INT_P == 4
14#define TAG_LOW_BITS_32 /* 'Tags_32LowTag.h' tagging scheme */
15#define SIZE_FLOAT_AS_TERM 2
16#elif SIZEOF_INT_P == 8
17#define TAG_64BITS /* 'Tags_64bits.h' tagging scheme */
18#define SIZE_FLOAT_AS_TERM 1
19#else
20#error Unknown tagging scheme
21#endif /* YAP_SCHEME */
22
23/* --------------------------- */
24/* Defines */
25/* --------------------------- */
26
27#ifdef TAG_LOW_BITS_32
28#define ApplTag 1 /* 0x01 */
29#else /* TAG_64BITS */
30#define ApplTag 5 /* 0x05 */
31#endif /* TAG_SCHEME */
32#define PairInitTag 3 /* 0x03 */
33#define PairEndEmptyTag 19 /* 0x13 */
34#define PairEndTermTag 99 /* 0x63 */
35#define CommaInitTag 35 /* 0x23 */
36#define CommaEndTag 51 /* 0x33 */
37#define FloatInitTag 67 /* 0x43 */
38#define FloatEndTag 83 /* 0x53 */
39
40#define TRIE_MODE_STANDARD 0
41#define TRIE_MODE_REVERSE 1
42#define TRIE_MODE_MINIMAL 2
43#define TRIE_MODE_REVMIN TRIE_MODE_REVERSE || TRIE_MODE_MINIMAL // 3
44
45#define TRIE_PRINT_NORMAL 0
46#define TRIE_PRINT_FLOAT 1
47#define TRIE_PRINT_FLOAT2 2
48#define TRIE_PRINT_FLOAT_END 3
49
50#define BASE_AUXILIARY_TERM_STACK_SIZE 100000
51
52/* --------------------------- */
53/* Structs */
54/* --------------------------- */
55
56typedef struct trie_engine {
57 struct trie_node *first_trie;
58 /* in use */
59 YAP_Int memory_in_use;
60 YAP_Int tries_in_use;
61 YAP_Int entries_in_use;
62 YAP_Int nodes_in_use;
63 /* max used */
64 YAP_Int memory_max_used;
65 YAP_Int tries_max_used;
66 YAP_Int entries_max_used;
67 YAP_Int nodes_max_used;
68} * TrEngine;
69
70#define TrEngine_trie(X) ((X)->first_trie)
71#define TrEngine_memory(X) ((X)->memory_in_use)
72#define TrEngine_tries(X) ((X)->tries_in_use)
73#define TrEngine_entries(X) ((X)->entries_in_use)
74#define TrEngine_nodes(X) ((X)->nodes_in_use)
75#define TrEngine_memory_max(X) ((X)->memory_max_used)
76#define TrEngine_tries_max(X) ((X)->tries_max_used)
77#define TrEngine_entries_max(X) ((X)->entries_max_used)
78#define TrEngine_nodes_max(X) ((X)->nodes_max_used)
79
80typedef struct trie_node {
81 struct trie_node *parent;
82 struct trie_node *child;
83 struct trie_node *next;
84 struct trie_node *previous;
85 YAP_Term entry;
86} * TrNode;
87
88#define TrNode_parent(X) ((X)->parent)
89#define TrNode_child(X) ((X)->child)
90#define TrNode_next(X) ((X)->next)
91#define TrNode_previous(X) ((X)->previous)
92#define TrNode_entry(X) ((X)->entry)
93
94typedef struct trie_hash {
95 struct trie_node
96 *parent; /* for compatibility with the trie_node data structure */
97 struct trie_node **buckets;
98 int number_of_buckets;
99 int number_of_nodes;
100} * TrHash;
101
102#define TrHash_mark(X) ((X)->parent)
103#define TrHash_buckets(X) ((X)->buckets)
104#define TrHash_bucket(X, N) ((X)->buckets + N)
105#define TrHash_num_buckets(X) ((X)->number_of_buckets)
106#define TrHash_seed(X) ((X)->number_of_buckets - 1)
107#define TrHash_num_nodes(X) ((X)->number_of_nodes)
108
109#define TYPE_TR_ENGINE struct trie_engine
110#define TYPE_TR_NODE struct trie_node
111#define TYPE_TR_HASH struct trie_hash
112#define SIZEOF_TR_ENGINE sizeof(TYPE_TR_ENGINE)
113#define SIZEOF_TR_NODE sizeof(TYPE_TR_NODE)
114#define SIZEOF_TR_HASH sizeof(TYPE_TR_HASH)
115#define SIZEOF_TR_BUCKET sizeof(TYPE_TR_NODE *)
116
117#define AS_TR_NODE_NEXT(ADDR) \
118 (TrNode)((YAP_UInt)(ADDR)-2 * sizeof(struct trie_node *))
119
120/* --------------------------- */
121/* Macros */
122/* --------------------------- */
123
124#define TAG_ADDR(ADDR) ((YAP_UInt)(ADDR) | 0x1)
125#define UNTAG_ADDR(ADDR) ((YAP_UInt)(ADDR) & ~(0x1))
126#define PUT_DATA_IN_LEAF_TRIE_NODE(TR_NODE, DATA) \
127 TrNode_child(TR_NODE) = (TrNode)TAG_ADDR(DATA)
128#define GET_DATA_FROM_LEAF_TRIE_NODE(TR_NODE) UNTAG_ADDR(TrNode_child(TR_NODE))
129#define MARK_AS_LEAF_TRIE_NODE(TR_NODE) \
130 PUT_DATA_IN_LEAF_TRIE_NODE(TR_NODE, TrNode_child(TR_NODE))
131#define IS_LEAF_TRIE_NODE(TR_NODE) ((YAP_UInt)(TrNode_child(TR_NODE)) & 0x1)
132
133#define IsTrieVar(TERM, STACK, STACK_BASE) \
134 ((YAP_Term *)(TERM) > STACK && (YAP_Term *)(TERM) <= STACK_BASE)
135#define MkTrieVar(INDEX) ((INDEX) << 4)
136#define TrieVarIndex(TERM) ((TERM) >> 4)
137
138#define BASE_HASH_BUCKETS 256
139#define MAX_NODES_PER_TRIE_LEVEL 32
140#define MAX_NODES_PER_BUCKET (MAX_NODES_PER_TRIE_LEVEL / 2)
141#define HASH_TERM(TERM, SEED) (((TERM) >> 4) & (SEED))
142#define IS_HASH_NODE(NODE) (TrHash_mark(NODE) == NULL)
143
144#define BASE_SAVE_MARK \
145 10000 /* could lead to errors if the number of different variables in a term \
146 is greater than it */
147#define HASH_SAVE_MARK ((YAP_Term)MkTrieVar(BASE_SAVE_MARK))
148#define ATOM_SAVE_MARK ((YAP_Term)MkTrieVar(BASE_SAVE_MARK + 1))
149#define FUNCTOR_SAVE_MARK ((YAP_Term)MkTrieVar(BASE_SAVE_MARK + 2))
150#define FLOAT_SAVE_MARK ((YAP_Term)MkTrieVar(BASE_SAVE_MARK + 3))
151
152#define STACK_NOT_EMPTY(STACK, STACK_BASE) STACK != STACK_BASE
153#define POP_UP(STACK) *--STACK
154#define POP_DOWN(STACK) *++STACK
155#define PUSH_UP(STACK, ITEM, STACK_TOP) \
156 { \
157 if (STACK < STACK_TOP) { \
158 fprintf(stderr, "**************************************\n"); \
159 fprintf(stderr, " Tries core module: term stack full\n"); \
160 fprintf(stderr, "**************************************\n"); \
161 } \
162 *STACK = (YAP_Term)(ITEM); \
163 STACK--; \
164 }
165#define PUSH_DOWN(STACK, ITEM, STACK_TOP) \
166 { \
167 if (STACK > STACK_TOP) { \
168 fprintf(stderr, "**************************************\n"); \
169 fprintf(stderr, " Tries core module: term stack empty\n"); \
170 fprintf(stderr, "**************************************\n"); \
171 } \
172 *STACK = (YAP_Term)(ITEM); \
173 STACK++; \
174 }
175
176#define new_struct(STR, STR_TYPE, STR_SIZE) \
177 STR = (STR_TYPE *)YAP_AllocSpaceFromYap(STR_SIZE)
178#define new_trie_engine(TR_ENGINE) \
179 { \
180 new_struct(TR_ENGINE, TYPE_TR_ENGINE, SIZEOF_TR_ENGINE); \
181 TrEngine_trie(TR_ENGINE) = NULL; \
182 TrEngine_memory(TR_ENGINE) = 0; \
183 TrEngine_tries(TR_ENGINE) = 0; \
184 TrEngine_entries(TR_ENGINE) = 0; \
185 TrEngine_nodes(TR_ENGINE) = 0; \
186 TrEngine_memory_max(TR_ENGINE) = 0; \
187 TrEngine_tries_max(TR_ENGINE) = 0; \
188 TrEngine_entries_max(TR_ENGINE) = 0; \
189 TrEngine_nodes_max(TR_ENGINE) = 0; \
190 }
191#define new_trie_node(TR_NODE, ENTRY, PARENT, CHILD, NEXT, PREVIOUS) \
192 { \
193 new_struct(TR_NODE, TYPE_TR_NODE, SIZEOF_TR_NODE); \
194 TrNode_entry(TR_NODE) = ENTRY; \
195 TrNode_parent(TR_NODE) = PARENT; \
196 TrNode_child(TR_NODE) = CHILD; \
197 TrNode_next(TR_NODE) = NEXT; \
198 TrNode_previous(TR_NODE) = PREVIOUS; \
199 INCREMENT_NODES(CURRENT_TRIE_ENGINE); \
200 INCREMENT_MEMORY(CURRENT_TRIE_ENGINE, SIZEOF_TR_NODE); \
201 }
202#define new_trie_hash(TR_HASH, NUM_NODES, NUM_BUCKETS) \
203 { \
204 new_struct(TR_HASH, TYPE_TR_HASH, SIZEOF_TR_HASH); \
205 TrHash_mark(TR_HASH) = NULL; \
206 TrHash_num_buckets(TR_HASH) = NUM_BUCKETS; \
207 new_hash_buckets(TR_HASH, NUM_BUCKETS); \
208 TrHash_num_nodes(TR_HASH) = NUM_NODES; \
209 INCREMENT_MEMORY(CURRENT_TRIE_ENGINE, SIZEOF_TR_HASH); \
210 }
211#define new_hash_buckets(TR_HASH, NUM_BUCKETS) \
212 { \
213 int i; \
214 void **ptr; \
215 new_struct(ptr, void *, NUM_BUCKETS * sizeof(void *)); \
216 TrHash_buckets(TR_HASH) = (TYPE_TR_NODE **)ptr; \
217 for (i = NUM_BUCKETS; i != 0; i--) \
218 *ptr++ = NULL; \
219 INCREMENT_MEMORY(CURRENT_TRIE_ENGINE, (NUM_BUCKETS)*SIZEOF_TR_BUCKET); \
220 }
221
222#define expand_auxiliary_term_stack() \
223 { \
224 YAP_Term *aux_stack; \
225 YAP_Int aux_size = CURRENT_AUXILIARY_TERM_STACK_SIZE * sizeof(YAP_Term); \
226 new_struct(aux_stack, YAP_Term, aux_size * 2); \
227 memmove(aux_stack, AUXILIARY_TERM_STACK, aux_size); \
228 free_struct(AUXILIARY_TERM_STACK); \
229 AUXILIARY_TERM_STACK = aux_stack; \
230 CURRENT_AUXILIARY_TERM_STACK_SIZE *= 2; \
231 }
232
233#define free_struct(STR) YAP_FreeSpaceFromYap((char *)(STR))
234#define free_trie_node(STR) \
235 { \
236 free_struct(STR); \
237 DECREMENT_NODES(CURRENT_TRIE_ENGINE); \
238 DECREMENT_MEMORY(CURRENT_TRIE_ENGINE, SIZEOF_TR_NODE); \
239 }
240#define free_trie_hash(STR) \
241 { \
242 free_struct(STR); \
243 DECREMENT_MEMORY(CURRENT_TRIE_ENGINE, SIZEOF_TR_HASH); \
244 }
245#define free_hash_buckets(STR, NUM_BUCKETS) \
246 { \
247 free_struct(STR); \
248 DECREMENT_MEMORY(CURRENT_TRIE_ENGINE, (NUM_BUCKETS)*SIZEOF_TR_BUCKET); \
249 }
250
251#define INCREMENT_MEMORY(TR_ENGINE, SIZE) \
252 { \
253 TrEngine_memory(TR_ENGINE) += SIZE; \
254 if (TrEngine_memory(TR_ENGINE) > TrEngine_memory_max(TR_ENGINE)) \
255 TrEngine_memory_max(TR_ENGINE) = TrEngine_memory(TR_ENGINE); \
256 }
257#define INCREMENT_TRIES(TR_ENGINE) \
258 { \
259 TrEngine_tries(TR_ENGINE)++; \
260 if (TrEngine_tries(TR_ENGINE) > TrEngine_tries_max(TR_ENGINE)) \
261 TrEngine_tries_max(TR_ENGINE) = TrEngine_tries(TR_ENGINE); \
262 }
263#define INCREMENT_ENTRIES(TR_ENGINE) \
264 { \
265 TrEngine_entries(TR_ENGINE)++; \
266 if (TrEngine_entries(TR_ENGINE) > TrEngine_entries_max(TR_ENGINE)) \
267 TrEngine_entries_max(TR_ENGINE) = TrEngine_entries(TR_ENGINE); \
268 }
269#define INCREMENT_NODES(TR_ENGINE) \
270 { \
271 TrEngine_nodes(TR_ENGINE)++; \
272 if (TrEngine_nodes(TR_ENGINE) > TrEngine_nodes_max(TR_ENGINE)) \
273 TrEngine_nodes_max(TR_ENGINE) = TrEngine_nodes(TR_ENGINE); \
274 }
275#define DECREMENT_MEMORY(TR_ENGINE, SIZE) TrEngine_memory(TR_ENGINE) -= SIZE
276#define DECREMENT_TRIES(TR_ENGINE) TrEngine_tries(TR_ENGINE)--
277#define DECREMENT_ENTRIES(TR_ENGINE) TrEngine_entries(TR_ENGINE)--
278#define DECREMENT_NODES(TR_ENGINE) TrEngine_nodes(TR_ENGINE)--
279
280#define IS_FUNCTOR_NODE(N) \
281 (((ApplTag & TrNode_entry(N)) == ApplTag) && \
282 (TrNode_entry(N) != PairInitTag) && (TrNode_entry(N) != PairEndEmptyTag) && \
283 (TrNode_entry(N) != PairEndTermTag))
284
285/* --------------------------- */
286/* API */
287/* --------------------------- */
288
289extern TrEngine core_trie_init_module(void);
290extern TrNode core_trie_open(TrEngine engine);
291extern void core_trie_close(TrEngine engine, TrNode node,
292 void (*destruct_function)(TrNode));
293extern void core_trie_close_all(TrEngine engine,
294 void (*destruct_function)(TrNode));
295extern void core_trie_set_mode(YAP_Int mode);
296extern YAP_Int core_trie_get_mode(void);
297extern TrNode core_trie_put_entry(TrEngine engine, TrNode node, YAP_Term entry,
298 YAP_Int *depth);
299extern TrNode core_trie_check_entry(TrNode node, YAP_Term entry);
300extern YAP_Term core_trie_get_entry(TrNode node);
301extern void core_trie_remove_entry(TrEngine engine, TrNode node,
302 void (*destruct_function)(TrNode));
303extern void core_trie_remove_subtree(TrEngine engine, TrNode node,
304 void (*destruct_function)(TrNode));
305extern void core_trie_add(TrNode node_dest, TrNode node_source,
306 void (*add_function)(TrNode, TrNode));
307extern void core_trie_join(TrEngine engine, TrNode node_dest,
308 TrNode node_source,
309 void (*add_function)(TrNode, TrNode),
310 void (*copy_function)(TrNode, TrNode));
311extern void core_trie_intersect(TrEngine engine, TrNode node_dest,
312 TrNode node_source,
313 void (*add_function)(TrNode, TrNode),
314 void (*destruct_function)(TrNode));
315extern YAP_Int core_trie_count_join(TrNode node1, TrNode node2);
316extern YAP_Int core_trie_count_intersect(TrNode node1, TrNode node2);
317extern void core_trie_save(TrNode node, FILE *file,
318 void (*save_function)(TrNode, FILE *));
319extern TrNode core_trie_load(TrEngine engine, FILE *file,
320 void (*load_function)(TrNode, YAP_Int, FILE *));
321extern void core_trie_stats(TrEngine engine, YAP_Int *memory, YAP_Int *tries,
322 YAP_Int *entries, YAP_Int *nodes);
323extern void core_trie_max_stats(TrEngine engine, YAP_Int *memory,
324 YAP_Int *tries, YAP_Int *entries,
325 YAP_Int *nodes);
326extern void core_trie_usage(TrNode node, YAP_Int *entries, YAP_Int *nodes,
327 YAP_Int *virtual_nodes);
328extern void core_trie_print(TrNode node, void (*print_function)(TrNode));
329
330extern void core_disable_hash_table(void);
331extern void core_enable_hash_table(void);
332
333extern YAP_Term core_trie_to_list(TrNode node);
334
335#include "core_dbtries.h"
trie_engine
Definition: core_tries.h:56
trie_hash
Definition: core_tries.h:94
trie_node
Definition: core_tries.h:80