Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  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. }
  440.