1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#ifndef __LIBCFS_HASH_H__
43#define __LIBCFS_HASH_H__
44
45
46
47
48
49
50
51
52
53
54
55#define CFS_GOLDEN_RATIO_PRIME_32 0x9e370001UL
56
57#define CFS_GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL
58
59
60
61
62
63
64
65
66#include <linux/hash.h>
67
68#define cfs_hash_long(val, bits) hash_long(val, bits)
69
70
71#define CFS_HASH_DEBUG_NONE 0
72
73
74#define CFS_HASH_DEBUG_1 1
75
76#define CFS_HASH_DEBUG_2 2
77
78#define CFS_HASH_DEBUG_LEVEL CFS_HASH_DEBUG_NONE
79
80struct cfs_hash_ops;
81struct cfs_hash_lock_ops;
82struct cfs_hash_hlist_ops;
83
84typedef union {
85 rwlock_t rw;
86 spinlock_t spin;
87} cfs_hash_lock_t;
88
89
90
91
92
93
94
95
96
97
98
99
100typedef struct cfs_hash_bucket {
101 cfs_hash_lock_t hsb_lock;
102 __u32 hsb_count;
103 __u32 hsb_version;
104 unsigned int hsb_index;
105 int hsb_depmax;
106 long hsb_head[0];
107} cfs_hash_bucket_t;
108
109
110
111
112typedef struct cfs_hash_bd {
113 cfs_hash_bucket_t *bd_bucket;
114 unsigned int bd_offset;
115} cfs_hash_bd_t;
116
117#define CFS_HASH_NAME_LEN 16
118#define CFS_HASH_BIGNAME_LEN 64
119
120#define CFS_HASH_BKT_BITS 3
121#define CFS_HASH_BITS_MAX 30
122#define CFS_HASH_BITS_MIN CFS_HASH_BKT_BITS
123
124
125
126
127enum cfs_hash_tag {
128
129
130
131
132
133
134
135
136 CFS_HASH_NO_LOCK = 1 << 0,
137
138 CFS_HASH_NO_BKTLOCK = 1 << 1,
139
140 CFS_HASH_RW_BKTLOCK = 1 << 2,
141
142 CFS_HASH_SPIN_BKTLOCK = 1 << 3,
143
144 CFS_HASH_ADD_TAIL = 1 << 4,
145
146 CFS_HASH_NO_ITEMREF = 1 << 5,
147
148 CFS_HASH_BIGNAME = 1 << 6,
149
150 CFS_HASH_COUNTER = 1 << 7,
151
152 CFS_HASH_REHASH_KEY = 1 << 8,
153
154 CFS_HASH_REHASH = 1 << 9,
155
156 CFS_HASH_SHRINK = 1 << 10,
157
158 CFS_HASH_ASSERT_EMPTY = 1 << 11,
159
160 CFS_HASH_DEPTH = 1 << 12,
161
162
163
164
165 CFS_HASH_NBLK_CHANGE = 1 << 13,
166
167
168};
169
170
171#define CFS_HASH_DEFAULT (CFS_HASH_RW_BKTLOCK | \
172 CFS_HASH_COUNTER | CFS_HASH_REHASH)
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213typedef struct cfs_hash {
214
215
216 cfs_hash_lock_t hs_lock;
217
218 struct cfs_hash_ops *hs_ops;
219
220 struct cfs_hash_lock_ops *hs_lops;
221
222 struct cfs_hash_hlist_ops *hs_hops;
223
224 cfs_hash_bucket_t **hs_buckets;
225
226 atomic_t hs_count;
227
228 __u16 hs_flags;
229
230 __u16 hs_extra_bytes;
231
232 __u8 hs_iterating;
233
234 __u8 hs_exiting;
235
236 __u8 hs_cur_bits;
237
238 __u8 hs_min_bits;
239
240 __u8 hs_max_bits;
241
242 __u8 hs_rehash_bits;
243
244 __u8 hs_bkt_bits;
245
246 __u16 hs_min_theta;
247
248 __u16 hs_max_theta;
249
250 __u32 hs_rehash_count;
251
252 __u32 hs_iterators;
253
254 cfs_workitem_t hs_rehash_wi;
255
256 atomic_t hs_refcount;
257
258 cfs_hash_bucket_t **hs_rehash_buckets;
259#if CFS_HASH_DEBUG_LEVEL >= CFS_HASH_DEBUG_1
260
261 spinlock_t hs_dep_lock;
262
263 unsigned int hs_dep_max;
264
265 unsigned int hs_dep_bkt;
266
267 unsigned int hs_dep_off;
268
269 unsigned int hs_dep_bits;
270
271 cfs_workitem_t hs_dep_wi;
272#endif
273
274 char hs_name[0];
275} cfs_hash_t;
276
277typedef struct cfs_hash_lock_ops {
278
279 void (*hs_lock)(cfs_hash_lock_t *lock, int exclusive);
280
281 void (*hs_unlock)(cfs_hash_lock_t *lock, int exclusive);
282
283 void (*hs_bkt_lock)(cfs_hash_lock_t *lock, int exclusive);
284
285 void (*hs_bkt_unlock)(cfs_hash_lock_t *lock, int exclusive);
286} cfs_hash_lock_ops_t;
287
288typedef struct cfs_hash_hlist_ops {
289
290 struct hlist_head *(*hop_hhead)(cfs_hash_t *hs, cfs_hash_bd_t *bd);
291
292 int (*hop_hhead_size)(cfs_hash_t *hs);
293
294 int (*hop_hnode_add)(cfs_hash_t *hs,
295 cfs_hash_bd_t *bd, struct hlist_node *hnode);
296
297 int (*hop_hnode_del)(cfs_hash_t *hs,
298 cfs_hash_bd_t *bd, struct hlist_node *hnode);
299} cfs_hash_hlist_ops_t;
300
301typedef struct cfs_hash_ops {
302
303 unsigned (*hs_hash)(cfs_hash_t *hs, const void *key, unsigned mask);
304
305 void * (*hs_key)(struct hlist_node *hnode);
306
307 void (*hs_keycpy)(struct hlist_node *hnode, void *key);
308
309
310
311
312 int (*hs_keycmp)(const void *key, struct hlist_node *hnode);
313
314 void * (*hs_object)(struct hlist_node *hnode);
315
316 void (*hs_get)(cfs_hash_t *hs, struct hlist_node *hnode);
317
318 void (*hs_put)(cfs_hash_t *hs, struct hlist_node *hnode);
319
320 void (*hs_put_locked)(cfs_hash_t *hs, struct hlist_node *hnode);
321
322 void (*hs_exit)(cfs_hash_t *hs, struct hlist_node *hnode);
323} cfs_hash_ops_t;
324
325
326#define CFS_HASH_NBKT(hs) \
327 (1U << ((hs)->hs_cur_bits - (hs)->hs_bkt_bits))
328
329
330#define CFS_HASH_RH_NBKT(hs) \
331 (1U << ((hs)->hs_rehash_bits - (hs)->hs_bkt_bits))
332
333
334#define CFS_HASH_BKT_NHLIST(hs) (1U << (hs)->hs_bkt_bits)
335
336
337#define CFS_HASH_NHLIST(hs) (1U << (hs)->hs_cur_bits)
338
339
340#define CFS_HASH_RH_NHLIST(hs) (1U << (hs)->hs_rehash_bits)
341
342static inline int
343cfs_hash_with_no_lock(cfs_hash_t *hs)
344{
345
346 return (hs->hs_flags & CFS_HASH_NO_LOCK) != 0;
347}
348
349static inline int
350cfs_hash_with_no_bktlock(cfs_hash_t *hs)
351{
352
353 return (hs->hs_flags & CFS_HASH_NO_BKTLOCK) != 0;
354}
355
356static inline int
357cfs_hash_with_rw_bktlock(cfs_hash_t *hs)
358{
359
360 return (hs->hs_flags & CFS_HASH_RW_BKTLOCK) != 0;
361}
362
363static inline int
364cfs_hash_with_spin_bktlock(cfs_hash_t *hs)
365{
366
367 return (hs->hs_flags & CFS_HASH_SPIN_BKTLOCK) != 0;
368}
369
370static inline int
371cfs_hash_with_add_tail(cfs_hash_t *hs)
372{
373 return (hs->hs_flags & CFS_HASH_ADD_TAIL) != 0;
374}
375
376static inline int
377cfs_hash_with_no_itemref(cfs_hash_t *hs)
378{
379
380
381
382 return (hs->hs_flags & CFS_HASH_NO_ITEMREF) != 0;
383}
384
385static inline int
386cfs_hash_with_bigname(cfs_hash_t *hs)
387{
388 return (hs->hs_flags & CFS_HASH_BIGNAME) != 0;
389}
390
391static inline int
392cfs_hash_with_counter(cfs_hash_t *hs)
393{
394 return (hs->hs_flags & CFS_HASH_COUNTER) != 0;
395}
396
397static inline int
398cfs_hash_with_rehash(cfs_hash_t *hs)
399{
400 return (hs->hs_flags & CFS_HASH_REHASH) != 0;
401}
402
403static inline int
404cfs_hash_with_rehash_key(cfs_hash_t *hs)
405{
406 return (hs->hs_flags & CFS_HASH_REHASH_KEY) != 0;
407}
408
409static inline int
410cfs_hash_with_shrink(cfs_hash_t *hs)
411{
412 return (hs->hs_flags & CFS_HASH_SHRINK) != 0;
413}
414
415static inline int
416cfs_hash_with_assert_empty(cfs_hash_t *hs)
417{
418 return (hs->hs_flags & CFS_HASH_ASSERT_EMPTY) != 0;
419}
420
421static inline int
422cfs_hash_with_depth(cfs_hash_t *hs)
423{
424 return (hs->hs_flags & CFS_HASH_DEPTH) != 0;
425}
426
427static inline int
428cfs_hash_with_nblk_change(cfs_hash_t *hs)
429{
430 return (hs->hs_flags & CFS_HASH_NBLK_CHANGE) != 0;
431}
432
433static inline int
434cfs_hash_is_exiting(cfs_hash_t *hs)
435{
436 return hs->hs_exiting;
437}
438
439static inline int
440cfs_hash_is_rehashing(cfs_hash_t *hs)
441{
442 return hs->hs_rehash_bits != 0;
443}
444
445static inline int
446cfs_hash_is_iterating(cfs_hash_t *hs)
447{
448 return hs->hs_iterating || hs->hs_iterators != 0;
449}
450
451static inline int
452cfs_hash_bkt_size(cfs_hash_t *hs)
453{
454 return offsetof(cfs_hash_bucket_t, hsb_head[0]) +
455 hs->hs_hops->hop_hhead_size(hs) * CFS_HASH_BKT_NHLIST(hs) +
456 hs->hs_extra_bytes;
457}
458
459#define CFS_HOP(hs, op) (hs)->hs_ops->hs_ ## op
460
461static inline unsigned
462cfs_hash_id(cfs_hash_t *hs, const void *key, unsigned mask)
463{
464 return CFS_HOP(hs, hash)(hs, key, mask);
465}
466
467static inline void *
468cfs_hash_key(cfs_hash_t *hs, struct hlist_node *hnode)
469{
470 return CFS_HOP(hs, key)(hnode);
471}
472
473static inline void
474cfs_hash_keycpy(cfs_hash_t *hs, struct hlist_node *hnode, void *key)
475{
476 if (CFS_HOP(hs, keycpy) != NULL)
477 CFS_HOP(hs, keycpy)(hnode, key);
478}
479
480
481
482
483static inline int
484cfs_hash_keycmp(cfs_hash_t *hs, const void *key, struct hlist_node *hnode)
485{
486 return CFS_HOP(hs, keycmp)(key, hnode);
487}
488
489static inline void *
490cfs_hash_object(cfs_hash_t *hs, struct hlist_node *hnode)
491{
492 return CFS_HOP(hs, object)(hnode);
493}
494
495static inline void
496cfs_hash_get(cfs_hash_t *hs, struct hlist_node *hnode)
497{
498 return CFS_HOP(hs, get)(hs, hnode);
499}
500
501static inline void
502cfs_hash_put_locked(cfs_hash_t *hs, struct hlist_node *hnode)
503{
504 LASSERT(CFS_HOP(hs, put_locked) != NULL);
505
506 return CFS_HOP(hs, put_locked)(hs, hnode);
507}
508
509static inline void
510cfs_hash_put(cfs_hash_t *hs, struct hlist_node *hnode)
511{
512 LASSERT(CFS_HOP(hs, put) != NULL);
513
514 return CFS_HOP(hs, put)(hs, hnode);
515}
516
517static inline void
518cfs_hash_exit(cfs_hash_t *hs, struct hlist_node *hnode)
519{
520 if (CFS_HOP(hs, exit))
521 CFS_HOP(hs, exit)(hs, hnode);
522}
523
524static inline void cfs_hash_lock(cfs_hash_t *hs, int excl)
525{
526 hs->hs_lops->hs_lock(&hs->hs_lock, excl);
527}
528
529static inline void cfs_hash_unlock(cfs_hash_t *hs, int excl)
530{
531 hs->hs_lops->hs_unlock(&hs->hs_lock, excl);
532}
533
534static inline int cfs_hash_dec_and_lock(cfs_hash_t *hs,
535 atomic_t *condition)
536{
537 LASSERT(cfs_hash_with_no_bktlock(hs));
538 return atomic_dec_and_lock(condition, &hs->hs_lock.spin);
539}
540
541static inline void cfs_hash_bd_lock(cfs_hash_t *hs,
542 cfs_hash_bd_t *bd, int excl)
543{
544 hs->hs_lops->hs_bkt_lock(&bd->bd_bucket->hsb_lock, excl);
545}
546
547static inline void cfs_hash_bd_unlock(cfs_hash_t *hs,
548 cfs_hash_bd_t *bd, int excl)
549{
550 hs->hs_lops->hs_bkt_unlock(&bd->bd_bucket->hsb_lock, excl);
551}
552
553
554
555
556
557void cfs_hash_bd_get(cfs_hash_t *hs, const void *key, cfs_hash_bd_t *bd);
558
559static inline void cfs_hash_bd_get_and_lock(cfs_hash_t *hs, const void *key,
560 cfs_hash_bd_t *bd, int excl)
561{
562 cfs_hash_bd_get(hs, key, bd);
563 cfs_hash_bd_lock(hs, bd, excl);
564}
565
566static inline unsigned cfs_hash_bd_index_get(cfs_hash_t *hs, cfs_hash_bd_t *bd)
567{
568 return bd->bd_offset | (bd->bd_bucket->hsb_index << hs->hs_bkt_bits);
569}
570
571static inline void cfs_hash_bd_index_set(cfs_hash_t *hs,
572 unsigned index, cfs_hash_bd_t *bd)
573{
574 bd->bd_bucket = hs->hs_buckets[index >> hs->hs_bkt_bits];
575 bd->bd_offset = index & (CFS_HASH_BKT_NHLIST(hs) - 1U);
576}
577
578static inline void *
579cfs_hash_bd_extra_get(cfs_hash_t *hs, cfs_hash_bd_t *bd)
580{
581 return (void *)bd->bd_bucket +
582 cfs_hash_bkt_size(hs) - hs->hs_extra_bytes;
583}
584
585static inline __u32
586cfs_hash_bd_version_get(cfs_hash_bd_t *bd)
587{
588
589 return bd->bd_bucket->hsb_version;
590}
591
592static inline __u32
593cfs_hash_bd_count_get(cfs_hash_bd_t *bd)
594{
595
596 return bd->bd_bucket->hsb_count;
597}
598
599static inline int
600cfs_hash_bd_depmax_get(cfs_hash_bd_t *bd)
601{
602 return bd->bd_bucket->hsb_depmax;
603}
604
605static inline int
606cfs_hash_bd_compare(cfs_hash_bd_t *bd1, cfs_hash_bd_t *bd2)
607{
608 if (bd1->bd_bucket->hsb_index != bd2->bd_bucket->hsb_index)
609 return bd1->bd_bucket->hsb_index - bd2->bd_bucket->hsb_index;
610
611 if (bd1->bd_offset != bd2->bd_offset)
612 return bd1->bd_offset - bd2->bd_offset;
613
614 return 0;
615}
616
617void cfs_hash_bd_add_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd,
618 struct hlist_node *hnode);
619void cfs_hash_bd_del_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd,
620 struct hlist_node *hnode);
621void cfs_hash_bd_move_locked(cfs_hash_t *hs, cfs_hash_bd_t *bd_old,
622 cfs_hash_bd_t *bd_new, struct hlist_node *hnode);
623
624static inline int cfs_hash_bd_dec_and_lock(cfs_hash_t *hs, cfs_hash_bd_t *bd,
625 atomic_t *condition)
626{
627 LASSERT(cfs_hash_with_spin_bktlock(hs));
628 return atomic_dec_and_lock(condition,
629 &bd->bd_bucket->hsb_lock.spin);
630}
631
632static inline struct hlist_head *cfs_hash_bd_hhead(cfs_hash_t *hs,
633 cfs_hash_bd_t *bd)
634{
635 return hs->hs_hops->hop_hhead(hs, bd);
636}
637
638struct hlist_node *cfs_hash_bd_lookup_locked(cfs_hash_t *hs,
639 cfs_hash_bd_t *bd, const void *key);
640struct hlist_node *cfs_hash_bd_peek_locked(cfs_hash_t *hs,
641 cfs_hash_bd_t *bd, const void *key);
642struct hlist_node *cfs_hash_bd_findadd_locked(cfs_hash_t *hs,
643 cfs_hash_bd_t *bd, const void *key,
644 struct hlist_node *hnode,
645 int insist_add);
646struct hlist_node *cfs_hash_bd_finddel_locked(cfs_hash_t *hs,
647 cfs_hash_bd_t *bd, const void *key,
648 struct hlist_node *hnode);
649
650
651
652
653
654void cfs_hash_dual_bd_get(cfs_hash_t *hs, const void *key, cfs_hash_bd_t *bds);
655void cfs_hash_dual_bd_lock(cfs_hash_t *hs, cfs_hash_bd_t *bds, int excl);
656void cfs_hash_dual_bd_unlock(cfs_hash_t *hs, cfs_hash_bd_t *bds, int excl);
657
658static inline void cfs_hash_dual_bd_get_and_lock(cfs_hash_t *hs, const void *key,
659 cfs_hash_bd_t *bds, int excl)
660{
661 cfs_hash_dual_bd_get(hs, key, bds);
662 cfs_hash_dual_bd_lock(hs, bds, excl);
663}
664
665struct hlist_node *cfs_hash_dual_bd_lookup_locked(cfs_hash_t *hs,
666 cfs_hash_bd_t *bds,
667 const void *key);
668struct hlist_node *cfs_hash_dual_bd_findadd_locked(cfs_hash_t *hs,
669 cfs_hash_bd_t *bds,
670 const void *key,
671 struct hlist_node *hnode,
672 int insist_add);
673struct hlist_node *cfs_hash_dual_bd_finddel_locked(cfs_hash_t *hs,
674 cfs_hash_bd_t *bds,
675 const void *key,
676 struct hlist_node *hnode);
677
678
679cfs_hash_t *cfs_hash_create(char *name, unsigned cur_bits, unsigned max_bits,
680 unsigned bkt_bits, unsigned extra_bytes,
681 unsigned min_theta, unsigned max_theta,
682 cfs_hash_ops_t *ops, unsigned flags);
683
684cfs_hash_t *cfs_hash_getref(cfs_hash_t *hs);
685void cfs_hash_putref(cfs_hash_t *hs);
686
687
688void cfs_hash_add(cfs_hash_t *hs, const void *key,
689 struct hlist_node *hnode);
690int cfs_hash_add_unique(cfs_hash_t *hs, const void *key,
691 struct hlist_node *hnode);
692void *cfs_hash_findadd_unique(cfs_hash_t *hs, const void *key,
693 struct hlist_node *hnode);
694
695
696void *cfs_hash_del(cfs_hash_t *hs, const void *key, struct hlist_node *hnode);
697void *cfs_hash_del_key(cfs_hash_t *hs, const void *key);
698
699
700#define CFS_HASH_LOOP_HOG 1024
701
702typedef int (*cfs_hash_for_each_cb_t)(cfs_hash_t *hs, cfs_hash_bd_t *bd,
703 struct hlist_node *node, void *data);
704void *cfs_hash_lookup(cfs_hash_t *hs, const void *key);
705void cfs_hash_for_each(cfs_hash_t *hs, cfs_hash_for_each_cb_t, void *data);
706void cfs_hash_for_each_safe(cfs_hash_t *hs, cfs_hash_for_each_cb_t, void *data);
707int cfs_hash_for_each_nolock(cfs_hash_t *hs,
708 cfs_hash_for_each_cb_t, void *data);
709int cfs_hash_for_each_empty(cfs_hash_t *hs,
710 cfs_hash_for_each_cb_t, void *data);
711void cfs_hash_for_each_key(cfs_hash_t *hs, const void *key,
712 cfs_hash_for_each_cb_t, void *data);
713typedef int (*cfs_hash_cond_opt_cb_t)(void *obj, void *data);
714void cfs_hash_cond_del(cfs_hash_t *hs, cfs_hash_cond_opt_cb_t, void *data);
715
716void cfs_hash_hlist_for_each(cfs_hash_t *hs, unsigned hindex,
717 cfs_hash_for_each_cb_t, void *data);
718int cfs_hash_is_empty(cfs_hash_t *hs);
719__u64 cfs_hash_size_get(cfs_hash_t *hs);
720
721
722
723
724
725void cfs_hash_rehash_cancel_locked(cfs_hash_t *hs);
726void cfs_hash_rehash_cancel(cfs_hash_t *hs);
727int cfs_hash_rehash(cfs_hash_t *hs, int do_rehash);
728void cfs_hash_rehash_key(cfs_hash_t *hs, const void *old_key,
729 void *new_key, struct hlist_node *hnode);
730
731#if CFS_HASH_DEBUG_LEVEL > CFS_HASH_DEBUG_1
732
733static inline void
734cfs_hash_key_validate(cfs_hash_t *hs, const void *key,
735 struct hlist_node *hnode)
736{
737 LASSERT(cfs_hash_keycmp(hs, key, hnode));
738}
739
740
741static inline void
742cfs_hash_bucket_validate(cfs_hash_t *hs, cfs_hash_bd_t *bd,
743 struct hlist_node *hnode)
744{
745 cfs_hash_bd_t bds[2];
746
747 cfs_hash_dual_bd_get(hs, cfs_hash_key(hs, hnode), bds);
748 LASSERT(bds[0].bd_bucket == bd->bd_bucket ||
749 bds[1].bd_bucket == bd->bd_bucket);
750}
751
752#else
753
754static inline void
755cfs_hash_key_validate(cfs_hash_t *hs, const void *key,
756 struct hlist_node *hnode) {}
757
758static inline void
759cfs_hash_bucket_validate(cfs_hash_t *hs, cfs_hash_bd_t *bd,
760 struct hlist_node *hnode) {}
761
762#endif
763
764#define CFS_HASH_THETA_BITS 10
765#define CFS_HASH_MIN_THETA (1U << (CFS_HASH_THETA_BITS - 1))
766#define CFS_HASH_MAX_THETA (1U << (CFS_HASH_THETA_BITS + 1))
767
768
769static inline int __cfs_hash_theta_int(int theta)
770{
771 return (theta >> CFS_HASH_THETA_BITS);
772}
773
774
775static inline int __cfs_hash_theta_frac(int theta)
776{
777 return ((theta * 1000) >> CFS_HASH_THETA_BITS) -
778 (__cfs_hash_theta_int(theta) * 1000);
779}
780
781static inline int __cfs_hash_theta(cfs_hash_t *hs)
782{
783 return (atomic_read(&hs->hs_count) <<
784 CFS_HASH_THETA_BITS) >> hs->hs_cur_bits;
785}
786
787static inline void __cfs_hash_set_theta(cfs_hash_t *hs, int min, int max)
788{
789 LASSERT(min < max);
790 hs->hs_min_theta = (__u16)min;
791 hs->hs_max_theta = (__u16)max;
792}
793
794
795struct seq_file;
796int cfs_hash_debug_header(struct seq_file *m);
797int cfs_hash_debug_str(cfs_hash_t *hs, struct seq_file *m);
798
799
800
801
802static inline unsigned
803cfs_hash_djb2_hash(const void *key, size_t size, unsigned mask)
804{
805 unsigned i, hash = 5381;
806
807 LASSERT(key != NULL);
808
809 for (i = 0; i < size; i++)
810 hash = hash * 33 + ((char *)key)[i];
811
812 return (hash & mask);
813}
814
815
816
817
818static inline unsigned
819cfs_hash_u32_hash(const __u32 key, unsigned mask)
820{
821 return ((key * CFS_GOLDEN_RATIO_PRIME_32) & mask);
822}
823
824
825
826
827static inline unsigned
828cfs_hash_u64_hash(const __u64 key, unsigned mask)
829{
830 return ((unsigned)(key * CFS_GOLDEN_RATIO_PRIME_64) & mask);
831}
832
833
834#define cfs_hash_for_each_bd(bds, n, i) \
835 for (i = 0; i < n && (bds)[i].bd_bucket != NULL; i++)
836
837
838#define cfs_hash_for_each_bucket(hs, bd, pos) \
839 for (pos = 0; \
840 pos < CFS_HASH_NBKT(hs) && \
841 ((bd)->bd_bucket = (hs)->hs_buckets[pos]) != NULL; pos++)
842
843
844#define cfs_hash_bd_for_each_hlist(hs, bd, hlist) \
845 for ((bd)->bd_offset = 0; \
846 (bd)->bd_offset < CFS_HASH_BKT_NHLIST(hs) && \
847 (hlist = cfs_hash_bd_hhead(hs, bd)) != NULL; \
848 (bd)->bd_offset++)
849
850
851#endif
852