/*
 * Copyright (c) 2010-2013 Yuichi Watanabe
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 * 3. Neither the name of Yuichi Watanabe nor the names of its
 *    contributors may be used to endorse or promote products derived from
 *    this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#include <common/list.h>
#include <common/common.h>
#include <core/rm.h>
#include <core/printf.h>
#include <core/string.h>
#include <core/vmmerr.h>

void
rm_init_resource(struct resource *resource, phys_t start, phys_t end,
		 u32 type, u32 data, char *name)
{
	LIST2_HEAD_INIT(resource->children);
	resource->start = start;
	resource->end = end;
	resource->type = type;
	resource->data = data;
	resource->name = name;
}

struct resource *
rm_find_resource(struct resource *parent, phys_t address)
{
	struct resource *cur;

	if (parent == NULL) {
		return NULL;
	}
	LIST2_FOREACH(parent->children, sibling, cur) {
		if (address >= cur->start && address <= cur->end) {
			return cur;
		}
	}
	return NULL;
}

vmmerr_t
rm_insert_resource(struct resource *parent, struct resource *new)
{
	struct resource *next, *prev;

	if (parent == NULL) {
		return VMMERR_INVAL;
	}
	if (new->start > new->end) {
		return VMMERR_INVAL;
	}
	if (new->start < parent->start ||
	    new->end > parent->end) {
		return VMMERR_RANGE;
	}
	LIST2_FOREACH(parent->children, sibling, next) {
		if (new->start < next->start) {
			break;
		}
	}
	if (next && new->end >= next->start) {
		return VMMERR_BUSY;
	}
	prev = LIST2_PREV(parent->children, sibling, next);
	if (prev && new->start <= prev->end) {
		return VMMERR_BUSY;
	}
	if (next) {
		LIST2_INSERT(parent->children, sibling, next, new);
	} else {
		LIST2_ADD(parent->children, sibling, new);
	}
	new->parent = parent;
	return VMMERR_SUCCESS;
}

/*
 * case1: (not-found)
 * avail_start avail_end start        end
 *                       avail_start'
 *
 * case2: (found)
 * avail_start start        avail_end end
 *              avail_start'
 *
 * case3: (found)
 * avail_start start        end        avail_end
 *             avail_start' avail_end'
 *
 * case4: (found)
 * start avail_start end        avail_end
 *                   avail_end'
 *
 * case5 (found)
 * start avail_start avail_end end
 *
 * case6 (not-found)
 * start end        avail_start avail_end
 *       avail_end'
 *
 */
vmmerr_t
rm_alloc_avail_resource(struct resource *parent, struct resource *new,
			phys_t start, phys_t end, phys_t align,
			u32 type, u32 data, char *name)
{
	struct resource *next, *prev;
	phys_t avail_start;
	phys_t avail_end;

	if (parent == NULL) {
		return VMMERR_INVAL;
	}
	if (start > end) {
		return VMMERR_INVAL;
	}
	if (end < parent->start || start > parent->end) {
		return VMMERR_RANGE;
	}
	LIST2_FOREACH(parent->children, sibling, next) {
		prev = LIST2_PREV(parent->children, sibling, next);
		avail_start = prev ? prev->end + 1 : parent->start;
		if (next->start == 0) {
			continue;
		}
		avail_end = next->start - 1;
		if (avail_start < start) {
			avail_start = start;
		}
		if (avail_end > end) {
			avail_end = end;
		}
		avail_start = ROUND_UP(avail_start, align);
		avail_end = ROUND_DOWN(avail_end + 1, align) - 1;
		if (avail_start <= avail_end &&
		    avail_end < next->start) {
			goto found;
		}
	}
	prev = LIST2_PREV(parent->children, sibling, (struct resource *)NULL);
	avail_start = prev ? prev->end + 1 : parent->start;
	avail_end = parent->end;
	if (avail_start < start) {
		avail_start = start;
	}
	if (avail_end > end) {
		avail_end = end;
	}
	avail_start = ROUND_UP(avail_start, align);
	avail_end = ROUND_DOWN(avail_end + 1, align) - 1;
	if (avail_start > avail_end &&
	    avail_end <= parent->end) {
		return VMMERR_BUSY;
	}
 found:
	rm_init_resource(new, avail_start, avail_end,
			 type, data, name);
	if (next) {
		LIST2_INSERT(parent->children, sibling, next, new);
	} else {
		LIST2_ADD(parent->children, sibling, new);
	}
	new->parent = parent;
	return VMMERR_SUCCESS;
}

vmmerr_t
rm_alloc_resource(struct resource *parent, struct resource *new, size_t size,
		  phys_t align, u32 type, u32 data, char *name)
{
	struct resource *next, *prev;
	phys_t avail_start;
	phys_t avail_end;

	if (parent == NULL) {
		return VMMERR_INVAL;
	}
	if (size <= 0) {
		return VMMERR_INVAL;
	}
	if (size > (parent->end - parent->start + 1)) {
		return VMMERR_RANGE;
	}
	LIST2_FOREACH(parent->children, sibling, next) {
		prev = LIST2_PREV(parent->children, sibling, next);
		avail_start = prev ? prev->end + 1 : parent->start;
		avail_start = ROUND_UP(avail_start, align);
		avail_end = ROUND_DOWN(next->start, align) - 1;
		if (avail_start <= avail_end &&
		    avail_start + size - 1 <= avail_end &&
		    avail_end < next->start) {
			goto found;
		}
	}
	prev = LIST2_PREV(parent->children, sibling, (struct resource *)NULL);
	avail_start = prev ? prev->end + 1 : parent->start;
	avail_start = ROUND_UP(avail_start, align);
	avail_end = ROUND_DOWN(parent->end + 1, align) - 1;
	if (avail_start <= avail_end &&
	    avail_start + size -1 <= avail_end &&
	    avail_end <= parent->end) {
		goto found;
	}
	return VMMERR_BUSY;
 found:
	rm_init_resource(new, avail_start, avail_start + size - 1,
			 type, data, name);
	if (next) {
		LIST2_INSERT(parent->children, sibling, next, new);
	} else {
		LIST2_ADD(parent->children, sibling, new);
	}
	new->parent = parent;
	return VMMERR_SUCCESS;
}

static void
dump_resources(struct resource *resource, int level)
{
	struct resource *child;
	char buf[17] = {0};

	memset(buf, ' ', level <= 8 ? level * 2 : 16);
	printf("%s%016llx-%016llx type %x data %x %s\n", buf,
	       resource->start, resource->end, resource->type,
	       resource->data, resource->name);
	if (LIST2_NEXT(resource->children, sibling, (struct resource *)NULL)
	    == NULL) {
		return;
	}
	LIST2_FOREACH(resource->children, sibling, child) {
		dump_resources(child, level + 1);
	}
}

void
rm_dump_resources(struct resource *resource)
{
	dump_resources(resource, 0);
}
