Date: Wed, 11 Jul 2007 16:25:51 +0000 From: Pawel Wieczorek <wieczyk@trzask.int.pl> To: Ricardo Nabinger Sanchez <rnsanchez@wait4.org> Cc: freebsd-arch@freebsd.org Subject: Re: new friend of sys/queue.h and sys/tree.h Message-ID: <4695048F.9020408@trzask.int.pl> In-Reply-To: <20070711104949.7cc844e9.rnsanchez@wait4.org> References: <20070708081511.GX1221@funkthat.com> <200707101833.l6AIX0xl049962@ambrisko.com> <20070710.205751.-1962670861.imp@bsdimp.com> <4694AC5C.9040107@trzask.int.pl> <20070711104949.7cc844e9.rnsanchez@wait4.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Ricardo Nabinger Sanchez wrote: > On Wed, 11 Jul 2007 10:09:32 +0000 > Pawel Wieczorek <wieczyk@trzask.int.pl> wrote: > >> Hash table are basic data structure, it is good to have it in kernel, >> but i did not see some easy to use framework like sys/queue.h in our >> kernel. > >>From what I understood, the actual implementation is based on lists > (SLIST, specifically)? > Yes, MAP is getting hash-number of key and selecting which list should be used. In this way we dont need to find for example one element in 1000 elements in list, but in 10 elements list. I used SLIST because it is done and tested, if i will did this self it will be lost time and do bigger probality to get bug. :) --- Selecting way is easy, if we have for example 14 lists, and hash number is 15 we are doing: INDEX = 15 mod 14 = 1 It is better to use prime numbers as dividers because the bits in result value are more changed. For example if you are dividing by power of 2 the bits are only shifted and it is bigger probability that more of items will be selected to have this same index. Sorry if my english is sometime too much complicated, i am not a expert of this language.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4695048F.9020408>