Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 111 lines (98 sloc) 2.6 kb
9027f53 Linus Torvalds Do linear-time/space rename logic for exact renames
torvalds authored
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 */
d1f128b Linus Torvalds Add 'const' where appropriate to index handling functions
torvalds authored
12 static struct hash_table_entry *lookup_hash_entry(unsigned int hash, const struct hash_table *table)
9027f53 Linus Torvalds Do linear-time/space rename logic for exact renames
torvalds authored
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
d1f128b Linus Torvalds Add 'const' where appropriate to index handling functions
torvalds authored
69 void *lookup_hash(unsigned int hash, const struct hash_table *table)
9027f53 Linus Torvalds Do linear-time/space rename logic for exact renames
torvalds authored
70 {
71 if (!table->array)
72 return NULL;
9ea0980 Jeff King hash: fix lookup_hash semantics
peff authored
73 return lookup_hash_entry(hash, table)->ptr;
9027f53 Linus Torvalds Do linear-time/space rename logic for exact renames
torvalds authored
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
11f944d Linus Torvalds for_each_hash: allow passing a 'void *data' pointer to callback
torvalds authored
84 int for_each_hash(const struct hash_table *table, int (*fn)(void *, void *), void *data)
9027f53 Linus Torvalds Do linear-time/space rename logic for exact renames
torvalds authored
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) {
11f944d Linus Torvalds for_each_hash: allow passing a 'void *data' pointer to callback
torvalds authored
95 int val = fn(ptr, data);
9027f53 Linus Torvalds Do linear-time/space rename logic for exact renames
torvalds authored
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 }
Something went wrong with that request. Please try again.