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