tree.c File Reference

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "defines.h"
#include "tree.h"
#include "util.h"

Functions
tnode *	tree_add (const char *key, const char *value, bool override, tnode **root)
	Adds specified key/value pair to tree as a node.
tnode *	tree_find (const char *key, tnode *root)
	Returns pointer to tree node that matches specified key.
void	tree_remove (const char *key, tnode **root)
	Removes specified tree node from tree.
void	tree_dealloc (tnode *root)
	Deallocates entire tree from memory.

---

Detailed Description

Author:

Trevor Williams (phase1geo@gmail.com)

Date:

1/4/2003

---

Function Documentation

tnode* tree_add	(	const char *	key,
		const char *	value,
		bool	override,
		tnode **	root
	)

Adds specified key/value pair to tree as a node.

Returns:

Returns pointer to newly created tree node.

Creates new node for this pairing and adds it to the binary tree for quick lookup.

Parameters:

	key	String containing search key for node retrieval
	value	Value associated with this node
	override	If TRUE, causes new value to overwrite old value if match found
	root	Pointer to root of tree to add to

References FALSE, free_safe, tnode_s::left, malloc_safe, tnode_s::name, PROFILE, PROFILE_END, tnode_s::right, strdup_safe, TRUE, tnode_s::up, and tnode_s::value.

Referenced by obfuscate_name().

  { PROFILE(TREE_ADD);
  
  tnode* node;            /* Pointer to newly created tree node */
  tnode* curr   = *root;  /* Pointer to current node */
  bool   placed = FALSE;  /* Sets to TRUE when node is placed in tree */
  int    comp;            /* Specifies compare value for string comparison */

  /* Allocate memory for tree node and populate */
  node        = (tnode*)malloc_safe( sizeof( tnode ) );
  node->name  = strdup_safe( key );
  node->value = strdup_safe( value );
  node->left  = NULL;
  node->right = NULL;
  node->up    = NULL;

  /* Add node to tree */
  if( *root == NULL ) {
    *root = node;
  } else {
    while( !placed ) {
      comp = strcmp( node->name, curr->name );
      if( comp == 0 ) {

        /* Match found, replace value with new value */
        if( override ) {
          free_safe( curr->value, (strlen( curr->value ) + 1) );
          curr->value = node->value;
        } else {
          free_safe( node->value, (strlen( node->value ) + 1) );
          node->value = NULL;
        }

        free_safe( node->name, (strlen( node->name ) + 1) );
        free_safe( node, sizeof( tnode ) );
        node   = curr;
        placed = TRUE;

      } else if( comp < 0 ) {

        if( curr->left == NULL ) {
          curr->left = node;
          node->up   = curr;
          placed     = TRUE;
        } else {
          curr = curr->left;
        }

      } else {
        
        if( curr->right == NULL ) {
          curr->right = node;
          node->up    = curr;
          placed      = TRUE;
        } else {
          curr        = curr->right;
        }

      }
    }
  }

  PROFILE_END;

  return( node );

}

void tree_dealloc

(

tnode *

root

)

Deallocates entire tree from memory.

Recursively traverses specified tree, deallocating all memory associated with that tree.

Parameters:

root

Pointer to root of tree to deallocate

References free_safe, tnode_s::left, tnode_s::name, PROFILE, PROFILE_END, tnode_s::right, tree_dealloc(), and tnode_s::value.

Referenced by db_close(), obfuscate_dealloc(), and tree_dealloc().

  { PROFILE(TREE_DEALLOC);
  
  if( root != NULL ) {
    
    if( root->left != NULL ) {
      tree_dealloc( root->left );
    }
    
    if( root->right != NULL ) {
      tree_dealloc( root->right );
    }
    
    free_safe( root->name, (strlen( root->name ) + 1) );
    free_safe( root->value, (strlen( root->value ) + 1) );
    free_safe( root, sizeof( tnode ) );
    
  }

  PROFILE_END;
  
}

tnode* tree_find	(	const char *	key,
		tnode *	root
	)

Returns pointer to tree node that matches specified key.

Returns:

Returns pointer to found node or NULL if not found.

Searches binary tree for key that matches the specified name parameter. If found, a pointer to the node is returned; otherwise, the value of NULL is returned.

Parameters:

	key	Key value to search for in tree
	root	Pointer to root of binary tree to search

References tnode_s::left, tnode_s::name, PROFILE, PROFILE_END, and tnode_s::right.

Referenced by obfuscate_name(), and tree_remove().

  { PROFILE(TREE_FIND);

  int comp;  /* Value of string comparison */

  while( (root != NULL) && ((comp = strcmp( key, root->name )) != 0) ) {
    if( comp < 0 ) {
      root = root->left;
    } else {
      root = root->right;
    }
  }

  PROFILE_END;

  return( root );

}

void tree_remove	(	const char *	key,
		tnode **	root
	)

Removes specified tree node from tree.

Looks up the specified node (based on key value) and removes it from the tree in such a was as to keep the integrity of the tree in check for continual quick searching.

Parameters:

	key	Key to search for and remove from tree
	root	Pointer to root of tree to search

References free_safe, tnode_s::left, tnode_s::name, PROFILE, PROFILE_END, tnode_s::right, tree_find(), tnode_s::up, and tnode_s::value.

  { PROFILE(TREE_REMOVE);
  
  tnode* node;  /* Pointer to found tree node to remove */
  tnode* tail;  /* Temporary pointer to tail node */
  
  /* Find undefined identifer string in table */
  node = tree_find( key, *root );

  /* If node is found, restitch the define tree. */
  if( node != NULL ) {

    /* If we are the root node in the tree */
    if( node->up == NULL ) {

      /* If we have no children */
      if( (node->left == NULL) && (node->right == NULL) ) {

        *root = NULL;

      } else if( node->left == NULL ) {

        *root = node->right;
        if( node->right ) {
          node->right->up = NULL;
        }

      } else if( node->right == NULL ) {

        assert( node->left != NULL );
        *root       = node->left;
        (*root)->up = NULL;

      } else {

        tail = node->left;
        while( tail->right ) {
          tail = tail->right;
        }

        tail->right     = node->right;
        tail->right->up = tail;
        *root           = node->left;
        (*root)->up     = NULL;

      }

    } else if( node->left == NULL ) {

      if( node->up->left == node ) {

        node->up->left = node->right;

      } else {

        assert( node->up->right == node );
        node->up->right = node->right;

      }

      if( node->right ) {
        node->right->up = node->up;
      }

    } else if( node->right == NULL ) {

      assert( node->left != NULL );

      if( node->up->left == node ) {

        node->up->left = node->left;

      } else {

        assert( node->up->right == node );
        node->up->right = node->left;

      }

      node->left->up = node->up;

    } else {

      tail = node->left;
      assert( (node->left != NULL) && (node->right != NULL) );

      while( tail->right ) {
        tail = tail->right;
      }

      tail->right     = node->right;
      tail->right->up = tail;

      if( node->up->left == node ) {

        node->up->left = node->left;

      } else {

        assert( node->up->right == node );
        node->up->right = node->left;

      }

      node->left->up = node->up;

    }

    free_safe( node->name, (strlen( node->name ) + 1) );
    free_safe( node->value, (strlen( node->value ) + 1) );
    free_safe( node, sizeof( tnode ) );

  }

  PROFILE_END;
  
}