YAP 7.1.0
base_itries.c
1/*********************************
2 File: base_itries.c
3 Author: Ricardo Rocha
4 Comments: Tries module for ILP
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_itries.h"
19
20
21
22/* -------------------------- */
23/* Local Variables */
24/* -------------------------- */
25
26static TrEngine ITRIE_ENGINE;
27static TrEntry FIRST_ITRIE, CURRENT_ITRIE;
28
29
30
31/* -------------------------- */
32/* API */
33/* -------------------------- */
34
35
36void itrie_init_module(void) {
37 ITRIE_ENGINE = core_trie_init_module();
38 FIRST_ITRIE = NULL;
39 return;
40}
41
42
43
44void itrie_data_save(TrNode node, FILE *file) {
45 TrData data;
46
47 data = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node);
48 fprintf(file, Int_FORMAT " " Int_FORMAT " " Int_FORMAT " ", TrData_pos(data), TrData_neg(data), TrData_timestamp(data));
49 return;
50}
51
52
53
54void itrie_data_load(TrNode node, YAP_Int depth, FILE *file) {
55 TrData data;
56 YAP_Int pos, neg, timestamp;
57
58 fscanf(file, Int_FORMAT " " Int_FORMAT " " Int_FORMAT, &pos, &neg, &timestamp);
59 new_itrie_data(data, CURRENT_ITRIE, node, pos, neg, timestamp, depth);
60 PUT_DATA_IN_LEAF_TRIE_NODE(node, data);
61 return;
62}
63
64
65
66void itrie_data_print(TrNode node) {
67 TrData data;
68
69 data = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node);
70 printf(" pos: " Int_FORMAT " neg: " Int_FORMAT " timestamp: " Int_FORMAT "\\n", TrData_pos(data), TrData_neg(data), TrData_timestamp(data));
71 return;
72}
73
74
75
76void itrie_data_copy(TrNode node_dest, TrNode node_source) {
77 TrData data_dest, data_source;
78
79 data_source = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node_source);
80 new_itrie_data(data_dest, CURRENT_ITRIE, node_dest, TrData_pos(data_source), TrData_neg(data_source), TrData_timestamp(data_source), TrData_depth(data_source));
81 PUT_DATA_IN_LEAF_TRIE_NODE(node_dest, data_dest);
82 return;
83}
84
85
86
87void itrie_data_destruct(TrNode node) {
88 TrEntry itrie;
89 TrData data;
90
91 data = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node);
92 itrie = TrData_itrie(data);
93 if (data == TrEntry_traverse_data(itrie))
94 TrEntry_traverse_data(itrie) = TrData_next(data);
95 if (TrData_next(data)) {
96 TrData_previous(TrData_next(data)) = TrData_previous(data);
97 TrData_next(TrData_previous(data)) = TrData_next(data);
98 } else
99 TrData_next(TrData_previous(data)) = NULL;
100 free_itrie_data(data);
101 return;
102}
103
104
105
106void itrie_data_add(TrNode node_dest, TrNode node_source) {
107 TrData data_dest, data_source;
108
109 data_dest = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node_dest);
110 data_source = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node_source);
111 TrData_pos(data_dest) += TrData_pos(data_source);
112 TrData_neg(data_dest) += TrData_neg(data_source);
113 if (TrData_timestamp(data_dest) < TrData_timestamp(data_source))
114 TrData_timestamp(data_dest) = TrData_timestamp(data_source);
115 return;
116}
117
118
119
120void itrie_data_subtract(TrNode node_dest, TrNode node_source) {
121 TrData data_dest, data_source;
122
123 data_dest = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node_dest);
124 data_source = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node_source);
125 TrData_pos(data_dest) -= TrData_pos(data_source);
126 TrData_neg(data_dest) -= TrData_neg(data_source);
127 if (TrData_timestamp(data_dest) < TrData_timestamp(data_source))
128 TrData_timestamp(data_dest) = TrData_timestamp(data_source);
129 return;
130}
131
132
133
134TrEntry itrie_open(void) {
135 TrEntry itrie;
136 TrNode node;
137
138 node = core_trie_open(ITRIE_ENGINE);
139 new_itrie_entry(itrie, node);
140 if (FIRST_ITRIE)
141 TrEntry_previous(FIRST_ITRIE) = itrie;
142 FIRST_ITRIE = itrie;
143 return itrie;
144}
145
146
147
148void itrie_close(TrEntry itrie) {
149 core_trie_close(ITRIE_ENGINE, TrEntry_trie(itrie), &itrie_data_destruct);
150 if (TrEntry_next(itrie)) {
151 TrEntry_previous(TrEntry_next(itrie)) = TrEntry_previous(itrie);
152 TrEntry_next(TrEntry_previous(itrie)) = TrEntry_next(itrie);
153 } else
154 TrEntry_next(TrEntry_previous(itrie)) = NULL;
155 free_itrie_entry(itrie);
156 return;
157}
158
159
160
161void itrie_close_all(void) {
162 TrEntry itrie;
163
164 core_trie_close_all(ITRIE_ENGINE, &itrie_data_destruct);
165 while (FIRST_ITRIE) {
166 itrie = TrEntry_next(FIRST_ITRIE);
167 free_itrie_entry(FIRST_ITRIE);
168 FIRST_ITRIE = itrie;
169 }
170 return;
171}
172
173
174
175void itrie_set_mode(TrEntry itrie, YAP_Int mode) {
176 TrEntry_mode(itrie) = mode;
177 return;
178}
179
180
181
182YAP_Int itrie_get_mode(TrEntry itrie) {
183 return TrEntry_mode(itrie);
184}
185
186
187
188void itrie_set_timestamp(TrEntry itrie, YAP_Int timestamp) {
189 TrEntry_timestamp(itrie) = timestamp;
190 return;
191}
192
193
194
195YAP_Int itrie_get_timestamp(TrEntry itrie) {
196 return TrEntry_timestamp(itrie);
197}
198
199
200
201void itrie_put_entry(TrEntry itrie, YAP_Term entry) {
202 TrData data;
203 TrNode node;
204 YAP_Int depth;
205
206 node = core_trie_put_entry(ITRIE_ENGINE, TrEntry_trie(itrie), entry, &depth);
207 if (!(data = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node))) {
208 new_itrie_data(data, itrie, node, 0, 0, -1, depth);
209 PUT_DATA_IN_LEAF_TRIE_NODE(node, data);
210 }
211 update_itrie_data(data, TrEntry_timestamp(itrie), TrEntry_mode(itrie));
212 return;
213}
214
215
216
217void itrie_update_entry(TrEntry itrie, YAP_Term entry) {
218 TrData data;
219 TrNode node;
220
221 if ((node = core_trie_check_entry(TrEntry_trie(itrie), entry)) != NULL) {
222 data = (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node);
223 update_itrie_data(data, TrEntry_timestamp(itrie), TrEntry_mode(itrie));
224 }
225 return;
226}
227
228
229
230TrData itrie_check_entry(TrEntry itrie, YAP_Term entry) {
231 TrNode node;
232
233 if (!(node = core_trie_check_entry(TrEntry_trie(itrie), entry)))
234 return NULL;
235 return (TrData) GET_DATA_FROM_LEAF_TRIE_NODE(node);
236}
237
238
239
240YAP_Term itrie_get_entry(TrData data) {
241 return core_trie_get_entry(TrData_leaf(data));
242}
243
244
245
246void itrie_get_data(TrData data, YAP_Int *pos, YAP_Int *neg, YAP_Int *timestamp) {
247 *pos = TrData_pos(data);
248 *neg = TrData_neg(data);
249 *timestamp = TrData_timestamp(data);
250 return;
251}
252
253
254
255TrData itrie_traverse_init(TrEntry itrie) {
256 TrData data, *bucket;
257 YAP_Int traverse_bucket = 0;
258
259 do {
260 bucket = TrEntry_bucket(itrie, traverse_bucket);
261 traverse_bucket++;
262 } while (!*bucket && traverse_bucket != TrEntry_num_buckets(itrie));
263 data = *bucket;
264 if (data) {
265 TrEntry_traverse_bucket(itrie) = traverse_bucket;
266 TrEntry_traverse_data(itrie) = TrData_next(data);
267 }
268 return data;
269}
270
271
272
273TrData itrie_traverse_cont(TrEntry itrie) {
274 TrData data, *bucket;
275 YAP_Int traverse_bucket;
276
277 data = TrEntry_traverse_data(itrie);
278 if (!data) {
279 traverse_bucket = TrEntry_traverse_bucket(itrie);
280 if (traverse_bucket == TrEntry_num_buckets(itrie))
281 return NULL;
282 do {
283 bucket = TrEntry_bucket(itrie, traverse_bucket);
284 traverse_bucket++;
285 } while (!*bucket && traverse_bucket != TrEntry_num_buckets(itrie));
286 data = *bucket;
287 if (data) {
288 TrEntry_traverse_bucket(itrie) = traverse_bucket;
289 TrEntry_traverse_data(itrie) = TrData_next(data);
290 }
291 } else
292 TrEntry_traverse_data(itrie) = TrData_next(data);
293 return data;
294}
295
296
297
298void itrie_remove_entry(TrData data) {
299 core_trie_remove_entry(ITRIE_ENGINE, TrData_leaf(data), &itrie_data_destruct);
300 return;
301}
302
303
304
305void itrie_remove_subtree(TrData data) {
306 core_trie_remove_subtree(ITRIE_ENGINE, TrData_leaf(data), &itrie_data_destruct);
307 return;
308}
309
310
311
312void itrie_add(TrEntry itrie_dest, TrEntry itrie_source) {
313 core_trie_add(TrEntry_trie(itrie_dest), TrEntry_trie(itrie_source), &itrie_data_add);
314 return;
315}
316
317
318
319void itrie_subtract(TrEntry itrie_dest, TrEntry itrie_source) {
320 core_trie_add(TrEntry_trie(itrie_dest), TrEntry_trie(itrie_source), &itrie_data_subtract);
321 return;
322}
323
324
325
326void itrie_join(TrEntry itrie_dest, TrEntry itrie_source) {
327 CURRENT_ITRIE = itrie_dest;
328 core_trie_join(ITRIE_ENGINE, TrEntry_trie(itrie_dest), TrEntry_trie(itrie_source), &itrie_data_add, &itrie_data_copy);
329 return;
330}
331
332
333
334void itrie_intersect(TrEntry itrie_dest, TrEntry itrie_source) {
335 core_trie_intersect(ITRIE_ENGINE, TrEntry_trie(itrie_dest), TrEntry_trie(itrie_source), &itrie_data_add, &itrie_data_destruct);
336 return;
337}
338
339
340
341YAP_Int itrie_count_join(TrEntry itrie1, TrEntry itrie2) {
342 return core_trie_count_join(TrEntry_trie(itrie1), TrEntry_trie(itrie2));
343}
344
345
346
347YAP_Int itrie_count_intersect(TrEntry itrie1, TrEntry itrie2) {
348 return core_trie_count_intersect(TrEntry_trie(itrie1), TrEntry_trie(itrie2));
349}
350
351
352
353void itrie_save(TrEntry itrie, FILE *file) {
354 core_trie_save(TrEntry_trie(itrie), file, &itrie_data_save);
355 return;
356}
357
358
359
360void itrie_save_as_trie(TrEntry itrie, FILE *file) {
361 core_trie_save(TrEntry_trie(itrie), file, NULL);
362 return;
363}
364
365
366
367TrEntry itrie_load(FILE *file) {
368 TrEntry itrie;
369 TrNode node;
370
371 new_itrie_entry(itrie, NULL);
372 CURRENT_ITRIE = itrie;
373 if (!(node = core_trie_load(ITRIE_ENGINE, file, &itrie_data_load))) {
374 free_itrie_entry(itrie);
375 return NULL;
376 }
377 TrEntry_trie(itrie) = node;
378 if (FIRST_ITRIE)
379 TrEntry_previous(FIRST_ITRIE) = itrie;
380 FIRST_ITRIE = itrie;
381 return itrie;
382}
383
384
385
386void itrie_stats(YAP_Int *memory, YAP_Int *tries, YAP_Int *entries, YAP_Int *nodes) {
387 core_trie_stats(ITRIE_ENGINE, memory, tries, entries, nodes);
388 return;
389}
390
391
392
393void itrie_max_stats(YAP_Int *memory, YAP_Int *tries, YAP_Int *entries, YAP_Int *nodes) {
394 core_trie_max_stats(ITRIE_ENGINE, memory, tries, entries, nodes);
395 return;
396}
397
398
399
400void itrie_usage(TrEntry itrie, YAP_Int *entries, YAP_Int *nodes, YAP_Int *virtual_nodes) {
401 core_trie_usage(TrEntry_trie(itrie), entries, nodes, virtual_nodes);
402 return;
403}
404
405
406
407void itrie_print(TrEntry itrie) {
408 core_trie_print(TrEntry_trie(itrie), &itrie_data_print);
409 return;
410}
bucket
Definition: hash.h:40
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