Merge commit 'origin/bfd'

1 files changed, 123 insertions, 0 deletions

diff --git a/lib/hash.h b/lib/hash.h
new file mode 100644
index 00000000..3ac9eebd
--- /dev/null
+++ b/lib/hash.h
@@ -0,0 +1,123 @@
+
+
+#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_INIT(v,pool,init_order)					\
+  ({									\
+    (v).count = 0;							\
+    (v).order = (init_order);						\
+    (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data));	\
+  })
+
+#define HASH_FIND(v,id,key...)						\
+  ({									\
+    uint _h = id##_FN((key)) & HASH_MASK(v);				\
+    HASH_TYPE(v) *_n = (v).data[_h];					\
+    while (_n && !id##_EQ(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);			\
+    HASH_TYPE(v) **_nn = (v).data + _h;					\
+    id##_NEXT(node) = *_nn;						\
+    *_nn = node;							\
+    (v).count++;							\
+  })
+
+#define HASH_DO_REMOVE(v,id,_nn)					\
+  ({									\
+    HASH_TYPE(v) *_n = *_nn;						\
+    if (_n)								\
+    {									\
+      *_nn = id##_NEXT(_n);						\
+      (v).count--;							\
+    }									\
+    _n;									\
+  })
+
+#define HASH_DELETE(v,id,key...)					\
+  ({									\
+    uint _h = id##_FN((key)) & HASH_MASK(v);				\
+    HASH_TYPE(v) **_nn = (v).data + _h;					\
+									\
+    while ((*_nn) && !id##_EQ(id##_KEY((*_nn)), (key)))			\
+      _nn = &(id##_NEXT((*_nn)));					\
+									\
+    HASH_DO_REMOVE(v,id,_nn);						\
+  })
+
+#define HASH_REMOVE(v,id,node)						\
+  ({									\
+    uint _h = id##_FN(id##_KEY((node))) & HASH_MASK(v);			\
+    HASH_TYPE(v) **_nn = (v).data + _h;					\
+									\
+    while ((*_nn) && (*_nn != (node)))					\
+      _nn = &(id##_NEXT((*_nn)));					\
+									\
+    HASH_DO_REMOVE(v,id,_nn);						\
+  })
+
+
+#define HASH_REHASH(v,id,pool,step)					\
+  ({									\
+    HASH_TYPE(v) *_n, *_n2, **_od;					\
+    uint _i, _s;							\
+									\
+    _s = 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 (_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)		\
+  { HASH_REHASH(* (HASH(type) *) v, id, p, step); }
+
+#define HASH_TRY_REHASH_UP(v,id,pool)					\
+  ({									\
+    if (((v).order < id##_REHASH_MAX) && ((v).count > HASH_SIZE(v)))	\
+      id##_REHASH_FN(&v, pool, 1);					\
+  })
+
+#define HASH_TRY_REHASH_DOWN(v,id,pool)					\
+  ({									\
+    if (((v).order > id##_REHASH_MIN) && ((v).count < HASH_SIZE(v)/2))	\
+      id##_REHASH_FN(&v, pool, -1);					\
+  })
+
+#define HASH_WALK(v,next,n)						\
+  do {									\
+    HASH_TYPE(v) *n;							\
+    uint _i;								\
+    uint _s = HASH_SIZE(v);						\
+    for (_i = 0; _i < _s; _i++)						\
+      for (n = (v).data[_i]; n; n = n->next)
+
+#define HASH_WALK_END } while (0)
+
+
+#define HASH_WALK_DELSAFE(v,next,n)					\
+  do {									\
+    HASH_TYPE(v) *n, *_next;						\
+    uint _i;								\
+    uint _s = HASH_SIZE(v);						\
+    for (_i = 0; _i < _s; _i++)						\
+      for (n = (v).data[_i]; n && (_next = n->next, 1); n = _next)
+
+#define HASH_WALK_DELSAFE_END } while (0)
+
+