/*
  Copyright (c) 2022 Alex Diener
  
  This software is provided 'as-is', without any express or implied
  warranty. In no event will the authors be held liable for any damages
  arising from the use of this software.
  
  Permission is granted to anyone to use this software for any purpose,
  including commercial applications, and to alter it and redistribute it
  freely, subject to the following restrictions:
  
  1. The origin of this software must not be misrepresented; you must not
     claim that you wrote the original software. If you use this software
     in a product, an acknowledgment in the product documentation would be
     appreciated but is not required.
  2. Altered source versions must be plainly marked as such, and must not be
     misrepresented as being the original software.
  3. This notice may not be removed or altered from any source distribution.
  
  Alex Diener alex@ludobloom.com
*/

#ifndef __HashTable_H__
#define __HashTable_H__
#ifdef __cplusplus
extern "C" {
#endif

#include "utilities/HashTableObjectKey.h"
#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>

#define HASH_TABLE_DENSITY_DEFAULT 5

typedef enum HashTable_keyType {
	HASH_KEY_TYPE_STRING,
	HASH_KEY_TYPE_BYTES,
	HASH_KEY_TYPE_UINT32,
	HASH_KEY_TYPE_POINTER,
	HASH_KEY_TYPE_UINT32_PAIR,
	HASH_KEY_TYPE_OBJECT
} HashTable_keyType;

typedef struct HashTable_key {
	HashTable_keyType type;
	union {
		struct {
			const char * characters;
			size_t length;
		} string;
		struct {
			const void * data;
			size_t length;
		} bytes;
		uint32_t uint32;
		struct {
			uint32_t first;
			uint32_t second;
		} uint32Pair;
		const void * pointer;
		HashTableObjectKey * object;
	} data;
} HashTable_key;

#define HashTable_stringKey(key_string) ((HashTable_key) {HASH_KEY_TYPE_STRING, {.string = {.characters = key_string, .length = strlen(key_string)}}})
#define HashTable_stringLiteralKey(key_string) ((HashTable_key) {HASH_KEY_TYPE_STRING, {.string = {.characters = key_string, .length = sizeof(key_string) - 1}}})
#define HashTable_stringKeyWithLength(key_string, key_length) ((HashTable_key) {HASH_KEY_TYPE_STRING, {.string = {.characters = key_string, .length = key_length}}})
#define HashTable_byteKey(key_bytes, key_length) ((HashTable_key) {HASH_KEY_TYPE_BYTES, {.bytes = {.data = key_bytes, .length = key_length}}})
#define HashTable_uint32Key(key_integer) ((HashTable_key) {HASH_KEY_TYPE_UINT32, {.uint32 = key_integer}})
#define HashTable_uint32PairKey(key_integer_1, key_integer_2) ((HashTable_key) {HASH_KEY_TYPE_UINT32_PAIR, {.uint32Pair = {.first = key_integer_1, .second = key_integer_2}}})
#define HashTable_uint32PairKeyUnordered(key_integer_1, key_integer_2) ((HashTable_key) {HASH_KEY_TYPE_UINT32_PAIR, {.uint32Pair = {.first = key_integer_1 > key_integer_2 ? key_integer_2 : key_integer_1, .second = key_integer_1 > key_integer_2 ? key_integer_1 : key_integer_2}}})
#define HashTable_pointerKey(key_pointer) ((HashTable_key) {HASH_KEY_TYPE_POINTER, {.pointer = key_pointer}})
#define HashTable_objectKey(key_object) ((HashTable_key) {HASH_KEY_TYPE_OBJECT, {.object = (HashTableObjectKey *) key_object}})

struct HashTable_bucket {
	size_t count;
	size_t allocatedCount;
	void * entries;
};

typedef struct HashTable {
	size_t entryDataSize;
	// densityMax is a tuning value used to determine when the HashTable should resize itself. It specifies the maximum
	// average depth of all storage buckets in the HashTable, and when exceeded, twice as many buckets are allocated
	// and the contents are redistributed. Smaller values will cause more reallocations of buckets; larger values will
	// cause a larger number of comparison operations to be necessary during lookup. Tables with relatively few entries
	// that are accessed frequently may benefit from a lower number, while tables with relatively many entries that are
	// accessed infrequently may benefit from a higher number. HASH_TABLE_DENSITY_DEFAULT should be used in situations
	// where performance requirements are irrelevant or unknown.
	size_t densityMax;
	size_t bucketCount;
	struct HashTable_bucket * buckets;
	size_t count;
} HashTable;

typedef bool (* HashTable_foreachCallback)(HashTable * hashTable, HashTable_key key, void * value, void * context);

// The entryDataSize specified at HashTable creation establishes the stride of data storage, and cannot be changed.
// get() and set() operate on blocks of data of this size, the bytes of which are copied when added to a HashTable.
// densityMax is set to HASH_TABLE_DENSITY_DEFAULT upon creation. See remarks above. This field can be changed any
// time to affect the frequency of rehashing.
HashTable * HashTable_create(size_t entryDataSize);
HashTable * HashTable_copy(HashTable * hashTable);
void HashTable_dispose(HashTable * hashTable);

// Returns a pointer to data of size entryDataSize, or NULL if the key is not found. The returned pointer should be
// considered fragile; any mutation to HashTable may invalidate it, so its content should not be read again after
// a subsequent call to HashTable_set(), HashTable_delete(), or HashTable_dispose().
void * HashTable_get(HashTable * hashTable, HashTable_key key);

// Adds a new entry to HashTable if a match for key is not found, or updates the existing entry if a match for key
// is found. Returns a pointer to the entry's data. If entryData is non-NULL, a number of bytes equal to the
// entryDataSize given at HashTable creation will be read from it and written to the retrieved entry within the
// HashTable. If entryData is NULL, newly created entries will contain uninitialized memory, and existing entries
// will be unaltered. It is the caller's responsibility to either provide a non-NULL entryData, or write to the
// returned pointer after calling this function.
void * HashTable_set(HashTable * hashTable, HashTable_key key, void * entryData);

// Removes the entry with the specified key, if it exists, returning true if an entry was successfully deleted
bool HashTable_delete(HashTable * hashTable, HashTable_key key);

// Removes all entries
void HashTable_deleteAll(HashTable * hashTable);

// Returns a heap-allocated array containing all keys stored in this HashTable, optionally writing the count to
// outCount if a non-NULL pointer is provided. The caller is responsible for freeing the returned array. The
// entries in the returned array should be considered fragile; any mutation to HashTable may invalidate then,
// so their contents should not be read again after a subsequent call to HashTable_set(), HashTable_delete(),
// or HashTable_dispose(). The order of keys in a HashTable is undefined, and may change when new items are added.
HashTable_key * HashTable_listKeys(HashTable * hashTable, size_t * outCount);

// Returns a single key without any heap allocation, equivalent to what the element at the specified index would
// have been in the array returned from a call to HashTable_listKeys(). Returns NULL if index is out of range.
// Intended to be used for small numbers of key lookups; if all keys need to be listed, HashTable_listKeys() is
// more performant. The order of keys in a HashTable is undefined, and may change when new items are added.
HashTable_key * HashTable_keyAtIndex(HashTable * hashTable, size_t index);

// Returns true if the HashTable contains any keys that are not of type HASH_KEY_TYPE_STRING
bool HashTable_hasNonStringKeys(HashTable * hashTable);

// Copies all data from fromHashTable to toHashTable, overwriting entries in toHashTable if it already contains
// an item with the same key as an item being copied. The two HashTables must have the same entryDataSize.
void HashTable_merge(HashTable * toHashTable, HashTable * fromHashTable);

// Calls callback for every key/value pair stored in HashTable. Return true from callback in order to continue
// iterating, or false to terminate iteration early. The order of keys in a HashTable is undefined, and may
// change when new items are added. Modifying value during iteration is permitted, and changes to it will be
// immediately stored in the hash table; however, items must not be inserted or removed during iteration.
// Returns true if every callback always returned true; returns false if callback ever returned false.
bool HashTable_foreach(HashTable * hashTable, HashTable_foreachCallback callback, void * callbackContext);

// Calls callback for every key/value pair stored in HashTable. Return true from callback in order to delete
// the specified item, or false to leave it in the table. Similar semantics to HashTable_foreach(), other than
// the meaning of callback's return value. Returns true if any items were deleted.
bool HashTable_deleteMatching(HashTable * hashTable, HashTable_foreachCallback callback, void * callbackContext);

#ifdef __cplusplus
}
#endif
#endif