All of lore.kernel.org
 help / color / mirror / Atom feed
From: Liu Bo <bo.li.liu@oracle.com>
To: Wang Shilong <wangsl.fnst@cn.fujitsu.com>
Cc: linux-btrfs@vger.kernel.org
Subject: Re: [PATCH 2/2 v2] Btrfs: check if directory has already been created smarter
Date: Thu, 27 Feb 2014 16:12:36 +0800	[thread overview]
Message-ID: <20140227081235.GC15138@localhost.localdomain> (raw)
In-Reply-To: <530EF0D3.7090805@cn.fujitsu.com>

On Thu, Feb 27, 2014 at 04:01:23PM +0800, Wang Shilong wrote:
> On 02/27/2014 03:47 PM, Liu Bo wrote:
> >Currently to check whether a directory has been created, we search
> >DIR_INDEX items one by one to check if children has been processed.
> >
> >Try to picture such a scenario:
> >    .
> >    |-- dir            (ino X)
> >          |-- foo_1    (ino X+1)
> >          |-- ...
> >          |-- foo_k    (ino X+k)
> >
> >With the current way, we have to check all the k DIR_INDEX items
> >to find it is a fresh new one.
> >
> >So this introduced a rbtree to store those directories which are
> >created out of order, and in the above case, we just need an O(logn)
> >search instead of O(1) search.
> Just a reminder, we ususally call O(n) rather O(1) here.
> If we falls O(1) to O(logn)..things are becoming worse~~

Good catch, my bad.

thanks,
-liubo

  reply	other threads:[~2014-02-27  8:12 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2014-02-27  7:47 [PATCH 1/2 v2] Btrfs: rename waiting_dir_move Liu Bo
2014-02-27  7:47 ` [PATCH 2/2 v2] Btrfs: check if directory has already been created smarter Liu Bo
2014-02-27  8:01   ` Wang Shilong
2014-02-27  8:12     ` Liu Bo [this message]
2014-02-27  9:35   ` [PATCH 2/2 v3] " Liu Bo
2014-03-07 18:00 ` [PATCH 1/2 v2] Btrfs: rename waiting_dir_move Josef Bacik

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20140227081235.GC15138@localhost.localdomain \
    --to=bo.li.liu@oracle.com \
    --cc=linux-btrfs@vger.kernel.org \
    --cc=wangsl.fnst@cn.fujitsu.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.