1 /*
2 +----------------------------------------------------------------------+
3 | See COPYING file for further copyright information |
4 | This is a specialized hash map mapping uintprt_t to int32_t |
5 +----------------------------------------------------------------------+
6 | Author: Oleg Grenrus <oleg.grenrus@dynamoid.com> |
7 | Modified by Tyson Andre for fixed size, removing unused functions |
8 | See CREDITS for contributors |
9 +----------------------------------------------------------------------+
10 */
11
12 #include <stdint.h>
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <string.h>
17
18 #include <assert.h>
19
20 #include "hash_ptr.h"
21 #include "zend.h"
22 #include "igbinary_bswap.h"
23
24 /* This assumes that pointers differ in low addresses rather than high addresses */
inline_hash_of_address(zend_uintptr_t ptr)25 inline static uint32_t inline_hash_of_address(zend_uintptr_t ptr) {
26 #if UINTPTR_MAX > UINT32_MAX
27 uint64_t hash = ptr;
28 hash *= 0x5e2d58d8b3bce8d9;
29 // This is a single assembly instruction on recent compilers/platforms
30 hash = bswap_64(hash);
31 return hash;
32 #else
33 uint32_t hash = ptr;
34 hash *= 0x5e2d58d9;
35 // This is a single assembly instruction on recent compilers/platforms
36 hash = bswap_32(hash);
37 return hash;
38 #endif
39 }
40
41 /* {{{ nextpow2 */
42 /** Next power of 2.
43 * @param n Integer.
44 * @return next to n power of 2 .
45 */
nextpow2(uint32_t n)46 inline static uint32_t nextpow2(uint32_t n) {
47 uint32_t m = 1;
48 while (m < n) {
49 m = m << 1;
50 }
51
52 return m;
53 }
54 /* }}} */
55 /* {{{ hash_si_ptr_init */
56 /**
57 * @param h the pointer to the hash map that will be initialized in place
58 * @param size the new capacity of the hash map
59 */
hash_si_ptr_init(struct hash_si_ptr * h,size_t size)60 int hash_si_ptr_init(struct hash_si_ptr *h, size_t size) {
61 size = nextpow2(size);
62
63 h->size = size;
64 h->used = 0;
65 /* Set everything to 0. sets keys to HASH_PTR_KEY_INVALID. */
66 h->data = (struct hash_si_ptr_pair *)ecalloc(size, sizeof(struct hash_si_ptr_pair));
67 if (h->data == NULL) {
68 return 1;
69 }
70
71 return 0;
72 }
73 /* }}} */
74 /* {{{ hash_si_ptr_deinit */
75 /**
76 * Frees the hash map h
77 * @param h Pointer to the hash map (hash_si_ptr struct) to free internal data structures of
78 */
hash_si_ptr_deinit(struct hash_si_ptr * h)79 void hash_si_ptr_deinit(struct hash_si_ptr *h) {
80 efree(h->data);
81 h->data = NULL;
82
83 h->size = 0;
84 h->used = 0;
85 }
86 /* }}} */
87 /* {{{ hash_si_ptr_rehash */
88 /** Rehash/resize hash_si_ptr.
89 * @param h Pointer to hash_si_ptr struct.
90 */
hash_si_ptr_rehash(struct hash_si_ptr * h)91 inline static void hash_si_ptr_rehash(struct hash_si_ptr *h) {
92 size_t i;
93 size_t old_size;
94 size_t size;
95 size_t mask;
96 struct hash_si_ptr_pair *old_data;
97 struct hash_si_ptr_pair *new_data;
98
99 ZEND_ASSERT(h != NULL);
100
101 /* Allocate a table with double the capacity (the next power of 2). */
102 old_size = h->size;
103 size = old_size * 2;
104 mask = size - 1;
105 old_data = h->data;
106 new_data = (struct hash_si_ptr_pair *)ecalloc(size, sizeof(struct hash_si_ptr_pair));
107
108 h->size = size;
109 h->data = new_data;
110
111 /* Copy old entries to new entries */
112 for (i = 0; i < old_size; i++) {
113 if (old_data[i].key != HASH_PTR_KEY_INVALID) {
114 uint32_t hv = inline_hash_of_address(old_data[i].key) & mask;
115
116 /* Do linear probing for the next free slot. */
117 while (new_data[hv].key != HASH_PTR_KEY_INVALID) {
118 ZEND_ASSERT(new_data[hv].key != old_data[i].key);
119 hv = (hv + 1) & mask;
120 }
121
122 new_data[hv] = old_data[i];
123 }
124 }
125
126 /* Free old entries */
127 efree(old_data);
128 }
129 /* }}} */
130 /* {{{ hash_si_ptr_find_or_insert */
131 /**
132 * @param h the pointer to the hash map.
133 * @param key the key (representing to look up (or insert, if it doesn't exist)
134 * @param value - If the key does not exist, this is the value to associate with key
135 * @return the old value, or SIZE_MAX if the key is brand new.
136 */
hash_si_ptr_find_or_insert(struct hash_si_ptr * h,const zend_uintptr_t key,uint32_t value)137 size_t hash_si_ptr_find_or_insert(struct hash_si_ptr *h, const zend_uintptr_t key, uint32_t value) {
138 size_t size;
139 size_t mask;
140 uint32_t hv;
141
142 ZEND_ASSERT(h != NULL);
143
144 size = h->size;
145 mask = size - 1;
146 hv = inline_hash_of_address(key) & mask;
147
148 while (1) {
149 if (h->data[hv].key == HASH_PTR_KEY_INVALID) {
150 /* This is a brand new key */
151 h->data[hv].key = key;
152 h->data[hv].value = value;
153 h->used++;
154
155 /* The size increased, so check if we need to expand the map */
156 if ((h->size >> 1) < h->used) {
157 hash_si_ptr_rehash(h);
158 }
159 return SIZE_MAX;
160 } else if (h->data[hv].key == key) {
161 /* This already exists in the hash map */
162 return h->data[hv].value;
163 }
164 /* linear prob */
165 hv = (hv + 1) & mask;
166 }
167 }
168 /* }}} */
169 /* {{{ hash_si_ptr_size */
170 /**
171 * @param h the hash map from pointers to integers.
172 * @return the number of elements in this hash map.
173 */
hash_si_ptr_size(struct hash_si_ptr * h)174 size_t hash_si_ptr_size(struct hash_si_ptr *h) {
175 assert(h != NULL);
176
177 return h->used;
178 }
179 /* }}} */
180 /* {{{ hash_si_ptr_capacity */
181 /**
182 * @param h the hash map from pointers to integers.
183 * @return the capacity of this hash map.
184 */
hash_si_ptr_capacity(struct hash_si_ptr * h)185 size_t hash_si_ptr_capacity(struct hash_si_ptr *h) {
186 assert(h != NULL);
187
188 return h->size;
189 }
190 /* }}} */
191
192 /*
193 * Local variables:
194 * tab-width: 2
195 * c-basic-offset: 4
196 * End:
197 * vim600: noet sw=4 ts=4 fdm=marker
198 * vim<600: noet sw=4 ts=4
199 */
200