30#include "tab.macros.h"
43bool YAP_AssertTuples(
PredEntry *pe,
const Term *ts,
size_t offset,
size_t m);
52#define FNV32_PRIME (16777619UL)
53#define FNV32_OFFSET (0x811c9dc5UL)
54#define FNV_PRIME FNV32_PRIME
55#define FNV_OFFSET FNV32_OFFSET
57#define FNV64_PRIME (1099511628211)
59#define FNV64_OFFSET (14695981039346656037ULL)
61#define FNV64_OFFSET (14695981039346656037UL)
63#define FNV_PRIME FNV64_PRIME
64#define FNV_OFFSET FNV64_OFFSET
68BITS32 rotl32 ( BITS32, int8_t);
70inline BITS32 rotl32 ( BITS32 x, int8_t r )
72 return (x << r) | (x >> (32 - r));
74#define ROTL32(x,y) rotl32(x,y)
78BITS32 fmix32 ( BITS32 );
79inline BITS32 fmix32 ( BITS32 h )
91HASH_MURMUR3_32 (UInt arity, CELL *cl, UInt bnds[], UInt sz);
94HASH_MURMUR3_32 (UInt arity, CELL *cl, UInt bnds[], UInt sz)
99 const BITS32 c1 = 0xcc9e2d51;
100 const BITS32 c2 = 0x1b873593;
106 unsigned char *i=(
unsigned char*)(cl+j);
107 unsigned char *
m=(
unsigned char*)(cl+(j+1));
117 hash = ROTL32(hash,13);
118 hash = hash*5+0xe6546b64;
140#define DJB2_OFFSET 5381
143HASH_DJB2(UInt arity, CELL *cl, UInt bnds[], UInt sz);
146HASH_DJB2(UInt arity, CELL *cl, UInt bnds[], UInt sz)
154 unsigned char *i=(
unsigned char*)(cl+j);
155 unsigned char *
m=(
unsigned char*)(cl+(j+1));
158 BITS32 h5 = hash << 5;
169HASH_RS(UInt arity, CELL *cl, UInt bnds[], UInt sz);
173HASH_RS(UInt arity, CELL *cl, UInt bnds[], UInt sz)
183 unsigned char *i=(
unsigned char*)(cl+j);
184 unsigned char *
m=(
unsigned char*)(cl+(j+1));
187 hash = hash * a + i[0];
198HASH_FVN_1A(UInt arity, CELL *cl, UInt bnds[], UInt sz);
207HASH_FVN_1A(UInt arity, CELL *cl, UInt bnds[], UInt sz)
215 unsigned char *i=(
unsigned char*)(cl+j);
216 unsigned char *
m=(
unsigned char*)(cl+(j+1));
220 hash = hash * FNV_PRIME;
231#if defined TEST_HASH_MURMUR
232# define HASH(...) HASH_MURMUR3_32(__VA_ARGS__)
233#elif defined TEST_HASH_DJB
234# define HASH(...) HASH_DJB2(__VA_ARGS__)
235#elif defined TEST_HASH_RS
236# define HASH(...) HASH_RS(__VA_ARGS__)
239# define HASH(...) HASH_FVN_1A(__VA_ARGS__)
240# define HASH1(...) HASH_MURMUR3_32(__VA_ARGS__)
244NEXT(UInt arity, CELL *cl, UInt bnds[], UInt sz, BITS32 hash)
249 while (bnds[i]==0) i++;
250 hash1 = HASH1(arity, cl, bnds, sz);
251 return (hash + hash1 +cl[i]);
256MATCH(CELL *clp, CELL *kvp, UInt arity, UInt bnds[])
260 if ( bnds[j] && clp[j] != kvp[j])
268ADD_TO_TRY_CHAIN(CELL *kvp, CELL *cl,
struct index_t *it)
270 BITS32 old = EXO_ADDRESS_TO_OFFSET(it, kvp);
271 BITS32
new = EXO_ADDRESS_TO_OFFSET(it, cl);
272 BITS32 *links = it->links;
273 BITS32 tmp = links[old];
276 links[old] = links[
new] =
new;
278 links[
new] = links[tmp];
302INSERT(CELL *cl,
struct index_t *it, UInt arity, UInt base, UInt bnds[])
309 hash = HASH(arity, cl, bnds, it->hsize);
311 kvp = EXO_OFFSET_TO_ADDRESS(it, it->key [hash % it->hsize]);
315 it->key[hash % it->hsize ] = EXO_ADDRESS_TO_OFFSET(it, cl);
316 if (coll_count > it -> max_col_count)
317 it->max_col_count = coll_count;
319 }
else if (MATCH(kvp, cl, arity, bnds)) {
321 ADD_TO_TRY_CHAIN(kvp, cl, it);
327 hash = NEXT(arity, cl, bnds, it->hsize, hash);
334LOOKUP(
struct index_t *it, UInt arity, UInt j, UInt bnds[])
342 hash = HASH(arity, XREGS+1, bnds, it->hsize);
345 kvp = EXO_OFFSET_TO_ADDRESS(it, it->key[hash % it->hsize]);
349 }
else if (MATCH(kvp, XREGS+1, arity, bnds)) {
351 if (!it->is_key && it->links[EXO_ADDRESS_TO_OFFSET(it, S)])
354 return NEXTOP(NEXTOP(it->code,lp),lp);
357 hash = NEXT(arity, XREGS+1, bnds, it->hsize, hash);
363fill_hash(UInt bmap,
struct index_t *it, UInt bnds[])
366 UInt arity = it->arity;
369 for (i=0; i < it->nels; i++) {
370 if (!INSERT(cl, it, arity, 0, bnds))
374 for (i=0; i < it->hsize; i++) {
376 BITS32 offset = it->key[i];
377 BITS32 last = it->links[offset];
380 it->links[offset] = it->links[last];
392 UInt ncls = ap->cs.p_code.NOfClauses, j;
397 UInt *bnds = LOCAL_ibnds;
399 sz = (CELL)NEXTOP(NEXTOP((
yamop*)NULL,lp),lp)+ap->ArityOfPE*(CELL)NEXTOP((
yamop *)NULL,x) +(CELL)NEXTOP(NEXTOP((
yamop *)NULL,p),l);
400 if (!(i = (
struct index_t *)Yap_AllocCodeSpace(
sizeof(
struct index_t)+sz))) {
403 LOCAL_Error_Size = 3*ncls*
sizeof(CELL);
404 LOCAL_ErrorMessage =
"not enough space to index";
405 Yap_Error(RESOURCE_ERROR_HEAP, TermNil, LOCAL_ErrorMessage);
412 i->arity = ap->ArityOfPE;
417 dsz =
sizeof(BITS32)*(ncls+1+i->hsize);
419 if (!(base = (CELL *)Yap_AllocCodeSpace(dsz))) {
422 LOCAL_Error_Size = dsz;
423 LOCAL_ErrorMessage =
"not enough space to generate indices";
424 Yap_FreeCodeSpace((
void *)i);
425 Yap_Error(RESOURCE_ERROR_HEAP, TermNil, LOCAL_ErrorMessage);
428 memset(base, 0, dsz);
430 i->size = sz+dsz+
sizeof(
struct index_t);
431 i->key = (BITS32 *)base;
432 i->links = (BITS32 *)base+i->hsize;
433 i->ncollisions = i->nentries = i->ntrys = 0;
434 i->cls = (CELL *)((ADDR)ap->cs.p_code.FirstClause+2*
sizeof(
struct index_t *));
435 i->bcls= i->cls-i->arity;
436 i->udi_free_args = 0;
441 if (!fill_hash(bmap, i, bnds)) {
445 sz = i->hsize*
sizeof(BITS32);
447 sz = (ncls+1+i->hsize)*
sizeof(BITS32);
449 if (base != (CELL *)Yap_ReallocCodeSpace((
char *)base, sz))
452 i->key = (BITS32 *)base;
453 i->links = (BITS32 *)(base+i->hsize);
454 i->ncollisions = i->nentries = i->ntrys = 0;
458 fprintf(stderr,
"entries=" UInt_FORMAT
" collisions=" UInt_FORMAT
" (max=" UInt_FORMAT
") trys=" UInt_FORMAT
"\n", i->nentries, i->ncollisions, i->max_col_count, i->ntrys);
460 if (!i->ntrys && !i->is_key) {
462 if (base != (CELL *)Yap_ReallocCodeSpace((
char *)base, i->hsize*
sizeof(BITS32)))
466 if (( i->nentries+i->ncollisions )*10 < i->hsize) {
468 i->hsize = ( i->nentries+i->ncollisions )*10;
470 sz = i->hsize*
sizeof(BITS32);
472 sz = (ncls+1+i->hsize)*
sizeof(BITS32);
474 if (base != (CELL *)Yap_ReallocCodeSpace((
char *)base, sz))
477 i->key = (BITS32 *)base;
478 i->links = (BITS32 *)base+i->hsize;
479 i->ncollisions = i->nentries = i->ntrys = 0;
484 ptr = (
yamop *)(i+1);
487 ptr->opc = Yap_opcode(_try_exo);
489 ptr->opc = Yap_opcode(_try_all_exo);
490 ptr->y_u.lp.l = (
yamop *)i;
492 ptr = NEXTOP(ptr, lp);
494 ptr->opc = Yap_opcode(_retry_exo);
496 ptr->opc = Yap_opcode(_retry_all_exo);
498 ptr->y_u.lp.l = (
yamop *)i;
499 ptr = NEXTOP(ptr, lp);
500 for (j = 0; j < i->arity; j++) {
501 ptr->opc = Yap_opcode(_get_atom_exo);
502#if PRECOMPUTE_REGADDRESS
503 ptr->y_u.x.x = (CELL) (XREGS + (j+1));
507 ptr = NEXTOP(ptr, x);
509 ptr->opc = Yap_opcode(_procceed);
511 ptr = NEXTOP(ptr, p);
512 ptr->opc = Yap_opcode(_Ystop);
513 ptr->y_u.l.l = i->code;
514 Yap_inform_profiler_of_clause((
char *)(i->code), (
char *)NEXTOP(ptr,l), ap, GPROF_INDEX);
515 if (ap->PredFlags & UDIPredFlag) {
516 Yap_new_udi_clause( ap, NULL, (Term)ip);
526 UInt arity = ap->ArityOfPE;
527 UInt bmap = 0L, bit = 1, count = 0, j, j0 = 0;
528 struct index_t **ip = (
struct index_t **)(ap->cs.p_code.FirstClause);
531 for (j=0; j< arity; j++, bit<<=1) {
532 Term t = Deref(XREGS[j+1]);
535 LOCAL_ibnds[j] = TRUE;
539 LOCAL_ibnds[j] = FALSE;
548 if (i->bmap == bmap) {
555 i = add_index(ip, bmap, ap, count);
558 yamop *code = LOOKUP(i, arity, j0, LOCAL_ibnds);
559 if (code == FAILCODE)
562 return ((CEnterExoIndex)i->udi_first)(i PASS_REGS);
565 }
else if(i->is_udi) {
566 return ((CEnterExoIndex)i->udi_first)(i PASS_REGS);
576 BITS32 offset = ADDRESS_TO_LINK(it,(BITS32 *)((CELL *)(B+1))[it->arity]);
577 BITS32 next = it->links[offset];
578 ((CELL *)(B+1))[it->arity] = (CELL)LINK_TO_ADDRESS(it, next);
579 S = it->cls+it->arity*offset;
584exodb_get_space( Term t, Term mod, Term tn )
595 if (IsVarTerm(mod) || !IsAtomTerm(mod)) {
599 Atom a = AtomOfTerm(t);
601 pe = PredPropByAtom(a, mod);
602 }
else if (IsApplTerm(t)) {
603 register Functor f = FunctorOfTerm(t);
604 arity = ArityOfFunctor(f);
605 pe = PredPropByFunc(f, mod);
611 ap = RepPredProp(pe);
612 if (ap->PredFlags & (DynamicPredFlag|LogUpdatePredFlag
617 Yap_Error(PERMISSION_ERROR_MODIFY_STATIC_PROCEDURE,t,
"dbload_get_space/4");
620 if (IsVarTerm(tn) || !IsIntegerTerm(tn)) {
623 ncls = IntegerOfTerm(tn);
628 required = ncls*arity*
sizeof(CELL)+
sizeof(
MegaClause)+2*
sizeof(
struct index_t *);
629 while (!(mcl = (
MegaClause *)Yap_AllocCodeSpace(required))) {
630 if (!Yap_growheap(FALSE, required, NULL)) {
635 Yap_ClauseSpace += required;
637 mcl->ClFlags = MegaMask|ExoMask;
638 mcl->ClSize = required;
640 mcl->ClItemSize = arity*
sizeof(CELL);
642 li = (
struct index_t **)(mcl->ClCode);
643 li[0] = li[1] = NULL;
644 ap->cs.p_code.FirstClause =
645 ap->cs.p_code.LastClause =
647 ap->PredFlags |= MegaClausePredFlag;
648 ap->cs.p_code.NOfClauses = ncls;
649 if (ap->PredFlags & (SpiedPredFlag|CountPredFlag|ProfiledPredFlag)) {
650 ap->OpcodeOfPred = Yap_opcode(_spy_pred);
652 ap->OpcodeOfPred = Yap_opcode(_enter_exo);
654 ap->CodeOfPred = ap->cs.p_code.TrueCodeOfPred = (
yamop *)(&(ap->OpcodeOfPred));
665 if (data <= ap->ArityOfPE*
sizeof(CELL)) {
670 while (!(mcl = (
MegaClause *)Yap_AllocCodeSpace(required))) {
671 if (!Yap_growheap(FALSE, required, NULL)) {
676 Yap_ClauseSpace += required;
678 mcl->ClFlags = MegaMask|ExoMask;
679 mcl->ClSize = required;
681 mcl->ClItemSize = ap->ArityOfPE*
sizeof(CELL);
683 li = (
struct index_t **)(mcl->ClCode);
684 li[0] = li[1] = NULL;
685 ap->cs.p_code.FirstClause =
686 ap->cs.p_code.LastClause =
688 ap->PredFlags |= MegaClausePredFlag;
689 ap->cs.p_code.NOfClauses = 0;
690 if (ap->PredFlags & (SpiedPredFlag|CountPredFlag|ProfiledPredFlag)) {
691 ap->OpcodeOfPred = Yap_opcode(_spy_pred);
693 ap->OpcodeOfPred = Yap_opcode(_enter_exo);
695 ap->CodeOfPred = ap->cs.p_code.TrueCodeOfPred = (
yamop *)(&(ap->OpcodeOfPred));
700p_exodb_get_space( USES_REGS1 )
704 if ((mcl = exodb_get_space(Deref(ARG1), Deref(ARG2), Deref(ARG3))) == NULL)
707 return Yap_unify(ARG4, MkIntegerTerm((Int)mcl));
710#define DerefAndCheck(t, V) \
711 t = Deref(V); if(IsVarTerm(t) || !(IsAtomOrIntTerm(t))) Yap_Error(TYPE_ERROR_ATOMIC, t0, "load_db");
714store_exo(
yamop *pc, UInt arity, Term t0)
717 CELL *tp = RepAppl(t0)+1,
720 for (i = 0; i< arity; i++) {
721 DerefAndCheck(t, tp[0]);
732YAP_AssertTuples(
PredEntry *pe,
const Term *ts,
size_t offset,
size_t m)
734 MegaClause *mcl = ClauseCodeToMegaClause(pe->cs.p_code.FirstClause);
736 ADDR base = (ADDR)mcl->ClCode+2*
sizeof(
struct index_t *);
737 for (i=0; i<
m; i++) {
738 yamop *ptr = (
yamop *)(base+offset*(mcl->ClItemSize));
739 store_exo( ptr, pe->ArityOfPE, ts[i]);
745exoassert(
void *handle, Int n, Term term )
753 store_exo((
yamop *)((ADDR)mcl->ClCode+2*
sizeof(
struct index_t *)+n*(mcl->ClItemSize)),pe->ArityOfPE, term);
757p_exoassert( USES_REGS1 )
759 Term thandle = Deref(ARG2);
760 Term tn = Deref(ARG3);
765 if (IsVarTerm(thandle) || !IsIntegerTerm(thandle)) {
769 if (IsVarTerm(tn) || !IsIntegerTerm(tn)) {
772 n = IntegerOfTerm(tn);
773 exoassert(mcl,n,Deref(ARG1));
778Yap_InitExoPreds(
void)
781 Term cm = CurrentModule;
783 CurrentModule = DBLOAD_MODULE;
784 Yap_InitCPred(
"exo_db_get_space", 4, p_exodb_get_space, 0L);
785 Yap_InitCPred(
"exoassert", 3, p_exoassert, 0L);