| 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 |