Linus Torvalds | 9027f53 | 2007-10-25 11:23:26 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Some generic hashing helpers. |
| 3 | */ |
| 4 | #include "cache.h" |
| 5 | #include "hash.h" |
| 6 | |
| 7 | /* |
| 8 | * Look up a hash entry in the hash table. Return the pointer to |
| 9 | * the existing entry, or the empty slot if none existed. The caller |
| 10 | * can then look at the (*ptr) to see whether it existed or not. |
| 11 | */ |
Linus Torvalds | d1f128b | 2008-03-06 12:46:09 -0800 | [diff] [blame] | 12 | static struct hash_table_entry *lookup_hash_entry(unsigned int hash, const struct hash_table *table) |
Linus Torvalds | 9027f53 | 2007-10-25 11:23:26 -0700 | [diff] [blame] | 13 | { |
| 14 | unsigned int size = table->size, nr = hash % size; |
| 15 | struct hash_table_entry *array = table->array; |
| 16 | |
| 17 | while (array[nr].ptr) { |
| 18 | if (array[nr].hash == hash) |
| 19 | break; |
| 20 | nr++; |
| 21 | if (nr >= size) |
| 22 | nr = 0; |
| 23 | } |
| 24 | return array + nr; |
| 25 | } |
| 26 | |
| 27 | |
| 28 | /* |
| 29 | * Insert a new hash entry pointer into the table. |
| 30 | * |
| 31 | * If that hash entry already existed, return the pointer to |
| 32 | * the existing entry (and the caller can create a list of the |
| 33 | * pointers or do anything else). If it didn't exist, return |
| 34 | * NULL (and the caller knows the pointer has been inserted). |
| 35 | */ |
| 36 | static void **insert_hash_entry(unsigned int hash, void *ptr, struct hash_table *table) |
| 37 | { |
| 38 | struct hash_table_entry *entry = lookup_hash_entry(hash, table); |
| 39 | |
| 40 | if (!entry->ptr) { |
| 41 | entry->ptr = ptr; |
| 42 | entry->hash = hash; |
| 43 | table->nr++; |
| 44 | return NULL; |
| 45 | } |
| 46 | return &entry->ptr; |
| 47 | } |
| 48 | |
| 49 | static void grow_hash_table(struct hash_table *table) |
| 50 | { |
| 51 | unsigned int i; |
| 52 | unsigned int old_size = table->size, new_size; |
| 53 | struct hash_table_entry *old_array = table->array, *new_array; |
| 54 | |
| 55 | new_size = alloc_nr(old_size); |
| 56 | new_array = xcalloc(sizeof(struct hash_table_entry), new_size); |
| 57 | table->size = new_size; |
| 58 | table->array = new_array; |
| 59 | table->nr = 0; |
| 60 | for (i = 0; i < old_size; i++) { |
| 61 | unsigned int hash = old_array[i].hash; |
| 62 | void *ptr = old_array[i].ptr; |
| 63 | if (ptr) |
| 64 | insert_hash_entry(hash, ptr, table); |
| 65 | } |
| 66 | free(old_array); |
| 67 | } |
| 68 | |
Linus Torvalds | d1f128b | 2008-03-06 12:46:09 -0800 | [diff] [blame] | 69 | void *lookup_hash(unsigned int hash, const struct hash_table *table) |
Linus Torvalds | 9027f53 | 2007-10-25 11:23:26 -0700 | [diff] [blame] | 70 | { |
| 71 | if (!table->array) |
| 72 | return NULL; |
Jeff King | 9ea0980 | 2008-02-22 14:47:27 -0500 | [diff] [blame] | 73 | return lookup_hash_entry(hash, table)->ptr; |
Linus Torvalds | 9027f53 | 2007-10-25 11:23:26 -0700 | [diff] [blame] | 74 | } |
| 75 | |
| 76 | void **insert_hash(unsigned int hash, void *ptr, struct hash_table *table) |
| 77 | { |
| 78 | unsigned int nr = table->nr; |
| 79 | if (nr >= table->size/2) |
| 80 | grow_hash_table(table); |
| 81 | return insert_hash_entry(hash, ptr, table); |
| 82 | } |
| 83 | |
Linus Torvalds | 11f944d | 2011-02-18 19:55:19 -0800 | [diff] [blame] | 84 | int for_each_hash(const struct hash_table *table, int (*fn)(void *, void *), void *data) |
Linus Torvalds | 9027f53 | 2007-10-25 11:23:26 -0700 | [diff] [blame] | 85 | { |
| 86 | int sum = 0; |
| 87 | unsigned int i; |
| 88 | unsigned int size = table->size; |
| 89 | struct hash_table_entry *array = table->array; |
| 90 | |
| 91 | for (i = 0; i < size; i++) { |
| 92 | void *ptr = array->ptr; |
| 93 | array++; |
| 94 | if (ptr) { |
Linus Torvalds | 11f944d | 2011-02-18 19:55:19 -0800 | [diff] [blame] | 95 | int val = fn(ptr, data); |
Linus Torvalds | 9027f53 | 2007-10-25 11:23:26 -0700 | [diff] [blame] | 96 | if (val < 0) |
| 97 | return val; |
| 98 | sum += val; |
| 99 | } |
| 100 | } |
| 101 | return sum; |
| 102 | } |
| 103 | |
| 104 | void free_hash(struct hash_table *table) |
| 105 | { |
| 106 | free(table->array); |
| 107 | table->array = NULL; |
| 108 | table->size = 0; |
| 109 | table->nr = 0; |
| 110 | } |