/*
 * Copyright © 2026 Kana Steimle
 *
 * 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.
 */

#define _DEFAULT_SOURCE
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include "table.h"

typedef struct table table_t;

struct table {
	size_t alloclength; ///< Number of key-value pairs allocated.
	size_t length; ///< Number of key-value pairs actually in use.
	struct kvpair {
		char *key; ///< A string used to refer to the value.
		void *value; ///< A generic pointer, typically used to point to data associated with the key.
	} *kvpairs; ///< An array containing each key and its associated value.
	copyval_f *copyval; ///< The function used to copy values for this table.
	freeval_f *freeval; ///< The function used to free values for this table.
	cmpkeys_f *cmpkeys; ///< The function used to free values for this table.
};

table_t *table_create (copyval_f *copyval, freeval_f *freeval, cmpkeys_f *cmpkeys) {
	table_t *table = malloc(sizeof(*table));
	if (table == NULL) goto err0;
	table->alloclength = 16;
	table->kvpairs = calloc(sizeof(*table->kvpairs), table->alloclength);
	if (table->kvpairs == NULL) goto err1;
	table->copyval = copyval;
	table->freeval = freeval;
	table->cmpkeys = cmpkeys == NULL ? strcmp : cmpkeys;
	table->length = 0;
	return table;
err1:
	free(table);
err0:
	return NULL;
}

table_t *table_copy (table_t const *original) {
	table_t *table = malloc(sizeof(*table));
	if (table == NULL) goto err0;
	table->alloclength = original->alloclength;
	table->kvpairs = calloc(sizeof(*table->kvpairs), table->alloclength);
	if (table->kvpairs == NULL) goto err1;

	table->copyval = original->copyval;
	table->freeval = original->freeval;
	table->length = 0;
err1:
	free(table);
err0:
	return NULL;
}

table_t *table_merge (table_t const **originals, size_t numoriginals) {
	size_t origindexes[numoriginals];
	if (numoriginals == 0) goto err0;
	table_t *table = malloc(sizeof(*table));
	if (table == NULL) goto err0;
	table->length = 0;
	table->copyval = originals[0]->copyval;
	table->freeval = originals[0]->freeval;
	table->cmpkeys = originals[0]->cmpkeys;
	// We track the target table length separately from the table length, so that if an error occurs we know how many key / value pairs to free.
	size_t targettablelength = 0;
	// Calculate the maximum total length of the new table, while also checking the copyval / freeval functions and initializing each original table's index to 0
	for (size_t i=0; i<numoriginals; ++i) {
		targettablelength += originals[i]->length;
		if (table->copyval != originals[i]->copyval || table->freeval != originals[i]->freeval || table->cmpkeys != originals[i]->cmpkeys) goto err1;
		origindexes[i] = 0;
	}
	table->alloclength = 16;
	// Allocate enough space to hold the new table's contents
	while (table->alloclength < targettablelength) table->alloclength *= 2;
	table->kvpairs = calloc(sizeof(*table->kvpairs), table->alloclength);
	if (table->kvpairs == NULL) goto err1;
	// We need to track which table we can initialize the minimum key from
	size_t initminorigindex = 0;
	for (size_t i=0; i<targettablelength; ++i) {
		while (origindexes[initminorigindex] >= originals[initminorigindex]->length) {
			if (++initminorigindex >= numoriginals) break;
		}
		if (initminorigindex >= numoriginals) break;
		size_t minorigindex = initminorigindex;
		char const *minkey = originals[initminorigindex]->kvpairs[origindexes[initminorigindex]].key;
		// Find the next key that sorts the lowest. Since the tables should already be sorted, the next lowest key should be the first in one of the tables.
		for (size_t j=initminorigindex+1; j<numoriginals; ++j) {
			// Skip tables we've already reached the end of
			if (origindexes[j] >= originals[j]->length) continue;
			// Compare the current minimum key to the next key
			char const *cmpkey = originals[j]->kvpairs[origindexes[j]].key;
			int cmp = table->cmpkeys(minkey, cmpkey);
			if (cmp > 0) {
				// If this key is lower, it becomes the new minimum
				minorigindex = j;
				minkey = cmpkey;
			} else if (cmp == 0) {
				// If we find a duplicate of another key, skip it.
				// This will also decrease the target table length, but should never put the current index out of bounds, since this comparison inherently means there's at least one other key.
				++origindexes[j];
				--targettablelength;
				continue;
			}
		}
		void *minvalue = originals[minorigindex]->kvpairs[origindexes[minorigindex]].value;
		// Increment the index of the table we've added the key from
		++origindexes[minorigindex];
		// Add the key and its value to the new table
		table->kvpairs[table->length].key = strdup(minkey);
		if (table->kvpairs[table->length].key == NULL) goto err2;
		// Increment the table length here to make sure if an error occurs, we free this key's string
		++table->length;
		// If the copyval function is set and the value isn't NULL, use it to copy the original value
		if (table->copyval != NULL && minvalue != NULL) {
			table->kvpairs[i].value = table->copyval(minvalue);
			if (table->kvpairs[i].value == NULL) goto err2;
		} else {
			table->kvpairs[i].value = minvalue;
		}
	}
	return table;
err2:
	for (size_t i=0; i<table->length; ++i) {
		free(table->kvpairs[i].key);
	}
	if (table->freeval != NULL) {
		for (size_t i=0; i<table->length; ++i) {
			if (table->kvpairs[i].value != NULL) {
				table->freeval(table->kvpairs[i].value);
			}
		}
	}
	free(table->kvpairs);
err1:
	free(table);
err0:
	return NULL;
}

void table_delete (table_t *table) {
	for (size_t i=0; i<table->length; ++i) {
		free(table->kvpairs[i].key);
	}
	if (table->freeval != NULL) {
		for (size_t i=0; i<table->length; ++i) {
			if (table->kvpairs[i].value != NULL) {
				table->freeval(table->kvpairs[i].value);
			}
		}
	}
	free(table);
}

size_t table_length (table_t const *table) {
	return table->length;
}

int table_getindex (table_t const *table, size_t index, char const **key, void const **value) {
	if (index >= table->length) return 1;
	if (key != NULL) *key = table->kvpairs[index].key;
	if (value != NULL) *value = table->kvpairs[index].value;
	return 0;
}

/**
 * Returns the index into a table where a key is, or where that key should be inserted if it doesn't exist yet.
 * Also returns 0 in cmp is the index is a match, or non-zero if it isn't a match.
 */
static size_t table_locatekeyrange (table_t const *table, char const *key, size_t min, size_t max, int *cmp) {
	size_t mid;
	while (min <= max) {
		mid = (min + max) / 2;
		*cmp = table->cmpkeys(key, table->kvpairs[mid].key);
		if (*cmp > 0) {
			min=mid+1;
		} else if (*cmp < 0) {
			// Exit here if mid is 0, because otherwise we'd be attempting to assign a negative value to an unsigned number
			if (mid == 0) break;
			max=mid-1;
		} else {
			return mid;
		}
	}
	return min;
}

// Wraps table_locatekeyrange, while also handling the index cache input
static inline size_t table_locatekey (table_t const *table, char const *key, size_t const *indexcache, int *cmp) {
	if (table->length == 0) {
		*cmp = 1;
		return 0;
	}
	if (indexcache != NULL && *indexcache < table->length) {
		*cmp = table->cmpkeys(key, table->kvpairs[*indexcache].key);
		if (cmp > 0) {
			return table_locatekeyrange(table, key, *indexcache+1, table->length-1, cmp);
		} else if (cmp < 0) {
			return table_locatekeyrange(table, key, 0, *indexcache-1, cmp);
		} else {
			return *indexcache;
		}
	} else {
		return table_locatekeyrange(table, key, 0, table->length-1, cmp);
	}
}

int table_getval (table_t const *table, size_t *indexcache, char const *key, void **value) {
	int cmp;
	size_t index = table_locatekey(table, key, indexcache, &cmp);
	if (!cmp) {
		if (indexcache != NULL) *indexcache = index;
		if (value != NULL) *value = table->kvpairs[index].value;
		return 0;
	} else {
		return 1;
	}
}

int table_getvalcopy (table_t const *table, size_t *indexcache, char const *key, void **value) {
	if (table->copyval == NULL || value == NULL) {
		return table_getval(table, indexcache, key, value);
	} else {
		void *origvalue = NULL;
		if (table_getval(table, indexcache, key, &origvalue)) return 1;
		void *newvalue = table->copyval(origvalue);
		if (newvalue == NULL) return -1;
		*value = newvalue;
		return 0;
	}
}

// Ensure that the table can fit the specified number of values, resizing it if necessary.
// Returns -1 if an allocation error occurs.
static int table_fit (table_t *table, size_t targetlength) {
	if (table->alloclength < targetlength) {
		size_t nalloclength = table->alloclength;
		do nalloclength *= 2; while (nalloclength < targetlength);
		struct kvpair *nkvpairs = reallocarray(table->kvpairs, sizeof(*nkvpairs), nalloclength);
		if (nkvpairs == NULL) return -1;
		table->kvpairs = nkvpairs;
		table->alloclength = nalloclength;
	}
	return 0;
}

// Insert a key into the table
static inline int table_insert (table_t *table, size_t index, char const *key, void *value) {
	char *nkey = strdup(key);
	if (nkey == 0) goto err0;
	void *nvalue = value;
	if (table->copyval != NULL && value != NULL) {
		nvalue = table->copyval(value);
		if (nvalue == NULL) goto err1;
	}
	if (table_fit(table, table->length+1)) goto err2;
	memmove(&table->kvpairs[index+1], &table->kvpairs[index], sizeof(*table->kvpairs)*(table->length-index));
	table->kvpairs[index].key = nkey;
	table->kvpairs[index].value = nvalue;
	++table->length;
	return 0;
err2:
	if (table->copyval != NULL && value != NULL) free(nvalue);
err1:
	free(nkey);
err0:
	return -1;
}

static inline int table_replace (table_t *table, size_t index, void *value) {
	void *nvalue = value;
	if (table->copyval != NULL && value != NULL) {
		nvalue = table->copyval(value);
		if (nvalue == NULL) return -1;
	}
	table->kvpairs[index].value = nvalue;
	return 0;
}

int table_setval (table_t *table, size_t *indexcache, char const *key, void *value) {
	int cmp;
	size_t index = table_locatekey(table, key, indexcache, &cmp);
	int ret;
	if (!cmp) {
		ret = table_replace(table, index, value);
	} else {
		ret = table_insert(table, index, key, value);
	}
	if (ret) return ret;
	if (indexcache != NULL) *indexcache = index;
	return 0;
}

int table_addval (table_t *table, size_t *indexcache, char const *key, void *value) {
	int cmp;
	size_t index = table_locatekey(table, key, indexcache, &cmp);
	int ret;
	if (!cmp) {
		if (indexcache != NULL) *indexcache = index;
		return 1;
	} else {
		ret = table_insert(table, index, key, value);
	}
	if (ret) return ret;
	if (indexcache != NULL) *indexcache = index;
	return 0;
}

int table_unsetval (table_t *table, size_t *indexcache, char const *key) {
	int cmp;
	size_t index = table_locatekey(table, key, indexcache, &cmp);
	if (!cmp) {
		if (indexcache != NULL) *indexcache = index;
		free(table->kvpairs[index].key);
		if (table->freeval != NULL && table->kvpairs[index].value != NULL) table->freeval(table->kvpairs[index].value);
		--table->length;
		memmove(&table->kvpairs[index], &table->kvpairs[index+1], sizeof(*table->kvpairs)*(table->length-index));
		return 0;
	} else {
		return 1;
	}
}