Commit | Line | Data |
---|---|---|
9027f53c LT |
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 | */ | |
d1f128b0 | 12 | static struct hash_table_entry *lookup_hash_entry(unsigned int hash, const struct hash_table *table) |
9027f53c LT |
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 | ||
d1f128b0 | 69 | void *lookup_hash(unsigned int hash, const struct hash_table *table) |
9027f53c LT |
70 | { |
71 | if (!table->array) | |
72 | return NULL; | |
9ea0980a | 73 | return lookup_hash_entry(hash, table)->ptr; |
9027f53c LT |
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 | ||
11f944dd | 84 | int for_each_hash(const struct hash_table *table, int (*fn)(void *, void *), void *data) |
9027f53c LT |
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) { | |
11f944dd | 95 | int val = fn(ptr, data); |
9027f53c LT |
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 | } |