From mboxrd@z Thu Jan 1 00:00:00 1970 From: Joel Becker Date: Thu, 23 Oct 2008 18:14:51 -0700 Subject: [Ocfs2-devel] [PATCH 3/3] ocfs2/xattr: Proper hash collision handle in bucket division.v2 In-Reply-To: <49011C51.1030806@oracle.com> References: <1224218678-32196-3-git-send-email-tao.ma@oracle.com> <1224204876-26802-1-git-send-email-tao.ma@oracle.com> <20081023232030.GE12751@mail.oracle.com> <49011C51.1030806@oracle.com> Message-ID: <20081024011451.GH12751@mail.oracle.com> List-Id: MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit To: ocfs2-devel@oss.oracle.com On Fri, Oct 24, 2008 at 08:52:33AM +0800, Tao Ma wrote: > Joel Becker wrote: >> Do we really need such a complex function? Some of your >> bailouts don't even help much. I *think* what you are doing here is >> trying to find the hash value change closest to the middle. >> Also, you don't need to pass around u16s. It just makes the code >> more complex. >> What about: >> >> /* In an ocfs2_xattr_header, are the hashes of entries n and n+1 equal?. */ >> static inline int xe_cmp(struct ocfs2_xattr_entry *entres, int n) >> { >> return le32_to_cpu(entries[n].xe_name_hash) == >> le32_to_cpu(entries[n + 1].xe_name_hash); >> } > Don't agree. Actually in most cases we won't be so lucky to hit this > situation(I run the test scripts many times and hit one), so I think > most times we will just return "middle" and my function go out > immediately, it is O(1). You function suppose that the hash collision > happens frequently and iterate the half of the xh_entries so it is O(n). Are you saying that you usually have only one xattr per bucket, even with many xattrs? Because if we have n xattrs per bucket, your function will walk down from middle to 0 (half the bucket) unless n is 1. Your function would be much more understandable even if it just used my xe_cmp() function. Then some comment about what you are trying to achieve (I guessed at that), and perhaps a mention of the common case. Joel -- "War doesn't determine who's right; war determines who's left." Joel Becker Principal Software Developer Oracle E-mail: joel.becker at oracle.com Phone: (650) 506-8127