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_node *	cso_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_node *	cso_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_hash *	cso_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_node *	cso_hash_data_next (struct cso_node *node)
static struct cso_node *	cso_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,
		b		)	((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().

{
   int numBits = 0;
   int bits = hint;

   while (bits > 1) {
      bits >>= 1;
      numBits++;
   }

   if (numBits >= (int)sizeof(prime_deltas)) {
      numBits = sizeof(prime_deltas) - 1;
   } else if (primeForNumBits(numBits) < hint) {
      ++numBits;
   }
   return numBits;
}

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.

{
   return MALLOC(hash->nodeSize);
}

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.

{
   struct cso_node *e = (struct cso_node *)(hash);
   struct cso_node **bucket = hash->buckets;
   int n = hash->numBuckets;
   while (n--) {
      if (*bucket != e)
         return *bucket;
      ++bucket;
   }
   return e;
}

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.

{
   if (hash->size <= (hash->numBuckets >> 3) &&
       hash->numBits > hash->userNumBits) {
      int max = MAX(hash->numBits-2, hash->userNumBits);
      cso_data_rehash(hash,  max);
   }
}

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.

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

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.

{
   if (hint < 0) {
      hint = countBits(-hint);
      if (hint < MinNumBits)
         hint = MinNumBits;
      hash->userNumBits = (short)hint;
      while (primeForNumBits(hint) < (hash->size >> 1))
         ++hint;
   } else if (hint < MinNumBits) {
      hint = MinNumBits;
   }

   if (hash->numBits != hint) {
      struct cso_node *e = (struct cso_node *)(hash);
      struct cso_node **oldBuckets = hash->buckets;
      int oldNumBuckets = hash->numBuckets;
      int  i = 0;

      hash->numBits = (short)hint;
      hash->numBuckets = primeForNumBits(hint);
      hash->buckets = MALLOC(sizeof(struct cso_node*) * hash->numBuckets);
      for (i = 0; i < hash->numBuckets; ++i)
         hash->buckets[i] = e;

      for (i = 0; i < oldNumBuckets; ++i) {
         struct cso_node *firstNode = oldBuckets[i];
         while (firstNode != e) {
            unsigned h = firstNode->key;
            struct cso_node *lastNode = firstNode;
            struct cso_node *afterLastNode;
            struct cso_node **beforeFirstNode;
            
            while (lastNode->next != e && lastNode->next->key == h)
               lastNode = lastNode->next;

            afterLastNode = lastNode->next;
            beforeFirstNode = &hash->buckets[h % hash->numBuckets];
            while (*beforeFirstNode != e)
               beforeFirstNode = &(*beforeFirstNode)->next;
            lastNode->next = *beforeFirstNode;
            *beforeFirstNode = firstNode;
            firstNode = afterLastNode;
         }
      }
      FREE(oldBuckets);
   }
}

static void cso_free_node

(

struct cso_node *

node

)

[static]

Definition at line 102 of file cso_hash.c.

References FREE.

{
   FREE(node);
}

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;
}

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.

{
   struct cso_node *node = cso_data_allocate_node(hash->data.d);

   if (!node)
      return NULL;

   node->key = akey;
   node->value = avalue;

   node->next = (struct cso_node*)(*anextNode);
   *anextNode = node;
   ++hash->data.d->size;
   return node;
}

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.

{
   union {
      struct cso_node *next;
      struct cso_node *e;
      struct cso_hash_data *d;
   } a;
   int start;
   struct cso_node **bucket;
   int n;

   a.next = node->next;
   if (!a.next) {
      debug_printf("iterating beyond the last element\n");
      return 0;
   }
   if (a.next->next)
      return a.next;

   start = (node->key % a.d->numBuckets) + 1;
   bucket = a.d->buckets + start;
   n = a.d->numBuckets - start;
   while (n--) {
      if (*bucket != a.e)
         return *bucket;
      ++bucket;
   }
   return a.e;
}

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.

{
   union {
      struct cso_node *e;
      struct cso_hash_data *d;
   } a;
   int start;
   struct cso_node *sentinel;
   struct cso_node **bucket;

   a.e = node;
   while (a.e->next)
      a.e = a.e->next;

   if (node == a.e)
      start = a.d->numBuckets - 1;
   else
      start = node->key % a.d->numBuckets;

   sentinel = node;
   bucket = a.d->buckets + start;
   while (start >= 0) {
      if (*bucket != sentinel) {
         struct cso_node *prev = *bucket;
         while (prev->next != sentinel)
            prev = prev->next;
         return prev;
      }

      sentinel = a.e;
      --bucket;
      --start;
   }
   debug_printf("iterating backward beyond first element\n");
   return a.e;
}

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;
}

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.

{
   struct cso_node **node;

   if (hash->data.d->numBuckets) {
      node = (struct cso_node **)(&hash->data.d->buckets[akey % hash->data.d->numBuckets]);
      assert(*node == hash->data.e || (*node)->next);
      while (*node != hash->data.e && (*node)->key != akey)
         node = &(*node)->next;
   } else {
      node = (struct cso_node **)((const struct cso_node * const *)(&hash->data.e));
   }
   return node;
}

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

{
   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;
}

static int primeForNumBits

(

int

numBits

)

[static]

Definition at line 47 of file cso_hash.c.

References prime_deltas.

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

---

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.

---