Concurrent trie-hash map

[Mindaugas Rasiukevicius <rmind%netbsd.org@localhost>]

Hi,

I recently implemented thmap [1] -- a concurrent trie-hash map, combining
the elements of hashing and radix trie.  It is supports lock-free lookups
and concurrent inserts/deletes.  It is designed to be optimal as a general
purpose *concurrent* associative array [2][3].

I am going to import it under src/sys/net/npf, so it could be used by NPF.
However, there are various other areas in the kernel where it could improve
the performance significantly, e.g. in the network stack, 5-tuple mapping
to socket (in_pcb.c).  While I currently do not have plans to work in those
areas, if anybody would like to use it elsewhere, I can import thmap in the
src/sys/kern directory.  Let me know.

Thanks.


[1] https://github.com/rmind/thmap
[2] http://www.netbsd.org/~rmind/thmap_lookup_80_64bit_keys_intel_4980hq.svg
[3] http://www.netbsd.org/~rmind/thmap_insert_80_64bit_keys_intel_4980hq.svg

-- 
Mindaugas