Hi Aaron, sorry if my question was confusing. I am not after the hash function (I stored your suggestion already ;)) but of the complete plumbing for a hash table (like create, collision handling, delete). It's not an awful lot of code, but I'd prefer to use some existing thing if there is a good enough one available.
The actual use case will be pid_t (I need a hash table because the max value can change at runtime, else I'd simply taken a "static" table) and cgroup names. I'll definitely look at Bahamut! In case you are interested in what I've done, here is the first shot at it: http://git.adiscon.com/?p=rsyslog.git;a=commitdiff;h=b5da6352830e9841dd367b84 90d79461adb5cb22 This is based on the kernel rate limiter and thus pretty efficient (though a bit limited in what it can do). Thanks for all suggestions. Rainer > -----Original Message----- > From: [email protected] [mailto:rsyslog- > [email protected]] On Behalf Of Aaron Wiebe > Sent: Monday, September 27, 2010 3:40 PM > To: rsyslog-users > Subject: Re: [rsyslog] help request: hashtable library? > > Hash table algorithms are usually very dependent on what you're using > as a key. What are you planning to use as a key? > > If you're looking for something generic, I'm generally a fan of perl's > hashing algorithm: > > if (!len) > len = strlen(rkey); > else if (table->flags & HASH_FL_STRING) > { > len = strlen(rkey); > if (len > table->keylen) > len = table->keylen; > } > if (table->flags & HASH_FL_NOCASE) > while (len--) > hash = hash * 33 + ToLower(*rkey++); > else > while (len--) > hash = hash * 33 + *rkey++; > > return hash % table->size; > > That should be fairly self-explanatory... but feel free to ask > questions. I pulled that out of Bahamut's src/throttle.c where we use > a generic hashing mechanism for throttling connections. You may want > to take a look at that code. > > -Aaron > > On Mon, Sep 27, 2010 at 9:24 AM, Rainer Gerhards > <[email protected]> wrote: > > Hi all, > > > > I am about to implement input rate limiting for imuxsock. This will > be done > > on a per-pid (or per-cgroup) basis. I now have almost all plumbing > done, but > > now need to implement a hash table to lookup the rate limiter > objects. Before > > I go ahead and do my own implementation, I wanted to ask if you can > recommend > > a small and lightweight hashtable "library". > > > > Doing some limited search myself, I found > > > > http://www.cl.cam.ac.uk/~cwc22/hashtable/ > > > > which looks quite usable to me. But I thought I ask if you can > recommend some > > other good libs. > > > > Feedback is appreciated, > > Rainer > > _______________________________________________ > > rsyslog mailing list > > http://lists.adiscon.net/mailman/listinfo/rsyslog > > http://www.rsyslog.com > > > _______________________________________________ > rsyslog mailing list > http://lists.adiscon.net/mailman/listinfo/rsyslog > http://www.rsyslog.com _______________________________________________ rsyslog mailing list http://lists.adiscon.net/mailman/listinfo/rsyslog http://www.rsyslog.com
