From patchwork Tue Sep 8 08:56:55 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 7139241 Return-Path: X-Original-To: patchwork-linux-btrfs@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id 59CAEBF036 for ; Tue, 8 Sep 2015 08:59:32 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 82E80206F4 for ; Tue, 8 Sep 2015 08:59:31 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 9DCED206F9 for ; Tue, 8 Sep 2015 08:59:30 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752383AbbIHI7K (ORCPT ); Tue, 8 Sep 2015 04:59:10 -0400 Received: from cn.fujitsu.com ([59.151.112.132]:31553 "EHLO heian.cn.fujitsu.com" rhost-flags-OK-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S1752232AbbIHI7C (ORCPT ); Tue, 8 Sep 2015 04:59:02 -0400 X-IronPort-AV: E=Sophos;i="5.15,520,1432569600"; d="scan'208";a="100466255" Received: from bogon (HELO edo.cn.fujitsu.com) ([10.167.33.5]) by heian.cn.fujitsu.com with ESMTP; 08 Sep 2015 17:01:58 +0800 Received: from G08CNEXCHPEKD01.g08.fujitsu.local (localhost.localdomain [127.0.0.1]) by edo.cn.fujitsu.com (8.14.3/8.13.1) with ESMTP id t888wkbY009124 for ; Tue, 8 Sep 2015 16:58:46 +0800 Received: from localhost.localdomain (10.167.226.33) by G08CNEXCHPEKD01.g08.fujitsu.local (10.167.33.89) with Microsoft SMTP Server (TLS) id 14.3.181.6; Tue, 8 Sep 2015 16:58:58 +0800 From: Qu Wenruo To: Subject: [PATCH 03/19] btrfs: qgroup: Introduce new function to search most left reserve range Date: Tue, 8 Sep 2015 16:56:55 +0800 Message-ID: <1441702615-18333-4-git-send-email-quwenruo@cn.fujitsu.com> X-Mailer: git-send-email 2.5.1 In-Reply-To: <1441702615-18333-1-git-send-email-quwenruo@cn.fujitsu.com> References: <1441702615-18333-1-git-send-email-quwenruo@cn.fujitsu.com> MIME-Version: 1.0 X-Originating-IP: [10.167.226.33] Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, T_RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Introduce the new function to search the most left reserve range in a reserve map. It provides the basis for later reserve map implement. Signed-off-by: Qu Wenruo --- fs/btrfs/qgroup.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c index cf07c17..fc24fc3 100644 --- a/fs/btrfs/qgroup.c +++ b/fs/btrfs/qgroup.c @@ -2541,6 +2541,42 @@ btrfs_qgroup_rescan_resume(struct btrfs_fs_info *fs_info) } /* + * Return the nearest left range of given start + * No ensure about the range will cover start. + */ +static struct data_rsv_range * +find_reserve_range(struct btrfs_qgroup_data_rsv_map *map, u64 start) +{ + struct rb_node **p = &map->root.rb_node; + struct rb_node *parent = NULL; + struct rb_node *prev = NULL; + struct data_rsv_range *range = NULL; + + while (*p) { + parent = *p; + range = rb_entry(parent, struct data_rsv_range, node); + if (range->start < start) + p = &(*p)->rb_right; + else if (range->start > start) + p = &(*p)->rb_left; + else + return range; + } + + /* empty tree */ + if (!parent) + return NULL; + if (range->start <= start) + return range; + + prev = rb_prev(parent); + /* Already most left one */ + if (!prev) + return range; + return rb_entry(prev, struct data_rsv_range, node); +} + +/* * Init data_rsv_map for a given inode. * * This is needed at write time as quota can be disabled and then enabled