cso_hash.c File Reference

Include dependency graph for cso_hash.c:

Go to the source code of this file.

Data Structures

struct  cso_node
struct  cso_hash_data
struct  cso_hash

Defines

#define MAX(a, b)   ((a > b) ? (a) : (b))

Functions

static int primeForNumBits (int numBits)
static int countBits (int hint)
static void * cso_data_allocate_node (struct cso_hash_data *hash)
static void cso_free_node (struct cso_node *node)
static struct cso_nodecso_hash_create_node (struct cso_hash *hash, unsigned akey, void *avalue, struct cso_node **anextNode)
static void cso_data_rehash (struct cso_hash_data *hash, int hint)
static void cso_data_might_grow (struct cso_hash_data *hash)
static void cso_data_has_shrunk (struct cso_hash_data *hash)
static struct cso_nodecso_data_first_node (struct cso_hash_data *hash)
static struct cso_node ** cso_hash_find_node (struct cso_hash *hash, unsigned akey)
struct cso_hash_iter cso_hash_insert (struct cso_hash *hash, unsigned key, void *data)
 Adds a data with the given key to the hash.
struct cso_hashcso_hash_create (void)
void cso_hash_delete (struct cso_hash *hash)
struct cso_hash_iter cso_hash_find (struct cso_hash *hash, unsigned key)
 Return an iterator pointing to the first entry in the collision list.
unsigned cso_hash_iter_key (struct cso_hash_iter iter)
void * cso_hash_iter_data (struct cso_hash_iter iter)
static struct cso_nodecso_hash_data_next (struct cso_node *node)
static struct cso_nodecso_hash_data_prev (struct cso_node *node)
struct cso_hash_iter cso_hash_iter_next (struct cso_hash_iter iter)
int cso_hash_iter_is_null (struct cso_hash_iter iter)
void * cso_hash_take (struct cso_hash *hash, unsigned akey)
struct cso_hash_iter cso_hash_iter_prev (struct cso_hash_iter iter)
struct cso_hash_iter cso_hash_first_node (struct cso_hash *hash)
int cso_hash_size (struct cso_hash *hash)
struct cso_hash_iter cso_hash_erase (struct cso_hash *hash, struct cso_hash_iter iter)
 Removes the item pointed to by the current iterator from the hash.

Variables

static const int MinNumBits = 4
static const unsigned char prime_deltas []


Define Documentation

#define MAX ( a,
 )     ((a > b) ? (a) : (b))

Definition at line 38 of file cso_hash.c.


Function Documentation

static int countBits ( int  hint  )  [static]

Definition at line 56 of file cso_hash.c.

References prime_deltas, and primeForNumBits().

00057 {
00058    int numBits = 0;
00059    int bits = hint;
00060 
00061    while (bits > 1) {
00062       bits >>= 1;
00063       numBits++;
00064    }
00065 
00066    if (numBits >= (int)sizeof(prime_deltas)) {
00067       numBits = sizeof(prime_deltas) - 1;
00068    } else if (primeForNumBits(numBits) < hint) {
00069       ++numBits;
00070    }
00071    return numBits;
00072 }

static void* cso_data_allocate_node ( struct cso_hash_data hash  )  [static]

Definition at line 97 of file cso_hash.c.

References MALLOC, and cso_hash_data::nodeSize.

00098 {
00099    return MALLOC(hash->nodeSize);
00100 }

static struct cso_node* cso_data_first_node ( struct cso_hash_data hash  )  [static, read]

Definition at line 190 of file cso_hash.c.

References cso_hash_data::buckets, and cso_hash_data::numBuckets.

00191 {
00192    struct cso_node *e = (struct cso_node *)(hash);
00193    struct cso_node **bucket = hash->buckets;
00194    int n = hash->numBuckets;
00195    while (n--) {
00196       if (*bucket != e)
00197          return *bucket;
00198       ++bucket;
00199    }
00200    return e;
00201 }

static void cso_data_has_shrunk ( struct cso_hash_data hash  )  [static]

Definition at line 181 of file cso_hash.c.

References cso_data_rehash(), MAX, max(), cso_hash_data::numBits, cso_hash_data::numBuckets, cso_hash_data::size, and cso_hash_data::userNumBits.

00182 {
00183    if (hash->size <= (hash->numBuckets >> 3) &&
00184        hash->numBits > hash->userNumBits) {
00185       int max = MAX(hash->numBits-2, hash->userNumBits);
00186       cso_data_rehash(hash,  max);
00187    }
00188 }

static void cso_data_might_grow ( struct cso_hash_data hash  )  [static]

Definition at line 175 of file cso_hash.c.

References cso_data_rehash(), cso_hash_data::numBits, cso_hash_data::numBuckets, and cso_hash_data::size.

00176 {
00177    if (hash->size >= hash->numBuckets)
00178       cso_data_rehash(hash, hash->numBits + 1);
00179 }

static void cso_data_rehash ( struct cso_hash_data hash,
int  hint 
) [static]

Definition at line 126 of file cso_hash.c.

References cso_hash_data::buckets, countBits(), FREE, cso_node::key, MALLOC, MinNumBits, cso_node::next, cso_hash_data::numBits, cso_hash_data::numBuckets, primeForNumBits(), cso_hash_data::size, and cso_hash_data::userNumBits.

00127 {
00128    if (hint < 0) {
00129       hint = countBits(-hint);
00130       if (hint < MinNumBits)
00131          hint = MinNumBits;
00132       hash->userNumBits = (short)hint;
00133       while (primeForNumBits(hint) < (hash->size >> 1))
00134          ++hint;
00135    } else if (hint < MinNumBits) {
00136       hint = MinNumBits;
00137    }
00138 
00139    if (hash->numBits != hint) {
00140       struct cso_node *e = (struct cso_node *)(hash);
00141       struct cso_node **oldBuckets = hash->buckets;
00142       int oldNumBuckets = hash->numBuckets;
00143       int  i = 0;
00144 
00145       hash->numBits = (short)hint;
00146       hash->numBuckets = primeForNumBits(hint);
00147       hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets);
00148       for (i = 0; i < hash->numBuckets; ++i)
00149          hash->buckets[i] = e;
00150 
00151       for (i = 0; i < oldNumBuckets; ++i) {
00152          struct cso_node *firstNode = oldBuckets[i];
00153          while (firstNode != e) {
00154             unsigned h = firstNode->key;
00155             struct cso_node *lastNode = firstNode;
00156             struct cso_node *afterLastNode;
00157             struct cso_node **beforeFirstNode;
00158             
00159             while (lastNode->next != e && lastNode->next->key == h)
00160                lastNode = lastNode->next;
00161 
00162             afterLastNode = lastNode->next;
00163             beforeFirstNode = &hash->buckets[h % hash->numBuckets];
00164             while (*beforeFirstNode != e)
00165                beforeFirstNode = &(*beforeFirstNode)->next;
00166             lastNode->next = *beforeFirstNode;
00167             *beforeFirstNode = firstNode;
00168             firstNode = afterLastNode;
00169          }
00170       }
00171       FREE(oldBuckets);
00172    }
00173 }

static void cso_free_node ( struct cso_node node  )  [static]

Definition at line 102 of file cso_hash.c.

References FREE.

00103 {
00104    FREE(node);
00105 }

struct cso_hash* cso_hash_create ( void   )  [read]

Definition at line 238 of file cso_hash.c.

References cso_hash_data::buckets, cso_hash::d, cso_hash::data, cso_hash_data::fakeNext, FREE, MALLOC_STRUCT, MinNumBits, cso_hash_data::nodeSize, cso_hash_data::numBits, cso_hash_data::numBuckets, cso_hash_data::size, and cso_hash_data::userNumBits.

00239 {
00240    struct cso_hash *hash = MALLOC_STRUCT(cso_hash);
00241    if (!hash)
00242       return NULL;
00243 
00244    hash->data.d = MALLOC_STRUCT(cso_hash_data);
00245    if (!hash->data.d) {
00246       FREE(hash);
00247       return NULL;
00248    }
00249 
00250    hash->data.d->fakeNext = 0;
00251    hash->data.d->buckets = 0;
00252    hash->data.d->size = 0;
00253    hash->data.d->nodeSize = sizeof(struct cso_node);
00254    hash->data.d->userNumBits = (short)MinNumBits;
00255    hash->data.d->numBits = 0;
00256    hash->data.d->numBuckets = 0;
00257 
00258    return hash;
00259 }

static struct cso_node* cso_hash_create_node ( struct cso_hash hash,
unsigned  akey,
void *  avalue,
struct cso_node **  anextNode 
) [static, read]

Definition at line 108 of file cso_hash.c.

References cso_data_allocate_node(), cso_hash::d, cso_hash::data, cso_node::key, cso_node::next, cso_hash_data::size, and cso_node::value.

00111 {
00112    struct cso_node *node = cso_data_allocate_node(hash->data.d);
00113 
00114    if (!node)
00115       return NULL;
00116 
00117    node->key = akey;
00118    node->value = avalue;
00119 
00120    node->next = (struct cso_node*)(*anextNode);
00121    *anextNode = node;
00122    ++hash->data.d->size;
00123    return node;
00124 }

static struct cso_node* cso_hash_data_next ( struct cso_node node  )  [static, read]

Definition at line 301 of file cso_hash.c.

References debug_printf(), cso_node::key, and cso_node::next.

00302 {
00303    union {
00304       struct cso_node *next;
00305       struct cso_node *e;
00306       struct cso_hash_data *d;
00307    } a;
00308    int start;
00309    struct cso_node **bucket;
00310    int n;
00311 
00312    a.next = node->next;
00313    if (!a.next) {
00314       debug_printf("iterating beyond the last element\n");
00315       return 0;
00316    }
00317    if (a.next->next)
00318       return a.next;
00319 
00320    start = (node->key % a.d->numBuckets) + 1;
00321    bucket = a.d->buckets + start;
00322    n = a.d->numBuckets - start;
00323    while (n--) {
00324       if (*bucket != a.e)
00325          return *bucket;
00326       ++bucket;
00327    }
00328    return a.e;
00329 }

static struct cso_node* cso_hash_data_prev ( struct cso_node node  )  [static, read]

Definition at line 332 of file cso_hash.c.

References debug_printf(), cso_node::key, and cso_node::next.

00333 {
00334    union {
00335       struct cso_node *e;
00336       struct cso_hash_data *d;
00337    } a;
00338    int start;
00339    struct cso_node *sentinel;
00340    struct cso_node **bucket;
00341 
00342    a.e = node;
00343    while (a.e->next)
00344       a.e = a.e->next;
00345 
00346    if (node == a.e)
00347       start = a.d->numBuckets - 1;
00348    else
00349       start = node->key % a.d->numBuckets;
00350 
00351    sentinel = node;
00352    bucket = a.d->buckets + start;
00353    while (start >= 0) {
00354       if (*bucket != sentinel) {
00355          struct cso_node *prev = *bucket;
00356          while (prev->next != sentinel)
00357             prev = prev->next;
00358          return prev;
00359       }
00360 
00361       sentinel = a.e;
00362       --bucket;
00363       --start;
00364    }
00365    debug_printf("iterating backward beyond first element\n");
00366    return a.e;
00367 }

void cso_hash_delete ( struct cso_hash hash  ) 

Definition at line 261 of file cso_hash.c.

References cso_hash_data::buckets, cso_free_node(), cso_hash::d, cso_hash::data, FREE, cso_node::next, and cso_hash_data::numBuckets.

00262 {
00263    struct cso_node *e_for_x = (struct cso_node *)(hash->data.d);
00264    struct cso_node **bucket = (struct cso_node **)(hash->data.d->buckets);
00265    int n = hash->data.d->numBuckets;
00266    while (n--) {
00267       struct cso_node *cur = *bucket++;
00268       while (cur != e_for_x) {
00269          struct cso_node *next = cur->next;
00270          cso_free_node(cur);
00271          cur = next;
00272       }
00273    }
00274    FREE(hash->data.d->buckets);
00275    FREE(hash->data.d);
00276    FREE(hash);
00277 }

struct cso_hash_iter cso_hash_erase ( struct cso_hash hash,
struct cso_hash_iter  iter 
) [read]

Removes the item pointed to by the current iterator from the hash.

Note that the data itself is not erased and if it was a malloc'ed pointer it will have to be freed after calling this function by the callee. Function returns iterator pointing to the item after the removed one in the hash.

Definition at line 416 of file cso_hash.c.

References cso_free_node(), cso_hash_iter_next(), cso_node::key, cso_node::next, and cso_hash_iter::node.

00417 {
00418    struct cso_hash_iter ret = iter;
00419    struct cso_node *node = iter.node;
00420    struct cso_node **node_ptr;
00421 
00422    if (node == hash->data.e)
00423       return iter;
00424 
00425    ret = cso_hash_iter_next(ret);
00426    node_ptr = (struct cso_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]);
00427    while (*node_ptr != node)
00428       node_ptr = &(*node_ptr)->next;
00429    *node_ptr = node->next;
00430    cso_free_node(node);
00431    --hash->data.d->size;
00432    return ret;
00433 }

struct cso_hash_iter cso_hash_find ( struct cso_hash hash,
unsigned  key 
) [read]

Return an iterator pointing to the first entry in the collision list.

Definition at line 279 of file cso_hash.c.

References cso_hash_find_node(), and cso_node::key.

00281 {
00282    struct cso_node **nextNode = cso_hash_find_node(hash, key);
00283    struct cso_hash_iter iter = {hash, *nextNode};
00284    return iter;
00285 }

static struct cso_node** cso_hash_find_node ( struct cso_hash hash,
unsigned  akey 
) [static, read]

Definition at line 203 of file cso_hash.c.

References assert, cso_hash_data::buckets, cso_hash::d, cso_hash::data, cso_hash::e, cso_node::key, cso_node::next, and cso_hash_data::numBuckets.

00204 {
00205    struct cso_node **node;
00206 
00207    if (hash->data.d->numBuckets) {
00208       node = (struct cso_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]);
00209       assert(*node == hash->data.e || (*node)->next);
00210       while (*node != hash->data.e && (*node)->key != akey)
00211          node = &(*node)->next;
00212    } else {
00213       node = (struct cso_node **)((const struct cso_node * const *)(&hash->data.e));
00214    }
00215    return node;
00216 }

struct cso_hash_iter cso_hash_first_node ( struct cso_hash hash  )  [read]

Definition at line 405 of file cso_hash.c.

References cso_data_first_node().

00406 {
00407    struct cso_hash_iter iter = {hash, cso_data_first_node(hash->data.d)};
00408    return iter;
00409 }

struct cso_hash_iter cso_hash_insert ( struct cso_hash hash,
unsigned  key,
void *  data 
) [read]

Adds a data with the given key to the hash.

If entry with the given key is already in the hash, this current entry is instered before it in the collision list. Function returns iterator pointing to the inserted item in the hash.

Definition at line 218 of file cso_hash.c.

References cso_data_might_grow(), cso_hash_create_node(), cso_hash_find_node(), and cso_node::key.

00220 {
00221    cso_data_might_grow(hash->data.d);
00222 
00223    {
00224       struct cso_node **nextNode = cso_hash_find_node(hash, key);
00225       struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode);
00226       if (!node) {
00227          struct cso_hash_iter null_iter = {hash, 0};
00228          return null_iter;
00229       }
00230 
00231       {
00232          struct cso_hash_iter iter = {hash, node};
00233          return iter;
00234       }
00235    }
00236 }

void* cso_hash_iter_data ( struct cso_hash_iter  iter  ) 

Definition at line 294 of file cso_hash.c.

References cso_hash::data, cso_hash::e, cso_hash_iter::hash, cso_hash_iter::node, and cso_node::value.

00295 {
00296    if (!iter.node || iter.hash->data.e == iter.node)
00297       return 0;
00298    return iter.node->value;
00299 }

int cso_hash_iter_is_null ( struct cso_hash_iter  iter  ) 

Definition at line 375 of file cso_hash.c.

References cso_hash::data, cso_hash::e, cso_hash_iter::hash, and cso_hash_iter::node.

00376 {
00377    if (!iter.node || iter.node == iter.hash->data.e)
00378       return 1;
00379    return 0;
00380 }

unsigned cso_hash_iter_key ( struct cso_hash_iter  iter  ) 

Definition at line 287 of file cso_hash.c.

References cso_hash::data, cso_hash::e, cso_hash_iter::hash, cso_node::key, and cso_hash_iter::node.

00288 {
00289    if (!iter.node || iter.hash->data.e == iter.node)
00290       return 0;
00291    return iter.node->key;
00292 }

struct cso_hash_iter cso_hash_iter_next ( struct cso_hash_iter  iter  )  [read]

Definition at line 369 of file cso_hash.c.

References cso_hash_data_next(), and cso_hash_iter::hash.

00370 {
00371    struct cso_hash_iter next = {iter.hash, cso_hash_data_next(iter.node)};
00372    return next;
00373 }

struct cso_hash_iter cso_hash_iter_prev ( struct cso_hash_iter  iter  )  [read]

Definition at line 398 of file cso_hash.c.

References cso_hash_data_prev(), and cso_hash_iter::hash.

00399 {
00400    struct cso_hash_iter prev = {iter.hash,
00401                                  cso_hash_data_prev(iter.node)};
00402    return prev;
00403 }

int cso_hash_size ( struct cso_hash hash  ) 

Definition at line 411 of file cso_hash.c.

References cso_hash::d, cso_hash::data, and cso_hash_data::size.

00412 {
00413    return hash->data.d->size;
00414 }

void* cso_hash_take ( struct cso_hash hash,
unsigned  akey 
)

Definition at line 382 of file cso_hash.c.

References cso_data_has_shrunk(), cso_free_node(), cso_hash_find_node(), cso_hash::d, cso_hash::data, cso_hash::e, cso_node::next, and cso_hash_data::size.

00384 {
00385    struct cso_node **node = cso_hash_find_node(hash, akey);
00386    if (*node != hash->data.e) {
00387       void *t = (*node)->value;
00388       struct cso_node *next = (*node)->next;
00389       cso_free_node(*node);
00390       *node = next;
00391       --hash->data.d->size;
00392       cso_data_has_shrunk(hash->data.d);
00393       return t;
00394    }
00395    return 0;
00396 }

static int primeForNumBits ( int  numBits  )  [static]

Definition at line 47 of file cso_hash.c.

References prime_deltas.

00048 {
00049    return (1 << numBits) + prime_deltas[numBits];
00050 }


Variable Documentation

const int MinNumBits = 4 [static]

Definition at line 40 of file cso_hash.c.

const unsigned char prime_deltas[] [static]

Initial value:

 {
   0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
   1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
}

Definition at line 42 of file cso_hash.c.


Generated on Tue Sep 29 06:25:19 2009 for Gallium3D by  doxygen 1.5.4