CEP/C/mod_bst.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3
   4 #include "misc.h"
   5 #include "module.h"
   6 #include "mod_bst.h"
   7
   8 struct node {
   9         void *data;
  10         struct node *left;
  11         struct node *right;
  12 };
  13
  14 struct bs_tree {
  15         int size;
  16         struct node *root;
  17         int (*compare)(const void *key1, const void *key2);
  18         void (*destroy)(void *data);
  19         void (*dump)(const void *data);
  20 };
  21
  22 static struct bs_tree cep_bs_tree;
  23
  24 static struct node *bst_node_alloc(void *data)
  25 {
  26         struct node *new;
  27
  28         new = malloc(sizeof(*new));
  29         if (!new)
  30                 fatal("Could not allocate memory");
  31
  32         new->data = data;
  33         new->left = new->right = NULL;
  34
  35         return new;
  36 }
  37
  38 static struct node *__bst_insert(void *data, struct node *node)
  39 {
  40         int cmpval;
  41
  42         if (!node)
  43                 return bst_node_alloc(data);
  44
  45         cmpval = cep_bs_tree.compare(data, node->data);
  46         if (cmpval < 0) {
  47                 /* go to the left */
  48                 node->left = __bst_insert(data, node->left);
  49         } else if (cmpval > 0) {
  50                 /* go to the right */
  51                 node->right = __bst_insert(data, node->right);
  52         }
  53
  54         /* we ignore duplicates */
  55
  56         return node;
  57 }
  58
  59 static void bst_insert(void *data)
  60 {
  61         cep_bs_tree.root = __bst_insert(data, cep_bs_tree.root);
  62         cep_bs_tree.size++;
  63 }
  64
  65 static void *lookup(const void *data, struct node *node)
  66 {
  67         void *ret;
  68         int cmpval;
  69
  70         if (!node) {
  71                 /* not found */
  72                 return NULL;
  73         }
  74
  75         cmpval = cep_bs_tree.compare(data, node->data);
  76         if (cmpval < 0) {
  77                 /* move to the left */
  78                 ret = lookup(data, node->left);
  79         } else if (cmpval > 0) {
  80                 /* move to the right */
  81                 ret = lookup(data, node->right);
  82         } else {
  83                 /* found */
  84                 ret = node->data;
  85         }
  86
  87         return ret;
  88 }
  89
  90 static void *bst_lookup(const void *data)
  91 {
  92         return lookup(data, cep_bs_tree.root);
  93 }
  94
  95 static void bst_init(int (*compare)(const void *key1, const void *key2),
  96                      void (*destroy)(void *data),
  97                      void (*dump)(const void *data))
  98
  99 {
 100         cep_bs_tree.size = 0;
 101         cep_bs_tree.root = NULL;
 102         cep_bs_tree.compare = compare;
 103         cep_bs_tree.destroy = destroy;
 104         cep_bs_tree.dump  = dump;
 105 }
 106
 107 static size_t bst_size(void)
 108 {
 109         return cep_bs_tree.size;
 110 }
 111
 112 static void destroy(struct node *node)
 113 {
 114         if (!node)
 115                 return;
 116
 117         destroy(node->left);
 118         destroy(node->right);
 119
 120         cep_bs_tree.destroy(node->data);
 121         free(node);
 122 }
 123
 124 static void bst_destroy(void)
 125 {
 126         destroy(cep_bs_tree.root);
 127 }
 128
 129 static void dump(struct node *node)
 130 {
 131         if (!node)
 132                 return;
 133
 134         dump(node->left);
 135
 136         cep_bs_tree.dump(node->data);
 137
 138         dump(node->right);
 139 }
 140
 141 static void bst_dump(void)
 142 {
 143         dump(cep_bs_tree.root);
 144 }
 145
 146 struct module bst_module = {
 147         .mod_name    = "BINARY SEARCH TREE",
 148         .mod_init    = bst_init,
 149         .mod_destroy = bst_destroy,
 150         .mod_insert  = bst_insert,
 151         .mod_lookup  = bst_lookup,
 152         .mod_dump    = bst_dump,
 153         .mod_size    = bst_size,
 154 };