[thirdparty/git.git] / reftable / tree.h

/*
Copyright 2020 Google LLC

Use of this source code is governed by a BSD-style
license that can be found in the LICENSE file or at
https://developers.google.com/open-source/licenses/bsd
*/

#ifndef TREE_H
#define TREE_H

/* tree_node is a generic binary search tree. */
struct tree_node {
	void *key;
	struct tree_node *left, *right;
};

/* looks for `key` in `rootp` using `compare` as comparison function. If insert
 * is set, insert the key if it's not found. Else, return NULL.
 */
struct tree_node *tree_search(void *key, struct tree_node **rootp,
			      int (*compare)(const void *, const void *),
			      int insert);

/* performs an infix walk of the tree. */
void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key),
		void *arg);

/*
 * deallocates the tree nodes recursively. Keys should be deallocated separately
 * by walking over the tree. */
void tree_free(struct tree_node *t);

#endif
Commit	Line	Data
35425d10 HWN	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	/* looks for `key` in `rootp` using `compare` as comparison function. If insert
	19	* is set, insert the key if it's not found. Else, return NULL.
	20	*/
	21	struct tree_node tree_search(void key, struct tree_node **rootp,
	22	int (compare)(const void , const void *),
	23	int insert);
	24
	25	/* performs an infix walk of the tree. */
	26	void infix_walk(struct tree_node t, void (action)(void arg, void key),
	27	void *arg);
	28
	29	/*
	30	* deallocates the tree nodes recursively. Keys should be deallocated separately
	31	* by walking over the tree. */
	32	void tree_free(struct tree_node *t);
	33
	34	#endif