PHP ハッシュ テーブルの原理

struct _zend_array { zend_refcounted_h gc; union { struct { ZEND_ENDIAN_LOHI_4( zend_uchar flags, zend_uchar nApplyCount, zend_uchar nIteratorsCount, zend_uchar reserve) } v; uint32_t flags; } u; uint32_t nTableMask; Bucket *arData; uint32_t nNumUsed; uint32_t nNumOfElements; uint32_t nTableSize; uint32_t nInternalPointer; zend_long nNextFreeElement; dtor_func_t pDestructor; };

typedef struct _Bucket { zval val; zend_ulong h; /* hash value (or numeric index) */ zend_string *key; /* string key or NULL for numerics */ } Bucket;

$a = [9 => "foo", 2 => 42, []]; var_dump($a); array(3) { [9]=> string(3) "foo" [2]=> int(42) [10]=> array(0) { } }

size_t i; Bucket p; zval val; for (i=0; i < ht->nTableSize; i++) { p = ht->arData[i]; val = p.val; /* do something with val */ }

idx = ht->nNumUsed++; /* take the next avalaible slot number */ ht->nNumOfElements++; /* increment number of elements */ /* ... */ p = ht->arData + idx; /* Get the bucket in that slot from arData */ p->key = key; /* Affect it the key we want to insert at */ /* ... */ p->h = h = ZSTR_H(key); /* save the hash of the current key into the bucket */ ZVAL_COPY_VALUE(&p->val, pData); /* Copy the value into the bucket's value : add operation */

size_t i; Bucket p; zval val; for (i=0; i < ht->nTableSize; i++) { p = ht->arData[i]; val = p.val; if (Z_TYPE(val) == IS_UNDEF) { /* empty hole ? */ continue; /* skip it */ } /* do something with val */ }

#define HT_HASH_SIZE(nTableMask) (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t)) #define HT_DATA_SIZE(nTableSize) ((size_t)(nTableSize) * sizeof(Bucket)) #define HT_SIZE_EX(nTableSize, nTableMask) (HT_DATA_SIZE((nTableSize)) + HT_HASH_SIZE((nTableMask))) #define HT_SIZE(ht) HT_SIZE_EX((ht)->nTableSize, (ht)->nTableMask) Bucket *arData; arData = emalloc(HT_SIZE(ht)); /* now alloc this */

(((size_t)(((ht)->nTableSize)) * sizeof(Bucket)) + (((size_t)(uint32_t)-(int32_t)(((ht)->nTableMask))) * sizeof(uint32_t)))

idx = ht->nNumUsed++; ht->nNumOfElements++; if (ht->nInternalPointer == HT_INVALID_IDX) { ht->nInternalPointer = idx; } zend_hash_iterators_update(ht, HT_INVALID_IDX, idx); p = ht->arData + idx; p->key = key; if (!ZSTR_IS_INTERNED(key)) { zend_string_addref(key); ht->u.flags &= ~HASH_FLAG_STATIC_KEYS; zend_string_hash_val(key); } p->h = h = ZSTR_H(key); ZVAL_COPY_VALUE(&p->val, pData); nIndex = h | ht->nTableMask; Z_NEXT(p->val) = HT_HASH(ht, nIndex); HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(idx);

#define HT_HASH_TO_BUCKET_EX(data, idx) ((data) + (idx)) #define HT_HASH_TO_BUCKET(ht, idx) HT_HASH_TO_BUCKET_EX((ht)->arData, idx) h = zend_string_hash_val(key); /* get the hash from the key (assuming string key here) */ nIndex = h | ht->nTableMask; /* get the translation table index */ idx = HT_HASH(ht, nIndex); /* Get the slot corresponding to that translation index */ while (idx != HT_INVALID_IDX) { /* If there is a corresponding slot */ p = HT_HASH_TO_BUCKET(ht, idx); /* Get the bucket from that slot */ if ((p->key == key) || /* Is it the right bucket ? same key pointer ? */ (p->h == h && /* ... or same hash */ p->key && /* and a key (string key based) */ ZSTR_LEN(p->key) == ZSTR_LEN(key) && /* and same key length */ memcmp(ZSTR_VAL(p->key), ZSTR_VAL(key), ZSTR_LEN(key)) == 0)) { /* and same key content ? */ _zend_hash_del_el_ex(ht, idx, p, prev); /* that's us ! delete us */ return SUCCESS; } prev = p; idx = Z_NEXT(p->val); /* get the next corresponding slot from current one */ } return FAILURE;

#define HT_MIN_MASK ((uint32_t) -2) #define HT_HASH_SIZE(nTableMask) (((size_t)(uint32_t)-(int32_t)(nTableMask)) * sizeof(uint32_t)) #define HT_SET_DATA_ADDR(ht, ptr) do { (ht)->arData = (Bucket*)(((char*)(ptr)) + HT_HASH_SIZE((ht)->nTableMask)); } while (0) static const uint32_t uninitialized_bucket[-HT_MIN_MASK] = {HT_INVALID_IDX, HT_INVALID_IDX}; /* hash lazy init */ ZEND_API void ZEND_FASTCALL _zend_hash_init(HashTable *ht, uint32_t nSize, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC) { /* ... */ ht->nTableSize = zend_hash_check_size(nSize); ht->nTableMask = HT_MIN_MASK; HT_SET_DATA_ADDR(ht, &uninitialized_bucket); ht->nNumUsed = 0; ht->nNumOfElements = 0; }

#define HT_HASH_EX(data, idx) ((uint32_t*)(data))[(int32_t)(idx)] #define HT_HASH(ht, idx) HT_HASH_EX((ht)->arData, idx) (ht)->nTableMask = -(ht)->nTableSize; HT_SET_DATA_ADDR(ht, pemalloc(HT_SIZE(ht), (ht)->u.flags & HASH_FLAG_PERSISTENT)); memset(&HT_HASH(ht, (ht)->nTableMask), HT_INVALID_IDX, HT_HASH_SIZE((ht)->nTableMask))

Bucket *p; uint32_t nIndex, i; HT_HASH_RESET(ht); i = 0; p = ht->arData; do { if (UNEXPECTED(Z_TYPE(p->val) == IS_UNDEF)) { uint32_t j = i; Bucket *q = p; while (++i < ht->nNumUsed) { p++; if (EXPECTED(Z_TYPE_INFO(p->val) != IS_UNDEF)) { ZVAL_COPY_VALUE(&q->val, &p->val); q->h = p->h; nIndex = q->h | ht->nTableMask; q->key = p->key; Z_NEXT(q->val) = HT_HASH(ht, nIndex); HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(j); if (UNEXPECTED(ht->nInternalPointer == i)) { ht->nInternalPointer = j; } q++; j++; } } ht->nNumUsed = j; break; } nIndex = p->h | ht->nTableMask; Z_NEXT(p->val) = HT_HASH(ht, nIndex); HT_HASH(ht, nIndex) = HT_IDX_TO_HASH(i); p++; } while (++i < ht->nNumUsed);