>>>>> On Wed, 26 Mar 2008 10:11:32 +0100, Kern Sibbald said: > > On Tuesday 25 March 2008 23:56:16 Martin Simmons wrote: > > >>>>> On Tue, 25 Mar 2008 17:55:50 +0100, Kern Sibbald said: > > > > > > As currently implemented this table is a hash table using the hash class > > > that I wrote 3 or 4 years ago for this particular project. It is fast and > > > efficient. > > > > BTW, the hash function is currently a little broken I think, e.g. these > > strings will all have the same hash index: > > > > "abcdefghijklm" > > "zzcdefghijklm" > > "zzzzzzzzzzzzzzcdefghijklm" > > > > The problem is that nothing collects the bits that are lost by the << > > operator, so you only hash on the last 32/3 chars. I think you need to > > rotate the bits instead of just shifting. > > Yes, I noticed the hashing is not uniform, but I haven't had the time to look > into why, so thanks for digging into it. You are surely right. If I am not > mistaken there is no rotate bits function in C because as I remember when I > wrote the original code (a long time ago) I had to use assembly language to > get the rotate (one instruction).
Yes, to get rotate in C you have to use two shifts and combine the results. However, gcc on x86 can detect patterns like (x << y) | (x >> (32-y)) for unsigned x and generate the rotate instruction :-) __Martin ------------------------------------------------------------------------- Check out the new SourceForge.net Marketplace. It's the best place to buy or sell services for just about anything Open Source. http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace _______________________________________________ Bacula-devel mailing list Bacula-devel@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bacula-devel