bintree.c

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