/* File:      tries.h
** Author(s): Ernie Johnson, Prasad Rao, Kostis Sagonas
** Contact:   xsb-contact@cs.sunysb.edu
** 
** Copyright (C) The Research Foundation of SUNY, 1986, 1993-1998
** 
** XSB is free software; you can redistribute it and/or modify it under the
** terms of the GNU Library General Public License as published by the Free
** Software Foundation; either version 2 of the License, or (at your option)
** any later version.
** 
** XSB is distributed in the hope that it will be useful, but WITHOUT ANY
** WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
** FOR A PARTICULAR PURPOSE.  See the GNU Library General Public License for
** more details.
** 
** You should have received a copy of the GNU Library General Public License
** along with XSB; if not, write to the Free Software Foundation,
** Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**
** $Id: tries.h,v 1.29 2000/12/04 17:10:45 ejohnson Exp $
** 
*/


#ifndef PUBLIC_TRIE_DEFS


#define PUBLIC_TRIE_DEFS


/*===========================================================================*/

/*
 *	A B S T R A C T E D   T R I E   R E P R E S E N T A T I O N
 *	===========================================================
 *
 *  There are several types of operations which are common to any trie,
 *  either to the structure as a whole, or to its components.  Likewise,
 *  there are places in the engine where it won't be apparent what type
 *  of trie (respectively, component) one is inspecting.  Although this
 *  can be ascertained, adherence to the following guidelines will make
 *  this unnecessary, as well as the need for any type-dependent special
 *  processing.  A set of macros are supplied for use in these "don't
 *  know" or "don't care" situations.
 *
 *  All types of trie nodes must be laid out in the same fashion, with
 *  common fields appearing in the same order.  Fields which point to
 *  like-component records may have different types, but the others
 *  (Info and Symbol) are fixed.  Currently, the layout is as indicated
 *  below.  Except for the Info field which MUST be first, the ordering
 *  of the other fields is arbitrary.  Field names have also been
 *  standardized to help ensure conformity.
 *
 *  We use the following notation:
 *    TN_*         Trie Node operation
 *    TrieHT_*     Trie Hash Table operation  (see trie_internals.h)
 *    TSC_*        Trie SubComponent operation (applicable to a TN or THT)
 *    pTN          pointer to a Trie Node
 *    pTHT         pointer to a Trie Hash Table
 *    pTSC pointer to a Trie SubComponent
 */

#define TN_Instr(pTN)		TSC_Instr(pTN)
#define TN_Status(pTN)		TSC_Status(pTN)
#define TN_TrieType(pTN)	TSC_TrieType(pTN)
#define TN_NodeType(pTN)	TSC_NodeType(pTN)
#define TN_Parent(pTN)		( (pTN)->parent )
#define TN_Child(pTN)		( (pTN)->child )
#define TN_Sibling(pTN)		( (pTN)->sibling )
#define TN_Symbol(pTN)		( (pTN)->symbol )

#define TSC_Instr(pTSC)		IPT_Instr((pTSC)->info)
#define TSC_Status(pTSC)	IPT_Status((pTSC)->info)
#define TSC_TrieType(pTSC)	IPT_TrieType((pTSC)->info)
#define TSC_NodeType(pTSC)	IPT_NodeType((pTSC)->info)


#define TN_SetHashHdr(pTN,pTHT)		TN_Child(pTN) = (void *)(pTHT)
#define TN_GetHashHdr(pTN)		TN_Child(pTN)

/*===========================================================================*/

/*
 *                      Trie Component Info Field
 *                      =========================
 *
 *  Defines a field one word in size which contains miscellaneous info
 *  needed for maximizing trie use: An instruction field allows tries to
 *  be traversed for term unification with speeds comparable to code
 *  execution for facts.  A status field signifies whether a particular
 *  node represents a valid subbranch of the trie.  Nodes (paths) may
 *  temporarily be marked as deleted until such time they can be safely
 *  removed from the trie.  Two type fields contain annotations which
 *  describe the type of trie in which a structure resides and the role
 *  the structure plays within this trie, respectively.
 *
 *  Each of the two main components of a trie contain this field: trie
 *  nodes and hash table headers.
 *
 *  For valid trie-embedded instruction values, see file "inst_xsb.h".  */

typedef struct InstructionPlusTypeFrame {
  byte instr;		/* contains compiled trie code */
  byte status;		/* whether the node has been deleted */
  byte trie_type;	/* global info: what type of trie is this? */
  byte node_type;	/* local info: what is the role of this struct? */
#ifdef BITS64
  byte padding[4];
#endif
} InstrPlusType;

#define IPT_Instr(IPT)		((IPT).instr)
#define IPT_Status(IPT)		((IPT).status)
#define IPT_TrieType(IPT)	((IPT).trie_type)
#define IPT_NodeType(IPT)	((IPT).node_type)

/*===========================================================================*/

/*
 *                         B A S I C   T R I E S
 *                         =====================
 *
 *  Each symbol in a term is maintained in a separate node in a trie.
 *  Paths from the root to the leaves trace out the terms stored in the
 *  trie.  Sharing between terms takes place only high-up within a trie,
 *  corresponding to left-to-right term factoring.
 *
 *  Children of a particular node are maintained in a linked-list pointed
 *  to by the Child field.  This list is maintained through the Sibling
 *  fields of the child nodes.  To facilitate rapid access when the
 *  number of children becomes large, a hash table is employed.  In this
 *  case, the parent node's Child field points to a header structure for
 *  the hash table, rather than directly to one of the children.
 *
 *  When used to build Call Tries, the Child field of a leaf trie node
 *  points to a SubgoalFrame which contains additional info for that call.
 */

typedef struct Basic_Trie_Node *BTNptr;
typedef struct Basic_Trie_Node {
  InstrPlusType info;
  BTNptr sibling;
  BTNptr child;
  BTNptr parent;
  Cell symbol;
} BasicTrieNode;

/* - - Preferred macros - - - - */
#define BTN_Instr(pBTN)		TN_Instr(pBTN)
#define BTN_Status(pBTN)	TN_Status(pBTN)
#define BTN_TrieType(pBTN)	TN_TrieType(pBTN)
#define BTN_NodeType(pBTN)	TN_NodeType(pBTN)
#define BTN_Parent(pBTN)	TN_Parent(pBTN)
#define BTN_Child(pBTN)		TN_Child(pBTN)
#define BTN_Sibling(pBTN)	TN_Sibling(pBTN)
#define BTN_Symbol(pBTN)	TN_Symbol(pBTN)

/* - - For backwards compatibility - - - - */
typedef struct Basic_Trie_Node *NODEptr;
#define Instr(X)	BTN_Instr(X)
#define TrieType(X)     BTN_TrieType(X)
#define NodeType(X)     BTN_NodeType(X)
#define Parent(X)	BTN_Parent(X)
#define Child(X)	BTN_Child(X)
#define Sibl(X)		BTN_Sibling(X)
#define Atom(X)		BTN_Symbol(X)

/*===========================================================================*/

/*
 *                  T I M E - S T A M P E D   T R I E S
 *                  ===================================
 *
 *  Similar in construction and maintenance to normal tries, these extend
 *  the basic design in order to support answer subsumption.  Conditions
 *  under which hash tables are created and the way symbols are stored in
 *  the nodes are identical.  (See the file trie_internals.h for details.)
 *
 *  A timestamp is maintained in each node of the Time-Stamped Trie (TST).
 *  When used for Answer Sets, the timestamp kept in each node is the
 *  maximum of the timestamps of its children.  Since timestamps
 *  monotonically increase as terms are entered, this property can be
 *  easily maintained by propagating the timestamp of a newly interned
 *  term from the leaf to the root.  Hence, the root ALWAYS contains the
 *  timestamp of the largest-timestamped answer contained in the Answer
 *  Set.
 *
 *  For facilitating certain subsumptive operations, it is important to
 *  quickly identify nodes having a timestamp greater than a given one.
 *  When a sibling chain becomes long, it is no longer acceptable to
 *  perform a linear scan in order to identify these timestamp-valid
 *  nodes.  Therefore, when we create a hash table for a group of nodes,
 *  we also create an auxiliary structure which maintains the nodes in
 *  decreasing timestamp order.  Each node's TimeStamp field is then used
 *  for pointing to an associated frame in this structure, where the
 *  timestamp is now kept.  The hash header is extended -- over the basic
 *  trie hash header -- to contain fields for maintaining these frames in
 *  a doubly linked list.  Once the Answer Set is completed, these
 *  structures can be disposed.  To facilitate this, hash tables, within
 *  a particular TST, are chained together from the root, accessible from
 *  its Sibling field.  Lazy evaluation...
 */

typedef unsigned long  TimeStamp;

typedef struct Time_Stamped_Trie_Node *TSTNptr;
typedef struct Time_Stamped_Trie_Node {
  InstrPlusType info;
  TSTNptr sibling;
  TSTNptr child;
  TSTNptr parent;
  Cell symbol;
  TimeStamp ts;
} TS_TrieNode;

/* Field Access Macros
   ------------------- */
#define TSTN_Instr(pTSTN)	TN_Instr(pTSTN)
#define TSTN_Status(pTSTN)	TN_Status(pTSTN)
#define TSTN_TrieType(pTSTN)	TN_TrieType(pTSTN)
#define TSTN_NodeType(pTSTN)	TN_NodeType(pTSTN)
#define TSTN_Parent(pTSTN)	TN_Parent(pTSTN)
#define TSTN_Child(pTSTN)	TN_Child(pTSTN)
#define TSTN_Sibling(pTSTN)	TN_Sibling(pTSTN)
#define TSTN_Symbol(pTSTN)	TN_Symbol(pTSTN)
#define TSTN_TimeStamp(pTSTN)	( (pTSTN)->ts )

/*===========================================================================*/

/*
 *                             Answer List Node
 *                             ================
 *
 *  A global resource for ALNs is currently implemented.  Blocks of memory
 *  for ALN storage are allocated whenever this resource is depleted.  All
 *  ALNs are allocated from this resource.  To allow rapid deallocation of
 *  these block-malloc'ed structures, the first word in the structure must
 *  contain the field used to link them into a chain when in use.
 */

typedef struct Answer_List_Node *ALNptr;
typedef struct Answer_List_Node {
  ALNptr link;
  BTNptr answer_leaf;
} AnsListNode;

#define ALN_Next(pALN)		((pALN)->link)
#define ALN_Answer(pALN)	((pALN)->answer_leaf)

/*===========================================================================*/

/*
 *                      Tabled-Call Lookup Structures
 *                      =============================
 *
 *  Data structures for parameter passing to and from the call
 *  check/insert routines.
 */

typedef struct Tabled_Call_Info_Record {
  struct Table_Info_Frame *table_info_record;
  int call_arity;
  CPtr arg_vector;
  CPtr var_vector_loc;     /* location to store the call var vector */
} TabledCallInfo;

#define CallInfo_TableInfo(CallInfo)	( (CallInfo).table_info_record )
#define CallInfo_CallArity(CallInfo)	( (CallInfo).call_arity )
#define CallInfo_Arguments(CallInfo)	( (CallInfo).arg_vector )
#define CallInfo_VarVectorLoc(CallInfo)	( (CallInfo).var_vector_loc )


typedef struct Call_Check_Insert_Results {
  BTNptr call_trie_term;
  struct subgoal_frame *subsumers_sgf;
  int variant_found;
  CPtr var_vector;         /* pointer to the vector of call variables */
} CallLookupResults;

#define CallLUR_Leaf(CLUR)		( (CLUR).call_trie_term )
#define CallLUR_Subsumer(CLUR)		( (CLUR).subsumers_sgf )
#define CallLUR_VariantFound(CLUR)	( (CLUR).variant_found )
#define CallLUR_VarVector(CLUR)		( (CLUR).var_vector )

/*===========================================================================*/


/*-- exported trie functions ------------------------------------------*/

extern BTNptr   newBasicTrie(Cell,int);
extern byte *	trie_get_calls(void);
extern Cell	get_lastnode_cs_retskel(Cell);
extern byte *	trie_get_returns(struct subgoal_frame *, Cell);
extern void	remove_open_tries(CPtr);
extern void     init_trie_aux_areas(void);
extern void     load_solution_trie(int, int, CPtr, BTNptr);
extern void     variant_call_search(TabledCallInfo *, CallLookupResults *);
extern BTNptr   one_term_chk_ins(CPtr, BTNptr, int *);
extern BTNptr   whole_term_chk_ins(Cell, BTNptr *, int *);
extern BTNptr	get_next_trie_solution(ALNptr *);
extern BTNptr	variant_answer_search(int, int, CPtr, struct subgoal_frame *,
				      xsbBool *);
extern BTNptr   delay_chk_insert(int, CPtr, CPtr *);
extern void     undo_answer_bindings(void);
extern void	load_delay_trie(int, CPtr, BTNptr);
extern xsbBool  bottom_up_unify(void);

extern void    consume_subsumptive_answer(BTNptr, int, CPtr);
extern ALNptr  tst_collect_relevant_answers(TSTNptr, TimeStamp, int, CPtr);
extern void    delete_subsumptive_table(struct Table_Info_Frame *);

extern void    tstShrinkDynStacks(void);

extern TSTNptr subsumptive_tst_search(TSTNptr, int, CPtr, xsbBool, xsbBool *);
extern BTNptr  subsumptive_bt_search(BTNptr, int, CPtr, xsbBool *);
extern TSTNptr variant_tst_search(TSTNptr, int, CPtr, xsbBool, xsbBool *);
extern BTNptr  variant_bt_search(BTNptr, int, CPtr, xsbBool *);


typedef enum Trie_Path_Type {
  NO_PATH, VARIANT_PATH, SUBSUMPTIVE_PATH
} TriePathType;

extern void *subsumptive_trie_lookup(void *root, int, CPtr,
				     TriePathType *, Cell[]);
extern void *variant_trie_lookup(void *root, int, CPtr, Cell[]);

/*---------------------------------------------------------------------*/

/* slg variables */
extern CPtr ans_var_pos_reg;
extern int  num_vars_in_var_regs;
extern int  global_num_vars;

/* used for statistics */
extern long subg_chk_ins, subg_inserts, ans_chk_ins, ans_inserts;

/* trie routine variables */
extern BTNptr Last_Nod_Sav, Paren;

/* registers for trie backtracking */
extern CPtr reg_arrayptr, var_regs[];

/*----------------------------------------------------------------------*/

/* allocate an array for easy expansion */ 
#define alloc_arr(AArrType,AArrayNam,AArraySz){\
    AArrayNam = (AArrType *)malloc(sizeof(AArrType) * AArraySz);\
    if (AArrayNam == NULL) {\
      xsb_exit("No More memory for reallocating Array");\
    }\
}

/* expand the array by doubling its size */
#define trie_expand_array(ArrType,ArrayNam, ArraySz, Nam) {\
    ArrType *Temp;\
    int Siz;\
    int i;\
\
    Temp = ArrayNam;\
    Siz  = ArraySz;\
    ArraySz = 2 * ArraySz;\
    alloc_arr(ArrType,ArrayNam,ArraySz);\
    for (i = 0; i < Siz; i++) {\
      ArrayNam[i] = Temp[i];\
    }\
    free(Temp);\
}

#define will_overflow_reg_array(x) {\
   if (x >= reg_array+reg_array_size) {\
     int idx = reg_arrayptr - reg_array;\
     trie_expand_array(Cell,reg_array,reg_array_size,"reg_array");\
     reg_arrayptr = reg_array + idx;\
   }\
}

#define pushreg(X) {\
   will_overflow_reg_array(reg_arrayptr+1);\
   (*(++reg_arrayptr)) = (Cell) X;\
}
/*----------------------------------------------------------------------*/

extern int  num_heap_term_vars;
extern CPtr *var_addr;
extern int  var_addr_arraysz;

/*----------------------------------------------------------------------*/

extern Cell * reg_array;
extern int reg_array_size;
extern int delay_it;

#define NUM_TRIEVARS 400
#define DEFAULT_ARRAYSIZ 512 

extern CPtr *copy_of_var_addr;
extern int  copy_of_num_heap_term_vars;

/*=========================================================================*/


#endif