btree

a balk tree implementation ;-)
Log | Files | Refs | LICENSE

btree.c (1626B)

      1 /**
      2  * btree -- a balk tree implementation ;-)
      3  * Copyright 2020, 2021 Matthias Balk
      4  */
      5 
      6 #include <stdio.h>
      7 #include <stdlib.h>
      8 #include <string.h>
      9 
     10 #include "btree.h"
     11 
     12 
     13 u_int8_t bt_contains(node_t *tree, const char *data)
     14 {
     15   int cmp = strcmp(data, tree->data);
     16   if (cmp == 0)
     17     return 1;
     18 
     19   if (cmp > 0)
     20     return tree->rchild ? bt_contains(tree->rchild, data) : 0;
     21   else
     22     return tree->lchild ? bt_contains(tree->lchild, data) : 0;
     23 }
     24 
     25 
     26 node_t* bt_new()
     27 {
     28   node_t *tree = (node_t*) malloc(sizeof(node_t));
     29   if (tree == NULL)
     30     return NULL;
     31 
     32   bzero(tree, sizeof(node_t));
     33 
     34   return tree;
     35 }
     36 
     37 
     38 void bt_free(node_t *tree, u_int8_t free_data)
     39 {
     40   if (tree->lchild != NULL)
     41   {
     42     bt_free(tree->lchild, free_data);
     43   }
     44 
     45   if (tree->rchild != NULL)
     46   {
     47     bt_free(tree->rchild, free_data);
     48   }
     49 
     50   if (free_data) free(tree->data);
     51   free(tree);
     52 }
     53 
     54 
     55 u_int8_t bt_add(node_t *tree, char *data)
     56 {
     57   if (tree->data == NULL)
     58   {
     59     tree->data = data;
     60     return 1;
     61   }
     62 
     63   int cmp = strcmp(data, tree->data);
     64 
     65   if (cmp == 0)
     66     return 0;
     67 
     68   if (cmp > 0)
     69   {
     70     if (tree->rchild == NULL)
     71     {
     72       if ((tree->rchild = bt_new()) == NULL)
     73         exit(EXIT_FAILURE);  /* TODO: proper shutdown */
     74     }
     75     return bt_add(tree->rchild, data);
     76   }
     77   else
     78   {
     79     if (tree->lchild == NULL)
     80     {
     81       if ((tree->lchild = bt_new()) == NULL)
     82         exit(EXIT_FAILURE);  /* TODO: proper shutdown */
     83     }
     84     return bt_add(tree->lchild, data);
     85   }
     86 }
     87 
     88 
     89 void bt_print_sorted(const node_t *tree)
     90 {
     91   if (tree == NULL)
     92     return;
     93 
     94   bt_print_sorted(tree->lchild);
     95   printf("%s\n", tree->data);
     96   bt_print_sorted(tree->rchild);
     97 }