#include #include #include #include "ht.h" #define HT_REHASH_THRESHOLD 0.5 P_ATTR static NUM num_hft(CCR_MOD(void *) key) { if (key == NULL) { fleprintf0("Got NULL key!\n"); return 0; } return *((NUM *) key); } P_ATTR static BOOL num_cft(CCR_MOD(void *) keya, CCR_MOD(void *) keyb) { if ((keya == NULL && keyb != NULL) || (keyb == NULL && keya != NULL)) return 0; if (keya == NULL && keyb == NULL) return 1; return *((NUM *) keya) == *((NUM *) keyb); } /* SIZE is a hint to the number of elements that might be put in the table. In fact we will allocate more memory than this number, as a hash table works better if it is not fully used. NARGS is the number of arguments to follow. It should be between 0 and 2 (inclusive). If there are more than one argument, the first argument is used as the hashing function; if there are two arguments, the second argument is used as the comparison function. */ ht * new_ht(UNUM size, int nargs, ...) { if (nargs < 0 || nargs > 2) { fleprintf("NARGS should be between zero and two, but got %d\n", nargs); return NULL; } hash_func_t hft = num_hft; compare_func_t cft = num_cft; va_list args; if (nargs) { va_start(args, nargs); if (nargs >= 1) hft = va_arg(args, hash_func_t); if (nargs == 2) cft = va_arg(args, compare_func_t); va_end(args); } ht *htp = NULL; SAFE_MALLOC(ht, htp, 1, return NULL;); htp->capability = (size<<1)+(size>>1); htp->size = 0; htp->hf = hft; htp->cf = cft; /* For safer clean up */ htp->keys = NULL; htp->values = NULL; htp->indices = NULL; SAFE_MALLOC(NUM, htp->keys, htp->capability, goto cleanup;); SAFE_MALLOC(void*, htp->values, htp->capability, goto cleanup;); SAFE_MALLOC(NUM, htp->indices, htp->capability, goto cleanup;); /* Initialize the keys to be -1 and the values to be NULL */ memset(htp->keys, 0xff, sizeof (NUM) * htp->capability); memset(htp->values, 0, sizeof (void*) * htp->capability); /* Initialize indices to be -1 */ memset(htp->indices, 0xff, sizeof (NUM) * htp->capability); return htp; cleanup: if (htp->keys) free(htp->keys); if (htp->values) free(htp->values); if (htp->indices) free(htp->indices); free(htp); return NULL; } void destroy_ht(ht * restrict htp, HT_DESTROY_FLAG flag) { switch (flag) { case DESTROY_KEY_SELF: case DESTROY_KEY_NO_SELF: case DESTROY_EVERY_SELF: case DESTROY_EVERY_NO_SELF: case DESTROY_KEY_VALUE_FIRST_SELF: case DESTROY_KEY_VALUE_FIRST_NO_SELF: for (NUM i = 0; i < htp->size;) free(*(htp->keys+i++)); break; case DESTROY_KEY_FIRST_SELF: case DESTROY_KEY_FIRST_NO_SELF: case DESTROY_EVERY_FIRST_SELF: case DESTROY_EVERY_FIRST_NO_SELF: case DESTROY_KEY_FIRST_VALUE_SELF: case DESTROY_KEY_FIRST_VALUE_NO_SELF: free(*(htp->keys)); break; default: break; } switch (flag) { case DESTROY_VALUE_SELF: case DESTROY_VALUE_NO_SELF: case DESTROY_EVERY_SELF: case DESTROY_EVERY_NO_SELF: case DESTROY_KEY_FIRST_VALUE_SELF: case DESTROY_KEY_FIRST_VALUE_NO_SELF: for (NUM i = 0; i < htp->size;) free(*(htp->values+i++)); break; case DESTROY_VALUE_FIRST_SELF: case DESTROY_VALUE_FIRST_NO_SELF: case DESTROY_EVERY_FIRST_SELF: case DESTROY_EVERY_FIRST_NO_SELF: case DESTROY_KEY_VALUE_FIRST_SELF: case DESTROY_KEY_VALUE_FIRST_NO_SELF: free(*(htp->values)); break; default: break; } free(htp->values); free(htp->keys); free(htp->indices); switch (flag) { case DESTROY_NONE_SELF: case DESTROY_KEY_SELF: case DESTROY_KEY_FIRST_SELF: case DESTROY_VALUE_SELF: case DESTROY_VALUE_FIRST_SELF: case DESTROY_EVERY_SELF: case DESTROY_EVERY_FIRST_SELF: case DESTROY_KEY_FIRST_VALUE_SELF: case DESTROY_KEY_VALUE_FIRST_SELF: free(htp); break; default: break; } } static BOOL ht_expand(ht *htp) { htp->capability <<= 1; void **keys = NULL; NUM size = htp->size; void **values = NULL; if (size) { SAFE_MALLOC(void*, keys, size, goto cleanup;); SAFE_MALLOC(void*, values, size, goto cleanup;); memcpy(keys, htp->keys, sizeof(void*) * size); memcpy(values, htp->values, sizeof(void*) * size); } SAFE_REALLOC(void*, htp->keys, htp->capability, goto cleanup;); memset(htp->keys, 0, sizeof (void*) * htp->capability); SAFE_REALLOC(void*, htp->values, htp->capability, goto cleanup;); memset(htp->values, 0, sizeof(void*) * htp->capability); SAFE_REALLOC(NUM, htp->indices, htp->capability, goto cleanup;); memset(htp->indices, 0xff, sizeof (NUM) * htp->capability); htp->size = 0; for (NUM i = 0; i < size; i++) ht_insert(htp, *(keys+i), *(values+i)); if (keys) free(keys); if (values) free(values); return 0; cleanup: if (keys) free(keys); if (values) free(values); return 1; } #define PERTURBATION_SHIFT 5 /* On error return non-zero. */ static BOOL ht_probe(CC_MOD(ht *) htp, CC_MOD(void *) key, NUM *result) { NUM hashed = htp->hf(key); NUM ikey = hashed % htp->capability; unsigned long perturbation = hashed - ikey; for (NUM count = 0; count < htp->capability * HT_REHASH_THRESHOLD && *(htp->indices+ikey) >= 0 && /* continue if keys don't match */ !(htp->cf (*(htp->keys+*(htp->indices+ikey)), key)); count++) { ikey = 5 * ikey + 1 + perturbation; perturbation >>= PERTURBATION_SHIFT; ikey %= htp->capability; } if (*(htp->indices+ikey) >= 0 && !(htp->cf(*(htp->keys+*(htp->indices+ikey)), key))) { /* failed for some reason */ fleprintf("Fail to probe a location for the key, ikey = %ld, " "last index = %ld\n", ikey, *(htp->indices+ikey)); return 1; } *result = ikey; /* if (*((NUM*) key) == 3) { * fleprintf("ikey = %ld, result = %ld\n", ikey, *result); * } */ return 0; } BOOL ht_insert(ht * const restrict htp, void *key, void *value) { if (htp->size+1 >= HT_REHASH_THRESHOLD * htp->capability) { if (ht_expand(htp)) { fleprintf0("Fail to expand\n"); return 1; } } NUM ikey = 0; /* check errors */ if (ht_probe(htp, key, &ikey)) return 1; if (*(htp->indices+ikey) < 0) { /* not inserted before */ *(htp->indices+ikey) = htp->size; /* Store the key and the value in the array. */ *(htp->keys+htp->size) = key; *(htp->values+htp->size) = value; (htp->size)++; } else { /* error check is performed in ht_probe */ *(htp->values+*(htp->indices+ikey)) = value; } /* fleprintf("ikey = %ld, size = %d, capability = %llu\n", * ikey, htp->size, htp->capability); */ return 0; } BOOL ht_delete(ht * const restrict htp, void *key, HT_DELETE_FLAG flag) { NUM ikey = 0; /* check errors */ if (ht_probe(htp, key, &ikey)) return 1; if (*(htp->indices+ikey) < 0) { /* not inserted before */ } else { (htp->size)--; switch (flag) { case DELETE_KEY: case DELETE_EVERY: free(*(htp->keys+*(htp->indices+ikey))); break; default: break; } switch (flag) { case DELETE_VALUE: case DELETE_EVERY: free(*(htp->values+*(htp->indices+ikey))); break; default: break; } *(htp->values+*(htp->indices+ikey)) = NULL; *(htp->keys+*(htp->indices+ikey)) = NULL; *(htp->indices+ikey) = -1; } return 0; } P_ATTR void * ht_find(CCR_MOD(ht *) htp, void *key) { NUM ikey = 0; /* check errors */ if (ht_probe(htp, key, &ikey)) return NULL; if (*(htp->indices+ikey) < 0) return NULL; return *(htp->values+*(htp->indices+ikey)); } P_ATTR NUM ht_size(CCR_MOD(ht *) htp) { return (NUM) htp->size; } P_ATTR void ** ht_values(CCR_MOD(ht *) htp) { return htp->values; } P_ATTR void ** ht_keys(CCR_MOD(ht *) htp) { return htp->keys; }