YAP 7.1.0
base_tries.h
1/*********************************************
2 File: base_tries.h
3 Author: Ricardo Rocha
4 Comments: Tries base module for Yap Prolog
5 version: $ID$
6*********************************************/
7
8#ifndef BASE_TRIES_H
9
10/* --------------------------- */
11/* Defines */
12/* --------------------------- */
13
14#define TRAVERSE_MODE_FORWARD 0
15#define TRAVERSE_MODE_BACKWARD 1
16
17
18/* --------------------------- */
19/* Structs */
20/* --------------------------- */
21
22typedef struct trie_entry {
23 struct trie_node *top_trie_node;
24 struct trie_data *first_trie_data;
25 struct trie_data *last_trie_data;
26 struct trie_data *traverse_trie_data;
27 struct trie_entry *next;
28 struct trie_entry *previous;
29} *TrEntry;
30
31#define TrEntry_trie(X) ((X)->top_trie_node)
32#define TrEntry_first_data(X) ((X)->first_trie_data)
33#define TrEntry_last_data(X) ((X)->last_trie_data)
34#define TrEntry_traverse_data(X) ((X)->traverse_trie_data)
35#define TrEntry_next(X) ((X)->next)
36#define TrEntry_previous(X) ((X)->previous)
37
38typedef struct trie_data {
39 struct trie_entry *trie;
40 struct trie_node *leaf_trie_node;
41 struct trie_data *next;
42 struct trie_data *previous;
43} *TrData;
44
45#define TrData_trie(X) ((X)->trie)
46#define TrData_leaf(X) ((X)->leaf_trie_node)
47#define TrData_next(X) ((X)->next)
48#define TrData_previous(X) ((X)->previous)
49
50#define TYPE_TR_ENTRY struct trie_entry
51#define TYPE_TR_DATA struct trie_data
52#define SIZEOF_TR_ENTRY sizeof(TYPE_TR_ENTRY)
53#define SIZEOF_TR_DATA sizeof(TYPE_TR_DATA)
54
55#define AS_TR_ENTRY_NEXT(ADDR) (TrEntry)((YAP_UInt)(ADDR) - sizeof(struct trie_node *) - 3 * sizeof(struct trie_data *))
56#define AS_TR_DATA_NEXT(ADDR) (TrData)((YAP_UInt)(ADDR) - sizeof(struct trie_entry *) - sizeof(struct trie_node *))
57
58
59
60/* --------------------------- */
61/* Macros */
62/* --------------------------- */
63
64#define new_trie_entry(TR_ENTRY, TR_NODE) \
65 { new_struct(TR_ENTRY, TYPE_TR_ENTRY, SIZEOF_TR_ENTRY); \
66 TrEntry_trie(TR_ENTRY) = TR_NODE; \
67 TrEntry_first_data(TR_ENTRY) = NULL; \
68 TrEntry_last_data(TR_ENTRY) = AS_TR_DATA_NEXT(&TrEntry_first_data(TR_ENTRY)); \
69 TrEntry_traverse_data(TR_ENTRY) = NULL; \
70 TrEntry_next(TR_ENTRY) = FIRST_TRIE; \
71 TrEntry_previous(TR_ENTRY) = AS_TR_ENTRY_NEXT(&FIRST_TRIE); \
72 INCREMENT_MEMORY(TRIE_ENGINE, SIZEOF_TR_ENTRY); \
73 }
74#define new_trie_data(TR_DATA, TR_ENTRY, TR_NODE) \
75 { TrData first_data = TrEntry_first_data(TR_ENTRY); \
76 new_struct(TR_DATA, TYPE_TR_DATA, SIZEOF_TR_DATA); \
77 TrData_trie(TR_DATA) = TR_ENTRY; \
78 TrData_leaf(TR_DATA) = TR_NODE; \
79 TrData_next(TR_DATA) = NULL; \
80 if (first_data) { \
81 TrData last_data = TrEntry_last_data(TR_ENTRY); \
82 TrData_next(last_data) = TR_DATA; \
83 TrData_previous(TR_DATA) = last_data; \
84 } else { \
85 TrData_previous(TR_DATA) = AS_TR_DATA_NEXT(&TrEntry_first_data(TR_ENTRY)); \
86 TrEntry_first_data(TR_ENTRY) = TR_DATA; \
87 } \
88 TrEntry_last_data(TR_ENTRY) = TR_DATA; \
89 INCREMENT_MEMORY(TRIE_ENGINE, SIZEOF_TR_DATA); \
90 }
91
92
93
94#define free_trie_entry(STR) \
95 { free_struct(STR); \
96 DECREMENT_MEMORY(TRIE_ENGINE, SIZEOF_TR_ENTRY); \
97 }
98#define free_trie_data(STR) \
99 { free_struct(STR); \
100 DECREMENT_MEMORY(TRIE_ENGINE, SIZEOF_TR_DATA); \
101 }
102
103
104
105/* --------------------------- */
106/* API */
107/* --------------------------- */
108
109void trie_init_module(void);
110void trie_data_load(TrNode node, YAP_Int depth, FILE *file);
111void trie_data_copy(TrNode node_dest, TrNode node_source);
112void trie_data_destruct(TrNode node);
113TrEntry trie_open(void);
114void trie_close(TrEntry trie);
115void trie_close_all(void);
116void trie_set_mode(YAP_Int mode);
117YAP_Int trie_get_mode(void);
118TrData trie_put_entry(TrEntry trie, YAP_Term entry);
119TrData trie_check_entry(TrEntry trie, YAP_Term entry);
120YAP_Term trie_get_entry(TrData data);
121TrData trie_get_first_entry(TrEntry trie);
122TrData trie_get_last_entry(TrEntry trie);
123TrData trie_traverse_init(TrEntry trie, TrData init_data);
124TrData trie_traverse_cont(TrEntry trie);
125void trie_remove_entry(TrData data);
126void trie_remove_subtree(TrData data);
127void trie_join(TrEntry trie_dest, TrEntry trie_source);
128void trie_intersect(TrEntry trie_dest, TrEntry trie_source);
129YAP_Int trie_count_join(TrEntry trie1, TrEntry trie2);
130YAP_Int trie_count_intersect(TrEntry trie1, TrEntry trie2);
131void trie_save(TrEntry trie, FILE *file);
132TrEntry trie_load(FILE *file);
133void trie_stats(YAP_Int *memory, YAP_Int *tries, YAP_Int *entries, YAP_Int *nodes);
134void trie_max_stats(YAP_Int *memory, YAP_Int *tries, YAP_Int *entries, YAP_Int *nodes);
135void trie_usage(TrEntry trie, YAP_Int *entries, YAP_Int *nodes, YAP_Int *virtual_nodes);
136void trie_print(TrEntry trie);
137
138extern void trie_data_construct(TrNode node);
139extern void trie_set_traverse_mode(YAP_Int mode);
140extern YAP_Int trie_get_traverse_mode(void);
141extern TrData trie_traverse_first(TrEntry trie);
142extern TrData trie_traverse_next(TrData data);
143extern void trie_disable_hash_table(void);
144extern void trie_enable_hash_table(void);
145
146YAP_Term trie_to_list(TrEntry trie);
147
148#include "base_dbtries.h"
149
150#endif
itrie_data
Definition: base_itries.h:50
itrie_entry
Definition: base_itries.h:27
trie_data
Definition: base_tries.h:38
trie_entry
Definition: base_tries.h:22
trie_node
Definition: core_tries.h:80