/* heap.c - an array based d-ary heap implementation
 *
 * Copyright (C) 2009 Timo Teräs <timo.teras@iki.fi>
 * All rights reserved.
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 or later as
 * published by the Free Software Foundation.
 *
 * See http://www.gnu.org/ for details.
 */

#include <errno.h>
#include <string.h>
#include <libtf/heap.h>

#define compare_values(a, b) tf_mtime_diff(a, b)

static inline int tf_heap_parent(int index)
{
	return (index - TF_HEAP_ITEM0 - 1) / TF_HEAP_D + TF_HEAP_ITEM0;
}

static inline int tf_heap_first_child(int index)
{
	return TF_HEAP_D * (index - TF_HEAP_ITEM0) + TF_HEAP_ITEM0 + 1;
}

#if 0
static void tf_heap_verify(struct tf_heap_head *head)
{
	int i, count = 0;

	for (i = TF_HEAP_ITEM0; i < head->num_items + TF_HEAP_ITEM0; i++) {
		if (head->item[i].ptr->index != i) {
			printf("Heap item %d is corrupt ptr->index=%d\n", i, head->item[i].ptr->index);
			count++;
		}
	}
	TF_BUG_ON(count);
}
#endif

static inline
void tf_heap_downheap(struct tf_heap_child *heap, int last_index, int index)
{
	struct tf_heap_child he = heap[index];
	struct tf_heap_child *minpos, *pos;
	int c, i, mi;

	while (1) {
		c = tf_heap_first_child(index);
		pos = &heap[c];

		/* find minimum child */
		minpos = pos;
		mi = 0;
		if (likely(c + TF_HEAP_D - 1 < last_index)) {
			for (i = 1, pos++; i < TF_HEAP_D; i++, pos++)
				if (compare_values(pos->val, minpos->val) < 0)
					minpos = pos, mi = i;
		} else if (c < last_index) {
			for (i = 1, pos++; c + i < last_index; i++, pos++)
				if (compare_values(pos->val, minpos->val) < 0)
					minpos = pos, mi = i;
	        } else
			break;

		if (compare_values(he.val, minpos->val) <= 0)
			break;

		heap[index] = *minpos;
		minpos->ptr->index = index;
		index = c + mi;
	}

	heap[index] = he;
	he.ptr->index = index;
}

static inline
void tf_heap_upheap(struct tf_heap_child *heap, int index)
{
	struct tf_heap_child he = heap[index];
	int p = tf_heap_parent(index);

	while (likely(index > TF_HEAP_ITEM0) &&
	       compare_values(heap[p].val, he.val) > 0) {
		heap[index] = heap[p];
		heap[index].ptr->index = index;
		index = p;
		p = tf_heap_parent(p);
	}

	heap[index] = he;
	he.ptr->index = index;
}

static inline
void tf_heap_heapify(struct tf_heap_head *head, int index)
{
	struct tf_heap_child *heap = head->item;

	if (likely(index > TF_HEAP_ITEM0) &&
	    compare_values(heap[index].val, heap[tf_heap_parent(index)].val) <= 0)
		tf_heap_upheap(heap, index);
	else
		tf_heap_downheap(heap, TF_HEAP_ITEM0 + head->num_items, index);
}

int __tf_heap_grow(struct tf_heap_head *head)
{
	void *item;

	if (head->allocated) {
		item = tf_bmem_resize(head->item,
				head->allocated * sizeof(struct tf_heap_child),
				2 * head->allocated * sizeof(struct tf_heap_child));
		head->allocated *= 2;
	} else {
		head->allocated = 4096 / sizeof(struct tf_heap_child);
		item = tf_bmem_alloc(head->allocated * sizeof(struct tf_heap_child));
	}

	if (item == NULL)
		return -ENOMEM;

	head->item = item;
	return 0;
}

void tf_heap_insert(struct tf_heap_node *node, struct tf_heap_head *head,
		    tf_heap_priority val)
{
	int i;

	tf_heap_prealloc(head, head->num_items + 1);

	i = node->index = TF_HEAP_ITEM0 + head->num_items;
	head->num_items++;
	head->item[i].ptr = node;
	head->item[i].val = val;
	tf_heap_upheap(head->item, i);
}

void tf_heap_delete(struct tf_heap_node *node, struct tf_heap_head *head)
{
	int index = node->index;

	if (index == 0)
		return;

	head->num_items--;
	if (likely(index < head->num_items + TF_HEAP_ITEM0)) {
		head->item[index] = head->item[head->num_items+TF_HEAP_ITEM0];
		tf_heap_heapify(head, index);
	}
	node->index = 0;
}

void tf_heap_change(struct tf_heap_node *node, struct tf_heap_head *head,
		    tf_heap_priority val)
{
	if (likely(node->index != 0)) {
		head->item[node->index].val = val;
		tf_heap_heapify(head, node->index);
	} else {
		tf_heap_insert(node, head, val);
	}
}