cso_hash.h File Reference

Hash table implementation. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	cso_hash_iter
Functions
struct cso_hash *	cso_hash_create (void)
void	cso_hash_delete (struct cso_hash *hash)
int	cso_hash_size (struct cso_hash *hash)
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_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.
void *	cso_hash_take (struct cso_hash *hash, unsigned key)
struct cso_hash_iter	cso_hash_first_node (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.
int	cso_hash_iter_is_null (struct cso_hash_iter iter)
unsigned	cso_hash_iter_key (struct cso_hash_iter iter)
void *	cso_hash_iter_data (struct cso_hash_iter iter)
struct cso_hash_iter	cso_hash_iter_next (struct cso_hash_iter iter)
struct cso_hash_iter	cso_hash_iter_prev (struct cso_hash_iter iter)
void *	cso_hash_find_data_from_template (struct cso_hash *hash, unsigned hash_key, void *templ, int size)
	Convenience routine to iterate over the collision list while doing a memory comparison to see which entry in the list is a direct copy of our template and returns that entry.

---

Detailed Description

Hash table implementation.

This file provides a hash implementation that is capable of dealing with collisions. It stores colliding entries in linked list. All functions operating on the hash return an iterator. The iterator itself points to the collision list. If there wasn't any collision the list will have just one entry, otherwise client code should iterate over the entries to find the exact entry among ones that had the same key (e.g. memcmp could be used on the data to check that)

Author:

Zack Rusin <zack@tungstengraphics.com>

Definition in file cso_hash.h.

---

Function Documentation

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.

{
   struct cso_hash *hash = MALLOC_STRUCT(cso_hash);
   if (!hash)
      return NULL;

   hash->data.d = MALLOC_STRUCT(cso_hash_data);
   if (!hash->data.d) {
      FREE(hash);
      return NULL;
   }

   hash->data.d->fakeNext = 0;
   hash->data.d->buckets = 0;
   hash->data.d->size = 0;
   hash->data.d->nodeSize = sizeof(struct cso_node);
   hash->data.d->userNumBits = (short)MinNumBits;
   hash->data.d->numBits = 0;
   hash->data.d->numBuckets = 0;

   return hash;
}

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.

{
   struct cso_node *e_for_x = (struct cso_node *)(hash->data.d);
   struct cso_node **bucket = (struct cso_node **)(hash->data.d->buckets);
   int n = hash->data.d->numBuckets;
   while (n--) {
      struct cso_node *cur = *bucket++;
      while (cur != e_for_x) {
         struct cso_node *next = cur->next;
         cso_free_node(cur);
         cur = next;
      }
   }
   FREE(hash->data.d->buckets);
   FREE(hash->data.d);
   FREE(hash);
}

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.

{
   struct cso_hash_iter ret = iter;
   struct cso_node *node = iter.node;
   struct cso_node **node_ptr;

   if (node == hash->data.e)
      return iter;

   ret = cso_hash_iter_next(ret);
   node_ptr = (struct cso_node**)(&hash->data.d->buckets[node->key % hash->data.d->numBuckets]);
   while (*node_ptr != node)
      node_ptr = &(*node_ptr)->next;
   *node_ptr = node->next;
   cso_free_node(node);
   --hash->data.d->size;
   return ret;
}

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.

{
   struct cso_node **nextNode = cso_hash_find_node(hash, key);
   struct cso_hash_iter iter = {hash, *nextNode};
   return iter;
}

void* cso_hash_find_data_from_template	(	struct cso_hash *	hash,
		unsigned	hash_key,
		void *	templ,
		int	size
	)

Convenience routine to iterate over the collision list while doing a memory comparison to see which entry in the list is a direct copy of our template and returns that entry.

Definition at line 263 of file cso_cache.c.

References cso_hash_find(), cso_hash_iter_data(), cso_hash_iter_is_null(), and cso_hash_iter_next().

{
   struct cso_hash_iter iter = cso_hash_find(hash, hash_key);
   while (!cso_hash_iter_is_null(iter)) {
      void *iter_data = cso_hash_iter_data(iter);
      if (!memcmp(iter_data, templ, size)) {
         /* We found a match
          */
         return iter_data;
      }
      iter = cso_hash_iter_next(iter);
   }
   return NULL;

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().

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

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.

{
   cso_data_might_grow(hash->data.d);

   {
      struct cso_node **nextNode = cso_hash_find_node(hash, key);
      struct cso_node *node = cso_hash_create_node(hash, key, data, nextNode);
      if (!node) {
         struct cso_hash_iter null_iter = {hash, 0};
         return null_iter;
      }

      {
         struct cso_hash_iter iter = {hash, node};
         return iter;
      }
   }
}

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.

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

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.

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

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.

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

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.

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

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.

{
   struct cso_hash_iter prev = {iter.hash,
                                 cso_hash_data_prev(iter.node)};
   return prev;
}

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.

{
   return hash->data.d->size;
}

void* cso_hash_take	(	struct cso_hash *	hash,
		unsigned	key
	)

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.

{
   struct cso_node **node = cso_hash_find_node(hash, akey);
   if (*node != hash->data.e) {
      void *t = (*node)->value;
      struct cso_node *next = (*node)->next;
      cso_free_node(*node);
      *node = next;
      --hash->data.d->size;
      cso_data_has_shrunk(hash->data.d);
      return t;
   }
   return 0;
}

---