Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 221 lines (178 sloc) 9.532 kb
573b460 andigutmans Zend Library
andigutmans authored
1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine |
4 +----------------------------------------------------------------------+
62dc854 Happy New Year.
Sebastian Bergmann authored
5 | Copyright (c) 1998-2002 Zend Technologies Ltd. (http://www.zend.com) |
573b460 andigutmans Zend Library
andigutmans authored
6 +----------------------------------------------------------------------+
d863d52 Update headers.
Sebastian Bergmann authored
7 | This source file is subject to version 2.00 of the Zend license, |
b5b1117 Zeev Suraski License update
zsuraski authored
8 | that is bundled with this package in the file LICENSE, and is |
9 | available at through the world-wide-web at |
d863d52 Update headers.
Sebastian Bergmann authored
10 | http://www.zend.com/license/2_00.txt. |
b5b1117 Zeev Suraski License update
zsuraski authored
11 | If you did not receive a copy of the Zend license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@zend.com so we can mail you a copy immediately. |
573b460 andigutmans Zend Library
andigutmans authored
14 +----------------------------------------------------------------------+
15 | Authors: Andi Gutmans <andi@zend.com> |
16 | Zeev Suraski <zeev@zend.com> |
17 +----------------------------------------------------------------------+
18 */
19
a617217 Replace macros which begin with an underscore through an appropiately
Sascha Schumann authored
20 #ifndef ZEND_HASH_H
21 #define ZEND_HASH_H
573b460 andigutmans Zend Library
andigutmans authored
22
23 #include <sys/types.h>
24
25 #define HASH_KEY_IS_STRING 1
26 #define HASH_KEY_IS_LONG 2
27 #define HASH_KEY_NON_EXISTANT 3
28
29 #define HASH_UPDATE (1<<0)
30 #define HASH_ADD (1<<1)
31 #define HASH_NEXT_INSERT (1<<2)
32
33 #define HASH_DEL_KEY 0
34 #define HASH_DEL_INDEX 1
35
2f8fa8c andigutmans - Merge faster hash implementation.
andigutmans authored
36 typedef ulong (*hash_func_t)(char *arKey, uint nKeyLength);
3bdddb4 MFZE1
Sebastian Bergmann authored
37 typedef int (*compare_func_t)(const void *, const void * TSRMLS_DC);
38 typedef void (*sort_func_t)(void *, size_t, register size_t, compare_func_t TSRMLS_DC);
62114c1 Zeev Suraski Destructors no longer return ints, the low level problem it was intended...
zsuraski authored
39 typedef void (*dtor_func_t)(void *pDest);
9f51f15 Zeev Suraski - Stop passing list/plist to internal functions
zsuraski authored
40 typedef void (*copy_ctor_func_t)(void *pElement);
62114c1 Zeev Suraski Destructors no longer return ints, the low level problem it was intended...
zsuraski authored
41
9b916e6 rename hastable -> _hashtable to avoid clashes
Thies C. Arntzen authored
42 struct _hashtable;
573b460 andigutmans Zend Library
andigutmans authored
43
44 typedef struct bucket {
45 ulong h; /* Used for numeric indexing */
46 uint nKeyLength;
47 void *pData;
48 void *pDataPtr;
49 struct bucket *pListNext;
50 struct bucket *pListLast;
51 struct bucket *pNext;
aa73f6b andigutmans - Hopefully fix the hash problem.
andigutmans authored
52 struct bucket *pLast;
573b460 andigutmans Zend Library
andigutmans authored
53 char arKey[1]; /* Must be last element */
54 } Bucket;
55
9b916e6 rename hastable -> _hashtable to avoid clashes
Thies C. Arntzen authored
56 typedef struct _hashtable {
573b460 andigutmans Zend Library
andigutmans authored
57 uint nTableSize;
2f8fa8c andigutmans - Merge faster hash implementation.
andigutmans authored
58 uint nTableMask;
573b460 andigutmans Zend Library
andigutmans authored
59 uint nNumOfElements;
60 ulong nNextFreeElement;
61 Bucket *pInternalPointer; /* Used for element traversal */
62 Bucket *pListHead;
63 Bucket *pListTail;
64 Bucket **arBuckets;
62114c1 Zeev Suraski Destructors no longer return ints, the low level problem it was intended...
zsuraski authored
65 dtor_func_t pDestructor;
38cdb8e Zeev Suraski Avoid crashing with recursive applies - limit apply nest level to 3 (I'm...
zsuraski authored
66 zend_bool persistent;
67 unsigned char nApplyCount;
1263932 Zeev Suraski Disable the hash_apply() protection on hashes that persist across reques...
zsuraski authored
68 zend_bool bApplyProtection;
c93a189 if ZEND_DEBUG mode is on we'll now see warnings when a HashTable is acc...
Thies C. Arntzen authored
69 #if ZEND_DEBUG
70 int inconsistent;
71 #endif
573b460 andigutmans Zend Library
andigutmans authored
72 } HashTable;
73
a32c54b Introduced a way to traverse hashes through external pointers.
Andrei Zmievski authored
74 typedef Bucket* HashPosition;
75
fd4650b Zeev Suraski Add zend_hash_get_current_key_type()
zsuraski authored
76 BEGIN_EXTERN_C()
77
573b460 andigutmans Zend Library
andigutmans authored
78 /* startup/shutdown */
62114c1 Zeev Suraski Destructors no longer return ints, the low level problem it was intended...
zsuraski authored
79 ZEND_API int zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, int persistent);
1263932 Zeev Suraski Disable the hash_apply() protection on hashes that persist across reques...
zsuraski authored
80 ZEND_API int zend_hash_init_ex(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, int persistent, zend_bool bApplyProtection);
573b460 andigutmans Zend Library
andigutmans authored
81 ZEND_API void zend_hash_destroy(HashTable *ht);
82 ZEND_API void zend_hash_clean(HashTable *ht);
83
84 /* additions/updates/changes */
4f6c95d Zeev Suraski Whitespace
zsuraski authored
85 ZEND_API int zend_hash_add_or_update(HashTable *ht, char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag);
86 #define zend_hash_update(ht, arKey, nKeyLength, pData, nDataSize, pDest) \
87 zend_hash_add_or_update(ht, arKey, nKeyLength, pData, nDataSize, pDest, HASH_UPDATE)
88 #define zend_hash_add(ht, arKey, nKeyLength, pData, nDataSize, pDest) \
89 zend_hash_add_or_update(ht, arKey, nKeyLength, pData, nDataSize, pDest, HASH_ADD)
90
91 ZEND_API int zend_hash_quick_add_or_update(HashTable *ht, char *arKey, uint nKeyLength, ulong h, void *pData, uint nDataSize, void **pDest, int flag);
92 #define zend_hash_quick_update(ht, arKey, nKeyLength, h, pData, nDataSize, pDest) \
93 zend_hash_quick_add_or_update(ht, arKey, nKeyLength, h, pData, nDataSize, pDest, HASH_UPDATE)
94 #define zend_hash_quick_add(ht, arKey, nKeyLength, h, pData, nDataSize, pDest) \
95 zend_hash_quick_add_or_update(ht, arKey, nKeyLength, h, pData, nDataSize, pDest, HASH_ADD)
573b460 andigutmans Zend Library
andigutmans authored
96
97 ZEND_API int zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag);
4f6c95d Zeev Suraski Whitespace
zsuraski authored
98 #define zend_hash_index_update(ht, h, pData, nDataSize, pDest) \
99 zend_hash_index_update_or_next_insert(ht, h, pData, nDataSize, pDest, HASH_UPDATE)
100 #define zend_hash_next_index_insert(ht, pData, nDataSize, pDest) \
101 zend_hash_index_update_or_next_insert(ht, 0, pData, nDataSize, pDest, HASH_NEXT_INSERT)
573b460 andigutmans Zend Library
andigutmans authored
102
755207a Zeev Suraski Implement zend_hash_add_empty_element() using the existing infrastructur...
zsuraski authored
103 ZEND_API int zend_hash_add_empty_element(HashTable *ht, char *arKey, uint nKeyLength);
104
c14baee Zeev Suraski Avoid going over huge lists of functions, classes and constants.
zsuraski authored
105
106 #define ZEND_HASH_APPLY_KEEP 0
107 #define ZEND_HASH_APPLY_REMOVE 1<<0
108 #define ZEND_HASH_APPLY_STOP 1<<1
109
746ce67 andigutmans - Add hash_apply_with_arguments()
andigutmans authored
110 typedef struct _zend_hash_key {
111 char *arKey;
112 uint nKeyLength;
113 ulong h;
114 } zend_hash_key;
115
116
7deb44e Zeev Suraski Some cleanup
zsuraski authored
117 typedef int (*apply_func_t)(void *pDest TSRMLS_DC);
118 typedef int (*apply_func_arg_t)(void *pDest, void *argument TSRMLS_DC);
b51aa1f Made an alias for hash apply with arguments.
Andrei Zmievski authored
119 typedef int (*apply_func_args_t)(void *pDest, int num_args, va_list args, zend_hash_key *hash_key);
120
ee08b81 Zeev Suraski - Make zend_hash_apply() (and friends) reentrant and much, much quicker
zsuraski authored
121 ZEND_API void zend_hash_graceful_destroy(HashTable *ht);
bf5bb84 MFZE1: make sure the resource-list is always consistent during shutdown ...
Sebastian Bergmann authored
122 ZEND_API void zend_hash_graceful_reverse_destroy(HashTable *ht);
d76cf1d Zeev Suraski More TSRMLS_FETCH work
zsuraski authored
123 ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC);
124 ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void * TSRMLS_DC);
1c2893a Zeev Suraski Minor cleaning
zsuraski authored
125 ZEND_API void zend_hash_apply_with_arguments(HashTable *ht, apply_func_args_t apply_func, int, ...);
746ce67 andigutmans - Add hash_apply_with_arguments()
andigutmans authored
126
c14baee Zeev Suraski Avoid going over huge lists of functions, classes and constants.
zsuraski authored
127 /* This function should be used with special care (in other words,
128 * it should usually not be used). When used with the ZEND_HASH_APPLY_STOP
129 * return value, it assumes things about the order of the elements in the hash.
130 * Also, it does not provide the same kind of reentrancy protection that
131 * the standard apply functions do.
132 */
133 ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC);
573b460 andigutmans Zend Library
andigutmans authored
134
135
136 /* Deletes */
137 ZEND_API int zend_hash_del_key_or_index(HashTable *ht, char *arKey, uint nKeyLength, ulong h, int flag);
4f6c95d Zeev Suraski Whitespace
zsuraski authored
138 #define zend_hash_del(ht, arKey, nKeyLength) \
139 zend_hash_del_key_or_index(ht, arKey, nKeyLength, 0, HASH_DEL_KEY)
140 #define zend_hash_index_del(ht, h) \
141 zend_hash_del_key_or_index(ht, NULL, 0, h, HASH_DEL_INDEX)
573b460 andigutmans Zend Library
andigutmans authored
142
143 ZEND_API ulong zend_get_hash_value(HashTable *ht, char *arKey, uint nKeyLength);
144
145 /* Data retreival */
146 ZEND_API int zend_hash_find(HashTable *ht, char *arKey, uint nKeyLength, void **pData);
147 ZEND_API int zend_hash_quick_find(HashTable *ht, char *arKey, uint nKeyLength, ulong h, void **pData);
148 ZEND_API int zend_hash_index_find(HashTable *ht, ulong h, void **pData);
149
150 /* Misc */
151 ZEND_API int zend_hash_exists(HashTable *ht, char *arKey, uint nKeyLength);
152 ZEND_API int zend_hash_index_exists(HashTable *ht, ulong h);
153 ZEND_API ulong zend_hash_next_free_element(HashTable *ht);
154
155 /* traversing */
ee286fe Make zend_hash_move_forward()/zenv_hash_move_backwards() a little smarte...
Andrei Zmievski authored
156 ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos);
157 ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos);
9b3df86 Zeev Suraski MFZE1
zsuraski authored
158 ZEND_API int zend_hash_get_current_key_ex(HashTable *ht, char **str_index, uint *str_length, ulong *num_index, zend_bool duplicate, HashPosition *pos);
a32c54b Introduced a way to traverse hashes through external pointers.
Andrei Zmievski authored
159 ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos);
160 ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosition *pos);
161 ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos);
162 ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos);
163
164 #define zend_hash_move_forward(ht) \
165 zend_hash_move_forward_ex(ht, NULL)
166 #define zend_hash_move_backwards(ht) \
167 zend_hash_move_backwards_ex(ht, NULL)
36eaad2 Zeev Suraski Allow get_current_key() not to return the key itself, instead of a dupli...
zsuraski authored
168 #define zend_hash_get_current_key(ht, str_index, num_index, duplicate) \
169 zend_hash_get_current_key_ex(ht, str_index, NULL, num_index, duplicate, NULL)
a32c54b Introduced a way to traverse hashes through external pointers.
Andrei Zmievski authored
170 #define zend_hash_get_current_key_type(ht) \
171 zend_hash_get_current_key_type_ex(ht, NULL)
172 #define zend_hash_get_current_data(ht, pData) \
173 zend_hash_get_current_data_ex(ht, pData, NULL)
174 #define zend_hash_internal_pointer_reset(ht) \
175 zend_hash_internal_pointer_reset_ex(ht, NULL)
176 #define zend_hash_internal_pointer_end(ht) \
177 zend_hash_internal_pointer_end_ex(ht, NULL)
573b460 andigutmans Zend Library
andigutmans authored
178
179 /* Copying, merging and sorting */
9f51f15 Zeev Suraski - Stop passing list/plist to internal functions
zsuraski authored
180 ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size);
181 ZEND_API void zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size, int overwrite);
e988715 andigutmans Don't use 'new' symbol
andigutmans authored
182 ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, uint size, zend_bool (*pReplaceOrig)(void *orig, void *p_new));
3bdddb4 MFZE1
Sebastian Bergmann authored
183 ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, int renumber TSRMLS_DC);
8ce8324 Zeev Suraski More TSRMLS_FETCH annihilation
zsuraski authored
184 ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC);
3bdddb4 MFZE1
Sebastian Bergmann authored
185 ZEND_API int zend_hash_minmax(HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC);
573b460 andigutmans Zend Library
andigutmans authored
186
187 ZEND_API int zend_hash_num_elements(HashTable *ht);
188
3964c92 Made zend_hash_rehash() callable from outside.
Andrei Zmievski authored
189 ZEND_API int zend_hash_rehash(HashTable *ht);
573b460 andigutmans Zend Library
andigutmans authored
190
b98acd6 andigutmans - Move inline_zend_hash_func() to header file
andigutmans authored
191 static inline ulong zend_inline_hash_func(char *arKey, uint nKeyLength)
192 {
193 ulong h = 5381;
194 char *arEnd = arKey + nKeyLength;
195
196 while (arKey < arEnd) {
197 h += (h << 5);
198 h ^= (ulong) *arKey++;
199 }
200 return h;
201 }
202
6cf5e7f Stanislav Malyshev No hashpjw anymore, but we have zend_hash_func
smalyshev authored
203 ZEND_API ulong zend_hash_func(char *arKey, uint nKeyLength);
573b460 andigutmans Zend Library
andigutmans authored
204
9353650 Fix warnings surfacing in maintainer-mode.
Stig S. Bakken authored
205 #if ZEND_DEBUG
573b460 andigutmans Zend Library
andigutmans authored
206 /* debug */
207 void zend_hash_display_pListTail(HashTable *ht);
208 void zend_hash_display(HashTable *ht);
209 #endif
210
fd4650b Zeev Suraski Add zend_hash_get_current_key_type()
zsuraski authored
211 END_EXTERN_C()
212
0a14a32 Zeev Suraski Add useful macros
zsuraski authored
213 #define ZEND_INIT_SYMTABLE(ht) \
214 ZEND_INIT_SYMTABLE_EX(ht, 2, 0)
215
216 #define ZEND_INIT_SYMTABLE_EX(ht, n, persistent) \
217 zend_hash_init(ht, n, NULL, ZVAL_PTR_DTOR, persistent)
218
219
a617217 Replace macros which begin with an underscore through an appropiately
Sascha Schumann authored
220 #endif /* ZEND_HASH_H */
Something went wrong with that request. Please try again.