bintree.c

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