lib: use trie structure for prefix list matching

Prefix lists were implemented with a simple linear list that is scanned
sequentially.  This is, of course, extremely inefficient as it scales by
O(n).  This patch adds a trie-ish data structure that allows quickly
descending based on the prefix.

Note that the trie structure used here is designed for real-world use,
hence it uses a relatively crude fixed-size bytewise table instead of
some fancy balancing scheme.  It is quite cacheline efficient.

Using real-world routeserver prefix lists, matching against a fulltable
dump:

entries   before     after    factor
   9103   63.8s      .0124s   5142x
    772    4.52s     .0101s    445.3x
     86     .445s    .0098s     45.51x
      7     .0379s   .0099s      3.834x
      2     .0136s   .0095s      1.440x
      1     .0084s   .0095s       .879x

This buys CPU with memory.  Memory usage on an IXP setup with 100k
prefix list entries is an additional 4 MB on top of the 9.5 MB that it
was before.

0 files changed, 0 insertions, 0 deletions