ipc/generic_hash.c

/***************************************************************************
 * 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 <sys/types.h>
#include <stdlib.h>
#include <assert.h>
#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 */