Patch php-trunk-zend-hash-optimization for Scripting Engine problem Bug #53866
Patch version 2011-01-28 12:36 UTC
Return to Bug #53866 |
Download this patch
Patch Revisions:
Developer: marcin.babij@nasza-klasa.pl
Index: ext/spl/spl_array.c
===================================================================
--- ext/spl/spl_array.c (revision 307577)
+++ ext/spl/spl_array.c (working copy)
@@ -117,12 +117,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);
Index: Zend/zend_hash.c
===================================================================
--- Zend/zend_hash.c (revision 307577)
+++ Zend/zend_hash.c (working copy)
@@ -22,27 +22,6 @@
#include "zend.h"
#include "zend_globals.h"
-#define CONNECT_TO_BUCKET_DLLIST(element, list_head) \
- (element)->pNext = (list_head); \
- (element)->pLast = NULL; \
- if ((element)->pNext) { \
- (element)->pNext->pLast = (element); \
- }
-
-#define CONNECT_TO_GLOBAL_DLLIST(element, ht) \
- (element)->pListLast = (ht)->pListTail; \
- (ht)->pListTail = (element); \
- (element)->pListNext = NULL; \
- if ((element)->pListLast != NULL) { \
- (element)->pListLast->pListNext = (element); \
- } \
- if (!(ht)->pListHead) { \
- (ht)->pListHead = (element); \
- } \
- if ((ht)->pInternalPointer == NULL) { \
- (ht)->pInternalPointer = (element); \
- }
-
#if ZEND_DEBUG
#define HT_OK 0
#define HT_IS_DESTROYING 1
@@ -91,19 +70,11 @@
}
-#define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
- if ((ht)->nNumOfElements > (ht)->nTableSize) { \
- zend_hash_do_resize(ht); \
- }
-
-static int zend_hash_do_resize(HashTable *ht);
-
ZEND_API ulong zend_hash_func(const char *arKey, uint nKeyLength)
{
return zend_inline_hash_func(arKey, nKeyLength);
}
-
#define UPDATE_DATA(ht, p, pData, nDataSize) \
if (nDataSize == sizeof(void*)) { \
if ((p)->pData != &(p)->pDataPtr) { \
@@ -135,13 +106,6 @@
memcpy((p)->pData, pData, nDataSize); \
(p)->pDataPtr=NULL; \
}
-
-#define CHECK_INIT(ht) do { \
- if (UNEXPECTED((ht)->nTableMask == 0)) { \
- (ht)->nTableMask = (ht)->nTableSize - 1; \
- (ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent); \
- } \
-} while (0)
static const Bucket *uninitialized_bucket = NULL;
@@ -158,12 +122,16 @@
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 = 0; /* 0 means that ht->arBuckets is uninitialized */
ht->pDestructor = pDestructor;
ht->arBuckets = (Bucket**)&uninitialized_bucket;
+ ht->arEmpty = NULL;
ht->pListHead = NULL;
ht->pListTail = NULL;
ht->nNumOfElements = 0;
@@ -210,36 +178,33 @@
CHECK_INIT(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->arKey == arKey ||
- ((p->h == h) && (p->nKeyLength == nKeyLength) && !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;
}
-
+
if (IS_INTERNED(arKey)) {
p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
if (!p) {
@@ -264,7 +229,7 @@
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++;
@@ -284,34 +249,31 @@
}
CHECK_INIT(ht);
- nIndex = h & ht->nTableMask;
-
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if (p->arKey == arKey ||
- ((p->h == h) && (p->nKeyLength == nKeyLength) && !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;
}
if (IS_INTERNED(arKey)) {
@@ -340,7 +302,7 @@
}
HANDLE_BLOCK_INTERRUPTIONS();
- ht->arBuckets[nIndex] = p;
+ ZEND_HASH_FILL_BUCKET(ht, nIndex, p);
CONNECT_TO_GLOBAL_DLLIST(p, ht);
HANDLE_UNBLOCK_INTERRUPTIONS();
@@ -369,11 +331,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;
}
@@ -398,7 +359,6 @@
}
return SUCCESS;
}
- p = p->pNext;
}
p = (Bucket *) pemalloc_rel(sizeof(Bucket), ht->persistent);
if (!p) {
@@ -415,7 +375,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();
@@ -427,91 +387,97 @@
return SUCCESS;
}
-
-static int zend_hash_do_resize(HashTable *ht)
+ZEND_API 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);
+ CHECK_INIT(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)
+int zend_hash_rehash(HashTable *ht)
{
Bucket *p;
uint nIndex;
IS_CONSISTENT(ht);
- if (UNEXPECTED(ht->nNumOfElements == 0)) {
- return SUCCESS;
+ if ((ht)->nTableMask == 0) {
+ return;
}
- 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;
Bucket *p;
IS_CONSISTENT(ht);
+ if ((ht)->nTableMask == 0) {
+ return FAILURE;
+ }
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;
- }
- if (p->pListLast != NULL) {
- p->pListLast->pListNext = p->pListNext;
- } else {
- /* Deleting the head of the list */
- ht->pListHead = p->pListNext;
- }
- if (p->pListNext != NULL) {
- p->pListNext->pListLast = p->pListLast;
- } else {
- ht->pListTail = p->pListLast;
- }
- if (ht->pInternalPointer == p) {
- ht->pInternalPointer = p->pListNext;
- }
+
+ REMOVE_FROM_HASH(p, nIndex, ht);
+
if (ht->pDestructor) {
ht->pDestructor(p->pData);
}
@@ -520,10 +486,8 @@
}
pefree(p, ht->persistent);
HANDLE_UNBLOCK_INTERRUPTIONS();
- ht->nNumOfElements--;
return SUCCESS;
}
- p = p->pNext;
}
return FAILURE;
}
@@ -578,7 +542,7 @@
pefree(q, ht->persistent);
}
if (ht->nTableMask) {
- memset(ht->arBuckets, 0, ht->nTableSize*sizeof(Bucket *));
+ memset(ht->arEmpty, 0, ht->nTableSize*1);
}
ht->pListHead = NULL;
ht->pListTail = NULL;
@@ -591,43 +555,28 @@
/* 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;
+ 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
}
- if (p->pNext) {
- p->pNext->pLast = p->pLast;
- } else {
- /* Nothing to do as this list doesn't have a tail */
- }
- if (p->pListLast != NULL) {
- p->pListLast->pListNext = p->pListNext;
- } else {
- /* Deleting the head of the list */
- ht->pListHead = p->pListNext;
- }
- if (p->pListNext != NULL) {
- p->pListNext->pListLast = p->pListLast;
- } else {
- ht->pListTail = p->pListLast;
- }
- if (ht->pInternalPointer == p) {
- ht->pInternalPointer = p->pListNext;
- }
- ht->nNumOfElements--;
+ HANDLE_BLOCK_INTERRUPTIONS();
+
+ REMOVE_FROM_HASH(p, nIndex, ht);
+
HANDLE_UNBLOCK_INTERRUPTIONS();
if (ht->pDestructor) {
@@ -899,19 +848,19 @@
uint nIndex;
Bucket *p;
+ if (ht->nTableMask == 0) {
+ return FAILURE;
+ }
+
IS_CONSISTENT(ht);
h = zend_inline_hash_func(arKey, nKeyLength);
- nIndex = h & ht->nTableMask;
-
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if (p->arKey == arKey ||
- ((p->h == h) && (p->nKeyLength == nKeyLength) && !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;
}
@@ -924,20 +873,19 @@
if (nKeyLength==0) {
return zend_hash_index_find(ht, h, pData);
+ } else if (ht->nTableMask == 0) {
+ return FAILURE;
}
IS_CONSISTENT(ht);
- nIndex = h & ht->nTableMask;
+ nIndex = ZEND_HASH_BUCKET(ht, h);
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if (p->arKey == arKey ||
- ((p->h == h) && (p->nKeyLength == nKeyLength) && !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;
}
@@ -949,18 +897,19 @@
uint nIndex;
Bucket *p;
+ if (ht->nTableMask == 0) {
+ return 0;
+ }
+
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->arKey == arKey ||
- ((p->h == h) && (p->nKeyLength == nKeyLength) && !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;
}
@@ -973,19 +922,18 @@
if (nKeyLength==0) {
return zend_hash_index_exists(ht, h);
+ } else if (ht->nTableMask == 0) {
+ return 0;
}
IS_CONSISTENT(ht);
- nIndex = h & ht->nTableMask;
+ nIndex = ZEND_HASH_BUCKET(ht, h);
- p = ht->arBuckets[nIndex];
- while (p != NULL) {
- if (p->arKey == arKey ||
- ((p->h == h) && (p->nKeyLength == nKeyLength) && !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;
@@ -997,17 +945,19 @@
uint nIndex;
Bucket *p;
+ if (ht->nTableMask == 0) {
+ return FAILURE;
+ }
+
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;
}
@@ -1018,16 +968,18 @@
uint nIndex;
Bucket *p;
+ if (ht->nTableMask == 0) {
+ return 0;
+ }
+
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;
}
@@ -1059,15 +1011,18 @@
ht->pInternalPointer = NULL;
} else if (ht->pInternalPointer != ptr->pos) {
Bucket *p;
+
+ if (ht->nTableMask == 0) {
+ return 0;
+ }
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;
}
@@ -1196,26 +1151,32 @@
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;
+ if (ht->nTableMask == 0) {
+ return FAILURE;
+ }
+
IS_CONSISTENT(ht);
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;
@@ -1240,28 +1201,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 {
@@ -1285,7 +1244,6 @@
}
}
}
- q = q->pNext;
}
}
@@ -1296,14 +1254,13 @@
HANDLE_BLOCK_INTERRUPTIONS();
- if (p->pNext) {
- p->pNext->pLast = p->pLast;
+ 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->pLast) {
- p->pLast->pNext = p->pNext;
- } else{
- ht->arBuckets[p->h & ht->nTableMask] = p->pNext;
- }
if (p->nKeyLength != str_length) {
Bucket *q = (Bucket *) pemalloc(sizeof(Bucket) + str_length, ht->persistent);
@@ -1345,8 +1302,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;
@@ -1539,7 +1498,6 @@
}
-
#if ZEND_DEBUG
void zend_hash_display_pListTail(const HashTable *ht)
{
@@ -1563,9 +1521,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 (revision 307577)
+++ Zend/zend_hash.h (working copy)
@@ -48,6 +48,7 @@
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;
@@ -58,8 +59,6 @@
void *pDataPtr;
struct bucket *pListNext;
struct bucket *pListLast;
- struct bucket *pNext;
- struct bucket *pLast;
char *arKey;
} Bucket;
@@ -72,6 +71,7 @@
Bucket *pListHead;
Bucket *pListTail;
Bucket **arBuckets;
+ uchar *arEmpty;
dtor_func_t pDestructor;
zend_bool persistent;
unsigned char nApplyCount;
@@ -124,7 +124,95 @@
ZEND_API int zend_hash_add_empty_element(HashTable *ht, const char *arKey, uint nKeyLength);
+ZEND_API int zend_hash_do_resize(HashTable *ht);
+#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 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)
+#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;
+#define ZEND_HASH_IF_FULL_DO_RESIZE(ht) \
+ 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); \
+ }
+#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; \
+ (ht)->pListTail = (element); \
+ (element)->pListNext = NULL; \
+ if ((element)->pListLast != NULL) { \
+ (element)->pListLast->pListNext = (element); \
+ } \
+ if (!(ht)->pListHead) { \
+ (ht)->pListHead = (element); \
+ } \
+ if ((ht)->pInternalPointer == NULL) { \
+ (ht)->pInternalPointer = (element); \
+ }
+#define REMOVE_FROM_GLOBAL_DLLIST(element, ht) \
+ if ((element)->pListLast != NULL) { \
+ (element)->pListLast->pListNext = (element)->pListNext; \
+ } else { \
+ (ht)->pListHead = (element)->pListNext; \
+ } \
+ if ((element)->pListNext != NULL) { \
+ (element)->pListNext->pListLast = (element)->pListLast; \
+ } else { \
+ (ht)->pListTail = (element)->pListLast; \
+ }
+#define REMOVE_FROM_HASH(element, nIndex, ht) \
+ zend_hash_free_bucket((ht), (nIndex)); \
+ REMOVE_FROM_GLOBAL_DLLIST((element), (ht)) \
+ if ((ht)->pInternalPointer == (element)) { \
+ (ht)->pInternalPointer = (element)->pListNext; \
+ } \
+ (ht)->nNumOfElements--;
+#define ALLOC_BUCKETS(ht) do { \
+ (ht)->nTableMask = (ht)->nTableSize - 1; \
+ void* 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); \
+} while (0)
+#define CHECK_INIT(ht) do { \
+ if (UNEXPECTED((ht)->nTableMask == 0)) { \
+ ALLOC_BUCKETS((ht)); \
+ } \
+} while (0)
+
#define ZEND_HASH_APPLY_KEEP 0
#define ZEND_HASH_APPLY_REMOVE 1<<0
#define ZEND_HASH_APPLY_STOP 1<<1
@@ -225,69 +313,33 @@
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<<8) | *arKey++; /* fallthrough... */
+ case 6: hash = (hash<<8) | *arKey++; /* fallthrough... */
+ case 5: hash = (hash<<8) | *arKey++; /* fallthrough... */
+ case 4: hash = (hash<<8) | *arKey++; /* fallthrough... */
+ case 3: hash = (hash<<8) | *arKey++; /* fallthrough... */
+ case 2: hash = (hash<<8) | *arKey++; /* fallthrough... */
+ case 1: hash = (hash<<8) | *arKey++; break;
+ case 0: break;
+ EMPTY_SWITCH_DEFAULT_CASE()
+ }
+ } else {
+ const ulong* arEnd = (ulong*)(arKey + nKeyLength - sizeof(ulong));
+ hash = *arEnd;
+ for (; ar < arEnd; ar++) {
+ hash = ((hash << 5) + hash) + *ar;
+ }
}
- switch (nKeyLength) {
- case 7: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
- case 6: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
- case 5: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
- case 4: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
- case 3: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
- case 2: hash = ((hash << 5) + hash) + *arKey++; /* fallthrough... */
- case 1: hash = ((hash << 5) + hash) + *arKey++; break;
- case 0: break;
-EMPTY_SWITCH_DEFAULT_CASE()
- }
- return hash;
+ return (hash<<16)|(hash%65165);
}
-
ZEND_API ulong zend_hash_func(const char *arKey, uint nKeyLength);
#if ZEND_DEBUG
Index: Zend/zend_string.c
===================================================================
--- Zend/zend_string.c (revision 307577)
+++ Zend/zend_string.c (working copy)
@@ -37,7 +37,7 @@
static void zend_interned_strings_snapshot_int(TSRMLS_D);
static void zend_interned_strings_restore_int(TSRMLS_D);
-void zend_interned_strings_init(TSRMLS_D)
+int zend_interned_strings_init(TSRMLS_D)
{
#ifndef ZTS
size_t size = 1024 * 1024;
@@ -53,10 +53,9 @@
CG(interned_strings_end) = CG(interned_strings_start) + size;
zend_hash_init(&CG(interned_strings), 0, NULL, NULL, 1);
-
- CG(interned_strings).nTableMask = CG(interned_strings).nTableSize - 1;
- CG(interned_strings).arBuckets = (Bucket **) pecalloc(CG(interned_strings).nTableSize, sizeof(Bucket *), CG(interned_strings).persistent);
+ ALLOC_BUCKETS(&CG(interned_strings));
+
#if ZEND_DEBUG_INTERNED_STRINGS
mprotect(CG(interned_strings_start), CG(interned_strings_end) - CG(interned_strings_start), PROT_READ);
#endif
@@ -66,6 +65,8 @@
zend_new_interned_string = zend_new_interned_string_int;
zend_interned_strings_snapshot = zend_interned_strings_snapshot_int;
zend_interned_strings_restore = zend_interned_strings_restore_int;
+
+ return SUCCESS;
}
void zend_interned_strings_dtor(TSRMLS_D)
@@ -91,18 +92,14 @@
}
h = zend_inline_hash_func(arKey, nKeyLength);
- nIndex = h & CG(interned_strings).nTableMask;
- p = CG(interned_strings).arBuckets[nIndex];
- while (p != NULL) {
- if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
- if (!memcmp(p->arKey, arKey, nKeyLength)) {
- if (free_src) {
- efree((void *)arKey);
- }
- return p->arKey;
+ nIndex = ZEND_HASH_BUCKET(&CG(interned_strings), h);
+ ZEND_HASH_ITERATE_UNTIL_FREE(&CG(interned_strings), nIndex, p) {
+ if (EQ_HASH_KEYS(p, arKey, h, nKeyLength)) {
+ if (free_src) {
+ efree((void *)arKey);
}
+ return p->arKey;
}
- p = p->pNext;
}
if (CG(interned_strings_top) + ZEND_MM_ALIGNED_SIZE(sizeof(Bucket) + nKeyLength) >=
@@ -127,46 +124,18 @@
p->h = h;
p->pData = &p->pDataPtr;
p->pDataPtr = p;
-
- p->pNext = CG(interned_strings).arBuckets[nIndex];
- p->pLast = NULL;
- if (p->pNext) {
- p->pNext->pLast = p;
- }
+ CONNECT_TO_BUCKET_DLLIST(p, &CG(interned_strings)->arBuckets[nIndex]);
HANDLE_BLOCK_INTERRUPTIONS();
-
- p->pListLast = CG(interned_strings).pListTail;
- CG(interned_strings).pListTail = p;
- p->pListNext = NULL;
- if (p->pListLast != NULL) {
- p->pListLast->pListNext = p;
- }
- if (!CG(interned_strings).pListHead) {
- CG(interned_strings).pListHead = p;
- }
- CG(interned_strings).arBuckets[nIndex] = p;
+ CONNECT_TO_GLOBAL_DLLIST(p, &CG(interned_strings));
+ ZEND_HASH_FILL_BUCKET(&CG(interned_strings), nIndex, p);
HANDLE_UNBLOCK_INTERRUPTIONS();
CG(interned_strings).nNumOfElements++;
+ ZEND_HASH_IF_FULL_DO_RESIZE(&CG(interned_strings));
- if (CG(interned_strings).nNumOfElements > CG(interned_strings).nTableSize) {
- if ((CG(interned_strings).nTableSize << 1) > 0) { /* Let's double the table size */
- Bucket **t = (Bucket **) perealloc_recoverable(CG(interned_strings).arBuckets, (CG(interned_strings).nTableSize << 1) * sizeof(Bucket *), CG(interned_strings).persistent);
-
- if (t) {
- HANDLE_BLOCK_INTERRUPTIONS();
- CG(interned_strings).arBuckets = t;
- CG(interned_strings).nTableSize = (CG(interned_strings).nTableSize << 1);
- CG(interned_strings).nTableMask = CG(interned_strings).nTableSize - 1;
- zend_hash_rehash(&CG(interned_strings));
- HANDLE_UNBLOCK_INTERRUPTIONS();
- }
- }
- }
-
#if ZEND_DEBUG_INTERNED_STRINGS
mprotect(CG(interned_strings_start), CG(interned_strings_end) - CG(interned_strings_start), PROT_READ);
#endif
@@ -197,25 +166,13 @@
#endif
for (i = 0; i < CG(interned_strings).nTableSize; i++) {
- p = CG(interned_strings).arBuckets[i];
- while (p && p->arKey > CG(interned_strings_top)) {
- CG(interned_strings).nNumOfElements--;
- if (p->pListLast != NULL) {
- p->pListLast->pListNext = p->pListNext;
- } else {
- CG(interned_strings).pListHead = p->pListNext;
+ for(;;) {
+ p = CG(interned_strings).arBuckets[i];
+ if (!ZEND_HASH_BUCKET_IS_OCCUPIED(&CG(interned_strings), i) || p->arKey <= CG(interned_strings_top)) {
+ break;
}
- if (p->pListNext != NULL) {
- p->pListNext->pListLast = p->pListLast;
- } else {
- CG(interned_strings).pListTail = p->pListLast;
- }
- p = p->pNext;
+ REMOVE_FROM_HASH(p, i, &CG(interned_strings));
}
- if (p) {
- p->pLast = NULL;
- }
- CG(interned_strings).arBuckets[i] = p;
}
#if ZEND_DEBUG_INTERNED_STRINGS
Index: Zend/zend_string.h
===================================================================
--- Zend/zend_string.h (revision 307577)
+++ Zend/zend_string.h (working copy)
@@ -27,7 +27,7 @@
ZEND_API extern void (*zend_interned_strings_snapshot)(TSRMLS_D);
ZEND_API extern void (*zend_interned_strings_restore)(TSRMLS_D);
-void zend_interned_strings_init(TSRMLS_D);
+int zend_interned_strings_init(TSRMLS_D);
void zend_interned_strings_dtor(TSRMLS_D);
#ifndef ZTS
|
Copyright © 2001-2024 The PHP Group