diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/bitops.h | 8 | ||||
| -rw-r--r-- | lib/hash.h | 115 | ||||
| -rw-r--r-- | lib/ipv4.h | 9 | ||||
| -rw-r--r-- | lib/ipv6.h | 8 |
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 + @@ -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) + @@ -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); @@ -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)); |