Lines Matching full:table
34 * chash_table_alloc - Allocate closed hash table
35 * @table: Pointer to the table structure
36 * @bits: Table size will be 2^bits entries
40 int chash_table_alloc(struct chash_table *table, u8 bits, u8 key_size, in chash_table_alloc() argument
49 table->data = kcalloc(__CHASH_DATA_SIZE(bits, key_size, value_size), in chash_table_alloc()
51 if (!table->data) in chash_table_alloc()
54 __CHASH_TABLE_INIT(table->table, table->data, in chash_table_alloc()
62 * chash_table_free - Free closed hash table
63 * @table: Pointer to the table structure
65 void chash_table_free(struct chash_table *table) in chash_table_free() argument
67 kfree(table->data); in chash_table_free()
91 void __chash_table_dump_stats(struct __chash_table *table) in __chash_table_dump_stats() argument
93 struct chash_iter iter = CHASH_ITER_INIT(table, 0); in __chash_table_dump_stats()
109 table->key_size, table->value_size); in __chash_table_dump_stats()
111 1 << table->bits, filled, empty, tombstones); in __chash_table_dump_stats()
112 if (table->hits > 0) { in __chash_table_dump_stats()
113 DIV_FRAC(table->hits_steps, table->hits, quot1, frac1, 1000); in __chash_table_dump_stats()
114 DIV_FRAC(table->hits * 1000, table->hits_time_ns, in __chash_table_dump_stats()
121 table->hits, quot1, frac1, quot2, frac2); in __chash_table_dump_stats()
122 if (table->miss > 0) { in __chash_table_dump_stats()
123 DIV_FRAC(table->miss_steps, table->miss, quot1, frac1, 1000); in __chash_table_dump_stats()
124 DIV_FRAC(table->miss * 1000, table->miss_time_ns, in __chash_table_dump_stats()
131 table->miss, quot1, frac1, quot2, frac2); in __chash_table_dump_stats()
132 if (table->hits + table->miss > 0) { in __chash_table_dump_stats()
133 DIV_FRAC(table->hits_steps + table->miss_steps, in __chash_table_dump_stats()
134 table->hits + table->miss, quot1, frac1, 1000); in __chash_table_dump_stats()
135 DIV_FRAC((table->hits + table->miss) * 1000, in __chash_table_dump_stats()
136 (table->hits_time_ns + table->miss_time_ns), in __chash_table_dump_stats()
143 table->hits + table->miss, quot1, frac1, quot2, frac2); in __chash_table_dump_stats()
144 if (table->relocs > 0) { in __chash_table_dump_stats()
145 DIV_FRAC(table->hits + table->miss, table->relocs, in __chash_table_dump_stats()
147 DIV_FRAC(table->reloc_dist, table->relocs, quot2, frac2, 1000); in __chash_table_dump_stats()
149 table->relocs, quot1, frac1, quot2, frac2); in __chash_table_dump_stats()
159 #define CHASH_INC(table, a) ((a) = ((a) + 1) & (table)->size_mask) argument
160 #define CHASH_ADD(table, a, b) (((a) + (b)) & (table)->size_mask) argument
161 #define CHASH_SUB(table, a, b) (((a) - (b)) & (table)->size_mask) argument
162 #define CHASH_IN_RANGE(table, slot, first, last) \ argument
163 (CHASH_SUB(table, slot, first) <= CHASH_SUB(table, last, first))
167 static void chash_table_dump(struct __chash_table *table) in chash_table_dump() argument
169 struct chash_iter iter = CHASH_ITER_INIT(table, 0); in chash_table_dump()
192 static int chash_table_check(struct __chash_table *table) in chash_table_check() argument
195 struct chash_iter iter = CHASH_ITER_INIT(table, 0); in chash_table_check()
196 struct chash_iter cur = CHASH_ITER_INIT(table, 0); in chash_table_check()
210 chash_table_dump(table); in chash_table_check()
225 BUG_ON(src.table == dst.table && src.slot == dst.slot); in chash_iter_relocate()
226 BUG_ON(src.table->key_size != dst.table->key_size); in chash_iter_relocate()
227 BUG_ON(src.table->value_size != dst.table->value_size); in chash_iter_relocate()
229 if (dst.table->key_size == 4) in chash_iter_relocate()
230 dst.table->keys32[dst.slot] = src.table->keys32[src.slot]; in chash_iter_relocate()
232 dst.table->keys64[dst.slot] = src.table->keys64[src.slot]; in chash_iter_relocate()
234 if (dst.table->value_size) in chash_iter_relocate()
236 dst.table->value_size); in chash_iter_relocate()
242 if (src.table == dst.table) { in chash_iter_relocate()
243 dst.table->relocs++; in chash_iter_relocate()
244 dst.table->reloc_dist += in chash_iter_relocate()
245 CHASH_SUB(dst.table, src.slot, dst.slot); in chash_iter_relocate()
251 * __chash_table_find - Helper for looking up a hash table entry
252 * @iter: Pointer to hash table iterator
256 * Searches for an entry in the hash table with a given key. iter must
258 * hypothetical entry, i.e. it must be initialized with the hash table
271 * key. If the table is full, the slot is set to -1.
280 struct chash_iter first_redundant = CHASH_ITER_INIT(iter->table, -1); in chash_table_find()
298 chash_table_check(iter->table); in chash_table_find()
321 if (!CHASH_IN_RANGE(iter->table, cur_hash, in chash_table_find()
340 CHASH_ITER_INIT(iter->table, cur_hash); in chash_table_find()
359 iter->table->hits++; in chash_table_find()
360 iter->table->hits_steps += CHASH_SUB(iter->table, iter->slot, hash) + 1; in chash_table_find()
371 iter->table->hits_time_ns += local_clock() - ts1; in chash_table_find()
378 iter->table->miss++; in chash_table_find()
379 iter->table->miss_steps += (iter->slot < 0) ? in chash_table_find()
380 (1 << iter->table->bits) : in chash_table_find()
381 CHASH_SUB(iter->table, iter->slot, hash) + 1; in chash_table_find()
388 iter->table->miss_time_ns += local_clock() - ts1; in chash_table_find()
394 int __chash_table_copy_in(struct __chash_table *table, u64 key, in __chash_table_copy_in() argument
397 u32 hash = (table->key_size == 4) ? in __chash_table_copy_in()
398 hash_32(key, table->bits) : hash_64(key, table->bits); in __chash_table_copy_in()
399 struct chash_iter iter = CHASH_ITER_INIT(table, hash); in __chash_table_copy_in()
404 if (value && table->value_size) in __chash_table_copy_in()
406 table->value_size); in __chash_table_copy_in()
412 pr_err("Hash table overflow\n"); in __chash_table_copy_in()
418 if (table->key_size == 4) in __chash_table_copy_in()
419 table->keys32[iter.slot] = key; in __chash_table_copy_in()
421 table->keys64[iter.slot] = key; in __chash_table_copy_in()
422 if (value && table->value_size) in __chash_table_copy_in()
423 memcpy(chash_iter_value(iter), value, table->value_size); in __chash_table_copy_in()
429 int __chash_table_copy_out(struct __chash_table *table, u64 key, in __chash_table_copy_out() argument
432 u32 hash = (table->key_size == 4) ? in __chash_table_copy_out()
433 hash_32(key, table->bits) : hash_64(key, table->bits); in __chash_table_copy_out()
434 struct chash_iter iter = CHASH_ITER_INIT(table, hash); in __chash_table_copy_out()
440 if (value && table->value_size) in __chash_table_copy_out()
441 memcpy(value, chash_iter_value(iter), table->value_size); in __chash_table_copy_out()
452 * chash_self_test - Run a self-test of the hash table implementation
453 * @bits: Table size will be 2^bits entries
459 * The test adds and removes entries from a hash table, cycling the
467 struct chash_table table; in chash_self_test() local
477 ret = chash_table_alloc(&table, bits, key_size, sizeof(u64), in chash_self_test()
498 ret = chash_table_copy_out(&table, find_count, in chash_self_test()
509 chash_table_dump(&table.table); in chash_self_test()
514 ret = chash_table_copy_in(&table, find_count, in chash_self_test()
525 ret = chash_table_remove(&table, rmv_count, in chash_self_test()
537 ret = chash_table_copy_in(&table, add_count, &value); in chash_self_test()
546 chash_table_dump_stats(&table); in chash_self_test()
547 chash_table_reset_stats(&table); in chash_self_test()
550 chash_table_free(&table); in chash_self_test()
598 pr_err("chash: test_minfill too big. Must be < table size.\n"); in chash_init()
602 pr_err("chash: test_maxfill too big. Must be < table size.\n"); in chash_init()
637 MODULE_DESCRIPTION("Closed hash table");