Merge branch 'add-path'

4 files changed, 111 insertions, 29 deletions

diff --git a/lib/bitops.h b/lib/bitops.h
index bebd830d..a12f6b60 100644
--- a/lib/bitops.h
+++ b/lib/bitops.h
@@ -6,6 +6,9 @@
  *	Can be freely distributed and used under the terms of the GNU GPL.
  */
 
+#ifndef _BIRD_BITOPTS_H_
+#define _BIRD_BITOPTS_H_
+
 /*
  *	Bit mask operations:
  *
@@ -19,3 +22,8 @@ u32 u32_mkmask(unsigned n);
 int u32_masklen(u32 x);
 
 u32 u32_log2(u32 v);
+
+static inline u32 u32_hash(u32 v) { return v * 2902958171u; }
+
+#endif
+
diff --git a/lib/hash.h b/lib/hash.h
index 3ac9eebd..a73f647a 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -3,7 +3,9 @@
 #define HASH(type)		struct { type **data; uint count, order; }
 #define HASH_TYPE(v)		typeof(** (v).data)
 #define HASH_SIZE(v)		(1 << (v).order)
-#define HASH_MASK(v)		((1 << (v).order)-1)
+
+#define HASH_EQ(v,id,k1,k2...)	(id##_EQ(k1, k2))
+#define HASH_FN(v,id,key...)	((u32) (id##_FN(key)) >> (32 - (v).order))
 
 
 #define HASH_INIT(v,pool,init_order)					\
@@ -15,16 +17,16 @@
 
 #define HASH_FIND(v,id,key...)						\
   ({									\
-    uint _h = id##_FN((key)) & HASH_MASK(v);				\
+    u32 _h = HASH_FN(v, id, key);					\
     HASH_TYPE(v) *_n = (v).data[_h];					\
-    while (_n && !id##_EQ(id##_KEY(_n), (key)))				\
+    while (_n && !HASH_EQ(v, id, id##_KEY(_n), key))			\
       _n = id##_NEXT(_n);						\
     _n;									\
   })
 
 #define HASH_INSERT(v,id,node)						\
   ({									\
-    uint _h = id##_FN(id##_KEY((node))) & HASH_MASK(v);			\
+    u32 _h = HASH_FN(v, id, id##_KEY((node)));				\
     HASH_TYPE(v) **_nn = (v).data + _h;					\
     id##_NEXT(node) = *_nn;						\
     *_nn = node;							\
@@ -33,72 +35,117 @@
 
 #define HASH_DO_REMOVE(v,id,_nn)					\
   ({									\
-    HASH_TYPE(v) *_n = *_nn;						\
-    if (_n)								\
-    {									\
-      *_nn = id##_NEXT(_n);						\
-      (v).count--;							\
-    }									\
-    _n;									\
+    *_nn = id##_NEXT((*_nn));						\
+    (v).count--;							\
   })
 
 #define HASH_DELETE(v,id,key...)					\
   ({									\
-    uint _h = id##_FN((key)) & HASH_MASK(v);				\
-    HASH_TYPE(v) **_nn = (v).data + _h;					\
+    u32 _h = HASH_FN(v, id, key);					\
+    HASH_TYPE(v) *_n, **_nn = (v).data + _h;				\
 									\
-    while ((*_nn) && !id##_EQ(id##_KEY((*_nn)), (key)))			\
+    while ((*_nn) && !HASH_EQ(v, id, id##_KEY((*_nn)), key))		\
       _nn = &(id##_NEXT((*_nn)));					\
 									\
-    HASH_DO_REMOVE(v,id,_nn);						\
+    if (_n = *_nn)							\
+      HASH_DO_REMOVE(v,id,_nn);						\
+    _n;									\
   })
 
 #define HASH_REMOVE(v,id,node)						\
   ({									\
-    uint _h = id##_FN(id##_KEY((node))) & HASH_MASK(v);			\
-    HASH_TYPE(v) **_nn = (v).data + _h;					\
+    u32 _h = HASH_FN(v, id, id##_KEY((node)));				\
+    HASH_TYPE(v) *_n, **_nn = (v).data + _h;				\
 									\
     while ((*_nn) && (*_nn != (node)))					\
       _nn = &(id##_NEXT((*_nn)));					\
 									\
-    HASH_DO_REMOVE(v,id,_nn);						\
+    if (_n = *_nn)							\
+      HASH_DO_REMOVE(v,id,_nn);						\
+    _n;									\
   })
 
 
 #define HASH_REHASH(v,id,pool,step)					\
   ({									\
     HASH_TYPE(v) *_n, *_n2, **_od;					\
-    uint _i, _s;							\
+    uint _i, _os;							\
 									\
-    _s = HASH_SIZE(v);							\
+    _os = HASH_SIZE(v);							\
     _od = (v).data;							\
     (v).count = 0;							\
     (v).order += (step);						\
     (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data));	\
 									\
-    for (_i = 0; _i < _s; _i++)						\
+    for (_i = 0; _i < _os; _i++)					\
       for (_n = _od[_i]; _n && (_n2 = id##_NEXT(_n), 1); _n = _n2)	\
 	HASH_INSERT(v, id, _n);						\
 									\
     mb_free(_od);							\
   })
 
-#define HASH_DEFINE_REHASH_FN(id, type)					\
-  static void id##_REHASH_FN(void *v, pool *p, int step)		\
+#define REHASH_LO_MARK(a,b,c,d,e,f)	a
+#define REHASH_HI_MARK(a,b,c,d,e,f)	b
+#define REHASH_LO_STEP(a,b,c,d,e,f)	c
+#define REHASH_HI_STEP(a,b,c,d,e,f)	d
+#define REHASH_LO_BOUND(a,b,c,d,e,f)	e
+#define REHASH_HI_BOUND(a,b,c,d,e,f)	f
+
+#define HASH_DEFINE_REHASH_FN(id,type)					\
+  static void id##_REHASH(void *v, pool *p, int step)			\
   { HASH_REHASH(* (HASH(type) *) v, id, p, step); }
 
-#define HASH_TRY_REHASH_UP(v,id,pool)					\
+
+#define HASH_MAY_STEP_UP(v,id,pool)	HASH_MAY_STEP_UP_(v,pool, id##_REHASH, id##_PARAMS)
+#define HASH_MAY_STEP_DOWN(v,id,pool)	HASH_MAY_STEP_DOWN_(v,pool, id##_REHASH, id##_PARAMS)
+#define HASH_MAY_RESIZE_DOWN(v,id,pool)	HASH_MAY_RESIZE_DOWN_(v,pool, id##_REHASH, id##_PARAMS)
+
+#define HASH_MAY_STEP_UP_(v,pool,rehash_fn,args)			\
+  ({                                                                    \
+    if (((v).count > (HASH_SIZE(v) REHASH_HI_MARK(args))) &&		\
+	((v).order < (REHASH_HI_BOUND(args))))				\
+      rehash_fn(&(v), pool, REHASH_HI_STEP(args));			\
+  })
+
+#define HASH_MAY_STEP_DOWN_(v,pool,rehash_fn,args)			\
+  ({                                                                    \
+    if (((v).count < (HASH_SIZE(v) REHASH_LO_MARK(args))) &&		\
+	((v).order > (REHASH_LO_BOUND(args))))				\
+      rehash_fn(&(v), pool, -(REHASH_LO_STEP(args)));			\
+  })
+
+#define HASH_MAY_RESIZE_DOWN_(v,pool,rehash_fn,args)			\
+  ({                                                                    \
+    int _o = (v).order;							\
+    while (((v).count < ((1 << _o) REHASH_LO_MARK(args))) &&		\
+	   (_o > (REHASH_LO_BOUND(args))))				\
+      _o -= (REHASH_LO_STEP(args));					\
+    if (_o < (v).order)							\
+      rehash_fn(&(v), pool, _o - (int) (v).order);			\
+  })
+
+
+#define HASH_INSERT2(v,id,pool,node)					\
   ({									\
-    if (((v).order < id##_REHASH_MAX) && ((v).count > HASH_SIZE(v)))	\
-      id##_REHASH_FN(&v, pool, 1);					\
+    HASH_INSERT(v, id, node);						\
+    HASH_MAY_STEP_UP(v, id, pool);					\
   })
 
-#define HASH_TRY_REHASH_DOWN(v,id,pool)					\
+#define HASH_DELETE2(v,id,pool,key...)					\
   ({									\
-    if (((v).order > id##_REHASH_MIN) && ((v).count < HASH_SIZE(v)/2))	\
-      id##_REHASH_FN(&v, pool, -1);					\
+    HASH_TYPE(v) *_n = HASH_DELETE(v, id, key);				\
+    if (_n) HASH_MAY_STEP_DOWN(v, id, pool);				\
+    _n;									\
+  })
+
+#define HASH_REMOVE2(v,id,pool,node)					\
+  ({									\
+    HASH_TYPE(v) *_n = HASH_REMOVE(v, id, node);			\
+    if (_n) HASH_MAY_STEP_DOWN(v, id, pool);				\
+    _n;									\
   })
 
+
 #define HASH_WALK(v,next,n)						\
   do {									\
     HASH_TYPE(v) *n;							\
@@ -121,3 +168,13 @@
 #define HASH_WALK_DELSAFE_END } while (0)
 
 
+#define HASH_WALK_FILTER(v,next,n,nn)					\
+  do {									\
+    HASH_TYPE(v) *n, **nn;						\
+    uint _i;								\
+    uint _s = HASH_SIZE(v);						\
+    for (_i = 0; _i < _s; _i++)						\
+      for (nn = (v).data + _i; n = *nn; (*nn == n) ? (nn = &n->next) : NULL)
+
+#define HASH_WALK_FILTER_END } while (0)
+
diff --git a/lib/ipv4.h b/lib/ipv4.h
index f258d37e..7fbdf2eb 100644
--- a/lib/ipv4.h
+++ b/lib/ipv4.h
@@ -52,6 +52,7 @@ typedef u32 ip_addr;
 #define ipa_mkmask(x) _MI(u32_mkmask(x))
 #define ipa_mklen(x) u32_masklen(_I(x))
 #define ipa_hash(x) ipv4_hash(_I(x))
+#define ipa_hash32(x) ipv4_hash32(_I(x))
 #define ipa_hton(x) x = _MI(htonl(_I(x)))
 #define ipa_ntoh(x) x = _MI(ntohl(_I(x)))
 #define ipa_classify(x) ipv4_classify(_I(x))
@@ -86,6 +87,14 @@ static inline unsigned ipv4_hash(u32 a)
   return a & 0xffff;
 }
 
+static inline u32 ipv4_hash32(u32 a)
+{
+  /* Returns a 32-bit value, although low-order bits are not mixed */
+  a ^= a << 16;
+  a ^= a << 12;
+  return a;
+}
+
 static inline int ipv4_compare(u32 x, u32 y)
 {
   return (x > y) - (x < y);
diff --git a/lib/ipv6.h b/lib/ipv6.h
index 2247d3fd..b935a6ef 100644
--- a/lib/ipv6.h
+++ b/lib/ipv6.h
@@ -58,6 +58,7 @@ typedef struct ipv6_addr {
 #define ipa_mkmask(x) ipv6_mkmask(x)
 #define ipa_mklen(x) ipv6_mklen(&(x))
 #define ipa_hash(x) ipv6_hash(&(x))
+#define ipa_hash32(x) ipv6_hash32(&(x))
 #define ipa_hton(x) ipv6_hton(&(x))
 #define ipa_ntoh(x) ipv6_ntoh(&(x))
 #define ipa_classify(x) ipv6_classify(&(x))
@@ -104,6 +105,13 @@ static inline unsigned ipv6_hash(ip_addr *a)
   return (x ^ (x >> 16) ^ (x >> 8)) & 0xffff;
 }
 
+static inline u32 ipv6_hash32(ip_addr *a)
+{
+  /* Returns a 32-bit hash key, although low-order bits are not ixed */
+  u32 x = _I0(*a) ^ _I1(*a) ^ _I2(*a) ^ _I3(*a);
+  return x ^ (x << 16) ^ (x << 24);
+}
+
 static inline u32 ipv6_getbit(ip_addr a, u32 y)
 {
   return a.addr[y / 32] & (0x80000000 >> (y % 32));