On Thu, Jun 10, 2010 at 10:11 AM, Rainer Gerhards
<[email protected]> wrote:
>> Sounds like the cache should be implemented as a hash table. :)
>
> Yes, but I need to find good hash functions. If someone already has
> suggestions, they are welcome (while I will not tackle this immediately, I
> would record that information).
Perl5 has a fairly good and simple generic hashing algorithm that I've
used in the past. As follows (simplified):
unsigned int get_hashkey(void *key)
{
char *rkey = (char *)key;
int len;
unsigned int hash = 0;
len = strlen(rkey);
if (len > MAX_KEYLEN)
len = MAX_KEYLEN;
while (len--)
hash = hash * 33 + *rkey++;
return hash % HASH_SIZE;
}
HASH_SIZE should be a suitable large prime number. For what we're
doing, I would guess something like 3001 would be a good hash table
size, and provide a pretty low chance of collisions.
Mind you, this algorithm isn't optimized at all for the fairly limited
input that is "name", and could hash just about anything. Probably
not the fastest we could get, but it would certainly be worth using
for the short term.
-Aaron
_______________________________________________
rsyslog mailing list
http://lists.adiscon.net/mailman/listinfo/rsyslog
http://www.rsyslog.com
