Back to index

im-sdk  12.3.91
Functions
tree.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "hhentry.h"
#include "tree.h"

Go to the source code of this file.

Functions

static TreeNode * _tree_search_hangul (TreeNode *node, unsigned char *hangul)
static void tree_init (Tree *tree)
Treetree_new ()
Treetree_n_new (int n)
void tree_inorder_traverse (TreeNode *node, void *(*func)(void *))
int tree_compare_hangul (TreeNode *a, unsigned char *b)
TreeNode * tree_search_hangul (Tree *tree, unsigned char *hangul)
static void _tree_clear (TreeNode *node)
void tree_clear (Tree *tree)
void tree_print (Tree *tree, void *(*print_function)(void *))
void tree_shallow_insert (Tree *tree, TreeNode *tnode)
void tree_node_copy (TreeNode *dst, TreeNode *src)
void tree_insert (Tree *tree, TreeNode *tnode)
void tree_build_from_array (Tree *tree, TreeNode *data, int first, int last)
TreeNode * tree_node_new_skeleton ()
TreeNode * tree_node_new_with_hhitem (HHItem *data)
void tree_node_free (TreeNode *tnode)

Function Documentation

static void _tree_clear ( TreeNode *  node) [static]

Definition at line 102 of file tree.c.

{
  if (node){
    _tree_clear (node->right);
    _tree_clear (node->left);
    node->right = NULL;
    node->left = NULL; 
    hhitem_free (node->data);
    node->data = NULL;
    free (node);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static TreeNode* _tree_search_hangul ( TreeNode *  node,
unsigned char *  hangul 
) [static]
void tree_build_from_array ( Tree tree,
TreeNode *  data,
int  first,
int  last 
)

Definition at line 233 of file tree.c.

{
  int middle;
  if (first <= last){
    middle = (first + last) / 2;
    tree_shallow_insert (tree, data + middle);
    tree_build_from_array (tree, data, first, middle - 1);
    tree_build_from_array (tree, data, middle + 1, last);
  }
    
}

Here is the call graph for this function:

void tree_clear ( Tree tree)

Definition at line 116 of file tree.c.

{
  _tree_clear (tree->root);
}

Here is the call graph for this function:

Here is the caller graph for this function:

int tree_compare_hangul ( TreeNode *  a,
unsigned char *  b 
)

Definition at line 70 of file tree.c.

{
  return  strcmp (a->data->hangul, b);
}
static void tree_init ( Tree tree) [static]
void tree_inorder_traverse ( TreeNode *  node,
void *(*)(void *)  func 
)

Definition at line 60 of file tree.c.

{
  if (node != NULL){
    tree_inorder_traverse (node->left, func);
    func ((void *)node->data);
    tree_inorder_traverse (node->right, func);
  }
}

Here is the call graph for this function:

void tree_insert ( Tree tree,
TreeNode *  tnode 
)

Definition at line 193 of file tree.c.

{
  TreeNode *ptr = tree->root ;
  TreeNode *prev;
  int comp_return;

  assert (tree != NULL);
  assert (tnode != NULL);

  if (tree == NULL || tnode == NULL){
    fprintf (stderr, "wrong parameter passed\n");
    exit (-1);
  }
  if (!ptr){
    tree->root = tnode;
    return;
  }

  while (ptr){
    prev = ptr;
    comp_return = hhitem_comp (ptr->data, tnode->data);
    if (comp_return < 0)
      ptr = ptr->left;
    else if (comp_return >0)
      ptr = ptr->right;
    else {
      /* no duplication expected, just return */
      return;
    }
  }
  if (hhitem_comp (prev->data, tnode->data) < 0)
    prev->left = tnode;
  else
    prev->right = tnode;
  
}

Here is the call graph for this function:

Here is the caller graph for this function:

Tree* tree_n_new ( int  n)

Definition at line 23 of file tree.c.

{
  Tree *trees;
  int i;

  if (!n)
    return NULL;
  
  trees = (Tree *) calloc (n, sizeof (Tree));
  if (!trees){
    fprintf (stderr, "tree_n_new error: memory allocation error\n");
    return NULL;
  }

  for (i = 0 ; i < n; i++){
    trees[i].root = NULL;
  }

  return trees;
}

Here is the caller graph for this function:

Tree* tree_new ( )

Definition at line 14 of file tree.c.

{
  Tree *new_tree;
  new_tree = (Tree *) calloc (1, sizeof (Tree));
  new_tree->root = NULL;
  return new_tree;
}
void tree_node_copy ( TreeNode *  dst,
TreeNode *  src 
)

Definition at line 176 of file tree.c.

{
  assert (dst != NULL);
  assert (src != NULL);

  if (dst == NULL || src == NULL){
    fprintf (stderr, "tree_node_copy error: dst or src is NULL\n");
    return;
  }

  dst->left = src->left;
  dst->right = src->right;
  if (dst->data && src->data)
    hhitem_copy (dst->data, src->data);
}

Here is the call graph for this function:

void tree_node_free ( TreeNode *  tnode)

Definition at line 277 of file tree.c.

{
  assert (tnode != NULL);
  if (!tnode)
    return;
  if (tnode->data){
    tnode->left = NULL;
    tnode->right = NULL;
    hhitem_free (tnode->data);
    tnode->data = NULL;
    free (tnode);
  }
}

Here is the call graph for this function:

TreeNode* tree_node_new_skeleton ( )

Definition at line 247 of file tree.c.

{
  TreeNode *new_node;
  new_node = (TreeNode *)calloc (1, sizeof (TreeNode));
  if (!new_node){
    fprintf (stderr, "tree_node_new_skeleton error: "
            "memory allocation failure\n");
    return NULL;
  }
  new_node->left = new_node->right = NULL;
  new_node->data = NULL;
  return new_node;
}
TreeNode* tree_node_new_with_hhitem ( HHItem data)

Definition at line 262 of file tree.c.

{
  TreeNode *p_newnode =
    (TreeNode *) calloc (1, sizeof (TreeNode));
  
  p_newnode->left = NULL;
  p_newnode->right = NULL;
  
  p_newnode->data = hhitem_new ();
  hhitem_copy (p_newnode->data, data);

  return p_newnode;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void tree_print ( Tree tree,
void *(*)(void *)  print_function 
)

Definition at line 122 of file tree.c.

{
  TreeNode *root = tree->root;
  tree_inorder_traverse (root, print_function);
}

Here is the call graph for this function:

TreeNode* tree_search_hangul ( Tree tree,
unsigned char *  hangul 
)

Definition at line 76 of file tree.c.

{
  TreeNode *ret_node = NULL;
  ret_node = _tree_search_hangul (tree->root, hangul);
  return ret_node;
}

Here is the call graph for this function:

void tree_shallow_insert ( Tree tree,
TreeNode *  tnode 
)

Definition at line 136 of file tree.c.

{
  TreeNode *ptr = tree->root ;
  TreeNode *prev;
  
  int comp_return;

  assert (tree != NULL);
  assert (tnode != NULL);

  if (tree == NULL || tnode == NULL){
    fprintf (stderr, "wrong parameter passed\n");
    exit (-1);
  }
  if (!ptr){
    tree->root = tnode;
    return;
  }

  while (ptr){
    prev = ptr;
    comp_return = hhitem_comp (ptr->data, tnode->data);
    if (comp_return < 0)
      ptr = ptr->left;
    else if (comp_return >0)
      ptr = ptr->right;
    else {
      /* no duplication expected, just return */
      return;
    }
  }
  if (hhitem_comp (prev->data, tnode->data) < 0)
    prev->left = tnode;
  else
    prev->right = tnode;
  
}

Here is the call graph for this function: