/*

 * Copyright (c) 2004 Stefan Walter

 * Copyright (c) 2011 Collabora Ltd.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 *

 *     * Redistributions of source code must retain the above

 *       copyright notice, this list of conditions and the

 *       following disclaimer.

 *     * Redistributions in binary form must reproduce the

 *       above copyright notice, this list of conditions and

 *       the following disclaimer in the documentation and/or

 *       other materials provided with the distribution.

 *     * The names of contributors to this software may not be

 *       used to endorse or promote products derived from this

 *       software without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS

 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE

 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,

 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,

 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS

 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED

 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,

 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF

 * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH

 * DAMAGE.

 */

#include "config.h"

#include "debug.h"

#include "dict.h"

#include "hash.h"

#include <sys/types.h>

#include <assert.h>

#include <stdint.h>

#include <stdlib.h>

#include <string.h>

struct _p11_dict {

  p11_dict_hasher hash_func;

  p11_dict_equals equal_func;

  p11_destroyer key_destroy_func;

  p11_destroyer value_destroy_func;

  struct _p11_dictbucket **buckets;

  unsigned int num_items;

  unsigned int num_buckets;

};

typedef struct _p11_dictbucket {

  void *key;

  unsigned int hashed;

  void *value;

  struct _p11_dictbucket *next;

} dictbucket;

static dictbucket *

next_entry (p11_dictiter *iter)

{

  dictbucket *bucket = iter->next;

  while (!bucket) {

    if (iter->index >= iter->dict->num_buckets)

      return NULL;

    bucket = iter->dict->buckets[iter->index++];

  }

  iter->next = bucket->next;

  return bucket;

}

bool

p11_dict_next (p11_dictiter *iter,

               void **key,

               void **value)

{

  dictbucket *bucket = next_entry (iter);

  if (bucket == NULL)

    return false;

  if (key)

    *key = bucket->key;

  if (value)

    *value = bucket->value;

  return true;

}

void

p11_dict_iterate (p11_dict *dict,

                  p11_dictiter *iter)

{

  iter->dict = dict;

  iter->index = 0;

  iter->next = NULL;

}

static dictbucket **

lookup_or_create_bucket (p11_dict *dict,

                         const void *key,

                         bool create)

{

  dictbucket **bucketp;

  unsigned int hash;

  /* Perform the hashing */

  hash = dict->hash_func (key);

  /* scan linked list */

  for (bucketp = &dict->buckets[hash % dict->num_buckets];

       *bucketp != NULL; bucketp = &(*bucketp)->next) {

    if((*bucketp)->hashed == hash && dict->equal_func ((*bucketp)->key, key))

      break;

  }

  if ((*bucketp) != NULL || !create)

    return bucketp;

  /* add a new entry for non-NULL val */

  (*bucketp) = calloc (1, sizeof (dictbucket));

  if (*bucketp != NULL) {

    (*bucketp)->key = (void*)key;

    (*bucketp)->hashed = hash;

    dict->num_items++;

  }

  return bucketp;

}

void *

p11_dict_get (p11_dict *dict,

              const void *key)

{

  dictbucket **bucketp;

  bucketp = lookup_or_create_bucket (dict, key, false);

  if (bucketp && *bucketp)

    return (void*)((*bucketp)->value);

  else

    return NULL;

}

bool

p11_dict_set (p11_dict *dict,

              void *key,

              void *val)

{

  dictbucket **bucketp;

  p11_dictiter iter;

  dictbucket *bucket;

  dictbucket **new_buckets;

  unsigned int num_buckets;

  bucketp = lookup_or_create_bucket (dict, key, true);

  if(bucketp && *bucketp) {

    /* Destroy the previous key */

    if ((*bucketp)->key && (*bucketp)->key != key && dict->key_destroy_func)

      dict->key_destroy_func ((*bucketp)->key);

    /* Destroy the previous value */

    if ((*bucketp)->value && (*bucketp)->value != val && dict->value_destroy_func)

      dict->value_destroy_func ((*bucketp)->value);

    /* replace entry */

    (*bucketp)->key = key;

    (*bucketp)->value = val;

    /* check that the collision rate isn't too high */

    if (dict->num_items > dict->num_buckets) {

      num_buckets = dict->num_buckets * 2 + 1;

      new_buckets = (dictbucket **)calloc (num_buckets, sizeof (dictbucket *));

      /* Ignore failures, maybe we can expand later */

      if(new_buckets) {

        p11_dict_iterate (dict, &iter);

        while ((bucket = next_entry (&iter)) != NULL) {

          unsigned int i = bucket->hashed % num_buckets;

          bucket->next = new_buckets[i];

          new_buckets[i] = bucket;

        }

        free (dict->buckets);

        dict->buckets = new_buckets;

        dict->num_buckets = num_buckets;

      }

    }

    return true;

  }

  return_val_if_reached (false);

}

bool

p11_dict_steal (p11_dict *dict,

                const void *key,

                void **stolen_key,

                void **stolen_value)

{

  dictbucket **bucketp;

  bucketp = lookup_or_create_bucket (dict, key, false);

  if (bucketp && *bucketp) {

    dictbucket *old = *bucketp;

    *bucketp = (*bucketp)->next;

    --dict->num_items;

    if (stolen_key)

      *stolen_key = old->key;

    if (stolen_value)

      *stolen_value = old->value;

    free (old);

    return true;

  }

  return false;

}

bool

p11_dict_remove (p11_dict *dict,

                 const void *key)

{

  void *old_key;

  void *old_value;

  if (!p11_dict_steal (dict, key, &old_key, &old_value))

    return false;

  if (dict->key_destroy_func)

    dict->key_destroy_func (old_key);

  if (dict->value_destroy_func)

    dict->value_destroy_func (old_value);

  return true;

}

void

p11_dict_clear (p11_dict *dict)

{

  dictbucket *bucket, *next;

  unsigned int i;

  /* Free all entries in the array */

  for (i = 0; i < dict->num_buckets; ++i) {

    bucket = dict->buckets[i];

    while (bucket != NULL) {

      next = bucket->next;

      if (dict->key_destroy_func)

        dict->key_destroy_func (bucket->key);

      if (dict->value_destroy_func)

        dict->value_destroy_func (bucket->value);

      free (bucket);

      bucket = next;

    }

  }

  memset (dict->buckets, 0, dict->num_buckets * sizeof (dictbucket *));

  dict->num_items = 0;

}

p11_dict *

p11_dict_new (p11_dict_hasher hash_func,

              p11_dict_equals equal_func,

              p11_destroyer key_destroy_func,

              p11_destroyer value_destroy_func)

{

  p11_dict *dict;

  assert (hash_func);

  assert (equal_func);

  dict = malloc (sizeof (p11_dict));

  if (dict) {

    dict->hash_func = hash_func;

    dict->equal_func = equal_func;

    dict->key_destroy_func = key_destroy_func;

    dict->value_destroy_func = value_destroy_func;

    dict->num_buckets = 9;

    dict->buckets = (dictbucket **)calloc (dict->num_buckets, sizeof (dictbucket *));

    if (!dict->buckets) {

      free (dict);

      return NULL;

    }

    dict->num_items = 0;

  }

  return dict;

}

void

p11_dict_free (p11_dict *dict)

{

  dictbucket *bucket;

  p11_dictiter iter;

  if (!dict)

    return;

  p11_dict_iterate (dict, &iter);

  while ((bucket = next_entry (&iter)) != NULL) {

    if (dict->key_destroy_func)

      dict->key_destroy_func (bucket->key);

    if (dict->value_destroy_func)

      dict->value_destroy_func (bucket->value);

    free (bucket);

  }

  if (dict->buckets)

    free (dict->buckets);

  free (dict);

}

unsigned int

p11_dict_size (p11_dict *dict)

{

  return dict->num_items;

}

unsigned int

p11_dict_str_hash (const void *string)

{

  uint32_t hash;

  p11_hash_murmur3 (&hash, string, strlen (string), NULL);

  return hash;

}

bool

p11_dict_str_equal (const void *string_one,

                    const void *string_two)

{

  assert (string_one);

  assert (string_two);

  return strcmp (string_one, string_two) == 0;

}

unsigned int

p11_dict_ulongptr_hash (const void *to_ulong)

{

  assert (to_ulong);

  return (unsigned int)*((unsigned long*)to_ulong);

}

bool

p11_dict_ulongptr_equal (const void *ulong_one,

                         const void *ulong_two)

{

  assert (ulong_one);

  assert (ulong_two);

  return *((unsigned long*)ulong_one) == *((unsigned long*)ulong_two);

}

unsigned int

p11_dict_intptr_hash (const void *to_int)

{

  assert (to_int);

  return (unsigned int)*((int*)to_int);

}

bool

p11_dict_intptr_equal (const void *int_one,

                        const void *int_two)

{

  assert (int_one);

  assert (int_two);

  return *((int*)int_one) == *((int*)int_two);

}

unsigned int

p11_dict_direct_hash (const void *ptr)

{

  return (unsigned int)(size_t)ptr;

}

bool

p11_dict_direct_equal (const void *ptr_one,

                       const void *ptr_two)

{

  return ptr_one == ptr_two;

}