1 /*
2 +----------------------------------------------------------------------+
3 | See COPYING file for further copyright information |
4 +----------------------------------------------------------------------+
5 | Author: Oleg Grenrus <oleg.grenrus@dynamoid.com> |
6 | See CREDITS for contributors |
7 +----------------------------------------------------------------------+
8 */
9
10 #ifdef PHP_WIN32
11 # include "ig_win32.h"
12 #endif
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <string.h>
17
18 #include <assert.h>
19
20 #include "hash.h"
21 #include "zend.h"
22
23 /* {{{ nextpow2 */
24 /** Next power of 2.
25 * @param n Integer.
26 * @return the smallest power of 2 that is >= n.
27 */
nextpow2(uint32_t n)28 inline static uint32_t nextpow2(uint32_t n) {
29 uint32_t m = 1;
30 while (m < n) {
31 m = m << 1;
32 }
33
34 return m;
35 }
36 /* }}} */
37 /* {{{ hash_si_init */
38 /**
39 * Initializes a hash_si value with the given capacity
40 */
hash_si_init(struct hash_si * h,uint32_t size)41 int hash_si_init(struct hash_si *h, uint32_t size) {
42 size = nextpow2(size);
43
44 h->mask = size - 1;
45 h->used = 0;
46 h->data = (struct hash_si_pair *)ecalloc(size, sizeof(struct hash_si_pair));
47 if (h->data == NULL) {
48 return 1;
49 }
50
51 return 0;
52 }
53 /* }}} */
54 /* {{{ hash_si_deinit */
hash_si_deinit(struct hash_si * h)55 void hash_si_deinit(struct hash_si *h) {
56 size_t i;
57 const size_t mask = h->mask;
58 struct hash_si_pair *const data = h->data;
59
60 for (i = 0; i <= mask; i++) {
61 if (data[i].key_zstr != NULL) {
62 zend_string_release(data[i].key_zstr);
63 }
64 }
65
66 efree(data);
67 }
68 /* }}} */
69 /* {{{ get_key_hash */
get_key_hash(zend_string * key_zstr)70 inline static uint32_t get_key_hash(zend_string *key_zstr) {
71 uint32_t key_hash = ZSTR_HASH(key_zstr);
72 #if SIZEOF_ZEND_LONG > 4
73 if (UNEXPECTED(key_hash == 0)) {
74 /* A key_hash of uint32_t(0) would be treated like a gap when inserted. Change the hash used to 1 instead. */
75 /* uint32_t(ZSTR_HASH) is 0 for 1 in 4 billion - optimized builds may use cmove so there are no branch mispredicts, changing to key_hash >> 32 doesn't speed up benchmark/serialize-stringarray */
76 return 1;
77 }
78 #endif
79 return key_hash;
80 }
81 /* }}} */
82 /* {{{ hash_si_rehash */
83 /** Rehash/resize hash_si.
84 * @param h Pointer to hash_si struct.
85 */
hash_si_rehash(struct hash_si * h)86 inline static void hash_si_rehash(struct hash_si *h) {
87 size_t i;
88 size_t old_size;
89 size_t new_size;
90 size_t new_mask;
91 struct hash_si_pair *old_data;
92 struct hash_si_pair *new_data;
93
94 /* Allocate a table with double the capacity (the next power of 2). */
95 ZEND_ASSERT(h != NULL);
96 old_size = h->mask + 1;
97 new_size = old_size * 2;
98 new_mask = new_size - 1;
99
100 old_data = h->data;
101 new_data = (struct hash_si_pair *)ecalloc(new_size, sizeof(struct hash_si_pair));
102 h->data = new_data;
103 h->mask = new_mask;
104
105 /* Copy old entries to new entries */
106 for (i = 0; i < old_size; i++) {
107 const struct hash_si_pair *old_pair = &old_data[i];
108 if (old_pair->key_zstr != NULL) {
109 uint32_t hv = old_pair->key_hash & new_mask;
110 /* We already computed the hash, avoid recomputing it. */
111 /* Do linear probing for the next free slot. */
112 while (new_data[hv].key_hash != 0) {
113 hv = (hv + 1) & new_mask;
114 }
115 new_data[hv] = old_data[i];
116 }
117 }
118
119 /* Free old entries */
120 efree(old_data);
121 }
122 /* }}} */
123 /**
124 * If the string key already exists in the map, return the associated value.
125 * If it doesn't exist, indicate that to the caller.
126 */
hash_si_find_or_insert(struct hash_si * h,zend_string * key_zstr,uint32_t value)127 struct hash_si_result hash_si_find_or_insert(struct hash_si *h, zend_string *key_zstr, uint32_t value) {
128 struct hash_si_result result;
129 struct hash_si_pair *pair;
130 struct hash_si_pair *data;
131 uint32_t key_hash = get_key_hash(key_zstr);
132 size_t mask;
133 uint32_t hv;
134
135 ZEND_ASSERT(h != NULL);
136
137 mask = h->mask;
138 hv = key_hash & mask;
139 data = h->data;
140
141 while (1) {
142 pair = &data[hv];
143 if (pair->key_hash == 0) {
144 /* This is a brand new key */
145 pair->key_zstr = key_zstr;
146 pair->key_hash = key_hash;
147 pair->value = value;
148 h->used++;
149
150 /* The size increased, so check if we need to expand the map */
151 if (h->mask * 3 / 4 < h->used) {
152 hash_si_rehash(h);
153 }
154 result.code = hash_si_code_inserted;
155 zend_string_addref(key_zstr);
156 return result;
157 } else if (pair->key_hash == key_hash && EXPECTED(zend_string_equals(pair->key_zstr, key_zstr))) {
158 /* This already exists in the hash map */
159 result.code = hash_si_code_exists;
160 result.value = pair->value;
161 return result;
162 }
163 /* linear prob */
164 hv = (hv + 1) & mask;
165 }
166 }
167 /* }}} */
168 /* {{{ hash_si_traverse */
169 /*
170 void hash_si_traverse(struct hash_si *h, int (*traverse_function) (const char *key, size_t key_len, uint32_t value)) {
171 size_t i;
172
173 assert(h != NULL && traverse_function != NULL);
174
175 for (i = 0; i < h->size; i++) {
176 if (h->data[i].key != NULL && traverse_function(h->data[i].key, h->data[i].key_len, h->data[i].value) != 1) {
177 return;
178 }
179 }
180 }
181 */
182 /* }}} */
183 /* {{{ hash_si_size */
184 /** Returns the number of elements in the hash map h. */
hash_si_size(struct hash_si * h)185 size_t hash_si_size(struct hash_si *h) {
186 assert(h != NULL);
187
188 return h->used;
189 }
190 /* }}} */
191 /* {{{ hash_si_capacity */
192 /** Returns the capacity of the hash map h */
hash_si_capacity(struct hash_si * h)193 size_t hash_si_capacity(struct hash_si *h) {
194 assert(h != NULL);
195
196 return h->mask + 1;
197 }
198 /* }}} */
199
200 /*
201 * Local variables:
202 * tab-width: 2
203 * c-basic-offset: 4
204 * End:
205 * vim600: noet sw=4 ts=4 fdm=marker
206 * vim<600: noet sw=4 ts=4
207 */
208