root/ext/opcache/zend_accelerator_hash.c

DEFINITIONS

1. zend_accel_hash_clean
2. zend_accel_hash_init
3. zend_accel_hash_update
4. zend_accel_hash_find_ex
5. zend_accel_hash_find
6. zend_accel_hash_find_entry
7. zend_accel_hash_str_find
8. zend_accel_hash_str_find_entry
9. zend_accel_hash_unlink

   1 /*
   2    +----------------------------------------------------------------------+
   3    | Zend OPcache                                                         |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 1998-2016 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 
  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 
  39 void zend_accel_hash_init(zend_accel_hash *accel_hash, uint32_t 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  */
  74 zend_accel_hash_entry* zend_accel_hash_update(zend_accel_hash *accel_hash, char *key, uint32_t 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 static zend_always_inline void* zend_accel_hash_find_ex(zend_accel_hash *accel_hash, char *key, uint32_t key_length, zend_ulong hash_value, int data)
 141 {
 142         zend_ulong index = hash_value % accel_hash->max_num_entries;
 143         zend_accel_hash_entry *entry = accel_hash->hash_table[index];
 144 
 145         while (entry) {
 146                 if (entry->hash_value == hash_value
 147                         && entry->key_length == key_length
 148                         && !memcmp(entry->key, key, key_length)) {
 149                         if (entry->indirect) {
 150                                 if (data) {
 151                                         return ((zend_accel_hash_entry*)entry->data)->data;
 152                                 } else {
 153                                         return entry->data;
 154                                 }
 155                         } else {
 156                                 if (data) {
 157                                         return entry->data;
 158                                 } else {
 159                                         return entry;
 160                                 }
 161                         }
 162                 }
 163                 entry = entry->next;
 164         }
 165         return NULL;
 166 }
 167 
 168 /* Returns the data associated with key on success
 169  * Returns NULL if data doesn't exist
 170  */
 171 void* zend_accel_hash_find(zend_accel_hash *accel_hash, zend_string *key)
 172 {
 173         return zend_accel_hash_find_ex(
 174                 accel_hash,
 175                 ZSTR_VAL(key),
 176                 ZSTR_LEN(key),
 177                 zend_string_hash_val(key),
 178                 1);
 179 }
 180 
 181 /* Returns the hash entry associated with key on success
 182  * Returns NULL if it doesn't exist
 183  */
 184 zend_accel_hash_entry* zend_accel_hash_find_entry(zend_accel_hash *accel_hash, zend_string *key)
 185 {
 186         return (zend_accel_hash_entry *)zend_accel_hash_find_ex(
 187                 accel_hash,
 188                 ZSTR_VAL(key),
 189                 ZSTR_LEN(key),
 190                 zend_string_hash_val(key),
 191                 0);
 192 }
 193 
 194 /* Returns the data associated with key on success
 195  * Returns NULL if data doesn't exist
 196  */
 197 void* zend_accel_hash_str_find(zend_accel_hash *accel_hash, char *key, uint32_t key_length)
 198 {
 199         return zend_accel_hash_find_ex(
 200                 accel_hash,
 201                 key,
 202                 key_length,
 203                 zend_inline_hash_func(key, key_length),
 204                 1);
 205 }
 206 
 207 /* Returns the hash entry associated with key on success
 208  * Returns NULL if it doesn't exist
 209  */
 210 zend_accel_hash_entry* zend_accel_hash_str_find_entry(zend_accel_hash *accel_hash, char *key, uint32_t key_length)
 211 {
 212         return (zend_accel_hash_entry *)zend_accel_hash_find_ex(
 213                 accel_hash,
 214                 key,
 215                 key_length,
 216                 zend_inline_hash_func(key, key_length),
 217                 0);
 218 }
 219 
 220 int zend_accel_hash_unlink(zend_accel_hash *accel_hash, char *key, uint32_t key_length)
 221 {
 222     zend_ulong hash_value;
 223     zend_ulong index;
 224     zend_accel_hash_entry *entry, *last_entry=NULL;
 225 
 226         hash_value = zend_inline_hash_func(key, key_length);
 227         index = hash_value % accel_hash->max_num_entries;
 228 
 229         entry = accel_hash->hash_table[index];
 230         while (entry) {
 231                 if (entry->hash_value == hash_value
 232                         && entry->key_length == key_length
 233                         && !memcmp(entry->key, key, key_length)) {
 234                         if (!entry->indirect) {
 235                                 accel_hash->num_direct_entries--;
 236                         }
 237                         if (last_entry) {
 238                                 last_entry->next = entry->next;
 239                         } else {
 240                                 accel_hash->hash_table[index] = entry->next;
 241                         }
 242                         return SUCCESS;
 243                 }
 244                 last_entry = entry;
 245                 entry = entry->next;
 246         }
 247         return FAILURE;
 248 }