HashTable.c File Reference

#include "Config.h"
#include <assert.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include "Hash.h"
#include "HashTable.h"

Go to the source code of this file.

Macros
#define	_Class   _HashTable
#define	HASHTABLE_DEFAULT_CAPACITY   16
#define	HASHTABLE_GROW_FACTOR   2
#define	HASHTABLE_MAX_LOAD   0.75f

Functions
Class *	_HashTable (void)
static void	_remove (HashTable *self, const ident key)
static bool	containsKey (const HashTable *self, const ident key)
static void	dealloc (Object *self)
static void	enumerate (const HashTable *self, HashTableEnumerator enumerator, ident data)
static ident	get (const HashTable *self, const ident key)
bool	HashTableEqualDirect (const ident a, const ident b)
bool	HashTableEqualStr (const ident a, const ident b)
bool	HashTableEqualStri (const ident a, const ident b)
size_t	HashTableHashDirect (const ident key)
size_t	HashTableHashStr (const ident key)
	Common hash functions for use with HashTable.
size_t	HashTableHashStri (const ident key)
static HashTable *	init (HashTable *self, HashTableHashFunc hash, HashTableEqualFunc equal)
static void	initialize (Class *clazz)
static HashTable *	initWithCapacity (HashTable *self, HashTableHashFunc hash, HashTableEqualFunc equal, size_t capacity)
static void	removeAll (HashTable *self)
static void	resize (HashTable *self, size_t capacity)
	Rehashes all entries into a new bucket array of the given capacity.
static void	set (HashTable *self, const ident key, const ident value)

Macro Definition Documentation

_Class

#define _Class   _HashTable

Definition at line 34 of file HashTable.c.

HASHTABLE_DEFAULT_CAPACITY

#define HASHTABLE_DEFAULT_CAPACITY   16

Definition at line 36 of file HashTable.c.

HASHTABLE_GROW_FACTOR

#define HASHTABLE_GROW_FACTOR   2

Definition at line 37 of file HashTable.c.

HASHTABLE_MAX_LOAD

#define HASHTABLE_MAX_LOAD   0.75f

Definition at line 38 of file HashTable.c.

Function Documentation

_HashTable()

Class * _HashTable

(

void

)

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;
}

_remove()

static void _remove ( HashTable *  self, const ident  key  )

static

Definition at line 200 of file HashTable.c.

                                                      {
 
  const size_t bin = self->hash(key) % self->capacity;
 
  HashTableEntry **e = &self->buckets[bin];
  while (*e) {
    if (self->equal((*e)->key, key)) {
      HashTableEntry *found = *e;
      *e = found->next;
      if (self->destroyKey) {
        self->destroyKey(found->key);
      }
      if (self->destroyValue) {
        self->destroyValue(found->value);
      }
      free(found);
      self->count--;
      return;
    }
    e = &(*e)->next;
  }
}

containsKey()

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

static

Definition at line 131 of file HashTable.c.

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

dealloc()

static void dealloc ( Object *  self )

static

See also

Object::dealloc(Object *)

Definition at line 101 of file HashTable.c.

                                  {
 
  HashTable *this = (HashTable *) self;
 
  for (size_t i = 0; i < this->capacity; i++) {
    HashTableEntry *e = this->buckets[i];
    while (e) {
      HashTableEntry *next = e->next;
      if (this->destroyKey) {
        this->destroyKey(e->key);
      }
      if (this->destroyValue) {
        this->destroyValue(e->value);
      }
      free(e);
      e = next;
    }
  }
 
  free(this->buckets);
 
  super(Object, self, dealloc);
}

enumerate()

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

static

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()

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

static

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;
}

HashTableEqualDirect()

bool HashTableEqualDirect	(	const ident	a,
		const ident	b
	)

See also

HashTableEqualDirect

Definition at line 92 of file HashTable.c.

                                                        {
  return a == b;
}

HashTableEqualStr()

bool HashTableEqualStr	(	const ident	a,
		const ident	b
	)

See also

HashTableEqualStr

Definition at line 58 of file HashTable.c.

                                                     {
  return strcmp((const char *) a, (const char *) b) == 0;
}

HashTableEqualStri()

bool HashTableEqualStri	(	const ident	a,
		const ident	b
	)

See also

HashTableEqualStri

Definition at line 78 of file HashTable.c.

                                                      {
  return strcasecmp((const char *) a, (const char *) b) == 0;
}

HashTableHashDirect()

size_t HashTableHashDirect

(

const ident

key

)

See also

HashTableHashDirect

Definition at line 85 of file HashTable.c.

                                            {
  return (size_t) (uintptr_t) key;
}

HashTableHashStr()

size_t HashTableHashStr

(

const ident

key

)

Common hash functions for use with HashTable.

See also

HashTableHashStr

Definition at line 45 of file HashTable.c.

                                         {
  const char *s = (const char *) key;
  size_t h = 5381;
  int c;
  while ((c = *s++)) {
    h = ((h << 5) + h) + (size_t) c;
  }
  return h;
}

HashTableHashStri()

size_t HashTableHashStri

(

const ident

key

)

See also

HashTableHashStri

Definition at line 65 of file HashTable.c.

                                          {
  const char *s = (const char *) key;
  size_t h = 5381;
  int c;
  while ((c = *s++)) {
    h = ((h << 5) + h) + (size_t) tolower(c);
  }
  return h;
}

init()

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

static

Definition at line 171 of file HashTable.c.

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

initialize()

static void initialize ( Class *  clazz )

static

See also

Class::initialize(Class *)

Definition at line 310 of file HashTable.c.

                                     {
 
  ((ObjectInterface *) clazz->interface)->dealloc = dealloc;
 
  ((HashTableInterface *) clazz->interface)->containsKey = containsKey;
  ((HashTableInterface *) clazz->interface)->enumerate = enumerate;
  ((HashTableInterface *) clazz->interface)->get = get;
  ((HashTableInterface *) clazz->interface)->init = init;
  ((HashTableInterface *) clazz->interface)->initWithCapacity = initWithCapacity;
  ((HashTableInterface *) clazz->interface)->remove = _remove;
  ((HashTableInterface *) clazz->interface)->removeAll = removeAll;
  ((HashTableInterface *) clazz->interface)->set = set;
}

initWithCapacity()

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

static

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;
}

removeAll()

static void removeAll ( HashTable *  self )

static

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;
}

resize()

static void resize ( HashTable *  self, size_t  capacity  )

static

Rehashes all entries into a new bucket array of the given capacity.

Definition at line 251 of file HashTable.c.

                                                     {
 
  HashTableEntry **buckets = calloc(capacity, sizeof(HashTableEntry *));
  assert(buckets);
 
  for (size_t i = 0; i < self->capacity; i++) {
    for (HashTableEntry *e = self->buckets[i]; e; ) {
      HashTableEntry *next = e->next;
      const size_t bin = self->hash(e->key) % capacity;
      e->next = buckets[bin];
      buckets[bin] = e;
      e = next;
    }
  }
 
  free(self->buckets);
  self->buckets = buckets;
  self->capacity = capacity;
}

set()

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

static

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++;
}