BFD work in progress.

Now it compiles and mostly works.

6 files changed, 111 insertions, 46 deletions

diff --git a/lib/hash.h b/lib/hash.h
index 7464f140..3ac9eebd 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -1,62 +1,110 @@
 
 
-#define HASH(type)		struct { type **data; uint used, size; }
+#define HASH(type)		struct { type **data; uint count, order; }
 #define HASH_TYPE(v)		typeof(** (v).data)
-#define HASH_SIZE(v)		((v).size * sizeof(* (v).data))
+#define HASH_SIZE(v)		(1 << (v).order)
+#define HASH_MASK(v)		((1 << (v).order)-1)
 
-#define HASH_INIT(v,pool,isize)						\
+
+#define HASH_INIT(v,pool,init_order)					\
   ({									\
-    (v).used = 0;							\
-    (v).size = (isize);							\
-    (v).data = mb_allocz(pool, HASH_SIZE(v));				\
+    (v).count = 0;							\
+    (v).order = (init_order);						\
+    (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data));	\
   })
 
-#define HASH_FIND(v,id,key)						\
+#define HASH_FIND(v,id,key...)						\
   ({									\
-    HASH_TYPE(v) *_n = (v).data[id##_FN(key, (v).size)];		\
-    while (_n && !id##_EQ(_n, key))					\
-      _n = _n->id##_NEXT;						\
+    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,key,node)					\
+#define HASH_INSERT(v,id,node)						\
   ({									\
-    HASH_TYPE(v) **_nn = (v).data + id##_FN(key, (v).size);		\
-    node->id##_NEXT = *_nn;						\
+    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_DELETE(v,id,key)						\
+#define HASH_DO_REMOVE(v,id,_nn)					\
   ({									\
-    HASH_TYPE(v) **_nn = (v).data + id##_FN(key, (v).size);		\
-    while ((*_nn) && !id##_EQ(*_nn, key))				\
-      _nn = &((*_nn)->id##_NEXT);					\
-									\
     HASH_TYPE(v) *_n = *_nn;						\
     if (_n)								\
-      *_nn = _n->id##_NEXT;						\
+    {									\
+      *_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)						\
   ({									\
-    HASH_TYPE(v) **_nn = (v).data + id##_FN(key, (v).size);		\
+    uint _h = id##_FN(id##_KEY((node))) & HASH_MASK(v);			\
+    HASH_TYPE(v) **_nn = (v).data + _h;					\
+									\
     while ((*_nn) && (*_nn != (node)))					\
-      _nn = &((*_nn)->id##_NEXT);					\
+      _nn = &(id##_NEXT((*_nn)));					\
 									\
-    HASH_TYPE(v) *_n = *_nn;						\
-    if (_n)								\
-      *_nn = _n->id##_NEXT;						\
-    _n;									\
+    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;								\
-    for (_i = 0; _i < ((v).size); _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)
@@ -66,18 +114,10 @@
   do {									\
     HASH_TYPE(v) *n, *_next;						\
     uint _i;								\
-    for (_i = 0; _i < ((v).size); _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)
 
-/*
-define HASH_REHASH(s)							\
-  ({									\
-    type *_n;								\
-    uint _i;								\
-    for (_i = 0; _i < (size_f); _i++)					\
-      for (_n = (hash)[_i]; _n != NULL; _n = 
 
-*/
-  
diff --git a/lib/heap.h b/lib/heap.h
index ecb9a1bd..c8c3d348 100644
--- a/lib/heap.h
+++ b/lib/heap.h
@@ -72,8 +72,8 @@
  **/
 #define HEAP_INIT(heap,num,type,less,swap)						\
   do {											\
-    uns _i = num;									\
-    uns _j, _l;										\
+    uint _i = num;									\
+    uint _j, _l;										\
     type x;										\
     while (_i >= 1)									\
       {											\
@@ -89,7 +89,7 @@
  **/
 #define HEAP_DELMIN(heap,num,type,less,swap)						\
   do {											\
-    uns _j, _l;										\
+    uint _j, _l;										\
     type x;										\
     swap(heap,1,num,x);									\
     num--;										\
@@ -102,7 +102,7 @@
  **/
 #define HEAP_INSERT(heap,num,type,less,swap)						\
   do {											\
-    uns _j, _u;										\
+    uint _j, _u;										\
     type x;										\
     _j = num;										\
     HEAP_BUBBLE_UP_J(heap,num,less,swap);						\
@@ -115,7 +115,7 @@
  **/
 #define HEAP_INCREASE(heap,num,type,less,swap,pos)					\
   do {											\
-    uns _j, _l;										\
+    uint _j, _l;										\
     type x;										\
     _j = pos;										\
     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);						\
@@ -128,7 +128,7 @@
  **/
 #define HEAP_DECREASE(heap,num,type,less,swap,pos)					\
   do {											\
-    uns _j, _u;										\
+    uint _j, _u;										\
     type x;										\
     _j = pos;										\
     HEAP_BUBBLE_UP_J(heap,num,less,swap);						\
@@ -139,7 +139,7 @@
  **/
 #define HEAP_DELETE(heap,num,type,less,swap,pos)					\
   do {											\
-    uns _j, _l, _u;									\
+    uint _j, _l, _u;									\
     type x;										\
     _j = pos;										\
     swap(heap,_j,num,x);								\
diff --git a/lib/lists.c b/lib/lists.c
index 58ffd230..d323a4b6 100644
--- a/lib/lists.c
+++ b/lib/lists.c
@@ -101,6 +101,25 @@ rem_node(node *n)
 }
 
 /**
+ * rem2_node - remove a node from a list, with cleanup
+ * @n: node to be removed
+ *
+ * Removes a node @n from the list it's linked in and resets its pointers to NULL.
+ * Useful if you want to distinguish between linked and unlinked nodes.
+ */
+LIST_INLINE void
+rem2_node(node *n)
+{
+  node *z = n->prev;
+  node *x = n->next;
+
+  z->next = x;
+  x->prev = z;
+  n->next = NULL;
+  n->prev = NULL;
+}
+
+/**
  * replace_node - replace a node in a list with another one
  * @old: node to be removed
  * @new: node to be inserted
diff --git a/lib/lists.h b/lib/lists.h
index 0b0fdbe3..9153029c 100644
--- a/lib/lists.h
+++ b/lib/lists.h
@@ -51,6 +51,7 @@ typedef struct list {			/* In fact two overlayed nodes */
 void add_tail(list *, node *);
 void add_head(list *, node *);
 void rem_node(node *);
+void rem2_node(node *);
 void add_tail_list(list *, list *);
 void init_list(list *);
 void insert_node(node *, node *);
diff --git a/lib/resource.c b/lib/resource.c
index 775b0c53..bf4b3ae9 100644
--- a/lib/resource.c
+++ b/lib/resource.c
@@ -220,7 +220,8 @@ ralloc(pool *p, struct resclass *c)
   bzero(r, c->size);
 
   r->class = c;
-  add_tail(&p->inside, &r->n);
+  if (p)
+    add_tail(&p->inside, &r->n);
   return r;
 }
 
@@ -423,6 +424,6 @@ buffer_realloc(void **buf, unsigned *size, unsigned need, unsigned item_size)
   while (nsize < need)
     nsize = STEP_UP(nsize);
 
-  *buf = mb_realloc(*buf, nsize*isize);
+  *buf = mb_realloc(*buf, nsize * item_size);
   *size = nsize;
 }
diff --git a/lib/resource.h b/lib/resource.h
index 5cb5e274..1a62d389 100644
--- a/lib/resource.h
+++ b/lib/resource.h
@@ -52,7 +52,7 @@ extern pool root_pool;
 
 void *mb_alloc(pool *, unsigned size);
 void *mb_allocz(pool *, unsigned size);
-void *mb_realloc(pool *p, void *m, unsigned size);
+void *mb_realloc(void *m, unsigned size);
 void mb_free(void *);
 
 /* Memory pools with linear allocation */
@@ -78,6 +78,9 @@ void sl_free(slab *, void *);
  * outside resource manager and possibly sysdep code.
  */
 
+void buffer_realloc(void **buf, unsigned *size, unsigned need, unsigned item_size);
+
+
 #ifdef HAVE_LIBDMALLOC
 /*
  * The standard dmalloc macros tend to produce lots of namespace
@@ -103,3 +106,4 @@ void *xrealloc(void *, unsigned);
 #endif
 
 #endif
+