Lines Matching refs:hash
22 /* This hashtable is implemented as a double hash. All elements are
24 * resolution (no linked list, etc.). When there is a hash collision
26 * using a secondary hash. The secondary hash is an increment
27 * computed as a hash function (a different one) of the primary
28 * hashcode. This increment is added to the initial hash value to
29 * obtain further slots assigned to the same hash code. For this to
122 #define HASH_DELETE_KEY_VALUE(hash, keypointer, valuepointer) UPRV_BLOCK_MACRO_BEGIN { \
123 if (hash->keyDeleter != nullptr && keypointer != nullptr) { \
124 (*hash->keyDeleter)(keypointer); \
126 if (hash->valueDeleter != nullptr && valuepointer != nullptr) { \
127 (*hash->valueDeleter)(valuepointer); \
146 _uhash_setElement(UHashtable *hash, UHashElement* e,
151 if (hash->keyDeleter != nullptr && e->key.pointer != nullptr &&
153 (*hash->keyDeleter)(e->key.pointer);
155 if (hash->valueDeleter != nullptr) {
158 (*hash->valueDeleter)(oldValue.pointer);
186 _uhash_internalRemoveElement(UHashtable *hash, UHashElement* e) {
189 --hash->count;
191 return _uhash_setElement(hash, e, HASH_DELETED, empty, empty, 0);
195 _uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
196 U_ASSERT(hash != nullptr);
199 hash->lowWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2];
200 hash->highWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2 + 1];
213 _uhash_allocate(UHashtable *hash,
224 hash->primeIndex = static_cast<int8_t>(primeIndex);
225 hash->length = PRIMES[primeIndex];
227 p = hash->elements = (UHashElement*)
228 uprv_malloc(sizeof(UHashElement) * hash->length);
230 if (hash->elements == nullptr) {
238 limit = p + hash->length;
246 hash->count = 0;
247 hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);
248 hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);
315 * a. identical: First check the hash values for a quick check,
333 * hash) is relatively prime to the table length.
336 _uhash_find(const UHashtable *hash, UHashTok key,
343 UHashElement *elements = hash->elements;
346 startIndex = theIndex = (hashcode ^ 0x4000000) % hash->length;
351 if ((*hash->keyComparator)(key, elements[theIndex].key)) {
356 * but for which the hash code does not match. Keep
369 jump = (hashcode % (hash->length - 1)) + 1;
371 theIndex = (theIndex + jump) % hash->length;
397 _uhash_rehash(UHashtable *hash, UErrorCode *status) {
399 UHashElement *old = hash->elements;
400 int32_t oldLength = hash->length;
401 int32_t newPrimeIndex = hash->primeIndex;
404 if (hash->count > hash->highWaterMark) {
408 } else if (hash->count < hash->lowWaterMark) {
416 _uhash_allocate(hash, newPrimeIndex, status);
419 hash->elements = old;
420 hash->length = oldLength;
426 UHashElement *e = _uhash_find(hash, old[i].key, old[i].hashcode);
432 ++hash->count;
440 _uhash_remove(UHashtable *hash,
450 UHashElement* e = _uhash_find(hash, key, hash->keyHasher(key));
455 result = _uhash_internalRemoveElement(hash, e);
456 if (hash->count < hash->lowWaterMark) {
458 _uhash_rehash(hash, &status);
465 _uhash_put(UHashtable *hash,
473 * non-nullptr keyDeleter. Then the key, the hash and the value are
483 U_ASSERT(hash != nullptr);
490 return _uhash_remove(hash, key);
492 if (hash->count > hash->highWaterMark) {
493 _uhash_rehash(hash, status);
499 hashcode = (*hash->keyHasher)(key);
500 e = _uhash_find(hash, key, hashcode);
511 ++hash->count;
512 if (hash->count == hash->length) {
514 --hash->count;
524 return _uhash_setElement(hash, e, hashcode & 0x7FFFFFFF, key, value, hint);
531 HASH_DELETE_KEY_VALUE(hash, key.pointer, value.pointer);
593 uhash_close(UHashtable *hash) {
594 if (hash == nullptr) {
597 if (hash->elements != nullptr) {
598 if (hash->keyDeleter != nullptr || hash->valueDeleter != nullptr) {
601 while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != nullptr) {
602 HASH_DELETE_KEY_VALUE(hash, e->key.pointer, e->value.pointer);
605 uprv_free(hash->elements);
606 hash->elements = nullptr;
608 if (hash->allocated) {
609 uprv_free(hash);
614 uhash_setKeyHasher(UHashtable *hash, UHashFunction *fn) {
615 UHashFunction *result = hash->keyHasher;
616 hash->keyHasher = fn;
621 uhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn) {
622 UKeyComparator *result = hash->keyComparator;
623 hash->keyComparator = fn;
627 uhash_setValueComparator(UHashtable *hash, UValueComparator *fn){
628 UValueComparator *result = hash->valueComparator;
629 hash->valueComparator = fn;
634 uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn) {
635 UObjectDeleter *result = hash->keyDeleter;
636 hash->keyDeleter = fn;
641 uhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn) {
642 UObjectDeleter *result = hash->valueDeleter;
643 hash->valueDeleter = fn;
648 uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
650 _uhash_internalSetResizePolicy(hash, policy);
651 hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);
652 hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);
653 _uhash_rehash(hash, &status);
657 uhash_count(const UHashtable *hash) {
658 return hash->count;
662 uhash_get(const UHashtable *hash,
666 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer;
670 uhash_iget(const UHashtable *hash,
674 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer;
678 uhash_geti(const UHashtable *hash,
682 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer;
686 uhash_igeti(const UHashtable *hash,
690 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer;
694 uhash_getiAndFound(const UHashtable *hash,
699 const UHashElement *e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder));
705 uhash_igetiAndFound(const UHashtable *hash,
710 const UHashElement *e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder));
716 uhash_put(UHashtable *hash,
723 return _uhash_put(hash, keyholder, valueholder,
729 uhash_iput(UHashtable *hash,
736 return _uhash_put(hash, keyholder, valueholder,
742 uhash_puti(UHashtable *hash,
749 return _uhash_put(hash, keyholder, valueholder,
756 uhash_iputi(UHashtable *hash,
763 return _uhash_put(hash, keyholder, valueholder,
769 uhash_putiAllowZero(UHashtable *hash,
776 return _uhash_put(hash, keyholder, valueholder,
783 uhash_iputiAllowZero(UHashtable *hash,
790 return _uhash_put(hash, keyholder, valueholder,
796 uhash_remove(UHashtable *hash,
800 return _uhash_remove(hash, keyholder).pointer;
804 uhash_iremove(UHashtable *hash,
808 return _uhash_remove(hash, keyholder).pointer;
812 uhash_removei(UHashtable *hash,
816 return _uhash_remove(hash, keyholder).integer;
820 uhash_iremovei(UHashtable *hash,
824 return _uhash_remove(hash, keyholder).integer;
828 uhash_removeAll(UHashtable *hash) {
831 U_ASSERT(hash != nullptr);
832 if (hash->count != 0) {
833 while ((e = uhash_nextElement(hash, &pos)) != nullptr) {
834 uhash_removeElement(hash, e);
837 U_ASSERT(hash->count == 0);
841 uhash_containsKey(const UHashtable *hash, const void *key) {
844 const UHashElement *e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder));
851 * @param hash The target UHashtable.
856 uhash_icontainsKey(const UHashtable *hash, int32_t key) {
859 const UHashElement *e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder));
864 uhash_find(const UHashtable *hash, const void* key) {
868 e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder));
873 uhash_nextElement(const UHashtable *hash, int32_t *pos) {
878 U_ASSERT(hash != nullptr);
879 for (i = *pos + 1; i < hash->length; ++i) {
880 if (!IS_EMPTY_OR_DELETED(hash->elements[i].hashcode)) {
882 return &(hash->elements[i]);
891 uhash_removeElement(UHashtable *hash, const UHashElement* e) {
892 U_ASSERT(hash != nullptr);
896 return _uhash_internalRemoveElement(hash, nce).pointer;
959 * of the hash values will yield random results on machines
969 Normally we would return an error here about incompatible hash tables,