Annotation of embedaddon/php/Zend/zend_hash.h, revision 1.1
1.1 ! misho 1: /*
! 2: +----------------------------------------------------------------------+
! 3: | Zend Engine |
! 4: +----------------------------------------------------------------------+
! 5: | Copyright (c) 1998-2012 Zend Technologies Ltd. (http://www.zend.com) |
! 6: +----------------------------------------------------------------------+
! 7: | This source file is subject to version 2.00 of the Zend 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.zend.com/license/2_00.txt. |
! 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. |
! 14: +----------------------------------------------------------------------+
! 15: | Authors: Andi Gutmans <andi@zend.com> |
! 16: | Zeev Suraski <zeev@zend.com> |
! 17: +----------------------------------------------------------------------+
! 18: */
! 19:
! 20: /* $Id: zend_hash.h 321634 2012-01-01 13:15:04Z felipe $ */
! 21:
! 22: #ifndef ZEND_HASH_H
! 23: #define ZEND_HASH_H
! 24:
! 25: #include <sys/types.h>
! 26: #include "zend.h"
! 27:
! 28: #define HASH_KEY_IS_STRING 1
! 29: #define HASH_KEY_IS_LONG 2
! 30: #define HASH_KEY_NON_EXISTANT 3
! 31:
! 32: #define HASH_UPDATE (1<<0)
! 33: #define HASH_ADD (1<<1)
! 34: #define HASH_NEXT_INSERT (1<<2)
! 35:
! 36: #define HASH_DEL_KEY 0
! 37: #define HASH_DEL_INDEX 1
! 38: #define HASH_DEL_KEY_QUICK 2
! 39:
! 40: #define HASH_UPDATE_KEY_IF_NONE 0
! 41: #define HASH_UPDATE_KEY_IF_BEFORE 1
! 42: #define HASH_UPDATE_KEY_IF_AFTER 2
! 43: #define HASH_UPDATE_KEY_ANYWAY 3
! 44:
! 45: typedef ulong (*hash_func_t)(const char *arKey, uint nKeyLength);
! 46: typedef int (*compare_func_t)(const void *, const void * TSRMLS_DC);
! 47: typedef void (*sort_func_t)(void *, size_t, register size_t, compare_func_t TSRMLS_DC);
! 48: typedef void (*dtor_func_t)(void *pDest);
! 49: typedef void (*copy_ctor_func_t)(void *pElement);
! 50: typedef void (*copy_ctor_param_func_t)(void *pElement, void *pParam);
! 51:
! 52: struct _hashtable;
! 53:
! 54: typedef struct bucket {
! 55: ulong h; /* Used for numeric indexing */
! 56: uint nKeyLength;
! 57: void *pData;
! 58: void *pDataPtr;
! 59: struct bucket *pListNext;
! 60: struct bucket *pListLast;
! 61: struct bucket *pNext;
! 62: struct bucket *pLast;
! 63: char arKey[1]; /* Must be last element */
! 64: } Bucket;
! 65:
! 66: typedef struct _hashtable {
! 67: uint nTableSize;
! 68: uint nTableMask;
! 69: uint nNumOfElements;
! 70: ulong nNextFreeElement;
! 71: Bucket *pInternalPointer; /* Used for element traversal */
! 72: Bucket *pListHead;
! 73: Bucket *pListTail;
! 74: Bucket **arBuckets;
! 75: dtor_func_t pDestructor;
! 76: zend_bool persistent;
! 77: unsigned char nApplyCount;
! 78: zend_bool bApplyProtection;
! 79: #if ZEND_DEBUG
! 80: int inconsistent;
! 81: #endif
! 82: } HashTable;
! 83:
! 84:
! 85: typedef struct _zend_hash_key {
! 86: char *arKey;
! 87: uint nKeyLength;
! 88: ulong h;
! 89: } zend_hash_key;
! 90:
! 91:
! 92: typedef zend_bool (*merge_checker_func_t)(HashTable *target_ht, void *source_data, zend_hash_key *hash_key, void *pParam);
! 93:
! 94: typedef Bucket* HashPosition;
! 95:
! 96: BEGIN_EXTERN_C()
! 97:
! 98: /* startup/shutdown */
! 99: ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC);
! 100: ZEND_API int _zend_hash_init_ex(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent, zend_bool bApplyProtection ZEND_FILE_LINE_DC);
! 101: ZEND_API void zend_hash_destroy(HashTable *ht);
! 102: ZEND_API void zend_hash_clean(HashTable *ht);
! 103: #define zend_hash_init(ht, nSize, pHashFunction, pDestructor, persistent) _zend_hash_init((ht), (nSize), (pHashFunction), (pDestructor), (persistent) ZEND_FILE_LINE_CC)
! 104: #define zend_hash_init_ex(ht, nSize, pHashFunction, pDestructor, persistent, bApplyProtection) _zend_hash_init_ex((ht), (nSize), (pHashFunction), (pDestructor), (persistent), (bApplyProtection) ZEND_FILE_LINE_CC)
! 105:
! 106: /* additions/updates/changes */
! 107: ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC);
! 108: #define zend_hash_update(ht, arKey, nKeyLength, pData, nDataSize, pDest) \
! 109: _zend_hash_add_or_update(ht, arKey, nKeyLength, pData, nDataSize, pDest, HASH_UPDATE ZEND_FILE_LINE_CC)
! 110: #define zend_hash_add(ht, arKey, nKeyLength, pData, nDataSize, pDest) \
! 111: _zend_hash_add_or_update(ht, arKey, nKeyLength, pData, nDataSize, pDest, HASH_ADD ZEND_FILE_LINE_CC)
! 112:
! 113: ZEND_API int _zend_hash_quick_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC);
! 114: #define zend_hash_quick_update(ht, arKey, nKeyLength, h, pData, nDataSize, pDest) \
! 115: _zend_hash_quick_add_or_update(ht, arKey, nKeyLength, h, pData, nDataSize, pDest, HASH_UPDATE ZEND_FILE_LINE_CC)
! 116: #define zend_hash_quick_add(ht, arKey, nKeyLength, h, pData, nDataSize, pDest) \
! 117: _zend_hash_quick_add_or_update(ht, arKey, nKeyLength, h, pData, nDataSize, pDest, HASH_ADD ZEND_FILE_LINE_CC)
! 118:
! 119: ZEND_API int _zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC);
! 120: #define zend_hash_index_update(ht, h, pData, nDataSize, pDest) \
! 121: _zend_hash_index_update_or_next_insert(ht, h, pData, nDataSize, pDest, HASH_UPDATE ZEND_FILE_LINE_CC)
! 122: #define zend_hash_next_index_insert(ht, pData, nDataSize, pDest) \
! 123: _zend_hash_index_update_or_next_insert(ht, 0, pData, nDataSize, pDest, HASH_NEXT_INSERT ZEND_FILE_LINE_CC)
! 124:
! 125: ZEND_API int zend_hash_add_empty_element(HashTable *ht, const char *arKey, uint nKeyLength);
! 126:
! 127:
! 128: #define ZEND_HASH_APPLY_KEEP 0
! 129: #define ZEND_HASH_APPLY_REMOVE 1<<0
! 130: #define ZEND_HASH_APPLY_STOP 1<<1
! 131:
! 132: typedef int (*apply_func_t)(void *pDest TSRMLS_DC);
! 133: typedef int (*apply_func_arg_t)(void *pDest, void *argument TSRMLS_DC);
! 134: typedef int (*apply_func_args_t)(void *pDest TSRMLS_DC, int num_args, va_list args, zend_hash_key *hash_key);
! 135:
! 136: ZEND_API void zend_hash_graceful_destroy(HashTable *ht);
! 137: ZEND_API void zend_hash_graceful_reverse_destroy(HashTable *ht);
! 138: ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC);
! 139: ZEND_API void zend_hash_apply_with_argument(HashTable *ht, apply_func_arg_t apply_func, void * TSRMLS_DC);
! 140: ZEND_API void zend_hash_apply_with_arguments(HashTable *ht TSRMLS_DC, apply_func_args_t apply_func, int, ...);
! 141:
! 142: /* This function should be used with special care (in other words,
! 143: * it should usually not be used). When used with the ZEND_HASH_APPLY_STOP
! 144: * return value, it assumes things about the order of the elements in the hash.
! 145: * Also, it does not provide the same kind of reentrancy protection that
! 146: * the standard apply functions do.
! 147: */
! 148: ZEND_API void zend_hash_reverse_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC);
! 149:
! 150:
! 151: /* Deletes */
! 152: ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag);
! 153: #define zend_hash_del(ht, arKey, nKeyLength) \
! 154: zend_hash_del_key_or_index(ht, arKey, nKeyLength, 0, HASH_DEL_KEY)
! 155: #define zend_hash_quick_del(ht, arKey, nKeyLength, h) \
! 156: zend_hash_del_key_or_index(ht, arKey, nKeyLength, h, HASH_DEL_KEY_QUICK)
! 157: #define zend_hash_index_del(ht, h) \
! 158: zend_hash_del_key_or_index(ht, NULL, 0, h, HASH_DEL_INDEX)
! 159:
! 160: ZEND_API ulong zend_get_hash_value(const char *arKey, uint nKeyLength);
! 161:
! 162: /* Data retreival */
! 163: ZEND_API int zend_hash_find(const HashTable *ht, const char *arKey, uint nKeyLength, void **pData);
! 164: ZEND_API int zend_hash_quick_find(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h, void **pData);
! 165: ZEND_API int zend_hash_index_find(const HashTable *ht, ulong h, void **pData);
! 166:
! 167: /* Misc */
! 168: ZEND_API int zend_hash_exists(const HashTable *ht, const char *arKey, uint nKeyLength);
! 169: ZEND_API int zend_hash_quick_exists(const HashTable *ht, const char *arKey, uint nKeyLength, ulong h);
! 170: ZEND_API int zend_hash_index_exists(const HashTable *ht, ulong h);
! 171: ZEND_API ulong zend_hash_next_free_element(const HashTable *ht);
! 172:
! 173:
! 174: /* traversing */
! 175: #define zend_hash_has_more_elements_ex(ht, pos) \
! 176: (zend_hash_get_current_key_type_ex(ht, pos) == HASH_KEY_NON_EXISTANT ? FAILURE : SUCCESS)
! 177: ZEND_API int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos);
! 178: ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos);
! 179: ZEND_API int zend_hash_get_current_key_ex(const HashTable *ht, char **str_index, uint *str_length, ulong *num_index, zend_bool duplicate, HashPosition *pos);
! 180: ZEND_API int zend_hash_get_current_key_type_ex(HashTable *ht, HashPosition *pos);
! 181: ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosition *pos);
! 182: ZEND_API void zend_hash_internal_pointer_reset_ex(HashTable *ht, HashPosition *pos);
! 183: ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos);
! 184: ZEND_API int zend_hash_update_current_key_ex(HashTable *ht, int key_type, const char *str_index, uint str_length, ulong num_index, int mode, HashPosition *pos);
! 185:
! 186: typedef struct _HashPointer {
! 187: HashPosition pos;
! 188: ulong h;
! 189: } HashPointer;
! 190:
! 191: ZEND_API int zend_hash_get_pointer(const HashTable *ht, HashPointer *ptr);
! 192: ZEND_API int zend_hash_set_pointer(HashTable *ht, const HashPointer *ptr);
! 193:
! 194: #define zend_hash_has_more_elements(ht) \
! 195: zend_hash_has_more_elements_ex(ht, NULL)
! 196: #define zend_hash_move_forward(ht) \
! 197: zend_hash_move_forward_ex(ht, NULL)
! 198: #define zend_hash_move_backwards(ht) \
! 199: zend_hash_move_backwards_ex(ht, NULL)
! 200: #define zend_hash_get_current_key(ht, str_index, num_index, duplicate) \
! 201: zend_hash_get_current_key_ex(ht, str_index, NULL, num_index, duplicate, NULL)
! 202: #define zend_hash_get_current_key_type(ht) \
! 203: zend_hash_get_current_key_type_ex(ht, NULL)
! 204: #define zend_hash_get_current_data(ht, pData) \
! 205: zend_hash_get_current_data_ex(ht, pData, NULL)
! 206: #define zend_hash_internal_pointer_reset(ht) \
! 207: zend_hash_internal_pointer_reset_ex(ht, NULL)
! 208: #define zend_hash_internal_pointer_end(ht) \
! 209: zend_hash_internal_pointer_end_ex(ht, NULL)
! 210: #define zend_hash_update_current_key(ht, key_type, str_index, str_length, num_index) \
! 211: zend_hash_update_current_key_ex(ht, key_type, str_index, str_length, num_index, HASH_UPDATE_KEY_ANYWAY, NULL)
! 212:
! 213: /* Copying, merging and sorting */
! 214: ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size);
! 215: ZEND_API void _zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size, int overwrite ZEND_FILE_LINE_DC);
! 216: ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, uint size, merge_checker_func_t pMergeSource, void *pParam);
! 217: ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, int renumber TSRMLS_DC);
! 218: ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC);
! 219: ZEND_API int zend_hash_minmax(const HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC);
! 220:
! 221: #define zend_hash_merge(target, source, pCopyConstructor, tmp, size, overwrite) \
! 222: _zend_hash_merge(target, source, pCopyConstructor, tmp, size, overwrite ZEND_FILE_LINE_CC)
! 223:
! 224: ZEND_API int zend_hash_num_elements(const HashTable *ht);
! 225:
! 226: ZEND_API int zend_hash_rehash(HashTable *ht);
! 227:
! 228: /*
! 229: * DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
! 230: *
! 231: * This is Daniel J. Bernstein's popular `times 33' hash function as
! 232: * posted by him years ago on comp.lang.c. It basically uses a function
! 233: * like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
! 234: * known hash functions for strings. Because it is both computed very
! 235: * fast and distributes very well.
! 236: *
! 237: * The magic of number 33, i.e. why it works better than many other
! 238: * constants, prime or not, has never been adequately explained by
! 239: * anyone. So I try an explanation: if one experimentally tests all
! 240: * multipliers between 1 and 256 (as RSE did now) one detects that even
! 241: * numbers are not useable at all. The remaining 128 odd numbers
! 242: * (except for the number 1) work more or less all equally well. They
! 243: * all distribute in an acceptable way and this way fill a hash table
! 244: * with an average percent of approx. 86%.
! 245: *
! 246: * If one compares the Chi^2 values of the variants, the number 33 not
! 247: * even has the best value. But the number 33 and a few other equally
! 248: * good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
! 249: * advantage to the remaining numbers in the large set of possible
! 250: * multipliers: their multiply operation can be replaced by a faster
! 251: * operation based on just one shift plus either a single addition
! 252: * or subtraction operation. And because a hash function has to both
! 253: * distribute good _and_ has to be very fast to compute, those few
! 254: * numbers should be preferred and seems to be the reason why Daniel J.
! 255: * Bernstein also preferred it.
! 256: *
! 257: *
! 258: * -- Ralf S. Engelschall <rse@engelschall.com>
! 259: */
! 260:
! 261: static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
! 262: {
! 263: register ulong hash = 5381;
! 264:
! 265: /* variant with the hash unrolled eight times */
! 266: for (; nKeyLength >= 8; nKeyLength -= 8) {
! 267: hash = ((hash << 5) + hash) + *arKey++;
! 268: hash = ((hash << 5) + hash) + *arKey++;
! 269: hash = ((hash << 5) + hash) + *arKey++;
! 270: hash = ((hash << 5) + hash) + *arKey++;
! 271: hash = ((hash << 5) + hash) + *arKey++;
! 272: hash = ((hash << 5) + hash) + *arKey++;
! 273: hash = ((hash << 5) + hash) + *arKey++;
! 274: hash = ((hash << 5) + hash) + *arKey++;
! 275: }
! 276: switch (nKeyLength) {
! 277: case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
! 278: case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
! 279: case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
! 280: case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
! 281: case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
! 282: case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
! 283: case 1: hash = ((hash << 5) + hash) + *arKey++; break;
! 284: case 0: break;
! 285: EMPTY_SWITCH_DEFAULT_CASE()
! 286: }
! 287: return hash;
! 288: }
! 289:
! 290:
! 291: ZEND_API ulong zend_hash_func(const char *arKey, uint nKeyLength);
! 292:
! 293: #if ZEND_DEBUG
! 294: /* debug */
! 295: void zend_hash_display_pListTail(const HashTable *ht);
! 296: void zend_hash_display(const HashTable *ht);
! 297: #endif
! 298:
! 299: END_EXTERN_C()
! 300:
! 301: #define ZEND_INIT_SYMTABLE(ht) \
! 302: ZEND_INIT_SYMTABLE_EX(ht, 2, 0)
! 303:
! 304: #define ZEND_INIT_SYMTABLE_EX(ht, n, persistent) \
! 305: zend_hash_init(ht, n, NULL, ZVAL_PTR_DTOR, persistent)
! 306:
! 307: #define ZEND_HANDLE_NUMERIC(key, length, func) do { \
! 308: register const char *tmp = key; \
! 309: \
! 310: if (*tmp == '-') { \
! 311: tmp++; \
! 312: } \
! 313: if (*tmp >= '0' && *tmp <= '9') { /* possibly a numeric index */ \
! 314: const char *end = key + length - 1; \
! 315: ulong idx; \
! 316: \
! 317: if ((*end != '\0') /* not a null terminated string */ \
! 318: || (*tmp == '0' && length > 2) /* numbers with leading zeros */ \
! 319: || (end - tmp > MAX_LENGTH_OF_LONG - 1) /* number too long */ \
! 320: || (SIZEOF_LONG == 4 && \
! 321: end - tmp == MAX_LENGTH_OF_LONG - 1 && \
! 322: *tmp > '2')) { /* overflow */ \
! 323: break; \
! 324: } \
! 325: idx = (*tmp - '0'); \
! 326: while (++tmp != end && *tmp >= '0' && *tmp <= '9') { \
! 327: idx = (idx * 10) + (*tmp - '0'); \
! 328: } \
! 329: if (tmp == end) { \
! 330: if (*key == '-') { \
! 331: if (idx-1 > LONG_MAX) { /* overflow */ \
! 332: break; \
! 333: } \
! 334: idx = (ulong)(-(long)idx); \
! 335: } else if (idx > LONG_MAX) { /* overflow */ \
! 336: break; \
! 337: } \
! 338: return func; \
! 339: } \
! 340: } \
! 341: } while (0)
! 342:
! 343: static inline int zend_symtable_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest) \
! 344: {
! 345: ZEND_HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_index_update(ht, idx, pData, nDataSize, pDest));
! 346: return zend_hash_update(ht, arKey, nKeyLength, pData, nDataSize, pDest);
! 347: }
! 348:
! 349:
! 350: static inline int zend_symtable_del(HashTable *ht, const char *arKey, uint nKeyLength)
! 351: {
! 352: ZEND_HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_index_del(ht, idx));
! 353: return zend_hash_del(ht, arKey, nKeyLength);
! 354: }
! 355:
! 356:
! 357: static inline int zend_symtable_find(HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
! 358: {
! 359: ZEND_HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_index_find(ht, idx, pData));
! 360: return zend_hash_find(ht, arKey, nKeyLength, pData);
! 361: }
! 362:
! 363:
! 364: static inline int zend_symtable_exists(HashTable *ht, const char *arKey, uint nKeyLength)
! 365: {
! 366: ZEND_HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_index_exists(ht, idx));
! 367: return zend_hash_exists(ht, arKey, nKeyLength);
! 368: }
! 369:
! 370: static inline int zend_symtable_update_current_key_ex(HashTable *ht, const char *arKey, uint nKeyLength, int mode, HashPosition *pos)
! 371: {
! 372: ZEND_HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_update_current_key_ex(ht, HASH_KEY_IS_LONG, NULL, 0, idx, mode, pos));
! 373: return zend_hash_update_current_key_ex(ht, HASH_KEY_IS_STRING, arKey, nKeyLength, 0, mode, pos);
! 374: }
! 375: #define zend_symtable_update_current_key(ht,arKey,nKeyLength,mode) \
! 376: zend_symtable_update_current_key_ex(ht, arKey, nKeyLength, mode, NULL)
! 377:
! 378:
! 379: #endif /* ZEND_HASH_H */
! 380:
! 381: /*
! 382: * Local variables:
! 383: * tab-width: 4
! 384: * c-basic-offset: 4
! 385: * indent-tabs-mode: t
! 386: * End:
! 387: */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to zend_hash.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / Zend