YAP 7.1.0
base_tries.c
1/*********************************************
2 File: base_tries.c
3 Author: Ricardo Rocha
4 Comments: Tries base module for Yap Prolog
5 version: $ID$
6*********************************************/
7
8
9
10/* -------------------------- */
11/* Includes */
12/* -------------------------- */
13
14#include <YapInterface.h>
15#include <stdio.h>
16#include <string.h>
17#include "core_tries.h"
18#include "base_tries.h"
19
20
21/* -------------------------- */
22/* Local Procedures */
23/* -------------------------- */
24
25static TrData get_data_from_trie_node(TrNode node);
26
27
28/* -------------------------- */
29/* Local Variables */
30/* -------------------------- */
31
32static TrEngine TRIE_ENGINE;
33static TrEntry FIRST_TRIE, CURRENT_TRIE;
34
35static YAP_Int CURRENT_TRAVERSE_MODE;
36
37
38/* -------------------------- */
39/* API */
40/* -------------------------- */
41
42void trie_init_module(void) {
43 TRIE_ENGINE = core_trie_init_module();
44 FIRST_TRIE = NULL;
45 CURRENT_TRAVERSE_MODE = TRAVERSE_MODE_FORWARD;
46 return;
47}
48
49
50
51void trie_data_load(TrNode node, YAP_Int depth, FILE *file) {
52 TrData data;
53
54 new_trie_data(data, CURRENT_TRIE, node);
55 PUT_DATA_IN_LEAF_TRIE_NODE(node, data);
56 return;
57}
58
59
60
61void trie_data_copy(TrNode node_dest, TrNode node_source) {
62 TrData data_dest;
63
64 new_trie_data(data_dest, CURRENT_TRIE, node_dest);
65 PUT_DATA_IN_LEAF_TRIE_NODE(node_dest, data_dest);
66 return;
67}
68
69
70
71void trie_data_destruct(TrNode node) {
72 TrEntry trie;
73 TrData data;
74
75 data = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node);
76 trie = TrData_trie(data);
77 if (data == TrEntry_traverse_data(trie)) {
78 if (CURRENT_TRAVERSE_MODE == TRAVERSE_MODE_FORWARD) {
79 TrEntry_traverse_data(trie) = TrData_previous(data);
80 } else {
81 if (TrData_next(data)) {
82 TrEntry_traverse_data(trie) = TrData_next(data);
83 } else {
84 TrData special;
85 new_struct(special, TYPE_TR_DATA, SIZEOF_TR_DATA);
86 TrData_next(special) = NULL;
87 TrData_previous(special) = TrData_previous(data);
88 TrData_trie(special) = NULL;
89 TrData_leaf(special) = NULL;
90 TrEntry_traverse_data(trie) = special; /* This special data is necessery to allow proper backwards traverse when the last entry is removed this is freed only if the trie is kept traversing */
91 }
92 }
93 }
94 if (TrData_next(data)) {
95 TrData_previous(TrData_next(data)) = TrData_previous(data);
96 TrData_next(TrData_previous(data)) = TrData_next(data);
97 } else {
98 TrEntry_last_data(trie) = TrData_previous(data);
99 TrData_next(TrData_previous(data)) = NULL;
100 }
101 free_trie_data(data);
102 return;
103}
104
105
106
107TrEntry trie_open(void) {
108 TrEntry trie;
109 TrNode node;
110
111 node = core_trie_open(TRIE_ENGINE);
112 new_trie_entry(trie, node);
113 if (FIRST_TRIE)
114 TrEntry_previous(FIRST_TRIE) = trie;
115 FIRST_TRIE = trie;
116 return trie;
117}
118
119
120
121void trie_close(TrEntry trie) {
122 core_trie_close(TRIE_ENGINE, TrEntry_trie(trie), &trie_data_destruct);
123 if (TrEntry_next(trie)) {
124 TrEntry_previous(TrEntry_next(trie)) = TrEntry_previous(trie);
125 TrEntry_next(TrEntry_previous(trie)) = TrEntry_next(trie);
126 } else
127 TrEntry_next(TrEntry_previous(trie)) = NULL;
128 free_trie_entry(trie);
129 return;
130}
131
132
133
134void trie_close_all(void) {
135 TrEntry trie;
136
137 core_trie_close_all(TRIE_ENGINE, &trie_data_destruct);
138 while (FIRST_TRIE) {
139 trie = TrEntry_next(FIRST_TRIE);
140 free_trie_entry(FIRST_TRIE);
141 FIRST_TRIE = trie;
142 }
143 return;
144}
145
146
147
148void trie_set_mode(YAP_Int mode) {
149 core_trie_set_mode(mode);
150 return;
151}
152
153
154
155YAP_Int trie_get_mode(void) {
156 return core_trie_get_mode();
157}
158
159
160
161TrData trie_put_entry(TrEntry trie, YAP_Term entry) {
162 TrData data;
163 TrNode node;
164
165 node = core_trie_put_entry(TRIE_ENGINE, TrEntry_trie(trie), entry, NULL);
166 if (!(data = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node))) {
167 new_trie_data(data, trie, node);
168 PUT_DATA_IN_LEAF_TRIE_NODE(node, data);
169 }
170 return data;
171}
172
173
174
175TrData trie_check_entry(TrEntry trie, YAP_Term entry) {
176 TrNode node;
177
178 if (!(node = core_trie_check_entry(TrEntry_trie(trie), entry)))
179 return NULL;
180 return (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node);
181}
182
183
184
185YAP_Term trie_get_entry(TrData data) {
186 return core_trie_get_entry(TrData_leaf(data));
187}
188
189
190
191TrData trie_get_first_entry(TrEntry trie) {
192 TrData data;
193
194 data = TrEntry_first_data(trie);
195 return data;
196}
197
198
199
200TrData trie_get_last_entry(TrEntry trie) {
201 TrData data;
202
203 data = TrEntry_last_data(trie);
204 if (data == AS_TR_DATA_NEXT(&TrEntry_first_data(trie)))
205 return NULL;
206 return data;
207}
208
209
210
211TrData trie_traverse_init(TrEntry trie, TrData init_data) {
212 TrData data;
213
214 if (init_data) {
215 data = TrData_next(init_data);
216 } else {
217 if (CURRENT_TRAVERSE_MODE == TRAVERSE_MODE_FORWARD)
218 data = TrEntry_first_data(trie);
219 else
220 data = trie_get_last_entry(trie);
221 }
222 TrEntry_traverse_data(trie) = data;
223 return data;
224}
225
226
227
228TrData trie_traverse_cont(TrEntry trie) {
229 TrData data, temp = NULL;
230 data = TrEntry_traverse_data(trie);
231 if (data) {
232 if (!TrData_trie(data)) {
233 if (TrEntry_first_data(trie)) {
234 temp = data;
235 } else {
236 free_trie_data(data);
237 data = NULL;
238 TrEntry_traverse_data(trie) = NULL;
239 return NULL;
240 }
241 }
242 if (CURRENT_TRAVERSE_MODE == TRAVERSE_MODE_FORWARD)
243 data = TrData_next(data);
244 else {
245 data = TrData_previous(data);
246 if (data == TrData_previous(TrEntry_first_data(trie)))
247 data = NULL;
248 }
249 TrEntry_traverse_data(trie) = data;
250 if (temp)
251 free_trie_data(temp);
252 }
253 return data;
254}
255
256
257
258void trie_remove_entry(TrData data) {
259 core_trie_remove_entry(TRIE_ENGINE, TrData_leaf(data), &trie_data_destruct);
260 return;
261}
262
263
264
265void trie_remove_subtree(TrData data) {
266 core_trie_remove_subtree(TRIE_ENGINE, TrData_leaf(data), &trie_data_destruct);
267 return;
268}
269
270
271
272void trie_join(TrEntry trie_dest, TrEntry trie_source) {
273 CURRENT_TRIE = trie_dest;
274 core_trie_join(TRIE_ENGINE, TrEntry_trie(trie_dest), TrEntry_trie(trie_source), NULL, &trie_data_copy);
275 return;
276}
277
278
279
280void trie_intersect(TrEntry trie_dest, TrEntry trie_source) {
281 core_trie_intersect(TRIE_ENGINE, TrEntry_trie(trie_dest), TrEntry_trie(trie_source), NULL, &trie_data_destruct);
282 return;
283}
284
285
286
287YAP_Int trie_count_join(TrEntry trie1, TrEntry trie2) {
288 return core_trie_count_join(TrEntry_trie(trie1), TrEntry_trie(trie2));
289}
290
291
292
293YAP_Int trie_count_intersect(TrEntry trie1, TrEntry trie2) {
294 return core_trie_count_intersect(TrEntry_trie(trie1), TrEntry_trie(trie2));
295}
296
297
298
299void trie_save(TrEntry trie, FILE *file) {
300 core_trie_save(TrEntry_trie(trie), file, NULL);
301 return;
302}
303
304
305
306TrEntry trie_load(FILE *file) {
307 TrEntry trie;
308 TrNode node;
309
310 new_trie_entry(trie, NULL);
311 CURRENT_TRIE = trie;
312 if (!(node = core_trie_load(TRIE_ENGINE, file, &trie_data_load))) {
313 free_trie_entry(trie);
314 return NULL;
315 }
316 TrEntry_trie(trie) = node;
317 if (FIRST_TRIE)
318 TrEntry_previous(FIRST_TRIE) = trie;
319 FIRST_TRIE = trie;
320 return trie;
321}
322
323
324
325void trie_stats(YAP_Int *memory, YAP_Int *tries, YAP_Int *entries, YAP_Int *nodes) {
326 core_trie_stats(TRIE_ENGINE, memory, tries, entries, nodes);
327 return;
328}
329
330
331
332void trie_max_stats(YAP_Int *memory, YAP_Int *tries, YAP_Int *entries, YAP_Int *nodes) {
333 core_trie_max_stats(TRIE_ENGINE, memory, tries, entries, nodes);
334 return;
335}
336
337
338void trie_usage(TrEntry trie, YAP_Int *entries, YAP_Int *nodes, YAP_Int *virtual_nodes) {
339 core_trie_usage(TrEntry_trie(trie), entries, nodes, virtual_nodes);
340 return;
341}
342
343
344
345void trie_print(TrEntry trie) {
346 core_trie_print(TrEntry_trie(trie), NULL);
347 return;
348}
349
350
351
352void trie_data_construct(TrNode node) {
353 TrData data;
354 new_trie_data(data, CURRENT_TRIE, node);
355 PUT_DATA_IN_LEAF_TRIE_NODE(node, data);
356 return;
357}
358
359
360
361void trie_set_traverse_mode(YAP_Int mode) {
362 CURRENT_TRAVERSE_MODE = mode;
363 return;
364}
365
366
367
368YAP_Int trie_get_traverse_mode(void) {
369 return CURRENT_TRAVERSE_MODE;
370}
371
372
373
374TrData trie_traverse_first(TrEntry trie) {
375 TrData data;
376 if (CURRENT_TRAVERSE_MODE == TRAVERSE_MODE_FORWARD)
377 data = TrEntry_first_data(trie);
378 else
379 data = TrEntry_last_data(trie);
380 return data;
381}
382
383
384
385TrData trie_traverse_next(TrData cur) {
386 TrData data = NULL;
387 if (cur) {
388 if (CURRENT_TRAVERSE_MODE == TRAVERSE_MODE_FORWARD)
389 data = TrData_next(cur);
390 else {
391 data = TrData_previous(cur);
392 if (data == TrData_previous(TrEntry_first_data(TrData_trie(cur))))
393 data = NULL;
394 }
395 }
396 return data;
397}
398
399
400
401void trie_disable_hash_table(void) {
402 core_disable_hash_table();
403 return;
404}
405
406
407
408void trie_enable_hash_table(void) {
409 core_enable_hash_table();
410 return;
411}
412
413
414/* -------------------------- */
415/* Local Procedures */
416/* -------------------------- */
417
418static
419TrData get_data_from_trie_node(TrNode node) {
420 while(!IS_LEAF_TRIE_NODE(node))
421 node = TrNode_child(node);
422 return (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node);
423}
424
425
426
427YAP_Term trie_to_list(TrEntry trie) {
428 return core_trie_to_list(TrEntry_trie(trie));
429}
430
431#include "base_dbtries.c"
itrie_data
Definition: base_itries.h:50
itrie_entry
Definition: base_itries.h:27
trie_engine
Definition: core_tries.h:56
trie_node
Definition: core_tries.h:80