Annotation of embedaddon/bird/lib/hash.h, revision 1.1.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: #endif

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>