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, 8 insertions, 8 deletions

diff --git a/lib/vrf.c b/lib/vrf.c
index c4e527db5..42debe5f1 100644
--- a/lib/vrf.c
+++ b/lib/vrf.c
@@ -35,11 +35,11 @@ DEFINE_MTYPE_STATIC(LIB, VRF_BITMAP, "VRF bit-map")
 
 DEFINE_QOBJ_TYPE(vrf)
 
-static __inline int vrf_id_compare (struct vrf *, struct vrf *);
-static __inline int vrf_name_compare (struct vrf *, struct vrf *);
+static __inline int vrf_id_compare (const struct vrf *, const struct vrf *);
+static __inline int vrf_name_compare (const struct vrf *, const struct vrf *);
 
-RB_GENERATE (vrf_id_head, vrf, id_entry, vrf_id_compare)
-RB_GENERATE (vrf_name_head, vrf, name_entry, vrf_name_compare)
+RB_GENERATE (vrf_id_head, vrf, id_entry, vrf_id_compare);
+RB_GENERATE (vrf_name_head, vrf, name_entry, vrf_name_compare);
 
 struct vrf_id_head vrfs_by_id = RB_INITIALIZER (&vrfs_by_id);
 struct vrf_name_head vrfs_by_name = RB_INITIALIZER (&vrfs_by_name);
@@ -72,13 +72,13 @@ vrf_lookup_by_name (const char *name)
 }
 
 static __inline int
-vrf_id_compare (struct vrf *a, struct vrf *b)
+vrf_id_compare (const struct vrf *a, const struct vrf *b)
 {
   return (a->vrf_id - b->vrf_id);
 }
 
 static int
-vrf_name_compare (struct vrf *a, struct vrf *b)
+vrf_name_compare (const struct vrf *a, const struct vrf *b)
 {
   return strcmp (a->name, b->name);
 }
@@ -419,9 +419,9 @@ vrf_terminate (void)
   if (debug_vrf)
     zlog_debug ("%s: Shutting down vrf subsystem", __PRETTY_FUNCTION__);
 
-  while ((vrf = RB_ROOT (&vrfs_by_id)) != NULL)
+  while ((vrf = RB_ROOT (vrf_id_head, &vrfs_by_id)) != NULL)
     vrf_delete (vrf);
-  while ((vrf = RB_ROOT (&vrfs_by_name)) != NULL)
+  while ((vrf = RB_ROOT (vrf_name_head, &vrfs_by_name)) != NULL)
     vrf_delete (vrf);
 }