/* purify.c - Don Yang (uguu.org)

   Check log file for memory leaks.

   lclint 2.5m: 24 errors
      -boolops -branchstate -compdef -compmempass +ignoresigns -mustfree
      -nullstate -onlytrans -predboolint -retvalint -unqualifiedtrans

   12/22/00
                                                                           */

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define LOGFILE      "log.txt"

typedef struct _node
{
   unsigned int data;
   int sdata;
   struct _node *left, *right;

} Node;

static void CheckFile(FILE *infile);
static int DeleteNode(Node **node, unsigned int data);
static void DeleteTree(Node **root);
static int InsertNode(Node **root, unsigned int data, int sdata);
static void TraverseTree(Node *root);

/******************************************************************** main */
int main(int argc, char **argv)
{
   FILE *infile;

   if( argc > 1 )
   {
      if( (infile = fopen(argv[1], "rt")) == NULL )
      {
         printf("Can not open %s\n", argv[1]);
         return 1;
      }
   }
   else if( (infile = fopen(LOGFILE, "rt")) == NULL )
   {
      puts("Can not open " LOGFILE);
      return 1;
   }

   CheckFile(infile);

   fclose(infile);
   return 0;

} /* main() */

/*************************************************************** CheckFile */
static void CheckFile(FILE *infile)
{
   char line[256], *request;
   unsigned int data;
   int status, sdata, heap, maxheap, totalalloc;
   Node *root;

   root = NULL;
   heap = maxheap = totalalloc = 0;
   for(fgets(line, 256, infile); !feof(infile); fgets(line, 256, infile))
   {
      if( (request = strstr(line, "malloc(")) != NULL )
      {
         request -= 13;
         sscanf(request + 2, "%x", &data);
         sdata = atoi(request + 20);
         status = InsertNode(&root, data, sdata);
         if( status == 0 )
         {
            printf("FAIL: %s", request);
         }
         else if( status < 0 )
         {
            puts("Out of memory.");
            DeleteTree(&root);
            return;
         }
         printf("heap =%10d\r", heap += sdata);
         totalalloc += sdata;
         if( heap > maxheap )
            maxheap = heap;
      }
      else if( (request = strstr(line, "free(")) != NULL )
      {
         sscanf(request + 7, "%x", &data);
         if( (sdata = DeleteNode(&root, data)) == 0 )
            printf("FAIL: %s", request);
         printf("heap =%10d\r", heap -= sdata);
      }
   }

   if( root != NULL )
   {
      TraverseTree(root);
      DeleteTree(&root);
      printf("heap = %d\n", heap);
   }
   else
   {
      puts("No memory leaks.");
   }
   printf("total allocated = %d\nmax heap = %d\n", totalalloc, maxheap);

} /* CheckFile() */

/************************************************************** DeleteNode */
static int DeleteNode(Node **root, unsigned int data)
{
   Node *cursor, *parent, *subtree;
   int sdata;

   /* Check for key not found */
   if( *root == NULL )
      return 0;

   /* Delete key */
   if( data == (*root)->data )
   {
      sdata = (*root)->sdata;
      if( (*root)->left == NULL || (*root)->right == NULL )
      {
         /* One branch is empty, shift other branch to root */
         subtree = (((*root)->left) == NULL)
            ? (*root)->right : (*root)->left;
         free(*root);
         *root = subtree;

         /* Success */
         return sdata;
      }
      else
      {
         /* Node contains two children, replace root with
            leftmost node in right subtree                  */
         parent = NULL;
         cursor = (*root)->right;
         while( cursor->left != NULL )
         {
            parent = cursor;
            cursor = cursor->left;
         }
         if( parent == NULL )
         {
            cursor->left = (*root)->left;
            *root = cursor;
         }
         else
         {
            parent->left = cursor->right;
            cursor->left = (*root)->left;
            cursor->right = (*root)->right;
            *root = cursor;
         }

         /* Success */
         return sdata;
      }
   }

   return (data < (*root)->data)
      ?  DeleteNode(&((*root)->left), data)
      :  DeleteNode(&((*root)->right), data);

} /* DeleteNode() */

/************************************************************** DeleteTree */
static void DeleteTree(Node **root)
{
   if( *root == NULL )
      return;
   DeleteTree( &((*root)->left) );
   DeleteTree( &((*root)->right) );
   free(*root);
   *root = NULL;

} /* DeleteTree() */

/************************************************************** InsertNode */
static int InsertNode(Node **root, unsigned int data, int sdata)
{
   /* Check for empty tree */
   if( *root == NULL )
   {
      if( (*root = (Node*)malloc(sizeof(Node))) == NULL )
         return -1;     /* Out of memory */

      (*root)->left = (*root)->right = NULL;
      (*root)->data = data;
      (*root)->sdata = sdata;
      return sdata;         /* Success */
   }

   /* Check for duplicates */
   if( data == (*root)->data )
      return 0;

   /* Insert leaf */
   return (data < (*root)->data)
      ?  InsertNode(&((*root)->left), data, sdata)
      :  InsertNode(&((*root)->right), data, sdata);

} /* InsertNode() */

/************************************************************ TraverseTree */
static void TraverseTree(Node *root)
{
   if( root == NULL )
      return;

   TraverseTree(root->left);
   printf("Memory leak: 0x%08x\n", root->data);
   TraverseTree(root->right);

} /* TraverseTree() */