1 /* 2 * Copyright (C) 2014 Facebook. All rights reserved. 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public 6 * License v2 as published by the Free Software Foundation. 7 * 8 * This program is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 11 * General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public 14 * License along with this program; if not, write to the 15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 16 * Boston, MA 021110-1307, USA. 17 */ 18 19 #ifndef __RBTREE_UTILS__ 20 #define __RBTREE_UTILS__ 21 22 #include <linux/rbtree.h> 23 24 #ifdef __cplusplus 25 extern "C" { 26 #endif 27 28 /* The common insert/search/free functions */ 29 typedef int (*rb_compare_nodes)(struct rb_node *node1, struct rb_node *node2); 30 typedef int (*rb_compare_keys)(struct rb_node *node, void *key); 31 typedef void (*rb_free_node)(struct rb_node *node); 32 33 int rb_insert(struct rb_root *root, struct rb_node *node, 34 rb_compare_nodes comp); 35 /* 36 * In some cases, we need return the next node if we don't find the node we 37 * specify. At this time, we can use next_ret. 38 */ 39 struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp, 40 struct rb_node **next_ret); 41 void rb_free_nodes(struct rb_root *root, rb_free_node free_node); 42 43 #define FREE_RB_BASED_TREE(name, free_func) \ 44 static void free_##name##_tree(struct rb_root *root) \ 45 { \ 46 rb_free_nodes(root, free_func); \ 47 } 48 49 #ifdef __cplusplus 50 } 51 #endif 52 53 #endif 54