C: » dev » sandbox » xsb_release » XSB » emu

trie_lookup.c File Reference

#include "xsb_config.h"
#include "xsb_debug.h"
#include "debugs/debug_tries.h"
#include <stdio.h>
#include <stdlib.h>
#include "auxlry.h"
#include "cell_xsb.h"
#include "error_xsb.h"
#include "psc_xsb.h"
#include "deref.h"
#include "table_stats.h"
#include "trie_internals.h"
#include "tst_aux.h"
#include "subp.h"
#include "debug_xsb.h"
#include "flags_xsb.h"
#include "context.h"
#include "memory_xsb.h"

Defines

#define ContStack_ExpandOnOverflow(Stack, StackSize, NeededSize)
#define CPF_AlternateNode   ((tstCCPStack.top)->alt_node)
#define CPF_VariableChain   ((tstCCPStack.top)->var_chain)
#define CPF_TermStackTopIndex   ((tstCCPStack.top)->termstk_top_index)
#define CPF_TermStackLogTopIndex   ((tstCCPStack.top)->log_top_index)
#define CPF_TrailTopIndex   ((tstCCPStack.top)->trail_top_index)
#define CPStack_ResetTOS   tstCCPStack.top = tstCCPStack.base
#define CPStack_IsEmpty   (tstCCPStack.top == tstCCPStack.base)
#define CPStack_IsFull   (tstCCPStack.top == tstCCPStack.ceiling)
#define CPStack_OverflowCheck
#define CPStack_PushFrame(AltNode, VarChain)
#define CPStack_PopFrame(CurNode, VarChain)
#define Conditionally_Create_ChoicePoint(VariableChain)
#define Create_ChoicePoint(AlternateBTN, VariableChain)   CPStack_PushFrame(AlternateBTN,VariableChain)
#define BacktrackSearch
#define SubsumptiveTrieLookupError(String)   sub_trie_lookup_error(CTXTc String)
#define TrieVar_BindToSubterm(TrieVarNum, Subterm)
#define TrieVar_BindToMarkedPrologVar(TrieVarNum, PrologVarMarker)
#define PrologVar_MarkIt(DerefedVar, Index)
#define PrologVar_IsMarked(pDerefedPrologVar)   IsStandardizedVariable(pDerefedPrologVar)
#define PrologVar_Index(VarEnumAddr)   IndexOfStdVar(VarEnumAddr)
#define Set_Matching_and_TrieVar_Chains(Symbol, MatchChain, VarChain)
#define SetNoVariant(LastNodeMatched)
#define NonVarSearchChain_ExactMatch(Symbol, MatchChain, VariableChain, TermStack_PushOp)
#define NonVarSearchChain_BoundTrievar(Subterm, CurNODE, VarChain)
#define NonVarSearchChain_UnboundTrievar(Subterm, VarChain)
#define Descend_In_Trie_and_Continue(PairedBTN)

Typedefs

typedef enum Search_Strategy_Mode SearchMode

Enumerations

enum  Search_Strategy_Mode { MATCH_SYMBOL_EXACTLY, MATCH_WITH_TRIEVAR }

Functions

static xsbBool save_variant_continuation (CTXTdeclc BTNptr last_node_match)
void * stl_restore_variant_cont (CTXTdecl)
void initSubsumptiveLookup (CTXTdecl)
static void sub_trie_lookup_error (CTXTdeclc char *string)
void * iter_sub_trie_lookup (CTXTdeclc void *trieNode, TriePathType *pathType)
void * var_trie_lookup (CTXTdeclc void *branchRoot, xsbBool *wasFound, Cell *failedSymbol)
void * variant_trie_lookup (CTXTdeclc void *trieRoot, int nTerms, CPtr termVector, Cell varArray[])
static BTNptr rec_sub_trie_lookup (CTXTdeclc BTNptr parent, TriePathType *pathType)
void * subsumptive_trie_lookup (CTXTdeclc void *trieRoot, int nTerms, CPtr termVector, TriePathType *path_type, Cell subtermArray[])

Variables

static struct VariantContinuation variant_cont
static struct tstCCPStack_t tstCCPStack

Define Documentation

#define BacktrackSearch
 

Value:

{                       \
   CPStack_PopFrame(pCurrentBTN,variableChain); \
   search_mode = MATCH_WITH_TRIEVAR;            \
 }

#define Conditionally_Create_ChoicePoint (  VariableChain   ) 
 

Value:

{       \
   BTNptr alternateBTN = VariableChain;                         \
                                                                \
   while ( IsNonNULL(alternateBTN) ) {                          \
     if ( IsTrieVar(BTN_Symbol(alternateBTN)) ) {               \
       CPStack_PushFrame(alternateBTN, VariableChain)           \
       break;                                                   \
     }                                                          \
     alternateBTN = BTN_Sibling(alternateBTN);                  \
   }                                                            \
 }

#define ContStack_ExpandOnOverflow (  Stack,
StackSize,
NeededSize   ) 
 

Value:

{       \
                                                                        \
   size_t new_size;     /* in number of stack elements */               \
   void *p;                                                             \
                                                                        \
   if ( StackSize < NeededSize ) {                                      \
     new_size = 2 * StackSize;                                          \
     if ( new_size < NeededSize )                                       \
       new_size = new_size + NeededSize;                                \
     p = realloc(Stack,(new_size * sizeof(Stack[0])));                  \
     if ( IsNULL(p) )                                                   \
       return FALSE;                                                    \
     Stack = p;                                                         \
     StackSize = new_size;                                              \
   }                                                                    \
 }

#define CPF_AlternateNode   ((tstCCPStack.top)->alt_node)
 

#define CPF_TermStackLogTopIndex   ((tstCCPStack.top)->log_top_index)
 

#define CPF_TermStackTopIndex   ((tstCCPStack.top)->termstk_top_index)
 

#define CPF_TrailTopIndex   ((tstCCPStack.top)->trail_top_index)
 

#define CPF_VariableChain   ((tstCCPStack.top)->var_chain)
 

#define CPStack_IsEmpty   (tstCCPStack.top == tstCCPStack.base)
 

#define CPStack_IsFull   (tstCCPStack.top == tstCCPStack.ceiling)
 

#define CPStack_OverflowCheck
 

Value:

if (CPStack_IsFull)                                     \
     SubsumptiveTrieLookupError("tstCCPStack overflow!")

#define CPStack_PopFrame (  CurNode,
VarChain   ) 
 

Value:

{               \
   tstCCPStack.top--;                                   \
   CurNode = CPF_AlternateNode;                         \
   VarChain = CPF_VariableChain;                        \
   TermStackLog_Unwind(CPF_TermStackLogTopIndex);       \
   TermStack_SetTOS(CPF_TermStackTopIndex);             \
   Trail_Unwind(CPF_TrailTopIndex);                     \
 }

#define CPStack_PushFrame (  AltNode,
VarChain   ) 
 

Value:

{       \
   CPStack_OverflowCheck;                       \
   CPF_AlternateNode = AltNode;                 \
   CPF_VariableChain = VarChain;                \
   CPF_TermStackTopIndex =                      \
     TermStack_Top - TermStack_Base + 1;        \
   CPF_TermStackLogTopIndex =                   \
     TermStackLog_Top - TermStackLog_Base - 1;  \
   CPF_TrailTopIndex = Trail_Top - Trail_Base;  \
   tstCCPStack.top++;                           \
 }

#define CPStack_ResetTOS   tstCCPStack.top = tstCCPStack.base
 

#define Create_ChoicePoint (  AlternateBTN,
VariableChain   )     CPStack_PushFrame(AlternateBTN,VariableChain)
 

#define Descend_In_Trie_and_Continue (  PairedBTN   ) 
 

Value:

pParentBTN = PairedBTN;                           \
   pCurrentBTN = BTN_Child(PairedBTN);               \
   search_mode = MATCH_SYMBOL_EXACTLY;               \
   goto While_TermStack_NotEmpty

#define NonVarSearchChain_BoundTrievar (  Subterm,
CurNODE,
VarChain   ) 
 

Value:

{       \
                                                                        \
   int trievar_index;                                                   \
                                                                        \
   while ( IsNonNULL(CurNODE) ) {                                       \
     if ( IsTrieVar(BTN_Symbol(CurNODE)) &&                             \
          ! IsNewTrieVar(BTN_Symbol(CurNODE)) ) {                       \
       trievar_index = DecodeTrieVar(BTN_Symbol(CurNODE));              \
       if ( are_identical_terms(TrieVarBindings[trievar_index],         \
                                Subterm) ) {                            \
         Create_ChoicePoint(BTN_Sibling(CurNODE),VarChain)              \
         Descend_In_Trie_and_Continue(CurNODE);                         \
       }                                                                \
     }                                                                  \
     CurNODE = BTN_Sibling(CurNODE);                                    \
   }                                                                    \
 }

#define NonVarSearchChain_ExactMatch (  Symbol,
MatchChain,
VariableChain,
TermStack_PushOp   ) 
 

Value:

\
   while ( IsNonNULL(MatchChain) ) {                                    \
     if (Symbol == BTN_Symbol(MatchChain)) {                            \
       Conditionally_Create_ChoicePoint(VariableChain)                  \
       TermStack_PushOp                                                 \
       Descend_In_Trie_and_Continue(MatchChain);                        \
     }                                                                  \
     MatchChain = BTN_Sibling(MatchChain);                              \
   }

#define NonVarSearchChain_UnboundTrievar (  Subterm,
VarChain   ) 
 

Value:

{       \
                                                                \
   int trievar_index;                                           \
                                                                \
   while ( IsNonNULL(VarChain) ) {                              \
     if ( IsTrieVar(BTN_Symbol(VarChain)) &&                    \
          IsNewTrieVar(BTN_Symbol(VarChain)) ) {                \
       trievar_index = DecodeTrieVar(BTN_Symbol(VarChain));     \
       TrieVar_BindToSubterm(trievar_index,Subterm);            \
       Descend_In_Trie_and_Continue(VarChain);                  \
     }                                                          \
     VarChain = BTN_Sibling(VarChain);                          \
   }                                                            \
 }

#define PrologVar_Index (  VarEnumAddr   )     IndexOfStdVar(VarEnumAddr)
 

#define PrologVar_IsMarked (  pDerefedPrologVar   )     IsStandardizedVariable(pDerefedPrologVar)
 

#define PrologVar_MarkIt (  DerefedVar,
Index   ) 
 

Value:

StandardizeVariable(DerefedVar,Index);  \
   Trail_Push((CPtr)DerefedVar)

#define Set_Matching_and_TrieVar_Chains (  Symbol,
MatchChain,
VarChain   ) 
 

Value:

if ( IsNonNULL(pCurrentBTN) && IsHashHeader(pCurrentBTN) ) {            \
     BTNptr *buckets;                                                   \
     BTHTptr pBTHT;                                                     \
                                                                        \
     pBTHT = (BTHTptr)pCurrentBTN;                                      \
     buckets = BTHT_BucketArray(pBTHT);                                 \
     MatchChain = buckets[TrieHash(Symbol,BTHT_GetHashSeed(pBTHT))];    \
     VarChain = buckets[TRIEVAR_BUCKET];                                \
   }                                                                    \
   else    /* simple chain of nodes */                                  \
     VarChain = MatchChain = pCurrentBTN

#define SetNoVariant (  LastNodeMatched   ) 
 

Value:

if (variant_path == YES) {                                      \
     if ( ! save_variant_continuation(CTXTc LastNodeMatched) )  \
       SubsumptiveTrieLookupError("Memory exhausted.");         \
     variant_path = NO;                                         \
   }

#define SubsumptiveTrieLookupError (  String   )     sub_trie_lookup_error(CTXTc String)
 

#define TrieVar_BindToMarkedPrologVar (  TrieVarNum,
PrologVarMarker   ) 
 

Value:

TrieVarBindings[TrieVarNum] =                                   \
     TrieVarBindings[PrologVar_Index(PrologVarMarker)];                 \
   Trail_Push(&TrieVarBindings[TrieVarNum])

#define TrieVar_BindToSubterm (  TrieVarNum,
Subterm   ) 
 

Value:

TrieVarBindings[TrieVarNum] = Subterm;          \
   Trail_Push(&TrieVarBindings[TrieVarNum])

Typedef Documentation

typedef enum Search_Strategy_Mode SearchMode
 

Enumeration Type Documentation

enum Search_Strategy_Mode
 

Enumerator:
MATCH_SYMBOL_EXACTLY 
MATCH_WITH_TRIEVAR 

Function Documentation

void initSubsumptiveLookup (  CTXTdecl   ) 
 

void* iter_sub_trie_lookup (  CTXTdeclc void *  trieNode,
TriePathType *  pathType
) 
 

static BTNptr rec_sub_trie_lookup (  CTXTdeclc BTNptr  parent,
TriePathType *  pathType
)  [static]
 

static xsbBool save_variant_continuation (  CTXTdeclc BTNptr  last_node_match  )  [static]
 

void* stl_restore_variant_cont (  CTXTdecl   ) 
 

static void sub_trie_lookup_error (  CTXTdeclc char *  string  )  [static]
 

void* subsumptive_trie_lookup (  CTXTdeclc void *  trieRoot,
int  nTerms,
CPtr  termVector,
TriePathType *  path_type,
Cell  subtermArray[]
) 
 

void* var_trie_lookup (  CTXTdeclc void *  branchRoot,
xsbBool *  wasFound,
Cell *  failedSymbol
) 
 

void* variant_trie_lookup (  CTXTdeclc void *  trieRoot,
int  nTerms,
CPtr  termVector,
Cell  varArray[]
) 
 

Variable Documentation

struct tstCCPStack_t tstCCPStack [static]
 

struct VariantContinuation variant_cont [static]
 

Generated on Wed Jul 26 13:26:54 2006 for XSB by  doxygen 1.4.5