1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
/*
+----------------------------------------------------------------------+
| Zend Engine |
+----------------------------------------------------------------------+
| Copyright (c) 1998-2000 Andi Gutmans, Zeev Suraski |
+----------------------------------------------------------------------+
| This source file is subject to version 0.91 of the Zend license, |
| that is bundled with this package in the file LICENSE, and is |
| available at through the world-wide-web at |
| http://www.zend.com/license/0_91.txt. |
| If you did not receive a copy of the Zend license and are unable to |
| obtain it through the world-wide-web, please send a note to |
| license@zend.com so we can mail you a copy immediately. |
+----------------------------------------------------------------------+
| Authors: Andi Gutmans <andi@zend.com> |
| Zeev Suraski <zeev@zend.com> |
+----------------------------------------------------------------------+
*/
#ifndef _HASH_
#define _HASH_
#include <sys/types.h>
#define HASH_KEY_IS_STRING 1
#define HASH_KEY_IS_LONG 2
#define HASH_KEY_NON_EXISTANT 3
#define HASH_UPDATE (1<<0)
#define HASH_ADD (1<<1)
#define HASH_NEXT_INSERT (1<<2)
#define HASH_ADD_PTR (1<<3)
#define HASH_DEL_KEY 0
#define HASH_DEL_INDEX 1
typedef int (*compare_func_t)(const void *, const void *);
typedef void (*sort_func_t)(void *, size_t, register size_t, compare_func_t);
typedef void (*dtor_func_t)(void *pDest);
typedef int (*apply_func_t)(void *pDest);
typedef int (*apply_func_arg_t)(void *pDest, void *argument);
typedef ulong (*hash_func_t)(char *arKey, uint nKeyLength);
typedef void (*copy_ctor_func_t)(void *pElement);
struct hashtable;
typedef struct bucket {
ulong h; /* Used for numeric indexing */
uint nKeyLength;
void *pData;
void *pDataPtr;
struct bucket *pListNext;
struct bucket *pListLast;
struct bucket *pNext;
struct bucket *pLast;
char arKey[1]; /* Must be last element */
} Bucket;
typedef struct hashtable {
uint nTableSize;
uint nHashSizeIndex;
uint nNumOfElements;
ulong nNextFreeElement;
hash_func_t pHashFunction;
Bucket *pInternalPointer; /* Used for element traversal */
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets;
dtor_func_t pDestructor;
unsigned char persistent;
#if ZEND_DEBUG
int inconsistent;
#endif
} HashTable;
BEGIN_EXTERN_C()
/* startup/shutdown */
ZEND_API int zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, int persistent);
ZEND_API void zend_hash_destroy(HashTable *ht);
ZEND_API void zend_hash_clean(HashTable *ht);
/* additions/updates/changes */
ZEND_API int zend_hash_add_or_update(HashTable *ht, char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest,int flag);
#define zend_hash_update(ht,arKey,nKeyLength,pData,nDataSize,pDest) \
zend_hash_add_or_update(ht,arKey,nKeyLength,pData,nDataSize,pDest,HASH_UPDATE)
#define zend_hash_add(ht,arKey,nKeyLength,pData,nDataSize,pDest) \
zend_hash_add_or_update(ht,arKey,nKeyLength,pData,nDataSize,pDest,HASH_ADD)
#define zend_hash_update_ptr(ht,arKey,nKeyLength,pData,nDataSize,pDest) \
zend_hash_add_or_update(ht,arKey,nKeyLength,pData,0,pDest,(HASH_UPDATE|HASH_ADD_PTR))
#define zend_hash_add_ptr(ht,arKey,nKeyLength,pData,nDataSize,pDest) \
zend_hash_add_or_update(ht,arKey,nKeyLength,pData,nDataSize,pDest,(HASH_ADD|HASH_ADD_PTR))
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);
#define zend_hash_quick_update(ht,arKey,nKeyLength,h,pData,nDataSize,pDest) \
zend_hash_quick_add_or_update(ht,arKey,nKeyLength,h,pData,nDataSize,pDest,HASH_UPDATE)
#define zend_hash_quick_add(ht,arKey,nKeyLength,h,pData,nDataSize,pDest) \
zend_hash_quick_add_or_update(ht,arKey,nKeyLength,h,pData,nDataSize,pDest,HASH_ADD)
#define zend_hash_quick_update_ptr(ht,arKey,nKeyLength,h,pData,nDataSize,pDest) \
zend_hash_quick_add_or_update(ht,arKey,nKeyLength,h,pData,0,pDest,HASH_UPDATE|HASH_ADD_PTR)
ZEND_API int zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag);
#define zend_hash_index_update(ht,h,pData,nDataSize,pDest) \
zend_hash_index_update_or_next_insert(ht,h,pData,nDataSize,pDest,HASH_UPDATE)
#define zend_hash_next_index_insert(ht,pData,nDataSize,pDest) \
zend_hash_index_update_or_next_insert(ht,0,pData,nDataSize,pDest,HASH_NEXT_INSERT)
#define zend_hash_next_index_insert_ptr(ht,pData,nDataSize,pDest) \
zend_hash_index_update_or_next_insert(ht,0,pData,nDataSize,pDest,HASH_NEXT_INSERT|HASH_ADD_PTR)
typedef struct _zend_hash_key {
char *arKey;
uint nKeyLength;
ulong h;
} zend_hash_key;
#define ZEND_STD_HASH_APPLIER \
int (*)(void *element, int num_args, va_list args, zend_hash_key *hash_key)
ZEND_API void zend_hash_graceful_destroy(HashTable *ht);
ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func);
ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void *);
ZEND_API void zend_hash_apply_with_arguments(HashTable *ht, ZEND_STD_HASH_APPLIER, int, ...);
/* Deletes */
ZEND_API int zend_hash_del_key_or_index(HashTable *ht, char *arKey, uint nKeyLength, ulong h, int flag);
#define zend_hash_del(ht,arKey,nKeyLength) \
zend_hash_del_key_or_index(ht,arKey,nKeyLength,0,HASH_DEL_KEY)
#define zend_hash_index_del(ht,h) \
zend_hash_del_key_or_index(ht,NULL,0,h,HASH_DEL_INDEX)
ZEND_API ulong zend_get_hash_value(HashTable *ht, char *arKey, uint nKeyLength);
/* Data retreival */
ZEND_API int zend_hash_find(HashTable *ht, char *arKey, uint nKeyLength, void **pData);
ZEND_API int zend_hash_quick_find(HashTable *ht, char *arKey, uint nKeyLength, ulong h, void **pData);
ZEND_API int zend_hash_index_find(HashTable *ht, ulong h, void **pData);
/* Misc */
ZEND_API int zend_hash_exists(HashTable *ht, char *arKey, uint nKeyLength);
ZEND_API int zend_hash_index_exists(HashTable *ht, ulong h);
ZEND_API ulong zend_hash_next_free_element(HashTable *ht);
/* traversing */
ZEND_API void zend_hash_move_forward(HashTable *ht);
ZEND_API void zend_hash_move_backwards(HashTable *ht);
ZEND_API int zend_hash_get_current_key(HashTable *ht, char **str_index, ulong *num_index);
ZEND_API int zend_hash_get_current_key_type(HashTable *ht);
ZEND_API int zend_hash_get_current_data(HashTable *ht, void **pData);
ZEND_API void zend_hash_internal_pointer_reset(HashTable *ht);
ZEND_API void zend_hash_internal_pointer_end(HashTable *ht);
/* Copying, merging and sorting */
ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size);
ZEND_API void zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size, int overwrite);
ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, int renumber);
ZEND_API int zend_hash_minmax(HashTable *ht, int (*compar)(const void *, const void *), int flag, void **pData);
ZEND_API int zend_hash_num_elements(HashTable *ht);
ZEND_API int zend_hash_rehash(HashTable *ht);
ZEND_API ulong hashpjw(char *arKey, uint nKeyLength);
#if ZEND_DEBUG
/* debug */
void zend_hash_display_pListTail(HashTable *ht);
void zend_hash_display(HashTable *ht);
#endif
END_EXTERN_C()
#endif /* _HASH_ */
|
