HashTable Struct Reference

#include <HashTable.h>

Overview

Hash tables with user-supplied hash and equality functions.

Definition at line 80 of file HashTable.h.

Inheritance diagram for HashTable:

Properties
size_t	count
	The number of entries.
Consumer	destroyKey
	Optional destructor called when a key is removed or replaced.
Consumer	destroyValue
	Optional destructor called when a value is removed or replaced.
HashTableEqualFunc	equal
	The equality function.
HashTableHashFunc	hash
	The hash function.
Object	object
	The superclass.
Properties inherited from Object
Class *	clazz
	Every instance of Object begins with a pointer to its Class.
unsigned int	magic
	A header to allow introspection of Object types.

Methods
Class *	_HashTable (void)
	The HashTable archetype.
bool	containsKey (const HashTable *self, const ident key)
void	enumerate (const HashTable *self, HashTableEnumerator enumerator, ident data)
	Enumerates the entries of this HashTable with the given function.
ident	get (const HashTable *self, const ident key)
HashTable *	init (HashTable *self, HashTableHashFunc hash, HashTableEqualFunc equal)
	Initializes this HashTable with the given hash and equality functions.
HashTable *	initWithCapacity (HashTable *self, HashTableHashFunc hash, HashTableEqualFunc equal, size_t capacity)
	Initializes this HashTable with the given capacity.
void	remove (HashTable *self, const ident key)
	Removes the entry for the given key.
void	removeAll (HashTable *self)
	Removes all entries from this HashTable.
void	set (HashTable *self, const ident key, const ident value)
	Sets the value for the given key, replacing any existing entry.
Methods inherited from Object
Class *	_Object (void)
	The Object archetype.
Object *	copy (const Object *self)
	Creates a shallow copy of this Object.
void	dealloc (Object *self)
	Frees all resources held by this Object.
String *	description (const Object *self)
int	hash (const Object *self)
Object *	init (Object *self)
	Initializes this Object.
bool	isEqual (const Object *self, const Object *other)
	Tests equality of the other Object.
bool	isKindOfClass (const Object *self, const Class *clazz)
	Tests for Class hierarchy membership.

Protected Attributes
HashTableEntry **	buckets
	The buckets.
size_t	capacity
	The number of buckets.
HashTableInterface *	interface
	The interface.
Protected Attributes inherited from Object
ObjectInterface *	interface
	The interface.

Property Details

buckets

HashTableEntry** HashTable::buckets

protected

The buckets.

Definition at line 108 of file HashTable.h.

capacity

size_t HashTable::capacity

protected

The number of buckets.

Definition at line 102 of file HashTable.h.

count

size_t HashTable::count

The number of entries.

Definition at line 96 of file HashTable.h.

destroyKey

Consumer HashTable::destroyKey

Optional destructor called when a key is removed or replaced.

Definition at line 123 of file HashTable.h.

destroyValue

Consumer HashTable::destroyValue

Optional destructor called when a value is removed or replaced.

Definition at line 128 of file HashTable.h.

equal

HashTableEqualFunc HashTable::equal

The equality function.

Definition at line 118 of file HashTable.h.

hash

HashTableHashFunc HashTable::hash

The hash function.

Definition at line 113 of file HashTable.h.

interface

HashTableInterface* HashTable::interface

protected

The interface.

Definition at line 91 of file HashTable.h.

object

Object HashTable::object

The superclass.

Definition at line 85 of file HashTable.h.

Method Details

_HashTable()

Class * _HashTable

(

void

)

The HashTable archetype.

Returns

The HashTable Class.

Definition at line 328 of file HashTable.c.

                        {
  static Class *clazz;
  static Once once;
 
  do_once(&once, {
    clazz = _initialize(&(const ClassDef) {
      .name = "HashTable",
      .superclass = _Object(),
      .instanceSize = sizeof(HashTable),
      .interfaceOffset = offsetof(HashTable, interface),
      .interfaceSize = sizeof(HashTableInterface),
      .initialize = initialize,
    });
  });
 
  return clazz;
}

containsKey()

bool containsKey	(	const HashTable *	self,
		const ident	key
	)

Parameters

self	The HashTable.
key	The key.

Returns

True if this HashTable contains the given key.

Definition at line 131 of file HashTable.c.

                                                                {
  return $(self, get, key) != NULL;
}

enumerate()

void enumerate	(	const HashTable *	self,
		HashTableEnumerator	enumerator,
		ident	data
	)

Enumerates the entries of this HashTable with the given function.

Parameters

self	The HashTable.
enumerator	The enumerator function.
data	User data.

Definition at line 139 of file HashTable.c.

                                                                                         {
 
  assert(enumerator);
 
  for (size_t i = 0; i < self->capacity; i++) {
    for (const HashTableEntry *e = self->buckets[i]; e; e = e->next) {
      enumerator(self, e->key, e->value, data);
    }
  }
}

get()

ident get	(	const HashTable *	self,
		const ident	key
	)

Parameters

self	The HashTable.
key	The key.

Returns

The value for the given key, or NULL if not found.

Definition at line 154 of file HashTable.c.

                                                         {
 
  const size_t bin = self->hash(key) % self->capacity;
 
  for (const HashTableEntry *e = self->buckets[bin]; e; e = e->next) {
    if (self->equal(e->key, key)) {
      return e->value;
    }
  }
 
  return NULL;
}

init()

HashTable * init	(	HashTable *	self,
		HashTableHashFunc	hash,
		HashTableEqualFunc	equal
	)

Initializes this HashTable with the given hash and equality functions.

Parameters

self	The HashTable.
hash	The hash function.
equal	The equality function.

Returns

The initialized HashTable, or NULL on error.

Definition at line 171 of file HashTable.c.

                                                                                          {
  return $(self, initWithCapacity, hash, equal, HASHTABLE_DEFAULT_CAPACITY);
}

initWithCapacity()

HashTable * initWithCapacity	(	HashTable *	self,
		HashTableHashFunc	hash,
		HashTableEqualFunc	equal,
		size_t	capacity
	)

Initializes this HashTable with the given capacity.

Parameters

self	The HashTable.
hash	The hash function.
equal	The equality function.
capacity	The initial bucket count.

Returns

The initialized HashTable, or NULL on error.

Definition at line 179 of file HashTable.c.

                                                                                                                       {
 
  self = (HashTable *) super(Object, self, init);
  if (self) {
    assert(hash);
    assert(equal);
    assert(capacity);
 
    self->hash = hash;
    self->equal = equal;
    self->capacity = capacity;
    self->buckets = calloc(self->capacity, sizeof(HashTableEntry *));
    assert(self->buckets);
  }
  return self;
}

remove()

void remove	(	HashTable *	self,
		const ident	key
	)

Removes the entry for the given key.

Parameters

self	The HashTable.
key	The key to remove.

removeAll()

void removeAll

(

HashTable *

self

)

Removes all entries from this HashTable.

Parameters

self	The HashTable.

Definition at line 227 of file HashTable.c.

                                       {
 
  for (size_t i = 0; i < self->capacity; i++) {
    HashTableEntry *e = self->buckets[i];
    while (e) {
      HashTableEntry *next = e->next;
      if (self->destroyKey) {
        self->destroyKey(e->key);
      }
      if (self->destroyValue) {
        self->destroyValue(e->value);
      }
      free(e);
      e = next;
    }
    self->buckets[i] = NULL;
  }
 
  self->count = 0;
}

set()

void set	(	HashTable *	self,
		const ident	key,
		const ident	value
	)

Sets the value for the given key, replacing any existing entry.

Parameters

self	The HashTable.
key	The key.
value	The value.

Definition at line 275 of file HashTable.c.

                                                                     {
 
  if ((float) self->count / (float) self->capacity >= HASHTABLE_MAX_LOAD) {
    resize(self, self->capacity * HASHTABLE_GROW_FACTOR);
  }
 
  const size_t bin = self->hash(key) % self->capacity;
 
  for (HashTableEntry *e = self->buckets[bin]; e; e = e->next) {
    if (self->equal(e->key, key)) {
      if (self->destroyKey) {
        self->destroyKey(e->key);
      }
      if (self->destroyValue) {
        self->destroyValue(e->value);
      }
      e->key = key;
      e->value = value;
      return;
    }
  }
 
  HashTableEntry *e = calloc(1, sizeof(HashTableEntry));
  assert(e);
  e->key = key;
  e->value = value;
  e->next = self->buckets[bin];
  self->buckets[bin] = e;
  self->count++;
}

---

The documentation for this struct was generated from the following files:

• Sources/Objectively/HashTable.h
• Sources/Objectively/HashTable.c