new friend of sys/queue.h and sys/tree.h

[Pawel Wieczorek]

Ricardo Nabinger Sanchez wrote:
> On Wed, 11 Jul 2007 10:09:32 +0000
> Pawel Wieczorek <wieczyk at 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.