MultiSource/Applications/SPASS/table.c

/**************************************************************/
/* ********************************************************** */
/* *                                                        * */
/* *             SIGNATURE TABLE                            * */
/* *                                                        * */
/* *  $Module:   TABLE                                      * */ 
/* *                                                        * */
/* *  Copyright (C) 1999, 2000, 2001 MPI fuer Informatik    * */
/* *                                                        * */
/* *  This program is free software; you can redistribute   * */
/* *  it and/or modify it under the terms of the GNU        * */
/* *  General Public License as published by the Free       * */
/* *  Software Foundation; either version 2 of the License, * */
/* *  or (at your option) any later version.                * */
/* *                                                        * */
/* *  This program 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 General Public * */
/* *  License for more details.                             * */
/* *                                                        * */
/* *  You should have received a copy of the GNU General    * */
/* *  Public License along with this program; if not, write * */
/* *  to the Free Software Foundation, Inc., 59 Temple      * */
/* *  Place, Suite 330, Boston, MA  02111-1307  USA         * */
/* *                                                        * */
/* *                                                        * */
/* $Revision$                                         * */
/* $State$                                            * */
/* $Date$                             * */
/* $Author$                                       * */
/* *                                                        * */
/* *             Contact:                                   * */
/* *             Christoph Weidenbach                       * */
/* *             MPI fuer Informatik                        * */
/* *             Stuhlsatzenhausweg 85                      * */
/* *             66123 Saarbruecken                         * */
/* *             Email: weidenb@mpi-sb.mpg.de               * */
/* *             Germany                                    * */
/* *                                                        * */
/* ********************************************************** */
/**************************************************************/


/**************************************************************/
/* Includes                                                   */
/**************************************************************/

#include "table.h"


/**************************************************************/
/* Inline functions                                           */
/**************************************************************/

static __inline__ int table_Index(SYMBOL symbol)
{
  if (symbol_IsVariable(symbol))
    return -(int) symbol;
  else
    return symbol_Index(symbol);
}


static __inline__ TERM table_GetTerm(TERMARRAY ta)
{
  return ta->term;
}


static __inline__ TERMARRAY table_SetTerm(TERMARRAY ta, TERM term)
{
  ta->term = term;
  return ta;
}


static __inline__ int table_GetStamp(TERMARRAY ta)
{
  return ta->stamp;
}


static __inline__ TERMARRAY table_SetStamp(TERMARRAY ta, int stamp)
{
  ta->stamp = stamp;
  return ta;
}


static __inline__ TERMARRAY table_GetChild(TERMARRAY ta)
{
  return ta->child;
}


static __inline__ TERMARRAY table_SetChild(TERMARRAY ta, TERMARRAY child)
{
  ta->child = child;
  return ta;
}


static __inline__ TERMARRAY table_GetTermarray(TABLE table)
{
  return table->ta;
}


static __inline__ TABLE table_SetTermarray(TABLE table, TERMARRAY ta)
{
  table->ta = ta;
  return table;
}


static __inline__ TERMARRAY *table_GetPoss(TABLE table)
{
  return table->pos;
}


static __inline__ TERMARRAY table_GetPos(TABLE table, int index)
{
  return table_GetPoss(table)[index];
}


static __inline__ TABLE table_SetPoss(TABLE table, TERMARRAY *ref)
{
  table->pos = ref;
  return table;
}


static __inline__ TABLE table_SetPos(TABLE table, int index, TERMARRAY ta)
{
  table_GetPoss(table)[index] = ta;
  return table;
}


static __inline__ int *table_GetPosstamps(TABLE table)
{
  return table->posstamp;
}


static __inline__ int table_GetPosstamp(TABLE table, int index)
{
  return table_GetPosstamps(table)[index];
}


static __inline__ TABLE table_SetPosstamps(TABLE table, int *ref)
{
  table->posstamp = ref;
  return table;
}


static __inline__ TABLE table_SetPosstamp(TABLE table, int index, int stamp)
{
  table_GetPosstamps(table)[index] = stamp;
  return table;
}


static __inline__ int table_GetStampcounter(TABLE table)
{
  return table->stampcounter;
}


static __inline__ TABLE table_SetStampcounter(TABLE table, int stampcounter)
{
  table->stampcounter = stampcounter;
  return table;
}


static __inline__ int table_GetOpbound(TABLE table)
{
  return table->opbound;
}


static __inline__ TABLE table_SetOpbound(TABLE table, int opbound)
{
  table->opbound = opbound;
  return table;
}


static __inline__ int table_GetVarbound(TABLE table)
{
  return table->varbound;
}


static __inline__ TABLE table_SetVarbound(TABLE table, int varbound)
{
  table->varbound = varbound;
  return table;
}


static __inline__ int table_GetTermbound(TABLE table)
{
  return table->termbound;
}


static __inline__ TABLE table_SetTermbound(TABLE table, int termbound)
{
  table->termbound = termbound;
  return table;
}


static __inline__ BOOL table_LegalPosIndex(TABLE table, int index)
{
  return 0 <= index && index <= table_GetTermbound(table);
}


static __inline__ BOOL table_Stamped(TABLE table, TERMARRAY ta)
{
  return table_GetStamp(ta) == table_GetStampcounter(table);
}


static __inline__ TERMARRAY table_DelayedInit(TABLE table, TERMARRAY ta)
/***************************************************************
  INPUT:   a table and a termarray
  RETURNS: the (now stamped) termarray
  EFFECT:  partially initializes table by setting the
	   termarray's entry to the empty term
***************************************************************/
{
  if (!table_Stamped(table, ta)) {
    table_SetTerm(ta, term_Null());
    table_SetStamp(ta, table_GetStampcounter(table));
  }
  return ta;
}


static __inline__ BOOL table_PosStamped(TABLE table, int index)
{
  return table_GetPosstamp(table, index) == table_GetStampcounter(table);
}


static __inline__ int table_DelayedPosInit(TABLE table, int index)
/***************************************************************
  INPUT:   a table and a position index
  RETURNS: the (now stamped) position index
  EFFECT:  partially initializes table by setting the indexed
	   position to the empty pointer, which means that the
	   term with this index is not stored in table
***************************************************************/
{
  if (!table_PosStamped(table, index)) {
    table_SetPos(table, index, (TERMARRAY) NULL);
    table_SetPosstamp(table, index, table_GetStampcounter(table));
  }
  return index;
}


/**************************************************************/
/* Functions                                                  */
/**************************************************************/

TABLE table_Null(void)
{
  return (TABLE) NULL;
}


TABLE table_Create(int opbound, int varbound, int termbound)
/***************************************************************
  INPUT:   bounds for the operator symbol, variable and term
	   indices of the terms to be stored in the signature
	   table (i. e. for every such term its top symbol index
	   has to be in [1, opbound] and the term numbers of its
	   arguments in [0, termbound] - or its variable index
	   in [1, varbound] if it is a variable)
  RETURNS: a new (and empty) signature table 
***************************************************************/
{
  TABLE result;

#ifdef CHECK
  if (opbound < 0) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In table_Create: negative opbound.");
    misc_FinishErrorReport();
  }
  if (varbound < 0) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In table_Create: negative varbound.");
    misc_FinishErrorReport();
  }
  if (termbound < 0) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In table_Create: negative termbound.");
    misc_FinishErrorReport();
  }
#endif

  result = (TABLE) memory_Malloc(sizeof(struct table));
  table_SetTermarray(result, (TERMARRAY) memory_Calloc (
                                           opbound + varbound + 1,
                                           sizeof(struct termarray)
                                         ) + varbound);
    /* move pointer to the middle of the array to allow negative indices */
  table_SetPoss(
    result,
    (TERMARRAY*) memory_Malloc((termbound + 1) * sizeof(TERMARRAY))
  );
  table_SetPosstamps(result, (int*) memory_Calloc(termbound + 1, sizeof(int)));
  table_SetOpbound(result, opbound);
  table_SetVarbound(result, varbound);
  table_SetTermbound(result, termbound);
  table_SetStampcounter(result, 1);
  return result;
}


static void table_FreeTermarray(TERMARRAY ta, int size)
/***************************************************************
  INPUT:  the termarray to free and its size
  EFFECT: recursively frees the tree structure allocated for the
	  signature array
***************************************************************/
{
  int i;

  if (ta) {
    for (i = 0; i < size; i++)
      table_FreeTermarray(table_GetChild(ta + i), size);
    memory_Free(ta, size * sizeof(struct termarray));
  }
}


void table_Free(TABLE table)
{
  int i;

  if (table != table_Null()) {
    for (i = -table_GetVarbound(table); i <= table_GetOpbound(table); i++)
      table_FreeTermarray(
        table_GetChild(table_GetTermarray(table) + i),
        table_GetTermbound(table) + 1
      );
    memory_Free(
      table_GetTermarray(table) - table_GetVarbound(table),
      (table_GetOpbound(table) + table_GetVarbound(table) + 1) * sizeof(struct
	termarray)
    );
    memory_Free(
      table_GetPoss(table),
      (table_GetTermbound(table) + 1) * sizeof(TERMARRAY)
    );
    memory_Free(
      table_GetPosstamps(table),
      (table_GetTermbound(table) + 1) * sizeof(int)
    );
    memory_Free(table, sizeof(struct table));
  }
}


TABLE table_Init(TABLE table, int opbound, int varbound, int termbound)
/***************************************************************
  INPUT:   the table to recycle and bounds for the operator
	   symbol, variable and term indices of the terms to be
	   stored in the signature table (i. e. for every such
	   term its top symbol index has to be in [1, opbound]
	   and the term numbers of its arguments in
	   [0, termbound] - or its variable index in
	   [1, varbound] if it is a variable)
  RETURNS: a cleaned up signature table 
  CAUTION: potentially frees the old table, therefore must be
	   called inside of an assignment like:
	     table = table_Init(table, ...)
***************************************************************/
{
  int opmax, varmax, termmax, i;
  TERMARRAY old;

#ifdef CHECK
  if (opbound < 0) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In table_Init: negative opbound.");
    misc_FinishErrorReport();
  }
  if (varbound < 0) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In table_Init: negative varbound.");
    misc_FinishErrorReport();
  }
  if (termbound < 0) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In table_Init: negative termbound.");
    misc_FinishErrorReport();
  }
#endif

  opmax   = table_GetOpbound(table) > opbound ? table_GetOpbound(table) :
	      opbound;
  varmax  = table_GetVarbound(table) > varbound ? table_GetVarbound(table) :
	      varbound;
  termmax = table_GetTermbound(table) > termbound ? table_GetTermbound(table) :
	      termbound;
  table_SetStampcounter(table, table_GetStampcounter(table) + 1);

  /* in case of stamp overflow or too small termarray nodes get a new table: */
  if (table_GetStampcounter(table)<=0 || termbound>table_GetTermbound(table)) {
    table_Free(table);
    return table_Create(opmax, varmax, termmax);
  }

  /* if only the top layer of the tree is too small get a larger top layer: */
  else if (opbound+varbound > table_GetOpbound(table)+table_GetVarbound(table)){
    old = table_GetTermarray(table);
    table_SetTermarray(table, (TERMARRAY) memory_Calloc(
					    opmax + varmax + 1,
					    sizeof(struct termarray)
					  ) + varmax);
    for (i = -table_GetVarbound(table); i <= table_GetOpbound(table); i++)
      table_SetChild(table_GetTermarray(table) + i, table_GetChild(old + i));
    memory_Free(
      old - table_GetVarbound(table),
      (table_GetOpbound(table) + table_GetVarbound(table) + 1) * sizeof(struct
	termarray)
    );
    table_SetOpbound(table, opmax);
    table_SetVarbound(table, varmax);
    return table;
  }

  else {

    /* move pointer to termarray's new middle: */
    table_SetTermarray(
      table,
      table_GetTermarray(table) + table_GetOpbound(table) - opbound
    );

    table_SetVarbound(
      table,
      table_GetOpbound(table) + table_GetVarbound(table) - opbound
    );
    table_SetOpbound(table, opbound);
    return table;
  }
}


TERM table_QueryAndEnter(TABLE table, PARTITION p, TERM term)
/***************************************************************
  RETURNS: a term with the same p-signature (sigtab_Index(top
	   symbol), [arg 1] , ..., [arg n] ) as term - or the
                           p              p
	   empty term if no such term exists
  EFFECT:  term enters table in the latter case
***************************************************************/
{
  TERMARRAY ta;
  LIST terms;

#ifdef CHECK
  if (part_Size(p) - 1 > table_GetTermbound(table)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In table_QueryAndEnter: partition not suitable.");
    misc_FinishErrorReport();
  }
  if (table_Index(term_TopSymbol(term)) > table_GetOpbound(table)) {
    misc_StartErrorReport();
    misc_ErrorReport
      ("\n In table_QueryAndEnter: term's operation symbol out of bounds.");
    misc_FinishErrorReport();
  }
  if (table_Index(term_TopSymbol(term)) < -table_GetVarbound(table)) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In table_QueryAndEnter: variable out of bounds.");
    misc_FinishErrorReport();
  }
  if (!table_LegalPosIndex(table, term_Size(term))) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In table_QueryAndEnter: term out of bounds.");
    misc_FinishErrorReport();
  }
#endif

  ta = table_GetTermarray(table) + table_Index(term_TopSymbol(term));
  for (terms = term_ArgumentList(term); !list_Empty(terms); terms =
      list_Cdr(terms)) {
    if (!table_GetChild(ta))
      table_SetChild(ta, (TERMARRAY) memory_Calloc (
                                       table_GetTermbound(table) + 1,
                                       sizeof(struct termarray)
                                     ));
    ta = table_GetChild(ta) + part_Find(p, term_Size(list_Car(terms)));
  }
  table_DelayedInit(table, ta);
  if (table_GetTerm(ta))
    return table_GetTerm(ta);
  else {
    table_SetTerm(ta, term);
    table_SetPos(table, table_DelayedPosInit(table, term_Size(term)), ta);
    return term_Null();
  }
}


TABLE table_Delete(TABLE table, TERM term)
/***************************************************************
  EFFECT: if term has entered table before, it is deleted
***************************************************************/
{
  int no;

#ifdef CHECK
  if (!table_LegalPosIndex(table, term_Size(term))) {
    misc_StartErrorReport();
    misc_ErrorReport("\n In table_Delete: illegal table access.");
    misc_FinishErrorReport();
  }
#endif

  no = term_Size(term);
  table_DelayedPosInit(table, no);
  if (table_GetPos(table, no)) {

#ifdef CHECK
    if (!table_Stamped(table, table_GetPos(table, no))) {
      misc_StartErrorReport();
      misc_ErrorReport("\n In table_Delete: table corrupted.");
      misc_FinishErrorReport();
    }
#endif

    table_SetTerm(table_GetPos(table, no), term_Null());
    table_SetPos(table, no, (TERMARRAY) NULL);
  }
  return table;
}