From owner-freebsd-arch@FreeBSD.ORG Wed Jul 11 14:25:03 2007 Return-Path: X-Original-To: freebsd-arch@freebsd.org Delivered-To: freebsd-arch@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 3110F16A400 for ; Wed, 11 Jul 2007 14:25:03 +0000 (UTC) (envelope-from wieczyk@trzask.int.pl) Received: from trzask.int.pl (host-81-190-193-233.gizycko.mm.pl [81.190.193.233]) by mx1.freebsd.org (Postfix) with ESMTP id 952AC13C46E for ; Wed, 11 Jul 2007 14:25:02 +0000 (UTC) (envelope-from wieczyk@trzask.int.pl) Received: from [192.168.0.99] (unknown [192.168.0.99]) by trzask.int.pl (Postfix) with ESMTP id B9A721A436; Wed, 11 Jul 2007 18:25:13 +0200 (CEST) Message-ID: <4695048F.9020408@trzask.int.pl> Date: Wed, 11 Jul 2007 16:25:51 +0000 From: Pawel Wieczorek User-Agent: Thunderbird 2.0.0.0 (X11/20070529) MIME-Version: 1.0 To: Ricardo Nabinger Sanchez 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> In-Reply-To: <20070711104949.7cc844e9.rnsanchez@wait4.org> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Cc: freebsd-arch@freebsd.org Subject: Re: new friend of sys/queue.h and sys/tree.h X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 11 Jul 2007 14:25:03 -0000 Ricardo Nabinger Sanchez wrote: > On Wed, 11 Jul 2007 10:09:32 +0000 > Pawel Wieczorek 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.