Back to index

glibc  2.9
Classes | Defines | Typedefs | Functions
simple-hash.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include "obstack.h"
#include "simple-hash.h"
#include "hashval.h"

Go to the source code of this file.

Classes

struct  hash_entry

Defines

#define obstack_chunk_alloc   malloc
#define obstack_chunk_free   free
#define BITSPERBYTE   8
#define bcopy(s, d, n)   memcpy ((d), (s), (n))

Typedefs

typedef struct hash_entry hash_entry

Functions

void * xmalloc (size_t __n)
void * xcalloc (size_t __n, size_t __m)
static void insert_entry_2 (hash_table *htab, const void *key, size_t keylen, unsigned long hval, size_t idx, void *data)
static size_t lookup (const hash_table *htab, const void *key, size_t keylen, unsigned long int hval)
static int is_prime (unsigned long int candidate)
int init_hash (hash_table *htab, unsigned long int init_size)
int delete_hash (hash_table *htab)
int insert_entry (hash_table *htab, const void *key, size_t keylen, void *data)
static void insert_entry_2 (hash_table *htab, const void *key, size_t keylen, unsigned long int hval, size_t idx, void *data)
int find_entry (hash_table *htab, const void *key, size_t keylen, void **result) const
int set_entry (hash_table *htab, const void *key, size_t keylen, void *newval)
int iterate_table (hash_table *htab, void **ptr, const void **key, size_t *keylen, void **data) const
static size_t lookup (hash_table *htab, const void *key, size_t keylen, unsigned long int hval) const
unsigned long int next_prime (unsigned long int seed)

Class Documentation

struct hash_entry

Definition at line 36 of file iconvconfig.h.

Collaboration diagram for hash_entry:
Class Members
void * data
const void * key
size_t keylen
gidx_t module_idx
struct hash_entry * next
gidx_t string_offset
unsigned long used

Define Documentation

#define bcopy (   s,
  d,
  n 
)    memcpy ((d), (s), (n))

Definition at line 49 of file simple-hash.c.

#define BITSPERBYTE   8

Definition at line 45 of file simple-hash.c.

Definition at line 41 of file simple-hash.c.

#define obstack_chunk_free   free

Definition at line 42 of file simple-hash.c.


Typedef Documentation

typedef struct hash_entry hash_entry

Function Documentation

int delete_hash ( hash_table htab)

Definition at line 98 of file simple-hash.c.

{
  free (htab->table);
  obstack_free (&htab->mem_pool, NULL);
  return 0;
}
int find_entry ( hash_table htab,
const void *  key,
size_t  keylen,
void **  result 
) const

Definition at line 186 of file simple-hash.c.

{
  hash_entry *table = (hash_entry *) htab->table;
  size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));

  if (table[idx].used == 0)
    return -1;

  *result = table[idx].data;
  return 0;
}

Here is the caller graph for this function:

int init_hash ( hash_table htab,
unsigned long int  init_size 
)

Definition at line 76 of file simple-hash.c.

{
  /* We need the size to be a prime.  */
  init_size = next_prime (init_size);

  /* Initialize the data structure.  */
  htab->size = init_size;
  htab->filled = 0;
  htab->first = NULL;
  htab->table = (void *) xcalloc (init_size + 1, sizeof (hash_entry));
  if (htab->table == NULL)
    return -1;

  obstack_init (&htab->mem_pool);

  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

int insert_entry ( hash_table htab,
const void *  key,
size_t  keylen,
void *  data 
)

Definition at line 108 of file simple-hash.c.

{
  unsigned long int hval = compute_hashval (key, keylen);
  hash_entry *table = (hash_entry *) htab->table;
  size_t idx = lookup (htab, key, keylen, hval);

  if (table[idx].used)
    /* We don't want to overwrite the old value.  */
    return -1;
  else
    {
      /* An empty bucket has been found.  */
      insert_entry_2 (htab, obstack_copy (&htab->mem_pool, key, keylen),
                    keylen, hval, idx, data);
      return 0;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void insert_entry_2 ( hash_table htab,
const void *  key,
size_t  keylen,
unsigned long  hval,
size_t  idx,
void *  data 
) [static]

Here is the caller graph for this function:

static void insert_entry_2 ( hash_table htab,
const void *  key,
size_t  keylen,
unsigned long int  hval,
size_t  idx,
void *  data 
) [static]

Definition at line 131 of file simple-hash.c.

{
  hash_entry *table = (hash_entry *) htab->table;

  table[idx].used = hval;
  table[idx].key = key;
  table[idx].keylen = keylen;
  table[idx].data = data;

      /* List the new value in the list.  */
  if ((hash_entry *) htab->first == NULL)
    {
      table[idx].next = &table[idx];
      htab->first = &table[idx];
    }
  else
    {
      table[idx].next = ((hash_entry *) htab->first)->next;
      ((hash_entry *) htab->first)->next = &table[idx];
      htab->first = &table[idx];
    }

  ++htab->filled;
  if (100 * htab->filled > 75 * htab->size)
    {
      /* Table is filled more than 75%.  Resize the table.
        Experiments have shown that for best performance, this threshold
        must lie between 40% and 85%.  */
      unsigned long int old_size = htab->size;

      htab->size = next_prime (htab->size * 2);
      htab->filled = 0;
      htab->first = NULL;
      htab->table = (void *) xcalloc (1 + htab->size, sizeof (hash_entry));

      for (idx = 1; idx <= old_size; ++idx)
       if (table[idx].used)
         insert_entry_2 (htab, table[idx].key, table[idx].keylen,
                       table[idx].used,
                       lookup (htab, table[idx].key, table[idx].keylen,
                              table[idx].used),
                       table[idx].data);

      free (table);
    }
}

Here is the call graph for this function:

static int is_prime ( unsigned long int  candidate) [static]

Definition at line 311 of file simple-hash.c.

{
  /* No even number and none less than 10 will be passed here.  */
  unsigned long int divn = 3;
  unsigned long int sq = divn * divn;

  while (sq < candidate && candidate % divn != 0)
    {
      ++divn;
      sq += 4 * divn;
      ++divn;
    }

  return candidate % divn != 0;
}

Here is the caller graph for this function:

int iterate_table ( hash_table htab,
void **  ptr,
const void **  key,
size_t keylen,
void **  data 
) const

Definition at line 222 of file simple-hash.c.

{
  if (*ptr == NULL)
    {
      if (htab->first == NULL)
       return -1;
      *ptr = (void *) ((hash_entry *) htab->first)->next;
    }
  else
    {
      if (*ptr == htab->first)
       return -1;
      *ptr = (void *) (((hash_entry *) *ptr)->next);
    }

  *key = ((hash_entry *) *ptr)->key;
  *keylen = ((hash_entry *) *ptr)->keylen;
  *data = ((hash_entry *) *ptr)->data;
  return 0;
}

Here is the caller graph for this function:

static size_t lookup ( const hash_table htab,
const void *  key,
size_t  keylen,
unsigned long int  hval 
) [static]
static size_t lookup ( hash_table htab,
const void *  key,
size_t  keylen,
unsigned long int  hval 
) const [static]

Definition at line 254 of file simple-hash.c.

{
  unsigned long int hash;
  size_t idx;
  hash_entry *table = (hash_entry *) htab->table;

  /* First hash function: simply take the modul but prevent zero.  */
  hash = 1 + hval % htab->size;

  idx = hash;

  if (table[idx].used)
    {
      if (table[idx].used == hval && table[idx].keylen == keylen
         && memcmp (table[idx].key, key, keylen) == 0)
       return idx;

      /* Second hash function as suggested in [Knuth].  */
      hash = 1 + hval % (htab->size - 2);

      do
       {
         if (idx <= hash)
           idx = htab->size + idx - hash;
         else
           idx -= hash;

         /* If entry is found use it.  */
         if (table[idx].used == hval && table[idx].keylen == keylen
             && memcmp (table[idx].key, key, keylen) == 0)
           return idx;
       }
      while (table[idx].used);
    }
  return idx;
}

Here is the call graph for this function:

unsigned long int next_prime ( unsigned long int  seed)

Definition at line 297 of file simple-hash.c.

{
  /* Make it definitely odd.  */
  seed |= 1;

  while (!is_prime (seed))
    seed += 2;

  return seed;
}

Here is the call graph for this function:

int set_entry ( hash_table htab,
const void *  key,
size_t  keylen,
void *  newval 
)

Definition at line 204 of file simple-hash.c.

{
  hash_entry *table = (hash_entry *) htab->table;
  size_t idx = lookup (htab, key, keylen, compute_hashval (key, keylen));

  if (table[idx].used == 0)
    return -1;

  table[idx].data = newval;
  return 0;
}
void* xcalloc ( size_t  __n,
size_t  __m 
)

Definition at line 91 of file xmalloc.c.

{
  VOID *p;

  p = calloc (n, s);
  if (p == 0)
    p = fixup_null_alloc (n);
  return p;
}
void* xmalloc ( size_t  __n)

Definition at line 77 of file xmalloc.c.

{
  VOID *p;

  p = malloc (n);
  if (p == 0)
    p = fixup_null_alloc (n);
  return p;
}