4
\$\begingroup\$

I wrote a BST in C a while back and may use it at some point.

 search_tree tree_make_empty( search_tree tree )
 {
   if ( tree != NULL )
   {
       tree_make_empty( tree->left );
       tree_make_empty( tree->right );
       free( tree );
   }
   return NULL;
 }

 tree_position tree_find( CHAR_DATA *target, search_tree tree )
 {
     if ( tree == NULL )
       return NULL;

     if ( target < tree->hatedata->target_char )
       return tree_find( target, tree->left );
     else if ( target > tree->hatedata->target_char )
       return tree_find( target, tree->right );
     else
       return tree;
 }

 search_tree tree_insert( HATE_DATA *hatedata, search_tree tree )
 {
     if ( tree == NULL )
     {
       tree = (HATE_NODE * ) malloc( sizeof( HATE_NODE ) );

       if ( tree == NULL )
          bug( "tree_insert: out of space!" );
       else
       {
          tree->hatedata = hatedata;
          tree->left = tree->right = NULL;
       }
     }
     else if ( hatedata->target_char < tree->hatedata->target_char )
       tree->left = tree_insert( hatedata, tree->left );
     else if ( hatedata->target_char > tree->hatedata->target_char )
          tree->right = tree_insert( hatedata, tree->right );

     return tree;
 }

 tree_position tree_find_min( search_tree tree )
 {
    if ( tree == NULL )
       return NULL;
    else if ( tree->left == NULL )
       return tree;
    else
       return tree_find_min( tree->left );
 }

 search_tree tree_delete( HATE_DATA *hatedata, search_tree tree )
 {
    tree_position pos;

    if ( tree == NULL )
       bug( "tree_delete: not found" );
    else if ( hatedata->target_char < tree->hatedata->target_char )
       tree->left = tree_delete( hatedata, tree->left );
    else if ( hatedata->target_char > tree->hatedata->target_char )
         tree->right = tree_delete( hatedata, tree->right );
    else if ( tree->left && tree->right )
    {
       pos = tree_find_min( tree->right );
       tree->hatedata = pos->hatedata;
       tree->right = tree_delete( tree->hatedata, tree->right );
    }
    else
    {
       pos = tree;
       if ( tree->left == NULL )
         tree = tree->right;
       else if ( tree->right == NULL )
         tree = tree->left;
       free( pos );
    }

    return tree;
 }

 HATE_DATA *tree_retrieve( tree_position pos )
 {
    return pos->hatedata;
 }

...

 struct hate_data
 {
    CHAR_DATA *target_char;
    int hate_amount;
 };

 struct hate_node
 {
    HATE_DATA *hatedata;
    search_tree left;
    search_tree right;
 };

...

mob->hatedata = tree_make_empty( NULL );

Example use:

if ( IS_NPC(victim) )
{
     HATE_DATA *hatedata;
   tree_position P;

   if( ( P = tree_find( ch, victim->hatedata )) == NULL || tree_retrieve( P )->target_char != ch )
   {
     int test;
     hatedata = (HATE_DATA * ) malloc( sizeof( HATE_DATA ) );
     hatedata->target_char = ch;
     test = number_range( 1, 50 );
     hatedata->hate_amount = test;
     victim->hatedata = tree_insert( hatedata, victim->hatedata );
     ch_printf( ch, "It should now hate you for %d.\n\r", test );
   }
   else
   {
     hatedata = tree_retrieve(tree_find( ch, victim->hatedata ));
     ch_printf(ch, "You are already hated for %d!\n\r", hatedata->hate_amount );
   }

}

Do you have any suggestions? Does it look okay? Are there any ways to optimize it?

\$\endgroup\$
2
  • \$\begingroup\$ I would say it is not going to work (if CHAR_DATA* is a string). You are comparing pointers. So unless all the data is static the comparisons using < and > are meaningless. \$\endgroup\$ Commented Jan 28, 2011 at 7:44
  • \$\begingroup\$ It's a pointer to a struct. \$\endgroup\$
    – Zeno
    Commented Jan 28, 2011 at 18:19

3 Answers 3

6
\$\begingroup\$

In tree_find and tree_find_min [edit: and even in tree_insert] you're not really gaining anything from using recursion. For example, I think tree_find_min would probably be clearer something like:

tree_position tree_find_min( search_tree tree )
{
   if ( tree == NULL )
      return NULL;
   while (tree->left != NULL)
       tree = tree->left;
   return tree;
}

As a side-benefit, this may also be faster with some compilers. In code like:

 HATE_DATA *hatedata;

 /* ... */

 hatedata = (HATE_DATA * ) malloc( sizeof( HATE_DATA ) );

I'd change it to look more like:

 hatedata = malloc(sizeof(*hatedata));

The cast accomplishes nothing useful in C, and can cover up the bug of forgetting to #include <stdlib.h> to get the proper prototype for malloc. Using sizeof(*hatedata) instead of sizeof(HATE_DATA) means that changing the type only requires changing it in one place (where you've defined the variable), instead of everywhere you've done an allocation.

\$\endgroup\$
1
  • \$\begingroup\$ +1 a) True for not gaining much, but recursion vs iteration readability is sometimes just matter of taste. So I believe it is subjective. I believe that more skilled programmer will recognize the pattern. b) what You did to malloc is good, it hides the type which can change ... one can make macro out of it then \$\endgroup\$
    – user712092
    Commented Sep 13, 2011 at 13:14
2
\$\begingroup\$

Using the comparison than operators < and > on pointers seems a bit redundant.

Depending on how the heap is working you may end up with a tree that looks like a list.
Without understand the properties of HATE_DATA it is imposable to know if this is a good or even valuable usage of theses operators.

If the data inside the pointer target_char has some intrinsic property that would allow you to do a more meaningful comparison then you can define/use a function to do the comparison or you can document the properties of HATE_DATA that make using these operators meaningful in this context.

\$\endgroup\$
2
\$\begingroup\$

An even better way to do the malloc is with this macro (simplified version of g_new in GLib):

#define my_new(type, count)  ((type*)malloc (sizeof (type) * (count)))

The advantages of this are:

  • less typing, more clarity
  • assignment to the wrong type will be a compiler warning
  • you can't accidentally sizeof() the wrong thing

Also, of course, malloc can return NULL. The easiest way to deal with that is to make a wrapper function that handles it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.