Logo Search packages:      
Sourcecode: callgrind version File versions

hash.c

// Generic resizable hash table

#include "hash.h"

void SK_(rhash_init)(rhash* h)
{
  Int i;

  h->entries = 0;
  h->resizes = 0;
  h->table   = (rhash_entry**) VG_(malloc)(h->size * sizeof(rhash_entry*));

  for (i = 0; i < h->size; i++)
     h->table[i] = 0;
}

/* double size of cxt table  */
static void resize_rhash(rhash* h)
{
  Int i, new_size, conflicts1 = 0, conflicts2 = 0;
  rhash_entry **new_table, *curr, *next;
  UInt new_hash;

  new_size  = 2* h->size +3;
  new_table = (rhash_entry**) VG_(malloc)(new_size * sizeof(rhash_entry*));

  if (!new_table) return;

  for (i = 0; i < new_size; i++)
    new_table[i] = NULL;

  for (i = 0; i < h->size; i++) {
    if (h->table[i] == NULL) continue;

    curr = h->table[i];
    while (NULL != curr) {
      next = curr->next;

      new_hash = curr->hash % new_size;

      curr->next = new_table[new_hash];
      new_table[new_hash] = curr;
      if (curr->next) {
      conflicts1++;
      if (curr->next->next)
        conflicts2++;
      }
      
      curr = next;
    }
  }

  VG_(free)(h->table);


  CT_DEBUG(0, "Resize %s hashtable: %d => %d (entries %d, conflicts %d/%d)\n",
         h->name, h->size, new_size,
         h->entries, conflicts1, conflicts2);

  h->size  = new_size;
  h->table = new_table;
  h->resizes++;
}


static rhash_entry* new_entry(rhash* h, void* data)
{
  UInt idx;
  rhash_entry* new = (*h->new_entry)(data);
  if (!new) return 0;

  h->entries++;
  if (10* h->entries / h->size > 8)
    resize_rhash(h);

  idx = new->hash % h->size;
  new->next = h->table[idx];
  h->table[idx] = new;

  return new;
}
  

rhash_entry* SK_(rhash_get)(rhash* h, int hash, void* data)
{
  UInt idx = hash % h->size;
  rhash_entry* e = h->table[idx];
 
  while(e) {
    if ( (*h->has_key)(e, data) ) break;
    e = e->next;
  }

  if (!e)
    e = new_entry(h,data);

  return e;
}

void SK_(rhash_forall)(rhash* h, void (*f)(rhash_entry*) )
{
  UInt i;
  rhash_entry* e;

  for(i=0;i<h->size; i++) {
    e = h->table[i];
    while(e) {
      (*f)(e);
      e = e->next;
    }
  }
}

Generated by  Doxygen 1.6.0   Back to index