src/gallium/auxiliary/cso_cache/cso_hash.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2007 Tungsten Graphics, Inc., Cedar Park, Texas.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  21  * IN NO EVENT SHALL TUNGSTEN GRAPHICS AND/OR ITS SUPPLIERS BE LIABLE FOR
  22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  **************************************************************************/
  27
  28  /*
  29   * Authors:
  30   *   Zack Rusin <zack@tungstengraphics.com>
  31   */
  32
  33 #include "util/u_debug.h"
  34 #include "util/u_memory.h"
  35
  36 #include "cso_hash.h"
  37
  38 #define MAX(a, b) ((a > b) ? (a) : (b))
  39
  40 static const int MinNumBits = 4;
  41
  42 static const unsigned char prime_deltas[] = {
  43    0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
  44    1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
  45 };
  46
  47 static int primeForNumBits(int numBits)
  48 {
  49    return (1 << numBits) + prime_deltas[numBits];
  50 }
  51
  52 /*
  53     Returns the smallest integer n such that
  54     primeForNumBits(n) >= hint.
  55 */
  56 static int countBits(int hint)
  57 {
  58    int numBits = 0;
  59    int bits = hint;
  60
  61    while (bits > 1) {
  62       bits >>= 1;
  63       numBits++;
  64    }
  65
  66    if (numBits >= (int)sizeof(prime_deltas)) {
  67       numBits = sizeof(prime_deltas) - 1;
  68    } else if (primeForNumBits(numBits) < hint) {
  69       ++numBits;
  70    }
  71    return numBits;
  72 }
  73
  74 struct cso_node {
  75    struct cso_node *next;
  76    unsigned key;
  77    void *value;
  78 };
  79
  80 struct cso_hash_data {
  81    struct cso_node *fakeNext;
  82    struct cso_node **buckets;
  83    int size;
  84    int nodeSize;
  85    short userNumBits;
  86    short numBits;
  87    int numBuckets;
  88 };
  89
  90 struct cso_hash {
  91    union {
  92       struct cso_hash_data *d;
  93       struct cso_node      *e;
  94    } data;
  95 };
  96
  97 static void *cso_data_allocate_node(struct cso_hash_data *hash)
  98 {
  99    return MALLOC(hash->nodeSize);
 100 }
 101
 102 static void cso_free_node(struct cso_node *node)
 103 {
 104    FREE(node);
 105 }
 106
 107 static struct cso_node *
 108 cso_hash_create_node(struct cso_hash *hash,
 109                       unsigned akey, void *avalue,
 110                       struct cso_node **anextNode)
 111 {
 112    struct cso_node *node = cso_data_allocate_node(hash->data.d);
 113
 114    if (!node)
 115       return NULL;
 116
 117    node->key = akey;
 118    node->value = avalue;
 119
 120    node->next = (struct cso_node*)(*anextNode);
 121    *anextNode = node;
 122    ++hash->data.d->size;
 123    return node;
 124 }
 125
 126 static void cso_data_rehash(struct cso_hash_data *hash, int hint)
 127 {
 128    if (hint < 0) {
 129       hint = countBits(-hint);
 130       if (hint < MinNumBits)
 131          hint = MinNumBits;
 132       hash->userNumBits = (short)hint;
 133       while (primeForNumBits(hint) < (hash->size >> 1))
 134          ++hint;
 135    } else if (hint < MinNumBits) {
 136       hint = MinNumBits;
 137    }
 138
 139    if (hash->numBits != hint) {
 140       struct cso_node *e = (struct cso_node *)(hash);
 141       struct cso_node **oldBuckets = hash->buckets;
 142       int oldNumBuckets = hash->numBuckets;
 143       int  i = 0;
 144
 145       hash->numBits = (short)hint;
 146       hash->numBuckets = primeForNumBits(hint);
 147       hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets);
 148       for (i = 0; i < hash->numBuckets; ++i)
 149          hash->buckets[i] = e;
 150
 151       for (i = 0; i < oldNumBuckets; ++i) {
 152          struct cso_node *firstNode = oldBuckets[i];
 153          while (firstNode != e) {
 154             unsigned h = firstNode->key;
 155             struct cso_node *lastNode = firstNode;
 156             struct cso_node *afterLastNode;
 157             struct cso_node **beforeFirstNode;
 158
 159             while (lastNode->next != e && lastNode->next->key == h)
 160                lastNode = lastNode->next;
 161
 162             afterLastNode = lastNode->next;
 163             beforeFirstNode = &hash->buckets[h % hash->numBuckets];
 164             while (*beforeFirstNode != e)
 165                beforeFirstNode = &(*beforeFirstNode)->next;
 166             lastNode->next = *beforeFirstNode;
 167             *beforeFirstNode = firstNode;
 168             firstNode = afterLastNode;
 169          }
 170       }
 171       FREE(oldBuckets);
 172    }
 173 }
 174
 175 static void cso_data_might_grow(struct cso_hash_data *hash)
 176 {
 177    if (hash->size >= hash->numBuckets)
 178       cso_data_rehash(hash, hash->numBits + 1);
 179 }
 180
 181 static void cso_data_has_shrunk(struct cso_hash_data *hash)
 182 {
 183    if (hash->size <= (hash->numBuckets >> 3) &&
 184        hash->numBits > hash->userNumBits) {
 185       int max = MAX(hash->numBits-2, hash->userNumBits);
 186       cso_data_rehash(hash,  max);
 187    }
 188 }
 189
 190 static struct cso_node *cso_data_first_node(struct cso_hash_data *hash)
 191 {
 192    struct cso_node *e = (struct cso_node *)(hash);
 193    struct cso_node **bucket = hash->buckets;
 194    int n = hash->numBuckets;
 195    while (n--) {
 196       if (*bucket != e)
 197          return *bucket;
 198       ++bucket;
 199    }
 200    return e;
 201 }
 202
 203 static struct cso_node **cso_hash_find_node(struct cso_hash *hash, unsigned akey)
 204 {
 205    struct cso_node **node;
 206
 207    if (hash->data.d->numBuckets) {
 208       node = (struct cso_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]);
 209       assert(*node == hash->data.e || (*node)->next);
 210       while (*node != hash->data.e && (*node)->key != akey)
 211          node = &(*node)->next;
 212    } else {
 213       node = (struct cso_node **)((const struct cso_node * const *)(&hash->data.e));
 214    }
 215    return node;
 216 }
 217
 218 struct cso_hash_iter cso_hash_insert(struct cso_hash *hash,
 219                                        unsigned key, void *data)
 220 {
 221    cso_data_might_grow(hash->data.d);
 222
 223    {
 224       struct cso_node **nextNode = cso_hash_find_node(hash, key);
 225       struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode);
 226       if (!node) {
 227          struct cso_hash_iter null_iter = {hash, 0};
 228          return null_iter;
 229       }
 230
 231       {
 232          struct cso_hash_iter iter = {hash, node};
 233          return iter;
 234       }
 235    }
 236 }
 237
 238 struct cso_hash * cso_hash_create(void)
 239 {
 240    struct cso_hash *hash = MALLOC_STRUCT(cso_hash);
 241    if (!hash)
 242       return NULL;
 243
 244    hash->data.d = MALLOC_STRUCT(cso_hash_data);
 245    if (!hash->data.d) {
 246       FREE(hash);
 247       return NULL;
 248    }
 249
 250    hash->data.d->fakeNext = 0;
 251    hash->data.d->buckets = 0;
 252    hash->data.d->size = 0;
 253    hash->data.d->nodeSize = sizeof(struct cso_node);
 254    hash->data.d->userNumBits = (short)MinNumBits;
 255    hash->data.d->numBits = 0;
 256    hash->data.d->numBuckets = 0;
 257
 258    return hash;
 259 }
 260
 261 void cso_hash_delete(struct cso_hash *hash)
 262 {
 263    struct cso_node *e_for_x = (struct cso_node *)(hash->data.d);
 264    struct cso_node **bucket = (struct cso_node **)(hash->data.d->buckets);
 265    int n = hash->data.d->numBuckets;
 266    while (n--) {
 267       struct cso_node *cur = *bucket++;
 268       while (cur != e_for_x) {
 269          struct cso_node *next = cur->next;
 270          cso_free_node(cur);
 271          cur = next;
 272       }
 273    }
 274    FREE(hash->data.d->buckets);
 275    FREE(hash->data.d);
 276    FREE(hash);
 277 }
 278
 279 struct cso_hash_iter cso_hash_find(struct cso_hash *hash,
 280                                      unsigned key)
 281 {
 282    struct cso_node **nextNode = cso_hash_find_node(hash, key);
 283    struct cso_hash_iter iter = {hash, *nextNode};
 284    return iter;
 285 }
 286
 287 unsigned cso_hash_iter_key(struct cso_hash_iter iter)
 288 {
 289    if (!iter.node || iter.hash->data.e == iter.node)
 290       return 0;
 291    return iter.node->key;
 292 }
 293
 294 void * cso_hash_iter_data(struct cso_hash_iter iter)
 295 {
 296    if (!iter.node || iter.hash->data.e == iter.node)
 297       return 0;
 298    return iter.node->value;
 299 }
 300
 301 static struct cso_node *cso_hash_data_next(struct cso_node *node)
 302 {
 303    union {
 304       struct cso_node *next;
 305       struct cso_node *e;
 306       struct cso_hash_data *d;
 307    } a;
 308    int start;
 309    struct cso_node **bucket;
 310    int n;
 311
 312    a.next = node->next;
 313    if (!a.next) {
 314       debug_printf("iterating beyond the last element\n");
 315       return 0;
 316    }
 317    if (a.next->next)
 318       return a.next;
 319
 320    start = (node->key % a.d->numBuckets) + 1;
 321    bucket = a.d->buckets + start;
 322    n = a.d->numBuckets - start;
 323    while (n--) {
 324       if (*bucket != a.e)
 325          return *bucket;
 326       ++bucket;
 327    }
 328    return a.e;
 329 }
 330
 331
 332 static struct cso_node *cso_hash_data_prev(struct cso_node *node)
 333 {
 334    union {
 335       struct cso_node *e;
 336       struct cso_hash_data *d;
 337    } a;
 338    int start;
 339    struct cso_node *sentinel;
 340    struct cso_node **bucket;
 341
 342    a.e = node;
 343    while (a.e->next)
 344       a.e = a.e->next;
 345
 346    if (node == a.e)
 347       start = a.d->numBuckets - 1;
 348    else
 349       start = node->key % a.d->numBuckets;
 350
 351    sentinel = node;
 352    bucket = a.d->buckets + start;
 353    while (start >= 0) {
 354       if (*bucket != sentinel) {
 355          struct cso_node *prev = *bucket;
 356          while (prev->next != sentinel)
 357             prev = prev->next;
 358          return prev;
 359       }
 360
 361       sentinel = a.e;
 362       --bucket;
 363       --start;
 364    }
 365    debug_printf("iterating backward beyond first element\n");
 366    return a.e;
 367 }
 368
 369 struct cso_hash_iter cso_hash_iter_next(struct cso_hash_iter iter)
 370 {
 371    struct cso_hash_iter next = {iter.hash, cso_hash_data_next(iter.node)};
 372    return next;
 373 }
 374
 375 int cso_hash_iter_is_null(struct cso_hash_iter iter)
 376 {
 377    if (!iter.node || iter.node == iter.hash->data.e)
 378       return 1;
 379    return 0;
 380 }
 381
 382 void * cso_hash_take(struct cso_hash *hash,
 383                       unsigned akey)
 384 {
 385    struct cso_node **node = cso_hash_find_node(hash, akey);
 386    if (*node != hash->data.e) {
 387       void *t = (*node)->value;
 388       struct cso_node *next = (*node)->next;
 389       cso_free_node(*node);
 390       *node = next;
 391       --hash->data.d->size;
 392       cso_data_has_shrunk(hash->data.d);
 393       return t;
 394    }
 395    return 0;
 396 }
 397
 398 struct cso_hash_iter cso_hash_iter_prev(struct cso_hash_iter iter)
 399 {
 400    struct cso_hash_iter prev = {iter.hash,
 401                                  cso_hash_data_prev(iter.node)};
 402    return prev;
 403 }
 404
 405 struct cso_hash_iter cso_hash_first_node(struct cso_hash *hash)
 406 {
 407    struct cso_hash_iter iter = {hash, cso_data_first_node(hash->data.d)};
 408    return iter;
 409 }
 410
 411 int cso_hash_size(struct cso_hash *hash)
 412 {
 413    return hash->data.d->size;
 414 }
 415
 416 struct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter)
 417 {
 418    struct cso_hash_iter ret = iter;
 419    struct cso_node *node = iter.node;
 420    struct cso_node **node_ptr;
 421
 422    if (node == hash->data.e)
 423       return iter;
 424
 425    ret = cso_hash_iter_next(ret);
 426    node_ptr = (struct cso_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]);
 427    while (*node_ptr != node)
 428       node_ptr = &(*node_ptr)->next;
 429    *node_ptr = node->next;
 430    cso_free_node(node);
 431    --hash->data.d->size;
 432    return ret;
 433 }
 434
 435 boolean cso_hash_contains(struct cso_hash *hash, unsigned key)
 436 {
 437    struct cso_node **node = cso_hash_find_node(hash, key);
 438    return (*node != hash->data.e);
 439 }