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