t7201.24: Add refspec to keep --track working
[git] / hash.c
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  */
12 static struct hash_table_entry *lookup_hash_entry(unsigned int hash, const struct hash_table *table)
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
69 void *lookup_hash(unsigned int hash, const struct hash_table *table)
70 {
71         if (!table->array)
72                 return NULL;
73         return lookup_hash_entry(hash, table)->ptr;
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
84 int for_each_hash(const struct hash_table *table, int (*fn)(void *, void *), void *data)
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) {
95                         int val = fn(ptr, data);
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 }