summaryrefslogtreecommitdiff
path: root/lib/hash.h
diff options
context:
space:
mode:
authorMaria Matejka <mq@ucw.cz>2022-08-02 17:58:14 +0200
committerMaria Matejka <mq@ucw.cz>2022-08-02 17:58:14 +0200
commit0072d11f3431165240656edf6ade473554b8747e (patch)
tree6c53bbbf0d3a4a3ad70846aae50995dc184cc5a5 /lib/hash.h
parent2e95d269d6bd42372d3273264e14775242b0744d (diff)
parentdb9153e216b6f1847ac9cdf170b1d14c04552e41 (diff)
Merge branch 'ballygarvan' into HEAD
Replacing the old 3.0-alpha0 cork mechanism with another one inside the routing table. This version should be simpler and also quite clear what it does, why and when.
Diffstat (limited to 'lib/hash.h')
-rw-r--r--lib/hash.h40
1 files changed, 30 insertions, 10 deletions
diff --git a/lib/hash.h b/lib/hash.h
index 8febb33f..ebb2857a 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -10,7 +10,7 @@
#ifndef _BIRD_HASH_H_
#define _BIRD_HASH_H_
-#define HASH(type) struct { type **data; uint count, order; }
+#define HASH(type) struct { type **data; uint count; u16 iterators; u8 order; u8 down_requested:1; }
#define HASH_TYPE(v) typeof(** (v).data)
#define HASH_SIZE(v) (1U << (v).order)
@@ -125,20 +125,26 @@
#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)))) \
+ if ((v).iterators) \
+ (v).down_requested = 1; \
+ else 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) \
({ \
- uint _o = (v).order; \
- while (((v).count < ((1U << _o) REHASH_LO_MARK(args))) && \
- (_o > (REHASH_LO_BOUND(args)))) \
- _o -= (REHASH_LO_STEP(args)); \
- if (_o < (v).order) \
- rehash_fn(&(v), pool, _o - (v).order); \
- })
+ if ((v).iterators) \
+ (v).down_requested = 1; \
+ else { \
+ uint _o = (v).order; \
+ while (((v).count < ((1U << _o) REHASH_LO_MARK(args))) && \
+ (_o > (REHASH_LO_BOUND(args)))) \
+ _o -= (REHASH_LO_STEP(args)); \
+ if (_o < (v).order) \
+ rehash_fn(&(v), pool, _o - (v).order); \
+ } \
+ })
#define HASH_INSERT2(v,id,pool,node) \
@@ -195,6 +201,20 @@
#define HASH_WALK_FILTER_END } while (0)
+#define HASH_WALK_ITER(v, id, n, iter) \
+ do { \
+ uint _hash_walk_iter_put = 0; \
+ uint _shift = 32 - (v).order; \
+ for ( ; !_hash_walk_iter_put; (iter) += (1U << _shift)) { \
+ _hash_walk_iter_put = ((iter) + (1U << _shift) == 0); \
+ for (HASH_TYPE(v) *n = (v).data[(iter) >> _shift]; n; n = id##_NEXT((n)))\
+ if (HASH_FN(v, id, id##_KEY(n)) >= ((iter) >> _shift)) \
+
+#define HASH_WALK_ITER_PUT (_hash_walk_iter_put = 1)
+
+#define HASH_WALK_ITER_END } } while (0)
+
+
static inline void
mem_hash_init(u64 *h)
{