ipc/generic_hash.c

   1 /***************************************************************************
   2  * Copyright 1995 Michael Veksler. mveksler@vnet.ibm.com
   3  ***************************************************************************
   4  * File:      generic_hash.c
   5  * Purpose :  dynamically growing hash, may use shared or local memory.
   6  ***************************************************************************
   7  */
   8 #ifdef CONFIG_IPC
   9
  10 #include <sys/types.h>
  11 #include <stdlib.h>
  12 #include <assert.h>
  13 #include "generic_hash.h"
  14
  15 #define ROUND_UP4(num) (( (num)+3) & ~3)
  16
  17 #define FREE_ENTRY          0
  18 #define DELETED_ENTRY       ((DWORD)-1)
  19
  20 #define NO_OF_PRIMES   512
  21 #define GET_ITEM(items,size,i)\
  22            (*(HASH_ITEM*) \
  23             (  ((char *)(items))+ \
  24                (i)*(size)) )
  25
  26 static HASH_ITEM *locate_entry(HASH_CONTAINER* hash, DWORD key,
  27                                HASH_VAL *seeked_data, BOOL32 skip_deleted);
  28
  29 static void copy_hash_items(HASH_CONTAINER *hash, HASH_ITEM *old_items,
  30                             int old_n_items);
  31
  32 static BOOL32 arrays_initialized = FALSE;
  33 static int primes[NO_OF_PRIMES];
  34 static int best_primes[NO_OF_PRIMES];
  35 static int no_of_primes;
  36 static int no_of_best_primes;
  37 static int max_num;
  38
  39 /* binary search for `num' in the `primes' array */
  40 static BOOL32 prime_binary_search_found(int num)
  41 {
  42   int min_idx, max_idx, idx;
  43
  44   min_idx=0;
  45   max_idx=no_of_primes-1;
  46
  47   while (min_idx <= max_idx) {
  48      idx = (max_idx + min_idx) >> 1;
  49      if (num == primes[idx])
  50         return TRUE;
  51      if (num < primes[idx])
  52         max_idx = idx-1;
  53      else
  54         min_idx = idx+1;
  55   }
  56   return FALSE;
  57 }
  58
  59 static BOOL32 is_prime(int num)
  60 {
  61   int i;
  62   if ((num & 0x1) == 0)            /* can be divided by 2 */
  63      if (num == 2)
  64         return TRUE;
  65      else
  66         return FALSE;
  67
  68   if (num <= primes[no_of_primes-1])
  69      return prime_binary_search_found(num);
  70
  71   for (i=0 ; i < no_of_primes ; i++) {
  72      if (num % primes[i] == 0)
  73         return FALSE;
  74      if (num < primes[i] * primes[i])
  75         return TRUE;
  76   }
  77   return TRUE;
  78 }
  79
  80 static void setup_primes()
  81 {
  82   int num;
  83
  84   primes[0]=2;
  85   primes[1]=3;
  86   no_of_primes=2;
  87
  88   /* count in modulo 6 to avoid numbers that divide by 2 or 3 */
  89   for (num=5 ; ; num+=6) {
  90      if (is_prime(num)) {
  91         primes[no_of_primes++]=num;
  92         if (no_of_primes >= NO_OF_PRIMES)
  93            break;
  94      }
  95      if (is_prime(num+2)) {
  96         primes[no_of_primes++]=num+2;
  97         if (no_of_primes >= NO_OF_PRIMES)
  98            break;
  99      }
 100   }
 101   max_num= primes[no_of_primes-1] * primes[no_of_primes-1];
 102 }
 103
 104
 105 /* Find primes which are far "enough" from powers of two */
 106
 107 void setup_best_primes()
 108 {
 109   int i;
 110   int num;
 111   int pow2before, pow2after;
 112   int min_range, max_range;
 113
 114   min_range=3;
 115   max_range=3;
 116   pow2before= 2;
 117   pow2after= 4;
 118
 119   no_of_best_primes= 0;
 120   for (i=0 ; i < no_of_primes ; i++){
 121      num= primes[i];
 122
 123      if (num > pow2after) {
 124         pow2before= pow2after;
 125         pow2after <<=1;
 126         min_range= pow2before+ (pow2before >> 3);
 127         max_range= pow2after-  (pow2before >> 2);
 128      }
 129      if (num > min_range && num < max_range)
 130         best_primes[no_of_best_primes++]=num;
 131   }
 132 }
 133
 134 /* binary search for `num' in the `best_primes' array,
 135  * Return smallest best_prime >= num.
 136  */
 137 static int best_prime_binary_search(int num)
 138 {
 139   int min_idx, max_idx, idx;
 140
 141   min_idx=0;
 142   max_idx=no_of_best_primes-1;
 143
 144   while (1) {
 145      idx = (max_idx + min_idx) >> 1;
 146      if (num == best_primes[idx])
 147         return num;
 148      if (num < best_primes[idx]) {
 149         max_idx = idx-1;
 150         if (max_idx <= min_idx)
 151             return best_primes[idx];
 152     }
 153      else {
 154         min_idx = idx+1;
 155         if (min_idx >= max_idx)
 156             return best_primes[max_idx];
 157     }
 158   }
 159
 160 }
 161
 162 /* Find the best prime, near `num' (which can be any number) */
 163 static int best_prime(int num)
 164 {
 165   int log2;
 166   int pow2less, pow2more;
 167   int min_range, max_range;
 168
 169   if (num < 11)
 170      return 11;
 171
 172   if (num <= best_primes[no_of_best_primes-1])
 173      return best_prime_binary_search(num);
 174
 175   assert( num < max_num );
 176
 177   for (log2=0 ; num >> log2 ; log2++)
 178      ;
 179
 180   pow2less= 1 << log2;
 181   pow2more= 1 << (log2+1);
 182   min_range= pow2less + (pow2less >> 3);
 183   max_range= pow2more - (pow2more >> 3);
 184
 185   if (num < min_range)
 186      num= min_range;
 187
 188   num |= 1;                        /* make sure num can't be divided by 2 */
 189
 190   while (1) {
 191      if (num >= max_range) {
 192         pow2less<<= 1;
 193         pow2more<<= 1;
 194         min_range= pow2less + (pow2less >> 3);
 195         max_range= pow2more - (pow2more >> 3);
 196         num= min_range | 1;        /* make sure num can't be divided by 2 */
 197      }
 198      /* num should be here in the range: (min_range, max_range) */
 199      if (is_prime(num))
 200         return num;
 201      num+=2;
 202   }
 203 }
 204
 205 /* FIXME: This can be done before compiling. (uning a script)*/
 206 static void setup_arrays()
 207 {
 208   setup_primes();
 209   setup_best_primes();
 210 }
 211
 212 /* Discard all DELETED_ENTRYs moving the data to it's correct location.
 213  * Done without a temporary buffer.
 214  * May require some efficiency improvements ( currently it's o(N^2)
 215  * or is it o(N^3) in the worst case ? In the avarege it seems to be
 216  * something like o(N log (N)))
 217  */
 218 static void static_collect_garbge(HASH_CONTAINER *hash)
 219 {
 220    int i;
 221    BOOL32 change;
 222    HASH_ITEM *items;
 223    HASH_ITEM *located;
 224    HASH_ITEM *item;
 225    int key;
 226
 227    items= hash->items;
 228
 229    do {
 230       change= FALSE;
 231       for (i=hash->shared->total_items-1 ; i >= 0 ; i--) {
 232          item= &GET_ITEM(items,hash->bytes_per_item,i);
 233          key= item->key;
 234          if (key != DELETED_ENTRY && key != FREE_ENTRY) {
 235             /* try to place the entry in a deleted location */
 236             located= locate_entry(hash, key, &item->data,
 237                                   0 /* no skip_deleted */);
 238             if (located->key == DELETED_ENTRY) {
 239                change= TRUE;
 240                memcpy(&located, &item,
 241                       hash->bytes_per_item);
 242                item->key= DELETED_ENTRY;
 243             }
 244          }
 245       }
 246    } while (change);
 247
 248    /* No change means that there is no need to go through a DELETED_ENTRY
 249     * in order to reach an item, so DELETED_ENTRY looses it's special
 250     * meaning, and it is the same as FREE_ENTRY.
 251     */
 252    for (i=hash->shared->total_items-1 ; i >= 0 ; i--)
 253       if (GET_ITEM(items,hash->bytes_per_item,i).key == DELETED_ENTRY)
 254          GET_ITEM(items,hash->bytes_per_item,i).key = FREE_ENTRY;
 255    hash->shared->deleted_items=0;
 256 }
 257
 258 static void collect_garbge(HASH_CONTAINER *hash)
 259 {
 260    HASH_SHARED *shared= hash->shared;
 261    HASH_ITEM *temp_items;
 262    int size;
 263
 264    size= shared->total_items * hash->bytes_per_item;
 265    temp_items= (HASH_ITEM*)malloc(size);
 266    if (temp_items==NULL) {
 267       static_collect_garbge(hash);
 268    } else {
 269       memcpy(temp_items, hash->items, size);
 270       copy_hash_items(hash, temp_items, shared->total_items);
 271    }
 272 }
 273
 274
 275 static void copy_hash_items(HASH_CONTAINER *hash, HASH_ITEM *old_items,
 276                             int old_n_items)
 277 {
 278    HASH_SHARED *shared= hash->shared;
 279    HASH_ITEM *item;
 280    int i;
 281
 282    shared->deleted_items = 0;
 283    shared->free_items= shared->total_items;
 284
 285    /* make all items free */
 286    for (i= shared->total_items-1 ; i>=0 ; i--)
 287       GET_ITEM(hash->items, hash->bytes_per_item, i).key = FREE_ENTRY;
 288
 289    /* copy items */
 290    for (i=0 ; i <= old_n_items; i++) {
 291       item= &GET_ITEM(old_items, hash->bytes_per_item,i);
 292       if (item->key != FREE_ENTRY && item->key != DELETED_ENTRY)
 293          hash_add_item(hash, item->key, &item->data);
 294    }
 295 }
 296
 297
 298 static void reorder_hash(HASH_CONTAINER *hash)
 299 {
 300   HASH_SHARED *shared= hash->shared;
 301   HASH_ITEM *items, *old_items;
 302   HASH_PTR shared_items, old_shared_items;
 303   int n_items, old_n_items;
 304   int size;
 305
 306   if (shared->deleted_items > hash->min_free_items) {
 307      collect_garbge(hash);
 308      return;
 309   }
 310   n_items= best_prime(shared->total_items * HASH_REALLOC_JUMPS);
 311
 312   size= n_items *
 313         (sizeof(items[0]) - sizeof(items[0].data) + hash->bytes_per_item);
 314
 315   shared_items= hash->allocate_mem(size);
 316   items= hash->access_mem(shared_items);
 317
 318   if (items == NULL) {
 319         collect_garbge(hash);
 320         return;
 321   }
 322   old_shared_items = shared->items;
 323   old_n_items=       shared->total_items;
 324   old_items=         hash->items;
 325
 326   /* setup a new clean hash based on the parameters of the original one */
 327   hash->items=          items;
 328   shared->total_items = n_items;
 329   shared->items=        shared_items;
 330   set_hash_parameters(hash, hash->maximum_load);
 331   copy_hash_items(hash, old_items, old_n_items);
 332
 333   hash->free_mem(old_shared_items);
 334   hash->last_ptr_update= ++shared->ptr_updates;
 335 }
 336
 337 /* low level: attach hash existing hash items, no checks are performed
 338  * No complex calculations done.
 339  */
 340 static HASH_CONTAINER *attach_no_check(HASH_ITEM *items, int bytes_per_datum)
 341 {
 342     HASH_CONTAINER *hash;
 343     int bytes_per_item;
 344     HASH_ITEM dummy_item;
 345
 346     hash= (HASH_CONTAINER*) malloc(sizeof(HASH_CONTAINER) );
 347     if (hash == NULL)
 348         return NULL;
 349
 350     bytes_per_item= bytes_per_datum+
 351                     sizeof(dummy_item)-sizeof(dummy_item.data);
 352     hash->bytes_per_item= ROUND_UP4(bytes_per_item);
 353     hash->items=          items;
 354     hash->is_correct_item= NULL;
 355     hash->allocate_mem=   HASH_MEM_ALLOC;
 356     hash->access_mem=     HASH_MEM_ACCESS;
 357     hash->free_mem=       HASH_MEM_FREE;
 358     set_hash_parameters(hash, HASH_LOAD);
 359
 360
 361     return hash;
 362 }
 363
 364
 365 /* Attach existing & running remote (i.e. shared) hash.
 366  * Attach the items using the data stored in "shared"
 367  */
 368 HASH_CONTAINER *attach_remote_hash(HASH_SHARED *shared, int bytes_per_datum,
 369                                    HASH_ITEM *(*access_mem)(HASH_PTR))
 370 {
 371     HASH_CONTAINER *hash;
 372     HASH_ITEM *items;
 373
 374     assert(access_mem != NULL);
 375     if (! arrays_initialized)
 376         setup_arrays();
 377
 378     items=access_mem(shared->items);
 379     hash= attach_no_check(items, bytes_per_datum);
 380     if (hash == NULL)
 381         return NULL;
 382
 383     hash->shared_was_malloced = FALSE;
 384     hash->shared= shared;
 385     return (hash);
 386 }
 387
 388
 389 HASH_CONTAINER *create_remote_hash(HASH_SHARED *shared,
 390                                    int bytes_per_datum,
 391                                    int total_items,
 392                                    HASH_PTR (*allocate_mem)(int size),
 393                                    HASH_ITEM *(*access_mem)(HASH_PTR))
 394 {
 395    HASH_CONTAINER *hash;
 396    int size;
 397    int i;
 398
 399    assert(total_items >= 1);
 400    assert(bytes_per_datum >=1);
 401    assert(access_mem != NULL);
 402    assert(allocate_mem != NULL);
 403    assert(shared != NULL);
 404    if (! arrays_initialized)
 405       setup_arrays();
 406
 407    if (total_items < MIN_HASH)
 408       total_items= MIN_HASH;
 409    else
 410       total_items= best_prime(total_items);
 411
 412    hash= attach_no_check(NULL, bytes_per_datum);
 413
 414    if (hash==NULL) {
 415       free(hash);
 416       return NULL;
 417    }
 418
 419    shared->total_items=  total_items;
 420    hash->shared= shared;
 421    hash->shared_was_malloced = FALSE;
 422
 423    size= total_items * hash->bytes_per_item;
 424
 425    shared->items = allocate_mem(size);
 426    hash->items=    access_mem(shared->items);
 427
 428    if (hash->items == NULL ) {
 429       free(hash);
 430       return NULL;
 431    }
 432    shared->items.ptr= hash->items;
 433
 434    /* make all items free */
 435    for (i=0 ; i < total_items ; i++)
 436       GET_ITEM(hash->items,hash->bytes_per_item,i).key = FREE_ENTRY;
 437
 438    shared->deleted_items= 0;
 439    shared->free_items= total_items;
 440    shared->ptr_updates= 0;
 441    return hash;
 442
 443 }
 444
 445 /* hash constructor: create brand new hash */
 446 HASH_CONTAINER *create_hash(int bytes_per_datum, int total_items)
 447 {
 448    HASH_CONTAINER *hash;
 449    HASH_SHARED *shared;
 450
 451
 452    shared= (HASH_SHARED*)malloc(sizeof(HASH_SHARED));
 453    if (shared == NULL)
 454       return NULL;
 455
 456    hash= create_remote_hash(shared, bytes_per_datum, total_items,
 457                             HASH_MEM_ALLOC, HASH_MEM_ACCESS);
 458
 459    if (hash == NULL) {
 460       free(shared);
 461       return NULL;
 462    }
 463
 464    hash->shared_was_malloced = TRUE;
 465    return hash;
 466 }
 467
 468 /* set the extra handlers to non default values */
 469 void set_hash_handlers(HASH_CONTAINER *hash,
 470                        HASH_ITEM_TEST *is_correct_item,
 471                        HASH_PTR (*allocate_mem)(int size),
 472                        void     (*free_mem)(HASH_PTR),
 473                        HASH_ITEM *(*access_mem)(HASH_PTR))
 474 {
 475    assert(hash);
 476    assert(allocate_mem);
 477    assert(free_mem);
 478
 479    hash->free_mem     = free_mem;
 480    hash->allocate_mem = allocate_mem;
 481    hash->access_mem   = access_mem;
 482    hash->is_correct_item = is_correct_item;
 483 }
 484
 485
 486 /* set extra parameters */
 487 void set_hash_parameters(HASH_CONTAINER *hash, int load)
 488 {
 489    assert(hash);
 490    assert(load>30);             /* no sence to realloc with less than */
 491                                 /* 50% load, limiting to 30% to be on */
 492                                 /* the safe size */
 493    assert(load<=100);
 494
 495    hash->maximum_load=   load;
 496    hash->min_free_items= (1.0 - load/100.0) * hash->shared->total_items + 1 ;
 497 }
 498
 499 /* hash destructor: destroy anything related to the hash */
 500 void destroy_hash(HASH_CONTAINER *hash)
 501 {
 502    assert(hash);
 503    hash->free_mem(hash->shared->items);
 504    if (hash->shared_was_malloced)
 505       free(hash->shared);
 506    free(hash);
 507 }
 508
 509 /* hash destructor: just detach hash, without destroing it (makes */
 510 /* sence in shared memory environment) */
 511 void detach_hash(HASH_CONTAINER *hash)
 512 {
 513    assert(hash);
 514    free(hash);
 515 }
 516
 517
 518 /********** Hash usage *************/
 519 static __inline__ BOOL32
 520 correct_entry(HASH_ITEM *item, int key, HASH_VAL *seeked_data,
 521               HASH_ITEM_TEST *is_correct_item, BOOL32 skip_deleted)
 522 {
 523    switch(item->key) {
 524       case FREE_ENTRY:
 525          return TRUE;
 526
 527       case DELETED_ENTRY:
 528          return skip_deleted ? FALSE : TRUE;
 529
 530       default:
 531          if (item->key != key)
 532             return FALSE;
 533          if (is_correct_item != NULL)
 534             return is_correct_item(&item->data, seeked_data);
 535          else
 536             return TRUE;
 537    }
 538
 539 }
 540
 541 /* The algorithm of the hash (one of the 2 standard hash implementations):
 542  *   Iterate through the hash table until
 543  *    1. The entry has been found.
 544  *    2. A FREE entry has been found.
 545  *    3. For insert operations only- A DELETED entry has been found.
 546  *       The difference between DELETED and FREE entires is that
 547  *       DELETED entry was one occupied, while FREE was never allocated.
 548  *       The idea behind this structure to keep other entries reachable.
 549  */
 550
 551 static HASH_ITEM *locate_entry(HASH_CONTAINER* hash, DWORD key,
 552                                HASH_VAL *seeked_data, BOOL32 skip_deleted)
 553 {
 554    DWORD hash_idx, hash_leaps;
 555    HASH_ITEM *item;
 556    int i;
 557    int total_items;
 558
 559    assert(hash);
 560
 561    total_items=     hash->shared->total_items;
 562    hash_idx=        key % total_items;
 563
 564    item= &GET_ITEM(hash->items, hash->bytes_per_item, hash_idx);
 565
 566    if (  correct_entry( item, key, seeked_data,
 567                         hash->is_correct_item, skip_deleted)   )
 568       return item;
 569
 570    /* get the WORDs in different order in this DWORD to avoid clustering */
 571    hash_leaps=((DWORD)MAKELONG(HIWORD(key), LOWORD(key))
 572                % (total_items-1)) +1;
 573
 574    /* interate through the hash table using hash_leaps */
 575    for (i= total_items ; i ; i--) {
 576       hash_idx+= hash_leaps;
 577       if (hash_idx > total_items)
 578          hash_idx -= total_items;
 579
 580       item= &GET_ITEM(hash->items,hash->bytes_per_item, hash_idx);
 581       if (  correct_entry( item, key, seeked_data,
 582                            hash->is_correct_item, skip_deleted)   )
 583          return item;
 584    }
 585    return NULL;
 586
 587 }
 588
 589 static __inline__ void sync_shared_hash(HASH_CONTAINER *hash)
 590 {
 591     HASH_SHARED *shared= hash->shared;
 592
 593     if (shared->ptr_updates == hash->last_ptr_update)
 594         return;
 595
 596     assert(shared->ptr_updates >= hash->last_ptr_update);
 597     hash->last_ptr_update= shared->ptr_updates;
 598     hash->min_free_items= (1.0 - hash->maximum_load/100.0) *
 599         shared->total_items + 1 ;
 600
 601     hash->items= hash->access_mem(shared->items);
 602 }
 603
 604 HASH_VAL *hash_locate_item(HASH_CONTAINER* hash,
 605                            int key, HASH_VAL *seeked_data)
 606 {
 607     HASH_ITEM *item;
 608
 609     assert(hash != NULL);
 610     sync_shared_hash(hash);
 611
 612     item= locate_entry(hash, key, seeked_data, 1 /* skip_deleted */);
 613     if (item == NULL)
 614         return NULL;
 615     if (item->key == FREE_ENTRY )
 616         return NULL;
 617
 618     return &item->data;
 619 }
 620
 621
 622 BOOL32 hash_add_item(HASH_CONTAINER* hash, int key, HASH_VAL *data)
 623 {
 624     HASH_SHARED *shared;
 625     HASH_ITEM *item;
 626
 627     assert(hash != NULL);
 628
 629     sync_shared_hash(hash);
 630     shared= hash->shared;
 631
 632     item=locate_entry(hash, key, data, 0 /* no skip_deleted */);
 633     assert(item != NULL);
 634     if (item->key == key)
 635         return FALSE;
 636     if (item->key == FREE_ENTRY)
 637        shared->free_items--;
 638     else
 639        shared->deleted_items--;
 640
 641     item->key=  key;
 642     memcpy(&item->data, data, hash->bytes_per_item-sizeof(key));
 643
 644     if (shared->free_items < hash->min_free_items ||
 645         shared->deleted_items > hash->min_free_items)
 646        reorder_hash(hash);
 647
 648     return TRUE;
 649 }
 650
 651
 652 BOOL32 hash_delete_item(HASH_CONTAINER* hash, int key, HASH_VAL *seeked_data)
 653 {
 654     HASH_ITEM *item;
 655
 656     assert(hash != NULL);
 657     sync_shared_hash(hash);
 658
 659     item=locate_entry(hash, key, seeked_data, 1 /* skip_deleted */);
 660     if (item == NULL)
 661         return FALSE;
 662
 663     if (item->key == FREE_ENTRY)
 664         return FALSE;
 665
 666     item->key = DELETED_ENTRY;
 667     hash->shared->deleted_items++;
 668
 669     return TRUE;
 670 }
 671
 672 void *ret_null()
 673 {
 674     return NULL;
 675 }
 676
 677
 678 HASH_ITEM *access_local_hash(HASH_PTR ptr)
 679 {
 680    return ptr.ptr;
 681 }
 682
 683 #endif  /* CONFIG_IPC */