diff options
Diffstat (limited to 'lib/hash.h')
| -rw-r--r-- | lib/hash.h | 112 |
1 files changed, 76 insertions, 36 deletions
@@ -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 = -*/ - |