"Fossies" - the Fresh Open Source Software Archive

Member "mesa-20.1.8/src/gallium/auxiliary/cso_cache/cso_hash.c" (16 Sep 2020, 8935 Bytes) of package /linux/misc/mesa-20.1.8.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "cso_hash.c" see the Fossies "Dox" file reference documentation.

    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 #include "util/u_debug.h"
   34 #include "util/u_memory.h"
   35 
   36 #include "cso_hash.h"
   37 
   38 #ifndef MAX
   39 #define MAX(a, b) ((a > b) ? (a) : (b))
   40 #endif
   41 
   42 static const int MinNumBits = 4;
   43 
   44 static const unsigned char prime_deltas[] = {
   45    0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
   46    1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
   47 };
   48 
   49 static int primeForNumBits(int numBits)
   50 {
   51    return (1 << numBits) + prime_deltas[numBits];
   52 }
   53 
   54 /*
   55     Returns the smallest integer n such that
   56     primeForNumBits(n) >= hint.
   57 */
   58 static int countBits(int hint)
   59 {
   60    int numBits = 0;
   61    int bits = hint;
   62 
   63    while (bits > 1) {
   64       bits >>= 1;
   65       numBits++;
   66    }
   67 
   68    if (numBits >= (int)sizeof(prime_deltas)) {
   69       numBits = sizeof(prime_deltas) - 1;
   70    } else if (primeForNumBits(numBits) < hint) {
   71       ++numBits;
   72    }
   73    return numBits;
   74 }
   75 
   76 static struct cso_node *
   77 cso_hash_create_node(struct cso_hash *hash,
   78                      unsigned akey, void *avalue,
   79                      struct cso_node **anextNode)
   80 {
   81    struct cso_node *node = MALLOC(sizeof(struct cso_node));
   82 
   83    if (!node)
   84       return NULL;
   85 
   86    node->key = akey;
   87    node->value = avalue;
   88 
   89    node->next = *anextNode;
   90    *anextNode = node;
   91    ++hash->size;
   92    return node;
   93 }
   94 
   95 static void cso_data_rehash(struct cso_hash *hash, int hint)
   96 {
   97    if (hint < 0) {
   98       hint = countBits(-hint);
   99       if (hint < MinNumBits)
  100          hint = MinNumBits;
  101       hash->userNumBits = (short)hint;
  102       while (primeForNumBits(hint) < (hash->size >> 1))
  103          ++hint;
  104    } else if (hint < MinNumBits) {
  105       hint = MinNumBits;
  106    }
  107 
  108    if (hash->numBits != hint) {
  109       struct cso_node *e = (struct cso_node *)hash;
  110       struct cso_node **oldBuckets = hash->buckets;
  111       int oldNumBuckets = hash->numBuckets;
  112       int  i = 0;
  113 
  114       hash->numBits = (short)hint;
  115       hash->numBuckets = primeForNumBits(hint);
  116       hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets);
  117       for (i = 0; i < hash->numBuckets; ++i)
  118          hash->buckets[i] = e;
  119 
  120       for (i = 0; i < oldNumBuckets; ++i) {
  121          struct cso_node *firstNode = oldBuckets[i];
  122          while (firstNode != e) {
  123             unsigned h = firstNode->key;
  124             struct cso_node *lastNode = firstNode;
  125             struct cso_node *afterLastNode;
  126             struct cso_node **beforeFirstNode;
  127             
  128             while (lastNode->next != e && lastNode->next->key == h)
  129                lastNode = lastNode->next;
  130 
  131             afterLastNode = lastNode->next;
  132             beforeFirstNode = &hash->buckets[h % hash->numBuckets];
  133             while (*beforeFirstNode != e)
  134                beforeFirstNode = &(*beforeFirstNode)->next;
  135             lastNode->next = *beforeFirstNode;
  136             *beforeFirstNode = firstNode;
  137             firstNode = afterLastNode;
  138          }
  139       }
  140       FREE(oldBuckets);
  141    }
  142 }
  143 
  144 static void cso_data_might_grow(struct cso_hash *hash)
  145 {
  146    if (hash->size >= hash->numBuckets)
  147       cso_data_rehash(hash, hash->numBits + 1);
  148 }
  149 
  150 static void cso_data_has_shrunk(struct cso_hash *hash)
  151 {
  152    if (hash->size <= (hash->numBuckets >> 3) &&
  153        hash->numBits > hash->userNumBits) {
  154       int max = MAX(hash->numBits-2, hash->userNumBits);
  155       cso_data_rehash(hash,  max);
  156    }
  157 }
  158 
  159 static struct cso_node *cso_data_first_node(struct cso_hash *hash)
  160 {
  161    struct cso_node *e = (struct cso_node *)hash;
  162    struct cso_node **bucket = hash->buckets;
  163    int n = hash->numBuckets;
  164 
  165    while (n--) {
  166       if (*bucket != e)
  167          return *bucket;
  168       ++bucket;
  169    }
  170    return e;
  171 }
  172 
  173 struct cso_hash_iter cso_hash_insert(struct cso_hash *hash,
  174                                      unsigned key, void *data)
  175 {
  176    cso_data_might_grow(hash);
  177 
  178    struct cso_node **nextNode = cso_hash_find_node(hash, key);
  179    struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode);
  180    if (!node) {
  181       struct cso_hash_iter null_iter = {hash, 0};
  182       return null_iter;
  183    }
  184 
  185    struct cso_hash_iter iter = {hash, node};
  186    return iter;
  187 }
  188 
  189 void cso_hash_init(struct cso_hash *hash)
  190 {
  191    hash->fakeNext = 0;
  192    hash->buckets = 0;
  193    hash->size = 0;
  194    hash->userNumBits = (short)MinNumBits;
  195    hash->numBits = 0;
  196    hash->numBuckets = 0;
  197    hash->end = (struct cso_node*)hash;
  198 }
  199 
  200 void cso_hash_deinit(struct cso_hash *hash)
  201 {
  202    struct cso_node *e_for_x = hash->end;
  203    struct cso_node **bucket = hash->buckets;
  204    int n = hash->numBuckets;
  205 
  206    while (n--) {
  207       struct cso_node *cur = *bucket++;
  208       while (cur != e_for_x) {
  209          struct cso_node *next = cur->next;
  210          FREE(cur);
  211          cur = next;
  212       }
  213    }
  214    FREE(hash->buckets);
  215 }
  216 
  217 unsigned cso_hash_iter_key(struct cso_hash_iter iter)
  218 {
  219    if (!iter.node || iter.hash->end == iter.node)
  220       return 0;
  221    return iter.node->key;
  222 }
  223 
  224 struct cso_node *cso_hash_data_next(struct cso_node *node)
  225 {
  226    union {
  227       struct cso_node *next;
  228       struct cso_node *e;
  229       struct cso_hash *d;
  230    } a;
  231    int start;
  232    struct cso_node **bucket;
  233    int n;
  234 
  235    a.next = node->next;
  236    if (!a.next) {
  237       debug_printf("iterating beyond the last element\n");
  238       return NULL;
  239    }
  240    if (a.next->next)
  241       return a.next;
  242 
  243    start = (node->key % a.d->numBuckets) + 1;
  244    bucket = a.d->buckets + start;
  245    n = a.d->numBuckets - start;
  246    while (n--) {
  247       if (*bucket != a.e)
  248          return *bucket;
  249       ++bucket;
  250    }
  251    return a.e;
  252 }
  253 
  254 
  255 static struct cso_node *cso_hash_data_prev(struct cso_node *node)
  256 {
  257    union {
  258       struct cso_node *e;
  259       struct cso_hash *d;
  260    } a;
  261    int start;
  262    struct cso_node *sentinel;
  263    struct cso_node **bucket;
  264 
  265    a.e = node;
  266    while (a.e->next)
  267       a.e = a.e->next;
  268 
  269    if (node == a.e)
  270       start = a.d->numBuckets - 1;
  271    else
  272       start = node->key % a.d->numBuckets;
  273 
  274    sentinel = node;
  275    bucket = a.d->buckets + start;
  276    while (start >= 0) {
  277       if (*bucket != sentinel) {
  278          struct cso_node *prev = *bucket;
  279          while (prev->next != sentinel)
  280             prev = prev->next;
  281          return prev;
  282       }
  283 
  284       sentinel = a.e;
  285       --bucket;
  286       --start;
  287    }
  288    debug_printf("iterating backward beyond first element\n");
  289    return a.e;
  290 }
  291 
  292 void *cso_hash_take(struct cso_hash *hash, unsigned akey)
  293 {
  294    struct cso_node **node = cso_hash_find_node(hash, akey);
  295 
  296    if (*node != hash->end) {
  297       void *t = (*node)->value;
  298       struct cso_node *next = (*node)->next;
  299       FREE(*node);
  300       *node = next;
  301       --hash->size;
  302       cso_data_has_shrunk(hash);
  303       return t;
  304    }
  305    return NULL;
  306 }
  307 
  308 struct cso_hash_iter cso_hash_iter_prev(struct cso_hash_iter iter)
  309 {
  310    struct cso_hash_iter prev = {iter.hash,
  311                                 cso_hash_data_prev(iter.node)};
  312    return prev;
  313 }
  314 
  315 struct cso_hash_iter cso_hash_first_node(struct cso_hash *hash)
  316 {
  317    struct cso_hash_iter iter = {hash, cso_data_first_node(hash)};
  318    return iter;
  319 }
  320 
  321 int cso_hash_size(struct cso_hash *hash)
  322 {
  323    return hash->size;
  324 }
  325 
  326 struct cso_hash_iter cso_hash_erase(struct cso_hash *hash, struct cso_hash_iter iter)
  327 {
  328    struct cso_hash_iter ret = iter;
  329    struct cso_node *node = iter.node;
  330    struct cso_node **node_ptr;
  331 
  332    if (node == hash->end)
  333       return iter;
  334 
  335    ret = cso_hash_iter_next(ret);
  336    node_ptr = &hash->buckets[node->key % hash->numBuckets];
  337    while (*node_ptr != node)
  338       node_ptr = &(*node_ptr)->next;
  339    *node_ptr = node->next;
  340    FREE(node);
  341    --hash->size;
  342    return ret;
  343 }
  344 
  345 bool cso_hash_contains(struct cso_hash *hash, unsigned key)
  346 {
  347    struct cso_node **node = cso_hash_find_node(hash, key);
  348    return *node != hash->end;
  349 }