1 /* Part of SWI-Prolog
2
3 Author: Jan Wielemaker
4 E-mail: J.Wielemaker@vu.nl
5 WWW: http://www.swi-prolog.org
6 Copyright (c) 2017-2020, VU University Amsterdam
7 CWI, Amsterdam
8 All rights reserved.
9
10 Redistribution and use in source and binary forms, with or without
11 modification, are permitted provided that the following conditions
12 are met:
13
14 1. Redistributions of source code must retain the above copyright
15 notice, this list of conditions and the following disclaimer.
16
17 2. Redistributions in binary form must reproduce the above copyright
18 notice, this list of conditions and the following disclaimer in
19 the documentation and/or other materials provided with the
20 distribution.
21
22 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 POSSIBILITY OF SUCH DAMAGE.
34 */
35
36 #ifndef _PL_TRIE_H
37 #define _PL_TRIE_H
38 #include "pl-indirect.h"
39 #include "pl-copyterm.h"
40
41 /* keep statistics on trie accesses */
42 #define O_TRIE_STATS 1
43
44 #define TRIE_MAGIC 0x4bcbcf87
45 #define TRIE_CMAGIC 0x4bcbcf88
46
47 typedef enum
48 { TN_KEY, /* Single key */
49 TN_HASHED /* Hashed */
50 } tn_node_type;
51
52 typedef struct try_children_any
53 { tn_node_type type;
54 } try_children_any;
55
56 typedef struct trie_children_key
57 { tn_node_type type;
58 word key;
59 struct trie_node *child;
60 } trie_children_key;
61
62 typedef struct trie_children_hashed
63 { tn_node_type type; /* TN_HASHED */
64 Table table; /* Key --> child map */
65 unsigned var_mask; /* Variables in this place */
66 trie_children_key *old_single; /* Old single node */
67 } trie_children_hashed;
68
69 typedef union trie_children
70 { try_children_any *any;
71 trie_children_key *key;
72 trie_children_hashed *hash;
73 } trie_children;
74
75
76 #define TN_PRIMARY 0x0001 /* Primary value node */
77 #define TN_SECONDARY 0x0002 /* Secondary value node */
78 #define TN_PRUNED 0x0004 /* Node path was pruned */
79 #define TN_IDG_DELETED 0x0008 /* IDG pre-evaluation */
80 #define TN_IDG_ADDED 0x0010 /* IDG recovery */
81 #define TN_IDG_UNCONDITIONAL 0x0020 /* IDG: previous cond state */
82 #define TN_IDG_SAVED_UNCONDITIONAL 0x0040 /* IDG recovery */
83 #define TN_IDG_MASK \
84 (TN_IDG_DELETED|TN_IDG_ADDED| \
85 TN_IDG_UNCONDITIONAL|TN_IDG_SAVED_UNCONDITIONAL)
86
87 typedef struct trie_node
88 { word value;
89 word key;
90 struct trie_node *parent;
91 trie_children children;
92 struct
93 { struct delay_info *delayinfo; /* can be unified with children */
94 } data;
95 unsigned flags; /* TN_* */
96 } trie_node;
97
98 #define TRIE_ISSET 0x0001 /* Trie nodes have no value */
99 #define TRIE_ISMAP 0x0002 /* Trie nodes have a value */
100 #define TRIE_ISSHARED 0x0004 /* This is a shared answer trie */
101 #define TRIE_COMPLETE 0x0008 /* Answer trie is complete */
102 #define TRIE_ABOLISH_ON_COMPLETE 0x0010 /* Abolish the table when completed */
103
104 typedef struct trie
105 { atom_t symbol; /* The associated symbol */
106 int magic; /* TRIE_MAGIC */
107 int references; /* access count */
108 unsigned int node_count; /* # nodes */
109 unsigned int value_count; /* # nodes with a value */
110 unsigned int flags; /* misc flags */
111 #ifdef O_PLMT
112 int tid; /* thread id doing completion or re-evaluation */
113 #endif
114 trie_node root; /* the root node */
115 indirect_table *indirects; /* indirect values */
116 void (*release_node)(struct trie *, trie_node *);
117 alloc_pool *alloc_pool; /* Node allocation pool */
118 atom_t clause; /* Compiled representation */
119 #ifdef O_TRIE_STATS
120 struct
121 { uint64_t lookups; /* trie_lookup */
122 uint64_t gen_call; /* trie_gen calls */
123 #ifdef O_PLMT
124 unsigned int deadlock; /* times involved in a deadlock */
125 unsigned int wait; /* times waited for */
126 #endif
127 } stats;
128 #endif
129 struct
130 { struct worklist *worklist; /* tabling worklist */
131 trie_node *variant; /* node in variant trie */
132 struct idg_node *IDG; /* Node in the IDG graph */
133 } data;
134 } trie;
135
136 typedef struct size_abstract
137 { int from_depth; /* start below depth */
138 size_t size; /* limit each term to size */
139 } size_abstract;
140
141 #define acquire_trie(t) ATOMIC_INC(&(t)->references)
142 #define release_trie(t) do { if ( ATOMIC_DEC(&(t)->references) == 0 ) \
143 trie_clean(t); \
144 } while(0)
145
146 #define TRIE_ARGS 3
147 #define TRIE_VAR_OFFSET (TRIE_ARGS+3)
148
149 #ifdef O_TRIE_STATS
150 #define TRIE_STAT_INC(t, v) ATOMIC_INC(&t->stats.v)
151 #else
152 #define TRIE_STAT_INC(t, v) ((void)0)
153 #endif
154
155 /* trie_lookup_abstract() return values (< 0: error) */
156 #define TRIE_ABSTRACTED 2
157 #define TRIE_LOOKUP_CONTAINS_ATTVAR -10
158 #define TRIE_LOOKUP_CYCLIC -11
159
160 COMMON(void) initTries(void);
161 COMMON(trie *) trie_create(alloc_pool *pool);
162 COMMON(void) trie_destroy(trie *trie);
163 COMMON(void) trie_empty(trie *trie);
164 COMMON(void) trie_clean(trie *trie);
165 COMMON(void) trie_delete(trie *trie, trie_node *node, int prune);
166 COMMON(void) prune_node(trie *trie, trie_node *n);
167 COMMON(void) prune_trie(trie *trie, trie_node *root,
168 void (*free)(trie_node *node, void *ctx), void *ctx);
169 COMMON(trie *) get_trie_from_node(trie_node *node);
170 COMMON(int) is_ground_trie_node(trie_node *node);
171 COMMON(int) get_trie(term_t t, trie **tp);
172 COMMON(int) get_trie_noex(term_t t, trie **tp);
173 COMMON(int) unify_trie_term(trie_node *node, trie_node **parent,
174 term_t term ARG_LD);
175 COMMON(int) trie_lookup_abstract(trie *trie,
176 trie_node *root, trie_node **nodep, Word k,
177 int add, size_abstract *abstract,
178 TmpBuffer vars ARG_LD);
179 COMMON(int) trie_error(int rc, term_t culprit);
180 COMMON(int) trie_trie_error(int rc, trie *trie);
181 COMMON(atom_t) trie_symbol(trie *trie);
182 COMMON(trie *) symbol_trie(atom_t symbol);
183 COMMON(int) put_trie_value(term_t t, trie_node *node ARG_LD);
184 COMMON(int) set_trie_value(trie *trie, trie_node *node, term_t value ARG_LD);
185 COMMON(int) set_trie_value_word(trie *trie, trie_node *node, word val);
186 COMMON(foreign_t) trie_gen_raw(
187 trie *trie, trie_node *root,
188 term_t Key, term_t Value,
189 term_t Data,
190 int (*unify_data)(term_t, trie_node*, void* ARG_LD),
191 void *ctx, control_t PL__ctx);
192 COMMON(foreign_t) trie_gen(term_t Trie, term_t Root, term_t Key, term_t Value,
193 term_t Data,
194 int (*unify_data)(term_t, trie_node*, void* ARG_LD),
195 void *ctx, control_t PL__ctx);
196 COMMON(void *) map_trie_node(trie_node *n,
197 void* (*map)(trie_node *n, void *ctx), void *ctx);
198 COMMON(atom_t) compile_trie(Definition def, trie *trie ARG_LD);
199
200 static inline int
trie_lookup(trie * trie,trie_node * node,trie_node ** nodep,Word k,int add,TmpBuffer vars ARG_LD)201 trie_lookup(trie *trie, trie_node *node, trie_node **nodep,
202 Word k, int add, TmpBuffer vars ARG_LD)
203 { return trie_lookup_abstract(trie, node, nodep, k, add,
204 NULL, vars PASS_LD);
205 }
206
207 #endif /*_PL_TRIE_H*/
208