Lines Matching full:hash
19 /* This hashtable is implemented as a double hash. All elements are
21 * resolution (no linked list, etc.). When there is a hash collision
23 * using a secondary hash. The secondary hash is an increment
24 * computed as a hash function (a different one) of the primary
25 * hashcode. This increment is added to the initial hash value to
26 * obtain further slots assigned to the same hash code. For this to
119 #define HASH_DELETE_KEY_VALUE(hash, keypointer, valuepointer) \
120 if (hash->keyDeleter != NULL && keypointer != NULL) { \
121 (*hash->keyDeleter)(keypointer); \
123 if (hash->valueDeleter != NULL && valuepointer != NULL) { \
124 (*hash->valueDeleter)(valuepointer); \
140 _uhash_setElement(UHashtable *hash, UHashElement* e,
145 if (hash->keyDeleter != NULL && e->key.pointer != NULL &&
147 (*hash->keyDeleter)(e->key.pointer);
149 if (hash->valueDeleter != NULL) {
152 (*hash->valueDeleter)(oldValue.pointer);
180 _uhash_internalRemoveElement(UHashtable *hash, UHashElement* e) {
183 --hash->count;
185 return _uhash_setElement(hash, e, HASH_DELETED, empty, empty, 0);
189 _uhash_internalSetResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
190 U_ASSERT(hash != NULL);
193 hash->lowWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2];
194 hash->highWaterRatio = RESIZE_POLICY_RATIO_TABLE[policy * 2 + 1];
207 _uhash_allocate(UHashtable *hash,
218 hash->primeIndex = primeIndex;
219 hash->length = PRIMES[primeIndex];
221 p = hash->elements = (UHashElement*)
222 uprv_malloc(sizeof(UHashElement) * hash->length);
224 if (hash->elements == NULL) {
232 limit = p + hash->length;
240 hash->count = 0;
241 hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);
242 hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);
309 * a. identical: First check the hash values for a quick check,
327 * hash) is relatively prime to the table length.
330 _uhash_find(const UHashtable *hash, UHashTok key,
337 UHashElement *elements = hash->elements;
340 startIndex = theIndex = (hashcode ^ 0x4000000) % hash->length;
345 if ((*hash->keyComparator)(key, elements[theIndex].key)) {
350 * but for which the hash code does not match. Keep
363 jump = (hashcode % (hash->length - 1)) + 1;
365 theIndex = (theIndex + jump) % hash->length;
392 _uhash_rehash(UHashtable *hash, UErrorCode *status) {
394 UHashElement *old = hash->elements;
395 int32_t oldLength = hash->length;
396 int32_t newPrimeIndex = hash->primeIndex;
399 if (hash->count > hash->highWaterMark) {
403 } else if (hash->count < hash->lowWaterMark) {
411 _uhash_allocate(hash, newPrimeIndex, status);
414 hash->elements = old;
415 hash->length = oldLength;
421 UHashElement *e = _uhash_find(hash, old[i].key, old[i].hashcode);
427 ++hash->count;
435 _uhash_remove(UHashtable *hash,
445 UHashElement* e = _uhash_find(hash, key, hash->keyHasher(key));
450 result = _uhash_internalRemoveElement(hash, e);
451 if (hash->count < hash->lowWaterMark) {
453 _uhash_rehash(hash, &status);
460 _uhash_put(UHashtable *hash,
468 * non-NULL keyDeleter. Then the key, the hash and the value are
478 U_ASSERT(hash != NULL);
484 return _uhash_remove(hash, key);
486 if (hash->count > hash->highWaterMark) {
487 _uhash_rehash(hash, status);
493 hashcode = (*hash->keyHasher)(key);
494 e = _uhash_find(hash, key, hashcode);
505 ++hash->count;
506 if (hash->count == hash->length) {
508 --hash->count;
518 return _uhash_setElement(hash, e, hashcode & 0x7FFFFFFF, key, value, hint);
525 HASH_DELETE_KEY_VALUE(hash, key.pointer, value.pointer);
571 uhash_close(UHashtable *hash) {
572 if (hash == NULL) {
575 if (hash->elements != NULL) {
576 if (hash->keyDeleter != NULL || hash->valueDeleter != NULL) {
579 while ((e = (UHashElement*) uhash_nextElement(hash, &pos)) != NULL) {
580 HASH_DELETE_KEY_VALUE(hash, e->key.pointer, e->value.pointer);
583 uprv_free(hash->elements);
584 hash->elements = NULL;
586 if (hash->allocated) {
587 uprv_free(hash);
592 uhash_setKeyHasher(UHashtable *hash, UHashFunction *fn) {
593 UHashFunction *result = hash->keyHasher;
594 hash->keyHasher = fn;
599 uhash_setKeyComparator(UHashtable *hash, UKeyComparator *fn) {
600 UKeyComparator *result = hash->keyComparator;
601 hash->keyComparator = fn;
605 uhash_setValueComparator(UHashtable *hash, UValueComparator *fn){
606 UValueComparator *result = hash->valueComparator;
607 hash->valueComparator = fn;
612 uhash_setKeyDeleter(UHashtable *hash, UObjectDeleter *fn) {
613 UObjectDeleter *result = hash->keyDeleter;
614 hash->keyDeleter = fn;
619 uhash_setValueDeleter(UHashtable *hash, UObjectDeleter *fn) {
620 UObjectDeleter *result = hash->valueDeleter;
621 hash->valueDeleter = fn;
626 uhash_setResizePolicy(UHashtable *hash, enum UHashResizePolicy policy) {
628 _uhash_internalSetResizePolicy(hash, policy);
629 hash->lowWaterMark = (int32_t)(hash->length * hash->lowWaterRatio);
630 hash->highWaterMark = (int32_t)(hash->length * hash->highWaterRatio);
631 _uhash_rehash(hash, &status);
635 uhash_count(const UHashtable *hash) {
636 return hash->count;
640 uhash_get(const UHashtable *hash,
644 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer;
648 uhash_iget(const UHashtable *hash,
652 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.pointer;
656 uhash_geti(const UHashtable *hash,
660 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer;
664 uhash_igeti(const UHashtable *hash,
668 return _uhash_find(hash, keyholder, hash->keyHasher(keyholder))->value.integer;
672 uhash_put(UHashtable *hash,
679 return _uhash_put(hash, keyholder, valueholder,
685 uhash_iput(UHashtable *hash,
692 return _uhash_put(hash, keyholder, valueholder,
698 uhash_puti(UHashtable *hash,
705 return _uhash_put(hash, keyholder, valueholder,
712 uhash_iputi(UHashtable *hash,
719 return _uhash_put(hash, keyholder, valueholder,
725 uhash_remove(UHashtable *hash,
729 return _uhash_remove(hash, keyholder).pointer;
733 uhash_iremove(UHashtable *hash,
737 return _uhash_remove(hash, keyholder).pointer;
741 uhash_removei(UHashtable *hash,
745 return _uhash_remove(hash, keyholder).integer;
749 uhash_iremovei(UHashtable *hash,
753 return _uhash_remove(hash, keyholder).integer;
757 uhash_removeAll(UHashtable *hash) {
760 U_ASSERT(hash != NULL);
761 if (hash->count != 0) {
762 while ((e = uhash_nextElement(hash, &pos)) != NULL) {
763 uhash_removeElement(hash, e);
766 U_ASSERT(hash->count == 0);
770 uhash_find(const UHashtable *hash, const void* key) {
774 e = _uhash_find(hash, keyholder, hash->keyHasher(keyholder));
779 uhash_nextElement(const UHashtable *hash, int32_t *pos) {
784 U_ASSERT(hash != NULL);
785 for (i = *pos + 1; i < hash->length; ++i) {
786 if (!IS_EMPTY_OR_DELETED(hash->elements[i].hashcode)) {
788 return &(hash->elements[i]);
797 uhash_removeElement(UHashtable *hash, const UHashElement* e) {
798 U_ASSERT(hash != NULL);
801 return _uhash_internalRemoveElement(hash, (UHashElement*) e).pointer;
831 * PUBLIC Key Hash Functions
835 Compute the hash by iterating sparsely over about 32 (up to 63)
837 multiply the previous hash value by a prime number and add the new
844 int32_t hash = 0; \
851 hash = (hash * 37) + DEREF; \
855 return hash
891 * of the hash values will yield random results on machines
901 Normally we would return an error here about incompatible hash tables,
