1 //
2 // Copyright (C) 2013-2014 Nick Gasson
3 //
4 // This program is free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 //
17
18 #include "hash.h"
19
20 #include <stdlib.h>
21 #include <string.h>
22 #include <assert.h>
23
24 struct hash {
25 unsigned size;
26 unsigned members;
27 bool replace;
28 void **values;
29 const void **keys;
30 };
31
hash_slot(hash_t * h,const void * key)32 static inline int hash_slot(hash_t *h, const void *key)
33 {
34 assert(key != NULL);
35
36 uintptr_t uptr = (uintptr_t)key;
37
38 // Bottom two bits will always be zero with 32-bit pointers
39 uptr >>= 2;
40
41 // Hash function from here:
42 // http://burtleburtle.net/bob/hash/integer.html
43
44 uint32_t a = (uint32_t)uptr;
45 a = (a ^ 61) ^ (a >> 16);
46 a = a + (a << 3);
47 a = a ^ (a >> 4);
48 a = a * UINT32_C(0x27d4eb2d);
49 a = a ^ (a >> 15);
50
51 return a & (h->size - 1);
52 }
53
hash_new(int size,bool replace)54 hash_t *hash_new(int size, bool replace)
55 {
56 struct hash *h = xmalloc(sizeof(struct hash));
57 h->size = next_power_of_2(size);
58 h->members = 0;
59 h->replace = replace;
60
61 char *mem = xcalloc(h->size * 2 * sizeof(void *));
62 h->values = (void **)mem;
63 h->keys = (const void **)(mem + (h->size * sizeof(void *)));
64
65 return h;
66 }
67
hash_free(hash_t * h)68 void hash_free(hash_t *h)
69 {
70 free(h->values);
71 free(h);
72 }
73
hash_put(hash_t * h,const void * key,void * value)74 bool hash_put(hash_t *h, const void *key, void *value)
75 {
76 if (unlikely(h->members >= h->size / 2)) {
77 // Rebuild the hash table with a larger size
78 // This is expensive so a conservative initial size should be chosen
79
80 const int old_size = h->size;
81 h->size *= 2;
82
83 const void **old_keys = h->keys;
84 void **old_values = h->values;
85
86 char *mem = xcalloc(h->size * 2 * sizeof(void *));
87 h->values = (void **)mem;
88 h->keys = (const void **)(mem + (h->size * sizeof(void *)));
89
90 h->members = 0;
91
92 for (int i = 0; i < old_size; i++) {
93 if (old_keys[i] != NULL)
94 hash_put(h, old_keys[i], old_values[i]);
95 }
96
97 free(old_values);
98 }
99
100 int slot = hash_slot(h, key);
101
102 for (; ; slot = (slot + 1) & (h->size - 1)) {
103 if ((h->keys[slot] == key) && h->replace) {
104 h->values[slot] = value;
105 return true;
106 }
107 else if (h->keys[slot] == NULL) {
108 h->values[slot] = value;
109 h->keys[slot] = key;
110 h->members++;
111 break;
112 }
113 }
114
115 return false;
116 }
117
hash_get_nth(hash_t * h,const void * key,int * n)118 void *hash_get_nth(hash_t *h, const void *key, int *n)
119 {
120 int slot = hash_slot(h, key);
121
122 for (; ; slot = (slot + 1) & (h->size - 1)) {
123 if (h->keys[slot] == key) {
124 if (*n == 0)
125 return h->values[slot];
126 else
127 --(*n);
128 }
129 else if (h->keys[slot] == NULL)
130 return NULL;
131 }
132 }
133
hash_get(hash_t * h,const void * key)134 void *hash_get(hash_t *h, const void *key)
135 {
136 int n = 0;
137 return hash_get_nth(h, key, &n);
138 }
139
hash_replace(hash_t * h,void * value,void * with)140 void hash_replace(hash_t *h, void *value, void *with)
141 {
142 for (int i = 0; i < h->size; i++) {
143 if (h->values[i] == value)
144 h->values[i] = with;
145 }
146 }
147
hash_iter(hash_t * h,hash_iter_t * now,const void ** key,void ** value)148 bool hash_iter(hash_t *h, hash_iter_t *now, const void **key, void **value)
149 {
150 assert(*now != HASH_END);
151
152 while (*now < h->size) {
153 const unsigned old = (*now)++;
154 if (h->keys[old] != NULL) {
155 *key = h->keys[old];
156 *value = h->values[old];
157 return true;
158 }
159 }
160
161 *now = HASH_END;
162 return false;
163 }
164
hash_members(hash_t * h)165 unsigned hash_members(hash_t *h)
166 {
167 return h->members;
168 }
169