Subject: Re: 1. uiopeek? 2. hashinit/hashdone?
To: Chapman Flack <>
From: Elad Efrat <>
List: tech-kern
Date: 06/04/2006 19:05:33
Chapman Flack wrote:
> To my question about a man page for hashinit/hashdone, I received
> one suggestion to import the man page from obsd. However, it turns
> out that there are both obvious and subtle differences, so I simply

Do you mind elaborating on the differences between the two
implementations? I think you could borrow the OpenBSD hashinit(9)
and simply adjust it.

> wrote one to fit. Any objections?

Lots. The purpose of a man-page is to be, first and foremost, helpful.
See below.

> .Nd kernel hash table construction and destruction

"construction and destruction" -> "functions".

> .Fa "u_int chains"

That's a lie. The prototype clearly says "u_int elements". Elements can
be either a LIST or a TAILQ.

> The
> .Fn hashinit
> function allocates and initializes space for a simple chaining hash table.


> The number of slots will be the least power of two not smaller than
> .Fa chains ,
> where
> .Fa chains
> should be the product of the intended load factor and the expected number
> of elements to be stored.

This must change. Nobody cares. How about "The number of slots will be
'elements', or the closest power of two."?

Now you need a paragraph separation (.Pp?), and then:

> The
> .Dv LIST...
> or
> .Dv TAILQ...
> macros of
> .Xr queue 3
> can be used to manipulate the chains; pass
> or
> as
> .Fa htype
> to indicate which. Each slot will be initialized as the head of an empty
> chain of the proper type. Note that the total size of the allocated table
> will therefore depend on the head size of the chosen chain type.

Too much. "'htype' indicates the type of each element in the hash table.
Valid types include 'HASH_LIST' to specify a LIST and 'HASH_TAILQ' to
specify a TAILQ. See queue(3)."

> .Pp
> The
> .Fa mtype
> and
> .Fa mflags
> arguments are passed to
> .Xr malloc 9
> to control the allocation.

Kill the last line.

> .Pp
> A value will be stored into
> .Fa *hashmask
> suitable for masking any computed hash, to obtain the index of a chain
> head in the allocated table.

Again, this is confusing and non-clear wording. People who never used a
hash table (or hashinit(9)) will need to see an example, which makes
this sentence useless.

Change it to something like "The hashmask argument is used to pass back
the mask for use with the allocated hashing table" -- as it appears in
the OpenBSD man-page.

> .Pp
> The
> .Fn hashdone
> function deallocates the storage allocated by
> .Fn hashinit
> and pointed to by
> .Fa hashtbl ,
> passing it and
> .Fa mtype
> to
> .Xr free 9 .

How about "The hashdone(9) function frees a hash table 'hashtbl' created
by hashinit(9). 'mtype' is the malloc(9) type passed to free(9)."?

Then a paragraph break, add something like "Note:"..

> It

"It" -> "hashdone(9)".

> .Em does not
> walk the table and deallocate anything in it, or check that the caller has
> done so.

Change this to something simpler. "hashinit(9) frees the hash table
itself and not the elements stored in it."

> The value returned by
> .Fn hashinit
> should be cast as pointer to an array of
> or 
> as appropriate.
> It can be
> .Dv NULL
> only if the specified
> .Fa mflags
> allow it.

Should say "hashinit(9) returns a pointer to the hash table, and
acts with the same semantics as a malloc(9) call with respect to the
passed flags."?

> A
> .Fn hashinit
> function was present, without the
> .Fa htype
> or
> .Fa mflags
> arguments, in
> .Bx 4.4 alpha .
> It was independent of
> .Xr queue 3
> and simply allocated and nulled a table of pointer-sized slots.
> It sized the table to the
> .Em largest
> power of two
> .Em not greater than
> .Fa chains ;
> that is, it built in a load factor usually less than 1.
> .Pp
> .Nx 1.0
> was the first
> .Nx
> release to have a
> .Fn hashinit
> function.
> It resembled that from
> .Bx 4.4
> but made each slot a
> from
> .Xr queue 3 .
> For
> .Nx 1.3.3
> it had been changed to size the table to the least power of two
> not less than
> .Em or equal to
> .Fa chains .
> By
> .Nx 1.4
> it had the
> .Fa mflags
> argument and the current sizing rule.
> .Pp
> .Nx 1.5
> had the
> .Fn hashdone
> function.
> By
> .Nx 1.6
> .Fn hashinit
> supported
> .Dv LIST
> or
> chains selected with
> .Fa htype .
> .Pp
> .Fx
> has a
> .Fn hashinit
> with behavior equivalent (as of
> .Fx 6.1 )
> to that in
> .Nx 1.0 ,
> and a
> .Fn hashdestroy
> that behaves as
> .Fn hashdone
> but checks that all chains are empty first.
> .Ox
> has a
> .Fn hashinit
> comparable (as of
> .Ox 3.9 )
> to that of
> .Nx 1.4 .
> This manual page was added for
> .Nx 3.99 .

The entire "HISTORY" section should go away. If people want to be anal,
just stick a "first appeared in 4.4BSD".

> .Sh BUGS
> The only part of the work of implementing a hash table that these functions
> relieve is the part that isn't much work.

Remove that section too.


Elad Efrat