/*

File: reverse_graph.c
Author: Neil Cafferkey
Copyright (C) 1999-2001 Neil Cafferkey

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.

*/

#include <assert.h>
#include "memory_protos.h"
#include "reverse_graph_protos.h"
#include "address_set_protos.h"


/* Private function prototypes */

ReverseGraphNode CreateRGN(Address address);
ReverseGraphNode SearchRGN(ReverseGraphNode node,Address address);
VOID KillRGN(ReverseGraphNode);


/* Function: CreateReverseGraph
 * ============================
 */

ReverseGraph CreateReverseGraph(VOID)
{
   ReverseGraph graph=Malloc(sizeof(ReverseGraph_imp));

   graph->root=NULL;

   return graph;
}


/* Function: ReverseConnect
 * ========================
 */

VOID ReverseConnect(ReverseGraph graph,Address source,Address dest)
{
   ReverseGraphNode node;

   assert(source!=NULL);
   assert(dest!=NULL);

   if(graph->root==NULL)
      node=graph->root=CreateRGN(source);
   else
   {
      node=SearchRGN(graph->root,source);
      if(source<node->address)
         node=node->left=CreateRGN(source);
      else if(source>node->address)
         node=node->right=CreateRGN(source);
   }

   PutInSet(node->adjacent,dest);

   return;
}


/* Function: GetReverseAdjacent
 * ============================
 */

AddressSet GetReverseAdjacent(ReverseGraph graph,Address address)
{
   ReverseGraphNode node;

   if(graph->root!=NULL)
   {
      node=SearchRGN(graph->root,address);
      if(node->address==address)
         return DupSet(node->adjacent);
   }

   return CreateSet();
}





#if 0
   if(node->address==NULL)
      node->address=address;

   node=SearchRGN(graph->root);

   if(node!=NULL)
      return DupSet(node->adjacent);
   else
      return CreateSet();
}
#endif

/* Function: GetPrevModifyMem
 * ==========================
 * Finds all instructions that could possibly be the last to modify a
 * particular address.
 */
#if 0
VOID GetPrevModifyMem(AddressSet previous,ReverseGraph graph,AddressSet visited,Address address,Address key)
{
   AddressSet rev_adj;
   Address next;

   if(ModifiesMem(GetInstructionaddress,key))
      PutInSet(previous,address);
   else
   {
      rev_adj=GetReverseAdjacent(graph,address);
      while(!IsEmptySet(rev_adj))
      {
         next=TakeFromSet(rev_adj);
         if(!IsInSet(visited,next))
         {
            PutInSet(visited,next);
            GetPrevModifyMem(previous,graph,visited,next,key);
         }
      }
      KillSet(rev_adj);
   }
   return;
}
#endif

/* Function: KillReverseGraph
 * ==========================
 */

VOID KillReverseGraph(ReverseGraph graph)
{
   KillRGN(graph->root);
   Free(graph,sizeof(ReverseGraph_imp));

   return;
}



/* Function: CreateRGN
 * ===================
 */

ReverseGraphNode CreateRGN(Address address)
{
   ReverseGraphNode node=Malloc(sizeof(ReverseGraphNode_imp));

   node->left=NULL;
   node->right=NULL;
   node->address=address;
   node->adjacent=CreateSet();

   return node;
}


/* Function: SearchRGN
 * ===================
 */

ReverseGraphNode SearchRGN(ReverseGraphNode node,Address address)
{
   if((address<node->address)&&(node->left!=NULL))
      return SearchRGN(node->left,address);
   else if((address>node->address)&&(node->right!=NULL))
      return SearchRGN(node->right,address);
   else
      return node;
}


/* Function: KillRGN
 * =================
 */

VOID KillRGN(ReverseGraphNode node)
{
   if(node!=NULL)
   {
      KillRGN(node->left);
      KillRGN(node->right);

      Free(node->left,sizeof(ReverseGraphNode_imp));
      Free(node->right,sizeof(ReverseGraphNode_imp));
      KillSet(node->adjacent);
   }

   return;
}



#ifdef TEST


LONG main()
{
   ReverseGraph graph=CreateReverseGraph();

   printf("graph=%d\n",graph);
   KillReverseGraph(graph);

   graph=CreateReverseGraph();
   ReverseConnect(graph,1,10);
   ReverseConnect(graph,11,10);
   ReverseConnect(graph,11,8);

   assert(GetSetSize(GetReverseAdjacent(graph,11))==2);

   assert(IsInSet(GetReverseAdjacent(graph,11),10));
   assert(!IsInSet(GetReverseAdjacent(graph,11),1));
   assert(IsInSet(GetReverseAdjacent(graph,1),10));
   assert(!IsInSet(GetReverseAdjacent(graph,1),11));

   KillReverseGraph(graph);

   return EXIT_SUCCESS;
}

#endif