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 "pipe/p_debug.h"
  34 #include "pipe/p_util.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    node->key = akey;
 114    node->value = avalue;
 115
 116    node->next = (struct cso_node*)(*anextNode);
 117    *anextNode = node;
 118    ++hash->data.d->size;
 119    return node;
 120 }
 121
 122 static void cso_data_rehash(struct cso_hash_data *hash, int hint)
 123 {
 124    if (hint < 0) {
 125       hint = countBits(-hint);
 126       if (hint < MinNumBits)
 127          hint = MinNumBits;
 128       hash->userNumBits = (short)hint;
 129       while (primeForNumBits(hint) < (hash->size >> 1))
 130          ++hint;
 131    } else if (hint < MinNumBits) {
 132       hint = MinNumBits;
 133    }
 134
 135    if (hash->numBits != hint) {
 136       struct cso_node *e = (struct cso_node *)(hash);
 137       struct cso_node **oldBuckets = hash->buckets;
 138       int oldNumBuckets = hash->numBuckets;
 139       int  i = 0;
 140
 141       hash->numBits = (short)hint;
 142       hash->numBuckets = primeForNumBits(hint);
 143       hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets);
 144       for (i = 0; i < hash->numBuckets; ++i)
 145          hash->buckets[i] = e;
 146
 147       for (i = 0; i < oldNumBuckets; ++i) {
 148          struct cso_node *firstNode = oldBuckets[i];
 149          while (firstNode != e) {
 150             unsigned h = firstNode->key;
 151             struct cso_node *lastNode = firstNode;
 152             struct cso_node *afterLastNode;
 153             struct cso_node **beforeFirstNode;
 154
 155             while (lastNode->next != e && lastNode->next->key == h)
 156                lastNode = lastNode->next;
 157
 158             afterLastNode = lastNode->next;
 159             beforeFirstNode = &hash->buckets[h % hash->numBuckets];
 160             while (*beforeFirstNode != e)
 161                beforeFirstNode = &(*beforeFirstNode)->next;
 162             lastNode->next = *beforeFirstNode;
 163             *beforeFirstNode = firstNode;
 164             firstNode = afterLastNode;
 165          }
 166       }
 167       FREE(oldBuckets);
 168    }
 169 }
 170
 171 static void cso_data_might_grow(struct cso_hash_data *hash)
 172 {
 173    if (hash->size >= hash->numBuckets)
 174       cso_data_rehash(hash, hash->numBits + 1);
 175 }
 176
 177 static void cso_data_has_shrunk(struct cso_hash_data *hash)
 178 {
 179    if (hash->size <= (hash->numBuckets >> 3) &&
 180        hash->numBits > hash->userNumBits) {
 181       int max = MAX(hash->numBits-2, hash->userNumBits);
 182       cso_data_rehash(hash,  max);
 183    }
 184 }
 185
 186 static struct cso_node *cso_data_first_node(struct cso_hash_data *hash)
 187 {
 188    struct cso_node *e = (struct cso_node *)(hash);
 189    struct cso_node **bucket = hash->buckets;
 190    int n = hash->numBuckets;
 191    while (n--) {
 192       if (*bucket != e)
 193          return *bucket;
 194       ++bucket;
 195    }
 196    return e;
 197 }
 198
 199 static struct cso_node **cso_hash_find_node(struct cso_hash *hash, unsigned akey)
 200 {
 201    struct cso_node **node;
 202
 203    if (hash->data.d->numBuckets) {
 204       node = (struct cso_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]);
 205       assert(*node == hash->data.e || (*node)->next);
 206       while (*node != hash->data.e && (*node)->key != akey)
 207          node = &(*node)->next;
 208    } else {
 209       node = (struct cso_node **)((const struct cso_node * const *)(&hash->data.e));
 210    }
 211    return node;
 212 }
 213
 214 struct cso_hash_iter cso_hash_insert(struct cso_hash *hash,
 215                                        unsigned key, void *data)
 216 {
 217    cso_data_might_grow(hash->data.d);
 218
 219    {
 220       struct cso_node **nextNode = cso_hash_find_node(hash, key);
 221       struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode);
 222       struct cso_hash_iter iter = {hash, node};
 223       return iter;
 224    }
 225 }
 226
 227 struct cso_hash * cso_hash_create(void)
 228 {
 229    struct cso_hash *hash = MALLOC_STRUCT(cso_hash);
 230    hash->data.d = MALLOC_STRUCT(cso_hash_data);
 231    hash->data.d->fakeNext = 0;
 232    hash->data.d->buckets = 0;
 233    hash->data.d->size = 0;
 234    hash->data.d->nodeSize = sizeof(struct cso_node);
 235    hash->data.d->userNumBits = (short)MinNumBits;
 236    hash->data.d->numBits = 0;
 237    hash->data.d->numBuckets = 0;
 238
 239    return hash;
 240 }
 241
 242 void cso_hash_delete(struct cso_hash *hash)
 243 {
 244    struct cso_node *e_for_x = (struct cso_node *)(hash->data.d);
 245    struct cso_node **bucket = (struct cso_node **)(hash->data.d->buckets);
 246    int n = hash->data.d->numBuckets;
 247    while (n--) {
 248       struct cso_node *cur = *bucket++;
 249       while (cur != e_for_x) {
 250          struct cso_node *next = cur->next;
 251          cso_free_node(cur);
 252          cur = next;
 253       }
 254    }
 255    FREE(hash->data.d->buckets);
 256    FREE(hash->data.d);
 257    FREE(hash);
 258 }
 259
 260 struct cso_hash_iter cso_hash_find(struct cso_hash *hash,
 261                                      unsigned key)
 262 {
 263    struct cso_node **nextNode = cso_hash_find_node(hash, key);
 264    struct cso_hash_iter iter = {hash, *nextNode};
 265    return iter;
 266 }
 267
 268 unsigned cso_hash_iter_key(struct cso_hash_iter iter)
 269 {
 270    if (!iter.node || iter.hash->data.e == iter.node)
 271       return 0;
 272    return iter.node->key;
 273 }
 274
 275 void * cso_hash_iter_data(struct cso_hash_iter iter)
 276 {
 277    if (!iter.node || iter.hash->data.e == iter.node)
 278       return 0;
 279    return iter.node->value;
 280 }
 281
 282 static struct cso_node *cso_hash_data_next(struct cso_node *node)
 283 {
 284    union {
 285       struct cso_node *next;
 286       struct cso_node *e;
 287       struct cso_hash_data *d;
 288    } a;
 289    int start;
 290    struct cso_node **bucket;
 291    int n;
 292
 293    a.next = node->next;
 294    if (!a.next) {
 295       debug_printf("iterating beyond the last element\n");
 296       return 0;
 297    }
 298    if (a.next->next)
 299       return a.next;
 300
 301    start = (node->key % a.d->numBuckets) + 1;
 302    bucket = a.d->buckets + start;
 303    n = a.d->numBuckets - start;
 304    while (n--) {
 305       if (*bucket != a.e)
 306          return *bucket;
 307       ++bucket;
 308    }
 309    return a.e;
 310 }
 311
 312
 313 static struct cso_node *cso_hash_data_prev(struct cso_node *node)
 314 {
 315    union {
 316       struct cso_node *e;
 317       struct cso_hash_data *d;
 318    } a;
 319    int start;
 320    struct cso_node *sentinel;
 321    struct cso_node **bucket;
 322
 323    a.e = node;
 324    while (a.e->next)
 325       a.e = a.e->next;
 326
 327    if (node == a.e)
 328       start = a.d->numBuckets - 1;
 329    else
 330       start = node->key % a.d->numBuckets;
 331
 332    sentinel = node;
 333    bucket = a.d->buckets + start;
 334    while (start >= 0) {
 335       if (*bucket != sentinel) {
 336          struct cso_node *prev = *bucket;
 337          while (prev->next != sentinel)
 338             prev = prev->next;
 339          return prev;
 340       }
 341
 342       sentinel = a.e;
 343       --bucket;
 344       --start;
 345    }
 346    debug_printf("iterating backward beyond first element\n");
 347    return a.e;
 348 }
 349
 350 struct cso_hash_iter cso_hash_iter_next(struct cso_hash_iter iter)
 351 {
 352    struct cso_hash_iter next = {iter.hash, cso_hash_data_next(iter.node)};
 353    return next;
 354 }
 355
 356 int cso_hash_iter_is_null(struct cso_hash_iter iter)
 357 {
 358    if (!iter.node || iter.node == iter.hash->data.e)
 359       return 1;
 360    return 0;
 361 }
 362
 363 void * cso_hash_take(struct cso_hash *hash,
 364                       unsigned akey)
 365 {
 366    struct cso_node **node = cso_hash_find_node(hash, akey);
 367    if (*node != hash->data.e) {
 368       void *t = (*node)->value;
 369       struct cso_node *next = (*node)->next;
 370       cso_free_node(*node);
 371       *node = next;
 372       --hash->data.d->size;
 373       cso_data_has_shrunk(hash->data.d);
 374       return t;
 375    }
 376    return 0;
 377 }
 378
 379 struct cso_hash_iter cso_hash_iter_prev(struct cso_hash_iter iter)
 380 {
 381    struct cso_hash_iter prev = {iter.hash,
 382                                  cso_hash_data_prev(iter.node)};
 383    return prev;
 384 }
 385
 386 struct cso_hash_iter cso_hash_first_node(struct cso_hash *hash)
 387 {
 388    struct cso_hash_iter iter = {hash, cso_data_first_node(hash->data.d)};
 389    return iter;
 390 }
 391
 392 int cso_hash_size(struct cso_hash *hash)
 393 {
 394    return hash->data.d->size;
 395 }
 396
 397 struct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter)
 398 {
 399    struct cso_hash_iter ret = iter;
 400    struct cso_node *node = iter.node;
 401    struct cso_node **node_ptr;
 402
 403    if (node == hash->data.e)
 404       return iter;
 405
 406    ret = cso_hash_iter_next(ret);
 407    node_ptr = (struct cso_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]);
 408    while (*node_ptr != node)
 409       node_ptr = &(*node_ptr)->next;
 410    *node_ptr = node->next;
 411    cso_free_node(node);
 412    --hash->data.d->size;
 413    return ret;
 414 }