amdgpu/util_hash.c

   1 /**************************************************************************
   2  *
   3  * Copyright 2007 VMware, Inc.
   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 VMWARE 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 <zackr@vmware.com>
  31   */
  32
  33 #ifdef HAVE_CONFIG_H
  34 #include "config.h"
  35 #endif
  36
  37 #include "util_hash.h"
  38
  39 #include <stdlib.h>
  40 #include <assert.h>
  41
  42 #define MAX(a, b) ((a > b) ? (a) : (b))
  43
  44 static const int MinNumBits = 4;
  45
  46 static const unsigned char prime_deltas[] = {
  47         0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
  48         1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
  49 };
  50
  51 static int primeForNumBits(int numBits)
  52 {
  53         return (1 << numBits) + prime_deltas[numBits];
  54 }
  55
  56 /* Returns the smallest integer n such that
  57    primeForNumBits(n) >= hint.
  58 */
  59 static int countBits(int hint)
  60 {
  61         int numBits = 0;
  62         int bits = hint;
  63
  64         while (bits > 1) {
  65                 bits >>= 1;
  66                 numBits++;
  67         }
  68
  69         if (numBits >= (int)sizeof(prime_deltas)) {
  70                 numBits = sizeof(prime_deltas) - 1;
  71         } else if (primeForNumBits(numBits) < hint) {
  72                 ++numBits;
  73         }
  74         return numBits;
  75 }
  76
  77 struct util_node {
  78    struct util_node *next;
  79    unsigned key;
  80    void *value;
  81 };
  82
  83 struct util_hash_data {
  84    struct util_node *fakeNext;
  85    struct util_node **buckets;
  86    int size;
  87    int nodeSize;
  88    short userNumBits;
  89    short numBits;
  90    int numBuckets;
  91 };
  92
  93 struct util_hash {
  94    union {
  95       struct util_hash_data *d;
  96       struct util_node      *e;
  97    } data;
  98 };
  99
 100 static void *util_data_allocate_node(struct util_hash_data *hash)
 101 {
 102    return malloc(hash->nodeSize);
 103 }
 104
 105 static void util_free_node(struct util_node *node)
 106 {
 107    free(node);
 108 }
 109
 110 static struct util_node *
 111 util_hash_create_node(struct util_hash *hash,
 112                       unsigned akey, void *avalue,
 113                       struct util_node **anextNode)
 114 {
 115    struct util_node *node = util_data_allocate_node(hash->data.d);
 116
 117    if (!node)
 118       return NULL;
 119
 120    node->key = akey;
 121    node->value = avalue;
 122
 123    node->next = (struct util_node*)(*anextNode);
 124    *anextNode = node;
 125    ++hash->data.d->size;
 126    return node;
 127 }
 128
 129 static void util_data_rehash(struct util_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 util_node *e = (struct util_node *)(hash);
 144       struct util_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 util_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 util_node *firstNode = oldBuckets[i];
 156          while (firstNode != e) {
 157             unsigned h = firstNode->key;
 158             struct util_node *lastNode = firstNode;
 159             struct util_node *afterLastNode;
 160             struct util_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 util_data_might_grow(struct util_hash_data *hash)
 179 {
 180    if (hash->size >= hash->numBuckets)
 181       util_data_rehash(hash, hash->numBits + 1);
 182 }
 183
 184 static void util_data_has_shrunk(struct util_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       util_data_rehash(hash,  max);
 190    }
 191 }
 192
 193 static struct util_node *util_data_first_node(struct util_hash_data *hash)
 194 {
 195    struct util_node *e = (struct util_node *)(hash);
 196    struct util_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 util_node **util_hash_find_node(struct util_hash *hash, unsigned akey)
 207 {
 208    struct util_node **node;
 209
 210    if (hash->data.d->numBuckets) {
 211       node = (struct util_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 util_node **)((const struct util_node * const *)(&hash->data.e));
 217    }
 218    return node;
 219 }
 220
 221 drm_private struct util_hash_iter
 222 util_hash_insert(struct util_hash *hash, unsigned key, void *data)
 223 {
 224    util_data_might_grow(hash->data.d);
 225
 226    {
 227       struct util_node **nextNode = util_hash_find_node(hash, key);
 228       struct util_node *node = util_hash_create_node(hash, key, data, nextNode);
 229       if (!node) {
 230          struct util_hash_iter null_iter = {hash, 0};
 231          return null_iter;
 232       }
 233
 234       {
 235          struct util_hash_iter iter = {hash, node};
 236          return iter;
 237       }
 238    }
 239 }
 240
 241 drm_private struct util_hash *util_hash_create(void)
 242 {
 243    struct util_hash *hash = malloc(sizeof(struct util_hash));
 244    if (!hash)
 245       return NULL;
 246
 247    hash->data.d = malloc(sizeof(struct util_hash_data));
 248    if (!hash->data.d) {
 249       free(hash);
 250       return NULL;
 251    }
 252
 253    hash->data.d->fakeNext = 0;
 254    hash->data.d->buckets = 0;
 255    hash->data.d->size = 0;
 256    hash->data.d->nodeSize = sizeof(struct util_node);
 257    hash->data.d->userNumBits = (short)MinNumBits;
 258    hash->data.d->numBits = 0;
 259    hash->data.d->numBuckets = 0;
 260
 261    return hash;
 262 }
 263
 264 drm_private void util_hash_delete(struct util_hash *hash)
 265 {
 266    struct util_node *e_for_x = (struct util_node *)(hash->data.d);
 267    struct util_node **bucket = (struct util_node **)(hash->data.d->buckets);
 268    int n = hash->data.d->numBuckets;
 269    while (n--) {
 270       struct util_node *cur = *bucket++;
 271       while (cur != e_for_x) {
 272          struct util_node *next = cur->next;
 273          util_free_node(cur);
 274          cur = next;
 275       }
 276    }
 277    free(hash->data.d->buckets);
 278    free(hash->data.d);
 279    free(hash);
 280 }
 281
 282 drm_private struct util_hash_iter
 283 util_hash_find(struct util_hash *hash, unsigned key)
 284 {
 285    struct util_node **nextNode = util_hash_find_node(hash, key);
 286    struct util_hash_iter iter = {hash, *nextNode};
 287    return iter;
 288 }
 289
 290 drm_private unsigned util_hash_iter_key(struct util_hash_iter iter)
 291 {
 292    if (!iter.node || iter.hash->data.e == iter.node)
 293       return 0;
 294    return iter.node->key;
 295 }
 296
 297 drm_private void *util_hash_iter_data(struct util_hash_iter iter)
 298 {
 299    if (!iter.node || iter.hash->data.e == iter.node)
 300       return 0;
 301    return iter.node->value;
 302 }
 303
 304 static struct util_node *util_hash_data_next(struct util_node *node)
 305 {
 306    union {
 307       struct util_node *next;
 308       struct util_node *e;
 309       struct util_hash_data *d;
 310    } a;
 311    int start;
 312    struct util_node **bucket;
 313    int n;
 314
 315    a.next = node->next;
 316    if (!a.next) {
 317       /* iterating beyond the last element */
 318       return 0;
 319    }
 320    if (a.next->next)
 321       return a.next;
 322
 323    start = (node->key % a.d->numBuckets) + 1;
 324    bucket = a.d->buckets + start;
 325    n = a.d->numBuckets - start;
 326    while (n--) {
 327       if (*bucket != a.e)
 328          return *bucket;
 329       ++bucket;
 330    }
 331    return a.e;
 332 }
 333
 334 drm_private struct util_hash_iter
 335 util_hash_iter_next(struct util_hash_iter iter)
 336 {
 337    struct util_hash_iter next = {iter.hash, util_hash_data_next(iter.node)};
 338    return next;
 339 }
 340
 341 drm_private int util_hash_iter_is_null(struct util_hash_iter iter)
 342 {
 343    if (!iter.node || iter.node == iter.hash->data.e)
 344       return 1;
 345    return 0;
 346 }
 347
 348 drm_private void *util_hash_take(struct util_hash *hash, unsigned akey)
 349 {
 350    struct util_node **node = util_hash_find_node(hash, akey);
 351    if (*node != hash->data.e) {
 352       void *t = (*node)->value;
 353       struct util_node *next = (*node)->next;
 354       util_free_node(*node);
 355       *node = next;
 356       --hash->data.d->size;
 357       util_data_has_shrunk(hash->data.d);
 358       return t;
 359    }
 360    return 0;
 361 }
 362
 363 drm_private struct util_hash_iter util_hash_first_node(struct util_hash *hash)
 364 {
 365    struct util_hash_iter iter = {hash, util_data_first_node(hash->data.d)};
 366    return iter;
 367 }
 368
 369 drm_private struct util_hash_iter
 370 util_hash_erase(struct util_hash *hash, struct util_hash_iter iter)
 371 {
 372    struct util_hash_iter ret = iter;
 373    struct util_node *node = iter.node;
 374    struct util_node **node_ptr;
 375
 376    if (node == hash->data.e)
 377       return iter;
 378
 379    ret = util_hash_iter_next(ret);
 380    node_ptr = (struct util_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]);
 381    while (*node_ptr != node)
 382       node_ptr = &(*node_ptr)->next;
 383    *node_ptr = node->next;
 384    util_free_node(node);
 385    --hash->data.d->size;
 386    return ret;
 387 }