From patchwork Tue Mar 19 16:06:03 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrey Sidorov X-Patchwork-Id: 229103 Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by ozlabs.org (Postfix) with ESMTP id 222832C00B5 for ; Wed, 20 Mar 2013 03:06:31 +1100 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756951Ab3CSQGa (ORCPT ); Tue, 19 Mar 2013 12:06:30 -0400 Received: from exprod5og114.obsmtp.com ([64.18.0.28]:60041 "EHLO exprod5og114.obsmtp.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754448Ab3CSQG3 (ORCPT ); Tue, 19 Mar 2013 12:06:29 -0400 Received: from il93mgrg01.am.mot-mobility.com ([144.188.21.13]) (using TLSv1) by exprod5ob114.postini.com ([64.18.4.12]) with SMTP ID DSNKUUiNBG/kHg2X26TmguCHI66lmNEgvZH/@postini.com; Tue, 19 Mar 2013 09:06:29 PDT Received: from il93mgrg01.am.mot-mobility.com ([10.22.94.168]) by il93mgrg01.am.mot-mobility.com (8.14.3/8.14.3) with ESMTP id r2JFt2sS021490 for ; Tue, 19 Mar 2013 11:55:02 -0400 (EDT) Received: from mail-ee0-f51.google.com (mail-ee0-f51.google.com [74.125.83.51]) by il93mgrg01.am.mot-mobility.com (8.14.3/8.14.3) with ESMTP id r2JFt1FJ021483 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Tue, 19 Mar 2013 11:55:02 -0400 (EDT) Received: by mail-ee0-f51.google.com with SMTP id d17so327703eek.24 for ; Tue, 19 Mar 2013 09:06:26 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=x-received:from:to:subject:date:message-id:x-mailer:in-reply-to :references:x-gm-message-state; bh=uARPJg7w0S/Q2sspzJAWzgbJfDElW3Eo4ILPNJOkz8Y=; b=b4hgXEB3WvzA6Nx0nHZGqTN+YL3pd2GucPhMP+aCtnnosk/eAs6hqFoz48+srhVNuh 9E6+MEHq970hvGOpCyXJqvHLcOb90UYuKuDrvbxpogYML8+zlWit/Ej1wYeRzLIW1MXi bghXEbAUCYMVNz4Q9pgA53stqe/QxxKvj954VRmji8xBItYbrFA6AtcjYFMOEQ+Xh4Pi N55/fiFXJMzrwW0/Ol3uFo2sbH+KyyRvqUhokfE/VPRi8mCuIu92s40gCzcpGNQgJa/K UGZLXMLy0HT+3zhpxCET1vd5mpdT7dyctS2GFLtVQPPnnxh85n0MJxLB5soJm2FSCYJA L62w== X-Received: by 10.14.211.65 with SMTP id v41mr61304801eeo.33.1363709186301; Tue, 19 Mar 2013 09:06:26 -0700 (PDT) Received: from qrxd43-motbuntu.mot-mobility.com ([144.187.32.17]) by mx.google.com with ESMTPS id r4sm33958776eeo.12.2013.03.19.09.06.24 (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Tue, 19 Mar 2013 09:06:25 -0700 (PDT) From: Andrey Sidorov To: linux-ext4@vger.kernel.org Subject: [PATCH 4/5] libext2fs: ffz/ffs for rb_tree bitmap Date: Tue, 19 Mar 2013 20:06:03 +0400 Message-Id: <1363709164-3210-5-git-send-email-qrxd43@motorola.com> X-Mailer: git-send-email 1.7.10.4 In-Reply-To: <1363709164-3210-1-git-send-email-qrxd43@motorola.com> References: <1363709164-3210-1-git-send-email-qrxd43@motorola.com> X-Gm-Message-State: ALoCoQnibuSphBr5LE8DjwAqGWBEOQd7K0JxSIJ5NsJRcZmoDbMosqOK0CMsj0ufyVxQsb9s0VTB X-CFilter-Loop: Reflected Sender: linux-ext4-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-ext4@vger.kernel.org find_first_zero / find_first_set Implementation for rb_tree bitmap. Use of rcursor / rcursor_next makes successive ffs/ffz/ffs/... calls to be equivalent of iterating tree via ext2fs_rb_next. Signed-off-by: Andrey Sidorov --- lib/ext2fs/blkmap64_rb.c | 164 +++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 156 insertions(+), 8 deletions(-) diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c index 702187f..76c525e 100644 --- a/lib/ext2fs/blkmap64_rb.c +++ b/lib/ext2fs/blkmap64_rb.c @@ -51,6 +51,21 @@ static int rb_insert_extent(__u64 start, __u64 count, struct ext2fs_rb_private *); static void rb_get_new_extent(struct bmap_rb_extent **, __u64, __u64); +static inline struct bmap_rb_extent * +rb_load_next_cursor(struct ext2fs_rb_private *bp) +{ + if (!bp->rcursor_next && bp->rcursor) { + struct rb_node *node; + node = ext2fs_rb_next(&bp->rcursor->node); + if (!node) + return NULL; + bp->rcursor_next = ext2fs_rb_entry(node, + struct bmap_rb_extent, + node); + } + return bp->rcursor_next; +} + /* #define DEBUG_RB */ #ifdef DEBUG_RB @@ -324,14 +339,7 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit) return 1; } - next_ext = bp->rcursor_next; - if (!next_ext) { - next = ext2fs_rb_next(&rcursor->node); - if (next) - next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent, - node); - bp->rcursor_next = next_ext; - } + next_ext = rb_load_next_cursor(bp); if (next_ext) { if ((bit >= rcursor->start + rcursor->count) && (bit < next_ext->start)) { @@ -855,6 +863,144 @@ static void rb_print_stats(ext2fs_generic_bitmap bitmap) static void rb_print_stats(ext2fs_generic_bitmap bitmap){} #endif +/* Find the first zero bit between start and end, inclusive. */ +static errcode_t rb_find_first_zero(ext2fs_generic_bitmap bitmap, + __u64 start, __u64 end, __u64 *out) +{ + struct ext2fs_rb_private *bp = bitmap->private; + struct rb_node *parent = NULL; + struct rb_node **n = &bp->root.rb_node; + struct bmap_rb_extent *ext = bp->rcursor; + + start -= bitmap->start; + end -= bitmap->start; + + if (!ext) + goto search_tree; + + if (start >= ext->start) { + if (start <= ext->start + ext->count) { + goto match; + } + ext = rb_load_next_cursor(bp); + if (ext && start <= ext->start + ext->count) { + if (start >= ext->start) { + bp->rcursor = ext; + bp->rcursor_next = NULL; + } + goto match; + } + } + +search_tree: + while (*n) { + parent = *n; + ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + + if (start < ext->start) { + n = &(*n)->rb_left; + } else if (start >= (ext->start + ext->count)) { + n = &(*n)->rb_right; + } else { + break; + } + } + bp->rcursor = ext; + bp->rcursor_next = NULL; + +match: + if (ext) { + if (start >= ext->start && start <= ext->start + ext->count) { + if (ext->start + ext->count <= end) { + *out = bitmap->start + ext->start + ext->count; + return 0; + } + else { + return ENOENT; + } + } + else { + *out = bitmap->start + start; + return 0; + } + } + + *out = bitmap->start; + return 0; +} + +/* Find the first set bit between start and end, inclusive. */ +static errcode_t rb_find_first_set(ext2fs_generic_bitmap bitmap, + __u64 start, __u64 end, __u64 *out) +{ + struct ext2fs_rb_private *bp = bitmap->private; + struct rb_node *parent = NULL; + struct rb_node **n = &bp->root.rb_node; + struct bmap_rb_extent *ext = bp->rcursor; + + start -= bitmap->start; + end -= bitmap->start; + + if (!ext) + goto search_tree; + + if (start >= ext->start) { + if (start < ext->start + ext->count) { + *out = bitmap->start + start; + return 0; + } + + ext = rb_load_next_cursor(bp); + if (!ext) + return ENOENT; + if (start < ext->start + ext->count) { + bp->rcursor = ext; + bp->rcursor_next = NULL; + goto match; + } + } + +search_tree: + while (*n) { + parent = *n; + ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node); + + if (start < ext->start) { + n = &(*n)->rb_left; + } else if (start >= (ext->start + ext->count)) { + n = &(*n)->rb_right; + } else { + break; + } + } + + if (ext && start >= ext->start + ext->count) { + struct rb_node *next = ext2fs_rb_next(parent); + if (next) + ext = ext2fs_rb_entry(next, struct bmap_rb_extent, + node); + } + + bp->rcursor = ext; + bp->rcursor_next = NULL; + +match: + if (ext) { + if (start < ext->start) { + if (ext->start <= end) { + *out = bitmap->start + ext->start; + return 0; + } + } + else if (start < ext->start + ext->count) { + *out = bitmap->start + start; + return 0; + } + } + + return ENOENT; +} + struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = { .type = EXT2FS_BMAP64_RBTREE, .new_bmap = rb_new_bmap, @@ -871,4 +1017,6 @@ struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = { .get_bmap_range = rb_get_bmap_range, .clear_bmap = rb_clear_bmap, .print_stats = rb_print_stats, + .find_first_zero = rb_find_first_zero, + .find_first_set = rb_find_first_set, };