(key, value) lookup algos in src/common/lib/libc/gen

["Mathew, Cherry G." <c%bow.st@localhost>]

Hello Kernel people, et. al.,

I've been researching range querying over multi-dimensional keys,
(mainly related to its application in searching for ("delta","epsilon")
tuple timestamp range queries over a database of timers, events.)

This led me to the current key,value pair lookup code in the NetBSD
source so far. Some of what I found seems fragmented, sometimes
specialised, partially documented, possibly in disrepair.

Although daunting, it seems to be a worthy task to consolidate and
document the bits that need some attention/love.

I'm including a set of sources that I have identified - I'm sure I've
left some out. If so, please point me at them.

Network route matching related (key would be IP/prefix address):

- src/sys/net/radix.[ch]
- src/sbin/routed/radix.c
- src/sys/net/npf/lpm.[ch]

string matching:
Focussed on parallelism:
- src/sys/sys/thmap.h
- src/sys/kern/subr_thmap.c

Generic:
N-way Trie:
- src/common/lib/libc/gen/ptree.c
Radix Tr[ie]e
- src/common/lib/libc/gen/radixtree.c
RB Tree:
- src/common/lib/libc/gen/rb.c
Radix Priority Search Tree:
- src/common/lib/libc/gen/rpst.c

I'd like to understand if anyone here has looked
organising/consolidating these, and updating them to the state of the
art anytime recently, and if anyone has suggestions for new additions.

I'd also appreciate pointers to design patterns around a generalised
interface for these, that wouldn't take away from them.

Many Thanks for any comments.

-- 
Math/(~cherry)