1 /*
2    +----------------------------------------------------------------------+
3    | Zend OPcache                                                         |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 1998-2018 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 #ifndef ZEND_ACCELERATOR_HASH_H
23 #define ZEND_ACCELERATOR_HASH_H
24 
25 #include "zend.h"
26 
27 /*
28 	zend_accel_hash - is a hash table allocated in shared memory and
29 	distributed across simultaneously running processes. The hash tables have
30 	fixed sizen selected during construction by zend_accel_hash_init(). All the
31 	hash entries are preallocated in the 'hash_entries' array. 'num_entries' is
32 	initialized by zero and grows when new data is added.
33 	zend_accel_hash_update() just takes the next entry from 'hash_entries'
34 	array and puts it into appropriate place of 'hash_table'.
35 	Hash collisions are resolved by separate chaining with linked lists,
36 	however, entries are still taken from the same 'hash_entries' array.
37 	'key' and 'data' passed to zend_accel_hash_update() must be already
38 	allocated in shared memory. Few keys may be resolved to the same data.
39 	using 'indirect' entries, that point to other entries ('data' is actually
40 	a pointer to another zend_accel_hash_entry).
41 	zend_accel_hash_update() requires exclusive lock, however,
42 	zend_accel_hash_find() does not.
43 */
44 
45 typedef struct _zend_accel_hash_entry zend_accel_hash_entry;
46 
47 struct _zend_accel_hash_entry {
48 	zend_ulong             hash_value;
49 	char                  *key;
50 	uint32_t              key_length;
51 	zend_accel_hash_entry *next;
52 	void                  *data;
53 	zend_bool              indirect;
54 };
55 
56 typedef struct _zend_accel_hash {
57 	zend_accel_hash_entry **hash_table;
58 	zend_accel_hash_entry  *hash_entries;
59 	uint32_t               num_entries;
60 	uint32_t               max_num_entries;
61 	uint32_t               num_direct_entries;
62 } zend_accel_hash;
63 
64 void zend_accel_hash_init(zend_accel_hash *accel_hash, uint32_t hash_size);
65 void zend_accel_hash_clean(zend_accel_hash *accel_hash);
66 
67 zend_accel_hash_entry* zend_accel_hash_update(
68 		zend_accel_hash        *accel_hash,
69 		char                   *key,
70 		uint32_t               key_length,
71 		zend_bool               indirect,
72 		void                   *data);
73 
74 void* zend_accel_hash_find(
75 		zend_accel_hash        *accel_hash,
76 		zend_string            *key);
77 
78 zend_accel_hash_entry* zend_accel_hash_find_entry(
79 		zend_accel_hash        *accel_hash,
80 		zend_string            *key);
81 
82 void* zend_accel_hash_str_find(
83 		zend_accel_hash        *accel_hash,
84 		char                   *key,
85 		uint32_t               key_length);
86 
87 zend_accel_hash_entry* zend_accel_hash_str_find_entry(
88 		zend_accel_hash        *accel_hash,
89 		char                   *key,
90 		uint32_t               key_length);
91 
92 int zend_accel_hash_unlink(
93 		zend_accel_hash        *accel_hash,
94 		char                   *key,
95 		uint32_t               key_length);
96 
zend_accel_hash_is_full(zend_accel_hash * accel_hash)97 static inline zend_bool zend_accel_hash_is_full(zend_accel_hash *accel_hash)
98 {
99 	if (accel_hash->num_entries == accel_hash->max_num_entries) {
100 		return 1;
101 	} else {
102 		return 0;
103 	}
104 }
105 
106 #endif /* ZEND_ACCELERATOR_HASH_H */
107