/*! Sunrise Data Dictionary Library
 *
 *  @brief a library for hashtable storage of arbitrary data objects
 *  with built-in reference counting and guaranteed order iteration.
 *
 *  @file dd_data_dictionary.c
 *  general purpose data dictionary
 *
 *  @author Benjamin Kowarsch <nospam://com.sunrise-tel/~firstname~>
 *
 *  @note The author's true email address is herewith specifically excluded
 *  from the license of this software.  You are _not permitted_ to make the
 *  author's true email address available to any third party.  You may only
 *  pass on the modified version of the email address as presented above.
 *
 * (C) 2006 Sunrise Telephone Systems Ltd. All rights reserved.
 *
 * @cond LICENSE_TERMS
 *
 * 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.
 *
 * Under no circumstances is it permitted for any licensee to take credit for
 * the creation of  the Software,  to claim  authorship  or  ownership in the
 * Software  or in any other way  give the impression  that they have created
 * the Software.  Credit to the  true authors  and  copyright holders  of the
 * Software is absolutely mandatory and must be given as follows:
 *
 * Software packages incorporating the Software or substantial portions of it
 * shall display  a copyright notice  for the Software  in the same manner as
 * they  display  any  other copyright notice;  shall  display  an authorship
 * notice  for  the Software  in the  same manner  as they display  any other
 * authorship notice;  and shall display  the license terms or a reference to
 * the license terms of the Software  in the same manner  as they display any
 * other license or license reference.
 *
 * GUI-based or GUI-alike  interactive installers  installing the Software or
 * substantial portions of it, shall display the Software's copyright notice,
 * authorship notice  and  license terms  in  full  during  the  installation
 * process.  Other installers such as shell command driven package installers
 * on Unix systems shall display copyright,  authorship  and  license  in the
 * same  manner  as for  any other software.  Installers shall allow users to
 * install the license file for the Software along with the Software itself.
 *
 * Software  which makes use of  but  does not incorporate,  nor bundle,  nor
 * install the Software  or substantial portions of it,  is  NOT  required to
 * display any copyright, authorship, license terms  or license reference for
 * the Software.  Static linking to the Software constitutes 'incorporating',
 * dynamic linking to the Software constitutes 'making use 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.
 *
 * In countries and territories  where  the  above  no-warranty disclaimer is
 * not permissible by applicable law, the following terms apply:
 *
 * NO PERMISSION TO USE THE SOFTWARE IS GRANTED  AND THE SOFTWARE MUST NOT BE
 * USED AT ALL  IN SUCH COUNTRIES AND TERRITORIES WHERE THE ABOVE NO-WARRANTY
 * DISCLAIMER IS NOT PERMISSIBLE AND INVALIDATED BY APPLICABLE LAW.  HOWEVER,
 * THE COPYRIGHT HOLDERS HEREBY WAIVE THEIR RIGHT TO PURSUE OFFENDERS AS LONG
 * AS THEY OTHERWISE ABIDE BY THE TERMS OF THE LICENSE  AS APPLICABLE FOR USE
 * OF THE SOFTWARE  IN COUNTRIES AND TERRITORIES WHERE THE ABOVE  NO-WARRANTY
 * DISCLAIMER IS PERMITTED BY APPLICABLE LAW. THIS WAIVER DOES NOT CONSTITUTE
 * A LICENSE TO USE THE SOFTWARE IN COUNTRIES AND TERRITORIES WHERE THE ABOVE
 * NO-WARRANTY DISCLAIMER IS  NOT PERMISSIBLE  AND  INVALIDATED BY APPLICABLE
 * LAW.  ANY LIABILITY OF ANY KIND IS CATEGORICALLY RULED OUT AT ALL TIMES.
 *
 * @endcond
 */

#include <stddef.h>
#include <stdlib.h>
#include <unistd.h>
#if (DD_USE_BOEHM_GC)
#include <gc.h>
#endif
#if (DD_USE_PTHREADS)
#include <pthread.h>
#endif

#include "dd_types.h"
#include "dd_settings.pp"
#include "dd_hash_functions.h"
#include "dd_hashtable_size.h"
#include "dd_data_dictionary.h"


// ==========================================================================
// P R I V A T E   M A C R O S
// ==========================================================================

// --------------------------------------------------------------------------
// macro: insert a fillbyte for alignment, pass <n> to avoid name conflicts
// --------------------------------------------------------------------------

#define __fillbyte(n) octett_t _unused_ ## n


// ==========================================================================
// P R I V A T E   D A T A
// ==========================================================================

// --------------------------------------------------------------------------
// private datatype:  _dictionary
// --------------------------------------------------------------------------
//
// _dictionary header, holds parameters and counters
//  +------------------------+
//  | marked_for_disposal    |  whether dictionary is scheduled for deletion
//  +------------------------+
//  | disposal_in_progress   |  whether dictionary is being deleted
//  +------------------------+
//  | hashtable_size         |  number of buckets in hashtable
//  +------------------------+
//  | buckets_in_use         |  number of hashtable buckets in use
//  +------------------------+
//  | pending_lookups        |  number of lookups in progress
//  +------------------------+
//  | pending_inserts        |  number of inserts in progress
//  +------------------------+
//  | retained_entries       |  number of entries being retained
//  +------------------------+
//  | entry_count            |  number of objects stored in this dictionary
//  +------------------------+
//  | hash_string            |  hash function to calculate hash values
//  +------------------------+
//  | copy_object            |  object content copy function
//  +------------------------+
//  | will_insert_object     |  event handler for DD_WILL_INSERT_OBJECT
//  +------------------------+
//  | did_insert_object      |  event handler for DD_DID_INSERT_OBJECT
//  +------------------------+
//  | will_remove_object     |  event handler for DD_WILL_REMOVE_OBJECT
//  +------------------------+
//  | did_remove_object      |  event handler for DD_DID_REMOVE_OBJECT
//  +------------------------+
//  | will_dispose_dict      |  event handler for DD_WILL_DISPOSE_DICT
//  +------------------------+
//  | did_dispose_dict       |  event handler for DD_DID_DISPOSE_DICT
//  +------------------------+
//
// _dictionary body, holds linked list and hashtable
//  +------------------------+
//  | first_entry            |  -----> pointer to first entry added
//  +------------------------+
//  | last entry             |  -----> pointer to last entry added
//  +------------------------+
//  | bucket[0]              |  -----> pointer to _dict_entry or NULL
//  +------------------------+
//  | bucket[1]              |  -----> pointer to _dict_entry or NULL
//  +------------------------+
//  | bucket[2]              |  -----> pointer to _dict_entry or NULL
//  +------------------------+
//  .                        .
//  .                        .
//  +------------------------+
//  | bucket[n]              |  -----> pointer to _dict_entry or NULL
//  +------------------------+

typedef struct _dictionary {
    /* dictionary header */
	bool
        marked_for_disposal,
        disposal_in_progress;
	_MUTEX(disposal_lock);
	word_t _ATTR(align2)
        hashtable_size,
        buckets_in_use,
		pending_lookups,
		pending_inserts,
		retained_entries,
        entry_count;
	dd_hash_function hash_string;
	dd_object_copy_function copy_object;
	dd_object_event_handler
		will_insert_object,
		did_insert_object,
		will_remove_object,
		did_remove_object,
        will_dispose_dict,
        did_dispose_dict;
    /* linked list */
	struct _dict_entry
        *first_entry,
        *last_entry,
    /* hashtable */
        *bucket[0];
} _dictionary _ATTR(aligned);


// --------------------------------------------------------------------------
// private datatype:  _dict_entry
// --------------------------------------------------------------------------
//
// _dict_entry
//  +--------------------+
//  | marked_for_removal |  whether entry is scheduled for deletion
//  +--------------------+
//  | lock               |  mutex lock, only if DD_USE_PTHREADS is true
//  +--------------------+
//  | hash               |  hash value of this entry's key
//  +--------------------+
//  | retain_count       |  number of times this entry has been retained
//  +--------------------+
//  | object             |  -----> pointer to stored object
//  +--------------------+
//  | next               |  -----> pointer to next entry on collision
//  +--------------------+
//  | previously_added   |  -----> pointer to previously added entry
//  +--------------------+
//  | subsequently_added |  -----> pointer to subsequently added entry
//  +--------------------+
//  | key[0]             |  key, first character
//  +--------------------+
//  | key[1]             |  key, second character
//  +--------------------+
//  .                    .
//  .                    .
//  +--------------------+
//  | key[n]             |  key, terminating character
//  +--------------------+

typedef struct _dict_entry {
	bool marked_for_removal;
	__fillbyte(1);
	__fillbyte(2);
	__fillbyte(3);
	_MUTEX(lock);
    cardinal _ATTR(aligned)
	   hash,
       retain_count;
    void *object;
    struct _dict_entry
	   *next,
       *previously_added,    // iterative predecessor
       *subsequently_added ; // iterative successor
    char key[0];
} _dict_entry _ATTR(aligned);


// --------------------------------------------------------------------------
// private datatype:  _entry_ptr
// --------------------------------------------------------------------------
//
// Pointer to _dict_entry

typedef _dict_entry * _entry_ptr;


// --------------------------------------------------------------------------
// private datatype:  _enumerator
// --------------------------------------------------------------------------
//
// _enumerator
//  +--------------------+
//  | dict               |  -----> pointer to dictionary
//  +--------------------+
//  | next_item          |  -----> pointer to next item in enumeration
//  +--------------------+
//  | reverse_order      |  flag indicating the enumeration order of items
//  +--------------------+

typedef /* _enumerator */ struct {
	_dictionary *dict;
	_entry_ptr next_item;
	bool reverse_order;
} _enumerator;


// --------------------------------------------------------------------------
// private data:  _EMPTY_CSTRING
// --------------------------------------------------------------------------

const char *_EMPTY_CSTRING = "/0";


// --------------------------------------------------------------------------
// private function forward declarations
// --------------------------------------------------------------------------

// dictionaries

inline static _dictionary *_alloc_init_dict_with(cardinal size) _ATTR(_ai_);
inline static void _dispose_dict(_dictionary *dict, dd_status *status) _ATTR(_ai_);

// entries

inline static _entry_ptr _alloc_init_entry_with(void *object, const char *key,
                            cardinal keylen, cardinal hash) _ATTR(_ai_);
inline static void _retain_entry(_entry_ptr entry) _ATTR(_ai_);

// keys

inline static cardinal _key_length(const char *key) _ATTR(_ai_, _nn_, pure);
inline static char *_effectice_key_and_length(const char *key, cardinal *keylen) _ATTR(_ai_, _nn_);
inline static void _copy_n_chars_from_key(const char *key, char *target, cardinal n) _ATTR(_ai_, _nn_);


// ==========================================================================
// P U B L I C   F U N C T I O N   I M P L E M E N T A T I O N S
// ==========================================================================

// --------------------------------------------------------------------------
// function:  dd_new_dictionary()
// --------------------------------------------------------------------------
//
// Creates and returns a  new empty dictionary.  The size of the dictionary's
// hashtable will be set to the default hastable size as returned by function
// dd_default_hashtable_size().
//
// Returns NULL if the dictionary could not be created.

dd_dictionary dd_new_dictionary() {
	return (dd_dictionary) _alloc_init_dict_with(DD_DEFAULT_HASHTABLE_SIZE);
} // end dd_new_dictionary;


// --------------------------------------------------------------------------
// function:  dd_new_dictionary_with_capacity(capacity)
// --------------------------------------------------------------------------
//
// Creates and returns a  new empty dictionary of arbitrary size.  The actual
// size of the  dictionary's hashtable  will be set  to the  return value  of
// function dd_hashtable_size_for_requested_minimum() for value <capacity>.
//
// If <capacity> is 0, the  actual hashtable size  will be set to the default
// as returned by dd_default_hashtable_size(), by default this value is 257.
//
// Returns NULL if the dictionary could not be created.

dd_dictionary dd_new_dictionary_with_capacity(cardinal capacity) {
	cardinal actual_size;
	
	if (capacity == 0)
		return (dd_dictionary) _alloc_init_dict_with(DD_DEFAULT_HASHTABLE_SIZE);
	
	actual_size = dd_hashtable_size_for_requested_minimum(capacity);
	
	return (dd_dictionary) _alloc_init_dict_with(actual_size);
} // end dd_new_dictionary_with_capacity;


// --------------------------------------------------------------------------
// function:  dd_set_hash_function_for_dictionary(dict, hashf)
// --------------------------------------------------------------------------
//
// Sets the  hash function  of dictionary <dict>  to the function  passed  in
// <hashf>, which must be of type dd_hash_function.
//
// If  no hash function  is  set,  the  default hash function  as returned by
// function  dd_default_hash_function() will be used.  The factory default is
// hash function dd_SDBM_hash_string().
//
// This operation is only allowed on empty dictionaries.

dd_status dd_set_hash_function_for_dictionary(dd_dictionary dict, dd_hash_function hashf) {
	_dictionary *this_dict = (_dictionary *) dict;
	
	// assert preconditions
	
	if (this_dict->buckets_in_use > 0)
		return DD_OPERATION_NOT_PERMITTED_ON_NON_EMPTY_DICT;
	
	if (hashf == NULL)
		return DD_INVALID_HASH_FUNCTION;
	
	// assign hash function to dictionary
	
	this_dict->hash_string = hashf;
	
	return DD_SUCCESS;
} // end dd_set_hash_function_for_dictionary;


// --------------------------------------------------------------------------
// function:  dd_set_object_copy_function_for_dictionary(dict, copyf)
// --------------------------------------------------------------------------
//
// Sets the object content copy function of dictionary <dict> to the function
// passed in <copyf>, which must be of type dd_object_copy_function.
//
// By default  no object content copy function is set and  the replacement of
// objects for keys  already present  in the dictionary is _not_ permitted.
//
// If an object content copy function is set, adding an object for a key that
// is already present in the dictionary  will copy  the contents  of the  new
// object  into  the  object  stored in the dictionary,  thereby  effectively
// replacing the stored object.
//
// This operation is only allowed on empty dictionaries.

dd_status dd_set_object_copy_function_for_dictionary(dd_dictionary dict,
													 dd_object_copy_function copyf) {
	
	_dictionary *this_dict = (_dictionary *) dict;
	
	// assert preconditions
	
	if (dict == NULL)
		return DD_INVALID_DICTIONARY;
	
	if (this_dict->buckets_in_use > 0)
		return DD_OPERATION_NOT_PERMITTED_ON_NON_EMPTY_DICT;
	
	if (copyf == NULL)
		return DD_INVALID_COPY_FUNCTION;
	
	// assign copy function to dictionary
	
	this_dict->copy_object = copyf;
	
	return DD_SUCCESS;
} // end dd_set_object_copy_function_for_dictionary;


// --------------------------------------------------------------------------
// function:  dd_set_object_event_handler_for_dictionary(dict, evt, handler)
// --------------------------------------------------------------------------
//
// Sets the object event handler  of dictionary <dict>  for event <event>  to
// the event handler function passed in <handler>,  which  must  be  of  type
// dd_object_event_handler.  By default no event handlers are set.
//
// This operation is only allowed on empty dictionaries.

dd_status dd_set_object_event_handler_for_dictionary(dd_dictionary dict,
													 dd_event event,
													 dd_object_event_handler handler) {
	_dictionary *this_dict = (_dictionary *) dict;

	// assert preconditions
	
	if (dict == NULL)
		return DD_INVALID_DICTIONARY;
	
	if (this_dict->buckets_in_use > 0)
		return DD_OPERATION_NOT_PERMITTED_ON_NON_EMPTY_DICT;
	
	if (handler == NULL)
		return DD_INVALID_EVENT_HANDLER;
	
	// assign handler to dictionary
	
	switch(event) {
		case DD_WILL_INSERT_OBJECT:
			this_dict->will_insert_object = handler;
			break;
		case DD_DID_INSERT_OBJECT:
			this_dict->did_insert_object = handler;
			break;
		case DD_WILL_REMOVE_OBJECT:
			this_dict->will_remove_object = handler;
			break;
		case DD_DID_REMOVE_OBJECT:
			this_dict->did_remove_object = handler;
			break;
		case DD_WILL_DISPOSE_DICT:
			this_dict->will_dispose_dict = handler;
			break;
		case DD_DID_DISPOSE_DICT:
			this_dict->did_dispose_dict = handler;
			break;
		default:
			return DD_INVALID_EVENT_CODE;
	} // end switch;
	
	return DD_SUCCESS;
} // end dd_set_object_event_handler_for_dictionary;


// --------------------------------------------------------------------------
// function:  dd_add_object_for_key(dict, key, object)
// --------------------------------------------------------------------------
//
// Adds the key <key> and its associated value <object> to dictionary <dict>.
//
// Keys are added to the dictionary by value, objects are added by reference.
// Keys must not be empty strings and objects must not be NULL.
//
// If key <key> is already present in dictionary <dict> and an object content
// copy function has been set  for the dictionary,  then the  content  of the
// previously stored stored object associated with <key> will be  replaced by
// the content of object <object>.
//
// If key <key> is already presnet in dictionary <dict> and no object content
// copy function has been set for the dictionary,  then the previously stored
// object associated with key <key>  will  remain unchanged  and  status code
// DD_OBJECT_REPLACEMENT_NOT_PERMITTED will be returned.

dd_status dd_add_object_for_key(dd_dictionary dict, const char *key, void *object) {
	_dictionary *this_dict = (_dictionary *) dict;
	_entry_ptr this_entry, new_entry = NULL;
	cardinal hash, index, keylen = 0;
	char *effective_key;

	// --------------------
	// assert preconditions
	// --------------------
	
	if (dict == NULL)
		return DD_INVALID_DICTIONARY;
		
	if (object == NULL)
		return DD_INVALID_OBJECT;
	
	if ((key == NULL) || (key[0] == '\0'))
		return DD_INVALID_KEY;
	
	// determine effective key and its length
	effective_key = _effectice_key_and_length(key, &keylen);
	
	if ((effective_key == NULL) || (keylen == 0))
		return DD_INVALID_KEY;
	
	// calculate the hash for the effective key
	hash = this_dict->hash_string(effective_key);
	
	// we've checked the key already and thus the hash wouldn't be zero
	// but a faulty user supplied hash function might return zero anyway
	if (hash == 0)
		return DD_INVALID_HASH;
	
	// check if lookups are inhibited
	if (this_dict->disposal_in_progress == true)
		return DD_DICTIONARY_DISPOSAL_IN_PROGRESS;
	
	// ---------------------------------
	// let others know what we are doing
	// ---------------------------------
	
	this_dict->pending_inserts++;	

	// ------------------------------
	// determine address for this key
	// ------------------------------
	
	index = hash % this_dict->hashtable_size;
	this_entry = this_dict->bucket[index];

	// ---------------------------------------
	// add new entry or replace existing entry
	// ---------------------------------------

	if /* bucket is empty */ (this_entry == NULL) {
		
		// call event handler for DD_WILL_INSERT_OBJECT
		if (this_dict->will_insert_object != NULL)
			this_dict->will_insert_object(object);
		
		// allocate and initialise a new entry
		// note, we've already checked object, effective_key, keylen and hash
		new_entry = _alloc_init_entry_with(object, effective_key, keylen, hash);
		
		if (new_entry == NULL) {
			this_dict->pending_inserts--;
			return DD_MEMORY_ALLOCATION_FAILED;
		} // end if
		
		// link the bucket to the new entry
		this_dict->bucket[index] = new_entry;
		this_entry = new_entry;
		
		// update counters
		this_dict->buckets_in_use++;
		this_dict->entry_count++;
		
		// update iteration list
		this_entry->previously_added = this_dict->last_entry;
		this_dict->last_entry->subsequently_added = this_entry;
		this_dict->last_entry = this_entry;
		
		// call event handler for DD_DID_INSERT_OBJECT
		if (this_dict->did_insert_object != NULL)
			this_dict->did_insert_object(object);		
	}
	else if /* key matches entry's key */ (this_entry->hash == hash) {
		
		// check if object replacement is permitted
		if (this_dict->copy_object == NULL) {
			this_dict->pending_inserts--;
			return DD_OBJECT_REPLACEMENT_NOT_PERMITTED;
		} // end if
		
		// replace the stored object's contents
		this_dict->copy_object(object, this_entry->object);
	}
	else /* collision occurred */ {
				
		// search for a match in the externally chained list
		while ((this_entry->next != NULL) &&
			   (this_entry->next->hash != hash)) {
			this_entry = this_entry->next;
		} // end while
		
		if (this_entry->next->hash == hash) {
			
			// check if object replacement is permitted
			if (this_dict->copy_object == NULL) {
				this_dict->pending_inserts--;
				return DD_OBJECT_REPLACEMENT_NOT_PERMITTED;
			} // end if
			
			// replace the stored object's contents
			this_dict->copy_object(object, this_entry->object);
		}
		else {
			
			// call event handler for DD_WILL_INSERT_OBJECT
			if (this_dict->will_insert_object != NULL)
				this_dict->will_insert_object(object);
			
			// allocate and initialise a new entry
			// note, we've already checked object, effective_key, keylen and hash
			new_entry = _alloc_init_entry_with(object, effective_key, keylen, hash);
			
			if (new_entry == NULL) {
				this_dict->pending_inserts--;
				return DD_MEMORY_ALLOCATION_FAILED;
			} // end if
			
			// link the new entry to end of externally chained list
			this_entry->next = new_entry;
			this_entry = new_entry;

			// update counters
			this_dict->entry_count++;
			
			// update iteration list
			this_entry->previously_added = this_dict->last_entry;
			this_dict->last_entry->subsequently_added = this_entry;
			this_dict->last_entry = this_entry;

			// call event handler for DD_DID_INSERT_OBJECT
			if (this_dict->did_insert_object != NULL)
				this_dict->did_insert_object(object);
		} // end if
		
	} // end if
	
	this_dict->pending_inserts--;
	return DD_SUCCESS;
} // end dd_add_object_for_key;


// --------------------------------------------------------------------------
// function:  dd_object_for_key(dict, key, retain)
// --------------------------------------------------------------------------
//
// Returns the pointer to object <object> associated with key <key> stored in
// dictionary <dict>.  If retain flag <retain>  is  set,  the  entry's retain 
// counter will be incremented and it will need to be released explicitly.
//
// Returns NULL if the key is not present in <dict>.

void* dd_object_for_key(dd_dictionary dict, const char *key, bool retain) {
	_dictionary *this_dict = (_dictionary *) dict;
	_entry_ptr this_entry;
	cardinal hash, index, keylen = 0;
	char *effective_key;
	
	// --------------------
	// assert preconditions
	// --------------------
	
	if (dict == NULL)
		return NULL;
	
	if (this_dict->disposal_in_progress == true)
		return NULL;
	
	if ((key == NULL) || (key[0] == '\0'))
		return NULL;
	
	// determine effective key and its length
	effective_key = _effectice_key_and_length(key, &keylen);
	
	if ((effective_key == NULL) || (keylen == 0))
		return NULL;
	
	// calculate the hash for the effective key
	hash = this_dict->hash_string(effective_key);
	
	// we've checked the key already and thus the hash wouldn't be zero
	// but a faulty user supplied hash function might return zero anyway
	if (hash == 0)
		return NULL;
	
	// check if lookups are inhibited
	if (this_dict->disposal_in_progress == true)
		return NULL;
	
	// ---------------------------------
	// let others know what we are doing
	// ---------------------------------
	
	this_dict->pending_lookups++;	
	
	// ------------------------------
	// determine address for this key
	// ------------------------------
	
	index = hash % this_dict->hashtable_size;
	this_entry = this_dict->bucket[index];

	// ---------------------------
	// lookup entry at the address
	// ---------------------------
		
	if /* bucket is empty */ (this_entry == NULL) {
		this_dict->pending_lookups++;
		return NULL;
	}
	else if /* key matches entry's key */ (this_entry->hash == hash) {

		if (retain == true)
			this_entry->retain_count++;

		this_dict->pending_lookups--;
		return this_entry->object;
	}
	else /* collision occurred */ {
		
		// search for a match in the externally chained list
		while ((this_entry->next != NULL) &&
			   (this_entry->next->hash != hash)) {
			this_entry = this_entry->next;
		} // end while
		
		if /* match found */ (this_entry->next->hash == hash) {
			
			if (retain == true)
				this_entry->retain_count++;
			
			this_dict->pending_lookups--;
			return this_entry->object;
		}
		else /* no match found */ {
			this_dict->pending_lookups--;
			return NULL;
		} // end if
	} // end if
	
} // end dd_object_for_key;


// --------------------------------------------------------------------------
// function:  dd_retain_count_for_key(dict, key)
// --------------------------------------------------------------------------
//
// Returns  the  retain counter  of the  entry associated  with key <key>  in
// dictionary <dict>.  Returns 0 if <key> is  not  present in the dictionary,
// returns -1 if <key> is an empty string or NULL or if <dict> is NULL.
//
// Note: The initial retain count for a newly created entry is always 1.

int dd_retain_count_for_key(dd_dictionary dict, const char *key) {
	_dictionary *this_dict = (_dictionary *) dict;
	_entry_ptr this_entry;
	cardinal hash, index, keylen = 0;
	char *effective_key;
	
	// --------------------
	// assert preconditions
	// --------------------
	
	if (dict == NULL)
		return -1;
		
	if ((key == NULL) || (key[0] == '\0'))
		return -1;
			
	// determine effective key and its length
	effective_key = _effectice_key_and_length(key, &keylen);
	
	if ((effective_key == NULL) || (keylen == 0))
		return -1;
	
	// calculate the hash for the effective key
	hash = this_dict->hash_string(effective_key);
	
	// we've checked the key already and thus the hash wouldn't be zero
	// but a faulty user supplied hash function might return zero anyway
	if (hash == 0)
		return -1;
	
	// check if lookups are inhibited
	if (this_dict->disposal_in_progress == true)
		return -1;
	
	// ---------------------------------
	// let others know what we are doing
	// ---------------------------------
	
	this_dict->pending_lookups++;	
	
	// ------------------------------
	// determine address for this key
	// ------------------------------
	
	index = hash % this_dict->hashtable_size;
	this_entry = this_dict->bucket[index];
	
	// ---------------------------
	// lookup entry at the address
	// ---------------------------
	
	if /* bucket is empty */ (this_entry == NULL) {
		this_dict->pending_lookups--;
		return 0;
	}
	else if /* key matches entry's key */ (this_entry->hash == hash) {
		
		this_dict->pending_lookups--;
		return this_entry->retain_count;
	}
	else /* collision occurred */ {
		
		// search for a match in the externally chained list
		while ((this_entry->next != NULL) &&
			   (this_entry->next->hash != hash)) {
			this_entry = this_entry->next;
		} // end while
		
		if /* match found */ (this_entry->next->hash == hash) {
						
			this_dict->pending_lookups--;
			return this_entry->retain_count;
		}
		else /* no match found */ {
			this_dict->pending_lookups--;
			return 0;
		} // end if
	} // end if
	
} // end dd_retain_count_for_key;


// --------------------------------------------------------------------------
// function:  dd_release_object_for_key(dict, key)
// --------------------------------------------------------------------------
//
// Decrements the  retain counter  of key <key>'s entry  in dictionary <dict>
// and thereby  releases a previous retain operation.  If,  as a result,  the
// entry's  retain counter  reaches 1  and  it had  earlier  been  marked for
// removal, then it will be removed from the dictionary immediately.

dd_status dd_release_object_for_key(dd_dictionary dict, const char *key) {
	_dictionary *this_dict = (_dictionary *) dict;
	_entry_ptr this_entry, predecessor = NULL;
	cardinal hash, index, keylen = 0;
	char *effective_key;
	void *object;
	
	// --------------------
	// assert preconditions
	// --------------------
	
	if (dict == NULL)
		return DD_INVALID_DICTIONARY;
	
	if ((key == NULL) || (key[0] == '\0'))
		return DD_INVALID_KEY;
	
	// determine effective key and its length
	effective_key = _effectice_key_and_length(key, &keylen);
	
	if ((effective_key == NULL) || (keylen == 0))
		return DD_INVALID_KEY;
	
	// calculate the hash for the effective key
	hash = this_dict->hash_string(effective_key);
	
	// we've checked the key already and thus the hash wouldn't be zero
	// but a faulty user supplied hash function might return zero anyway
	if (hash == 0)
		return DD_INVALID_HASH;
	
	// ------------------------------
	// determine address for this key
	// ------------------------------
	
	index = hash % this_dict->hashtable_size;
	this_entry = this_dict->bucket[index];
	
	// ---------------------------
	// lookup entry at the address
	// ---------------------------
	
	if /* bucket is empty */ (this_entry == NULL) {
		return DD_NO_SUCH_KEY;
	}
	else if /* key matches entry's key */ (this_entry->hash == hash) {
		
		if (this_entry->retain_count > 1)
			this_entry->retain_count--;
	}
	else /* collision occurred */ {
		
		// search for a match in the externally chained list
		while ((this_entry->next != NULL) &&
			   (this_entry->next->hash != hash)) {
			predecessor = this_entry;
			this_entry = this_entry->next;
		} // end while
		
		if /* match found */ (this_entry->next->hash == hash) {
			
			if (this_entry->retain_count > 1)
				this_entry->retain_count--;
		}
		else /* no match found */ {
			return DD_NO_SUCH_KEY;
		} // end if
	} // end if
	
	// if this entry has a pending removal and its retain count is 1,
	// then we will need to remove it now
	
	if ((this_entry->retain_count == 1) &&
		(this_entry->marked_for_removal == true)) {
		
		this_entry->retain_count = 0;
		object = this_entry->object;
		
		// call event handler WILL_REMOVE_OBJECT
		if (this_dict->will_remove_object != NULL)
			this_dict->will_remove_object(object);

		// remove the entry
		if (this_dict->bucket[index] == this_entry) {
			this_dict->bucket[index] = NULL;
		}
		else {
			if (predecessor != NULL) /* just in case */ {
				predecessor->next = this_entry->next;
			}
			else {
				
				/* ERROR: predecessor should not be NULL */
				
			} // end if
		} // end if

		// remove object
		this_entry->object = NULL;
		
		// update counters
		this_dict->buckets_in_use--;
		this_dict->entry_count--;
		
		// update iteration list header, if needed
		if (this_dict->first_entry == this_entry)
			this_dict->first_entry = this_entry->subsequently_added;
		if (this_dict->last_entry == this_entry)
			this_dict->last_entry = this_entry->previously_added;
		
		// remove from iteration list
		this_entry->previously_added->subsequently_added = this_entry->subsequently_added;
		this_entry->subsequently_added->previously_added = this_entry->previously_added;
		
		// deallocate entry
		_DEALLOCATE(this_entry);
		
		// call event handler DID_REMOVE_OBJECT
		if (this_dict->did_remove_object != NULL)
			this_dict->did_remove_object(object);
				
	} // end if
	
	return DD_SUCCESS;
} // end dd_release_object_for_key;


// --------------------------------------------------------------------------
// function:  dd_remove_object_for_key(dict, key)
// --------------------------------------------------------------------------
//
// Requests the removal  of the entry  associated with <key>  from dictionary
// <dict>.  If the entry's  retain counter is 1  at the time this function is
// called,  the  entry  will  be  removed immediately.  If the entry's retain
// counter is  larger than 1,  the entry  will be  marked for removal  and it
// will be removed from the dictionary when its retain counter reaches 1.

dd_status dd_remove_object_for_key(dd_dictionary dict, const char *key) {
	_dictionary *this_dict = (_dictionary *) dict;
	_entry_ptr this_entry, predecessor = NULL;
	cardinal hash, index, keylen = 0;
	char *effective_key;
	void *object;
	
	// --------------------
	// assert preconditions
	// --------------------
	
	if (dict == NULL)
		return DD_INVALID_DICTIONARY;
	
	if ((key == NULL) || (key[0] == '\0'))
		return DD_INVALID_KEY;
	
	// determine effective key and its length
	effective_key = _effectice_key_and_length(key, &keylen);
	
	if ((effective_key == NULL) || (keylen == 0))
		return DD_INVALID_KEY;
	
	// calculate the hash for the effective key
	hash = this_dict->hash_string(effective_key);
	
	// we've checked the key already and thus the hash wouldn't be zero
	// but a faulty user supplied hash function might return zero anyway
	if (hash == 0)
		return DD_INVALID_HASH;
	
	// ------------------------------
	// determine address for this key
	// ------------------------------
	
	index = hash % this_dict->hashtable_size;
	this_entry = this_dict->bucket[index];
	
	// ---------------------------
	// lookup entry at the address
	// ---------------------------
	
	if /* bucket is empty */ (this_entry == NULL) {
		return DD_NO_SUCH_KEY;
	}
	else if /* key matches entry's key */ (this_entry->hash == hash) {
		
		// mark entry for removal, but don't remove it just yet
		this_entry->marked_for_removal = true;
	}
	else /* collision occurred */ {
		
		// search for a match in the externally chained list
		while ((this_entry->next != NULL) &&
			   (this_entry->next->hash != hash)) {
			predecessor = this_entry;
			this_entry = this_entry->next;
		} // end while
		
		if /* match found */ (this_entry->hash == hash) {

			// mark entry for removal, but don't remove it just yet
			this_entry->marked_for_removal = true;					
		}
		else /* no match found */ {
			return DD_NO_SUCH_KEY;
		} // end if
	} // end if
	
	// if this entry has a pending removal and its retain count is 1,
	// then we will need to remove it now
	
	if ((this_entry->retain_count == 1) &&
		(this_entry->marked_for_removal == true)) {
		
		this_entry->retain_count = 0;
		object = this_entry->object;
		
		// call event handler WILL_REMOVE_OBJECT
		if (this_dict->will_remove_object != NULL)
			this_dict->will_remove_object(object);
		
		// remove the entry
		if (this_dict->bucket[index] == this_entry) {
			this_dict->bucket[index] = NULL;
		}
		else {
			if (predecessor != NULL) /* just in case */ {
				predecessor->next = this_entry->next;
			}
			else {
				
				/* ERROR: predecessor should not be NULL */
				
			} // end if
		} // end if
		
		// remove object
		this_entry->object = NULL;
		
		// update counters
		this_dict->buckets_in_use--;
		this_dict->entry_count--;
		
		// update iteration list header, if needed
		if (this_dict->first_entry == this_entry)
			this_dict->first_entry = this_entry->subsequently_added;
		if (this_dict->last_entry == this_entry)
			this_dict->last_entry = this_entry->previously_added;
		
		// remove from iteration list
		this_entry->previously_added->subsequently_added = this_entry->subsequently_added;
		this_entry->subsequently_added->previously_added = this_entry->previously_added;
		
		// deallocate entry
		_DEALLOCATE(this_entry);
		
		// call event handler DID_REMOVE_OBJECT
		if (this_dict->did_remove_object != NULL)
			this_dict->did_remove_object(object);
		
	} // end if	
	
	return DD_SUCCESS;
} // end dd_remove_object;


// --------------------------------------------------------------------------
// function:  dd_key_for_hash(dict, hash, retain)
// --------------------------------------------------------------------------
//
// Returns the pointer to key <key>  for hash value <hash> if <key> is stored
// in dictionary <dict>.  If retain flag <retain> is set,  the entry's retain
// counter will be incremented and it will need to be released explicitly.
//
// Returns a pointer to an empty C string ("\0") if there is no key <key> for
// hash value <hash> stored in dictionary <dict>.  Returns NULL if dictionary
// <dict> is NULL.
//
// Note: This function is predominantly of interest when the dictionary is to
// be used as a  symbol lookup table  for lexers and parsers  which typically
// require the ability to do reverse lookups for keys.  However, if no object
// storage and no iteration is required for the desired  symbol lookup table,
// the symbol table specific API ("dd_symbol_table.h") should be used.

const char* dd_key_for_hash(dd_dictionary dict, cardinal hash, bool retain) {
	_dictionary *this_dict = (_dictionary *) dict;
	_entry_ptr this_entry;
	cardinal index;

	// assert preconditions
	
	if ((dict == NULL) || (hash == 0))
		return NULL;

	// check if lookups are inhibited
	if (this_dict->disposal_in_progress == true)
		return NULL;
	
	// let others know what we are doing
	
	this_dict->pending_lookups++;	
	
	// determine address from hash
	
	index = hash % this_dict->hashtable_size;
	this_entry = this_dict->bucket[index];
	
	// lookup entry at address
	
	if /* bucket is empty */ (this_entry == NULL) {
		this_dict->pending_lookups--;
		return _EMPTY_CSTRING;
	}
	else if /* key matches entry's key */ (this_entry->hash == hash) {
		
		if (retain == true)
			this_entry->retain_count++;
		
		this_dict->pending_lookups--;
		return this_entry->key;
	}
	else /* collision occurred */ {
		
		// search for a match in the externally chained list
		while ((this_entry->next != NULL) &&
			   (this_entry->next->hash != hash)) {
			this_entry = this_entry->next;
		} // end while
		
		if /* match found */ (this_entry->next->hash == hash) {
			
			if (retain == true)
				this_entry->retain_count++;
			
			this_dict->pending_lookups--;
			return this_entry->key;
		}
		else /* no match found */ {
			this_dict->pending_lookups--;
			return _EMPTY_CSTRING;
		} // end if
	} // end if
	
} // end dd_key_for_hash;


// --------------------------------------------------------------------------
// function:  dd_object_count(dict)
// --------------------------------------------------------------------------
//
// Returns the  number of objects  stored in dictionary <dict>.  Returns 0 if
// dictionary <dict> is empty,  returns -1 if <dict> is NULL.

int dd_object_count(dd_dictionary dict) {
	_dictionary *this_dict = (_dictionary *) dict;

	if (dict == NULL)
		return -1;

	// check if lookups are inhibited
	if (this_dict->disposal_in_progress == true)
		return -1;
	
	return this_dict->entry_count;
} // end dd_dictionary_object_count;


// --------------------------------------------------------------------------
// function:  dd_hashtable_size(dict)
// --------------------------------------------------------------------------
//
// Returns the hashtable size of dictionary <dict>.  Returns -1 if dictionary
// <dict> is NULL.

int dd_hashtable_size(dd_dictionary dict) {
	_dictionary *this_dict = (_dictionary *) dict;

	if (this_dict == NULL)
		return -1;

	// check if lookups are inhibited
	if (this_dict->disposal_in_progress == true)
		return -1;
		
	return this_dict->hashtable_size;
} // end dd_dictionary_size;


// --------------------------------------------------------------------------
// function:  dd_hashtable_load(dict)
// --------------------------------------------------------------------------
//
// Returns  the  hashtable load factor  of  dictionary <dict>.  Returns -1 if
// dictionary <dict> is NULL.

int dd_hashtable_load(dd_dictionary dict) {
	_dictionary *this_dict = (_dictionary *) dict;
	
	if (this_dict == NULL)
		return -1;
	
	// check if lookups are inhibited
	if (this_dict->disposal_in_progress == true)
		return -1;
	
	if (this_dict->hashtable_size != 0) /* shouldn't be 0, but just in case */
		return 100 * this_dict->entry_count / this_dict->hashtable_size;
	else
		return -1;
} // end dd_dictionary_load;


// --------------------------------------------------------------------------
// function:  dd_new_enumerator_from_dictionary(dict, reverse_order)
// --------------------------------------------------------------------------
//
// Creates and returns a new enumerator object  representing an  ordered list
// of all keys and objects in dictionary <dict>.  The list order  follows the
// order in which the objects  were added to <dict>.  If flag <reverse_order>
// is set, the list order is reversed.
//
// Returns NULL if dictionary <dict> is NULL or empty.

dd_enumerator dd_new_enumerator_for_dictionary(dd_dictionary dict, bool reverse_order) {
	_dictionary *this_dict = (_dictionary *) dict;
	_enumerator *this_enumerator = NULL;
	
	if (this_dict == NULL)
		return NULL;
		
	if (this_dict->hashtable_size == 0) /* shouldn't be 0, but just in case */
		return NULL;
	
	// check if lookups are inhibited
	if (this_dict->disposal_in_progress == true)
		return NULL;
	
	// let others know what we are doing
	this_dict->pending_lookups++;	
	
	// allocate a new enumerator object
	this_enumerator = (_enumerator *) _ALLOCATE(sizeof(_enumerator));
	
	if (this_enumerator == NULL) {
		this_dict->pending_lookups--;
		return NULL;
	} // end if
	
	this_enumerator->dict = this_dict;
	this_enumerator->reverse_order = reverse_order;
	if /* forward order */ (reverse_order == false) {
		_retain_entry(this_dict->first_entry);
		this_enumerator->next_item = this_dict->first_entry;
	}
	else /* reverse order */ {
		_retain_entry(this_dict->last_entry);
		this_enumerator->next_item = this_dict->last_entry;
	} // end if

	this_dict->pending_lookups--;
	return this_enumerator;
} // end dd_new_enumerator_for_dictionary;


// --------------------------------------------------------------------------
// function:  dd_next_key_and_object_in_enumeration(enum, key, obj, retain)
// --------------------------------------------------------------------------
//
// Retrieves key and object for the next item  in enumerator <enumerator>  to
// return  the key  in <key>  and  its object  in <object>,  then  moves  the
// enumerator's item pointer  to the successor item.  Both key and object are
// returned by reference.  If retain flag <retain> is set, the entry's retain
// counter will be incremented and it will need to be released explicitly.
//
// Returns NULL in <key> and <object> if <enumerator> is invalid or if the
// end of the list of items in <enumerator> has been reached.

dd_status dd_next_key_and_object_in_enumeration(dd_enumerator enumerator,
                                                         char *key,
                                                         void *object,
                                                         bool retain) {
	_enumerator *this_enumerator = (_enumerator *) enumerator;
	_dictionary *this_dict;
	_entry_ptr this_entry;
	
	// assert preconditions
	
	if (enumerator == NULL)
		return DD_INVALID_ENUMERATOR;
	
	this_dict = this_enumerator->dict;
		
	// check if lookups are inhibited
	if (this_dict->disposal_in_progress == true)
		return DD_DICTIONARY_DISPOSAL_IN_PROGRESS;
	
	// let others know what we are doing
	this_dict->pending_lookups++;	
		
	// obtain key and object for this entry
	
	if (this_enumerator->next_item == NULL) {
		key = NULL;
		object = NULL;
	}
	else {
		key = this_enumerator->next_item->key;
		object = this_enumerator->next_item->object;
	} // end if
	
	// remember current entry so we can release it later
	
	this_entry = this_enumerator->next_item;
	
	// update entry pointer to point to its successor entry
	
	if /* forward order */ (this_enumerator->reverse_order == false) {
		_retain_entry(this_enumerator->next_item->subsequently_added);
		this_enumerator->next_item = this_enumerator->next_item->subsequently_added;
	}
	else /* reverse order */ {
		_retain_entry(this_enumerator->next_item->previously_added);
		this_enumerator->next_item = this_enumerator->next_item->previously_added;
	} // end if
	
	// release current entry, but only if retain flag isn't set
	
	if (retain != true)
		dd_release_object_for_key(this_enumerator->dict, this_entry->key);
	
	this_dict->pending_lookups--;
	return DD_SUCCESS;
} // end dd_get_next_item_in_enumeration;


// --------------------------------------------------------------------------
// function:  dd_dictionary_for_enumerator(enumerator)
// --------------------------------------------------------------------------
//
// Returns the dictionary from which enumerator <enumerator> was created.

dd_dictionary dd_dictionary_for_enumerator(dd_enumerator enumerator) {
	_enumerator *this_enumerator = (_enumerator *) enumerator;
	
	// assert preconditions
	
	if (this_enumerator == NULL)
		return NULL;
	
	return (_dictionary *) this_enumerator->dict;
} // end dd_dictionary_for_enumerator


// --------------------------------------------------------------------------
// function:  dd_reset_enumerator(enumerator)
// --------------------------------------------------------------------------
//
// Resets the  item pointer  of enumerator <enumerator> to point to the first
// item.  Corresponding entries will be retained and released automatically.

dd_status dd_reset_enumerator(dd_enumerator enumerator) {
	_enumerator *this_enumerator = (_enumerator *) enumerator;
	_dictionary *this_dict;
	_entry_ptr this_entry;

	// assert preconditions

	if (this_enumerator == NULL)
		return DD_INVALID_ENUMERATOR;

	this_dict = this_enumerator->dict;
	
	// check if lookups are inhibited
	if (this_dict->disposal_in_progress == true)
		return DD_DICTIONARY_DISPOSAL_IN_PROGRESS;
	
	// let others know what we are doing
	
	this_dict->pending_lookups++;	
	
	// remember current entry so we can release it later

	this_entry = this_enumerator->next_item;
	
	// reset entry pointer to point to the first entry in this enumeration

	if /* forward order */ (this_enumerator->reverse_order == false) {
		_retain_entry(this_enumerator->dict->first_entry);
		this_enumerator->next_item = this_enumerator->dict->first_entry;
	}
	else /* reverse order */ {
		_retain_entry(this_enumerator->dict->last_entry);
		this_enumerator->next_item = this_enumerator->dict->last_entry;
	} // end if
	
	// release current entry

	dd_release_object_for_key(this_enumerator->dict, this_entry->key);

	this_dict->pending_lookups--;
	return DD_SUCCESS;
} // end dd_reset_enumerator;


// --------------------------------------------------------------------------
// function:  dd_dispose_enumerator(enumerator)
// --------------------------------------------------------------------------
//
// Releases the entry to which the enumerator <enumerator>'s item pointer  is
// pointing to and disposes of <enumerator>.

dd_status dd_dispose_enumerator(dd_enumerator enumerator) {
	_enumerator *this_enumerator = (_enumerator *) enumerator;
	
	if (enumerator == NULL)
		return DD_INVALID_ENUMERATOR;
	
	dd_release_object_for_key(this_enumerator->dict, this_enumerator->next_item->key);
	
	_DEALLOCATE(this_enumerator);
	
	return DD_SUCCESS;
} // end dd_dispose_enumerator;


// --------------------------------------------------------------------------
// function:  dd_dispose_dictionary(dict)
// --------------------------------------------------------------------------
//
// Requests disposal  of dictionary <dict>  and  the  removal of  all objects
// stored in it.  Once a disposal is pending,  objects can no longer be added
// to the dictionary.  The dictionary will be deallocated when the  reference
// counters of all objects stored in it are 0.

dd_status dd_dispose_dictionary(dd_dictionary dict) {
	_dictionary *this_dict = (_dictionary *) dict;
	bool pending, in_progress;
	dd_status status;

	if (dict == NULL)
		return DD_INVALID_DICTIONARY;
	
	_LOCK(this_dict->disposal_lock);
	if (this_dict->disposal_in_progress == true) {
		in_progress = true;
		pending = false;
	}
	else if (this_dict->marked_for_disposal == true) {
		in_progress = false;
		pending = true;
	}
	else {
		this_dict->marked_for_disposal = true;
		in_progress = false;
		pending = true;
	} // end if
	_UNLOCK(this_dict->disposal_lock);
	
	if (in_progress == true)
		return DD_DICTIONARY_DISPOSAL_IN_PROGRESS;
	
	if ((pending == true) && (this_dict->retained_entries > 0))
		return DD_DICTIONARY_DISPOSAL_PENDING;
	
	// retain count might go up again due to still executing lookups
	// but we'll make an _attempt_ to start the disposal now anyway
	_dispose_dict(this_dict, &status);
	
	return status;
} // end dd_dispose_dictionary;


// ==========================================================================
// P R I V A T E   F U N C T I O N   I M P L E M E N T A T I O N S
// ==========================================================================

// --------------------------------------------------------------------------
// private function:  _alloc_init_dict_with(size)
// --------------------------------------------------------------------------

inline static _dictionary *_alloc_init_dict_with(cardinal size) {
	_dictionary * new_dict;
	word_t index;
	
	new_dict = (_dictionary *) _ALLOCATE(sizeof(_dictionary) + (size * sizeof(pointer_t)));
	
	if (new_dict == NULL)
		return NULL;
	
	new_dict->marked_for_disposal = false;
	new_dict->disposal_in_progress = false;
	new_dict->hashtable_size = size;
	new_dict->buckets_in_use = 0;
	new_dict->pending_lookups = 0;
	new_dict->pending_inserts = 0;
	new_dict->retained_entries = 0;
	new_dict->entry_count = 0;
	new_dict->hash_string = DD_DEFAULT_HASH_FUNCTION;
	new_dict->copy_object = NULL;
	new_dict->will_insert_object = NULL;
	new_dict->did_insert_object = NULL;
	new_dict->will_remove_object = NULL;
	new_dict->did_remove_object = NULL;
	new_dict->will_dispose_dict = NULL;
	new_dict->did_dispose_dict = NULL;
	new_dict->first_entry = NULL;
	new_dict->last_entry = NULL;
	
	for (index = 0; index < size; index++)
		new_dict->bucket[index] = NULL;
	
	return new_dict;
} // end _alloc_init_dict_with;


// --------------------------------------------------------------------------
// private function:  _dispose_dict(dict)
// --------------------------------------------------------------------------
//
// caller must ensure that dict is not NULL.

inline static void _dispose_dict(_dictionary *dict, dd_status *status) {
	_entry_ptr this_entry, next_entry;
	bool already_running;
	void *object;
	
	// make sure that we don't execute multiple instances
	_LOCK(dict->disposal_lock);
	already_running = dict->disposal_in_progress;
	if (already_running == false)
		// prevent any new lookups and inserts
		dict->disposal_in_progress = true;
	_UNLOCK(dict->disposal_lock);
	
	if (already_running == true) {
		*status = DD_DICTIONARY_DISPOSAL_IN_PROGRESS;
		return;
	} // end if
	
	// wait until all running lookups and inserts have finished
	while ((dict->pending_lookups > 0) || (dict->pending_inserts > 0)) {
		usleep(75000); // suspend this thread for 75 ms
	} // end while
	
	// at this point we are safe to start deleting because
	// other threads can no longer access the dictionary
	
	// call event handler WILL_DISPOSE_DICTIONARY
	if (dict->will_dispose_dict != NULL)
		dict->will_dispose_dict(dict);
	
	this_entry = dict->first_entry;
	next_entry = this_entry;
	
	while (next_entry != NULL) {
		
		object = this_entry->object;
		
		// call event handler WILL_REMOVE_OBJECT
		if (dict->will_remove_object != NULL)
			dict->will_remove_object(object);
		
		next_entry = this_entry->subsequently_added;
		
		_DEALLOCATE(this_entry);
		this_entry = next_entry;
		
		// call event handler DID_REMOVE_OBJECT
		if (dict->did_remove_object != NULL)
			dict->did_remove_object(object);
		
	} // end while
	
	dd_object_event_handler did_dispose_dict;
	did_dispose_dict = dict->did_dispose_dict;
	
	_DEALLOCATE(dict);
	
	// call event handler DID_DISPOSE_DICTIONARY
	if (did_dispose_dict != NULL)
		did_dispose_dict(dict);
	
	*status = DD_SUCCESS;
	return;
} // end _dispose_dict;


// --------------------------------------------------------------------------
// private function:  _retain_entry(entry)
// --------------------------------------------------------------------------

inline static void _retain_entry(_entry_ptr entry) {

	// only increment retain count if entry is not currently being removed
	if ((entry != NULL) && (entry->retain_count > 0))
		entry->retain_count++;
	
	return;
} // end _retain_entry;


// --------------------------------------------------------------------------
// private function:  _alloc_init_entry_with(object, key, keylen, hash)
// --------------------------------------------------------------------------
//
// Returns  a pointer to a  newly allocated  and  intialised dictionary entry
// containing <object>, <key> and <hash>.  Argument <keylen> is also required
// for better performance as it won't have to be calculated again.

inline static _entry_ptr _alloc_init_entry_with(void *object,
                                          const char *key,
                                            cardinal keylen,
                                            cardinal hash) {
	_dict_entry *_new_entry;
	
	_new_entry = (_dict_entry *) _ALLOCATE(sizeof(_dict_entry) + keylen + 1);
	
	if (_new_entry == NULL)
		return NULL;
	
	_new_entry->marked_for_removal = false;
	_new_entry->hash = hash;
	_new_entry->retain_count = 1;
	_new_entry->object = object;
	_new_entry->next = NULL;
	_new_entry->previously_added = NULL;
	_new_entry->subsequently_added = NULL;
	
	_copy_n_chars_from_key(key, _new_entry->key, keylen);
	
	return _new_entry;
} // end _alloc_init_entry_with;


// --------------------------------------------------------------------------
// private function:  _key_length(key)
// --------------------------------------------------------------------------
//
// may not be needed, keep it around for now
//
// Argument <key> must not be NULL.

inline static cardinal _key_length(const char *key) {
	register cardinal len = 0;
	
	while ((key[len] != 0) && (len < DD_MAXIMUM_KEY_LENGTH))
		len++;
	
	return len;
} // end _key_length


// --------------------------------------------------------------------------
// private function:  _effectice_key_and_length(key, keylen)
// --------------------------------------------------------------------------
//
// Returns a pointer to the effective key for <key>  and passes its length in
// <keylen>. The effective key depends on settings DD_AUTOMATICALLY_TRIM_KEYS
// and DD_PRINTABLE_7BIT_ASCII_KEYS_ONLY as follows:
//
// If DD_AUTOMATICALLY_TRIM_KEYS is true, the effective key will start at the
// first non-whitespace/non-tab character of <key>  and  <keylen> will be set
// so that effective key does not have any trailing whitespace/tab.
//
// If DD_AUTOMATICALLY_TRIM_KEYS is true  and  all characters  within range 0
// and  DD_MAXIMUM_CHARS_TO_SCAN_WHEN_TRIMMING  are whitespace and tabs,  the
// effective key  will be set to  NULL  and  <keylen> will be  zero,  thereby
// rejecting <key>.
//
// If DD_PRINTABLE_7BIT_ASCII_KEYS_ONLY is true and any characters other than
// printable 7-bit ASCII characters  are present in <key> within the range of
// characters that would constitute the effective key, then the effective key
// will be set to NULL and <keylen> will be zero, thereby rejecting <key>.
//
// Arguments <key> and <keylen> must not be NULL. 

inline static char *_effectice_key_and_length(const char *key, cardinal *keylen) {
	register char *start = key; // causes compiler warning -- ignore!
	register cardinal len = 0, offset = 0;
	
#if (DD_AUTOMATICALLY_TRIM_KEYS == true)
	// trim any leading whitespace and tab
	while ((*start == 32) || (*start == 8)) {
		if (offset >= DD_MAXIMUM_CHARS_TO_SCAN_WHEN_TRIMMING) {
			*keylen = 0;
			return NULL; // nothing but whitespace/tab
		} // end if
		start++;
		offset++;
	} // end while
#endif

	// find the end of key
	while ((key[offset] != 0) && (len < DD_MAXIMUM_KEY_LENGTH)) {
#if (DD_PRINTABLE_7BIT_ASCII_KEYS_ONLY == true)
		// abort if any chars other than printable 7bit ASCII found
		if ((key[offset] < 32 x) && (key[offset] > 126)) {
			*keylen = 0;
			return NULL; // illegal character found
		} // end if
#endif
		len++;
		offset++;
	} // end while
	
#if (DD_AUTOMATICALLY_TRIM_KEYS == true)
	// trim any trailing whitespace and tab
	offset--;
	while ((len > 0) && ((key[offset] == 32) || (key[offset] == 8))) {
		len--;
		offset--;
	} // end while
#endif

	*keylen = len;
	return start;
} // end _effectice_key_and_length


// --------------------------------------------------------------------------
// private function:  _copy_n_chars_from_key(key, target, n)
// --------------------------------------------------------------------------
//
// Copies characters from <key> to <target>.  The number of characters copied
// will be determined by <n> or DD_MAXIMUM_KEY_LENGTH,  whichever is smaller.
// The target string <target> will always be  null-terminated at index <n> or
// DD_MAXIMUM_KEY_LENGTH, whichever is smaller.
//
// Arguments <key> and <target> must not be NULL.

inline static void _copy_n_chars_from_key(const char *key, char *target, cardinal n) {
	register cardinal i = 0;
	
	if (n > DD_MAXIMUM_KEY_LENGTH)
		n = DD_MAXIMUM_KEY_LENGTH;
	
	while (i < n) {
		target[i] = target[i];
		i++;
	} // end while
	
	target[n] = '\0';
	
	return;
} // end _copy_n_chars_from_key


// END OF FILE