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)
  26 {
  27         if (*nodeptr) {
  28                 int cond;
  29
  30                 if ((cond = tree->cmp((*nodeptr)->key, key, tree)) == 0)
  31                         return nodeptr;
  32                 else if (cond > 0)
  33                         return search_recursive(tree, &(*nodeptr)->left, key);
  34                 else
  35                         return search_recursive(tree, &(*nodeptr)->right, key);
  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);
  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 static void bintree_free(BintreeNode *node, void *arg)
  56 {
  57         BintreeFreeData *fdata = arg;
  58
  59         if (fdata->func)
  60                 fdata->func(node, fdata->arg);
  61
  62         free(node->key);
  63         free(node);
  64 }
  65
  66 void bintree_clear(Bintree *tree, BintreeTraversionFunction func, void *arg)
  67 {
  68         if (tree) {
  69                 BintreeFreeData fdata = {
  70                         .func = func,
  71                         .arg = arg,
  72                 };
  73
  74                 bintree_traverse(tree, BTT_POSTORDER, &bintree_free, &fdata);
  75                 tree->root = NULL;
  76         }
  77 }
  78
  79 static void traverse_recursive(BintreeNode *node, BintreeTraversion traversion, BintreeTraversionFunction func, void *arg)
  80 {
  81         if (node) {
  82                 if (traversion == BTT_PREORDER)
  83                         func(node, arg);
  84
  85                 traverse_recursive(node->left, traversion, func, arg);
  86
  87                 if (traversion == BTT_INORDER)
  88                         func(node, arg);
  89
  90                 traverse_recursive(node->right, traversion, func, arg);
  91
  92                 if (traversion == BTT_POSTORDER)
  93                         func(node, arg);
  94         }
  95 }
  96
  97 void bintree_traverse(Bintree *tree, BintreeTraversion traversion, BintreeTraversionFunction func, void *arg)
  98 {
  99         traverse_recursive(tree->root, traversion, func, arg);
 100 }