From patchwork Fri Dec 13 22:24:51 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: John Stultz X-Patchwork-Id: 22438 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-qa0-f72.google.com (mail-qa0-f72.google.com [209.85.216.72]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 7869923FBA for ; Fri, 13 Dec 2013 22:28:08 +0000 (UTC) Received: by mail-qa0-f72.google.com with SMTP id f11sf2637252qae.11 for ; Fri, 13 Dec 2013 14:28:08 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:delivered-to:from:to:cc:subject :date:message-id:in-reply-to:references:x-original-sender :x-original-authentication-results:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-unsubscribe; bh=oR/1wzJoENBsmCXujzARTyen5kxJRtgMtRgbmb4ojmI=; b=SobrDxCkKJQMOc8zEk9NccG2dcUN35SVXiPyW3mGeQgw4PdduFntPGFCCcHYeC1BSb jwE2i0YoCnAMEZaIhpB8GyOm7pIbzxzMtxVEwr0/4alc6EL82Y5+YO5CNRcgXQ6bSF9h f8EccSgjIGFD8yITx02jPpznhmbW7UEbK9zhucKBKrE0jo7TTwrs+gSh/3WGLtc+hHp/ V5XZrYg5mlOH9YJ+P4zlWeOC5xm7paMMVMHyxPme9uR3KFJdv+G6+8d9CzhAq3w8u+il XFuNMoosPYnWU+L1wofdba9V8oLJTPRTTEbHcA87FJ482AYb2o0roMgnfLKv7NXF4Vk9 gFWQ== X-Gm-Message-State: ALoCoQk7Yahd1ZBXcUQ7MiddLKGnMuP2DGKUk4ROuIMv4NB/5Uvs0u+dvHrxAGEErHWOoNpdrRAP X-Received: by 10.236.20.114 with SMTP id o78mr1636812yho.8.1386973688349; Fri, 13 Dec 2013 14:28:08 -0800 (PST) MIME-Version: 1.0 X-BeenThere: patchwork-forward@linaro.org Received: by 10.49.120.5 with SMTP id ky5ls1237604qeb.26.gmail; Fri, 13 Dec 2013 14:28:08 -0800 (PST) X-Received: by 10.58.254.200 with SMTP id ak8mr2267812ved.12.1386973688241; Fri, 13 Dec 2013 14:28:08 -0800 (PST) Received: from mail-vb0-f42.google.com (mail-vb0-f42.google.com [209.85.212.42]) by mx.google.com with ESMTPS id cy15si1168839veb.30.2013.12.13.14.28.08 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 13 Dec 2013 14:28:08 -0800 (PST) Received-SPF: neutral (google.com: 209.85.212.42 is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) client-ip=209.85.212.42; Received: by mail-vb0-f42.google.com with SMTP id w5so1729801vbf.15 for ; Fri, 13 Dec 2013 14:28:08 -0800 (PST) X-Received: by 10.220.95.139 with SMTP id d11mr2221378vcn.21.1386973688166; Fri, 13 Dec 2013 14:28:08 -0800 (PST) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patches@linaro.org Received: by 10.220.174.196 with SMTP id u4csp73600vcz; Fri, 13 Dec 2013 14:28:07 -0800 (PST) X-Received: by 10.68.238.226 with SMTP id vn2mr5418648pbc.50.1386973687353; Fri, 13 Dec 2013 14:28:07 -0800 (PST) Received: from mail-pa0-f48.google.com (mail-pa0-f48.google.com [209.85.220.48]) by mx.google.com with ESMTPS id ot3si2486162pac.282.2013.12.13.14.28.07 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 13 Dec 2013 14:28:07 -0800 (PST) Received-SPF: neutral (google.com: 209.85.220.48 is neither permitted nor denied by best guess record for domain of john.stultz@linaro.org) client-ip=209.85.220.48; Received: by mail-pa0-f48.google.com with SMTP id rd3so593483pab.21 for ; Fri, 13 Dec 2013 14:28:07 -0800 (PST) X-Received: by 10.68.195.70 with SMTP id ic6mr6061500pbc.112.1386973686968; Fri, 13 Dec 2013 14:28:06 -0800 (PST) Received: from localhost.localdomain (c-67-170-153-23.hsd1.or.comcast.net. [67.170.153.23]) by mx.google.com with ESMTPSA id qz9sm7457908pbc.3.2013.12.13.14.28.05 for (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 13 Dec 2013 14:28:06 -0800 (PST) From: John Stultz To: LKML Cc: Greg KH , Android Kernel Team , Sumit Semwal , Jesse Barker , Colin Cross , John Stultz Subject: [PATCH 077/115] ion: index client->handles rbtree by buffer Date: Fri, 13 Dec 2013 14:24:51 -0800 Message-Id: <1386973529-4884-78-git-send-email-john.stultz@linaro.org> X-Mailer: git-send-email 1.8.3.2 In-Reply-To: <1386973529-4884-1-git-send-email-john.stultz@linaro.org> References: <1386973529-4884-1-git-send-email-john.stultz@linaro.org> X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: john.stultz@linaro.org X-Original-Authentication-Results: mx.google.com; spf=neutral (google.com: 209.85.212.42 is neither permitted nor denied by best guess record for domain of patch+caf_=patchwork-forward=linaro.org@linaro.org) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Precedence: list Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org List-ID: X-Google-Group-Id: 836684582541 List-Post: , List-Help: , List-Archive: List-Unsubscribe: , From: Colin Cross The only remaining users of the client->handles rbtree are iterating through it like a list. Keep the rbtree, but change its index to be the buffer address instead of the handle address, which makes ion_handle_lookup a fast rbtree search. Signed-off-by: Colin Cross [jstultz: modified patch to apply to staging directory] Signed-off-by: John Stultz --- drivers/staging/android/ion/ion.c | 21 ++++++++++++--------- 1 file changed, 12 insertions(+), 9 deletions(-) diff --git a/drivers/staging/android/ion/ion.c b/drivers/staging/android/ion/ion.c index ece1a4c..ef0b2d7 100644 --- a/drivers/staging/android/ion/ion.c +++ b/drivers/staging/android/ion/ion.c @@ -388,13 +388,16 @@ static int ion_handle_put(struct ion_handle *handle) static struct ion_handle *ion_handle_lookup(struct ion_client *client, struct ion_buffer *buffer) { - struct rb_node *n; - - for (n = rb_first(&client->handles); n; n = rb_next(n)) { - struct ion_handle *handle = rb_entry(n, struct ion_handle, - node); - if (handle->buffer == buffer) - return handle; + struct rb_node *n = client->handles.rb_node; + + while (n) { + struct ion_handle *entry = rb_entry(n, struct ion_handle, node); + if (buffer < entry->buffer) + n = n->rb_left; + else if (buffer > entry->buffer) + n = n->rb_right; + else + return entry; } return ERR_PTR(-EINVAL); } @@ -432,9 +435,9 @@ static int ion_handle_add(struct ion_client *client, struct ion_handle *handle) parent = *p; entry = rb_entry(parent, struct ion_handle, node); - if (handle < entry) + if (handle->buffer < entry->buffer) p = &(*p)->rb_left; - else if (handle > entry) + else if (handle->buffer > entry->buffer) p = &(*p)->rb_right; else WARN(1, "%s: buffer already found.", __func__);