/*

 * Copyright (C) 2011 Red Hat, Inc.

 *

 * Author: Angus Salkeld <asalkeld@redhat.com>

 *

 * This file is part of libqb.

 *

 * libqb is free software: you can redistribute it and/or modify

 * it under the terms of the GNU Lesser General Public License as published by

 * the Free Software Foundation, either version 2.1 of the License, or

 * (at your option) any later version.

 *

 * libqb is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public License

 * along with libqb.  If not, see <http://www.gnu.org/licenses/>.

 */

#include <os_base.h>

#include <assert.h>

#include <qb/qbdefs.h>

#include <qb/qblist.h>

#include <qb/qbmap.h>

#include "map_int.h"

struct trie_iter {

	struct qb_map_iter i;

	const char *prefix;

	struct trie_node *n;

	struct trie_node *root;

};

struct trie_node {

	uint32_t idx;

	char *segment;

	uint32_t num_segments;

	char *key;

	void *value;

	struct trie_node **children;

	uint32_t num_children;

	uint32_t refcount;

	struct trie_node *parent;

	struct qb_list_head *notifier_head;

};

struct trie {

	struct qb_map map;

	size_t length;

	uint32_t num_nodes;

	uint32_t mem_used;

	struct trie_node *header;

};

static void trie_notify(struct trie_node *n, uint32_t event, const char *key,

			void *old_value, void *value);

static struct trie_node *trie_new_node(struct trie *t, struct trie_node *parent);

static void trie_destroy_node(struct trie_node *node);

/*

 * characters are stored in reverse to make accessing the

 * more common case (non-control chars) more space efficient.

 */

#define TRIE_CHAR2INDEX(ch) (126 - ch)

#define TRIE_INDEX2CHAR(idx) (126 - idx)

static int32_t

trie_node_alive(struct trie_node *node)

{

	if (node->value == NULL ||

	    node->refcount <= 0) {

		return QB_FALSE;

	}

	return QB_TRUE;

}

static struct trie_node *

trie_node_next(struct trie_node *node, struct trie_node *root, int all)

{

	struct trie_node *c = node;

	struct trie_node *n;

	struct trie_node *p;

	int i;

keep_going:

	n = NULL;

	/* child/outward

	 */

	for (i = c->num_children - 1; i >= 0; i--) {

		if (c->children[i]) {

			n = c->children[i];

			break;

		}

	}

	if (n) {

		if (all || trie_node_alive(n)) {

			return n;

		} else {

			c = n;

			goto keep_going;

		}

	}

	/* sibling/parent

	 */

	if (c == root) {

		return NULL;

	}

	p = c;

	do {

		for (i = p->idx - 1; i >= 0; i--) {

			if (p->parent->children[i]) {

				n = p->parent->children[i];

				break;

			}

		}

		if (n == NULL) {

			p = p->parent;

		}

	} while (n == NULL && p != root);

	if (n) {

		if (all || trie_node_alive(n)) {

			return n;

		}

		if (n == root) {

			return NULL;

		}

		c = n;

		goto keep_going;

	}

	return n;

}

static struct trie_node *

new_child_node(struct trie *t, struct trie_node * parent, char ch)

{

	struct trie_node *new_node;

	int old_max_idx;

	int i;

	int idx = TRIE_CHAR2INDEX(ch);

	if (idx >= parent->num_children) {

		old_max_idx = parent->num_children;

		parent->num_children = QB_MAX(idx + 1, 30);

		t->mem_used += (sizeof(struct trie_node*) * (parent->num_children - old_max_idx));

		parent->children = realloc(parent->children,

				(parent->num_children * sizeof(struct trie_node*)));

		if (parent->children == NULL) {

			return NULL;

		}

		for (i = old_max_idx; i < parent->num_children; i++) {

			parent->children[i] = NULL;

		}

	}

	new_node = trie_new_node(t, parent);

	if (new_node == NULL) {

		return NULL;

	}

	new_node->idx = idx;

	parent->children[idx] = new_node;

	return new_node;

}

static struct trie_node *

trie_node_split(struct trie *t, struct trie_node *cur_node, int seg_cnt)

{

	struct trie_node *split_node;

	struct trie_node ** children = cur_node->children;

	uint32_t num_children = cur_node->num_children;

	struct qb_list_head *tmp;

	int i;

	int s;

	cur_node->children = NULL;

	cur_node->num_children = 0;

	split_node = new_child_node(t, cur_node, cur_node->segment[seg_cnt]);

	if (split_node == NULL) {

		return NULL;

	}

	split_node->children = children;

	split_node->num_children = num_children;

	for (i = 0; i < split_node->num_children; i++) {

		if (split_node->children[i]) {

			split_node->children[i]->parent = split_node;

		}

	}

	split_node->value = cur_node->value;

	split_node->key = cur_node->key;

	split_node->refcount = cur_node->refcount;

	cur_node->value = NULL;

	cur_node->key = NULL;

	cur_node->refcount = 0;

	/* move notifier list to split */

	tmp = split_node->notifier_head;

	split_node->notifier_head = cur_node->notifier_head;

	cur_node->notifier_head = tmp;

	qb_list_init(cur_node->notifier_head);

	if (seg_cnt < cur_node->num_segments) {

		split_node->num_segments = cur_node->num_segments - seg_cnt - 1;

		split_node->segment = malloc(split_node->num_segments * sizeof(char));

		if (split_node->segment == NULL) {

			trie_destroy_node(split_node);

			return NULL;

		}

		for (i = (seg_cnt + 1); i < cur_node->num_segments; i++) {

			s = i - seg_cnt - 1;

			split_node->segment[s] = cur_node->segment[i];

			cur_node->segment[i] = '\0';

		}

		cur_node->num_segments = seg_cnt;

	}

	return cur_node;

}

static struct trie_node *

trie_insert(struct trie *t, const char *key)

{

	struct trie_node *cur_node = t->header;

	struct trie_node *new_node;

	char *cur = (char *)key;

	int idx = TRIE_CHAR2INDEX(key[0]);

	int seg_cnt = 0;

	do {

		new_node = NULL;

		if (cur_node->num_segments > 0 &&

		    seg_cnt < cur_node->num_segments) {

			if (cur_node->segment[seg_cnt] == *cur) {

				/* we found the char in the segment */

				seg_cnt++;

			} else {

				cur_node = trie_node_split(t, cur_node, seg_cnt);

				if (cur_node == NULL) {

					return NULL;

				}

				new_node = new_child_node(t, cur_node, *cur);

				if (new_node == NULL) {

					return NULL;

				}

			}

		} else if (idx < cur_node->num_children &&

		    cur_node->children[idx]) {

			/* the char can be found on the next node */

			new_node = cur_node->children[idx];

		} else if (cur_node == t->header) {

			/* the root node is empty so make it on the next node */

			new_node = new_child_node(t, cur_node, *cur);

			if (new_node == NULL) {

				return NULL;

			}

		} else if (cur_node->value == NULL &&

			   qb_list_empty(cur_node->notifier_head) &&

			   cur_node->num_children == 0 &&

			   seg_cnt == cur_node->num_segments) {

			/* we are on a leaf (with no value) so just add it as a segment */

			cur_node->segment = realloc(cur_node->segment, cur_node->num_segments + 1);

			cur_node->segment[cur_node->num_segments] = *cur;

			t->mem_used += sizeof(char);

			cur_node->num_segments++;

			seg_cnt++;

		} else if (seg_cnt == cur_node->num_segments) {

			/* on the last segment need to make a new node */

			new_node = new_child_node(t, cur_node, *cur);

			if (new_node == NULL) {

				return NULL;

			}

		} else /* need_to_split */ {

			cur_node = trie_node_split(t, cur_node, seg_cnt);

			if (cur_node == NULL) {

				return NULL;

			}

			new_node = new_child_node(t, cur_node, *cur);

			if (new_node == NULL) {

				return NULL;

			}

		}

		if (new_node) {

			seg_cnt = 0;

			cur_node = new_node;

		}

		cur++;

		idx = TRIE_CHAR2INDEX(*cur);

	} while (*cur != '\0');

	if (cur_node->num_segments > 0 &&

	    seg_cnt < cur_node->num_segments) {

		/* we need to split */

		cur_node = trie_node_split(t, cur_node, seg_cnt);

		if (cur_node == NULL) {

			return NULL;

		}

		new_node = new_child_node(t, cur_node, *cur);

		if (new_node == NULL) {

			return NULL;

		}

	}

	return cur_node;

}

static struct trie_node *

trie_lookup(struct trie *t, const char *key, int exact_match)

{

	struct trie_node *cur_node = t->header;

	char *cur = (char *)key;

	int idx = TRIE_CHAR2INDEX(key[0]);

	int seg_cnt = 0;

	do {

		if (cur_node->num_segments > 0 &&

		    seg_cnt < cur_node->num_segments) {

			if (cur_node->segment[seg_cnt] == *cur) {

				/* we found the char in the segment */

				seg_cnt++;

			} else {

				return NULL;

			}

		} else if (idx < cur_node->num_children &&

		    cur_node->children[idx]) {

			/* the char can be found on the next node */

			cur_node = cur_node->children[idx];

			seg_cnt = 0;

		} else {

			return NULL;

		}

		cur++;

		idx = TRIE_CHAR2INDEX(*cur);

	} while (*cur != '\0');

	if (exact_match &&

	    cur_node->num_segments > 0 &&

	    seg_cnt < cur_node->num_segments) {

		return NULL;

	}

	return cur_node;

}

static void

trie_node_release(struct trie *t, struct trie_node *node)

{

	int i;

	int empty = QB_FALSE;

	if (node->key == NULL &&

	    node->parent != NULL &&

	    qb_list_empty(node->notifier_head)) {

		struct trie_node *p = node->parent;

		if (node->num_children == 0) {

			empty = QB_TRUE;

		} else {

			empty = QB_TRUE;

			for (i = node->num_children - 1; i >= 0; i--) {

				if (node->children[i]) {

					empty = QB_FALSE;

					break;

				}

			}

		}

		if (!empty) {

			return;

		}

		/*

		 * unlink the node from the parent

		 */

		p->children[node->idx] = NULL;

		trie_destroy_node(node);

		t->num_nodes--;

		t->mem_used -= sizeof(struct trie_node);

		trie_node_release(t, p);

	}

}

static void

trie_node_destroy(struct trie *t, struct trie_node *n)

{

	if (n->value == NULL) {

		return;

	}

	trie_notify(n, QB_MAP_NOTIFY_DELETED, n->key, n->value, NULL);

	n->key = NULL;

	n->value = NULL;

	trie_node_release(t, n);

}

static void

trie_print_node(struct trie_node *n, struct trie_node *r, const char *suffix)

{

	int i;

	if (n->parent) {

		trie_print_node(n->parent, n, suffix);

	}

	if (n->idx == 0) {

		return;

	}

	printf("[%c", (char) TRIE_INDEX2CHAR(n->idx));

	for (i = 0; i < n->num_segments; i++) {

		printf("%c", n->segment[i]);

	}

	if (n == r) {

#ifndef S_SPLINT_S

		printf("] (%" PRIu32 ") %s\n", n->refcount, suffix);

#endif /* S_SPLINT_S */

	} else {

		printf("] ");

	}

}

static void

trie_node_ref(struct trie *t, struct trie_node *node)

{

	if (t->header == node) {

		return;

	}

	node->refcount++;

}

static void

trie_node_deref(struct trie *t, struct trie_node *node)

{

	if (!trie_node_alive(node)) {

		return;

	}

	node->refcount--;

	if (node->refcount > 0) {

		return;

	}

	trie_node_destroy(t, node);

}

static void

trie_destroy(struct qb_map *map)

{

	struct trie *t = (struct trie *)map;

	struct trie_node *cur_node = t->header;

	struct trie_node *fwd_node;

	do {

		fwd_node = trie_node_next(cur_node, t->header, QB_FALSE);

		trie_node_destroy(t, cur_node);

	} while ((cur_node = fwd_node));

	free(t);

}

static void

trie_destroy_node(struct trie_node *node)

{

	free(node->segment);

	free(node->children);

	free(node->notifier_head);

	free(node);

}

static struct trie_node *

trie_new_node(struct trie *t, struct trie_node *parent)

{

	struct trie_node *new_node = calloc(1, sizeof(struct trie_node));

	if (new_node == NULL) {

		return NULL;

	}

	new_node->notifier_head = calloc(1, sizeof(struct qb_list_head));

	if (new_node->notifier_head == NULL) {

		free(new_node);

		return NULL;

	}

	new_node->parent = parent;

	new_node->num_children = 0;

	new_node->children = NULL;

	new_node->num_segments = 0;

	new_node->segment = NULL;

	t->num_nodes++;

	t->mem_used += sizeof(struct trie_node);

	qb_list_init(new_node->notifier_head);

	return new_node;

}

void

qb_trie_dump(qb_map_t* m)

{

	struct trie * t = (struct trie*)m;

	struct trie_node *n;

	if (t == NULL) {

		return;

	}

#ifndef S_SPLINT_S

	printf("nodes: %" PRIu32 ", bytes: %" PRIu32 "\n", t->num_nodes, t->mem_used);

#endif /* S_SPLINT_S */

	n = t->header;

	do {

		if (n->num_children == 0) {

			trie_print_node(n, n, " ");

		}

		n = trie_node_next(n, t->header, QB_FALSE);

	} while (n);

}

static void

trie_put(struct qb_map *map, const char *key, const void *value)

{

	struct trie *t = (struct trie *)map;

	struct trie_node *n = trie_insert(t, key);

	if (n) {

		const char *old_value = n->value;

		const char *old_key = n->key;

		n->key = (char *)key;

		n->value = (void *)value;

		if (old_value == NULL) {

			trie_node_ref(t, n);

			t->length++;

			trie_notify(n, QB_MAP_NOTIFY_INSERTED,

				    n->key, NULL, n->value);

		} else {

			trie_notify(n, QB_MAP_NOTIFY_REPLACED,

				    (char *)old_key, (void *)old_value,

				    (void *)value);

		}

	}

}

static int32_t

trie_rm(struct qb_map *map, const char *key)

{

	struct trie *t = (struct trie *)map;

	struct trie_node *n = trie_lookup(t, key, QB_TRUE);

	if (n) {

		trie_node_deref(t, n);

		t->length--;

		return QB_TRUE;

	} else {

		return QB_FALSE;

	}

}

static void *

trie_get(struct qb_map *map, const char *key)

{

	struct trie *t = (struct trie *)map;

	struct trie_node *n = trie_lookup(t, key, QB_TRUE);

	if (n) {

		return n->value;

	}

	return NULL;

}

static void

trie_notify_deref(struct qb_map_notifier *f)

{

	f->refcount--;

	if (f->refcount == 0) {

		qb_list_del(&f->list);

		free(f);

	}

}

static void

trie_notify_ref(struct qb_map_notifier *f)

{

	f->refcount++;

}

static void

trie_notify(struct trie_node *n,

	    uint32_t event, const char *key, void *old_value, void *value)

{

	struct trie_node *c = n;

	struct qb_list_head *list;

	struct qb_list_head *next;

	struct qb_list_head *head;

	struct qb_map_notifier *tn;

	do {

		head = c->notifier_head;

		qb_list_for_each_safe(list, next, head) {

			tn = qb_list_entry(list, struct qb_map_notifier, list);

			trie_notify_ref(tn);

			if ((tn->events & event) &&

			    ((tn->events & QB_MAP_NOTIFY_RECURSIVE) ||

			     (n == c))) {

				tn->callback(event, (char *)key, old_value,

					     value, tn->user_data);

			}

			if (((event & QB_MAP_NOTIFY_DELETED) ||

			     (event & QB_MAP_NOTIFY_REPLACED)) &&

			    (tn->events & QB_MAP_NOTIFY_FREE)) {

				tn->callback(QB_MAP_NOTIFY_FREE, (char *)key,

					     old_value, value, tn->user_data);

			}

			trie_notify_deref(tn);

		}

		c = c->parent;

	} while (c);

}

static int32_t

trie_notify_add(qb_map_t * m, const char *key,

		qb_map_notify_fn fn, int32_t events, void *user_data)

{

	struct trie *t = (struct trie *)m;

	struct qb_map_notifier *f;

	struct trie_node *n;

	struct qb_list_head *list;

	int add_to_tail = QB_FALSE;

	if (key) {

		n = trie_lookup(t, key, QB_TRUE);

		if (n == NULL) {

			n = trie_insert(t, key);

		}

	} else {

		n = t->header;

	}

	if (n) {

		qb_list_for_each(list, n->notifier_head) {

			f = qb_list_entry(list, struct qb_map_notifier, list);

			if (events & QB_MAP_NOTIFY_FREE &&

			    f->events == events) {

				/* only one free notifier */

				return -EEXIST;

			}

			if (f->events == events &&

			    f->callback == fn &&

			    f->user_data == user_data) {

				return -EEXIST;

			}

		}

		f = malloc(sizeof(struct qb_map_notifier));

		if (f == NULL) {

			return -errno;

		}

		f->events = events;

		f->user_data = user_data;

		f->callback = fn;

		f->refcount = 1;

		qb_list_init(&f->list);

		if (key) {

			if (events & QB_MAP_NOTIFY_RECURSIVE) {

				add_to_tail = QB_TRUE;

			}

		} else {

			if (events & QB_MAP_NOTIFY_FREE) {

				add_to_tail = QB_TRUE;

			}

		}

		if (add_to_tail) {

			qb_list_add_tail(&f->list, n->notifier_head);

		} else {

			qb_list_add(&f->list, n->notifier_head);

		}

		return 0;

	}

	return -EINVAL;

}

static int32_t

trie_notify_del(qb_map_t * m, const char *key,

		qb_map_notify_fn fn, int32_t events,

		int32_t cmp_userdata, void *user_data)

{

	struct trie *t = (struct trie *)m;

	struct trie_node *n;

	struct qb_list_head *list;

	struct qb_list_head *next;

	int32_t found = QB_FALSE;

	if (key) {

		n = trie_lookup(t, key, QB_FALSE);

	} else {

		n = t->header;

	}

	if (n == NULL) {

		return -ENOENT;

	}

	qb_list_for_each_safe(list, next, n->notifier_head) {

		struct qb_map_notifier *f = qb_list_entry(list, struct qb_map_notifier, list);

		if (f->events == events && f->callback == fn) {

			if (cmp_userdata && (f->user_data == user_data)) {

				trie_notify_deref(f);

				found = QB_TRUE;

			} else if (!cmp_userdata) {

				trie_notify_deref(f);

				found = QB_TRUE;

			}

		}

	}

	if (found) {

		trie_node_release(t, n);

		return 0;

	} else {

		return -ENOENT;

	}

}

static qb_map_iter_t *

trie_iter_create(struct qb_map *map, const char *prefix)

{

	struct trie_iter *i = malloc(sizeof(struct trie_iter));

	struct trie *t = (struct trie *)map;

	if (i == NULL) {

		return NULL;

	}

	i->i.m = map;

	i->prefix = prefix;

	i->n = t->header;

	i->root = t->header;

	return (qb_map_iter_t *) i;

}

static const char *

trie_iter_next(qb_map_iter_t * i, void **value)

{

	struct trie_iter *si = (struct trie_iter *)i;

	struct trie_node *p = si->n;

	struct trie *t = (struct trie *)(i->m);

	if (p == NULL) {

		return NULL;

	}

	if (p->parent == NULL && si->prefix) {

		si->root = trie_lookup(t, si->prefix, QB_FALSE);

		if (si->root == NULL) {

			si->n = NULL;

		} else if (si->root->value == NULL) {

			si->n = trie_node_next(si->root, si->root, QB_FALSE);

		} else {

			si->n = si->root;

		}

	} else {

		si->n = trie_node_next(p, si->root, QB_FALSE);

	}

	if (si->n == NULL) {

		trie_node_deref(t, p);

		return NULL;

	}

	trie_node_ref(t, si->n);

	trie_node_deref(t, p);

	*value = si->n->value;

	return si->n->key;

}

static void

trie_iter_free(qb_map_iter_t * i)

{

	struct trie_iter *si = (struct trie_iter *)i;

	struct trie *t = (struct trie *)(i->m);

	if (si->n != NULL) {

		/* if free'ing the iterator before getting to the last

		 * node make sure we de-ref the current node.

		 */

		trie_node_deref(t, si->n);

	}

	free(i);

}

static size_t

trie_count_get(struct qb_map *map)

{

	struct trie *list = (struct trie *)map;

	return list->length;

}

qb_map_t *

qb_trie_create(void)

{

	struct trie *t = malloc(sizeof(struct trie));

	if (t == NULL) {

		return NULL;

	}

	t->map.put = trie_put;

	t->map.get = trie_get;

	t->map.rm = trie_rm;

	t->map.count_get = trie_count_get;

	t->map.iter_create = trie_iter_create;

	t->map.iter_next = trie_iter_next;

	t->map.iter_free = trie_iter_free;

	t->map.destroy = trie_destroy;

	t->map.notify_add = trie_notify_add;

	t->map.notify_del = trie_notify_del;

	t->length = 0;

	t->num_nodes = 0;

	t->mem_used = sizeof(struct trie);

	t->header = trie_new_node(t, NULL);

	return (qb_map_t *) t;

}