/*
 * This file is part of the UCB release of Plan 9. It is subject to the license
 * terms in the LICENSE file found in the top-level directory of this
 * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
 * part of the UCB release of Plan 9, including this file, may be copied,
 * modified, propagated, or distributed except according to the terms contained
 * in the LICENSE file.
 */

#include "u.h"
#include "../port/lib.h"
#include "mem.h"
#include "dat.h"
#include "fns.h"

typedef struct Map Map;
struct Map {
        uint32_t   size;
        uint32_t   addr;
};

typedef struct RMap RMap;
struct RMap {
        char*   name;
        Map*    map;
        Map*    mapend;

        Lock Lock;
};

void
rmapfree(RMap* rmap, uintptr_t addr, uint size)
{
	Map *mp;
	uint t;

	if(size == 0)
		return;

	lock(&rmap->Lock);
	for(mp = rmap->map; mp->addr <= addr && mp->size; mp++)
		;

	if(mp > rmap->map && (mp-1)->addr+(mp-1)->size == addr){
		(mp-1)->size += size;
		if(addr+size == mp->addr){
			(mp-1)->size += mp->size;
			while(mp->size){
				mp++;
				(mp-1)->addr = mp->addr;
				(mp-1)->size = mp->size;
			}
		}
	}else{
		if(addr+size == mp->addr && mp->size){
			mp->addr -= size;
			mp->size += size;
		}else{
			do{
				if(mp >= rmap->mapend){
					print("mapfree: %s: losing 0x%lX, %u\n", rmap->name, addr, size);
					break;
				}
				t = mp->addr;
				mp->addr = addr;
				addr = t;
				t = mp->size;
				mp->size = size;
				mp++;
			}while((size = t) != 0);
		}
	}
	unlock(&rmap->Lock);
}

uintptr_t
rmapalloc(RMap* rmap, uintptr_t addr, uint size, int align)
{
	Map *mp;
	uint32_t maddr, oaddr;

	lock(&rmap->Lock);
	for(mp = rmap->map; mp->size; mp++){
		maddr = mp->addr;

		if(addr){
			/*
			 * A specific address range has been given:
			 *   if the current map entry is greater then
			 *   the address is not in the map;
			 *   if the current map entry does not overlap
			 *   the beginning of the requested range then
			 *   continue on to the next map entry;
			 *   if the current map entry does not entirely
			 *   contain the requested range then the range
			 *   is not in the map.
			 */
			if(maddr > addr)
				break;
			if(mp->size < addr - maddr)	/* maddr+mp->size < addr, but no overflow */
				continue;
			if(addr - maddr > mp->size - size)	/* addr+size > maddr+mp->size, but no overflow */
				break;
			maddr = addr;
		}

		if(align > 0)
			maddr = ((maddr+align-1)/align)*align;
		if(mp->addr+mp->size-maddr < size)
			continue;

		oaddr = mp->addr;
		mp->addr = maddr+size;
		mp->size -= maddr-oaddr+size;
		if(mp->size == 0){
			do{
				mp++;
				(mp-1)->addr = mp->addr;
			}while((mp-1)->size = mp->size);
		}

		unlock(&rmap->Lock);
		if(oaddr != maddr)
			rmapfree(rmap, oaddr, maddr-oaddr);

		return maddr;
	}
	unlock(&rmap->Lock);

	return 0;
}