lib: improve the RB implementation

Switch the RB tree implementation completely to the new dlg@'s version
that uses pre-declared functions instead of macros for tree functions.

Original e-mail/diff:
https://marc.info/?l=openbsd-tech&m=147087487111068&w=2

Pros:

* Reduces the amount of code that the usage of those macros generate
* Allows the compiler to do a better compile-time check job
* Might have better i-cache utilization since the tree code is shared

Con:

* dlg@ benchmarks shows it has 'very slightly slower' insertions
* imported RB_* code must adapt the following calls:
  RB_INIT(), RB_GENERATE(), RB_ROOT(), RB_EMPTY(), make compare
  functions use 'const' (if not already) and maybe others.

1 files changed, 3 insertions, 3 deletions

diff --git a/lib/ns.c b/lib/ns.c
index 8c489d68fd..68dc3fa340 100644
--- a/lib/ns.c
+++ b/lib/ns.c
@@ -39,7 +39,7 @@
 DEFINE_MTYPE_STATIC(LIB, NS,        "Logical-Router")
 DEFINE_MTYPE_STATIC(LIB, NS_NAME,   "Logical-Router Name")
 
-static __inline int ns_compare (struct ns *, struct ns *);
+static __inline int ns_compare (const struct ns *, const struct ns *);
 static struct ns *ns_lookup (ns_id_t);
 
 RB_GENERATE (ns_head, ns, entry, ns_compare)
@@ -108,7 +108,7 @@ static int ns_enable (struct ns *ns);
 static void ns_disable (struct ns *ns);
 
 static __inline int
-ns_compare(struct ns *a, struct ns *b)
+ns_compare(const struct ns *a, const struct ns *b)
 {
   return (a->ns_id - b->ns_id);
 }
@@ -453,7 +453,7 @@ ns_terminate (void)
 {
   struct ns *ns;
 
-  while ((ns = RB_ROOT (&ns_tree)) != NULL)
+  while ((ns = RB_ROOT (ns_head, &ns_tree)) != NULL)
     ns_delete (ns);
 }