hashmap.c

/* hashmap - a rehashing hash map
 * Copyright (c) 2003 Michael B. Allen <mba2000 ioplex.com>
 *
 * The MIT License
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * 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 OR COPYRIGHT HOLDERS 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.
 */

#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <stdio.h>
#include <wchar.h>

#include "mba/msgno.h"
#include "mba/iterator.h"
#include "mba/allocator.h"
#include "mba/suba.h"
#include "mba/hashmap.h"


#define HAL(h) ((struct allocator *)((h)->al ? (char *)(h) - (ptrdiff_t)(h)->al : NULL))

#define TABLE_SIZES_SIZE 20
#define DELETED 1

const int table_sizes[] = {
  0,
  17,      31,      61,      131,
  257,     509,     1021,    2053,
  4099,    8191,    16381,   32771,
  65537,   131071,  262147,  524287,
  1048573, 2097143, 4194301, 8388617
};

struct entry {
  unsigned long hash;
  ref_t key;
  ref_t data;
};

unsigned long
hash_str(const void *str, void *context)
{
  unsigned long h = 5381;
  const unsigned char *s = (const unsigned char *)str;
  int c;

  if (context) { /* then str is ref and context is suba */
    s = (const unsigned char *)context + (size_t)str;
  }

  while ((c = *s++)) {
    h = ((h << 5) + h) + c;
  }

  return h;
}
unsigned long
hash_wcs(const void *wcs, void *context)
{
  unsigned long h = 5381;
  const wchar_t *s = (const wchar_t *)wcs;
  wint_t c;

  if (context) { /* then wcs is ref and context is suba */
    s = (const wchar_t *)context + (size_t)wcs;
  }

  while ((c = *s++)) {
    h = ((h << 5) + h) + c;
  }

  return h;
}
static unsigned long
hash_ptr(const void *ptr, void *context)
{
  unsigned long h = (unsigned long)ptr;

  if (context) {
    h = (unsigned long)((char *)context + (size_t)ptr);
  }

  return h;
}
int
cmp_str(const void *object1, const void *object2, void *context)
{
  const unsigned char *s1 = object1;
  const unsigned char *s2 = object2;
  const unsigned char *slim;

  if (context) {
    s1 = (const unsigned char *)context + (size_t)object1;
    s2 = (const unsigned char *)context + (size_t)object2;
    slim = (const unsigned char *)context + ((struct allocator *)context)->size;
  } else {
    slim = (const unsigned char *)-1;
  }

  while (s1 < slim && s2 < slim) {
    if (*s1 != *s2) {
      return *s1 < *s2 ? -1 : 1;
    } else if (*s1 == '\0') {
      return 0;
    }
    s1++;
    s2++;
  }

  return s2 < slim ? -1 : 1;
}
int
cmp_wcs(const void *object1, const void *object2, void *context)
{
  const wchar_t *s1 = object1;
  const wchar_t *s2 = object2;
  const wchar_t *slim;

  if (context) {
    s1 = (const wchar_t *)((char *)context + (size_t)object1);
    s2 = (const wchar_t *)((char *)context + (size_t)object2);
    slim = (const wchar_t *)((char *)context + ((struct allocator *)context)->size);
  } else {
    slim = (const wchar_t *)-1;
  }

  while (s1 < slim && s2 < slim) {
    if (*s1 != *s2) {
      return *s1 < *s2 ? -1 : 1;
    } else if (*s1 == '\0') {
      return 0;
    }
    s1++;
    s2++;
  }

  return s2 < slim ? -1 : 1;
}

int
hashmap_init(struct hashmap *h,
    unsigned int load_factor,
    hash_fn hash,
    cmp_fn cmp,
    void *context,
    struct allocator *al)
{
  memset(h, 0, sizeof *h);
  h->table_size_index = 0;
  h->hash = ALREF(al, hash);
  h->cmp = ALREF(al, cmp);
  h->context = ALREF(al, context);
  h->size = 0;
  if (load_factor == 0 || load_factor > 100) {
    h->load_factor_high = 75;
    h->load_factor_low = 18;
  } else {
    h->load_factor_high = load_factor;
    h->load_factor_low = load_factor / 4;
  }
  if (al && al->tail) { /* al is a suba allocator */
    h->al = (char *)h - (char *)al;
  }
  h->table = 0;

  return 0;
}
int
hashmap_deinit(struct hashmap *h, del_fn key_del, del_fn data_del, void *context)
{
  int ret = 0;

  if (h) {
    struct allocator *al = HAL(h);
    ret += hashmap_clear(h, key_del, data_del, context);
    ret += allocator_free(al, ALADR(al, h->table));
  }

  if (ret) {
    AMSG("");
    return -1;
  }

  return 0;
}
struct hashmap *
hashmap_new(hash_fn hash, cmp_fn cmp, void *context, struct allocator *al)
{
  struct hashmap *h;

  if ((h = allocator_alloc(al, sizeof *h, 0)) == NULL ||
        hashmap_init(h, 75, hash, cmp, context, al) == -1) {
    AMSG("");
    allocator_free(al, h);
    return NULL;
  }

  return h;
}
int
hashmap_del(struct hashmap *h, del_fn key_del, del_fn data_del, void *context)
{
  int ret = 0;

  if (h) {
    ret += hashmap_deinit(h, key_del, data_del, context);
    ret += allocator_free(HAL(h), h);
  }

  if (ret) {
    AMSG("");
    return -1;
  }

  return 0;
}
int
hashmap_clear(struct hashmap *h, del_fn key_del, del_fn data_del, void *context)
{
  int ret = 0;

  if (h->table) {
    int idx, table_size;
    struct allocator *al = HAL(h);
    struct entry *table = ALADR(al, h->table);

    table_size = table_sizes[h->table_size_index];

    for (idx = 0; idx < table_size; idx++) {
      struct entry *e = table + idx;

      if (e->key > DELETED) {
        void *k = ALADR(al, e->key);

        if (key_del)
          ret += key_del(context, k);
        if (data_del)
          ret += data_del(context, ALADR(al, e->data));
      }
    }

    ret += allocator_free(al, table);

    h->table_size_index = 0;
    h->size = 0;
    h->table = 0;
  }

  if (ret) {
    AMSG("");
    return -1;
  }

  return 0;
}
int
hashmap_clean(struct hashmap *h)
{
  (void)h; /* TODO */
  return 0;
}
static int
hashmap_resize(struct hashmap *h, int new_table_size_index)
{
  struct entry *old_table, *oe;
  int old_table_size, table_size, i;
  struct allocator *al = HAL(h);

  if ((oe = allocator_alloc(al, table_sizes[new_table_size_index] * sizeof *oe, 1)) == NULL) {
    AMSG("");
    return -1;
  }

  old_table_size = table_sizes[h->table_size_index];
  old_table = ALADR(al, h->table);
  h->table_size_index = new_table_size_index;
  h->table = ALREF(al, oe);

  if (old_table == NULL) {
    return 0;
  }

  table_size = table_sizes[h->table_size_index];
  for (i = 0; i < old_table_size; i++) {
    oe = old_table + i;

    if (oe->key > DELETED) {
      int idx, rehash_adv;
      struct entry *e;

      idx = oe->hash % table_size;
      rehash_adv = 1 + oe->hash % (table_size - 2);

      for ( ;; ) {
        e = (struct entry *)ALADR(al, h->table) + idx;

        if (e->key == 0) {
          *e = *oe;
          break;
        }

        idx = (idx + rehash_adv) % table_size;
      }
    }
  }

  if (allocator_free(al, old_table) == -1) {
    AMSG("");
    return -1;
  }

  return 0;
}
int
hashmap_put(struct hashmap *h, void *key, void *data)
{
  unsigned long hash;
  int idx, rehash_adv, count, table_size;
  struct entry *e;
  struct allocator *al = HAL(h);

  if (h->table_size_index == 0 ||
        ((h->size * 100 / table_sizes[h->table_size_index]) >= h->load_factor_high &&
        h->table_size_index < TABLE_SIZES_SIZE)) {
    if (hashmap_resize(h, h->table_size_index + 1) == -1) {
      AMSG("");
      return -1;
    }
  }

  hash = h->hash ? ((hash_fn)ALADR(al, h->hash))(key, ALADR(al, h->context)) : hash_ptr(key, ALADR(al, h->context));
  table_size = table_sizes[h->table_size_index];
  idx = hash % table_size;
  rehash_adv = 1 + hash % (table_size - 2);

  count = table_size;
  do {
    e = (struct entry *)ALADR(al, h->table) + idx;
    if (e->key <= DELETED) {
      break;
    } else {
      void *k = ALADR(al, e->key);

      if (hash == e->hash && (h->cmp ? ((cmp_fn)ALADR(al, h->cmp))(key, k, ALADR(al, h->context)) == 0 : key == k)) {
        errno = EEXIST;
        PMNO(errno);
        return -1;
      }
    }
    idx = (idx + rehash_adv) % table_size;
  } while(--count);

  if (!count) {
    errno = ENOSPC;
    PMNO(errno);
    return -1;
  }

  e->hash = hash;
  e->key = ALREF(al, key);
  e->data = ALREF(al, data);
  h->size++;

  return 0;
}
void *
hashmap_get(const struct hashmap *h, const void *key)
{
  if (h->table) {
    unsigned long hash;
    int idx, rehash_adv, count, table_size;
    struct entry *e;
    struct allocator *al = HAL(h);

    hash = h->hash ? ((hash_fn)ALADR(al, h->hash))(key, ALADR(al, h->context)) : hash_ptr(key, ALADR(al, h->context));
    table_size = table_sizes[h->table_size_index];
    idx = hash % table_size;
    rehash_adv = 1 + hash % (table_size - 2);

    count = table_size;
    do {
      e = (struct entry *)ALADR(al, h->table) + idx;
      if (e->key == 0) {
        break;
      } else if (e->key != DELETED) {
        void *k = ALADR(al, e->key);

        if (hash == e->hash && (h->cmp ? ((cmp_fn)ALADR(al, h->cmp))(key, k, ALADR(al, h->context)) == 0 : key == k)) {
          return ALADR(al, e->data);
        }
      }
      idx = (idx + rehash_adv) % table_size;
    } while(count--);
  }

  return NULL;
}
int
hashmap_remove(struct hashmap *h, void **key, void **data)
{
  if (h->table) {
    unsigned long hash;
    int idx, rehash_adv, count, table_size;
    struct entry *e;
    struct allocator *al = HAL(h);

    if (h->table_size_index > 1 &&
          (h->size * 100 / table_sizes[h->table_size_index]) < h->load_factor_low) {
      if (hashmap_resize(h, h->table_size_index - 1) == -1) {
        AMSG("");
        return -1;
      }
    }

    hash = h->hash ? ((hash_fn)ALADR(al, h->hash))(*key, ALADR(al, h->context)) : hash_ptr(*key, ALADR(al, h->context));
    table_size = table_sizes[h->table_size_index];
    idx = hash % table_size;
    rehash_adv = 1 + hash % (table_size - 2);

    count = table_size;
    do {
      e = (struct entry *)ALADR(al, h->table) + idx;
      if (e->key == 0) {
        break;
      } else if (e->key != DELETED) {
        void *k = ALADR(al, e->key);

        if (hash == e->hash && (h->cmp ? ((cmp_fn)ALADR(al, h->cmp))(*key, k, ALADR(al, h->context)) == 0 : *key == k)) {
          *key = k;
          *data = ALADR(al, e->data);
          e->key = DELETED;
          h->size--;
          return 0;
        }
      }
      idx = (idx + rehash_adv) % table_size;
    } while(count--);
  }

  *data = NULL;

  errno = ENOENT;
  PMNO(errno);

  return -1;
}
int
hashmap_is_empty(struct hashmap *h)
{
  return h == NULL || h->size == 0;
}
unsigned int
hashmap_size(struct hashmap *h)
{
  return h ? h->size : 0;
}
void
hashmap_iterate(void *h, iter_t *iter)
{
  memset(iter, 0, sizeof *iter);
  (void)h;
}
void *
hashmap_next(void *h0, iter_t *iter)
{
  struct hashmap *h = h0;

  if (h->table) {
    int idx, table_size;
    struct entry *e;
    struct allocator *al = HAL(h);

    table_size = table_sizes[h->table_size_index];

    idx = iter->i2;
    while (idx < table_size) {
      e = (struct entry *)ALADR(al, h->table) + idx++;
      if (e->key > DELETED) {
        iter->i2 = idx;
        return ALADR(al, e->key);
      }
    }
  }

  return NULL;
}