hashtable.c File Reference

---

Detailed Description

A simple hashtable implementation.

Author:

Christian Biere

Date:

2006

#include "common.h"
#include "lib/hashtable.h"
#include "lib/vmm.h"
#include "lib/override.h"

Data Structures
struct	hash_item
struct	hash_table
Defines
#define	HASH_ITEMS_PER_BIN   4
#define	hash_table_check(ht)
Typedefs
typedef hash_item	hash_item_t
Functions
hash_item_t *	hash_item_alloc (hash_table_t *ht, void *key, void *value)
void	hash_item_free (hash_table_t *ht, hash_item_t *item)
void	hash_table_new_intern (hash_table_t *ht, size_t num_bins)
hash_table_t *	hash_table_new (void)
size_t	hash_table_size (const hash_table_t *ht)
	Checks how many items are currently in stored in the hash_table.
size_t	hash_key (const void *key)
	NOTE: A naive direct use of the pointer has a much worse distribution e.g., only a quarter of the bins are used.
hash_item_t *	hash_table_find (hash_table_t *ht, const void *key, size_t *bin)
void	hash_table_foreach (hash_table_t *ht, hash_table_foreach_func func, void *data)
void	hash_table_clear (hash_table_t *ht)
void	hash_table_resize_helper (void *key, void *value, void *data)
void	hash_table_resize (hash_table_t *ht)
void	hash_table_status (const hash_table_t *ht)
gboolean	hash_table_insert (hash_table_t *ht, void *key, void *value)
	Adds a new item to the hash_table.
gboolean	hash_table_remove (hash_table_t *ht, void *key)
void *	hash_table_lookup (hash_table_t *ht, void *key)
void	hash_table_destroy (hash_table_t *ht)

---

Define Documentation

#define HASH_ITEMS_PER_BIN   4

#define hash_table_check (  ht   )

Value: G_STMT_START { \ const hash_table_t *ht_ = (ht); \ \ RUNTIME_ASSERT(ht_ != NULL); \ RUNTIME_ASSERT(ht_->num_bins > 0); \ } G_STMT_END

---

Typedef Documentation

typedef struct hash_item hash_item_t

---

Function Documentation

hash_item_t* hash_item_alloc (  hash_table_t *  ht, void *  key, void *  value )  [static]

void hash_item_free (  hash_table_t *  ht, hash_item_t *  item )  [static]

size_t hash_key (  const void *  key  )  [inline, static]

NOTE: A naive direct use of the pointer has a much worse distribution e.g., only a quarter of the bins are used.

void hash_table_clear (  hash_table_t *  ht  )  [static]

void hash_table_destroy (  hash_table_t *  ht  )

hash_item_t* hash_table_find (  hash_table_t *  ht, const void *  key, size_t *  bin )  [static]

Parameters: ht  a hash_table. key  the key to look for. bin  if not NULL, it will be set to the bin number that is or would be used for the key. It is set regardless whether the key is in the hash_table. Returns: NULL if the key is not in the hash_table. Otherwise, the item associated with the key is returned.

void hash_table_foreach (  hash_table_t *  ht, hash_table_foreach_func  func, void *  data )

gboolean hash_table_insert (  hash_table_t *  ht, void *  key, void *  value )

Adds a new item to the hash_table. If the hash_table already contains an item with the same key, the old value is kept and FALSE is returned. Returns: FALSE if the item could not be added, TRUE on success.

void* hash_table_lookup (  hash_table_t *  ht, void *  key )

hash_table_t* hash_table_new (  void   )

void hash_table_new_intern (  hash_table_t *  ht, size_t  num_bins )

gboolean hash_table_remove (  hash_table_t *  ht, void *  key )

void hash_table_resize (  hash_table_t *  ht  )  [inline, static]

void hash_table_resize_helper (  void *  key, void *  value, void *  data )

size_t hash_table_size (  const hash_table_t *  ht  )

Checks how many items are currently in stored in the hash_table. Parameters: ht  the hash_table to check. Returns: the number of items in the hash_table.

void hash_table_status (  const hash_table_t *  ht  )

---