text: /*
   * 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 (sizeof (dictbucket), 1);
  
  	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 (sizeof (dictbucket *), num_buckets);
  
  			/* 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 (sizeof (dictbucket *), dict->num_buckets);
  		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;
  }
  