Skip to content

Instantly share code, notes, and snippets.

/php-5.3.4-hashtable-optimization.patch

Created December 31, 2010 15:47
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anonymous/761094 to your computer and use it in GitHub Desktop.
Save anonymous/761094 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
php-5.3.4-hashtable-optimization.patch
Index: Zend/zend_hash.c
===================================================================
--- Zend/zend_hash.c 2010-12-30 17:09:14.000000000 +0100
+++ Zend/zend_hash.c 2010-12-31 01:45:14.000000000 +0100
@@ -5,7 +5,7 @@
| Copyright (c) 1998-2010 Zend Technologies Ltd. (http://www.zend.com) |
+----------------------------------------------------------------------+
| This source file is subject to version 2.00 of the Zend license, |
- | that is bundled with this package in the file LICENSE, and is |
+ | that is bundled with this package in the file LICENSE, and is |
| available through the world-wide-web at the following url: |
| http://www.zend.com/license/2_00.txt. |
| If you did not receive a copy of the Zend license and are unable to |
@@ -21,12 +21,16 @@
#include "zend.h"
-#define CONNECT_TO_BUCKET_DLLIST(element, list_head) \
- (element)->pNext = (list_head); \
- (element)->pLast = NULL; \
- if ((element)->pNext) { \
- (element)->pNext->pLast = (element); \
- }
+#define ZEND_HASH_SMALL_TABLE_SIZE 64
+#define ZEND_HASH_MIN_TABLE_SIZE 4
+#define ZEND_HASH_SMALL_LOAD_FACTOR_TABLE_SIZE 16
+#define ZEND_HASH_SMALL_LOAD_FACTOR_INV 1.75
+#define ZEND_HASH_LOAD_FACTOR_INV 1.25
+
+#define EQ_INDEX(ptr,index) \
+ (EXPECTED(((ptr)->nKeyLength == 0) && (ptr)->h == index))
+
+#define CONNECT_TO_BUCKET_DLLIST(element, list_head)
#define CONNECT_TO_GLOBAL_DLLIST(element, ht) \
(element)->pListLast = (ht)->pListTail; \
@@ -91,7 +95,9 @@
#define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
- if ((ht)->nNumOfElements > (ht)->nTableSize) { \
+ if ((ht)->nTableSize <= ZEND_HASH_SMALL_LOAD_FACTOR_TABLE_SIZE ? \
+ ((ht)->nNumOfElements*ZEND_HASH_SMALL_LOAD_FACTOR_INV > (ht)->nTableSize) : \
+ ((ht)->nNumOfElements*ZEND_HASH_LOAD_FACTOR_INV > (ht)->nTableSize)) { \
zend_hash_do_resize(ht); \
}
@@ -102,7 +108,6 @@
return zend_inline_hash_func(arKey, nKeyLength);
}
-
#define UPDATE_DATA(ht, p, pData, nDataSize) \
if (nDataSize == sizeof(void*)) { \
if ((p)->pData != &(p)->pDataPtr) { \
@@ -136,11 +141,10 @@
}
-
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)
{
uint i = 3;
- Bucket **tmp;
+ void *tmp;
SET_INCONSISTENT(HT_OK);
@@ -151,7 +155,10 @@
while ((1U << i) < nSize) {
i++;
}
- ht->nTableSize = 1 << i;
+ ht->nTableSize = 1 << (i+1);
+ if (ht->nTableSize < ZEND_HASH_MIN_TABLE_SIZE) {
+ ht->nTableSize = ZEND_HASH_MIN_TABLE_SIZE;
+ }
}
ht->nTableMask = ht->nTableSize - 1;
@@ -165,21 +172,15 @@
ht->persistent = persistent;
ht->nApplyCount = 0;
ht->bApplyProtection = 1;
-
- /* Uses ecalloc() so that Bucket* == NULL */
- if (persistent) {
- tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
- if (!tmp) {
- return FAILURE;
- }
- ht->arBuckets = tmp;
- } else {
- tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
- if (tmp) {
- ht->arBuckets = tmp;
- }
+
+ tmp = pemalloc_rel(ht->nTableSize * (sizeof(Bucket*)+1), ht->persistent);
+ if (!tmp) {
+ return FAILURE;
}
-
+ ht->arBuckets = (Bucket**)tmp;
+ ht->arEmpty = ((uchar*)tmp) + (ht->nTableSize * (sizeof(Bucket*)));
+ memset(ht->arEmpty, 0, ht->nTableSize * 1);
+
return SUCCESS;
}
@@ -216,38 +217,34 @@
}
h = zend_inline_hash_func(arKey, nKeyLength);
- nIndex = h & ht->nTableMask;
+ nIndex = ZEND_HASH_BUCKET(ht, h);
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
- if (!memcmp(p->arKey, arKey, nKeyLength)) {
- if (flag & HASH_ADD) {
- return FAILURE;
- }
- HANDLE_BLOCK_INTERRUPTIONS();
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+ if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+ if (flag & HASH_ADD) {
+ return FAILURE;
+ }
+ HANDLE_BLOCK_INTERRUPTIONS();
#if ZEND_DEBUG
- if (p->pData == pData) {
- ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
- HANDLE_UNBLOCK_INTERRUPTIONS();
- return FAILURE;
- }
-#endif
- if (ht->pDestructor) {
- ht->pDestructor(p->pData);
- }
- UPDATE_DATA(ht, p, pData, nDataSize);
- if (pDest) {
- *pDest = p->pData;
- }
+ if (p->pData == pData) {
+ ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
HANDLE_UNBLOCK_INTERRUPTIONS();
- return SUCCESS;
+ return FAILURE;
+ }
+#endif
+ if (ht->pDestructor) {
+ ht->pDestructor(p->pData);
+ }
+ UPDATE_DATA(ht, p, pData, nDataSize);
+ if (pDest) {
+ *pDest = p->pData;
}
+ HANDLE_UNBLOCK_INTERRUPTIONS();
+ return SUCCESS;
}
- p = p->pNext;
}
-
- p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
+
+ p = (Bucket *)pemalloc_rel(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
if (!p) {
return FAILURE;
}
@@ -262,11 +259,11 @@
HANDLE_BLOCK_INTERRUPTIONS();
CONNECT_TO_GLOBAL_DLLIST(p, ht);
- ht->arBuckets[nIndex] = p;
+ ZEND_HASH_FILL_BUCKET(ht, nIndex, p);
HANDLE_UNBLOCK_INTERRUPTIONS();
ht->nNumOfElements++;
- ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
+ ZEND_HASH_IF_FULL_DO_RESIZE(ht);
return SUCCESS;
}
@@ -281,38 +278,34 @@
return zend_hash_index_update(ht, h, pData, nDataSize, pDest);
}
- nIndex = h & ht->nTableMask;
-
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
- if (!memcmp(p->arKey, arKey, nKeyLength)) {
- if (flag & HASH_ADD) {
- return FAILURE;
- }
- HANDLE_BLOCK_INTERRUPTIONS();
+ nIndex = ZEND_HASH_BUCKET(ht, h);
+
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+ if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+ if (flag & HASH_ADD) {
+ return FAILURE;
+ }
+ HANDLE_BLOCK_INTERRUPTIONS();
#if ZEND_DEBUG
- if (p->pData == pData) {
- ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
- HANDLE_UNBLOCK_INTERRUPTIONS();
- return FAILURE;
- }
-#endif
- if (ht->pDestructor) {
- ht->pDestructor(p->pData);
- }
- UPDATE_DATA(ht, p, pData, nDataSize);
- if (pDest) {
- *pDest = p->pData;
- }
+ if (p->pData == pData) {
+ ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData\n");
HANDLE_UNBLOCK_INTERRUPTIONS();
- return SUCCESS;
+ return FAILURE;
}
+#endif
+ if (ht->pDestructor) {
+ ht->pDestructor(p->pData);
+ }
+ UPDATE_DATA(ht, p, pData, nDataSize);
+ if (pDest) {
+ *pDest = p->pData;
+ }
+ HANDLE_UNBLOCK_INTERRUPTIONS();
+ return SUCCESS;
}
- p = p->pNext;
}
-
- p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
+
+ p = (Bucket *)pemalloc_rel(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
if (!p) {
return FAILURE;
}
@@ -321,7 +314,7 @@
p->nKeyLength = nKeyLength;
INIT_DATA(ht, p, pData, nDataSize);
p->h = h;
-
+
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
if (pDest) {
@@ -329,12 +322,12 @@
}
HANDLE_BLOCK_INTERRUPTIONS();
- ht->arBuckets[nIndex] = p;
+ ZEND_HASH_FILL_BUCKET(ht, nIndex, p);
CONNECT_TO_GLOBAL_DLLIST(p, ht);
HANDLE_UNBLOCK_INTERRUPTIONS();
ht->nNumOfElements++;
- ZEND_HASH_IF_FULL_DO_RESIZE(ht); /* If the Hash table is full, resize it */
+ ZEND_HASH_IF_FULL_DO_RESIZE(ht);
return SUCCESS;
}
@@ -357,11 +350,10 @@
if (flag & HASH_NEXT_INSERT) {
h = ht->nNextFreeElement;
}
- nIndex = h & ht->nTableMask;
+ nIndex = ZEND_HASH_BUCKET(ht, h);
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if ((p->nKeyLength == 0) && (p->h == h)) {
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+ if (EQ_INDEX(p, h)) {
if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) {
return FAILURE;
}
@@ -386,7 +378,6 @@
}
return SUCCESS;
}
- p = p->pNext;
}
p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent);
if (!p) {
@@ -402,7 +393,7 @@
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
HANDLE_BLOCK_INTERRUPTIONS();
- ht->arBuckets[nIndex] = p;
+ ZEND_HASH_FILL_BUCKET(ht, nIndex, p);
CONNECT_TO_GLOBAL_DLLIST(p, ht);
HANDLE_UNBLOCK_INTERRUPTIONS();
@@ -414,27 +405,28 @@
return SUCCESS;
}
-
static int zend_hash_do_resize(HashTable *ht)
{
- Bucket **t;
+ void *t;
+ uint dest_size = ht->nTableSize <= ZEND_HASH_SMALL_TABLE_SIZE ? (ht->nTableSize << 2) : (ht->nTableSize << 1);
IS_CONSISTENT(ht);
- if ((ht->nTableSize << 1) > 0) { /* Let's double the table size */
- t = (Bucket **) perealloc_recoverable(ht->arBuckets, (ht->nTableSize << 1) * sizeof(Bucket *), ht->persistent);
- if (t) {
- HANDLE_BLOCK_INTERRUPTIONS();
- ht->arBuckets = t;
- ht->nTableSize = (ht->nTableSize << 1);
- ht->nTableMask = ht->nTableSize - 1;
- zend_hash_rehash(ht);
- HANDLE_UNBLOCK_INTERRUPTIONS();
- return SUCCESS;
+ if (dest_size > 0) { /* Let's change the table size */
+ t = perealloc(ht->arBuckets, dest_size * (sizeof(Bucket *) + 1), ht->persistent);
+ if (!t) {
+ return FAILURE;
}
- return FAILURE;
+ HANDLE_BLOCK_INTERRUPTIONS();
+ ht->nTableSize = dest_size;
+ ht->nTableMask = ht->nTableSize - 1;
+ ht->arBuckets = (Bucket**)t;
+ ht->arEmpty = ((uchar*)t) + (ht->nTableSize * (sizeof(Bucket*)));
+ zend_hash_rehash(ht);
+ HANDLE_UNBLOCK_INTERRUPTIONS();
+ return SUCCESS;
}
- return SUCCESS;
+ return FAILURE;
}
ZEND_API int zend_hash_rehash(HashTable *ht)
@@ -444,17 +436,41 @@
IS_CONSISTENT(ht);
- memset(ht->arBuckets, 0, ht->nTableSize * sizeof(Bucket *));
+ memset(ht->arEmpty, 0, ht->nTableSize * 1);
+
p = ht->pListHead;
while (p != NULL) {
- nIndex = p->h & ht->nTableMask;
+ nIndex = ZEND_HASH_BUCKET(ht, p->h);
+ ZEND_HASH_FIND_FREE(ht, nIndex);
+ ZEND_HASH_FILL_BUCKET(ht, nIndex, p);
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
- ht->arBuckets[nIndex] = p;
p = p->pListNext;
}
return SUCCESS;
}
+inline void zend_hash_free_bucket(HashTable *ht, uint nIndex) {
+ uint nIndexSlot = nIndex;
+ uint nSourceIndex;
+
+ ZEND_HASH_MAKE_ELEMENT_EMPTY(ht, nIndexSlot);
+ for(;;) {
+ ZEND_HASH_NEXT_INDEX(ht, nIndexSlot);
+ if (!ZEND_HASH_BUCKET_IS_OCCUPIED(ht, nIndexSlot)) {
+ break;
+ }
+ nSourceIndex = ZEND_HASH_BUCKET(ht, ht->arBuckets[nIndexSlot]->h);
+ if ((nIndex < nIndexSlot) ?
+ ((nIndex < nSourceIndex) && (nSourceIndex <= nIndexSlot)) :
+ ((nIndex < nSourceIndex) || (nSourceIndex <= nIndexSlot))) {
+ continue;
+ }
+ ZEND_HASH_FILL_BUCKET(ht, nIndex, ht->arBuckets[nIndexSlot]);
+ nIndex = nIndexSlot;
+ ZEND_HASH_MAKE_ELEMENT_EMPTY(ht, nIndexSlot);
+ }
+}
+
ZEND_API int zend_hash_del_key_or_index(HashTable *ht, const char *arKey, uint nKeyLength, ulong h, int flag)
{
uint nIndex;
@@ -465,27 +481,17 @@
if (flag == HASH_DEL_KEY) {
h = zend_inline_hash_func(arKey, nKeyLength);
}
- nIndex = h & ht->nTableMask;
+ nIndex = ZEND_HASH_BUCKET(ht, h);
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if ((p->h == h)
- && (p->nKeyLength == nKeyLength)
- && ((p->nKeyLength == 0) /* Numeric index (short circuits the memcmp() check) */
- || !memcmp(p->arKey, arKey, nKeyLength))) { /* String index */
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+ if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
HANDLE_BLOCK_INTERRUPTIONS();
- if (p == ht->arBuckets[nIndex]) {
- ht->arBuckets[nIndex] = p->pNext;
- } else {
- p->pLast->pNext = p->pNext;
- }
- if (p->pNext) {
- p->pNext->pLast = p->pLast;
- }
+
+ zend_hash_free_bucket(ht, nIndex);
+
if (p->pListLast != NULL) {
p->pListLast->pListNext = p->pListNext;
- } else {
- /* Deleting the head of the list */
+ } else {
ht->pListHead = p->pListNext;
}
if (p->pListNext != NULL) {
@@ -503,11 +509,11 @@
pefree(p->pData, ht->persistent);
}
pefree(p, ht->persistent);
+
HANDLE_UNBLOCK_INTERRUPTIONS();
ht->nNumOfElements--;
return SUCCESS;
}
- p = p->pNext;
}
return FAILURE;
}
@@ -559,7 +565,7 @@
}
pefree(q, ht->persistent);
}
- memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
+ memset(ht->arEmpty, 0, ht->nTableSize*1);
ht->pListHead = NULL;
ht->pListTail = NULL;
ht->nNumOfElements = 0;
@@ -571,31 +577,31 @@
/* This function is used by the various apply() functions.
* It deletes the passed bucket, and returns the address of the
- * next bucket. The hash *may* be altered during that time, the
+ * next bucket. The hash *may* be altered during that time, the
* returned value will still be valid.
*/
static Bucket *zend_hash_apply_deleter(HashTable *ht, Bucket *p)
{
Bucket *retval;
- HANDLE_BLOCK_INTERRUPTIONS();
- if (p->pLast) {
- p->pLast->pNext = p->pNext;
- } else {
- uint nIndex;
+ uint nIndex;
- nIndex = p->h & ht->nTableMask;
- ht->arBuckets[nIndex] = p->pNext;
- }
- if (p->pNext) {
- p->pNext->pLast = p->pLast;
- } else {
- /* Nothing to do as this list doesn't have a tail */
+ nIndex = ZEND_HASH_BUCKET(ht, p->h);
+ for (; ht->arBuckets[nIndex] != p; ZEND_HASH_NEXT_INDEX(ht, nIndex)) {
+#ifdef ZEND_DEBUG
+ if (!ZEND_HASH_BUCKET_IS_OCCUPIED(ht, nIndex)) {
+ zend_output_debug_string(1, "No element to delete");
+ }
+#endif
}
+ HANDLE_BLOCK_INTERRUPTIONS();
+
+ zend_hash_free_bucket(ht, nIndex);
+
if (p->pListLast != NULL) {
p->pListLast->pListNext = p->pListNext;
- } else {
+ } else {
/* Deleting the head of the list */
ht->pListHead = p->pListNext;
}
@@ -655,9 +661,9 @@
SET_INCONSISTENT(HT_DESTROYED);
}
-/* This is used to recurse elements and selectively delete certain entries
- * from a hashtable. apply_func() receives the data and decides if the entry
- * should be deleted or recursion should be stopped. The following three
+/* This is used to recurse elements and selectively delete certain entries
+ * from a hashtable. apply_func() receives the data and decides if the entry
+ * should be deleted or recursion should be stopped. The following three
* return codes are possible:
* ZEND_HASH_APPLY_KEEP - continue
* ZEND_HASH_APPLY_STOP - stop iteration
@@ -674,7 +680,7 @@
p = ht->pListHead;
while (p != NULL) {
int result = apply_func(p->pData TSRMLS_CC);
-
+
if (result & ZEND_HASH_APPLY_REMOVE) {
p = zend_hash_apply_deleter(ht, p);
} else {
@@ -698,7 +704,7 @@
p = ht->pListHead;
while (p != NULL) {
int result = apply_func(p->pData, argument TSRMLS_CC);
-
+
if (result & ZEND_HASH_APPLY_REMOVE) {
p = zend_hash_apply_deleter(ht, p);
} else {
@@ -878,17 +884,12 @@
IS_CONSISTENT(ht);
h = zend_inline_hash_func(arKey, nKeyLength);
- nIndex = h & ht->nTableMask;
-
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
- if (!memcmp(p->arKey, arKey, nKeyLength)) {
- *pData = p->pData;
- return SUCCESS;
- }
+ nIndex = ZEND_HASH_BUCKET(ht, h);
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+ if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+ *pData = p->pData;
+ return SUCCESS;
}
- p = p->pNext;
}
return FAILURE;
}
@@ -905,17 +906,13 @@
IS_CONSISTENT(ht);
- nIndex = h & ht->nTableMask;
+ nIndex = ZEND_HASH_BUCKET(ht, h);
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
- if (!memcmp(p->arKey, arKey, nKeyLength)) {
- *pData = p->pData;
- return SUCCESS;
- }
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+ if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+ *pData = p->pData;
+ return SUCCESS;
}
- p = p->pNext;
}
return FAILURE;
}
@@ -930,16 +927,12 @@
IS_CONSISTENT(ht);
h = zend_inline_hash_func(arKey, nKeyLength);
- nIndex = h & ht->nTableMask;
+ nIndex = ZEND_HASH_BUCKET(ht, h);
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
- if (!memcmp(p->arKey, arKey, nKeyLength)) {
- return 1;
- }
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+ if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+ return 1;
}
- p = p->pNext;
}
return 0;
}
@@ -956,16 +949,12 @@
IS_CONSISTENT(ht);
- nIndex = h & ht->nTableMask;
+ nIndex = ZEND_HASH_BUCKET(ht, h);
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
- if (!memcmp(p->arKey, arKey, nKeyLength)) {
- return 1;
- }
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+ if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+ return 1;
}
- p = p->pNext;
}
return 0;
@@ -979,15 +968,13 @@
IS_CONSISTENT(ht);
- nIndex = h & ht->nTableMask;
+ nIndex = ZEND_HASH_BUCKET(ht, h);
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if ((p->h == h) && (p->nKeyLength == 0)) {
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+ if (EQ_INDEX(p, h)) {
*pData = p->pData;
return SUCCESS;
}
- p = p->pNext;
}
return FAILURE;
}
@@ -1000,14 +987,12 @@
IS_CONSISTENT(ht);
- nIndex = h & ht->nTableMask;
+ nIndex = ZEND_HASH_BUCKET(ht, h);
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if ((p->h == h) && (p->nKeyLength == 0)) {
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
+ if (EQ_INDEX(p, h)) {
return 1;
}
- p = p->pNext;
}
return 0;
}
@@ -1041,13 +1026,12 @@
Bucket *p;
IS_CONSISTENT(ht);
- p = ht->arBuckets[ptr->h & ht->nTableMask];
- while (p != NULL) {
+ uint nIndex = ZEND_HASH_BUCKET(ht, ptr->h);
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
if (p == ptr->pos) {
ht->pInternalPointer = p;
return 1;
}
- p = p->pNext;
}
return 0;
}
@@ -1065,7 +1049,7 @@
}
-/* This function will be extremely optimized by remembering
+/* This function will be extremely optimized by remembering
* the end of the list
*/
ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos)
@@ -1106,7 +1090,7 @@
}
-/* This function should be made binary safe */
+/* This function should be made binary safe */
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)
{
Bucket *p;
@@ -1176,6 +1160,8 @@
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)
{
Bucket *p;
+ Bucket *q;
+ uint nIndex;
p = pos ? (*pos) : ht->pInternalPointer;
@@ -1184,18 +1170,18 @@
if (p) {
if (key_type == HASH_KEY_IS_LONG) {
str_length = 0;
- if (!p->nKeyLength && p->h == num_index) {
+ if (EQ_INDEX(p, num_index)) {
return SUCCESS;
}
if (mode != HASH_UPDATE_KEY_ANYWAY) {
- Bucket *q = ht->arBuckets[num_index & ht->nTableMask];
+ nIndex = ZEND_HASH_BUCKET(ht, num_index);
int found = 0;
- while (q != NULL) {
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, q) {
if (q == p) {
found = 1;
- } else if (!q->nKeyLength && q->h == num_index) {
+ } else if (EQ_INDEX(q, num_index)) {
if (found) {
if (mode & HASH_UPDATE_KEY_IF_BEFORE) {
break;
@@ -1220,28 +1206,26 @@
}
}
}
- q = q->pNext;
}
}
zend_hash_index_del(ht, num_index);
} else if (key_type == HASH_KEY_IS_STRING) {
if (p->nKeyLength == str_length &&
- memcmp(p->arKey, str_index, str_length) == 0) {
+ memcmp(p->arKey, str_index, str_length) == 0) {
return SUCCESS;
}
if (mode != HASH_UPDATE_KEY_ANYWAY) {
ulong h = zend_inline_hash_func(str_index, str_length);
- Bucket *q = ht->arBuckets[h & ht->nTableMask];
+ nIndex = ZEND_HASH_BUCKET(ht, h);
int found = 0;
- while (q != NULL) {
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, q) {
if (q == p) {
found = 1;
- } else if (q->h == h && q->nKeyLength == str_length &&
- memcmp(q->arKey, str_index, str_length) == 0) {
- if (found) {
+ } else if (EQ_HASH_KEYS(q, str_index, h, str_length)) {
+ if (found) {
if (mode & HASH_UPDATE_KEY_IF_BEFORE) {
break;
} else {
@@ -1265,7 +1249,6 @@
}
}
}
- q = q->pNext;
}
}
@@ -1276,13 +1259,12 @@
HANDLE_BLOCK_INTERRUPTIONS();
- if (p->pNext) {
- p->pNext->pLast = p->pLast;
- }
- if (p->pLast) {
- p->pLast->pNext = p->pNext;
- } else{
- ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
+ nIndex = ZEND_HASH_BUCKET(ht, p->h);
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, q) {
+ if (p == q) {
+ zend_hash_free_bucket(ht, nIndex);
+ break;
+ }
}
if (p->nKeyLength != str_length) {
@@ -1324,8 +1306,10 @@
p->h = zend_inline_hash_func(str_index, str_length);
}
- CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[p->h & ht->nTableMask]);
- ht->arBuckets[p->h & ht->nTableMask] = p;
+ nIndex = ZEND_HASH_BUCKET(ht, p->h);
+ CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
+ ZEND_HASH_FIND_FREE(ht, nIndex);
+ ZEND_HASH_FILL_BUCKET(ht, nIndex, p);
HANDLE_UNBLOCK_INTERRUPTIONS();
return SUCCESS;
@@ -1406,13 +1390,13 @@
IS_CONSISTENT(ht1);
IS_CONSISTENT(ht2);
- HASH_PROTECT_RECURSION(ht1);
- HASH_PROTECT_RECURSION(ht2);
+ HASH_PROTECT_RECURSION(ht1);
+ HASH_PROTECT_RECURSION(ht2);
result = ht1->nNumOfElements - ht2->nNumOfElements;
if (result!=0) {
- HASH_UNPROTECT_RECURSION(ht1);
- HASH_UNPROTECT_RECURSION(ht2);
+ HASH_UNPROTECT_RECURSION(ht1);
+ HASH_UNPROTECT_RECURSION(ht2);
return result;
}
@@ -1423,29 +1407,29 @@
while (p1) {
if (ordered && !p2) {
- HASH_UNPROTECT_RECURSION(ht1);
- HASH_UNPROTECT_RECURSION(ht2);
+ HASH_UNPROTECT_RECURSION(ht1);
+ HASH_UNPROTECT_RECURSION(ht2);
return 1; /* That's not supposed to happen */
}
if (ordered) {
if (p1->nKeyLength==0 && p2->nKeyLength==0) { /* numeric indices */
result = p1->h - p2->h;
if (result!=0) {
- HASH_UNPROTECT_RECURSION(ht1);
- HASH_UNPROTECT_RECURSION(ht2);
+ HASH_UNPROTECT_RECURSION(ht1);
+ HASH_UNPROTECT_RECURSION(ht2);
return result;
}
} else { /* string indices */
result = p1->nKeyLength - p2->nKeyLength;
if (result!=0) {
- HASH_UNPROTECT_RECURSION(ht1);
- HASH_UNPROTECT_RECURSION(ht2);
+ HASH_UNPROTECT_RECURSION(ht1);
+ HASH_UNPROTECT_RECURSION(ht2);
return result;
}
result = memcmp(p1->arKey, p2->arKey, p1->nKeyLength);
if (result!=0) {
- HASH_UNPROTECT_RECURSION(ht1);
- HASH_UNPROTECT_RECURSION(ht2);
+ HASH_UNPROTECT_RECURSION(ht1);
+ HASH_UNPROTECT_RECURSION(ht2);
return result;
}
}
@@ -1453,22 +1437,22 @@
} else {
if (p1->nKeyLength==0) { /* numeric index */
if (zend_hash_index_find(ht2, p1->h, &pData2)==FAILURE) {
- HASH_UNPROTECT_RECURSION(ht1);
- HASH_UNPROTECT_RECURSION(ht2);
+ HASH_UNPROTECT_RECURSION(ht1);
+ HASH_UNPROTECT_RECURSION(ht2);
return 1;
}
} else { /* string index */
if (zend_hash_quick_find(ht2, p1->arKey, p1->nKeyLength, p1->h, &pData2)==FAILURE) {
- HASH_UNPROTECT_RECURSION(ht1);
- HASH_UNPROTECT_RECURSION(ht2);
+ HASH_UNPROTECT_RECURSION(ht1);
+ HASH_UNPROTECT_RECURSION(ht2);
return 1;
}
}
}
result = compar(p1->pData, pData2 TSRMLS_CC);
if (result!=0) {
- HASH_UNPROTECT_RECURSION(ht1);
- HASH_UNPROTECT_RECURSION(ht2);
+ HASH_UNPROTECT_RECURSION(ht1);
+ HASH_UNPROTECT_RECURSION(ht2);
return result;
}
p1 = p1->pListNext;
@@ -1476,9 +1460,9 @@
p2 = p2->pListNext;
}
}
-
- HASH_UNPROTECT_RECURSION(ht1);
- HASH_UNPROTECT_RECURSION(ht2);
+
+ HASH_UNPROTECT_RECURSION(ht1);
+ HASH_UNPROTECT_RECURSION(ht2);
return 0;
}
@@ -1538,9 +1522,8 @@
for (i = 0; i < ht->nTableSize; i++) {
p = ht->arBuckets[i];
- while (p != NULL) {
+ if (ZEND_HASH_BUCKET_IS_OCCUPIED(ht, i)) {
zend_output_debug_string(0, "%s <==> 0x%lX\n", p->arKey, p->h);
- p = p->pNext;
}
}
Index: Zend/zend_hash.h
===================================================================
--- Zend/zend_hash.h 2010-12-30 17:09:14.000000000 +0100
+++ Zend/zend_hash.h 2010-12-31 01:03:46.000000000 +0100
@@ -48,18 +48,17 @@
typedef void (*dtor_func_t)(void *pDest);
typedef void (*copy_ctor_func_t)(void *pElement);
typedef void (*copy_ctor_param_func_t)(void *pElement, void *pParam);
+typedef unsigned char uchar;
struct _hashtable;
typedef struct bucket {
- ulong h; /* Used for numeric indexing */
+ ulong h;
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;
@@ -72,6 +71,7 @@
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets;
+ uchar *arEmpty;
dtor_func_t pDestructor;
zend_bool persistent;
unsigned char nApplyCount;
@@ -124,6 +124,31 @@
ZEND_API int zend_hash_add_empty_element(HashTable *ht, const char *arKey, uint nKeyLength);
+#define ZEND_HASH_BUCKET(ht, index) \
+ (((index) + ((index)<<4)) & (ht)->nTableMask)
+
+#define EQ_KEYS(a,b,n) (!memcmp((a), (b), (n)))
+#define EQ_HASH_KEYS(ptr,key,hash,len) (EXPECTED(((ptr)->h == (hash)) && \
+ ((ptr)->nKeyLength == (len)) && \
+ ((len) == 0 || EQ_KEYS((ptr)->arKey,(key),(len)))))
+
+#define ZEND_HASH_NEXT_INDEX(ht, index) \
+ (index) = (((index)+1) & (ht)->nTableMask)
+#define ZEND_HASH_BUCKET_IS_OCCUPIED(ht, index) \
+ ((ht)->arEmpty[(index)] != 0)
+// ((ht)->arBuckets[(index)] != NULL)
+#define ZEND_HASH_GET_BUCKET_AND_CHECK_OCCUPIED(ht, index, bucket) \
+ (bucket) = (ht)->arBuckets[(index)], ZEND_HASH_BUCKET_IS_OCCUPIED((ht), (index))
+#define ZEND_HASH_ITERATE_UNTIL_FREE(ht, index, bucket) \
+ for (; ZEND_HASH_GET_BUCKET_AND_CHECK_OCCUPIED((ht), (index), (bucket)); ZEND_HASH_NEXT_INDEX((ht), (index)))
+#define ZEND_HASH_FIND_FREE(ht, index) \
+ for (; ZEND_HASH_BUCKET_IS_OCCUPIED((ht), (index)); ZEND_HASH_NEXT_INDEX((ht), (index)))
+#define ZEND_HASH_FILL_BUCKET(ht, index, element) \
+ (ht)->arBuckets[(index)] = element; \
+ (ht)->arEmpty[(index)] = 1;
+#define ZEND_HASH_MAKE_ELEMENT_EMPTY(ht, index) \
+ (ht)->arEmpty[(index)] = 0;
+// (ht)->arBuckets[(index)] = 0;
#define ZEND_HASH_APPLY_KEEP 0
#define ZEND_HASH_APPLY_REMOVE 1<<0
@@ -225,54 +250,12 @@
ZEND_API int zend_hash_rehash(HashTable *ht);
-/*
- * DJBX33A (Daniel J. Bernstein, Times 33 with Addition)
- *
- * This is Daniel J. Bernstein's popular `times 33' hash function as
- * posted by him years ago on comp.lang.c. It basically uses a function
- * like ``hash(i) = hash(i-1) * 33 + str[i]''. This is one of the best
- * known hash functions for strings. Because it is both computed very
- * fast and distributes very well.
- *
- * The magic of number 33, i.e. why it works better than many other
- * constants, prime or not, has never been adequately explained by
- * anyone. So I try an explanation: if one experimentally tests all
- * multipliers between 1 and 256 (as RSE did now) one detects that even
- * numbers are not useable at all. The remaining 128 odd numbers
- * (except for the number 1) work more or less all equally well. They
- * all distribute in an acceptable way and this way fill a hash table
- * with an average percent of approx. 86%.
- *
- * If one compares the Chi^2 values of the variants, the number 33 not
- * even has the best value. But the number 33 and a few other equally
- * good numbers like 17, 31, 63, 127 and 129 have nevertheless a great
- * advantage to the remaining numbers in the large set of possible
- * multipliers: their multiply operation can be replaced by a faster
- * operation based on just one shift plus either a single addition
- * or subtraction operation. And because a hash function has to both
- * distribute good _and_ has to be very fast to compute, those few
- * numbers should be preferred and seems to be the reason why Daniel J.
- * Bernstein also preferred it.
- *
- *
- * -- Ralf S. Engelschall <rse@engelschall.com>
- */
-
static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength)
{
- register ulong hash = 5381;
+ ulong hash = 5381;
+ const ulong* ar = (ulong*)arKey;
- /* variant with the hash unrolled eight times */
- for (; nKeyLength >= 8; nKeyLength -= 8) {
- hash = ((hash << 5) + hash) + *arKey++;
- hash = ((hash << 5) + hash) + *arKey++;
- hash = ((hash << 5) + hash) + *arKey++;
- hash = ((hash << 5) + hash) + *arKey++;
- hash = ((hash << 5) + hash) + *arKey++;
- hash = ((hash << 5) + hash) + *arKey++;
- hash = ((hash << 5) + hash) + *arKey++;
- hash = ((hash << 5) + hash) + *arKey++;
- }
+ if (nKeyLength < sizeof(ulong)) {
switch (nKeyLength) {
case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
@@ -284,10 +267,17 @@
case 0: break;
EMPTY_SWITCH_DEFAULT_CASE()
}
- return hash;
+ } else {
+ const ulong* arEnd = (ulong*)(arKey + nKeyLength - sizeof(ulong));
+// memcpy(&hash, arKey, sizeof(ulong)); // hash = *arEnd, but this could be from unaligned address
+ hash = *arEnd;
+ for (; ar < arEnd; ar++) {
+ hash = ((hash << 5) + hash) + *ar;
+ }
+ }
+ return (hash<<16)|(hash%65165);
}
-
ZEND_API ulong zend_hash_func(const char *arKey, uint nKeyLength);
#if ZEND_DEBUG
Index: ext/spl/spl_array.c
===================================================================
--- ext/spl/spl_array.c 2010-12-30 17:07:19.000000000 +0100
+++ ext/spl/spl_array.c 2010-12-30 17:11:02.000000000 +0100
@@ -115,12 +115,11 @@
/* IS_CONSISTENT(ht);*/
/* HASH_PROTECT_RECURSION(ht);*/
- p = ht->arBuckets[intern->pos_h & ht->nTableMask];
- while (p != NULL) {
+ uint nIndex = ZEND_HASH_BUCKET(ht, intern->pos_h);
+ ZEND_HASH_ITERATE_UNTIL_FREE(ht, nIndex, p) {
if (p == intern->pos) {
return SUCCESS;
}
- p = p->pNext;
}
/* HASH_UNPROTECT_RECURSION(ht); */
spl_array_rewind(intern TSRMLS_CC);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment