[Ocfs2-devel] [PATCH 3/3] ocfs2/xattr: Proper hash collision handle in bucket division.v2
Joel Becker
Joel.Becker at oracle.com
Fri Oct 24 01:47:38 PDT 2008
On Fri, Oct 24, 2008 at 12:43:53AM -0700, Joel Becker wrote:
> On Fri, Oct 24, 2008 at 02:15:35PM +0800, Tao Ma wrote:
> > Joel Becker wrote:
> >> I have an idea to do what you're doing, but cleaner. I'll look
> >> at cmp_xe and try again in the morning.
> > cool, so waiting for your perfect code. ;)
>
> Zing! You got me :-)
How's this (untested)?
/*
* If this ocfs2_xattr_header covers more than one hash value, find a
* place where the hash value changes. Try to find the most even split.
* The most common case is that all entries have different hash values,
* and the first check we make will find a place to split.
*/
static int ocfs2_xattr_find_divide_pos(struct ocfs2_xattr_header *xh)
{
struct ocfs2_xattr_entry *entries = &xh->xh_entries;
int count = le16_to_cpu(xh->xh_count);
int delta, middle = count / 2;
/*
* We start at the middle. Each step gets farther away in both
* directions. We therefore hit the change in hash value
* nearest to the middle. Note that this loop does not execute for
* count < 2.
*/
for (delta = 0; delta < middle; delta++) {
/* Let's check delta earlier than middle */
if (!cmp_ex(&entries[middle - delta - 1],
&entries[middle - delta]))
return middle - delta;
/* For even counts, don't walk off the end */
if ((middle + delta + 1) == count)
continue;
/* Now try delta past middle */
if (!cmp_ex(&entries[middle + delta],
&entries[middle + delta + 1]))
return middle + delta + 1;
}
/* Every entry had the same hash */
return count;
}
Joel
--
"Reader, suppose you were and idiot. And suppose you were a member of
Congress. But I repeat myself."
- Mark Twain
Joel Becker
Principal Software Developer
Oracle
E-mail: joel.becker at oracle.com
Phone: (650) 506-8127
More information about the Ocfs2-devel
mailing list