From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755907AbcASO0t (ORCPT ); Tue, 19 Jan 2016 09:26:49 -0500 Received: from mga11.intel.com ([192.55.52.93]:33022 "EHLO mga11.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755384AbcASOZy (ORCPT ); Tue, 19 Jan 2016 09:25:54 -0500 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.22,317,1449561600"; d="scan'208";a="32234531" From: Matthew Wilcox To: Andrew Morton , Johannes Weiner Cc: Matthew Wilcox , "Kirill A. Shutemov" , Ross Zwisler , linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, linux-mm@kvack.org Subject: [PATCH 6/8] radix_tree: Loop based on shift count, not height Date: Tue, 19 Jan 2016 09:25:31 -0500 Message-Id: <1453213533-6040-7-git-send-email-matthew.r.wilcox@intel.com> X-Mailer: git-send-email 2.7.0.rc3 In-Reply-To: <1453213533-6040-1-git-send-email-matthew.r.wilcox@intel.com> References: <1453213533-6040-1-git-send-email-matthew.r.wilcox@intel.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org From: Matthew Wilcox When we introduce entries that can cover multiple indices, we will need to stop in __radix_tree_create based on the shift, not the height. Split out for ease of bisect. Signed-off-by: Matthew Wilcox --- lib/radix-tree.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 422a92a..869be33 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -407,10 +407,10 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index, slot = indirect_to_ptr(root->rnode); height = root->height; - shift = (height-1) * RADIX_TREE_MAP_SHIFT; + shift = height * RADIX_TREE_MAP_SHIFT; offset = 0; /* uninitialised var warning */ - while (height > 0) { + while (shift > 0) { if (slot == NULL) { /* Have to add a child node. */ slot = radix_tree_node_alloc(root); @@ -429,11 +429,11 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index, } /* Go a level down */ + shift -= RADIX_TREE_MAP_SHIFT; offset = (index >> shift) & RADIX_TREE_MAP_MASK; node = slot; slot = node->slots[offset]; slot = indirect_to_ptr(slot); - shift -= RADIX_TREE_MAP_SHIFT; height--; } -- 2.7.0.rc3