diff options
Diffstat (limited to 'ext/opcache/zend_accelerator_hash.c')
-rw-r--r-- | ext/opcache/zend_accelerator_hash.c | 224 |
1 files changed, 224 insertions, 0 deletions
diff --git a/ext/opcache/zend_accelerator_hash.c b/ext/opcache/zend_accelerator_hash.c new file mode 100644 index 0000000000..afd227c5d5 --- /dev/null +++ b/ext/opcache/zend_accelerator_hash.c @@ -0,0 +1,224 @@ +/* + +----------------------------------------------------------------------+ + | Zend OPcache | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2013 The PHP Group | + +----------------------------------------------------------------------+ + | This source file is subject to version 3.01 of the PHP license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.php.net/license/3_01.txt | + | If you did not receive a copy of the PHP license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@php.net so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ + | Authors: Andi Gutmans <andi@zend.com> | + | Zeev Suraski <zeev@zend.com> | + | Stanislav Malyshev <stas@zend.com> | + | Dmitry Stogov <dmitry@zend.com> | + +----------------------------------------------------------------------+ +*/ + +#include "ZendAccelerator.h" +#include "zend_accelerator_hash.h" +#include "zend_hash.h" +#include "zend_shared_alloc.h" + +/* Generated on an Octa-ALPHA 300MHz CPU & 2.5GB RAM monster */ +static uint prime_numbers[] = + {5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963, 16229, 32531, 65407, 130987, 262237, 524521, 1048793 }; +static uint num_prime_numbers = sizeof(prime_numbers) / sizeof(uint); + +void zend_accel_hash_clean(zend_accel_hash *accel_hash) +{ + accel_hash->num_entries = 0; + accel_hash->num_direct_entries = 0; + memset(accel_hash->hash_table, 0, sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries); +} + +void zend_accel_hash_init(zend_accel_hash *accel_hash, zend_uint hash_size) +{ + uint i; + + for (i=0; i<num_prime_numbers; i++) { + if (hash_size <= prime_numbers[i]) { + hash_size = prime_numbers[i]; + break; + } + } + + accel_hash->num_entries = 0; + accel_hash->num_direct_entries = 0; + accel_hash->max_num_entries = hash_size; + + /* set up hash pointers table */ + accel_hash->hash_table = zend_shared_alloc(sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries); + if (!accel_hash->hash_table) { + zend_accel_error(ACCEL_LOG_FATAL, "Insufficient shared memory!"); + return; + } + + /* set up hash values table */ + accel_hash->hash_entries = zend_shared_alloc(sizeof(zend_accel_hash_entry)*accel_hash->max_num_entries); + if (!accel_hash->hash_entries) { + zend_accel_error(ACCEL_LOG_FATAL, "Insufficient shared memory!"); + return; + } + memset(accel_hash->hash_table, 0, sizeof(zend_accel_hash_entry *)*accel_hash->max_num_entries); +} + +/* Returns NULL if hash is full + * Returns pointer the actual hash entry on success + * key needs to be already allocated as it is not copied + */ +zend_accel_hash_entry* zend_accel_hash_update(zend_accel_hash *accel_hash, char *key, zend_uint key_length, zend_bool indirect, void *data) +{ + zend_ulong hash_value; + zend_ulong index; + zend_accel_hash_entry *entry; + zend_accel_hash_entry *indirect_bucket = NULL; + + if (indirect) { + indirect_bucket = (zend_accel_hash_entry*)data; + while (indirect_bucket->indirect) { + indirect_bucket = (zend_accel_hash_entry*)indirect_bucket->data; + } + } + + hash_value = zend_inline_hash_func(key, key_length); + index = hash_value % accel_hash->max_num_entries; + + /* try to see if the element already exists in the hash */ + entry = accel_hash->hash_table[index]; + while (entry) { + if (entry->hash_value == hash_value + && entry->key_length == key_length + && !memcmp(entry->key, key, key_length)) { + + if (entry->indirect) { + if (indirect_bucket) { + entry->data = indirect_bucket; + } else { + ((zend_accel_hash_entry*)entry->data)->data = data; + } + } else { + if (indirect_bucket) { + accel_hash->num_direct_entries--; + entry->data = indirect_bucket; + entry->indirect = 1; + } else { + entry->data = data; + } + } + return entry; + } + entry = entry->next; + } + + /* Does not exist, add a new entry */ + if (accel_hash->num_entries == accel_hash->max_num_entries) { + return NULL; + } + + entry = &accel_hash->hash_entries[accel_hash->num_entries++]; + if (indirect) { + entry->data = indirect_bucket; + entry->indirect = 1; + } else { + accel_hash->num_direct_entries++; + entry->data = data; + entry->indirect = 0; + } + entry->hash_value = hash_value; + entry->key = key; + entry->key_length = key_length; + entry->next = accel_hash->hash_table[index]; + accel_hash->hash_table[index] = entry; + return entry; +} + +/* Returns the data associated with key on success + * Returns NULL if data doesn't exist + */ +void* zend_accel_hash_find(zend_accel_hash *accel_hash, char *key, zend_uint key_length) +{ + zend_ulong hash_value; + zend_ulong index; + zend_accel_hash_entry *entry; + + hash_value = zend_inline_hash_func(key, key_length); + index = hash_value % accel_hash->max_num_entries; + + entry = accel_hash->hash_table[index]; + while (entry) { + if (entry->hash_value == hash_value + && entry->key_length == key_length + && !memcmp(entry->key, key, key_length)) { + if (entry->indirect) { + return ((zend_accel_hash_entry *) entry->data)->data; + } else { + return entry->data; + } + } + entry = entry->next; + } + return NULL; +} + +/* Returns the hash entry associated with key on success + * Returns NULL if it doesn't exist + */ +zend_accel_hash_entry* zend_accel_hash_find_entry(zend_accel_hash *accel_hash, char *key, zend_uint key_length) +{ + zend_ulong hash_value; + zend_ulong index; + zend_accel_hash_entry *entry; + + hash_value = zend_inline_hash_func(key, key_length); + index = hash_value % accel_hash->max_num_entries; + + entry = accel_hash->hash_table[index]; + while (entry) { + if (entry->hash_value == hash_value + && entry->key_length == key_length + && !memcmp(entry->key, key, key_length)) { + if (entry->indirect) { + return (zend_accel_hash_entry *) entry->data; + } else { + return entry; + } + } + entry = entry->next; + } + return NULL; +} + +int zend_accel_hash_unlink(zend_accel_hash *accel_hash, char *key, zend_uint key_length) +{ + zend_ulong hash_value; + zend_ulong index; + zend_accel_hash_entry *entry, *last_entry=NULL; + + hash_value = zend_inline_hash_func(key, key_length); + index = hash_value % accel_hash->max_num_entries; + + entry = accel_hash->hash_table[index]; + while (entry) { + if (entry->hash_value == hash_value + && entry->key_length == key_length + && !memcmp(entry->key, key, key_length)) { + if (!entry->indirect) { + accel_hash->num_direct_entries--; + } + if (last_entry) { + last_entry->next = entry->next; + } else { + accel_hash->hash_table[index] = entry->next; + } + return SUCCESS; + } + last_entry = entry; + entry = entry->next; + } + return FAILURE; +} |