[Ocfs2-devel] [PATCH 3/3] ocfs2/xattr: Proper hash collision handle in bucket division.v2

[Joel Becker]

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);
>> }

<snip>

> 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