HashTable implementation in C + GLib

hash-table.c

/* This is free and unencumbered software released into the public domain.
 *
 * Anyone is free to copy, modify, publish, use, compile, sell, or distribute
 * this software, either in source code form or as a compiled binary, for any
 * purpose, commercial or non-commercial, and by any means.
 *
 * In jurisdictions that recognize copyright laws, the author or authors of this
 * software dedicate any and all copyright interest in the software to the public
 * domain. We make this dedication for the benefit of the public at large and to
 * the detriment of our heirs and successors. We intend this dedication to be an
 * overt act of relinquishment in perpetuity of all present and future rights to
 * this software under copyright law.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 * For more information, please refer to <http://unlicense.org/>
 */

#include <glib.h>

typedef struct _HashTable HashTable;
typedef struct _HashTableEntry HashTableEntry;
typedef struct _HashTableIterator HashTableIterator;

struct _HashTableEntry
{
  gchar *key;
  gpointer value;
  HashTableEntry *next;
};

struct _HashTableIterator
{
  HashTable *table;
  HashTableEntry *current;
  guint index;
};

struct _HashTable
{
  HashTableEntry **entries;
  guint entries_length;
  guint size;
};

HashTableEntry *
hash_table_entry_new (const gchar *key,
                      gpointer     value)
{
  HashTableEntry *self = g_slice_new0 (HashTableEntry);

  self->key = g_strdup (key);
  self->value = value;

  return self;
}

void
hash_table_entry_free (HashTableEntry *self)
{
  g_return_if_fail (self != NULL);

  g_clear_pointer (&self->key, g_free);
  g_clear_pointer (&self->value, g_free);

  g_slice_free (HashTableEntry, self);
}

HashTableIterator *
hash_table_iterator_new (HashTable *table)
{
  HashTableIterator *self;

  g_return_val_if_fail (table != NULL, NULL);

  self = g_slice_new0 (HashTableIterator);

  self->table = table;

  return self;
}

HashTableEntry *
hash_table_iterator_get (HashTableIterator *self)
{
  g_return_val_if_fail (self != NULL, NULL);
  return self->current;
}

gboolean
hash_table_iterator_next (HashTableIterator *self)
{
  g_return_val_if_fail (self != NULL, FALSE);

  if (self->current != NULL && self->current->next != NULL)
    {
      self->current = self->current->next;
      return TRUE;
    }

  while (self->index < self->table->entries_length)
    {
      guint i = self->index;
      self->index++;

      if (self->table->entries[i] != NULL)
        {
          self->current = self->table->entries[i];
          return TRUE;
        }
    }

  return FALSE;
}

void
hash_table_iterator_free (HashTableIterator *self)
{
  g_return_if_fail (self != NULL);
  g_slice_free (HashTableIterator, self);
}

HashTable *
hash_table_new (void)
{
  HashTable *self = g_slice_new0 (HashTable);

  self->entries = g_new0 (HashTableEntry *, 20);
  self->entries_length = 20U;

  return self;
}

guint
str_hash (const gchar *str)
{
  if (str == NULL)
    return 0U;

  return g_str_hash (str);
}

gconstpointer
hash_table_get (HashTable   *self,
                const gchar *key)
{
  guint hash, index;

  g_return_val_if_fail (self != NULL, NULL);

  hash = str_hash (key);
  index = hash % self->entries_length;

  if (self->entries[index] != NULL)
    {
      HashTableEntry *temp = self->entries[index];

      while (g_strcmp0 (key, temp->key) != 0 && temp->next != NULL)
        temp = temp->next;

      return temp->value;
    }

  return NULL;
}

void
hash_table_grow_if_needed (HashTable *self)
{
  g_return_if_fail (self != NULL);

  if (self->size < self->entries_length * 0.6)
    return;

  g_print ("Threshold crossed, resizing internal array...\n");

  /* To resize the array, we first call g_renew(), which will reallocate the
   * memory so that it now has twice as much space. Then we'll have to fill the 
   * empty space with 0 using memset(), since there's no g_renew0() to do it for
   * us. */
  self->entries = g_renew (HashTableEntry *, self->entries, self->entries_length * 2);
  memset (self->entries + self->entries_length, 0, sizeof (HashTableEntry *) * self->entries_length);
  self->entries_length *= 2;
}

void
hash_table_set (HashTable   *self,
                const gchar *key,
                gpointer     value)
{
  guint hash, index;
  HashTableEntry *temp;

  g_return_if_fail (self != NULL);

  hash_table_grow_if_needed (self);

  hash = str_hash (key);
  index = hash % self->entries_length;

  if (self->entries[index] == NULL)
    {
      g_print ("Key not found, creating new entry...\n");

      self->entries[index] = hash_table_entry_new (key, value);
      self->size++;

      return;
    }

  temp = self->entries[index];
  while (TRUE)
    {
      if (g_strcmp0 (key, temp->key) == 0)
        {
          g_print ("Key found, setting new value...\n");
          temp->value = value;

          return;
        }

      if (temp->next == NULL)
        break;

      temp = temp->next;
    }

  g_print ("Collision! Creating new linked entry...\n");

  temp->next = hash_table_entry_new (key, value);
  self->size++;
}

HashTableIterator *
hash_table_iterator (HashTable *self)
{
  g_return_val_if_fail (self != NULL, NULL);
  return hash_table_iterator_new (self);
}

void
hash_table_free (HashTable *self)
{
  guint i;

  g_return_if_fail (self != NULL);

  for (i = 0U; i < self->entries_length; i++)
    g_clear_pointer (&self->entries[i], hash_table_entry_free);

  g_clear_pointer (&self->entries, g_free);

  g_slice_free (HashTable, self);
}

gint
main (void)
{
  HashTableIterator *it;
  gint i;

  HashTable *table = hash_table_new ();

  for (i = 0; i < 50; i++)
    {
      gchar *key = g_uuid_string_random ();

      gint *pi = g_new0 (gint, 1);
      *pi = i;

      hash_table_set (table, key, pi);

      g_clear_pointer (&key, g_free);
    }

  it = hash_table_iterator (table);

  while (hash_table_iterator_next (it))
    {
      HashTableEntry *entry = hash_table_iterator_get (it);
      g_print ("Key: %s, Value: %i\n", entry->key, *(gint *) entry->value);
    }

  g_print ("\nSize: %u\n", table->size);

  g_clear_pointer (&it, hash_table_iterator_free);
  g_clear_pointer (&table, hash_table_free);

  return 0;
}