summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/hash.h112
-rw-r--r--lib/heap.h14
-rw-r--r--lib/lists.c19
-rw-r--r--lib/lists.h1
-rw-r--r--lib/resource.c5
-rw-r--r--lib/resource.h6
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
+
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-24 12:34:41 +0000