1 /*
2 +----------------------------------------------------------------------+
3 | Zend OPcache |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2015 The PHP Group |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
15 | Authors: Andi Gutmans <andi@zend.com> |
16 | Zeev Suraski <zeev@zend.com> |
17 | Stanislav Malyshev <stas@zend.com> |
18 | Dmitry Stogov <dmitry@zend.com> |
19 +----------------------------------------------------------------------+
20 */
21
22 #include "ZendAccelerator.h"
23 #include "zend_accelerator_hash.h"
24 #include "zend_hash.h"
25 #include "zend_shared_alloc.h"
26
27 /* Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster */
28 static uint prime_numbers[] =
29 {5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963, 16229, 32531, 65407, 130987, 262237, 524521, 1048793 };
30 static uint num_prime_numbers = sizeof(prime_numbers) / sizeof(uint);
31
zend_accel_hash_clean(zend_accel_hash * accel_hash)32 void zend_accel_hash_clean(zend_accel_hash *accel_hash)
33 {
34 accel_hash->num_entries = 0;
35 accel_hash->num_direct_entries = 0;
36 memset(accel_hash->hash_table, 0, sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries);
37 }
38
zend_accel_hash_init(zend_accel_hash * accel_hash,zend_uint hash_size)39 void zend_accel_hash_init(zend_accel_hash *accel_hash, zend_uint hash_size)
40 {
41 uint i;
42
43 for (i=0; i<num_prime_numbers; i++) {
44 if (hash_size <= prime_numbers[i]) {
45 hash_size = prime_numbers[i];
46 break;
47 }
48 }
49
50 accel_hash->num_entries = 0;
51 accel_hash->num_direct_entries = 0;
52 accel_hash->max_num_entries = hash_size;
53
54 /* set up hash pointers table */
55 accel_hash->hash_table = zend_shared_alloc(sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries);
56 if (!accel_hash->hash_table) {
57 zend_accel_error(ACCEL_LOG_FATAL, "Insufficient shared memory!");
58 return;
59 }
60
61 /* set up hash values table */
62 accel_hash->hash_entries = zend_shared_alloc(sizeof(zend_accel_hash_entry)*accel_hash->max_num_entries);
63 if (!accel_hash->hash_entries) {
64 zend_accel_error(ACCEL_LOG_FATAL, "Insufficient shared memory!");
65 return;
66 }
67 memset(accel_hash->hash_table, 0, sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries);
68 }
69
70 /* Returns NULL if hash is full
71 * Returns pointer the actual hash entry on success
72 * key needs to be already allocated as it is not copied
73 */
zend_accel_hash_update(zend_accel_hash * accel_hash,char * key,zend_uint key_length,zend_bool indirect,void * data)74 zend_accel_hash_entry* zend_accel_hash_update(zend_accel_hash *accel_hash, char *key, zend_uint key_length, zend_bool indirect, void *data)
75 {
76 zend_ulong hash_value;
77 zend_ulong index;
78 zend_accel_hash_entry *entry;
79 zend_accel_hash_entry *indirect_bucket = NULL;
80
81 if (indirect) {
82 indirect_bucket = (zend_accel_hash_entry*)data;
83 while (indirect_bucket->indirect) {
84 indirect_bucket = (zend_accel_hash_entry*)indirect_bucket->data;
85 }
86 }
87
88 hash_value = zend_inline_hash_func(key, key_length);
89 index = hash_value % accel_hash->max_num_entries;
90
91 /* try to see if the element already exists in the hash */
92 entry = accel_hash->hash_table[index];
93 while (entry) {
94 if (entry->hash_value == hash_value
95 && entry->key_length == key_length
96 && !memcmp(entry->key, key, key_length)) {
97
98 if (entry->indirect) {
99 if (indirect_bucket) {
100 entry->data = indirect_bucket;
101 } else {
102 ((zend_accel_hash_entry*)entry->data)->data = data;
103 }
104 } else {
105 if (indirect_bucket) {
106 accel_hash->num_direct_entries--;
107 entry->data = indirect_bucket;
108 entry->indirect = 1;
109 } else {
110 entry->data = data;
111 }
112 }
113 return entry;
114 }
115 entry = entry->next;
116 }
117
118 /* Does not exist, add a new entry */
119 if (accel_hash->num_entries == accel_hash->max_num_entries) {
120 return NULL;
121 }
122
123 entry = &accel_hash->hash_entries[accel_hash->num_entries++];
124 if (indirect) {
125 entry->data = indirect_bucket;
126 entry->indirect = 1;
127 } else {
128 accel_hash->num_direct_entries++;
129 entry->data = data;
130 entry->indirect = 0;
131 }
132 entry->hash_value = hash_value;
133 entry->key = key;
134 entry->key_length = key_length;
135 entry->next = accel_hash->hash_table[index];
136 accel_hash->hash_table[index] = entry;
137 return entry;
138 }
139
140 /* Returns the data associated with key on success
141 * Returns NULL if data doesn't exist
142 */
zend_accel_hash_find(zend_accel_hash * accel_hash,char * key,zend_uint key_length)143 void* zend_accel_hash_find(zend_accel_hash *accel_hash, char *key, zend_uint key_length)
144 {
145 zend_ulong hash_value;
146 zend_ulong index;
147 zend_accel_hash_entry *entry;
148
149 hash_value = zend_inline_hash_func(key, key_length);
150 index = hash_value % accel_hash->max_num_entries;
151
152 entry = accel_hash->hash_table[index];
153 while (entry) {
154 if (entry->hash_value == hash_value
155 && entry->key_length == key_length
156 && !memcmp(entry->key, key, key_length)) {
157 if (entry->indirect) {
158 return ((zend_accel_hash_entry *) entry->data)->data;
159 } else {
160 return entry->data;
161 }
162 }
163 entry = entry->next;
164 }
165 return NULL;
166 }
167
168 /* Returns the hash entry associated with key on success
169 * Returns NULL if it doesn't exist
170 */
zend_accel_hash_find_entry(zend_accel_hash * accel_hash,char * key,zend_uint key_length)171 zend_accel_hash_entry* zend_accel_hash_find_entry(zend_accel_hash *accel_hash, char *key, zend_uint key_length)
172 {
173 zend_ulong hash_value;
174 zend_ulong index;
175 zend_accel_hash_entry *entry;
176
177 hash_value = zend_inline_hash_func(key, key_length);
178 index = hash_value % accel_hash->max_num_entries;
179
180 entry = accel_hash->hash_table[index];
181 while (entry) {
182 if (entry->hash_value == hash_value
183 && entry->key_length == key_length
184 && !memcmp(entry->key, key, key_length)) {
185 if (entry->indirect) {
186 return (zend_accel_hash_entry *) entry->data;
187 } else {
188 return entry;
189 }
190 }
191 entry = entry->next;
192 }
193 return NULL;
194 }
195
zend_accel_hash_unlink(zend_accel_hash * accel_hash,char * key,zend_uint key_length)196 int zend_accel_hash_unlink(zend_accel_hash *accel_hash, char *key, zend_uint key_length)
197 {
198 zend_ulong hash_value;
199 zend_ulong index;
200 zend_accel_hash_entry *entry, *last_entry=NULL;
201
202 hash_value = zend_inline_hash_func(key, key_length);
203 index = hash_value % accel_hash->max_num_entries;
204
205 entry = accel_hash->hash_table[index];
206 while (entry) {
207 if (entry->hash_value == hash_value
208 && entry->key_length == key_length
209 && !memcmp(entry->key, key, key_length)) {
210 if (!entry->indirect) {
211 accel_hash->num_direct_entries--;
212 }
213 if (last_entry) {
214 last_entry->next = entry->next;
215 } else {
216 accel_hash->hash_table[index] = entry->next;
217 }
218 return SUCCESS;
219 }
220 last_entry = entry;
221 entry = entry->next;
222 }
223 return FAILURE;
224 }
225