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_ARRAY(n, 1);
  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         action(arg, t->key);
  45         if (t->right)
  46                 infix_walk(t->right, action, arg);
  47 }
  48
  49 void tree_free(struct tree_node *t)
  50 {
  51         if (!t)
  52                 return;
  53         if (t->left)
  54                 tree_free(t->left);
  55         if (t->right)
  56                 tree_free(t->right);
  57         reftable_free(t);
  58 }