Annotation of embedaddon/bird2/lib/hash.h, revision 1.1
1.1 ! misho 1: /*
! 2: * BIRD Library -- Generic Hash Table
! 3: *
! 4: * (c) 2013 Ondrej Zajicek <santiago@crfreenet.org>
! 5: * (c) 2013 CZ.NIC z.s.p.o.
! 6: *
! 7: * Can be freely distributed and used under the terms of the GNU GPL.
! 8: */
! 9:
! 10: #ifndef _BIRD_HASH_H_
! 11: #define _BIRD_HASH_H_
! 12:
! 13: #define HASH(type) struct { type **data; uint count, order; }
! 14: #define HASH_TYPE(v) typeof(** (v).data)
! 15: #define HASH_SIZE(v) (1U << (v).order)
! 16:
! 17: #define HASH_EQ(v,id,k1,k2...) (id##_EQ(k1, k2))
! 18: #define HASH_FN(v,id,key...) ((u32) (id##_FN(key)) >> (32 - (v).order))
! 19:
! 20:
! 21: #define HASH_INIT(v,pool,init_order) \
! 22: ({ \
! 23: (v).count = 0; \
! 24: (v).order = (init_order); \
! 25: (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data)); \
! 26: })
! 27:
! 28: #define HASH_FREE(v) \
! 29: ({ \
! 30: mb_free((v).data); \
! 31: (v) = (typeof(v)){ }; \
! 32: })
! 33:
! 34: #define HASH_FIND(v,id,key...) \
! 35: ({ \
! 36: u32 _h = HASH_FN(v, id, key); \
! 37: HASH_TYPE(v) *_n = (v).data[_h]; \
! 38: while (_n && !HASH_EQ(v, id, id##_KEY(_n), key)) \
! 39: _n = id##_NEXT(_n); \
! 40: _n; \
! 41: })
! 42:
! 43: #define HASH_INSERT(v,id,node) \
! 44: ({ \
! 45: u32 _h = HASH_FN(v, id, id##_KEY((node))); \
! 46: HASH_TYPE(v) **_nn = (v).data + _h; \
! 47: id##_NEXT(node) = *_nn; \
! 48: *_nn = node; \
! 49: (v).count++; \
! 50: })
! 51:
! 52: #define HASH_DO_REMOVE(v,id,_nn) \
! 53: ({ \
! 54: *_nn = id##_NEXT((*_nn)); \
! 55: (v).count--; \
! 56: })
! 57:
! 58: #define HASH_DELETE(v,id,key...) \
! 59: ({ \
! 60: u32 _h = HASH_FN(v, id, key); \
! 61: HASH_TYPE(v) *_n, **_nn = (v).data + _h; \
! 62: \
! 63: while ((*_nn) && !HASH_EQ(v, id, id##_KEY((*_nn)), key)) \
! 64: _nn = &(id##_NEXT((*_nn))); \
! 65: \
! 66: if (_n = *_nn) \
! 67: HASH_DO_REMOVE(v,id,_nn); \
! 68: _n; \
! 69: })
! 70:
! 71: #define HASH_REMOVE(v,id,node) \
! 72: ({ \
! 73: u32 _h = HASH_FN(v, id, id##_KEY((node))); \
! 74: HASH_TYPE(v) *_n, **_nn = (v).data + _h; \
! 75: \
! 76: while ((*_nn) && (*_nn != (node))) \
! 77: _nn = &(id##_NEXT((*_nn))); \
! 78: \
! 79: if (_n = *_nn) \
! 80: HASH_DO_REMOVE(v,id,_nn); \
! 81: _n; \
! 82: })
! 83:
! 84:
! 85: #define HASH_REHASH(v,id,pool,step) \
! 86: ({ \
! 87: HASH_TYPE(v) *_n, *_n2, **_od; \
! 88: uint _i, _os; \
! 89: \
! 90: _os = HASH_SIZE(v); \
! 91: _od = (v).data; \
! 92: (v).count = 0; \
! 93: (v).order += (step); \
! 94: (v).data = mb_allocz(pool, HASH_SIZE(v) * sizeof(* (v).data)); \
! 95: \
! 96: for (_i = 0; _i < _os; _i++) \
! 97: for (_n = _od[_i]; _n && (_n2 = id##_NEXT(_n), 1); _n = _n2) \
! 98: HASH_INSERT(v, id, _n); \
! 99: \
! 100: mb_free(_od); \
! 101: })
! 102:
! 103: #define REHASH_LO_MARK(a,b,c,d,e,f) a
! 104: #define REHASH_HI_MARK(a,b,c,d,e,f) b
! 105: #define REHASH_LO_STEP(a,b,c,d,e,f) c
! 106: #define REHASH_HI_STEP(a,b,c,d,e,f) d
! 107: #define REHASH_LO_BOUND(a,b,c,d,e,f) e
! 108: #define REHASH_HI_BOUND(a,b,c,d,e,f) f
! 109:
! 110: #define HASH_DEFINE_REHASH_FN(id,type) \
! 111: static void id##_REHASH(void *v, pool *p, int step) \
! 112: { HASH_REHASH(* (HASH(type) *) v, id, p, step); }
! 113:
! 114:
! 115: #define HASH_MAY_STEP_UP(v,id,pool) HASH_MAY_STEP_UP_(v,pool, id##_REHASH, id##_PARAMS)
! 116: #define HASH_MAY_STEP_DOWN(v,id,pool) HASH_MAY_STEP_DOWN_(v,pool, id##_REHASH, id##_PARAMS)
! 117: #define HASH_MAY_RESIZE_DOWN(v,id,pool) HASH_MAY_RESIZE_DOWN_(v,pool, id##_REHASH, id##_PARAMS)
! 118:
! 119: #define HASH_MAY_STEP_UP_(v,pool,rehash_fn,args) \
! 120: ({ \
! 121: if (((v).count > (HASH_SIZE(v) REHASH_HI_MARK(args))) && \
! 122: ((v).order < (REHASH_HI_BOUND(args)))) \
! 123: rehash_fn(&(v), pool, REHASH_HI_STEP(args)); \
! 124: })
! 125:
! 126: #define HASH_MAY_STEP_DOWN_(v,pool,rehash_fn,args) \
! 127: ({ \
! 128: if (((v).count < (HASH_SIZE(v) REHASH_LO_MARK(args))) && \
! 129: ((v).order > (REHASH_LO_BOUND(args)))) \
! 130: rehash_fn(&(v), pool, -(REHASH_LO_STEP(args))); \
! 131: })
! 132:
! 133: #define HASH_MAY_RESIZE_DOWN_(v,pool,rehash_fn,args) \
! 134: ({ \
! 135: uint _o = (v).order; \
! 136: while (((v).count < ((1U << _o) REHASH_LO_MARK(args))) && \
! 137: (_o > (REHASH_LO_BOUND(args)))) \
! 138: _o -= (REHASH_LO_STEP(args)); \
! 139: if (_o < (v).order) \
! 140: rehash_fn(&(v), pool, _o - (v).order); \
! 141: })
! 142:
! 143:
! 144: #define HASH_INSERT2(v,id,pool,node) \
! 145: ({ \
! 146: HASH_INSERT(v, id, node); \
! 147: HASH_MAY_STEP_UP(v, id, pool); \
! 148: })
! 149:
! 150: #define HASH_DELETE2(v,id,pool,key...) \
! 151: ({ \
! 152: HASH_TYPE(v) *_n = HASH_DELETE(v, id, key); \
! 153: if (_n) HASH_MAY_STEP_DOWN(v, id, pool); \
! 154: _n; \
! 155: })
! 156:
! 157: #define HASH_REMOVE2(v,id,pool,node) \
! 158: ({ \
! 159: HASH_TYPE(v) *_n = HASH_REMOVE(v, id, node); \
! 160: if (_n) HASH_MAY_STEP_DOWN(v, id, pool); \
! 161: _n; \
! 162: })
! 163:
! 164:
! 165: #define HASH_WALK(v,next,n) \
! 166: do { \
! 167: HASH_TYPE(v) *n; \
! 168: uint _i; \
! 169: uint _s = HASH_SIZE(v); \
! 170: for (_i = 0; _i < _s; _i++) \
! 171: for (n = (v).data[_i]; n; n = n->next)
! 172:
! 173: #define HASH_WALK_END } while (0)
! 174:
! 175:
! 176: #define HASH_WALK_DELSAFE(v,next,n) \
! 177: do { \
! 178: HASH_TYPE(v) *n, *_next; \
! 179: uint _i; \
! 180: uint _s = HASH_SIZE(v); \
! 181: for (_i = 0; _i < _s; _i++) \
! 182: for (n = (v).data[_i]; n && (_next = n->next, 1); n = _next)
! 183:
! 184: #define HASH_WALK_DELSAFE_END } while (0)
! 185:
! 186:
! 187: #define HASH_WALK_FILTER(v,next,n,nn) \
! 188: do { \
! 189: HASH_TYPE(v) *n, **nn; \
! 190: uint _i; \
! 191: uint _s = HASH_SIZE(v); \
! 192: for (_i = 0; _i < _s; _i++) \
! 193: for (nn = (v).data + _i; n = *nn; (*nn == n) ? (nn = &n->next) : NULL)
! 194:
! 195: #define HASH_WALK_FILTER_END } while (0)
! 196:
! 197:
! 198: static inline void
! 199: mem_hash_init(u64 *h)
! 200: {
! 201: *h = 0x001047d54778bcafULL;
! 202: }
! 203:
! 204: static inline void
! 205: mem_hash_mix(u64 *h, const void *p, uint s)
! 206: {
! 207: const u64 multiplier = 0xb38bc09a61202731ULL;
! 208: const char *pp = p;
! 209: uint i;
! 210:
! 211: for (i=0; i<s/4; i++)
! 212: *h = *h * multiplier + ((const u32 *)pp)[i];
! 213:
! 214: for (i=s & ~0x3; i<s; i++)
! 215: *h = *h * multiplier + pp[i];
! 216: }
! 217:
! 218: static inline uint
! 219: mem_hash_value(u64 *h)
! 220: {
! 221: return ((*h >> 32) ^ (*h & 0xffffffff));
! 222: }
! 223:
! 224: static inline uint
! 225: mem_hash(const void *p, uint s)
! 226: {
! 227: static u64 h;
! 228: mem_hash_init(&h);
! 229: mem_hash_mix(&h, p, s);
! 230: return mem_hash_value(&h);
! 231: }
! 232:
! 233: static inline uint
! 234: ptr_hash(void *ptr)
! 235: {
! 236: uintptr_t p = (uintptr_t) ptr;
! 237: return p ^ (p << 8) ^ (p >> 16);
! 238: }
! 239:
! 240: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hash.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib