bintree.c

   1 #include <string.h>
   2 #include <stdlib.h>
   3 #include "bintree.h"
   4
   5 Bintree bintree_create(size_t key_size)
   6 {
   7         return (Bintree) {
   8                 .root = NULL,
   9                 .key_size = key_size,
  10         };
  11 }
  12
  13 static BintreeNode **search_recursive(Bintree *tree, BintreeNode **nodeptr, void *key)
  14 {
  15         if (*nodeptr) {
  16                 int cond;
  17
  18                 if ((cond = memcmp((*nodeptr)->key, key, tree->key_size)) == 0)
  19                         return nodeptr;
  20                 else if (cond > 0)
  21                         return search_recursive(tree, &(*nodeptr)->left, key);
  22                 else
  23                         return search_recursive(tree, &(*nodeptr)->right, key);
  24         } else {
  25                 return nodeptr;
  26         }
  27 }
  28
  29 BintreeNode **bintree_search(Bintree *tree, void *key)
  30 {
  31         return search_recursive(tree, &tree->root, key);
  32 }
  33
  34 void bintree_add_node(Bintree *tree, BintreeNode **nodeptr, void *key, void *value)
  35 {
  36         *nodeptr = malloc(sizeof(BintreeNode));
  37         (*nodeptr)->key = malloc(tree->key_size);
  38         memcpy((*nodeptr)->key, key, tree->key_size);
  39         (*nodeptr)->value = value;
  40         (*nodeptr)->left = (*nodeptr)->right = NULL;
  41 }
  42
  43 static void free_recursive(BintreeNode *node, BintreeFreeFunction func, void *arg)
  44 {
  45         if (node) {
  46                 free_recursive(node->left, func, arg);
  47                 free_recursive(node->right, func, arg);
  48                 free(node->key);
  49                 if (func)
  50                         func(node->value, arg);
  51                 free(node);
  52         }
  53 }
  54
  55 void bintree_clear(Bintree *tree, BintreeFreeFunction func, void *arg)
  56 {
  57         if (tree) {
  58                 free_recursive(tree->root, func, arg);
  59                 tree->root = NULL;
  60         }
  61 }