1 /************************************************************************ 2 ** ** 3 ** The YapTab/YapOr/OPTYap systems ** 4 ** ** 5 ** YapTab extends the Yap Prolog engine to support sequential tabling ** 6 ** YapOr extends the Yap Prolog engine to support or-parallelism ** 7 ** OPTYap extends the Yap Prolog engine to support or-parallel tabling ** 8 ** ** 9 ** ** 10 ** Yap Prolog was developed at University of Porto, Portugal ** 11 ** ** 12 ************************************************************************/ 13 14 /************************************************************************ 15 ** Table Space Data Structures ** 16 ************************************************************************/ 17 18 /************************** 19 ** table_entry ** 20 **************************/ 21 22 typedef struct table_entry { 23 #if defined(YAPOR) || defined(THREADS) 24 lockvar lock; 25 #endif /* YAPOR || THREADS */ 26 struct pred_entry *pred_entry; 27 Atom pred_atom; 28 int pred_arity; 29 short pred_flags; 30 short execution_mode; /* combines yap_flags with pred_flags */ 31 struct subgoal_trie_node *subgoal_trie; 32 struct subgoal_trie_hash *hash_chain; 33 struct table_entry *next; 34 } *tab_ent_ptr; 35 36 #define TabEnt_lock(X) ((X)->lock) 37 #define TabEnt_pe(X) ((X)->pred_entry) 38 #define TabEnt_atom(X) ((X)->pred_atom) 39 #define TabEnt_arity(X) ((X)->pred_arity) 40 #define TabEnt_flags(X) ((X)->pred_flags) 41 #define TabEnt_mode(X) ((X)->execution_mode) 42 #define TabEnt_subgoal_trie(X) ((X)->subgoal_trie) 43 #define TabEnt_hash_chain(X) ((X)->hash_chain) 44 #define TabEnt_next(X) ((X)->next) 45 46 47 48 /*********************************************************************** 49 ** global_trie_node, subgoal_trie_node and answer_trie_node ** 50 ***********************************************************************/ 51 52 typedef struct subgoal_trie_node { 53 Term entry; 54 struct subgoal_trie_node *parent; 55 struct subgoal_trie_node *child; 56 struct subgoal_trie_node *next; 57 #ifdef TABLE_LOCK_AT_NODE_LEVEL 58 lockvar lock; 59 #endif /* TABLE_LOCK_AT_NODE_LEVEL */ 60 } *sg_node_ptr; 61 62 typedef struct answer_trie_node { 63 OPCODE trie_instruction; /* u.opc */ 64 #ifdef YAPOR 65 int or_arg; /* u.Otapl.or_arg */ 66 #endif /* YAPOR */ 67 Term entry; 68 struct answer_trie_node *parent; 69 struct answer_trie_node *child; 70 struct answer_trie_node *next; 71 #ifdef TABLE_LOCK_AT_NODE_LEVEL 72 lockvar lock; 73 #endif /* TABLE_LOCK_AT_NODE_LEVEL */ 74 } *ans_node_ptr; 75 76 typedef struct global_trie_node { 77 Term entry; 78 struct global_trie_node *parent; 79 struct global_trie_node *child; 80 struct global_trie_node *next; 81 #ifdef TABLE_LOCK_AT_NODE_LEVEL 82 lockvar lock; 83 #endif /* TABLE_LOCK_AT_NODE_LEVEL */ 84 } *gt_node_ptr; 85 86 #define TrNode_instr(X) ((X)->trie_instruction) 87 #define TrNode_or_arg(X) ((X)->or_arg) 88 #define TrNode_entry(X) ((X)->entry) 89 #define TrNode_parent(X) ((X)->parent) 90 #define TrNode_child(X) ((X)->child) 91 #define TrNode_sg_fr(X) ((X)->child) 92 #define TrNode_next(X) ((X)->next) 93 #define TrNode_lock(X) ((X)->lock) 94 95 96 97 /*********************************************************************** 98 ** global_trie_hash, subgoal_trie_hash and answer_trie_hash ** 99 ***********************************************************************/ 100 101 typedef struct subgoal_trie_hash { 102 /* the first field is used for compatibility ** 103 ** with the subgoal_trie_node data structure */ 104 Term mark; 105 int number_of_buckets; 106 struct subgoal_trie_node **buckets; 107 int number_of_nodes; 108 struct subgoal_trie_hash *next; 109 } *sg_hash_ptr; 110 111 typedef struct answer_trie_hash { 112 /* the first field is used for compatibility ** 113 ** with the answer_trie_node data structure */ 114 OPCODE mark; 115 int number_of_buckets; 116 struct answer_trie_node **buckets; 117 int number_of_nodes; 118 struct answer_trie_hash *next; 119 } *ans_hash_ptr; 120 121 typedef struct global_trie_hash { 122 /* the first field is used for compatibility ** 123 ** with the global_trie_node data structure */ 124 Term mark; 125 int number_of_buckets; 126 struct global_trie_node **buckets; 127 int number_of_nodes; 128 } *gt_hash_ptr; 129 130 #define Hash_mark(X) ((X)->mark) 131 #define Hash_num_buckets(X) ((X)->number_of_buckets) 132 #define Hash_seed(X) ((X)->number_of_buckets - 1) 133 #define Hash_buckets(X) ((X)->buckets) 134 #define Hash_bucket(X,N) ((X)->buckets + N) 135 #define Hash_num_nodes(X) ((X)->number_of_nodes) 136 #define Hash_next(X) ((X)->next) 137 138 139 140 /************************************************************************ 141 ** Execution Data Structures ** 142 ************************************************************************/ 143 144 /**************************** 145 ** choice points ** 146 ****************************/ 147 148 struct generator_choicept { 149 struct choicept cp; 150 struct dependency_frame *cp_dep_fr; /* always NULL if batched scheduling */ 151 struct subgoal_frame *cp_sg_fr; 152 #ifdef LOW_LEVEL_TRACER 153 struct pred_entry *cp_pred_entry; 154 #endif /* LOW_LEVEL_TRACER */ 155 }; 156 157 #ifdef DETERMINISTIC_TABLING 158 struct deterministic_generator_choicept { 159 struct deterministic_choicept cp; 160 struct subgoal_frame *cp_sg_fr; 161 #ifdef LOW_LEVEL_TRACER 162 struct pred_entry *cp_pred_entry; 163 #endif /* LOW_LEVEL_TRACER */ 164 }; 165 #endif /* DETERMINISTIC_TABLING */ 166 167 struct consumer_choicept { 168 struct choicept cp; 169 struct dependency_frame *cp_dep_fr; 170 #ifdef LOW_LEVEL_TRACER 171 struct pred_entry *cp_pred_entry; 172 #endif /* LOW_LEVEL_TRACER */ 173 }; 174 175 struct loader_choicept { 176 struct choicept cp; 177 struct answer_trie_node *cp_last_answer; 178 #ifdef LOW_LEVEL_TRACER 179 struct pred_entry *cp_pred_entry; 180 #endif /* LOW_LEVEL_TRACER */ 181 }; 182 183 184 185 /**************************** 186 ** subgoal_frame ** 187 ****************************/ 188 189 typedef struct subgoal_frame { 190 #if defined(YAPOR) || defined(THREADS) 191 lockvar lock; 192 #endif /* YAPOR || THREADS */ 193 #ifdef YAPOR 194 int generator_worker; 195 struct or_frame *top_or_frame_on_generator_branch; 196 #endif /* YAPOR */ 197 yamop *code_of_subgoal; 198 enum { /* do not change order !!! */ 199 incomplete = 0, /* INCOMPLETE_TABLING */ 200 ready = 1, 201 evaluating = 2, 202 complete = 3, 203 complete_in_use = 4, /* LIMIT_TABLING */ 204 compiled = 5, 205 compiled_in_use = 6 /* LIMIT_TABLING */ 206 } state_flag; 207 choiceptr generator_choice_point; 208 struct answer_trie_hash *hash_chain; 209 struct answer_trie_node *answer_trie; 210 struct answer_trie_node *first_answer; 211 struct answer_trie_node *last_answer; 212 #ifdef INCOMPLETE_TABLING 213 struct answer_trie_node *try_answer; 214 #endif /* INCOMPLETE_TABLING */ 215 #ifdef LIMIT_TABLING 216 struct subgoal_frame *previous; 217 #endif /* LIMIT_TABLING */ 218 struct subgoal_frame *next; 219 } *sg_fr_ptr; 220 221 #define SgFr_lock(X) ((X)->lock) 222 #define SgFr_gen_worker(X) ((X)->generator_worker) 223 #define SgFr_gen_top_or_fr(X) ((X)->top_or_frame_on_generator_branch) 224 #define SgFr_code(X) ((X)->code_of_subgoal) 225 #define SgFr_tab_ent(X) (((X)->code_of_subgoal)->u.Otapl.te) 226 #define SgFr_arity(X) (((X)->code_of_subgoal)->u.Otapl.s) 227 #define SgFr_state(X) ((X)->state_flag) 228 #define SgFr_gen_cp(X) ((X)->generator_choice_point) 229 #define SgFr_hash_chain(X) ((X)->hash_chain) 230 #define SgFr_answer_trie(X) ((X)->answer_trie) 231 #define SgFr_first_answer(X) ((X)->first_answer) 232 #define SgFr_last_answer(X) ((X)->last_answer) 233 #define SgFr_try_answer(X) ((X)->try_answer) 234 #define SgFr_previous(X) ((X)->previous) 235 #define SgFr_next(X) ((X)->next) 236 237 /************************************************************************************************** 238 239 SgFr_lock: spin-lock to modify the frame fields. 240 SgFr_gen_worker: the id of the worker that had allocated the frame. 241 SgFr_gen_top_or_fr: a pointer to the top or-frame in the generator choice point branch. 242 When the generator choice point is shared the pointer is updated 243 to its or-frame. It is used to find the direct dependency node for 244 consumer nodes in other workers branches. 245 SgFr_code initial instruction of the subgoal's compiled code. 246 SgFr_tab_ent a pointer to the correspondent table entry. 247 SgFr_arity the arity of the subgoal. 248 SgFr_state: a flag that indicates the subgoal state. 249 SgFr_gen_cp: a pointer to the correspondent generator choice point. 250 SgFr_hash_chain: a pointer to the first answer_trie_hash struct for the subgoal in hand. 251 SgFr_answer_trie: a pointer to the top answer trie node. 252 It is used to check for/insert new answers. 253 SgFr_first_answer: a pointer to the bottom answer trie node of the first available answer. 254 SgFr_last_answer: a pointer to the bottom answer trie node of the last available answer. 255 SgFr_try_answer: a pointer to the bottom answer trie node of the last tried answer. 256 It is used when a subgoal was not completed during the previous evaluation. 257 Not completed subgoals start by trying the answers already found. 258 SgFr_previous: a pointer to the previous subgoal frame on the chain. 259 SgFr_next: a pointer to the next subgoal frame on the chain. 260 261 **************************************************************************************************/ 262 263 264 265 /******************************* 266 ** dependency_frame ** 267 *******************************/ 268 269 typedef struct dependency_frame { 270 #if defined(YAPOR) || defined(THREADS) 271 lockvar lock; 272 #endif /* YAPOR || THREADS */ 273 #ifdef YAPOR 274 int leader_dependency_is_on_stack; 275 struct or_frame *top_or_frame; 276 #ifdef TIMESTAMP_CHECK 277 long timestamp; 278 #endif /* TIMESTAMP_CHECK */ 279 #endif /* YAPOR */ 280 choiceptr backchain_choice_point; 281 choiceptr leader_choice_point; 282 choiceptr consumer_choice_point; 283 struct answer_trie_node *last_consumed_answer; 284 struct dependency_frame *next; 285 } *dep_fr_ptr; 286 287 #define DepFr_lock(X) ((X)->lock) 288 #define DepFr_leader_dep_is_on_stack(X) ((X)->leader_dependency_is_on_stack) 289 #define DepFr_top_or_fr(X) ((X)->top_or_frame) 290 #define DepFr_timestamp(X) ((X)->timestamp) 291 #define DepFr_backchain_cp(X) ((X)->backchain_choice_point) 292 #define DepFr_leader_cp(X) ((X)->leader_choice_point) 293 #define DepFr_cons_cp(X) ((X)->consumer_choice_point) 294 #define DepFr_last_answer(X) ((X)->last_consumed_answer) 295 #define DepFr_next(X) ((X)->next) 296 297 /******************************************************************************************************* 298 299 DepFr_lock: lock variable to modify the frame fields. 300 DepFr_leader_dep_is_on_stack: the generator choice point for the correspondent consumer choice point 301 is on the worker's stack (FALSE/TRUE). 302 DepFr_top_or_fr: a pointer to the top or-frame in the consumer choice point branch. 303 When the consumer choice point is shared the pointer is updated to 304 its or-frame. It is used to update the LOCAL_top_or_fr when a worker 305 backtracks through answers. 306 DepFr_timestamp: a timestamp used to optimize the search for suspension frames to be 307 resumed. 308 DepFr_backchain_cp: a pointer to the nearest choice point with untried alternatives. 309 It is used to efficiently return (backtrack) to the leader node where 310 we perform the last backtracking through answers operation. 311 DepFr_leader_cp: a pointer to the leader choice point. 312 DepFr_cons_cp: a pointer to the correspondent consumer choice point. 313 DepFr_last_answer: a pointer to the last consumed answer. 314 DepFr_next: a pointer to the next dependency frame on the chain. 315 316 *******************************************************************************************************/ 317 318 319 320 /******************************* 321 ** suspension_frame ** 322 *******************************/ 323 324 #ifdef YAPOR 325 typedef struct suspension_frame { 326 struct or_frame *top_or_frame_on_stack; 327 struct dependency_frame *top_dependency_frame; 328 struct subgoal_frame *top_subgoal_frame; 329 struct suspended_block { 330 void *resume_register; 331 void *block_start; 332 long block_size; 333 } global_block, local_block, trail_block; 334 struct suspension_frame *next; 335 } *susp_fr_ptr; 336 #endif /* YAPOR */ 337 338 #define SuspFr_top_or_fr_on_stack(X) ((X)->top_or_frame_on_stack) 339 #define SuspFr_top_dep_fr(X) ((X)->top_dependency_frame) 340 #define SuspFr_top_sg_fr(X) ((X)->top_subgoal_frame) 341 #define SuspFr_global_reg(X) ((X)->global_block.resume_register) 342 #define SuspFr_global_start(X) ((X)->global_block.block_start) 343 #define SuspFr_global_size(X) ((X)->global_block.block_size) 344 #define SuspFr_local_reg(X) ((X)->local_block.resume_register) 345 #define SuspFr_local_start(X) ((X)->local_block.block_start) 346 #define SuspFr_local_size(X) ((X)->local_block.block_size) 347 #define SuspFr_trail_reg(X) ((X)->trail_block.resume_register) 348 #define SuspFr_trail_start(X) ((X)->trail_block.block_start) 349 #define SuspFr_trail_size(X) ((X)->trail_block.block_size) 350 #define SuspFr_next(X) ((X)->next) 351