bintree.c

   1 #include <string.h>
   2 #include <stdlib.h>
   3 #include "bintree.h"
   4
   5 typedef struct
   6 {
   7         BintreeTraversionFunction func;
   8         void *arg;
   9 } BintreeFreeData;
  10
  11 static int bintree_compare_mem(void *v1, void *v2, Bintree *tree)
  12 {
  13         return memcmp(v1, v2, tree->key_size);
  14 }
  15
  16 Bintree bintree_create(size_t key_size, BintreeComparator cmp)
  17 {
  18         return (Bintree) {
  19                 .root = NULL,
  20                 .key_size = key_size,
  21                 .cmp = cmp ? cmp : &bintree_compare_mem,
  22         };
  23 }
  24
  25 static BintreeNode **search_recursive(Bintree *tree, BintreeNode **nodeptr, void *key, bool return_existing)
  26 {
  27         if (*nodeptr) {
  28                 int cond;
  29
  30                 if ((cond = tree->cmp((*nodeptr)->key, key, tree)) == 0 && return_existing)
  31                         return nodeptr;
  32                 else if (cond > 0)
  33                         return search_recursive(tree, &(*nodeptr)->left, key, return_existing);
  34                 else
  35                         return search_recursive(tree, &(*nodeptr)->right, key, return_existing);
  36         } else {
  37                 return nodeptr;
  38         }
  39 }
  40
  41 BintreeNode **bintree_search(Bintree *tree, void *key)
  42 {
  43         return search_recursive(tree, &tree->root, key, true);
  44 }
  45
  46 void bintree_add_node(Bintree *tree, BintreeNode **nodeptr, void *key, void *value)
  47 {
  48         *nodeptr = malloc(sizeof(BintreeNode));
  49         (*nodeptr)->key = malloc(tree->key_size);
  50         memcpy((*nodeptr)->key, key, tree->key_size);
  51         (*nodeptr)->value = value;
  52         (*nodeptr)->left = (*nodeptr)->right = NULL;
  53 }
  54
  55 void bintree_insert(Bintree *tree, void *key, void *value)
  56 {
  57         bintree_add_node(tree, search_recursive(tree, &tree->root, key, false), key, value);
  58 }
  59
  60 static void bintree_free(BintreeNode *node, void *arg)
  61 {
  62         BintreeFreeData *fdata = arg;
  63
  64         if (fdata->func)
  65                 fdata->func(node, fdata->arg);
  66
  67         free(node->key);
  68         free(node);
  69 }
  70
  71 void bintree_clear(Bintree *tree, BintreeTraversionFunction func, void *arg)
  72 {
  73         if (tree) {
  74                 BintreeFreeData fdata = {
  75                         .func = func,
  76                         .arg = arg,
  77                 };
  78
  79                 bintree_traverse(tree, BTT_POSTORDER, &bintree_free, &fdata);
  80                 tree->root = NULL;
  81         }
  82 }
  83
  84 static void traverse_recursive(BintreeNode *node, BintreeTraversion traversion, BintreeTraversionFunction func, void *arg)
  85 {
  86         if (node) {
  87                 if (traversion == BTT_PREORDER)
  88                         func(node, arg);
  89
  90                 traverse_recursive(node->left, traversion, func, arg);
  91
  92                 if (traversion == BTT_INORDER)
  93                         func(node, arg);
  94
  95                 traverse_recursive(node->right, traversion, func, arg);
  96
  97                 if (traversion == BTT_POSTORDER)
  98                         func(node, arg);
  99         }
 100 }
 101
 102 void bintree_traverse(Bintree *tree, BintreeTraversion traversion, BintreeTraversionFunction func, void *arg)
 103 {
 104         traverse_recursive(tree->root, traversion, func, arg);
 105 }