diff options
| -rw-r--r-- | Makefile | 2 | ||||
| -rw-r--r-- | ctree.h | 9 | ||||
| -rw-r--r-- | disk-io.c | 5 | ||||
| -rw-r--r-- | extent-tree.c | 155 | ||||
| -rw-r--r-- | pending-extent.c | 152 | ||||
| -rw-r--r-- | pending-extent.h | 51 | ||||
| -rw-r--r-- | rbtree.c | 389 | ||||
| -rw-r--r-- | rbtree.h | 160 |
8 files changed, 824 insertions, 99 deletions
@@ -2,7 +2,7 @@ CC=gcc CFLAGS = -g -Wall -fno-strict-aliasing -Werror objects = ctree.o disk-io.o radix-tree.o extent-tree.o print-tree.o \ root-tree.o dir-item.o hash.o file-item.o inode-item.o \ - inode-map.o crc32c.o\ + inode-map.o crc32c.o rbtree.o pending-extent.o \ # CHECKFLAGS=-D__linux__ -Dlinux -D__STDC__ -Dunix -D__unix__ -Wbitwise \ -Wuninitialized -Wshadow -Wundef @@ -21,6 +21,7 @@ #include "list.h" #include "kerncompat.h" +#include "pending-extent.h" struct btrfs_trans_handle; @@ -280,11 +281,12 @@ struct btrfs_fs_info { struct btrfs_root *fs_root; struct btrfs_root *extent_root; struct btrfs_root *tree_root; - struct btrfs_key current_insert; struct btrfs_key last_insert; struct radix_tree_root cache_radix; - struct radix_tree_root pinned_radix; struct radix_tree_root block_group_radix; + struct pending_tree pending_tree; + struct pending_tree pinned_tree; + struct pending_tree del_pending; struct list_head trans; struct list_head cache; u64 last_inode_alloc; @@ -298,8 +300,7 @@ struct btrfs_fs_info { /* * in ram representation of the tree. extent_root is used for all allocations - * and for the extent tree extent_root root. current_insert is used - * only for the extent tree. + * and for the extent tree extent_root root. */ struct btrfs_root { struct btrfs_buffer *node; @@ -343,10 +343,12 @@ struct btrfs_root *open_ctree_fd(int fp, struct btrfs_super_block *super) int ret; INIT_RADIX_TREE(&fs_info->cache_radix, GFP_KERNEL); - INIT_RADIX_TREE(&fs_info->pinned_radix, GFP_KERNEL); INIT_RADIX_TREE(&fs_info->block_group_radix, GFP_KERNEL); INIT_LIST_HEAD(&fs_info->trans); INIT_LIST_HEAD(&fs_info->cache); + pending_tree_init(&fs_info->pending_tree); + pending_tree_init(&fs_info->pinned_tree); + pending_tree_init(&fs_info->del_pending); fs_info->cache_size = 0; fs_info->fp = fp; fs_info->running_transaction = NULL; @@ -356,7 +358,6 @@ struct btrfs_root *open_ctree_fd(int fp, struct btrfs_super_block *super) fs_info->last_inode_alloc = 0; fs_info->last_inode_alloc_dirid = 0; fs_info->disk_super = super; - memset(&fs_info->current_insert, 0, sizeof(fs_info->current_insert)); memset(&fs_info->last_insert, 0, sizeof(fs_info->last_insert)); ret = pread(fp, super, sizeof(struct btrfs_super_block), diff --git a/extent-tree.c b/extent-tree.c index 95c4a5a4..85705dca 100644 --- a/extent-tree.c +++ b/extent-tree.c @@ -25,9 +25,6 @@ #include "print-tree.h" #include "transaction.h" -static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root - *orig_root, u64 num_blocks, u64 search_start, u64 - search_end, struct btrfs_key *ins); static int finish_current_insert(struct btrfs_trans_handle *trans, struct btrfs_root *extent_root); static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root @@ -40,7 +37,6 @@ static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root * other allocations are done. The pending tag is also used in the same * manner for deletes. */ -#define CTREE_EXTENT_PENDING_DEL 0 static int inc_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root, u64 blocknr) @@ -50,11 +46,8 @@ static int inc_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root struct btrfs_key key; struct btrfs_leaf *l; struct btrfs_extent_item *item; - struct btrfs_key ins; u32 refs; - find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1, - &ins); btrfs_init_path(&path); key.objectid = blocknr; btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY); @@ -126,11 +119,7 @@ static int write_one_cache_group(struct btrfs_trans_handle *trans, int pending_ret; struct btrfs_root *extent_root = root->fs_info->extent_root; struct btrfs_block_group_item *bi; - struct btrfs_key ins; - ret = find_free_extent(trans, root, 0, 0, (u64)-1, &ins); - if (ret) - return ret; ret = btrfs_search_slot(trans, root->fs_info->extent_root, &cache->key, path, 0, 1); BUG_ON(ret); @@ -220,23 +209,18 @@ static int update_block_group(struct btrfs_trans_handle *trans, int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct btrfs_root *root) { - unsigned long gang[8]; u64 first = 0; - int ret; - int i; - - while(1) { - ret = radix_tree_gang_lookup(&root->fs_info->pinned_radix, - (void *)gang, 0, - ARRAY_SIZE(gang)); - if (!ret) - break; - if (!first) - first = gang[0]; - for (i = 0; i < ret; i++) { - radix_tree_delete(&root->fs_info->pinned_radix, - gang[i]); - } + struct pending_extent *pe; + struct pending_extent *next; + + pe = find_first_pending_extent(&root->fs_info->pinned_tree, 0); + if (pe) + first = pe->start; + while(pe) { + next = next_pending_extent(pe); + remove_pending_extent(&root->fs_info->pinned_tree, pe); + free_pending_extent(pe); + pe = next; } root->fs_info->last_insert.objectid = first; root->fs_info->last_insert.offset = 0; @@ -248,19 +232,31 @@ static int finish_current_insert(struct btrfs_trans_handle *trans, struct { struct btrfs_key ins; struct btrfs_extent_item extent_item; - int i; int ret; u64 super_blocks_used, root_blocks_used; struct btrfs_fs_info *info = extent_root->fs_info; + struct pending_extent *pe; + struct pending_extent *next; + struct pending_tree *pending_tree = &info->pending_tree; btrfs_set_extent_refs(&extent_item, 1); btrfs_set_extent_owner(&extent_item, extent_root->root_key.objectid); ins.offset = 1; btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY); + pe = find_first_pending_extent(pending_tree, 0); + while(pe) { + ins.offset = pe->size; + ins.objectid = pe->start; + + remove_pending_extent(pending_tree, pe); + next = next_pending_extent(pe); + if (!next) + next = find_first_pending_extent(pending_tree, 0); + + free_pending_extent(pe); + pe = next; + - for (i = 0; i < extent_root->fs_info->current_insert.type; i++) { - ins.objectid = extent_root->fs_info->current_insert.objectid + - i; super_blocks_used = btrfs_super_blocks_used(info->disk_super); btrfs_set_super_blocks_used(info->disk_super, super_blocks_used + 1); @@ -274,7 +270,6 @@ static int finish_current_insert(struct btrfs_trans_handle *trans, struct } BUG_ON(ret); } - extent_root->fs_info->current_insert.offset = 0; return 0; } @@ -290,7 +285,6 @@ static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root struct btrfs_root *extent_root = info->extent_root; int ret; struct btrfs_extent_item *ei; - struct btrfs_key ins; u32 refs; BUG_ON(pin && num_blocks != 1); @@ -298,7 +292,6 @@ static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY); key.offset = num_blocks; - find_free_extent(trans, root, 0, 0, (u64)-1, &ins); btrfs_init_path(&path); ret = btrfs_search_slot(trans, extent_root, &key, &path, -1, 1); if (ret) { @@ -316,12 +309,9 @@ static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root u64 super_blocks_used, root_blocks_used; if (pin) { int err; - unsigned long bl = blocknr; - radix_tree_preload(GFP_KERNEL); - err = radix_tree_insert(&info->pinned_radix, - blocknr, (void *)bl); + err = insert_pending_extent(&info->pinned_tree, + blocknr, 1); BUG_ON(err); - radix_tree_preload_end(); } super_blocks_used = btrfs_super_blocks_used(info->disk_super); btrfs_set_super_blocks_used(info->disk_super, @@ -352,25 +342,21 @@ static int del_pending_extents(struct btrfs_trans_handle *trans, struct btrfs_root *extent_root) { int ret; - struct btrfs_buffer *gang[4]; - int i; - - while(1) { - ret = radix_tree_gang_lookup_tag( - &extent_root->fs_info->cache_radix, - (void *)gang, 0, - ARRAY_SIZE(gang), - CTREE_EXTENT_PENDING_DEL); - if (!ret) - break; - for (i = 0; i < ret; i++) { - ret = __free_extent(trans, extent_root, - gang[i]->blocknr, 1, 1); - radix_tree_tag_clear(&extent_root->fs_info->cache_radix, - gang[i]->blocknr, - CTREE_EXTENT_PENDING_DEL); - btrfs_block_release(extent_root, gang[i]); - } + struct pending_extent *pe; + struct pending_extent *next; + struct pending_tree *del_pending = &extent_root->fs_info->del_pending; + + pe = find_first_pending_extent(del_pending, 0); + while(pe) { + remove_pending_extent(del_pending, pe); + ret = __free_extent(trans, extent_root, + pe->start, 1, 1); + BUG_ON(ret); + next = next_pending_extent(pe); + if (!next) + next = find_first_pending_extent(del_pending, 0); + free_pending_extent(pe); + pe = next; } return 0; } @@ -378,9 +364,7 @@ static int del_pending_extents(struct btrfs_trans_handle *trans, struct static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root *extent_root) { - while(radix_tree_tagged(&extent_root->fs_info->cache_radix, - CTREE_EXTENT_PENDING_DEL)) - del_pending_extents(trans, extent_root); + del_pending_extents(trans, extent_root); return 0; } @@ -392,14 +376,13 @@ int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root *root, u64 blocknr, u64 num_blocks, int pin) { struct btrfs_root *extent_root = root->fs_info->extent_root; - struct btrfs_buffer *t; int pending_ret; int ret; if (root == extent_root) { - t = find_tree_block(root, blocknr); - radix_tree_tag_set(&root->fs_info->cache_radix, blocknr, - CTREE_EXTENT_PENDING_DEL); + ret = insert_pending_extent(&root->fs_info->del_pending, + blocknr, num_blocks); + BUG_ON(ret); return 0; } ret = __free_extent(trans, root, blocknr, num_blocks, pin); @@ -425,13 +408,11 @@ static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root u64 hole_size = 0; int slot = 0; u64 last_block = 0; - u64 test_block; int start_found; struct btrfs_leaf *l; struct btrfs_root * root = orig_root->fs_info->extent_root; int total_needed = num_blocks; - total_needed += (btrfs_header_level(&root->node->node.header) + 1) * 3; if (root->fs_info->last_insert.objectid > search_start) search_start = root->fs_info->last_insert.objectid; @@ -496,18 +477,16 @@ check_pending: */ btrfs_release_path(root, &path); BUG_ON(ins->objectid < search_start); - for (test_block = ins->objectid; - test_block < ins->objectid + total_needed; test_block++) { - if (radix_tree_lookup(&root->fs_info->pinned_radix, - test_block)) { - search_start = test_block + 1; - goto check_failed; - } + if (find_pending_extent(&root->fs_info->pinned_tree, + ins->objectid, total_needed)) { + search_start = ins->objectid + total_needed; + goto check_failed; + } + if (find_pending_extent(&root->fs_info->pending_tree, + ins->objectid, total_needed)) { + search_start = ins->objectid + total_needed; + goto check_failed; } - BUG_ON(root->fs_info->current_insert.offset); - root->fs_info->current_insert.offset = total_needed - num_blocks; - root->fs_info->current_insert.objectid = ins->objectid + num_blocks; - root->fs_info->current_insert.type = 0; root->fs_info->last_insert.objectid = ins->objectid; ins->offset = num_blocks; return 0; @@ -537,21 +516,17 @@ static int alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root btrfs_set_extent_refs(&extent_item, 1); btrfs_set_extent_owner(&extent_item, owner); - if (root == extent_root) { - BUG_ON(extent_root->fs_info->current_insert.offset == 0); - BUG_ON(num_blocks != 1); - BUG_ON(extent_root->fs_info->current_insert.type == - extent_root->fs_info->current_insert.offset); - ins->offset = 1; - ins->objectid = extent_root->fs_info->current_insert.objectid + - extent_root->fs_info->current_insert.type++; - return 0; - } ret = find_free_extent(trans, root, num_blocks, search_start, search_end, ins); if (ret) return ret; + if (root == extent_root) { + ret = insert_pending_extent(&root->fs_info->pending_tree, + ins->objectid, ins->offset); + BUG_ON(ret); + return 0; + } super_blocks_used = btrfs_super_blocks_used(info->disk_super); btrfs_set_super_blocks_used(info->disk_super, super_blocks_used + num_blocks); @@ -803,14 +778,10 @@ int btrfs_insert_block_group(struct btrfs_trans_handle *trans, struct btrfs_key *key, struct btrfs_block_group_item *bi) { - struct btrfs_key ins; int ret; int pending_ret; root = root->fs_info->extent_root; - ret = find_free_extent(trans, root, 0, 0, (u64)-1, &ins); - if (ret) - return ret; ret = btrfs_insert_item(trans, root, key, bi, sizeof(*bi)); finish_current_insert(trans, root); pending_ret = run_pending(trans, root); diff --git a/pending-extent.c b/pending-extent.c new file mode 100644 index 00000000..e04b0324 --- /dev/null +++ b/pending-extent.c @@ -0,0 +1,152 @@ +/* + * Copyright (C) 2007 Oracle. 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 <stdio.h> +#include <stdlib.h> +#include "kerncompat.h" +#include "pending-extent.h" + +void pending_tree_init(struct pending_tree *tree) +{ + tree->root.rb_node = NULL; +} + +static struct rb_node *tree_insert(struct rb_root *root, u64 offset, + u64 size, struct rb_node *node) +{ + struct rb_node ** p = &root->rb_node; + struct rb_node * parent = NULL; + struct pending_extent *entry; + + while(*p) { + parent = *p; + entry = rb_entry(parent, struct pending_extent, rb_node); + + if (offset + size <= entry->start) + p = &(*p)->rb_left; + else if (offset >= entry->start + entry->size) + p = &(*p)->rb_right; + else + return parent; + } + + entry = rb_entry(parent, struct pending_extent, rb_node); + rb_link_node(node, parent, p); + rb_insert_color(node, root); + return NULL; +} + +static struct rb_node *__tree_search(struct rb_root *root, u64 offset, + u64 size, struct rb_node **prev_ret) +{ + struct rb_node * n = root->rb_node; + struct rb_node *prev = NULL; + struct pending_extent *entry; + struct pending_extent *prev_entry = NULL; + + while(n) { + entry = rb_entry(n, struct pending_extent, rb_node); + prev = n; + prev_entry = entry; + + if (offset + size <= entry->start) + n = n->rb_left; + else if (offset >= entry->start + entry->size) + n = n->rb_right; + else + return n; + } + if (!prev_ret) + return NULL; + + while(prev && offset >= prev_entry->start + prev_entry->size) { + prev = rb_next(prev); + prev_entry = rb_entry(prev, struct pending_extent, rb_node); + } + *prev_ret = prev; + return NULL; +} + +struct pending_extent *alloc_pending_extent(u64 start, u64 size) +{ + struct pending_extent *pe = malloc(sizeof(*pe)); + + if (!pe) + return pe; + pe->start = start; + pe->size = size; + return pe; +} + +int insert_pending_extent(struct pending_tree *tree, u64 start, u64 size) +{ + struct pending_extent *pe = alloc_pending_extent(start, size); + struct rb_node *found; + + found = tree_insert(&tree->root, start, size, &pe->rb_node); + + if (found) + return -EEXIST; + return 0; +} + +struct pending_extent *find_pending_extent(struct pending_tree *tree, + u64 start, u64 size) +{ + struct rb_node *prev; + struct rb_node *ret; + struct pending_extent *entry; + + ret = __tree_search(&tree->root, start, size, &prev); + if (!ret) + return NULL; + + entry = rb_entry(ret, struct pending_extent, rb_node); + return entry; +} + +struct pending_extent *find_first_pending_extent(struct pending_tree *tree, + u64 start) +{ + struct rb_node *prev; + struct rb_node *ret; + struct pending_extent *entry; + + ret = __tree_search(&tree->root, start, 1, &prev); + if (!ret) + ret = prev; + if (!ret) + return NULL; + entry = rb_entry(ret, struct pending_extent, rb_node); + return entry; +} + +struct pending_extent *next_pending_extent(struct pending_extent *pe) +{ + struct rb_node *node = rb_next(&pe->rb_node); + + if (!node) + return NULL; + return rb_entry(node, struct pending_extent, rb_node); +} + +void remove_pending_extent(struct pending_tree *tree, + struct pending_extent *pe) +{ + rb_erase(&pe->rb_node, &tree->root); +} + diff --git a/pending-extent.h b/pending-extent.h new file mode 100644 index 00000000..972f9559 --- /dev/null +++ b/pending-extent.h @@ -0,0 +1,51 @@ +/* + * Copyright (C) 2007 Oracle. 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 __PENDING_EXTENT__ +#define __PENDING_EXTENT__ +#include "kerncompat.h" +#include "rbtree.h" + +struct pending_tree { + struct rb_root root; +}; + +struct pending_extent { + struct rb_node rb_node; + u64 start; + u64 size; +}; + +void pending_tree_init(struct pending_tree *tree); +void remove_pending_extent(struct pending_tree *tree, + struct pending_extent *pe); +struct pending_extent *find_first_pending_extent(struct pending_tree *tree, + u64 start); +struct pending_extent *next_pending_extent(struct pending_extent *pe); +struct pending_extent *find_pending_extent(struct pending_tree *tree, + u64 start, u64 size); +int insert_pending_extent(struct pending_tree *tree, u64 start, u64 size); + +static inline void free_pending_extent(struct pending_extent *pe) +{ + free(pe); +} + +struct pending_extent *alloc_pending_extent(u64 start, u64 size); + +#endif diff --git a/rbtree.c b/rbtree.c new file mode 100644 index 00000000..6ad800fd --- /dev/null +++ b/rbtree.c @@ -0,0 +1,389 @@ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli <andrea@suse.de> + (C) 2002 David Woodhouse <dwmw2@infradead.org> + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + 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 02111-1307 USA + + linux/lib/rbtree.c +*/ + +#include "rbtree.h" + +static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *right = node->rb_right; + struct rb_node *parent = rb_parent(node); + + if ((node->rb_right = right->rb_left)) + rb_set_parent(right->rb_left, node); + right->rb_left = node; + + rb_set_parent(right, parent); + + if (parent) + { + if (node == parent->rb_left) + parent->rb_left = right; + else + parent->rb_right = right; + } + else + root->rb_node = right; + rb_set_parent(node, right); +} + +static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *left = node->rb_left; + struct rb_node *parent = rb_parent(node); + + if ((node->rb_left = left->rb_right)) + rb_set_parent(left->rb_right, node); + left->rb_right = node; + + rb_set_parent(left, parent); + + if (parent) + { + if (node == parent->rb_right) + parent->rb_right = left; + else + parent->rb_left = left; + } + else + root->rb_node = left; + rb_set_parent(node, left); +} + +void rb_insert_color(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *parent, *gparent; + + while ((parent = rb_parent(node)) && rb_is_red(parent)) + { + gparent = rb_parent(parent); + + if (parent == gparent->rb_left) + { + { + register struct rb_node *uncle = gparent->rb_right; + if (uncle && rb_is_red(uncle)) + { + rb_set_black(uncle); + rb_set_black(parent); + rb_set_red(gparent); + node = gparent; + continue; + } + } + + if (parent->rb_right == node) + { + register struct rb_node *tmp; + __rb_rotate_left(parent, root); + tmp = parent; + parent = node; + node = tmp; + } + + rb_set_black(parent); + rb_set_red(gparent); + __rb_rotate_right(gparent, root); + } else { + { + register struct rb_node *uncle = gparent->rb_left; + if (uncle && rb_is_red(uncle)) + { + rb_set_black(uncle); + rb_set_black(parent); + rb_set_red(gparent); + node = gparent; + continue; + } + } + + if (parent->rb_left == node) + { + register struct rb_node *tmp; + __rb_rotate_right(parent, root); + tmp = parent; + parent = node; + node = tmp; + } + + rb_set_black(parent); + rb_set_red(gparent); + __rb_rotate_left(gparent, root); + } + } + + rb_set_black(root->rb_node); +} + +static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, + struct rb_root *root) +{ + struct rb_node *other; + + while ((!node || rb_is_black(node)) && node != root->rb_node) + { + if (parent->rb_left == node) + { + other = parent->rb_right; + if (rb_is_red(other)) + { + rb_set_black(other); + rb_set_red(parent); + __rb_rotate_left(parent, root); + other = parent->rb_right; + } + if ((!other->rb_left || rb_is_black(other->rb_left)) && + (!other->rb_right || rb_is_black(other->rb_right))) + { + rb_set_red(other); + node = parent; + parent = rb_parent(node); + } + else + { + if (!other->rb_right || rb_is_black(other->rb_right)) + { + struct rb_node *o_left; + if ((o_left = other->rb_left)) + rb_set_black(o_left); + rb_set_red(other); + __rb_rotate_right(other, root); + other = parent->rb_right; + } + rb_set_color(other, rb_color(parent)); + rb_set_black(parent); + if (other->rb_right) + rb_set_black(other->rb_right); + __rb_rotate_left(parent, root); + node = root->rb_node; + break; + } + } + else + { + other = parent->rb_left; + if (rb_is_red(other)) + { + rb_set_black(other); + rb_set_red(parent); + __rb_rotate_right(parent, root); + other = parent->rb_left; + } + if ((!other->rb_left || rb_is_black(other->rb_left)) && + (!other->rb_right || rb_is_black(other->rb_right))) + { + rb_set_red(other); + node = parent; + parent = rb_parent(node); + } + else + { + if (!other->rb_left || rb_is_black(other->rb_left)) + { + register struct rb_node *o_right; + if ((o_right = other->rb_right)) + rb_set_black(o_right); + rb_set_red(other); + __rb_rotate_left(other, root); + other = parent->rb_left; + } + rb_set_color(other, rb_color(parent)); + rb_set_black(parent); + if (other->rb_left) + rb_set_black(other->rb_left); + __rb_rotate_right(parent, root); + node = root->rb_node; + break; + } + } + } + if (node) + rb_set_black(node); +} + +void rb_erase(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *child, *parent; + int color; + + if (!node->rb_left) + child = node->rb_right; + else if (!node->rb_right) + child = node->rb_left; + else + { + struct rb_node *old = node, *left; + + node = node->rb_right; + while ((left = node->rb_left) != NULL) + node = left; + child = node->rb_right; + parent = rb_parent(node); + color = rb_color(node); + + if (child) + rb_set_parent(child, parent); + if (parent == old) { + parent->rb_right = child; + parent = node; + } else + parent->rb_left = child; + + node->rb_parent_color = old->rb_parent_color; + node->rb_right = old->rb_right; + node->rb_left = old->rb_left; + + if (rb_parent(old)) + { + if (rb_parent(old)->rb_left == old) + rb_parent(old)->rb_left = node; + else + rb_parent(old)->rb_right = node; + } else + root->rb_node = node; + + rb_set_parent(old->rb_left, node); + if (old->rb_right) + rb_set_parent(old->rb_right, node); + goto color; + } + + parent = rb_parent(node); + color = rb_color(node); + + if (child) + rb_set_parent(child, parent); + if (parent) + { + if (parent->rb_left == node) + parent->rb_left = child; + else + parent->rb_right = child; + } + else + root->rb_node = child; + + color: + if (color == RB_BLACK) + __rb_erase_color(child, parent, root); +} + +/* + * This function returns the first node (in sort order) of the tree. + */ +struct rb_node *rb_first(struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_left) + n = n->rb_left; + return n; +} + +struct rb_node *rb_last(struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_right) + n = n->rb_right; + return n; +} + +struct rb_node *rb_next(struct rb_node *node) +{ + struct rb_node *parent; + + if (rb_parent(node) == node) + return NULL; + + /* If we have a right-hand child, go down and then left as far + as we can. */ + if (node->rb_right) { + node = node->rb_right; + while (node->rb_left) + node=node->rb_left; + return node; + } + + /* No right-hand children. Everything down and left is + smaller than us, so any 'next' node must be in the general + direction of our parent. Go up the tree; any time the + ancestor is a right-hand child of its parent, keep going + up. First time it's a left-hand child of its parent, said + parent is our 'next' node. */ + while ((parent = rb_parent(node)) && node == parent->rb_right) + node = parent; + + return parent; +} + +struct rb_node *rb_prev(struct rb_node *node) +{ + struct rb_node *parent; + + if (rb_parent(node) == node) + return NULL; + + /* If we have a left-hand child, go down and then right as far + as we can. */ + if (node->rb_left) { + node = node->rb_left; + while (node->rb_right) + node=node->rb_right; + return node; + } + + /* No left-hand children. Go up till we find an ancestor which + is a right-hand child of its parent */ + while ((parent = rb_parent(node)) && node == parent->rb_left) + node = parent; + + return parent; +} + +void rb_replace_node(struct rb_node *victim, struct rb_node *new, + struct rb_root *root) +{ + struct rb_node *parent = rb_parent(victim); + + /* Set the surrounding nodes to point to the replacement */ + if (parent) { + if (victim == parent->rb_left) + parent->rb_left = new; + else + parent->rb_right = new; + } else { + root->rb_node = new; + } + if (victim->rb_left) + rb_set_parent(victim->rb_left, new); + if (victim->rb_right) + rb_set_parent(victim->rb_right, new); + + /* Copy the pointers/colour from the victim to the replacement */ + *new = *victim; +} diff --git a/rbtree.h b/rbtree.h new file mode 100644 index 00000000..bed054d4 --- /dev/null +++ b/rbtree.h @@ -0,0 +1,160 @@ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli <andrea@suse.de> + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + 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 02111-1307 USA + + linux/include/linux/rbtree.h + + To use rbtrees you'll have to implement your own insert and search cores. + This will avoid us to use callbacks and to drop drammatically performances. + I know it's not the cleaner way, but in C (not in C++) to get + performances and genericity... + + Some example of insert and search follows here. The search is a plain + normal search over an ordered tree. The insert instead must be implemented + int two steps: as first thing the code must insert the element in + order as a red leaf in the tree, then the support library function + rb_insert_color() must be called. Such function will do the + not trivial work to rebalance the rbtree if necessary. + +----------------------------------------------------------------------- +static inline struct page * rb_search_page_cache(struct inode * inode, + unsigned long offset) +{ + struct rb_node * n = inode->i_rb_page_cache.rb_node; + struct page * page; + + while (n) + { + page = rb_entry(n, struct page, rb_page_cache); + + if (offset < page->offset) + n = n->rb_left; + else if (offset > page->offset) + n = n->rb_right; + else + return page; + } + return NULL; +} + +static inline struct page * __rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct rb_node ** p = &inode->i_rb_page_cache.rb_node; + struct rb_node * parent = NULL; + struct page * page; + + while (*p) + { + parent = *p; + page = rb_entry(parent, struct page, rb_page_cache); + + if (offset < page->offset) + p = &(*p)->rb_left; + else if (offset > page->offset) + p = &(*p)->rb_right; + else + return page; + } + + rb_link_node(node, parent, p); + + return NULL; +} + +static inline struct page * rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct page * ret; + if ((ret = __rb_insert_page_cache(inode, offset, node))) + goto out; + rb_insert_color(node, &inode->i_rb_page_cache); + out: + return ret; +} +----------------------------------------------------------------------- +*/ + +#ifndef _LINUX_RBTREE_H +#define _LINUX_RBTREE_H +#include "kerncompat.h" +struct rb_node +{ + unsigned long rb_parent_color; +#define RB_RED 0 +#define RB_BLACK 1 + struct rb_node *rb_right; + struct rb_node *rb_left; +} __attribute__((aligned(sizeof(long)))); + /* The alignment might seem pointless, but allegedly CRIS needs it */ + +struct rb_root +{ + struct rb_node *rb_node; + void (*rotate_notify)(struct rb_node *old_parent, struct rb_node *node); + +}; + + +#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) +#define rb_color(r) ((r)->rb_parent_color & 1) +#define rb_is_red(r) (!rb_color(r)) +#define rb_is_black(r) rb_color(r) +#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) +#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) + +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) +{ + rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; +} +static inline void rb_set_color(struct rb_node *rb, int color) +{ + rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; +} + +#define RB_ROOT (struct rb_root) { NULL, } +#define rb_entry(ptr, type, member) container_of(ptr, type, member) + +#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) +#define RB_EMPTY_NODE(node) (rb_parent(node) == node) +#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) + +extern void rb_insert_color(struct rb_node *, struct rb_root *); +extern void rb_erase(struct rb_node *, struct rb_root *); + +/* Find logical next and previous nodes in a tree */ +extern struct rb_node *rb_next(struct rb_node *); +extern struct rb_node *rb_prev(struct rb_node *); +extern struct rb_node *rb_first(struct rb_root *); +extern struct rb_node *rb_last(struct rb_root *); + +/* Fast replacement of a single node without remove/rebalance/add/rebalance */ +extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, + struct rb_root *root); + +static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, + struct rb_node ** rb_link) +{ + node->rb_parent_color = (unsigned long )parent; + node->rb_left = node->rb_right = NULL; + + *rb_link = node; +} + +#endif /* _LINUX_RBTREE_H */ |