YAP 7.1.0
base_itries.h
1/*********************************
2 File: base_itries.h
3 Author: Ricardo Rocha
4 Comments: Tries module for ILP
5 version: $ID$
6*********************************/
7
8
9
10/* --------------------------- */
11/* Defines */
12/* --------------------------- */
13
14#define ITRIES_MODE_NONE 0
15#define ITRIES_MODE_INC_POS 1
16#define ITRIES_MODE_DEC_POS 2
17#define ITRIES_MODE_INC_NEG 3
18#define ITRIES_MODE_DEC_NEG 4
19#define BASE_TR_DATA_BUCKETS 20
20
21
22
23/* --------------------------- */
24/* Structs */
25/* --------------------------- */
26
27typedef struct itrie_entry {
28 struct trie_node *top_trie_node;
29 struct itrie_data **trie_data_buckets;
30 struct itrie_data *traverse_trie_data;
31 struct itrie_entry *next;
32 struct itrie_entry *previous;
33 YAP_Int mode;
34 YAP_Int timestamp;
35 YAP_Int number_of_buckets;
36 YAP_Int traverse_bucket;
37} *TrEntry;
38
39#define TrEntry_trie(X) ((X)->top_trie_node)
40#define TrEntry_buckets(X) ((X)->trie_data_buckets)
41#define TrEntry_bucket(X,N) ((X)->trie_data_buckets + N)
42#define TrEntry_traverse_data(X) ((X)->traverse_trie_data)
43#define TrEntry_next(X) ((X)->next)
44#define TrEntry_previous(X) ((X)->previous)
45#define TrEntry_mode(X) ((X)->mode)
46#define TrEntry_timestamp(X) ((X)->timestamp)
47#define TrEntry_num_buckets(X) ((X)->number_of_buckets)
48#define TrEntry_traverse_bucket(X) ((X)->traverse_bucket)
49
50typedef struct itrie_data {
51 struct itrie_entry *itrie;
52 struct trie_node *leaf_trie_node;
53 struct itrie_data *next;
54 struct itrie_data *previous;
55 YAP_Int pos;
56 YAP_Int neg;
57 YAP_Int timestamp;
58 YAP_Int depth;
59} *TrData;
60
61#define TrData_itrie(X) ((X)->itrie)
62#define TrData_leaf(X) ((X)->leaf_trie_node)
63#define TrData_next(X) ((X)->next)
64#define TrData_previous(X) ((X)->previous)
65#define TrData_pos(X) ((X)->pos)
66#define TrData_neg(X) ((X)->neg)
67#define TrData_timestamp(X) ((X)->timestamp)
68#define TrData_depth(X) ((X)->depth)
69
70#define TYPE_TR_ENTRY struct itrie_entry
71#define TYPE_TR_DATA struct itrie_data
72#define SIZEOF_TR_ENTRY sizeof(TYPE_TR_ENTRY)
73#define SIZEOF_TR_DATA sizeof(TYPE_TR_DATA)
74#define SIZEOF_TR_DATA_BUCKET sizeof(TYPE_TR_DATA *)
75
76#define AS_TR_ENTRY_NEXT(ADDR) (TrEntry)((YAP_UInt)(ADDR) - sizeof(struct trie_node *) - sizeof(struct itrie_data **) - sizeof(struct itrie_data *))
77#define AS_TR_DATA_NEXT(ADDR) (TrData)((YAP_UInt)(ADDR) - sizeof(struct itrie_entry *) - sizeof(struct trie_node *))
78
79
80
81/* --------------------------- */
82/* Macros */
83/* --------------------------- */
84
85#define new_itrie_entry(TR_ENTRY, TR_NODE) \
86 { new_struct(TR_ENTRY, TYPE_TR_ENTRY, SIZEOF_TR_ENTRY); \
87 TrEntry_mode(TR_ENTRY) = ITRIES_MODE_NONE; \
88 TrEntry_timestamp(TR_ENTRY) = -1; \
89 TrEntry_num_buckets(TR_ENTRY) = BASE_TR_DATA_BUCKETS; \
90 new_itrie_buckets(TR_ENTRY, BASE_TR_DATA_BUCKETS); \
91 TrEntry_trie(TR_ENTRY) = TR_NODE; \
92 TrEntry_next(TR_ENTRY) = FIRST_ITRIE; \
93 TrEntry_previous(TR_ENTRY) = AS_TR_ENTRY_NEXT(&FIRST_ITRIE); \
94 INCREMENT_MEMORY(ITRIE_ENGINE, SIZEOF_TR_ENTRY); \
95 }
96#define new_itrie_buckets(TR_ENTRY, NUM_BUCKETS) \
97 { YAP_Int i; void **ptr; \
98 new_struct(ptr, void *, NUM_BUCKETS * sizeof(void *)); \
99 TrEntry_buckets(TR_ENTRY) = (TYPE_TR_DATA **) ptr; \
100 for (i = NUM_BUCKETS; i != 0; i--) \
101 *ptr++ = NULL; \
102 INCREMENT_MEMORY(ITRIE_ENGINE, (NUM_BUCKETS) * SIZEOF_TR_DATA_BUCKET); \
103 }
104#define new_itrie_data(TR_DATA, TR_ENTRY, TR_NODE, POS, NEG, TIME, DEPTH) \
105 { TrData *bucket; \
106 new_struct(TR_DATA, TYPE_TR_DATA, SIZEOF_TR_DATA); \
107 TrData_pos(TR_DATA) = POS; \
108 TrData_neg(TR_DATA) = NEG; \
109 TrData_timestamp(TR_DATA) = TIME; \
110 TrData_depth(TR_DATA) = DEPTH; \
111 TrData_itrie(TR_DATA) = TR_ENTRY; \
112 TrData_leaf(TR_DATA) = TR_NODE; \
113 if (DEPTH >= TrEntry_num_buckets(TR_ENTRY)) { \
114 YAP_Int i, new_num_buckets = DEPTH + BASE_TR_DATA_BUCKETS; \
115 bucket = TrEntry_buckets(TR_ENTRY); \
116 new_itrie_buckets(TR_ENTRY, new_num_buckets); \
117 memmove(TrEntry_buckets(TR_ENTRY), bucket, \
118 TrEntry_num_buckets(TR_ENTRY) * SIZEOF_TR_DATA_BUCKET); \
119 free_itrie_buckets(bucket, TrEntry_num_buckets(TR_ENTRY)); \
120 bucket = TrEntry_buckets(TR_ENTRY); \
121 for (i = 0; i != TrEntry_num_buckets(TR_ENTRY); i++) { \
122 if (*bucket) \
123 TrData_previous(*bucket) = AS_TR_DATA_NEXT(bucket); \
124 bucket++; \
125 } \
126 TrEntry_num_buckets(TR_ENTRY) = new_num_buckets; \
127 } \
128 bucket = TrEntry_bucket(TR_ENTRY, DEPTH); \
129 TrData_next(TR_DATA) = *bucket; \
130 TrData_previous(TR_DATA) = AS_TR_DATA_NEXT(bucket); \
131 if (*bucket) \
132 TrData_previous(*bucket) = TR_DATA; \
133 *bucket = TR_DATA; \
134 INCREMENT_MEMORY(ITRIE_ENGINE, SIZEOF_TR_DATA); \
135 }
136#define update_itrie_data(TR_DATA, TIMESTAMP, ITRIES_MODE) \
137 if (TrData_timestamp(TR_DATA) != TIMESTAMP) { \
138 if (ITRIES_MODE == ITRIES_MODE_INC_POS) \
139 TrData_pos(TR_DATA)++; \
140 else if (ITRIES_MODE == ITRIES_MODE_DEC_POS) \
141 TrData_pos(TR_DATA)--; \
142 else if (ITRIES_MODE == ITRIES_MODE_INC_NEG) \
143 TrData_neg(TR_DATA)++; \
144 else if (ITRIES_MODE == ITRIES_MODE_DEC_NEG) \
145 TrData_neg(TR_DATA)--; \
146 TrData_timestamp(TR_DATA) = TIMESTAMP; \
147 }
148
149
150
151#define free_itrie_entry(STR) \
152 { free_itrie_buckets(TrEntry_buckets(STR), TrEntry_num_buckets(STR)); \
153 free_struct(STR); \
154 DECREMENT_MEMORY(ITRIE_ENGINE, SIZEOF_TR_ENTRY); \
155 }
156#define free_itrie_buckets(STR, NUM_BUCKETS) \
157 { free_struct(STR); \
158 DECREMENT_MEMORY(ITRIE_ENGINE, (NUM_BUCKETS) * SIZEOF_TR_DATA_BUCKET); \
159 }
160#define free_itrie_data(STR) \
161 { free_struct(STR); \
162 DECREMENT_MEMORY(ITRIE_ENGINE, SIZEOF_TR_DATA); \
163 }
164
165
166
167/* --------------------------- */
168/* API */
169/* --------------------------- */
170
171void itrie_init_module(void);
172void itrie_data_save(TrNode node, FILE *file);
173void itrie_data_load(TrNode node, YAP_Int depth, FILE *file);
174void itrie_data_print(TrNode node);
175void itrie_data_copy(TrNode node_dest, TrNode node_source);
176void itrie_data_destruct(TrNode node);
177void itrie_data_add(TrNode node_dest, TrNode node_source);
178void itrie_data_subtract(TrNode node_dest, TrNode node_source);
179TrEntry itrie_open(void);
180void itrie_close(TrEntry itrie);
181void itrie_close_all(void);
182void itrie_set_mode(TrEntry itrie, YAP_Int mode);
183YAP_Int itrie_get_mode(TrEntry itrie);
184void itrie_set_timestamp(TrEntry itrie, YAP_Int timestamp);
185YAP_Int itrie_get_timestamp(TrEntry itrie);
186void itrie_put_entry(TrEntry itrie, YAP_Term entry);
187void itrie_update_entry(TrEntry itrie, YAP_Term entry);
188TrData itrie_check_entry(TrEntry itrie, YAP_Term entry);
189YAP_Term itrie_get_entry(TrData data);
190void itrie_get_data(TrData data, YAP_Int *pos, YAP_Int *neg, YAP_Int *timestamp);
191TrData itrie_traverse_init(TrEntry itrie);
192TrData itrie_traverse_cont(TrEntry itrie);
193void itrie_remove_entry(TrData data);
194void itrie_remove_subtree(TrData data);
195void itrie_add(TrEntry itrie_dest, TrEntry itrie_source);
196void itrie_subtract(TrEntry itrie_dest, TrEntry itrie_source);
197void itrie_join(TrEntry itrie_dest, TrEntry itrie_source);
198void itrie_intersect(TrEntry itrie_dest, TrEntry itrie_source);
199YAP_Int itrie_count_join(TrEntry itrie1, TrEntry itrie2);
200YAP_Int itrie_count_intersect(TrEntry itrie1, TrEntry itrie2);
201void itrie_save(TrEntry itrie, FILE *file);
202void itrie_save_as_trie(TrEntry itrie, FILE *file);
203TrEntry itrie_load(FILE *file);
204void itrie_stats(YAP_Int *memory, YAP_Int *tries, YAP_Int *entries, YAP_Int *nodes);
205void itrie_max_stats(YAP_Int *memory, YAP_Int *tries, YAP_Int *entries, YAP_Int *nodes);
206void itrie_usage(TrEntry itrie, YAP_Int *entries, YAP_Int *nodes, YAP_Int *virtual_nodes);
207void itrie_print(TrEntry itrie);
itrie_data
Definition: base_itries.h:50
itrie_entry
Definition: base_itries.h:27
trie_node
Definition: core_tries.h:80