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
5. zend_accel_hash_find_entry
6. 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, 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  */
  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  */
 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  */
 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 
 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 }