| /**************************************************************/ |
| /* ********************************************************** */ |
| /* * * */ |
| /* * STRUCTURE SHARING * */ |
| /* * * */ |
| /* * $Module: SHARING * */ |
| /* * * */ |
| /* * Copyright (C) 1996, 1997, 1998, 1999, 2000 * */ |
| /* * 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 * */ |
| /* * * */ |
| /* ********************************************************** */ |
| /**************************************************************/ |
| |
| |
| /* $RCSfile$ */ |
| |
| #include "sharing.h" |
| |
| /**************************************************************/ |
| /* Static Variables */ |
| /**************************************************************/ |
| |
| #ifdef CHECK |
| static BOOL sharing_DATABLOCKED; |
| #endif |
| |
| static LIST sharing_DATALIST = (LIST) NULL; |
| |
| #define sharing_STACKSIZE 500 |
| static LIST sharing_STACK[sharing_STACKSIZE]; |
| static LIST* sharing_STACKPOINTER = sharing_STACK; |
| |
| /**************************************************************/ |
| /* Prototypes for static functions used only in this module */ |
| /**************************************************************/ |
| |
| static BOOL sharing_IsNoMoreUsed(TERM); |
| static LIST sharing_InternGetDataList(TERM); |
| |
| static TERM sharing_InsertIntoSharing(TERM, SHARED_INDEX); |
| static void sharing_DeleteFromSharing(TERM, SHARED_INDEX); |
| |
| static void sharing_ResetTermStamp(TERM); |
| |
| static void sharing_PrintWithSuperterms(TERM); |
| |
| |
| /**************************************************************/ |
| /* ********************************************************** */ |
| /* * * */ |
| /* * PRIMITIVE SHARING FUNCTIONS * */ |
| /* * * */ |
| /* ********************************************************** */ |
| /**************************************************************/ |
| |
| |
| SHARED_INDEX sharing_IndexCreate(void) |
| /********************************************************** |
| INPUT: None. |
| RETURNS: A shared index, consisting of an Index, a Consttable |
| and a Vartable. |
| EFFECTS: Initializes the shared Index for the sharing_Vartable and the |
| sharing_Consttable with NULL-Pointers and an empty st_index. |
| **********************************************************/ |
| { |
| SHARED_INDEX Result; |
| int i; |
| |
| Result = (SHARED_INDEX)memory_Malloc(sizeof(SHARED_INDEX_NODE)); |
| sharing_SetIndex(Result, st_IndexCreate()); |
| |
| for (i=0; (i < symbol_MaxVars()); i++) |
| sharing_SetVartableEntry(Result, i, NULL); |
| |
| for (i=0; (i < symbol_MaxConsts()); i++) |
| sharing_SetConsttableEntry(Result, i, NULL); |
| |
| sharing_SetStampID(Result, term_GetStampID()); |
| return Result; |
| } |
| |
| |
| void sharing_IndexDelete(SHARED_INDEX ShIndex) |
| /********************************************************** |
| INPUT: A shared Index. |
| RETURNS: None. |
| EFFECTS: Deletes the Index and frees the memory for the |
| structure including the Const- and Vartable. |
| **********************************************************/ |
| { |
| st_IndexDelete(sharing_Index(ShIndex)); |
| |
| memory_Free(ShIndex, sizeof(SHARED_INDEX_NODE)); |
| } |
| |
| |
| void sharing_PushOnStack(TERM Term) |
| /********************************************************** |
| INPUT: A term. |
| RETURNS: None. |
| EFFECTS: Creates a Stack of Pointers to the |
| term and all of its subterms in their order in |
| the arglist (thus ordered by depth). |
| top of the stack is bottom term |
| **********************************************************/ |
| { |
| LIST ArgList; |
| |
| #ifdef CHECK |
| if (!term_IsTerm(Term)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_PushOnStack: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| stack_Push(Term); |
| |
| ArgList = term_ArgumentList(Term); |
| |
| while (!list_Empty(ArgList)){ |
| sharing_PushOnStack(list_Car(ArgList)); |
| ArgList = list_Cdr(ArgList); |
| } |
| } |
| |
| |
| void sharing_PushReverseOnStack(TERM Term) |
| /********************************************************** |
| INPUT: A term. |
| RETURNS: None. |
| EFFECTS: Creates a Stack of Pointers to the |
| term and all of its subterms, except variables in their order in |
| the arglist (thus ordered by depth). |
| top of the stack is top term |
| **********************************************************/ |
| { |
| LIST ArgList; |
| |
| #ifdef CHECK |
| if (!term_IsTerm(Term)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_PushReverseOnStack: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| if (!term_IsVariable(Term)) { |
| |
| ArgList = term_ArgumentList(Term); |
| |
| while (!list_Empty(ArgList)){ |
| sharing_PushReverseOnStack(list_Car(ArgList)); |
| ArgList = list_Cdr(ArgList); |
| } |
| |
| stack_Push(Term); |
| } |
| } |
| |
| void sharing_PushReverseOnStackExcept(TERM Term, LIST DontTermList) |
| /********************************************************** |
| INPUT: A term and an exception list. |
| RETURNS: None. |
| EFFECTS: Creates a Stack of Pointers to the |
| term and all of its subterms that are not contained |
| or below the terms in DontTermList in their order in |
| the arglist (thus ordered by depth). |
| top of the stack is top term |
| **********************************************************/ |
| { |
| LIST ArgList; |
| |
| #ifdef CHECK |
| if (!term_IsTerm(Term)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_PushReverseOnStack: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| if (!term_IsVariable(Term) && !term_ListContainsTerm(DontTermList, Term)) { |
| ArgList = term_ArgumentList(Term); |
| |
| while (!list_Empty(ArgList)){ |
| sharing_PushReverseOnStackExcept(list_Car(ArgList), DontTermList); |
| ArgList = list_Cdr(ArgList); |
| } |
| |
| stack_Push(Term); |
| } |
| } |
| |
| void sharing_PushOnStackNoStamps(TERM Term) |
| /********************************************************** |
| INPUT: A term. |
| RETURNS: None. |
| EFFECTS: Creates a Stack of Pointers to the |
| term and all of its subterms that are not stamped |
| or below stamped terms. |
| top of the stack is top term. |
| **********************************************************/ |
| { |
| LIST ArgList; |
| |
| #ifdef CHECK |
| if (!term_IsTerm(Term)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_PushReverseOnStackNoStamps: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| if (!term_IsVariable(Term) && !term_HasTermStamp(Term)) { |
| |
| stack_Push(Term); |
| |
| ArgList = term_ArgumentList(Term); |
| |
| while (!list_Empty(ArgList)){ |
| sharing_PushOnStackNoStamps(list_Car(ArgList)); |
| ArgList = list_Cdr(ArgList); |
| } |
| } |
| } |
| |
| |
| void sharing_PushListOnStack(LIST TermList) |
| /********************************************************** |
| INPUT: A list of terms. |
| RETURNS: None. |
| EFFECTS: Creates a Stack of Pointers to the |
| terms in <TermList> and all of subterms in their order in |
| the arglist (thus ordered by depth). |
| **********************************************************/ |
| { |
| while (!list_Empty(TermList)) { |
| sharing_PushOnStack(list_Car(TermList)); |
| TermList = list_Cdr(TermList); |
| } |
| } |
| |
| |
| void sharing_PushListReverseOnStack(LIST TermList) |
| /********************************************************** |
| INPUT: A list of terms. |
| RETURNS: None. |
| EFFECTS: Puts all terms in Termlist and their superterms |
| in their order in the arglist (thus ordered by depth) |
| on the stack. |
| On top of the stack are subterms. |
| **********************************************************/ |
| { |
| while (!list_Empty(TermList)) { |
| sharing_PushReverseOnStack(list_Car(TermList)); |
| TermList = list_Cdr(TermList); |
| } |
| } |
| |
| void sharing_PushListReverseOnStackExcept(LIST TermList, LIST DontPushList) |
| /********************************************************** |
| INPUT: Two lists of terms. |
| RETURNS: None. |
| EFFECTS: Puts all terms in Termlist except those contained in |
| DontPushList and their superterms |
| in their order in the arglist (thus ordered by depth) |
| on the stack. |
| On top of the stack are subterms. |
| **********************************************************/ |
| { |
| while (!list_Empty(TermList)) { |
| sharing_PushReverseOnStackExcept(list_Car(TermList), DontPushList); |
| TermList = list_Cdr(TermList); |
| } |
| } |
| |
| void sharing_PushListOnStackNoStamps(LIST TermList) |
| /********************************************************** |
| INPUT: A list of terms. |
| RETURNS: None. |
| EFFECTS: Puts all terms in Termlist on the stack. |
| On top of the stack are subterms. |
| **********************************************************/ |
| { |
| while (!list_Empty(TermList)) { |
| sharing_PushOnStackNoStamps(list_Car(TermList)); |
| TermList = list_Cdr(TermList); |
| } |
| } |
| |
| |
| static BOOL sharing_IsNoMoreUsed(TERM Term) |
| /********************************************************** |
| INPUT: A term. |
| RETURNS: TRUE, if the Term has no superterms, |
| FALSE, else. |
| **********************************************************/ |
| { |
| #ifdef CHECK |
| if (!term_IsTerm(Term)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_IsNoMoreUsed: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| return (list_Empty(term_SupertermList(Term))); |
| } |
| |
| |
| /**************************************************************/ |
| /* ********************************************************** */ |
| /* * * */ |
| /* * FUNCTIONS FOR INSERTION AND DELETION * */ |
| /* * * */ |
| /* ********************************************************** */ |
| /**************************************************************/ |
| |
| /**************************************************************/ |
| /* ********************************************************** */ |
| /* * * */ |
| /* * 1) FUNCTIONS FOR INSERTION * */ |
| /* * * */ |
| /* ********************************************************** */ |
| /**************************************************************/ |
| |
| TERM sharing_Insert(POINTER Data, TERM Atom, SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A data element, it's unshared atom and a SharedIndex. |
| RETURNS: The shared term inserted into the SharedIndex. |
| CAUTION: The superterm slot of <Atom> is destructively used! |
| MEMORY: The term 'Atom' still exists, memory needed for |
| the shared version is allocated. |
| **********************************************************/ |
| { |
| #ifdef CHECK |
| if (!term_IsTerm(Atom) || (!sharing_IsNoMoreUsed(Atom))){ |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_Insert: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| Atom = sharing_InsertIntoSharing(Atom, SharedIndex); |
| |
| term_RplacSupertermList(Atom, list_Cons(Data, term_SupertermList(Atom))); |
| |
| return(Atom); |
| } |
| |
| |
| static TERM sharing_InsertIntoSharing(TERM Term, SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A term and a shared index. |
| RETURNS: A copy of 'Term' which is inserted into the Sharing |
| and the "SharedIndex". |
| MEMORY: The unshared version isn't freed, needed memory |
| is allocated. |
| **********************************************************/ |
| { |
| int B_Stack; |
| TERM InsTerm; |
| |
| #ifdef CHECK |
| if (!term_IsTerm(Term)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_InsertIntoSharing: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| B_Stack = stack_Bottom(); |
| sharing_PushOnStack(Term); |
| InsTerm = stack_Top(); /* not necessary initialization ... */ |
| |
| while (! stack_Empty(B_Stack)){ |
| InsTerm = stack_PopResult(); |
| |
| if (term_IsVariable(InsTerm)){ |
| if (!sharing_IsSharedVar(InsTerm, SharedIndex)) { |
| |
| sharing_SetVartableEntry(SharedIndex, sharing_VariableIndex(InsTerm), |
| term_Create(term_TopSymbol(InsTerm), |
| list_Nil())); |
| |
| st_EntryCreate(sharing_Index(SharedIndex), |
| sharing_VartableEntry(SharedIndex, |
| sharing_VariableIndex(InsTerm)), |
| sharing_VartableEntry(SharedIndex, |
| sharing_VariableIndex(InsTerm)), |
| cont_LeftContext()); |
| } |
| |
| /* The NULL-Pointer in the Vartable is replaced by a copy of the */ |
| /* InsTerm, which is referenced by the InsTerms SharedTermCopy. */ |
| /* A complex T still has to be insert. into its Args superlists. */ |
| /* The unshared Term isn't yet in the 'SharedIndex' and thus is */ |
| /* inserted, too. */ |
| |
| |
| sharing_RememberSharedTermCopy(InsTerm, |
| sharing_VartableEntry(SharedIndex, sharing_VariableIndex(InsTerm))); |
| |
| }else if (term_IsConstant(InsTerm)){ |
| if (!sharing_IsSharedConst(InsTerm, SharedIndex)) { |
| sharing_SetConsttableEntry(SharedIndex, sharing_ConstantIndex(InsTerm), |
| term_Create(term_TopSymbol(InsTerm), |
| list_Nil())); |
| |
| st_EntryCreate(sharing_Index(SharedIndex), |
| sharing_ConsttableEntry(SharedIndex, sharing_ConstantIndex(InsTerm)), |
| sharing_ConsttableEntry(SharedIndex, sharing_ConstantIndex(InsTerm)), |
| cont_LeftContext()); |
| } |
| |
| /* The NULL-Pointer in the Consttable is replaced by a copy of the */ |
| /* InsTerm, which is referenced by the InsTerms SharedTermCopy. */ |
| /* A complex T still has to be insert. into its Args superlists. */ |
| /* The unshared Term isn't yet in the 'SharedIndex' and thus is */ |
| /* inserted, too. */ |
| |
| sharing_RememberSharedTermCopy(InsTerm, |
| sharing_ConsttableEntry(SharedIndex, sharing_ConstantIndex(InsTerm))); |
| |
| }else{ /* term_IsComplex(InsTerm) */ |
| /* -> owns subterms which now have copies in Sharing. */ |
| |
| TERM SharedDuplicate; |
| LIST HelpList; |
| BOOL DuplCandHasSameArgs; |
| |
| SharedDuplicate = (TERM)NULL; |
| HelpList = |
| term_SupertermList(sharing_SharedTermCopy(term_FirstArgument(InsTerm))); |
| if (list_Empty(HelpList)){ |
| SharedDuplicate = term_Create(term_TopSymbol(InsTerm), list_Nil()); |
| DuplCandHasSameArgs = FALSE; |
| } |
| else{ |
| DuplCandHasSameArgs = FALSE; |
| while (!DuplCandHasSameArgs && !list_Empty(HelpList)){ |
| SharedDuplicate = (TERM) list_First(HelpList); |
| |
| if (term_TopSymbol(SharedDuplicate) == term_TopSymbol(InsTerm)){ |
| LIST OrigHelpArgList, DuplHelpArgList; |
| |
| OrigHelpArgList = term_ArgumentList(InsTerm); |
| DuplHelpArgList = term_ArgumentList(SharedDuplicate); |
| while (!list_Empty(OrigHelpArgList) && |
| (DuplCandHasSameArgs = |
| (sharing_SharedTermCopy(list_First(OrigHelpArgList)) == |
| list_First(DuplHelpArgList)))){ |
| DuplHelpArgList = list_Cdr(DuplHelpArgList); |
| OrigHelpArgList = list_Cdr(OrigHelpArgList); |
| } |
| } |
| HelpList = list_Cdr(HelpList); |
| } |
| if (!DuplCandHasSameArgs) |
| SharedDuplicate = term_Create(term_TopSymbol(InsTerm), list_Nil()); |
| } /* end of else fuer Behandlung von InsTerm mit shared FirstArg. */ |
| |
| if (!DuplCandHasSameArgs){ |
| /* Falls neue Kopie gemacht wurde, wird diese hier "eingeshared": */ |
| |
| for (HelpList = term_ArgumentList(InsTerm); !list_Empty(HelpList); |
| HelpList = list_Cdr(HelpList)){ |
| TERM SharedArg; |
| |
| SharedArg = sharing_SharedTermCopy((TERM)list_First(HelpList)); |
| |
| term_RplacArgumentList(SharedDuplicate, |
| list_Cons(SharedArg, |
| term_ArgumentList(SharedDuplicate))); |
| |
| term_RplacSupertermList(SharedArg, |
| list_Cons(SharedDuplicate, |
| term_SupertermList(SharedArg))); |
| } |
| term_RplacArgumentList(SharedDuplicate, |
| list_NReverse(term_ArgumentList(SharedDuplicate))); |
| |
| /* Now a newly generated term can be inserted into the 'SharedIndex' ! */ |
| |
| st_EntryCreate(sharing_Index(SharedIndex), |
| SharedDuplicate, |
| SharedDuplicate, |
| cont_LeftContext()); |
| |
| } |
| sharing_RememberSharedTermCopy(InsTerm, |
| SharedDuplicate); |
| } |
| } |
| |
| return(sharing_SharedTermCopy(InsTerm)); |
| } |
| |
| /**************************************************************/ |
| /* ********************************************************** */ |
| /* * * */ |
| /* * 2) FUNCTIONS FOR DELETION * */ |
| /* * * */ |
| /* ********************************************************** */ |
| /**************************************************************/ |
| |
| void sharing_Delete(POINTER Data, TERM Atom, SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A data element, its atom and an index. |
| RETURNS: Nothing. |
| MEMORY: Destructive, deletes 'Atom' from Sharing and frees |
| memory that's no more needed. |
| ***********************************************************/ |
| { |
| #ifdef CHECK |
| if (!term_IsTerm(Atom)){ |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_Delete: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| term_RplacSupertermList(Atom, |
| list_PointerDeleteElement(term_SupertermList(Atom), Data)); |
| |
| if (sharing_IsNoMoreUsed(Atom)) |
| sharing_DeleteFromSharing(Atom, SharedIndex); |
| |
| } |
| |
| |
| static void sharing_DeleteFromSharing(TERM Term, SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A term and a SharedIndex |
| RETURNS: Nothing |
| MEMORY: 'Term' is removed from the Sharing, only correct |
| if 'Term' is unshared in sharing (real subterms |
| may be shared, off course). |
| ***********************************************************/ |
| { |
| BOOL IsIndexed; |
| #ifdef CHECK |
| if (!term_IsTerm(Term)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_DeleteFromSharing: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| IsIndexed = st_EntryDelete(sharing_Index(SharedIndex), Term, Term, cont_LeftContext()); |
| |
| #ifdef CHECK |
| if (!IsIndexed) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_DeleteFromSharing: Input not indexed.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| if (term_IsComplex(Term)){ |
| LIST Args; |
| |
| Args = term_ArgumentList(Term); |
| |
| while (!list_Empty(Args)){ |
| TERM NextArg; |
| LIST Help; |
| |
| /* This block frees the terms arglists memory. */ |
| Help = Args; |
| NextArg = (TERM) list_First(Args); |
| Args = list_Cdr(Args); |
| list_Free(Help); |
| |
| term_RplacSupertermList(NextArg, |
| list_PointerDeleteOneElement(term_SupertermList(NextArg), Term)); |
| if (sharing_IsNoMoreUsed(NextArg)) |
| sharing_DeleteFromSharing(NextArg, SharedIndex); |
| } |
| |
| } else if (term_IsConstant(Term)) { |
| sharing_SetConsttableEntry(SharedIndex, sharing_ConstantIndex(Term), NULL); |
| } else { |
| sharing_SetVartableEntry(SharedIndex, sharing_VariableIndex(Term), NULL); |
| } |
| list_Delete(term_SupertermList(Term)); |
| term_Free(Term); |
| } |
| |
| |
| /**************************************************************/ |
| /* Functions to access unshared data via the shared term. */ |
| /**************************************************************/ |
| |
| LIST sharing_GetDataList(TERM Term, SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A shared term and the shared index it belongs to. |
| RETURNS: The list of data connected to all superterms of Term, |
| e.g. the list of all literals containing Term. |
| EFFECT: Allocates memory for the returned list. |
| CAUTION: Works recursive! |
| **********************************************************/ |
| { |
| LIST Result = list_Nil(); |
| #ifdef CHECK |
| if (!term_IsTerm(Term) || (SharedIndex == NULL)){ |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_GetDataList: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| /* What if the term doesn't belong to this shared index ?????? */ |
| |
| #endif |
| |
| if (term_StampOverflow(sharing_StampID(SharedIndex))) |
| sharing_ResetAllTermStamps(SharedIndex); |
| |
| term_StartStamp(); |
| |
| Result = sharing_InternGetDataList(Term); |
| |
| term_StopStamp(); |
| |
| return Result; |
| } |
| |
| |
| static LIST sharing_InternGetDataList(TERM Term) |
| /********************************************************** |
| INPUT: A shared term. |
| RETURNS: The list of data connected to all superterms of Term |
| EFFECT: Allocates memory for the returned list. |
| ********************************************************/ |
| { |
| if (term_IsAtom(Term)) |
| /* We are at top level of the superterm "tree", */ |
| /* so the recursion stops here */ |
| return list_Copy(term_AtomsLiterals(Term)); |
| else{ |
| LIST SuperList; |
| LIST DataList = list_Nil(); |
| |
| for (SuperList = term_SupertermList(Term); !list_Empty(SuperList); |
| SuperList = list_Cdr(SuperList)) { |
| TERM superterm = (TERM) list_Car(SuperList); |
| if (!term_AlreadyVisited(superterm)) { |
| DataList = list_Nconc(sharing_InternGetDataList(superterm), DataList); |
| term_SetTermStamp(superterm); |
| } |
| } |
| return DataList; |
| } |
| } |
| |
| |
| void sharing_StartDataIterator(TERM Term, SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A shared term and the shared index it belongs to. |
| RETURNS: Nothing. |
| EFFECT: Prepares the data iterator for Term. |
| After this call you can access single data items |
| for Term with function sharing_GetNextData. |
| ********************************************************/ |
| { |
| #ifdef CHECK |
| if (!term_IsTerm(Term) || (SharedIndex == NULL)){ |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_StartDataIterator: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| if (sharing_DATABLOCKED) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_StartDataIterator: Data iterator already used.\n"); |
| misc_FinishErrorReport(); |
| } |
| sharing_DATABLOCKED = TRUE; |
| #endif |
| |
| if (term_StampOverflow(sharing_StampID(SharedIndex))) |
| sharing_ResetAllTermStamps(SharedIndex); |
| term_StartStamp(); |
| |
| /* Init stack */ |
| sharing_STACKPOINTER = sharing_STACK; /* Pop all items */ |
| while (!term_IsAtom(Term)) { |
| /* Push superterm list on stack */ |
| *(sharing_STACKPOINTER++) = term_SupertermList(Term); |
| Term = list_Car(term_SupertermList(Term)); |
| } |
| |
| sharing_DATALIST = term_AtomsLiterals(Term); |
| } |
| |
| |
| POINTER sharing_GetNextData(void) |
| /********************************************************** |
| INPUT: None |
| RETURNS: A single data item connected to the term specified |
| in the previous call of sharing_StartDataIterator. |
| NULL is returned, if all data items were accessed before. |
| EFFECT: In contrast to function sharing_GetDataList |
| no memory is allocated. |
| ********************************************************/ |
| { |
| POINTER Result = NULL; |
| LIST superlist; |
| |
| #ifdef CHECK |
| if (!sharing_DATABLOCKED) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_GetNextData: Iterator wasn't started.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| if (!list_Empty(sharing_DATALIST)) { |
| Result = list_Car(sharing_DATALIST); |
| sharing_DATALIST = list_Cdr(sharing_DATALIST); |
| } else { |
| superlist = NULL; |
| while ((sharing_STACKPOINTER > sharing_STACK) && /* stack not empty */ |
| list_Empty(superlist)) { |
| /* change between backtracking and expansion */ |
| do { /* Backtracking */ |
| superlist = *(--sharing_STACKPOINTER); /* PopResult */ |
| term_SetTermStamp(list_Car(superlist)); |
| do |
| superlist = list_Cdr(superlist); |
| while (!list_Empty(superlist) && |
| term_AlreadyVisited(list_Car(superlist))); |
| } while ((sharing_STACKPOINTER>sharing_STACK) && list_Empty(superlist)); |
| while (!list_Empty(superlist) && |
| !term_IsAtom(list_Car(superlist))) { /* Expansion */ |
| *(sharing_STACKPOINTER++) = superlist; |
| superlist = term_SupertermList(list_Car(superlist)); |
| /* Search next unvisited term */ |
| while (!list_Empty(superlist) && |
| term_AlreadyVisited(list_Car(superlist))) |
| superlist = list_Cdr(superlist); |
| } |
| } |
| if (!list_Empty(superlist)) { |
| *(sharing_STACKPOINTER++) = superlist; |
| sharing_DATALIST = term_AtomsLiterals(list_Car(superlist)); |
| Result = list_Car(sharing_DATALIST); |
| sharing_DATALIST = list_Cdr(sharing_DATALIST); |
| } |
| } /* else */ |
| return Result; |
| } |
| |
| |
| void sharing_StopDataIterator(void) |
| /********************************************************** |
| INPUT: None. |
| RETURNS: Nothing. |
| EFFECT: The data iterator is stopped for the term you specified |
| in the corresponding call of sharing_StartDataIterator. |
| ********************************************************/ |
| { |
| #ifdef CHECK |
| if (!sharing_DATABLOCKED) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_StopDataIterator: Iterator wasn't started.\n"); |
| misc_FinishErrorReport(); |
| } |
| sharing_DATABLOCKED = FALSE; |
| #endif |
| sharing_DATALIST = list_Nil(); |
| term_StopStamp(); |
| } |
| |
| |
| LIST sharing_NAtomDataList(TERM Atom) |
| /********************************************************** |
| INPUT: A shared term. |
| RETURNS: A List of data connected with 'Term' or superterms. |
| EFFECT: No memory Allocation |
| CAUTION: THE RETURNED LIST MUST NOT CHANGE |
| **********************************************************/ |
| { |
| #ifdef CHECK |
| if (!term_IsTerm(Atom) || !term_IsAtom(Atom)){ |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_NAtomDataList: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| return(term_AtomsLiterals(Atom)); |
| } |
| |
| |
| LIST sharing_GetAllSuperTerms(SHARED_INDEX Index) |
| /********************************************************** |
| INPUT: A shared Index. |
| RETURNS: A List of all Data in the shared Index. |
| EFFECT: The term stamp is used. |
| **********************************************************/ |
| { |
| int i; |
| LIST Result = list_Nil(); |
| TERM term; |
| |
| if (term_StampOverflow(sharing_StampID(Index))) |
| sharing_ResetAllTermStamps(Index); |
| term_StartStamp(); |
| |
| for (i = 0; i < symbol_MaxVars(); i++) { |
| term = sharing_VartableEntry(Index,i); |
| if (term != NULL) |
| Result = list_Nconc(sharing_InternGetDataList(term), Result); |
| } |
| |
| for (i = 0; i < symbol_MaxConsts(); i++) { |
| term = sharing_ConsttableEntry(Index,i); |
| if (term != NULL) |
| Result = list_Nconc(sharing_InternGetDataList(term), Result); |
| } |
| |
| term_StopStamp(); |
| |
| return Result; |
| } |
| |
| |
| void sharing_ResetAllTermStamps(SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A shared index. |
| RETURNS: Nothing. |
| EFFECT: The stamps of all terms in the shared index are reset. |
| **********************************************************/ |
| { |
| TERM term; |
| int i; |
| |
| /* Reset stamp for all variables and their superterms */ |
| for (i = 0; i < symbol_MaxVars(); i++) { |
| term = sharing_VartableEntry(SharedIndex, i); |
| if (term != NULL) |
| sharing_ResetTermStamp(term); |
| } |
| |
| /* Reset stamp for all constants and their superterms */ |
| for (i = 0; i < symbol_MaxConsts(); i++){ |
| term = sharing_ConsttableEntry(SharedIndex, i); |
| if (term != NULL) |
| sharing_ResetTermStamp(term); |
| } |
| } |
| |
| |
| static void sharing_ResetTermStamp(TERM Term) |
| /********************************************************** |
| INPUT: A term. |
| RETURNS: Nothing. |
| EFFECT: The stamps of Term and all its superterms are reset. |
| **********************************************************/ |
| { |
| LIST SuperList; |
| TERM SuperTerm; |
| |
| if (!term_IsAtom(Term)) { |
| for (SuperList = term_SupertermList(Term); !list_Empty(SuperList); |
| SuperList = list_Cdr(SuperList)) { |
| SuperTerm = (TERM) list_Car(SuperList); |
| if (!term_StampAlreadyReset(SuperTerm)) { |
| sharing_ResetTermStamp(SuperTerm); |
| term_ResetTermStamp(SuperTerm); |
| } |
| } |
| } |
| } |
| |
| |
| NAT sharing_GetNumberOfOccurances(TERM Term) |
| /************************************************************** |
| INPUT: A shared (!) term. |
| RETURNS: How many literals contain <Term>. |
| Note that literals containing <Term> <n> times are counted |
| <n> times. |
| ***************************************************************/ |
| { |
| if (term_IsAtom(Term)) |
| /* Stop recursion */ |
| return list_Length(term_AtomsLiterals(Term)); |
| else { |
| LIST Scan; |
| NAT Result; |
| |
| Result = 0; |
| for (Scan = term_SupertermList(Term); !list_Empty(Scan); Scan = list_Cdr(Scan)) |
| Result += sharing_GetNumberOfOccurances(list_Car(Scan)); |
| |
| return Result; |
| } |
| } |
| |
| |
| NAT sharing_GetNumberOfInstances(TERM Term, SHARED_INDEX Index) |
| /************************************************************** |
| INPUT: A (!) shared term and a shared index. The term has to be |
| part of the index. |
| RETURNS: How many literals within the index contain an instance of <Term>. |
| Note that literals containing <n> instances of <Term> |
| are counted <n> times. |
| ***************************************************************/ |
| { |
| NAT Result; |
| TERM Instance; |
| |
| Result = 0; |
| Instance = st_ExistInstance(cont_LeftContext(), sharing_Index(Index), Term); |
| while (Instance != NULL) { |
| Result += sharing_GetNumberOfOccurances(Instance); |
| Instance = st_NextCandidate(); |
| } |
| return Result; |
| } |
| |
| |
| /**************************************************************/ |
| /* Output functions for the sharing structure. */ |
| /**************************************************************/ |
| |
| void sharing_PrintVartable(SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A shared index. |
| RETURNS: Nothing. |
| EFFECT: Prints the Vartable entries to stdout |
| **********************************************************/ |
| { |
| int i; |
| |
| for (i = 0; i < symbol_MaxVars(); i++){ |
| if (sharing_VartableEntry(SharedIndex, i) != NULL){ |
| printf("\n X%d : ", i); |
| |
| term_Print(sharing_VartableEntry(SharedIndex, i)); |
| } |
| } |
| } |
| |
| |
| void sharing_PrintConsttable(SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A shared index. |
| RETURNS: Nothing. |
| EFFECT: Prints the Consttable entries to stdout |
| **********************************************************/ |
| { |
| int i; |
| |
| for (i = 0; i < symbol_MaxConsts(); i++){ |
| if (sharing_ConsttableEntry(SharedIndex, i) != NULL){ |
| printf("\n c%d : ", i); |
| |
| term_Print(sharing_ConsttableEntry(SharedIndex, i)); |
| } |
| } |
| } |
| |
| |
| void sharing_PrintSharingConstterms1(SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A shared index. |
| RETURNS: Nothing. |
| EFFECT: Prints all terms from the Consttable and their |
| direct superterms to stdout |
| **********************************************************/ |
| { |
| TERM term; |
| int i; |
| |
| for (i = 0; i < symbol_MaxConsts(); i++) { |
| term = sharing_ConsttableEntry(SharedIndex, i); |
| if (term != NULL){ |
| printf("\n c%d : ", i); |
| term_Print(term); |
| puts(" has the direct superterms : "); |
| term_TermListPrint(term_SupertermList(term)); |
| } |
| } |
| } |
| |
| |
| void sharing_PrintSharingVarterms1(SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A shared index. |
| RETURNS: Nothing. |
| EFFECT: Prints all terms from the Vartable and their |
| superterms to stdout |
| **********************************************************/ |
| { |
| TERM term; |
| int i; |
| |
| for (i = 0; i < symbol_MaxVars(); i++) { |
| term = sharing_VartableEntry(SharedIndex, i); |
| if (term != NULL){ |
| printf("\n x%d : ", i); |
| term_Print(term); |
| puts(" has the direct superterms : "); |
| term_TermListPrint(term_SupertermList(term)); |
| } |
| } |
| } |
| |
| |
| static void sharing_PrintWithSuperterms(TERM Term) |
| /********************************************************** |
| INPUT: A Term |
| RETURNS: Nothing. |
| EFFECT: Prints all Superterms of 'Term' from the sharing |
| to stdout. |
| **********************************************************/ |
| { |
| |
| LIST HelpList; |
| |
| #ifdef CHECK |
| if (!term_IsTerm(Term)) { |
| misc_StartErrorReport(); |
| misc_ErrorReport("\n In sharing_PrintWithSuperterms: Illegal input.\n"); |
| misc_FinishErrorReport(); |
| } |
| #endif |
| |
| if (term_IsAtom(Term)) { |
| term_Print(Term); |
| putchar('\n'); |
| } |
| else{ |
| term_Print(Term); |
| HelpList = term_SupertermList(Term); |
| if (!list_Empty(HelpList)){ |
| putchar('['); |
| term_TermListPrint(HelpList); |
| puts("]"); |
| while (!list_Empty(HelpList)){ |
| sharing_PrintWithSuperterms(list_Car(HelpList)); |
| HelpList = list_Cdr(HelpList); |
| } |
| } |
| } |
| } |
| |
| |
| void sharing_PrintSharing(SHARED_INDEX SharedIndex) |
| /********************************************************** |
| INPUT: A shared Index. |
| EFFECT: Prints the sharing to standard.out. |
| **********************************************************/ |
| { |
| int i; |
| |
| for (i = 0; i < symbol_MaxConsts(); i++){ |
| if (sharing_ConsttableEntry(SharedIndex, i) != NULL){ |
| sharing_PrintWithSuperterms(sharing_ConsttableEntry(SharedIndex, i)); |
| puts("\n"); |
| } |
| } |
| puts("------------------------"); |
| for (i = 0; i < symbol_MaxVars(); i++){ |
| if (sharing_VartableEntry(SharedIndex, i) != NULL){ |
| sharing_PrintWithSuperterms(sharing_VartableEntry(SharedIndex, i)); |
| puts("\n"); |
| } |
| } |
| } |
| |
| |
| void sharing_PrintSameLevelTerms(TERM Term) |
| /********************************************************** |
| INPUT: A term. |
| RETURNS: Nothing. |
| EFFECT: Prints all terms, that share any of 'Term's args to |
| standard.out. |
| **********************************************************/ |
| { |
| LIST HelpList; |
| |
| HelpList = term_ArgumentList(Term); |
| |
| while (!list_Empty(HelpList)){ |
| if (!list_Empty(term_SupertermList(list_First(HelpList)))) |
| term_TermListPrint(term_SupertermList(list_First(HelpList))); |
| |
| HelpList = list_Cdr(HelpList); |
| } |
| } |
| |
| void sharing_PrintStack(void) |
| /********************************************************** |
| INPUT: None. |
| RETURNS: Nothing. |
| EFFECT: Prints the internal sharing stack for iterative |
| queries. Only for debugging purposes. |
| **********************************************************/ |
| { |
| TERM term; |
| LIST* ptr = sharing_STACKPOINTER; |
| |
| while (ptr > sharing_STACK) { |
| ptr--; |
| term = list_Car(*ptr); |
| term_Print(term); |
| putchar('\n'); |
| } |
| } |
| |
| |