reftable/tree.c

   1 /*
   2 Copyright 2020 Google LLC
   3
   4 Use of this source code is governed by a BSD-style
   5 license that can be found in the LICENSE file or at
   6 https://developers.google.com/open-source/licenses/bsd
   7 */
   8
   9 #include "system.h"
  10 #include "tree.h"
  11
  12 #include "basics.h"
  13
  14 struct tree_node *tree_search(struct tree_node *tree,
  15                               void *key,
  16                               int (*compare)(const void *, const void *))
  17 {
  18         int res;
  19         if (!tree)
  20                 return NULL;
  21         res = compare(key, tree->key);
  22         if (res < 0)
  23                 return tree_search(tree->left, key, compare);
  24         else if (res > 0)
  25                 return tree_search(tree->right, key, compare);
  26         return tree;
  27 }
  28
  29 struct tree_node *tree_insert(struct tree_node **rootp,
  30                               void *key,
  31                               int (*compare)(const void *, const void *))
  32 {
  33         int res;
  34
  35         if (!*rootp) {
  36                 struct tree_node *n;
  37
  38                 REFTABLE_CALLOC_ARRAY(n, 1);
  39                 if (!n)
  40                         return NULL;
  41
  42                 n->key = key;
  43                 *rootp = n;
  44                 return *rootp;
  45         }
  46
  47         res = compare(key, (*rootp)->key);
  48         if (res < 0)
  49                 return tree_insert(&(*rootp)->left, key, compare);
  50         else if (res > 0)
  51                 return tree_insert(&(*rootp)->right, key, compare);
  52         return *rootp;
  53 }
  54
  55 void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key),
  56                 void *arg)
  57 {
  58         if (t->left)
  59                 infix_walk(t->left, action, arg);
  60         action(arg, t->key);
  61         if (t->right)
  62                 infix_walk(t->right, action, arg);
  63 }
  64
  65 void tree_free(struct tree_node *t)
  66 {
  67         if (!t)
  68                 return;
  69         if (t->left)
  70                 tree_free(t->left);
  71         if (t->right)
  72                 tree_free(t->right);
  73         reftable_free(t);
  74 }