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(void *key, struct tree_node **rootp,
  15                               int (*compare)(const void *, const void *),
  16                               int insert)
  17 {
  18         int res;
  19         if (!*rootp) {
  20                 if (!insert) {
  21                         return NULL;
  22                 } else {
  23                         struct tree_node *n =
  24                                 reftable_calloc(sizeof(struct tree_node));
  25                         n->key = key;
  26                         *rootp = n;
  27                         return *rootp;
  28                 }
  29         }
  30
  31         res = compare(key, (*rootp)->key);
  32         if (res < 0)
  33                 return tree_search(key, &(*rootp)->left, compare, insert);
  34         else if (res > 0)
  35                 return tree_search(key, &(*rootp)->right, compare, insert);
  36         return *rootp;
  37 }
  38
  39 void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key),
  40                 void *arg)
  41 {
  42         if (t->left) {
  43                 infix_walk(t->left, action, arg);
  44         }
  45         action(arg, t->key);
  46         if (t->right) {
  47                 infix_walk(t->right, action, arg);
  48         }
  49 }
  50
  51 void tree_free(struct tree_node *t)
  52 {
  53         if (!t) {
  54                 return;
  55         }
  56         if (t->left) {
  57                 tree_free(t->left);
  58         }
  59         if (t->right) {
  60                 tree_free(t->right);
  61         }
  62         reftable_free(t);
  63 }