Lines Matching refs:hash
20 /* This hashtable is implemented as a double hash. All elements are
22 * resolution (no linked list, etc.). When there is a hash collision
24 * using a secondary hash. The secondary hash is an increment
25 * computed as a hash function (a different one) of the primary
26 * hashcode. This increment is added to the initial hash value to
27 * obtain further slots assigned to the same hash code. For this to
120 #define HASH_DELETE_KEY_VALUE(hash, keypointer, valuepointer) \
121 if (hash->keyDeleter != NULL && keypointer != NULL) { \
122 (*hash->keyDeleter)(keypointer); \
124 if (hash->valueDeleter != NULL && valuepointer != NULL) { \
125 (*hash->valueDeleter)(valuepointer); \
141 _uhash_setElement(UHashtable *hash, UHashElement* e,
146 if (hash->keyDeleter != NULL && e->key.pointer != NULL &&
148 (*hash->keyDeleter)(e->key.pointer);
150 if (hash->valueDeleter != NULL) {
153 (*hash->valueDeleter)(oldValue.pointer);
181 _uhash_internalRemoveElement(UHashtable *hash, UHashElement* e) {
184 --hash->count;
186 return _uhash_setElement(hash, e, HASH_DELETED, empty, empty, 0);
190 _uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
191 U_ASSERT(hash != NULL);
194 hash->lowWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2];
195 hash->highWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2 + 1];
208 _uhash_allocate(UHashtable *hash,
219 hash->primeIndex = primeIndex;
220 hash->length = PRIMES[primeIndex];
222 p = hash->elements = (UHashElement*)
223 uprv_malloc(sizeof(UHashElement) * hash->length);
225 if (hash->elements == NULL) {
233 limit = p + hash->length;
241 hash->count = 0;
242 hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);
243 hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);
310 * a. identical: First check the hash values for a quick check,
328 * hash) is relatively prime to the table length.
331 _uhash_find(const UHashtable *hash, UHashTok key,
338 UHashElement *elements = hash->elements;
341 startIndex = theIndex = (hashcode ^ 0x4000000) % hash->length;
346 if ((*hash->keyComparator)(key, elements[theIndex].key)) {
351 * but for which the hash code does not match. Keep
364 jump = (hashcode % (hash->length - 1)) + 1;
366 theIndex = (theIndex + jump) % hash->length;
393 _uhash_rehash(UHashtable *hash, UErrorCode *status) {
395 UHashElement *old = hash->elements;
396 int32_t oldLength = hash->length;
397 int32_t newPrimeIndex = hash->primeIndex;
400 if (hash->count > hash->highWaterMark) {
404 } else if (hash->count < hash->lowWaterMark) {
412 _uhash_allocate(hash, newPrimeIndex, status);
415 hash->elements = old;
416 hash->length = oldLength;
422 UHashElement *e = _uhash_find(hash, old[i].key, old[i].hashcode);
428 ++hash->count;
436 _uhash_remove(UHashtable *hash,
446 UHashElement* e = _uhash_find(hash, key, hash->keyHasher(key));
451 result = _uhash_internalRemoveElement(hash, e);
452 if (hash->count < hash->lowWaterMark) {
454 _uhash_rehash(hash, &status);
461 _uhash_put(UHashtable *hash,
469 * non-NULL keyDeleter. Then the key, the hash and the value are
479 U_ASSERT(hash != NULL);
485 return _uhash_remove(hash, key);
487 if (hash->count > hash->highWaterMark) {
488 _uhash_rehash(hash, status);
494 hashcode = (*hash->keyHasher)(key);
495 e = _uhash_find(hash, key, hashcode);
506 ++hash->count;
507 if (hash->count == hash->length) {
509 --hash->count;
519 return _uhash_setElement(hash, e, hashcode & 0x7FFFFFFF, key, value, hint);
526 HASH_DELETE_KEY_VALUE(hash, key.pointer, value.pointer);
572 uhash_close(UHashtable *hash) {
573 if (hash == NULL) {
576 if (hash->elements != NULL) {
577 if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) {
580 while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) {
581 HASH_DELETE_KEY_VALUE(hash, e->key.pointer, e->value.pointer);
584 uprv_free(hash->elements);
585 hash->elements = NULL;
587 if (hash->allocated) {
588 uprv_free(hash);
593 uhash_setKeyHasher(UHashtable *hash, UHashFunction *fn) {
594 UHashFunction *result = hash->keyHasher;
595 hash->keyHasher = fn;
600 uhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn) {
601 UKeyComparator *result = hash->keyComparator;
602 hash->keyComparator = fn;
606 uhash_setValueComparator(UHashtable *hash, UValueComparator *fn){
607 UValueComparator *result = hash->valueComparator;
608 hash->valueComparator = fn;
613 uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn) {
614 UObjectDeleter *result = hash->keyDeleter;
615 hash->keyDeleter = fn;
620 uhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn) {
621 UObjectDeleter *result = hash->valueDeleter;
622 hash->valueDeleter = fn;
627 uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
629 _uhash_internalSetResizePolicy(hash, policy);
630 hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);
631 hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);
632 _uhash_rehash(hash, &status);
636 uhash_count(const UHashtable *hash) {
637 return hash->count;
641 uhash_get(const UHashtable *hash,
645 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer;
649 uhash_iget(const UHashtable *hash,
653 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer;
657 uhash_geti(const UHashtable *hash,
661 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer;
665 uhash_igeti(const UHashtable *hash,
669 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer;
673 uhash_put(UHashtable *hash,
680 return _uhash_put(hash, keyholder, valueholder,
686 uhash_iput(UHashtable *hash,
693 return _uhash_put(hash, keyholder, valueholder,
699 uhash_puti(UHashtable *hash,
706 return _uhash_put(hash, keyholder, valueholder,
713 uhash_iputi(UHashtable *hash,
720 return _uhash_put(hash, keyholder, valueholder,
726 uhash_remove(UHashtable *hash,
730 return _uhash_remove(hash, keyholder).pointer;
734 uhash_iremove(UHashtable *hash,
738 return _uhash_remove(hash, keyholder).pointer;
742 uhash_removei(UHashtable *hash,
746 return _uhash_remove(hash, keyholder).integer;
750 uhash_iremovei(UHashtable *hash,
754 return _uhash_remove(hash, keyholder).integer;
758 uhash_removeAll(UHashtable *hash) {
761 U_ASSERT(hash != NULL);
762 if (hash->count != 0) {
763 while ((e = uhash_nextElement(hash, &pos)) != NULL) {
764 uhash_removeElement(hash, e);
767 U_ASSERT(hash->count == 0);
771 uhash_find(const UHashtable *hash, const void* key) {
775 e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder));
780 uhash_nextElement(const UHashtable *hash, int32_t *pos) {
785 U_ASSERT(hash != NULL);
786 for (i = *pos + 1; i < hash->length; ++i) {
787 if (!IS_EMPTY_OR_DELETED(hash->elements[i].hashcode)) {
789 return &(hash->elements[i]);
798 uhash_removeElement(UHashtable *hash, const UHashElement* e) {
799 U_ASSERT(hash != NULL);
803 return _uhash_internalRemoveElement(hash, nce).pointer;
866 * of the hash values will yield random results on machines
876 Normally we would return an error here about incompatible hash tables,