reftable/tree.h

   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 #ifndef TREE_H
  10 #define TREE_H
  11
  12 /* tree_node is a generic binary search tree. */
  13 struct tree_node {
  14         void *key;
  15         struct tree_node *left, *right;
  16 };
  17
  18 /*
  19  * Search the tree for the node matching the given key using `compare` as
  20  * comparison function. Returns the node whose key matches or `NULL` in case
  21  * the key does not exist in the tree.
  22  */
  23 struct tree_node *tree_search(struct tree_node *tree,
  24                               void *key,
  25                               int (*compare)(const void *, const void *));
  26
  27 /*
  28  * Insert a node into the tree. Returns the newly inserted node if the key does
  29  * not yet exist. Otherwise it returns the preexisting node. Returns `NULL`
  30  * when allocating the new node fails.
  31  */
  32 struct tree_node *tree_insert(struct tree_node **rootp,
  33                               void *key,
  34                               int (*compare)(const void *, const void *));
  35
  36 /* performs an infix walk of the tree. */
  37 void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key),
  38                 void *arg);
  39
  40 /*
  41  * deallocates the tree nodes recursively. Keys should be deallocated separately
  42  * by walking over the tree. */
  43 void tree_free(struct tree_node *t);
  44
  45 #endif