/*************************************************************************** * Copyright 1995 Michael Veksler. mveksler@vnet.ibm.com *************************************************************************** * File: generic_hash.c * Purpose : dynamically growing hash, may use shared or local memory. *************************************************************************** */ #ifdef CONFIG_IPC #include #include #include #include "generic_hash.h" #define ROUND_UP4(num) (( (num)+3) & ~3) #define FREE_ENTRY 0 #define DELETED_ENTRY ((DWORD)-1) #define NO_OF_PRIMES 512 #define GET_ITEM(items,size,i)\ (*(HASH_ITEM*) \ ( ((char *)(items))+ \ (i)*(size)) ) static HASH_ITEM *locate_entry(HASH_CONTAINER* hash, DWORD key, HASH_VAL *seeked_data, BOOL32 skip_deleted); static void copy_hash_items(HASH_CONTAINER *hash, HASH_ITEM *old_items, int old_n_items); static BOOL32 arrays_initialized = FALSE; static int primes[NO_OF_PRIMES]; static int best_primes[NO_OF_PRIMES]; static int no_of_primes; static int no_of_best_primes; static int max_num; /* binary search for `num' in the `primes' array */ static BOOL32 prime_binary_search_found(int num) { int min_idx, max_idx, idx; min_idx=0; max_idx=no_of_primes-1; while (min_idx <= max_idx) { idx = (max_idx + min_idx) >> 1; if (num == primes[idx]) return TRUE; if (num < primes[idx]) max_idx = idx-1; else min_idx = idx+1; } return FALSE; } static BOOL32 is_prime(int num) { int i; if ((num & 0x1) == 0) /* can be divided by 2 */ if (num == 2) return TRUE; else return FALSE; if (num <= primes[no_of_primes-1]) return prime_binary_search_found(num); for (i=0 ; i < no_of_primes ; i++) { if (num % primes[i] == 0) return FALSE; if (num < primes[i] * primes[i]) return TRUE; } return TRUE; } static void setup_primes() { int num; primes[0]=2; primes[1]=3; no_of_primes=2; /* count in modulo 6 to avoid numbers that divide by 2 or 3 */ for (num=5 ; ; num+=6) { if (is_prime(num)) { primes[no_of_primes++]=num; if (no_of_primes >= NO_OF_PRIMES) break; } if (is_prime(num+2)) { primes[no_of_primes++]=num+2; if (no_of_primes >= NO_OF_PRIMES) break; } } max_num= primes[no_of_primes-1] * primes[no_of_primes-1]; } /* Find primes which are far "enough" from powers of two */ void setup_best_primes() { int i; int num; int pow2before, pow2after; int min_range, max_range; min_range=3; max_range=3; pow2before= 2; pow2after= 4; no_of_best_primes= 0; for (i=0 ; i < no_of_primes ; i++){ num= primes[i]; if (num > pow2after) { pow2before= pow2after; pow2after <<=1; min_range= pow2before+ (pow2before >> 3); max_range= pow2after- (pow2before >> 2); } if (num > min_range && num < max_range) best_primes[no_of_best_primes++]=num; } } /* binary search for `num' in the `best_primes' array, * Return smallest best_prime >= num. */ static int best_prime_binary_search(int num) { int min_idx, max_idx, idx; min_idx=0; max_idx=no_of_best_primes-1; while (1) { idx = (max_idx + min_idx) >> 1; if (num == best_primes[idx]) return num; if (num < best_primes[idx]) { max_idx = idx-1; if (max_idx <= min_idx) return best_primes[idx]; } else { min_idx = idx+1; if (min_idx >= max_idx) return best_primes[max_idx]; } } } /* Find the best prime, near `num' (which can be any number) */ static int best_prime(int num) { int log2; int pow2less, pow2more; int min_range, max_range; if (num < 11) return 11; if (num <= best_primes[no_of_best_primes-1]) return best_prime_binary_search(num); assert( num < max_num ); for (log2=0 ; num >> log2 ; log2++) ; pow2less= 1 << log2; pow2more= 1 << (log2+1); min_range= pow2less + (pow2less >> 3); max_range= pow2more - (pow2more >> 3); if (num < min_range) num= min_range; num |= 1; /* make sure num can't be divided by 2 */ while (1) { if (num >= max_range) { pow2less<<= 1; pow2more<<= 1; min_range= pow2less + (pow2less >> 3); max_range= pow2more - (pow2more >> 3); num= min_range | 1; /* make sure num can't be divided by 2 */ } /* num should be here in the range: (min_range, max_range) */ if (is_prime(num)) return num; num+=2; } } /* FIXME: This can be done before compiling. (uning a script)*/ static void setup_arrays() { setup_primes(); setup_best_primes(); } /* Discard all DELETED_ENTRYs moving the data to it's correct location. * Done without a temporary buffer. * May require some efficiency improvements ( currently it's o(N^2) * or is it o(N^3) in the worst case ? In the avarege it seems to be * something like o(N log (N))) */ static void static_collect_garbge(HASH_CONTAINER *hash) { int i; BOOL32 change; HASH_ITEM *items; HASH_ITEM *located; HASH_ITEM *item; int key; items= hash->items; do { change= FALSE; for (i=hash->shared->total_items-1 ; i >= 0 ; i--) { item= &GET_ITEM(items,hash->bytes_per_item,i); key= item->key; if (key != DELETED_ENTRY && key != FREE_ENTRY) { /* try to place the entry in a deleted location */ located= locate_entry(hash, key, &item->data, 0 /* no skip_deleted */); if (located->key == DELETED_ENTRY) { change= TRUE; memcpy(&located, &item, hash->bytes_per_item); item->key= DELETED_ENTRY; } } } } while (change); /* No change means that there is no need to go through a DELETED_ENTRY * in order to reach an item, so DELETED_ENTRY looses it's special * meaning, and it is the same as FREE_ENTRY. */ for (i=hash->shared->total_items-1 ; i >= 0 ; i--) if (GET_ITEM(items,hash->bytes_per_item,i).key == DELETED_ENTRY) GET_ITEM(items,hash->bytes_per_item,i).key = FREE_ENTRY; hash->shared->deleted_items=0; } static void collect_garbge(HASH_CONTAINER *hash) { HASH_SHARED *shared= hash->shared; HASH_ITEM *temp_items; int size; size= shared->total_items * hash->bytes_per_item; temp_items= (HASH_ITEM*)malloc(size); if (temp_items==NULL) { static_collect_garbge(hash); } else { memcpy(temp_items, hash->items, size); copy_hash_items(hash, temp_items, shared->total_items); } } static void copy_hash_items(HASH_CONTAINER *hash, HASH_ITEM *old_items, int old_n_items) { HASH_SHARED *shared= hash->shared; HASH_ITEM *item; int i; shared->deleted_items = 0; shared->free_items= shared->total_items; /* make all items free */ for (i= shared->total_items-1 ; i>=0 ; i--) GET_ITEM(hash->items, hash->bytes_per_item, i).key = FREE_ENTRY; /* copy items */ for (i=0 ; i <= old_n_items; i++) { item= &GET_ITEM(old_items, hash->bytes_per_item,i); if (item->key != FREE_ENTRY && item->key != DELETED_ENTRY) hash_add_item(hash, item->key, &item->data); } } static void reorder_hash(HASH_CONTAINER *hash) { HASH_SHARED *shared= hash->shared; HASH_ITEM *items, *old_items; HASH_PTR shared_items, old_shared_items; int n_items, old_n_items; int size; if (shared->deleted_items > hash->min_free_items) { collect_garbge(hash); return; } n_items= best_prime(shared->total_items * HASH_REALLOC_JUMPS); size= n_items * (sizeof(items[0]) - sizeof(items[0].data) + hash->bytes_per_item); shared_items= hash->allocate_mem(size); items= hash->access_mem(shared_items); if (items == NULL) { collect_garbge(hash); return; } old_shared_items = shared->items; old_n_items= shared->total_items; old_items= hash->items; /* setup a new clean hash based on the parameters of the original one */ hash->items= items; shared->total_items = n_items; shared->items= shared_items; set_hash_parameters(hash, hash->maximum_load); copy_hash_items(hash, old_items, old_n_items); hash->free_mem(old_shared_items); hash->last_ptr_update= ++shared->ptr_updates; } /* low level: attach hash existing hash items, no checks are performed * No complex calculations done. */ static HASH_CONTAINER *attach_no_check(HASH_ITEM *items, int bytes_per_datum) { HASH_CONTAINER *hash; int bytes_per_item; HASH_ITEM dummy_item; hash= (HASH_CONTAINER*) malloc(sizeof(HASH_CONTAINER) ); if (hash == NULL) return NULL; bytes_per_item= bytes_per_datum+ sizeof(dummy_item)-sizeof(dummy_item.data); hash->bytes_per_item= ROUND_UP4(bytes_per_item); hash->items= items; hash->is_correct_item= NULL; hash->allocate_mem= HASH_MEM_ALLOC; hash->access_mem= HASH_MEM_ACCESS; hash->free_mem= HASH_MEM_FREE; set_hash_parameters(hash, HASH_LOAD); return hash; } /* Attach existing & running remote (i.e. shared) hash. * Attach the items using the data stored in "shared" */ HASH_CONTAINER *attach_remote_hash(HASH_SHARED *shared, int bytes_per_datum, HASH_ITEM *(*access_mem)(HASH_PTR)) { HASH_CONTAINER *hash; HASH_ITEM *items; assert(access_mem != NULL); if (! arrays_initialized) setup_arrays(); items=access_mem(shared->items); hash= attach_no_check(items, bytes_per_datum); if (hash == NULL) return NULL; hash->shared_was_malloced = FALSE; hash->shared= shared; return (hash); } HASH_CONTAINER *create_remote_hash(HASH_SHARED *shared, int bytes_per_datum, int total_items, HASH_PTR (*allocate_mem)(int size), HASH_ITEM *(*access_mem)(HASH_PTR)) { HASH_CONTAINER *hash; int size; int i; assert(total_items >= 1); assert(bytes_per_datum >=1); assert(access_mem != NULL); assert(allocate_mem != NULL); assert(shared != NULL); if (! arrays_initialized) setup_arrays(); if (total_items < MIN_HASH) total_items= MIN_HASH; else total_items= best_prime(total_items); hash= attach_no_check(NULL, bytes_per_datum); if (hash==NULL) { free(hash); return NULL; } shared->total_items= total_items; hash->shared= shared; hash->shared_was_malloced = FALSE; size= total_items * hash->bytes_per_item; shared->items = allocate_mem(size); hash->items= access_mem(shared->items); if (hash->items == NULL ) { free(hash); return NULL; } shared->items.ptr= hash->items; /* make all items free */ for (i=0 ; i < total_items ; i++) GET_ITEM(hash->items,hash->bytes_per_item,i).key = FREE_ENTRY; shared->deleted_items= 0; shared->free_items= total_items; shared->ptr_updates= 0; return hash; } /* hash constructor: create brand new hash */ HASH_CONTAINER *create_hash(int bytes_per_datum, int total_items) { HASH_CONTAINER *hash; HASH_SHARED *shared; shared= (HASH_SHARED*)malloc(sizeof(HASH_SHARED)); if (shared == NULL) return NULL; hash= create_remote_hash(shared, bytes_per_datum, total_items, HASH_MEM_ALLOC, HASH_MEM_ACCESS); if (hash == NULL) { free(shared); return NULL; } hash->shared_was_malloced = TRUE; return hash; } /* set the extra handlers to non default values */ void set_hash_handlers(HASH_CONTAINER *hash, HASH_ITEM_TEST *is_correct_item, HASH_PTR (*allocate_mem)(int size), void (*free_mem)(HASH_PTR), HASH_ITEM *(*access_mem)(HASH_PTR)) { assert(hash); assert(allocate_mem); assert(free_mem); hash->free_mem = free_mem; hash->allocate_mem = allocate_mem; hash->access_mem = access_mem; hash->is_correct_item = is_correct_item; } /* set extra parameters */ void set_hash_parameters(HASH_CONTAINER *hash, int load) { assert(hash); assert(load>30); /* no sence to realloc with less than */ /* 50% load, limiting to 30% to be on */ /* the safe size */ assert(load<=100); hash->maximum_load= load; hash->min_free_items= (1.0 - load/100.0) * hash->shared->total_items + 1 ; } /* hash destructor: destroy anything related to the hash */ void destroy_hash(HASH_CONTAINER *hash) { assert(hash); hash->free_mem(hash->shared->items); if (hash->shared_was_malloced) free(hash->shared); free(hash); } /* hash destructor: just detach hash, without destroing it (makes */ /* sence in shared memory environment) */ void detach_hash(HASH_CONTAINER *hash) { assert(hash); free(hash); } /********** Hash usage *************/ static __inline__ BOOL32 correct_entry(HASH_ITEM *item, int key, HASH_VAL *seeked_data, HASH_ITEM_TEST *is_correct_item, BOOL32 skip_deleted) { switch(item->key) { case FREE_ENTRY: return TRUE; case DELETED_ENTRY: return skip_deleted ? FALSE : TRUE; default: if (item->key != key) return FALSE; if (is_correct_item != NULL) return is_correct_item(&item->data, seeked_data); else return TRUE; } } /* The algorithm of the hash (one of the 2 standard hash implementations): * Iterate through the hash table until * 1. The entry has been found. * 2. A FREE entry has been found. * 3. For insert operations only- A DELETED entry has been found. * The difference between DELETED and FREE entires is that * DELETED entry was one occupied, while FREE was never allocated. * The idea behind this structure to keep other entries reachable. */ static HASH_ITEM *locate_entry(HASH_CONTAINER* hash, DWORD key, HASH_VAL *seeked_data, BOOL32 skip_deleted) { DWORD hash_idx, hash_leaps; HASH_ITEM *item; int i; int total_items; assert(hash); total_items= hash->shared->total_items; hash_idx= key % total_items; item= &GET_ITEM(hash->items, hash->bytes_per_item, hash_idx); if ( correct_entry( item, key, seeked_data, hash->is_correct_item, skip_deleted) ) return item; /* get the WORDs in different order in this DWORD to avoid clustering */ hash_leaps=((DWORD)MAKELONG(HIWORD(key), LOWORD(key)) % (total_items-1)) +1; /* interate through the hash table using hash_leaps */ for (i= total_items ; i ; i--) { hash_idx+= hash_leaps; if (hash_idx > total_items) hash_idx -= total_items; item= &GET_ITEM(hash->items,hash->bytes_per_item, hash_idx); if ( correct_entry( item, key, seeked_data, hash->is_correct_item, skip_deleted) ) return item; } return NULL; } static __inline__ void sync_shared_hash(HASH_CONTAINER *hash) { HASH_SHARED *shared= hash->shared; if (shared->ptr_updates == hash->last_ptr_update) return; assert(shared->ptr_updates >= hash->last_ptr_update); hash->last_ptr_update= shared->ptr_updates; hash->min_free_items= (1.0 - hash->maximum_load/100.0) * shared->total_items + 1 ; hash->items= hash->access_mem(shared->items); } HASH_VAL *hash_locate_item(HASH_CONTAINER* hash, int key, HASH_VAL *seeked_data) { HASH_ITEM *item; assert(hash != NULL); sync_shared_hash(hash); item= locate_entry(hash, key, seeked_data, 1 /* skip_deleted */); if (item == NULL) return NULL; if (item->key == FREE_ENTRY ) return NULL; return &item->data; } BOOL32 hash_add_item(HASH_CONTAINER* hash, int key, HASH_VAL *data) { HASH_SHARED *shared; HASH_ITEM *item; assert(hash != NULL); sync_shared_hash(hash); shared= hash->shared; item=locate_entry(hash, key, data, 0 /* no skip_deleted */); assert(item != NULL); if (item->key == key) return FALSE; if (item->key == FREE_ENTRY) shared->free_items--; else shared->deleted_items--; item->key= key; memcpy(&item->data, data, hash->bytes_per_item-sizeof(key)); if (shared->free_items < hash->min_free_items || shared->deleted_items > hash->min_free_items) reorder_hash(hash); return TRUE; } BOOL32 hash_delete_item(HASH_CONTAINER* hash, int key, HASH_VAL *seeked_data) { HASH_ITEM *item; assert(hash != NULL); sync_shared_hash(hash); item=locate_entry(hash, key, seeked_data, 1 /* skip_deleted */); if (item == NULL) return FALSE; if (item->key == FREE_ENTRY) return FALSE; item->key = DELETED_ENTRY; hash->shared->deleted_items++; return TRUE; } void *ret_null() { return NULL; } HASH_ITEM *access_local_hash(HASH_PTR ptr) { return ptr.ptr; } #endif /* CONFIG_IPC */