File:  [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / Zend / zend_hash.h
Revision 1.1.1.4 (vendor branch): download - view: text, annotated - select for diffs - revision graph
Sun Jun 15 20:04:03 2014 UTC (10 years, 4 months ago) by misho
Branches: php, MAIN
CVS tags: v5_4_29, HEAD
php 5.4.29

    1: /*
    2:    +----------------------------------------------------------------------+
    3:    | Zend Engine                                                          |
    4:    +----------------------------------------------------------------------+
    5:    | Copyright (c) 1998-2014 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,v 1.1.1.4 2014/06/15 20:04:03 misho Exp $ */
   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: 	const char *arKey;
   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: 	const 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_EX(key, length, idx, 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: 																			\
  316: 		if ((*end != '\0') /* not a null terminated string */				\
  317: 		 || (*tmp == '0' && length > 2) /* numbers with leading zeros */	\
  318: 		 || (end - tmp > MAX_LENGTH_OF_LONG - 1) /* number too long */		\
  319: 		 || (SIZEOF_LONG == 4 &&											\
  320: 		     end - tmp == MAX_LENGTH_OF_LONG - 1 &&							\
  321: 		     *tmp > '2')) { /* overflow */									\
  322: 			break;															\
  323: 		}																	\
  324: 		idx = (*tmp - '0');													\
  325: 		while (++tmp != end && *tmp >= '0' && *tmp <= '9') {				\
  326: 			idx = (idx * 10) + (*tmp - '0');								\
  327: 		}																	\
  328: 		if (tmp == end) {													\
  329: 			if (*key == '-') {												\
  330: 				if (idx-1 > LONG_MAX) { /* overflow */						\
  331: 					break;													\
  332: 				}															\
  333: 				idx = 0 - idx;               									\
  334: 			} else if (idx > LONG_MAX) { /* overflow */						\
  335: 				break;														\
  336: 			}																\
  337: 			func;															\
  338: 		}																	\
  339: 	}																		\
  340: } while (0)
  341: 
  342: #define ZEND_HANDLE_NUMERIC(key, length, func) do {							\
  343: 	ulong idx;																\
  344: 																			\
  345: 	ZEND_HANDLE_NUMERIC_EX(key, length, idx, return func);					\
  346: } while (0)
  347: 
  348: static inline int zend_symtable_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest)					\
  349: {
  350: 	ZEND_HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_index_update(ht, idx, pData, nDataSize, pDest));
  351: 	return zend_hash_update(ht, arKey, nKeyLength, pData, nDataSize, pDest);
  352: }
  353: 
  354: 
  355: static inline int zend_symtable_del(HashTable *ht, const char *arKey, uint nKeyLength)
  356: {
  357: 	ZEND_HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_index_del(ht, idx));
  358: 	return zend_hash_del(ht, arKey, nKeyLength);
  359: }
  360: 
  361: 
  362: static inline int zend_symtable_find(HashTable *ht, const char *arKey, uint nKeyLength, void **pData)
  363: {
  364: 	ZEND_HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_index_find(ht, idx, pData));
  365: 	return zend_hash_find(ht, arKey, nKeyLength, pData);
  366: }
  367: 
  368: 
  369: static inline int zend_symtable_exists(HashTable *ht, const char *arKey, uint nKeyLength)
  370: {
  371: 	ZEND_HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_index_exists(ht, idx));
  372: 	return zend_hash_exists(ht, arKey, nKeyLength);
  373: }
  374: 
  375: static inline int zend_symtable_update_current_key_ex(HashTable *ht, const char *arKey, uint nKeyLength, int mode, HashPosition *pos)
  376: {
  377: 	ZEND_HANDLE_NUMERIC(arKey, nKeyLength, zend_hash_update_current_key_ex(ht, HASH_KEY_IS_LONG, NULL, 0, idx, mode, pos));
  378: 	return zend_hash_update_current_key_ex(ht, HASH_KEY_IS_STRING, arKey, nKeyLength, 0, mode, pos);
  379: }
  380: #define zend_symtable_update_current_key(ht,arKey,nKeyLength,mode) \
  381: 	zend_symtable_update_current_key_ex(ht, arKey, nKeyLength, mode, NULL)
  382: 
  383: 
  384: #endif							/* ZEND_HASH_H */
  385: 
  386: /*
  387:  * Local variables:
  388:  * tab-width: 4
  389:  * c-basic-offset: 4
  390:  * indent-tabs-mode: t
  391:  * End:
  392:  */

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>