A Protocol Independent Hierarchical FIB (VPP-352)

Main Enhancements:
 - Protocol Independent FIB API
 - Hierarchical FIB entries. Dynamic recursive route resolution.
 - Extranet Support.
 - Integration of IP and MPLS forwarding.
 - Separation of FIB and Adjacency databases.
 - Data-Plane Object forwarding model.

Change-Id: I52dc815c0d0aa8b493e3cf6b978568f3cc82296c
Signed-off-by: Neale Ranns <nranns@cisco.com>

7 files changed, 40 insertions, 15 deletions

diff --git a/vppinfra/vppinfra/bihash_24_8.h b/vppinfra/vppinfra/bihash_24_8.h
index e97a37dadff..17e99bf8aa8 100644
--- a/vppinfra/vppinfra/bihash_24_8.h
+++ b/vppinfra/vppinfra/bihash_24_8.h
@@ -32,7 +32,7 @@ typedef struct
 } clib_bihash_kv_24_8_t;
 
 static inline int
-clib_bihash_is_free_24_8 (clib_bihash_kv_24_8_t * v)
+clib_bihash_is_free_24_8 (const clib_bihash_kv_24_8_t * v)
 {
   /* Free values are memset to 0xff, check a bit... */
   if (v->key[0] == ~0ULL && v->value == ~0ULL)
@@ -50,9 +50,9 @@ crc_u32 (u32 data, u32 value)
 }
 
 static inline u64
-clib_bihash_hash_24_8 (clib_bihash_kv_24_8_t * v)
+clib_bihash_hash_24_8 (const clib_bihash_kv_24_8_t * v)
 {
-  u32 *dp = (u32 *) & v->key[0];
+  const u32 *dp = (const u32 *) &v->key[0];
   u32 value = 0;
 
   value = crc_u32 (dp[0], value);
@@ -66,7 +66,7 @@ clib_bihash_hash_24_8 (clib_bihash_kv_24_8_t * v)
 }
 #else
 static inline u64
-clib_bihash_hash_24_8 (clib_bihash_kv_24_8_t * v)
+clib_bihash_hash_24_8 (const clib_bihash_kv_24_8_t * v)
 {
   u64 tmp = v->key[0] ^ v->key[1] ^ v->key[2];
   return clib_xxhash (tmp);
@@ -84,7 +84,7 @@ format_bihash_kvp_24_8 (u8 * s, va_list * args)
 }
 
 static inline int
-clib_bihash_key_compare_24_8 (u64 * a, u64 * b)
+clib_bihash_key_compare_24_8 (const u64 * a, const u64 * b)
 {
   return ((a[0] ^ b[0]) | (a[1] ^ b[1]) | (a[2] ^ b[2])) == 0;
 }
diff --git a/vppinfra/vppinfra/bihash_template.c b/vppinfra/vppinfra/bihash_template.c
index 2ad8293094c..4b0b425788a 100644
--- a/vppinfra/vppinfra/bihash_template.c
+++ b/vppinfra/vppinfra/bihash_template.c
@@ -321,7 +321,7 @@ unlock:
 }
 
 int BV (clib_bihash_search)
-  (BVT (clib_bihash) * h,
+  (const BVT (clib_bihash) * h,
    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 {
   u64 hash;
diff --git a/vppinfra/vppinfra/bihash_template.h b/vppinfra/vppinfra/bihash_template.h
index a8bb27ffb0e..f70190c63a5 100644
--- a/vppinfra/vppinfra/bihash_template.h
+++ b/vppinfra/vppinfra/bihash_template.h
@@ -88,7 +88,7 @@ typedef struct
 } BVT (clib_bihash);
 
 
-static inline void *BV (clib_bihash_get_value) (BVT (clib_bihash) * h,
+static inline void *BV (clib_bihash_get_value) (const BVT (clib_bihash) * h,
 						uword offset)
 {
   u8 *hp = h->mheap;
@@ -97,7 +97,7 @@ static inline void *BV (clib_bihash_get_value) (BVT (clib_bihash) * h,
   return (void *) vp;
 }
 
-static inline uword BV (clib_bihash_get_offset) (BVT (clib_bihash) * h,
+static inline uword BV (clib_bihash_get_offset) (const BVT (clib_bihash) * h,
 						 void *v)
 {
   u8 *hp, *vp;
@@ -116,7 +116,7 @@ void BV (clib_bihash_free) (BVT (clib_bihash) * h);
 
 int BV (clib_bihash_add_del) (BVT (clib_bihash) * h,
 			      BVT (clib_bihash_kv) * add_v, int is_add);
-int BV (clib_bihash_search) (BVT (clib_bihash) * h,
+int BV (clib_bihash_search) (const BVT (clib_bihash) * h,
 			     BVT (clib_bihash_kv) * search_v,
 			     BVT (clib_bihash_kv) * return_v);
 
@@ -128,7 +128,7 @@ format_function_t BV (format_bihash_kvp);
 
 
 static inline int BV (clib_bihash_search_inline)
-  (BVT (clib_bihash) * h, BVT (clib_bihash_kv) * kvp)
+  (const BVT (clib_bihash) * h, BVT (clib_bihash_kv) * kvp)
 {
   u64 hash;
   u32 bucket_index;
@@ -163,7 +163,7 @@ static inline int BV (clib_bihash_search_inline)
 }
 
 static inline int BV (clib_bihash_search_inline_2)
-  (BVT (clib_bihash) * h,
+  (const BVT (clib_bihash) * h,
    BVT (clib_bihash_kv) * search_key, BVT (clib_bihash_kv) * valuep)
 {
   u64 hash;
diff --git a/vppinfra/vppinfra/format.c b/vppinfra/vppinfra/format.c
index 0da3502ac0a..78e52e9a2ad 100644
--- a/vppinfra/vppinfra/format.c
+++ b/vppinfra/vppinfra/format.c
@@ -383,7 +383,7 @@ done:
 }
 
 u8 *
-va_format (u8 * s, char *fmt, va_list * va)
+va_format (u8 * s, const char *fmt, va_list * va)
 {
   u8 *f = (u8 *) fmt, *g;
   u8 c;
@@ -415,7 +415,7 @@ va_format (u8 * s, char *fmt, va_list * va)
 }
 
 u8 *
-format (u8 * s, char *fmt, ...)
+format (u8 * s, const char *fmt, ...)
 {
   va_list va;
   va_start (va, fmt);
diff --git a/vppinfra/vppinfra/format.h b/vppinfra/vppinfra/format.h
index c91cc74711e..bc0d6d15fd5 100644
--- a/vppinfra/vppinfra/format.h
+++ b/vppinfra/vppinfra/format.h
@@ -47,8 +47,8 @@
 
 typedef u8 *(format_function_t) (u8 * s, va_list * args);
 
-u8 *va_format (u8 * s, char *format, va_list * args);
-u8 *format (u8 * s, char *format, ...);
+u8 *va_format (u8 * s, const char *format, va_list * args);
+u8 *format (u8 * s, const char *format, ...);
 
 #ifdef CLIB_UNIX
 
diff --git a/vppinfra/vppinfra/hash.h b/vppinfra/vppinfra/hash.h
index 4db5a57602e..3f0efaa727c 100644
--- a/vppinfra/vppinfra/hash.h
+++ b/vppinfra/vppinfra/hash.h
@@ -683,6 +683,11 @@ unformat_function_t unformat_hash_string;
 /* Main test routine. */
 int test_hash_main (unformat_input_t * input);
 
+static inline void
+hash_delete (void *bob)
+{
+}
+
 #endif /* included_hash_h */
 
 /*
diff --git a/vppinfra/vppinfra/vec.h b/vppinfra/vppinfra/vec.h
index 353a06b0530..eed96d6b9c2 100644
--- a/vppinfra/vppinfra/vec.h
+++ b/vppinfra/vppinfra/vec.h
@@ -892,6 +892,26 @@ do {						\
   (_v(cmp) < 0 ? -1 : (_v(cmp) > 0 ? +1 : 0));		\
 })
 
+/** \brief Search a vector for the index of the entry that matches.
+
+    @param v1 Pointer to a vector
+    @param v2 Entry to match
+    @return index of match or ~0
+*/
+#define vec_search(v,E)					\
+({							\
+  word _v(i) = 0;					\
+  while (_v(i) < vec_len(v))				\
+  {							\
+    if (v[_v(i)] == E)				        \
+      break;						\
+    _v(i)++;						\
+  }							\
+  if (_v(i) == vec_len(v))				\
+    _v(i) = ~0;					        \
+  _v(i);						\
+})
+
 /** \brief Sort a vector using the supplied element comparison function
 
     @param vec vector to sort