1 /* SPDX-License-Identifier: LGPL-2.1 */ 2 /* 3 * Copyright (C) 2023 Google, Steven Rostedt <rostedt@goodmis.org> 4 * 5 */ 6 #ifndef _TRACE_RBTREE_H 7 #define _TRACE_RBTREE_H 8 9 struct trace_rbtree_node { 10 struct trace_rbtree_node *parent; 11 struct trace_rbtree_node *left; 12 struct trace_rbtree_node *right; 13 int color; 14 }; 15 16 typedef int (*trace_rbtree_cmp_fn)(const struct trace_rbtree_node *A, const struct trace_rbtree_node *B); 17 18 typedef int (*trace_rbtree_search_fn)(const struct trace_rbtree_node *n, const void *data); 19 20 struct trace_rbtree { 21 struct trace_rbtree_node *node; 22 trace_rbtree_search_fn search; 23 trace_rbtree_cmp_fn cmp; 24 size_t nr_nodes; 25 }; 26 27 void trace_rbtree_init(struct trace_rbtree *tree, trace_rbtree_cmp_fn cmp_fn, 28 trace_rbtree_search_fn search_fn); 29 struct trace_rbtree_node *trace_rbtree_find(struct trace_rbtree *tree, const void *data); 30 void trace_rbtree_delete(struct trace_rbtree *tree, struct trace_rbtree_node *node); 31 int trace_rbtree_insert(struct trace_rbtree *tree, struct trace_rbtree_node *node); 32 struct trace_rbtree_node *trace_rbtree_pop_nobalance(struct trace_rbtree *tree); 33 34 #endif /* _TRACE_RBTREE_H */ 35