Back to index

glibc  2.9
Classes | Typedefs | Functions
simple-hash.h File Reference
#include <obstack.h>
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  hash_table

Typedefs

typedef struct hash_table hash_table

Functions

int init_hash (hash_table *htab, unsigned long int init_size) __THROW
int delete_hash (hash_table *htab) __THROW
int insert_entry (hash_table *htab, const void *key, size_t keylen, void *data) __THROW
int find_entry (const hash_table *htab, const void *key, size_t keylen, void **result) __THROW
int set_entry (hash_table *htab, const void *key, size_t keylen, void *newval) __THROW
int iterate_table (const hash_table *htab, void **ptr, const void **key, size_t *keylen, void **data) __THROW
unsigned long int compute_hashval (const void *key, size_t keylen) __THROW
unsigned long int next_prime (unsigned long int seed) __THROW

Class Documentation

struct hash_table

Definition at line 24 of file simple-hash.h.

Class Members
unsigned long int filled
void * first
unsigned long int size
void * table

Typedef Documentation

typedef struct hash_table hash_table

Function Documentation

unsigned long int compute_hashval ( const void *  key,
size_t  keylen 
)

Definition at line 27 of file hashval.h.

{
  size_t cnt;
  hashval_t hval;

  /* Compute the hash value for the given string.  The algorithm
     is taken from [Aho,Sethi,Ullman], modified to reduce the number of
     collisions for short strings with very varied bit patterns.
     See http://www.clisp.org/haible/hashfunc.html.  */
  cnt = 0;
  hval = keylen;
  while (cnt < keylen)
    {
      hval = (hval << 9) | (hval >> (sizeof hval * CHAR_BIT - 9));
      hval += (hashval_t) *(((char *) key) + cnt++);
    }
  return hval != 0 ? hval : ~((hashval_t) 0);
}
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 ( const hash_table htab,
const void *  key,
size_t  keylen,
void **  result 
)
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:

int iterate_table ( const hash_table htab,
void **  ptr,
const void **  key,
size_t keylen,
void **  data 
)
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;
}