/*
 * This file is part of LibCSS
 * Licensed under the MIT License,
 *                http://www.opensource.org/licenses/mit-license.php
 * Copyright 2009 John-Mark Bell <jmb@netsurf-browser.org>
 */

#include <stdio.h>
#include <string.h>

#include "stylesheet.h"
#include "select/hash.h"
#include "utils/utils.h"

typedef struct hash_entry {
	const css_selector *sel;
	struct hash_entry *next;
} hash_entry;

typedef struct hash_t {
#define DEFAULT_SLOTS (1<<6)
	size_t n_slots;

	hash_entry *slots;
} hash_t;

struct css_selector_hash {
	hash_t elements;

	hash_t classes;

	hash_t ids;

	hash_entry universal;

	size_t hash_size;

	css_allocator_fn alloc;
	void *pw;
};

static hash_entry empty_slot;

static inline uint32_t _hash_name(lwc_string *name);
static inline lwc_string *_class_name(const css_selector *selector);
static inline lwc_string *_id_name(const css_selector *selector);
static css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head, 
		const css_selector *selector);
static css_error _remove_from_chain(css_selector_hash *ctx, hash_entry *head,
		const css_selector *selector);

static css_error _iterate_elements(css_selector_hash *hash, 
		const css_selector **current,
		const css_selector ***next);
static css_error _iterate_classes(css_selector_hash *hash, 
		const css_selector **current,
		const css_selector ***next);
static css_error _iterate_ids(css_selector_hash *hash, 
		const css_selector **current,
		const css_selector ***next);
static css_error _iterate_universal(css_selector_hash *hash, 
		const css_selector **current,
		const css_selector ***next);

/**
 * Create a hash
 *
 * \param alloc  Memory (de)allocation function
 * \param pw     Pointer to client-specific private data
 * \param hash   Pointer to location to receive result
 * \return CSS_OK on success, appropriate error otherwise
 */
css_error css__selector_hash_create(css_allocator_fn alloc, void *pw, 
		css_selector_hash **hash)
{
	css_selector_hash *h;

	if (alloc == NULL || hash == NULL)
		return CSS_BADPARM;

	h = alloc(0, sizeof(css_selector_hash), pw);
	if (h == NULL)
		return CSS_NOMEM;

	/* Element hash */
	h->elements.slots = alloc(0, DEFAULT_SLOTS * sizeof(hash_entry), pw);
	if (h->elements.slots == NULL) {
		alloc(h, 0, pw);
		return CSS_NOMEM;
	}
	memset(h->elements.slots, 0, DEFAULT_SLOTS * sizeof(hash_entry));
	h->elements.n_slots = DEFAULT_SLOTS;

	/* Class hash */
	h->classes.slots = alloc(0, DEFAULT_SLOTS * sizeof(hash_entry), pw);
	if (h->classes.slots == NULL) {
		alloc(h->elements.slots, 0, pw);
		alloc(h, 0, pw);
		return CSS_NOMEM;
	}
	memset(h->classes.slots, 0, DEFAULT_SLOTS * sizeof(hash_entry));
	h->classes.n_slots = DEFAULT_SLOTS;

	/* ID hash */
	h->ids.slots = alloc(0, DEFAULT_SLOTS * sizeof(hash_entry), pw);
	if (h->ids.slots == NULL) {
		alloc(h->classes.slots, 0, pw);
		alloc(h->elements.slots, 0, pw);
		alloc(h, 0, pw);
		return CSS_NOMEM;
	}
	memset(h->ids.slots, 0, DEFAULT_SLOTS * sizeof(hash_entry));
	h->ids.n_slots = DEFAULT_SLOTS;

	/* Universal chain */
	memset(&h->universal, 0, sizeof(hash_entry));

	h->hash_size = sizeof(css_selector_hash) + 
			DEFAULT_SLOTS * sizeof(hash_entry) +
			DEFAULT_SLOTS * sizeof(hash_entry) +
			DEFAULT_SLOTS * sizeof(hash_entry);

	h->alloc = alloc;
	h->pw = pw;

	*hash = h;

	return CSS_OK;
}

/**
 * Destroy a hash
 *
 * \param hash  The hash to destroy
 * \return CSS_OK on success, appropriate error otherwise
 */
css_error css__selector_hash_destroy(css_selector_hash *hash)
{
	hash_entry *d, *e;
	uint32_t i;

	if (hash == NULL)
		return CSS_BADPARM;

	/* Element hash */
	for (i = 0; i < hash->elements.n_slots; i++) {
		for (d = hash->elements.slots[i].next; d != NULL; d = e) {
			e = d->next;

			hash->alloc(d, 0, hash->pw);
		}
	}
	hash->alloc(hash->elements.slots, 0, hash->pw);

	/* Class hash */
	for (i = 0; i < hash->classes.n_slots; i++) {
		for (d = hash->classes.slots[i].next; d != NULL; d = e) {
			e = d->next;

			hash->alloc(d, 0, hash->pw);
		}
	}
	hash->alloc(hash->classes.slots, 0, hash->pw);

	/* ID hash */
	for (i = 0; i < hash->ids.n_slots; i++) {
		for (d = hash->ids.slots[i].next; d != NULL; d = e) {
			e = d->next;

			hash->alloc(d, 0, hash->pw);
		}
	}
	hash->alloc(hash->ids.slots, 0, hash->pw);

	/* Universal chain */
	for (d = hash->universal.next; d != NULL; d = e) {
		e = d->next;

		hash->alloc(d, 0, hash->pw);
	}

	hash->alloc(hash, 0, hash->pw);

	return CSS_OK;
}

/**
 * Insert an item into a hash
 *
 * \param hash      The hash to insert into
 * \param selector  Pointer to selector
 * \return CSS_OK on success, appropriate error otherwise
 */
css_error css__selector_hash_insert(css_selector_hash *hash,
		const css_selector *selector)
{
	uint32_t index, mask;
	lwc_string *name;
	css_error error;

	if (hash == NULL || selector == NULL)
		return CSS_BADPARM;

	/* Work out which hash to insert into */
	if (lwc_string_length(selector->data.name) != 1 ||
			lwc_string_data(selector->data.name)[0] != '*') {
		/* Named element */
		mask = hash->elements.n_slots - 1;
		index = _hash_name(selector->data.name) & mask;

		error = _insert_into_chain(hash, &hash->elements.slots[index], 
				selector);
	} else if ((name = _class_name(selector)) != NULL) {
		/* Named class */
		mask = hash->classes.n_slots - 1;
		index = _hash_name(name) & mask;

		error = _insert_into_chain(hash, &hash->classes.slots[index], 
				selector);
	} else if ((name = _id_name(selector)) != NULL) {
		/* Named ID */
		mask = hash->ids.n_slots - 1;
		index = _hash_name(name) & mask;

		error = _insert_into_chain(hash, &hash->ids.slots[index], 
				selector);
	} else {
		/* Universal chain */
		error = _insert_into_chain(hash, &hash->universal, selector);
	}

	return error;
}

/**
 * Remove an item from a hash
 *
 * \param hash      The hash to remove from
 * \param selector  Pointer to selector
 * \return CSS_OK on success, appropriate error otherwise
 */
css_error css__selector_hash_remove(css_selector_hash *hash,
		const css_selector *selector)
{
	uint32_t index, mask;
	lwc_string *name;
	css_error error;

	if (hash == NULL || selector == NULL)
		return CSS_BADPARM;

	/* Work out which hash to insert into */
	if (lwc_string_length(selector->data.name) != 1 ||
			lwc_string_data(selector->data.name)[0] != '*') {
		/* Named element */
		mask = hash->elements.n_slots - 1;
		index = _hash_name(selector->data.name) & mask;

		error = _remove_from_chain(hash, &hash->elements.slots[index], 
				selector);
	} else if ((name = _class_name(selector)) != NULL) {
		/* Named class */
		mask = hash->classes.n_slots - 1;
		index = _hash_name(name) & mask;

		error = _remove_from_chain(hash, &hash->classes.slots[index], 
				selector);
	} else if ((name = _id_name(selector)) != NULL) {
		/* Named ID */
		mask = hash->ids.n_slots - 1;
		index = _hash_name(name) & mask;

		error = _remove_from_chain(hash, &hash->ids.slots[index], 
				selector);
	} else {
		/* Universal chain */
		error = _remove_from_chain(hash, &hash->universal, selector);
	}

	return error;
}

/**
 * Find the first selector that matches name
 *
 * \param hash      Hash to search
 * \param name      Name to match
 * \param iterator  Pointer to location to receive iterator function
 * \param matched   Pointer to location to receive selector
 * \return CSS_OK on success, appropriate error otherwise
 *
 * If nothing matches, CSS_OK will be returned and **matched == NULL
 */
css_error css__selector_hash_find(css_selector_hash *hash,
		lwc_string *name, 
		css_selector_hash_iterator *iterator,
		const css_selector ***matched)
{
	uint32_t index, mask;
	hash_entry *head;

	if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
		return CSS_BADPARM;

	/* Find index */
	mask = hash->elements.n_slots - 1;
	index = _hash_name(name) & mask;

	head = &hash->elements.slots[index];

	if (head->sel != NULL) {
		/* Search through chain for first match */
		while (head != NULL) {
			lwc_error lerror;
			bool match = false;

			lerror = lwc_string_caseless_isequal(
					name, head->sel->data.name, &match);
			if (lerror != lwc_error_ok)
				return css_error_from_lwc_error(lerror);

			if (match)
				break;

			head = head->next;
		}

		if (head == NULL)
			head = &empty_slot;
	}

	(*iterator) = _iterate_elements;
	(*matched) = (const css_selector **) head;

	return CSS_OK;
}

/**
 * Find the first selector that has a class that matches name
 *
 * \param hash      Hash to search
 * \param name      Name to match
 * \param iterator  Pointer to location to receive iterator function
 * \param matched   Pointer to location to receive selector
 * \return CSS_OK on success, appropriate error otherwise
 *
 * If nothing matches, CSS_OK will be returned and **matched == NULL
 */
css_error css__selector_hash_find_by_class(css_selector_hash *hash,
		lwc_string *name, 
		css_selector_hash_iterator *iterator,
		const css_selector ***matched)
{
	uint32_t index, mask;
	hash_entry *head;

	if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
		return CSS_BADPARM;

	/* Find index */
	mask = hash->classes.n_slots - 1;
	index = _hash_name(name) & mask;

	head = &hash->classes.slots[index];

	if (head->sel != NULL) {
		/* Search through chain for first match */
		while (head != NULL) {
			lwc_error lerror;
			lwc_string *n;
			bool match = false;

			n = _class_name(head->sel);
			if (n != NULL) {
				lerror = lwc_string_caseless_isequal(
						name, n, &match);
				if (lerror != lwc_error_ok)
					return css_error_from_lwc_error(lerror);

				if (match)
					break;
			}

			head = head->next;
		}

		if (head == NULL)
			head = &empty_slot;
	}

	(*iterator) = _iterate_classes;
	(*matched) = (const css_selector **) head;

	return CSS_OK;
}

/**
 * Find the first selector that has an ID that matches name
 *
 * \param hash      Hash to search
 * \param name      Name to match
 * \param iterator  Pointer to location to receive iterator function
 * \param matched   Pointer to location to receive selector
 * \return CSS_OK on success, appropriate error otherwise
 *
 * If nothing matches, CSS_OK will be returned and **matched == NULL
 */
css_error css__selector_hash_find_by_id(css_selector_hash *hash,
		lwc_string *name, 
		css_selector_hash_iterator *iterator,
		const css_selector ***matched)
{
	uint32_t index, mask;
	hash_entry *head;

	if (hash == NULL || name == NULL || iterator == NULL || matched == NULL)
		return CSS_BADPARM;

	/* Find index */
	mask = hash->ids.n_slots - 1;
	index = _hash_name(name) & mask;

	head = &hash->ids.slots[index];

	if (head->sel != NULL) {
		/* Search through chain for first match */
		while (head != NULL) {
			lwc_error lerror;
			lwc_string *n;
			bool match = false;

			n = _id_name(head->sel);
			if (n != NULL) {
				lerror = lwc_string_caseless_isequal(
						name, n, &match);
				if (lerror != lwc_error_ok)
					return css_error_from_lwc_error(lerror);

				if (match)
					break;
			}

			head = head->next;
		}

		if (head == NULL)
			head = &empty_slot;
	}

	(*iterator) = _iterate_ids;
	(*matched) = (const css_selector **) head;

	return CSS_OK;
}

/**
 * Find the first universal selector
 *
 * \param hash      Hash to search
 * \param iterator  Pointer to location to receive iterator function
 * \param matched   Pointer to location to receive selector
 * \return CSS_OK on success, appropriate error otherwise
 *
 * If nothing matches, CSS_OK will be returned and **matched == NULL
 */
css_error css__selector_hash_find_universal(css_selector_hash *hash,
		css_selector_hash_iterator *iterator,
		const css_selector ***matched)
{
	if (hash == NULL || iterator == NULL || matched == NULL)
		return CSS_BADPARM;

	(*iterator) = _iterate_universal;
	(*matched) = (const css_selector **) &hash->universal;

	return CSS_OK;
}

/**
 * Determine the memory-resident size of a hash
 *
 * \param hash  Hash to consider
 * \param size  Pointer to location to receive byte count
 * \return CSS_OK on success.
 *
 * \note The returned size will represent the size of the hash datastructures,
 *       and will not include the size of the data stored in the hash.
 */
css_error css__selector_hash_size(css_selector_hash *hash, size_t *size)
{
	if (hash == NULL || size == NULL)
		return CSS_BADPARM;

	*size = hash->hash_size;

	return CSS_OK;
}

/******************************************************************************
 * Private functions                                                          *
 ******************************************************************************/

/**
 * Name hash function -- case-insensitive FNV.
 *
 * \param name  Name to hash
 * \return hash value
 */
uint32_t _hash_name(lwc_string *name)
{
	uint32_t z = 0x811c9dc5;
	size_t len = lwc_string_length(name);
	const char *data = lwc_string_data(name);

	while (len > 0) {
		const char c = *data++;

		z *= 0x01000193;
		z ^= ('A' <= c && c <= 'Z') ? (c + 'a' - 'A') : c;

		len--;
	}

	return z;
}

/**
 * Retrieve the first class name in a selector, or NULL if none
 *
 * \param selector  Selector to consider
 * \return Pointer to class name, or NULL if none
 */
lwc_string *_class_name(const css_selector *selector)
{
	const css_selector_detail *detail = &selector->data;
	lwc_string *name = NULL;

	do {
		/* Ignore :not(.class) */
		if (detail->type == CSS_SELECTOR_CLASS && detail->negate == 0) {
			name = detail->name;
			break;
		}

		if (detail->next)
			detail++;
		else
			detail = NULL;
	} while (detail != NULL);

	return name;
}

/**
 * Retrieve the first ID name in a selector, or NULL if none
 *
 * \param selector  Selector to consider
 * \return Pointer to ID name, or NULL if none
 */
lwc_string *_id_name(const css_selector *selector)
{
	const css_selector_detail *detail = &selector->data;
	lwc_string *name = NULL;

	do {
		/* Ignore :not(#id) */
		if (detail->type == CSS_SELECTOR_ID && detail->negate == 0) {
			name = detail->name;
			break;
		}

		if (detail->next)
			detail++;
		else
			detail = NULL;
	} while (detail != NULL);

	return name;
}

/**
 * Insert a selector into a hash chain
 *
 * \param ctx       Selector hash
 * \param head      Head of chain to insert into
 * \param selector  Selector to insert
 * \return CSS_OK    on success,
 *         CSS_NOMEM on memory exhaustion.
 */
css_error _insert_into_chain(css_selector_hash *ctx, hash_entry *head, 
		const css_selector *selector)
{
	if (head->sel == NULL) {
		head->sel = selector;
		head->next = NULL;
	} else {
		hash_entry *search = head;
		hash_entry *prev = NULL;
		hash_entry *entry = 
				ctx->alloc(NULL, sizeof(hash_entry), ctx->pw);
		if (entry == NULL)
			return CSS_NOMEM;

		/* Find place to insert entry */
		do {
			/* Sort by ascending specificity */
			if (search->sel->specificity > selector->specificity)
				break;

			/* Sort by ascending rule index */
			if (search->sel->specificity == selector->specificity &&
					search->sel->rule->index > 
					selector->rule->index)
				break;

			prev = search;
			search = search->next;
		} while (search != NULL);

		if (prev == NULL) {
			entry->sel = head->sel;
			entry->next = head->next;
			head->sel = selector;
			head->next = entry;
		} else {
			entry->sel = selector;
			entry->next = prev->next;
			prev->next = entry;
		}

		ctx->hash_size += sizeof(hash_entry);
	}

	return CSS_OK;
}

/**
 * Remove a selector from a hash chain
 *
 * \param ctx       Selector hash
 * \param head      Head of chain to remove from
 * \param selector  Selector to remove
 * \return CSS_OK       on success,
 *         CSS_INVALID  if selector not found in chain.
 */
css_error _remove_from_chain(css_selector_hash *ctx, hash_entry *head,
		const css_selector *selector)
{
	hash_entry *search = head, *prev = NULL;

	if (head->sel == NULL)
		return CSS_INVALID;

	do {
		if (search->sel == selector)
			break;

		prev = search;
		search = search->next;
	} while (search != NULL);

	if (search == NULL)
		return CSS_INVALID;

	if (prev == NULL) {
		if (search->next != NULL) {
			head->sel = search->next->sel;
			head->next = search->next->next;
		} else {
			head->sel = NULL;
			head->next = NULL;
		}
	} else {
		prev->next = search->next;

		ctx->alloc(search, 0, ctx->pw);

		ctx->hash_size -= sizeof(hash_entry);
	}

	return CSS_OK;
}

/**
 * Find the next selector that matches
 *
 * \param hash     Hash to search
 * \param current  Current item
 * \param next     Pointer to location to receive next item
 * \return CSS_OK on success, appropriate error otherwise
 *
 * If nothing further matches, CSS_OK will be returned and **next == NULL
 */
css_error _iterate_elements(css_selector_hash *hash,
		const css_selector **current,
		const css_selector ***next)
{
	const hash_entry *head = (const hash_entry *) current;
	lwc_string *name;

	if (hash == NULL || current == NULL || next == NULL)
		return CSS_BADPARM;

	name = head->sel->data.name;

	/* Look for the next selector that matches the key */
	for (head = head->next; head != NULL; head = head->next) {
		lwc_error lerror = lwc_error_ok;
		bool match = false;

		lerror = lwc_string_caseless_isequal(
				name, head->sel->data.name, &match);
		if (lerror != lwc_error_ok)
			return css_error_from_lwc_error(lerror);

		if (match)
			break;
	}

	if (head == NULL)
		head = &empty_slot;

	(*next) = (const css_selector **) head;

	return CSS_OK;
}

/**
 * Find the next selector that matches
 *
 * \param hash     Hash to search
 * \param current  Current item
 * \param next     Pointer to location to receive next item
 * \return CSS_OK on success, appropriate error otherwise
 *
 * If nothing further matches, CSS_OK will be returned and **next == NULL
 */
css_error _iterate_classes(css_selector_hash *hash,
		const css_selector **current,
		const css_selector ***next)
{
	const hash_entry *head = (const hash_entry *) current;
	lwc_string *ref;

	if (hash == NULL || current == NULL || next == NULL)
		return CSS_BADPARM;

	ref = _class_name(head->sel);

	/* Look for the next selector that matches the key */
	for (head = head->next; head != NULL; head = head->next) {
		lwc_error lerror = lwc_error_ok;
		lwc_string *name;
		bool match = false;

		name = _class_name(head->sel);
		if (name == NULL)
			continue;

		lerror = lwc_string_caseless_isequal(
				ref, name, &match);
		if (lerror != lwc_error_ok)
			return css_error_from_lwc_error(lerror);

		if (match)
			break;
	}

	if (head == NULL)
		head = &empty_slot;

	(*next) = (const css_selector **) head;

	return CSS_OK;
}

/**
 * Find the next selector that matches
 *
 * \param hash     Hash to search
 * \param current  Current item
 * \param next     Pointer to location to receive next item
 * \return CSS_OK on success, appropriate error otherwise
 *
 * If nothing further matches, CSS_OK will be returned and **next == NULL
 */
css_error _iterate_ids(css_selector_hash *hash,
		const css_selector **current,
		const css_selector ***next)
{
	const hash_entry *head = (const hash_entry *) current;
	lwc_string *ref;

	if (hash == NULL || current == NULL || next == NULL)
		return CSS_BADPARM;

	ref = _id_name(head->sel);

	/* Look for the next selector that matches the key */
	for (head = head->next; head != NULL; head = head->next) {
		lwc_error lerror = lwc_error_ok;
		lwc_string *name;
		bool match = false;

		name = _id_name(head->sel);
		if (name == NULL)
			continue;

		lerror = lwc_string_caseless_isequal(
				ref, name, &match);
		if (lerror != lwc_error_ok)
			return css_error_from_lwc_error(lerror);

		if (match)
			break;
	}

	if (head == NULL)
		head = &empty_slot;

	(*next) = (const css_selector **) head;

	return CSS_OK;
}

/**
 * Find the next selector that matches
 *
 * \param hash     Hash to search
 * \param current  Current item
 * \param next     Pointer to location to receive next item
 * \return CSS_OK on success, appropriate error otherwise
 *
 * If nothing further matches, CSS_OK will be returned and **next == NULL
 */
css_error _iterate_universal(css_selector_hash *hash,
		const css_selector **current,
		const css_selector ***next)
{
	const hash_entry *head = (const hash_entry *) current;

	if (hash == NULL || current == NULL || next == NULL)
		return CSS_BADPARM;

	if (head->next == NULL)
		head = &empty_slot;
	else
		head = head->next;

	(*next) = (const css_selector **) head;

	return CSS_OK;
}