path: root/hash.c

/* -*- c-basic-offset: 4 indent-tabs-mode: nil -*- */
/*  Libnul - Another Utility Library
 *  Copyright (C) 2008  Søren Sandmann
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Library General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Library General Public License for more details.
 *
 *  You should have received a copy of the GNU Library General Public
 *  License along with this library; if not, write to the
 *  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 *  Boston, MA  02111-1307, USA.
 */
#include "libnul.h"

typedef struct hash_entry_t hash_entry_t;

struct hash_entry_t
{
    nul_ptr_t	key;
    nul_ptr_t	value;
};

/* Expand the table when more than 1/HIGH_OCCUPATION is in use.
 * Shrink the table when less than 1/LOW_OCCUPATION is in use
 * When resizing the table, size it such that 1/DEFAULT_OCCUPATION is in use
 */
#define HIGH_WATER(hash)	((((hash)->mask + 1) * 5) / 8)
#define LOW_WATER(hash)		(((hash)->mask + 1) / 8)
#define DEFAULT_OCCUPATION	4
#define MIN_SIZE		128

struct nul_hash_t
{
    hash_entry_t *		entries;

    nul_hash_func_t		hash_func;
    nul_hash_equal_func_t	equal_func;

    nul_free_func_t		value_free_func;
    nul_free_func_t		key_free_func;

    size_t			n_dead;
    size_t			n_live;
    size_t			mask;

    nul_ptr_t free_marker;	/* entry->value has this value when it's not in use */
    nul_ptr_t dead_marker;	/* entry->value has this value when it's a tombstone */
};

static nul_ptr_t
random_pointer (void)
{
    size_t ptr = 0;
    int i;

    for (i = 0; i < sizeof (ptr) * 8; ++i)
    {
	uint32_t bit = nul_random_boolean();

	ptr |= (bit << i);
    }

    return (nul_ptr_t)ptr;
}

static inline void
kill_entry (nul_hash_t *hash, hash_entry_t *entry)
{
    if (hash->key_free_func)
	hash->key_free_func (entry->key);

    if (hash->value_free_func)
	hash->value_free_func (entry->value);

    entry->value = hash->dead_marker;
    hash->n_live--;
    hash->n_dead++;
}

/* FIXME: consider double hashing instead of this
 */
static inline size_t
next_probe (size_t index, size_t mask)
{
    return (index + 1) & mask;
}

static inline void
insert_internal (nul_hash_t *hash, nul_ptr_t key, nul_ptr_t value)
{
    size_t index = hash->hash_func (key) & hash->mask;
    hash_entry_t *entry;

    entry = &(hash->entries[index]);

    while (entry->value != hash->free_marker && entry->value != hash->dead_marker)
    {
	if (hash->equal_func (entry->key, key))
	{
	    kill_entry (hash, entry);
	    break;
	}

	index = next_probe (index, hash->mask);

	entry = &(hash->entries[index]);
    }

    hash->n_live++;
    entry->key = key;
    entry->value = value;
}

static void
rehash (nul_hash_t *hash)
{
    hash_entry_t *old_entries;
    size_t new_size;
    size_t t;

    new_size = 1;
    while (new_size < MAX (hash->n_live * DEFAULT_OCCUPATION, MIN_SIZE))
	new_size *= 2;

    old_entries = hash->entries;

    hash->entries = nul_array_new (hash_entry_t);
    hash->entries = nul_array_set_size (hash->entries, new_size);
    hash->mask = new_size - 1;
    hash->n_live = 0;
    hash->n_dead = 0;

    for (t = 0; t < new_size; ++t)
    {
	hash_entry_t *entry = &(hash->entries[t]);

	entry->key = NULL;
	entry->value = hash->free_marker;
    }

    if (old_entries)
    {
	for (t = 0; t < nul_array_len (old_entries); ++t)
	{
	    hash_entry_t *entry = &(old_entries[t]);

	    if (entry->value != hash->free_marker && entry->value != hash->dead_marker)
		insert_internal (hash, entry->key, entry->value);
	}

	nul_array_free (old_entries);
    }
}

static void
regenerate_markers (nul_hash_t *hash, nul_ptr_t value)
{
    nul_ptr_t new_free_marker, old_free_marker;
    nul_ptr_t new_dead_marker, old_dead_marker;
    int i;

    old_dead_marker = hash->dead_marker;
    old_free_marker = hash->free_marker;

retry:
    new_free_marker = random_pointer();
    new_dead_marker = random_pointer();

    /* Check for collisions */
    if (new_free_marker == value			||
	new_free_marker == old_free_marker		||
	new_free_marker == old_dead_marker		||
	new_dead_marker == value			||
	new_dead_marker == old_free_marker		||
	new_dead_marker == old_dead_marker)
    {
	goto retry;
    }

    for (i = 0; i < nul_array_len (hash->entries); ++i)
    {
	hash_entry_t *entry = &(hash->entries[i]);

	if (entry->value == new_free_marker	||
	    entry->value == new_dead_marker)
	{
	    goto retry;
	}
    }

    /* Update entries */
    for (i = 0; i < nul_array_len (hash->entries); ++i)
    {
	hash_entry_t *entry = &(hash->entries[i]);

	if (entry->value == old_free_marker)
	    entry->value = new_free_marker;

	if (entry->value == old_dead_marker)
	    entry->value = new_dead_marker;
    }

    hash->dead_marker = new_dead_marker;
    hash->free_marker = new_free_marker;
}

nul_hash_t *
nul_hash_new (nul_hash_func_t        hash_func,
	      nul_hash_equal_func_t  equal_func,
	      nul_free_func_t        key_free_func,
	      nul_free_func_t        value_free_func)
{
    nul_hash_t *hash = g_new (nul_hash_t, 1);

    hash->hash_func = hash_func;
    hash->equal_func = equal_func;
    hash->key_free_func = key_free_func;
    hash->value_free_func = value_free_func;
    hash->free_marker = random_pointer();
    hash->dead_marker = random_pointer();

    hash->entries = NULL;
    hash->n_live = 0;
    hash->n_dead = 0;
    hash->mask = 0;

    rehash (hash);

    return hash;
}

static inline nul_bool_t
need_rehash (nul_hash_t *hash)
{
    if (hash->n_dead + hash->n_live > HIGH_WATER (hash))
	return TRUE;

    if (hash->mask + 1 == MIN_SIZE)
	return FALSE;

    if (hash->n_live < LOW_WATER (hash))
	return TRUE;

    return FALSE;
}

void
nul_hash_insert (nul_hash_t            *hash,
		 nul_ptr_t              key,
		 nul_ptr_t              value)
{
    if (G_UNLIKELY (value == hash->free_marker || value == hash->dead_marker))
	regenerate_markers (hash, value);

    insert_internal (hash, key, value);

    if (need_rehash (hash))
	rehash (hash);
}

static inline hash_entry_t *
find_entry (nul_hash_t *hash, nul_ptr_t key)
{
    size_t index = hash->hash_func (key) & hash->mask;
    hash_entry_t *entry;

    entry = &(hash->entries[index]);

    while (entry->value != hash->free_marker)
    {
	if (entry->value != hash->dead_marker && hash->equal_func (entry->key, key))
	    return entry;

	index = next_probe (index, hash->mask);
	entry = &(hash->entries[index]);
    }

    return NULL;
}

nul_ptr_t
nul_hash_lookup  (nul_hash_t            *hash,
		  nul_ptr_t              key)
{
    hash_entry_t *entry = find_entry (hash, key);

    if (entry)
	return entry->value;

    return NULL;
}

nul_bool_t
nul_hash_remove (nul_hash_t *hash,
		 nul_ptr_t key)
{
    hash_entry_t *entry = find_entry (hash, key);

    if (entry)
    {
	kill_entry (hash, entry);

	if (need_rehash (hash))
	    rehash (hash);

	return TRUE;
    }

    return FALSE;
}

nul_bool_t
nul_hash_has_key (nul_hash_t            *hash,
		  nul_ptr_t              key)
{
    return !!find_entry (hash, key);
}

void
nul_hash_free (nul_hash_t *hash)
{
    size_t i;

    for (i = 0; i < nul_array_len (hash->entries); ++i)
    {
	hash_entry_t *entry = &(hash->entries[i]);

	if (entry->value != hash->free_marker && entry->value != hash->dead_marker)
	    kill_entry (hash, entry);
    }

    nul_array_free (hash->entries);

    g_free (hash);
}