diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | btrfs-list.c | 1 | ||||
| -rw-r--r-- | cmds-check.c | 1 | ||||
| -rw-r--r-- | disk-io.c | 1 | ||||
| -rw-r--r-- | extent-cache.c | 1 | ||||
| -rw-r--r-- | qgroup-verify.c | 1 | ||||
| -rw-r--r-- | rbtree-utils.c | 82 | ||||
| -rw-r--r-- | rbtree-utils.h | 45 | ||||
| -rw-r--r-- | rbtree.c | 63 | ||||
| -rw-r--r-- | rbtree.h | 22 |
10 files changed, 133 insertions, 86 deletions
@@ -10,7 +10,7 @@ objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \ root-tree.o dir-item.o file-item.o inode-item.o inode-map.o \ extent-cache.o extent_io.o volumes.o utils.o repair.o \ qgroup.o raid6.o free-space-cache.o list_sort.o props.o \ - ulist.o qgroup-verify.o backref.o + ulist.o qgroup-verify.o backref.o rbtree-utils.o cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \ cmds-inspect.o cmds-balance.o cmds-send.o cmds-receive.o \ cmds-quota.o cmds-qgroup.o cmds-replace.o cmds-check.o \ diff --git a/btrfs-list.c b/btrfs-list.c index 01ccca92..b6b84935 100644 --- a/btrfs-list.c +++ b/btrfs-list.c @@ -33,6 +33,7 @@ #include "utils.h" #include <uuid/uuid.h> #include "btrfs-list.h" +#include "rbtree-utils.h" #define BTRFS_LIST_NFILTERS_INCREASE (2 * BTRFS_LIST_FILTER_MAX) #define BTRFS_LIST_NCOMPS_INCREASE (2 * BTRFS_LIST_COMP_MAX) diff --git a/cmds-check.c b/cmds-check.c index d8664115..fede71ed 100644 --- a/cmds-check.c +++ b/cmds-check.c @@ -39,6 +39,7 @@ #include "free-space-cache.h" #include "btrfsck.h" #include "qgroup-verify.h" +#include "rbtree-utils.h" static u64 bytes_used = 0; static u64 total_csum_bytes = 0; @@ -34,6 +34,7 @@ #include "crc32c.h" #include "utils.h" #include "print-tree.h" +#include "rbtree-utils.h" static int check_tree_block(struct btrfs_root *root, struct extent_buffer *buf) { diff --git a/extent-cache.c b/extent-cache.c index 84de87b9..7656ab25 100644 --- a/extent-cache.c +++ b/extent-cache.c @@ -19,6 +19,7 @@ #include <stdlib.h> #include "kerncompat.h" #include "extent-cache.h" +#include "rbtree-utils.h" struct cache_extent_search_range { u64 objectid; diff --git a/qgroup-verify.c b/qgroup-verify.c index 430f0990..c0c61d0b 100644 --- a/qgroup-verify.c +++ b/qgroup-verify.c @@ -28,6 +28,7 @@ #include "print-tree.h" #include "utils.h" #include "ulist.h" +#include "rbtree-utils.h" #include "qgroup-verify.h" diff --git a/rbtree-utils.c b/rbtree-utils.c new file mode 100644 index 00000000..7371bbb4 --- /dev/null +++ b/rbtree-utils.c @@ -0,0 +1,82 @@ +/* + * Copyright (C) 2014 Facebook. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public + * License along with this program; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 021110-1307, USA. + */ + +#include "rbtree-utils.h" + +int rb_insert(struct rb_root *root, struct rb_node *node, + rb_compare_nodes comp) +{ + struct rb_node **p = &root->rb_node; + struct rb_node *parent = NULL; + int ret; + + while(*p) { + parent = *p; + + ret = comp(parent, node); + if (ret < 0) + p = &(*p)->rb_left; + else if (ret > 0) + p = &(*p)->rb_right; + else + return -EEXIST; + } + + rb_link_node(node, parent, p); + rb_insert_color(node, root); + return 0; +} + +struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp, + struct rb_node **next_ret) +{ + struct rb_node *n = root->rb_node; + struct rb_node *parent = NULL; + int ret = 0; + + while(n) { + parent = n; + + ret = comp(n, key); + if (ret < 0) + n = n->rb_left; + else if (ret > 0) + n = n->rb_right; + else + return n; + } + + if (!next_ret) + return NULL; + + if (parent && ret > 0) + parent = rb_next(parent); + + *next_ret = parent; + return NULL; +} + +void rb_free_nodes(struct rb_root *root, rb_free_node free_node) +{ + struct rb_node *node; + + while ((node = rb_first(root))) { + rb_erase(node, root); + free_node(node); + } +} diff --git a/rbtree-utils.h b/rbtree-utils.h new file mode 100644 index 00000000..7298c72e --- /dev/null +++ b/rbtree-utils.h @@ -0,0 +1,45 @@ +/* + * Copyright (C) 2014 Facebook. All rights reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public + * License v2 as published by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public + * License along with this program; if not, write to the + * Free Software Foundation, Inc., 59 Temple Place - Suite 330, + * Boston, MA 021110-1307, USA. + */ + +#ifndef __RBTREE_UTILS__ +#define __RBTREE_UTILS__ + +#include "rbtree.h" + +/* The common insert/search/free functions */ +typedef int (*rb_compare_nodes)(struct rb_node *node1, struct rb_node *node2); +typedef int (*rb_compare_keys)(struct rb_node *node, void *key); +typedef void (*rb_free_node)(struct rb_node *node); + +int rb_insert(struct rb_root *root, struct rb_node *node, + rb_compare_nodes comp); +/* + * In some cases, we need return the next node if we don't find the node we + * specify. At this time, we can use next_ret. + */ +struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp, + struct rb_node **next_ret); +void rb_free_nodes(struct rb_root *root, rb_free_node free_node); + +#define FREE_RB_BASED_TREE(name, free_func) \ +static void free_##name##_tree(struct rb_root *root) \ +{ \ + rb_free_nodes(root, free_func); \ +} + +#endif @@ -387,66 +387,3 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, /* Copy the pointers/colour from the victim to the replacement */ *new = *victim; } - -int rb_insert(struct rb_root *root, struct rb_node *node, - rb_compare_nodes comp) -{ - struct rb_node **p = &root->rb_node; - struct rb_node *parent = NULL; - int ret; - - while(*p) { - parent = *p; - - ret = comp(parent, node); - if (ret < 0) - p = &(*p)->rb_left; - else if (ret > 0) - p = &(*p)->rb_right; - else - return -EEXIST; - } - - rb_link_node(node, parent, p); - rb_insert_color(node, root); - return 0; -} - -struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp, - struct rb_node **next_ret) -{ - struct rb_node *n = root->rb_node; - struct rb_node *parent = NULL; - int ret = 0; - - while(n) { - parent = n; - - ret = comp(n, key); - if (ret < 0) - n = n->rb_left; - else if (ret > 0) - n = n->rb_right; - else - return n; - } - - if (!next_ret) - return NULL; - - if (parent && ret > 0) - parent = rb_next(parent); - - *next_ret = parent; - return NULL; -} - -void rb_free_nodes(struct rb_root *root, rb_free_node free_node) -{ - struct rb_node *node; - - while ((node = rb_first(root))) { - rb_erase(node, root); - free_node(node); - } -} @@ -157,26 +157,4 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, *rb_link = node; } - -/* The common insert/search/free functions */ -typedef int (*rb_compare_nodes)(struct rb_node *node1, struct rb_node *node2); -typedef int (*rb_compare_keys)(struct rb_node *node, void *key); -typedef void (*rb_free_node)(struct rb_node *node); - -int rb_insert(struct rb_root *root, struct rb_node *node, - rb_compare_nodes comp); -/* - * In some cases, we need return the next node if we don't find the node we - * specify. At this time, we can use next_ret. - */ -struct rb_node *rb_search(struct rb_root *root, void *key, rb_compare_keys comp, - struct rb_node **next_ret); -void rb_free_nodes(struct rb_root *root, rb_free_node free_node); - -#define FREE_RB_BASED_TREE(name, free_func) \ -static void free_##name##_tree(struct rb_root *root) \ -{ \ - rb_free_nodes(root, free_func); \ -} - #endif /* _LINUX_RBTREE_H */ |