![[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|
Return to hash.h CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / bird2 / lib |
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