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