/*
Copyright (C) 1996-1997 Id Software, Inc.

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program 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 General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

*/

///////////////////////////////////////////////////////////////////////////
/// @file	Z_zone.c
/// @brief	Zone functions 'n stuff.
/// 
/// @defgroup zone_functions Zone Functions
/// @defgroup zone_structures Zone Structures
/// 
/// @defgroup hunk_functions Hunk Functions
/// @defgroup hunk_structures Hunk Structures
/// 
/// @defgroup cache_functions Cache Functions
/// @defgroup cache_structures Cache Structures
/// 
/// @defgroup memory_functions Memory Functions
///////////////////////////////////////////////////////////////////////////
#include "quakedef.h"

#define	DYNAMIC_SIZE	0xc000

#define	ZONEID	0x1d4a11
#define MINFRAGMENT	64

///////////////////////////////////////////////////////////////////////////
/// @ingroup zone_structures
/// @brief	Memory Block.
///////////////////////////////////////////////////////////////////////////
typedef struct memblock_s
{
	int		size;           // including the header and possibly tiny fragments
	int     tag;            // a tag of 0 is a free block
	int     id;        		// should be ZONEID
	struct memblock_s       *next, *prev;
	int		pad;			// pad to 64 bit boundary
} memblock_t;


///////////////////////////////////////////////////////////////////////////
/// @ingroup zone_structures
/// @brief	Memory Zone.
///////////////////////////////////////////////////////////////////////////
typedef struct
{
	int		size;			///< total bytes malloced, including header
	memblock_t	blocklist;	///< start / end cap for linked list
	memblock_t	*rover;
} memzone_t;

void Cache_FreeLow (int new_low_hunk);
void Cache_FreeHigh (int new_high_hunk);

/*
==============================================================================

						ZONE MEMORY ALLOCATION

There is never any space between memblocks, and there will never be two
contiguous free memblocks.

The rover can be left pointing at a non-empty block

The zone calls are pretty much only used for small strings and structures,
all big things are allocated on the hunk.
==============================================================================
*/

memzone_t	*mainzone;

void Z_ClearZone (memzone_t *zone, int size);


///////////////////////////////////////////////////////////////////////////
/// @ingroup zone_functions
/// @brief	
/// @param	zone
/// @param	size
///////////////////////////////////////////////////////////////////////////
void Z_ClearZone (memzone_t *zone, int size)
{
	memblock_t	*block;
	
// set the entire zone to one free block

	zone->blocklist.next = zone->blocklist.prev = block =
							   (memblock_t *) ( (byte *) zone + sizeof (memzone_t));
	zone->blocklist.tag = 1;	// in use block
	zone->blocklist.id = 0;
	zone->blocklist.size = 0;
	zone->rover = block;
	
	block->prev = block->next = &zone->blocklist;
	block->tag = 0;			// free block
	block->id = ZONEID;
	block->size = size - sizeof (memzone_t);
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup zone_functions
/// @brief	
/// @param	ptr
///////////////////////////////////////////////////////////////////////////
void Z_Free (void *ptr)
{
	memblock_t	*block, *other;
	
	if (!ptr)
		Sys_Error ("Z_Free: NULL pointer");
		
	block = (memblock_t *) ( (byte *) ptr - sizeof (memblock_t));
	if (block->id != ZONEID)
		Sys_Error ("Z_Free: freed a pointer without ZONEID");
	if (block->tag == 0)
		Sys_Error ("Z_Free: freed a freed pointer");
		
	block->tag = 0;		// mark as free
	
	other = block->prev;
	if (!other->tag)
	{
		// merge with previous free block
		other->size += block->size;
		other->next = block->next;
		other->next->prev = other;
		if (block == mainzone->rover)
			mainzone->rover = other;
		block = other;
	}
	
	other = block->next;
	if (!other->tag)
	{
		// merge the next free block onto the end
		block->size += other->size;
		block->next = other->next;
		block->next->prev = block;
		if (other == mainzone->rover)
			mainzone->rover = block;
	}
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup zone_functions
/// @brief	Allocate memory
/// @param	size The size of the memory block to allocate.
/// @return	void
///////////////////////////////////////////////////////////////////////////
void *Z_Malloc (int size)
{
	void	*buf;
	
	Z_CheckHeap ();	// DEBUG
	buf = Z_TagMalloc (size, 1);
	if (!buf)
	{
		Sys_Error ("Z_Malloc: failed on allocation of %i bytes", size);
	}

	Q_memset (buf, 0, size);
	
	return buf;
}

void *Z_TagMalloc (int size, int tag)
{
	int		extra;
	memblock_t	*start, *rover, *_new, *base;
	
	if (!tag)
		Sys_Error ("Z_TagMalloc: tried to use a 0 tag");
		
//
// scan through the block list looking for the first free block
// of sufficient size
//
	size += sizeof (memblock_t);	// account for size of block header
	size += 4;					// space for memory trash tester
	size = (size + 7) & ~7;		// align to 8-byte boundary
	
	base = rover = mainzone->rover;
	start = base->prev;
	
	do
	{
		if (rover == start)	// scaned all the way around the list
			return NULL;
		if (rover->tag)
			base = rover = rover->next;
		else
			rover = rover->next;
	}
	while (base->tag || base->size < size);
	
//
// found a block big enough
//
	extra = base->size - size;
	if (extra >  MINFRAGMENT)
	{
		// there will be a free fragment after the allocated block
		_new = (memblock_t *) ( (byte *) base + size);
		_new->size = extra;
		_new->tag = 0;			// free block
		_new->prev = base;
		_new->id = ZONEID;
		_new->next = base->next;
		_new->next->prev = _new;
		base->next = _new;
		base->size = size;
	}
	
	base->tag = tag;				// no longer a free block
	
	mainzone->rover = base->next;	// next allocation will start looking here
	
	base->id = ZONEID;
	
// marker for memory trash testing
	* (int *) ( (byte *) base + base->size - 4) = ZONEID;
	
	return (void *) ( (byte *) base + sizeof (memblock_t));
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup zone_functions
/// @brief	
/// @param	zone
///////////////////////////////////////////////////////////////////////////
void Z_Print (memzone_t *zone)
{
	memblock_t	*block;
	
	Con_Printf ("zone size: %i  location: %p\n", mainzone->size, mainzone);
	
	for (block = zone->blocklist.next ; ; block = block->next)
	{
		Con_Printf ("block:%p    size:%7i    tag:%3i\n",
					block, block->size, block->tag);
					
		if (block->next == &zone->blocklist)
			break;			// all blocks have been hit
		if ( (byte *) block + block->size != (byte *) block->next)
			Con_Printf ("ERROR: block size does not touch the next block\n");
		if (block->next->prev != block)
			Con_Printf ("ERROR: next block doesn't have proper back link\n");
		if (!block->tag && !block->next->tag)
			Con_Printf ("ERROR: two consecutive free blocks\n");
	}
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup zone_functions
/// @brief
///////////////////////////////////////////////////////////////////////////
void Z_CheckHeap (void)
{
	memblock_t	*block;
	
	for (block = mainzone->blocklist.next ; ; block = block->next)
	{
		if (block->next == &mainzone->blocklist)
			break;			// all blocks have been hit
		if ( (byte *) block + block->size != (byte *) block->next)
			Sys_Error ("Z_CheckHeap: block size does not touch the next block\n");
		if (block->next->prev != block)
			Sys_Error ("Z_CheckHeap: next block doesn't have proper back link\n");
		if (!block->tag && !block->next->tag)
			Sys_Error ("Z_CheckHeap: two consecutive free blocks\n");
	}
}


#define	HUNK_SENTINAL	0x1df001ed

///////////////////////////////////////////////////////////////////////////
/// @ingroup hunk_structures
/// @brief A hunk of memory (?)
///////////////////////////////////////////////////////////////////////////
typedef struct
{
	int		sentinal;	///< unknown
	int		size;		///< including sizeof(hunk_t), -1 = not allocated
	char	name[8];	///< name of the memory hunk
} hunk_t;

byte	*hunk_base;
int		hunk_size;

int		hunk_low_used;
int		hunk_high_used;

bool	hunk_tempactive;
int		hunk_tempmark;

void R_FreeTextures (void);

///////////////////////////////////////////////////////////////////////////
/// @ingroup hunk_functions
/// @brief	Run consistency and sentinal trahing checks.
///////////////////////////////////////////////////////////////////////////
void Hunk_Check (void)
{
	hunk_t	*h;
	
	for (h = (hunk_t *) hunk_base ; (byte *) h != hunk_base + hunk_low_used ;)
	{
		if (h->sentinal != HUNK_SENTINAL)
			Sys_Error ("Hunk_Check: trahsed sentinal");
		if (h->size < 16 || h->size + (byte *) h - hunk_base > hunk_size)
			Sys_Error ("Hunk_Check: bad size");
		h = (hunk_t *) ( (byte *) h + h->size);
	}
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup hunk_functions
/// @brief	If "all" is specified, every single allocation is printed.
///			Otherwise, allocations with the same name will be totaled up
///			before printing.
///	@param	all
///////////////////////////////////////////////////////////////////////////
void Hunk_Print (bool all)
{
	hunk_t	*h, *next, *endlow, *starthigh, *endhigh;
	int		count, sum;
	int		totalblocks;
	char	name[9];
	
	name[8] = 0;
	count = 0;
	sum = 0;
	totalblocks = 0;
	
	h = (hunk_t *) hunk_base;
	endlow = (hunk_t *) (hunk_base + hunk_low_used);
	starthigh = (hunk_t *) (hunk_base + hunk_size - hunk_high_used);
	endhigh = (hunk_t *) (hunk_base + hunk_size);
	
	Con_Printf ("          :%8i total hunk size\n", hunk_size);
	Con_Printf ("-------------------------\n");
	
	while (1)
	{
		//
		// skip to the high hunk if done with low hunk
		//
		if (h == endlow)
		{
			Con_Printf ("-------------------------\n");
			Con_Printf ("          :%8i REMAINING\n", hunk_size - hunk_low_used - hunk_high_used);
			Con_Printf ("-------------------------\n");
			h = starthigh;
		}
		
		//
		// if totally done, break
		//
		if (h == endhigh)
			break;
			
		//
		// run consistancy checks
		//
		if (h->sentinal != HUNK_SENTINAL)
			Sys_Error ("Hunk_Check: trahsed sentinal");
		if (h->size < 16 || h->size + (byte *) h - hunk_base > hunk_size)
			Sys_Error ("Hunk_Check: bad size");
			
		next = (hunk_t *) ( (byte *) h + h->size);
		count++;
		totalblocks++;
		sum += h->size;
		
		//
		// print the single block
		//
		memcpy (name, h->name, 8);
		if (all)
			Con_Printf ("%8p :%8i %8s\n", h, h->size, name);
			
		//
		// print the total
		//
		if (next == endlow || next == endhigh ||
				strncmp (h->name, next->name, 8))
		{
			if (!all)
				Con_Printf ("          :%8i %8s (TOTAL)\n", sum, name);
			count = 0;
			sum = 0;
		}
		
		h = next;
	}
	
	Con_Printf ("-------------------------\n");
	Con_Printf ("%8i total blocks\n", totalblocks);
	
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup hunk_functions
/// @brief	Allocate a contigues block of memory (known as a hunk)
/// @param	size 
/// @param	name 
///////////////////////////////////////////////////////////////////////////
void *Hunk_AllocName (int size, char *name)
{
	hunk_t *h;
	
#ifdef PARANOID
	Hunk_Check ();
#endif
	
	if (size < 0)
		Sys_Error ("Hunk_Alloc: bad size: %i", size);
		
	size = sizeof (hunk_t) + ( (size + 15) &~15);
	
	if (hunk_size - hunk_low_used - hunk_high_used < size)
		Sys_Error ("Hunk_Alloc: failed on %i bytes", size);
		
	h = (hunk_t *) (hunk_base + hunk_low_used);
	hunk_low_used += size;
	
	Cache_FreeLow (hunk_low_used);
	
	memset (h, 0, size);
	
	h->size = size;
	h->sentinal = HUNK_SENTINAL;
	Q_strncpy (h->name, name, 8);
	
	return (void *) (h + 1);
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup hunk_functions
/// @brief	
/// @param	size	
///////////////////////////////////////////////////////////////////////////
void *Hunk_Alloc (int size)
{
	return Hunk_AllocName (size, "unknown");
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup hunk_functions
/// @brief	
/// @return	@b hunk_low_used
///////////////////////////////////////////////////////////////////////////
int	Hunk_LowMark (void)
{
	return hunk_low_used;
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup hunk_functions
/// @brief	
/// @param	mark
///////////////////////////////////////////////////////////////////////////
void Hunk_FreeToLowMark (int mark)
{
	if (mark < 0 || mark > hunk_low_used)
		Sys_Error ("Hunk_FreeToLowMark: bad mark %i", mark);
	memset (hunk_base + mark, 0, hunk_low_used - mark);
	hunk_low_used = mark;
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup hunk_functions
/// @brief	
///////////////////////////////////////////////////////////////////////////
int	Hunk_HighMark (void)
{
	if (hunk_tempactive)
	{
		hunk_tempactive = false;
		Hunk_FreeToHighMark (hunk_tempmark);
	}
	
	return hunk_high_used;
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup hunk_functions
/// @brief	
/// @param	mark
///////////////////////////////////////////////////////////////////////////
void Hunk_FreeToHighMark (int mark)
{
	if (hunk_tempactive)
	{
		hunk_tempactive = false;
		Hunk_FreeToHighMark (hunk_tempmark);
	}
	if (mark < 0 || mark > hunk_high_used)
		Sys_Error ("Hunk_FreeToHighMark: bad mark %i", mark);
	memset (hunk_base + hunk_size - hunk_high_used, 0, hunk_high_used - mark);
	hunk_high_used = mark;
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup hunk_functions
/// @brief	
/// @param	size
/// @param	name
/// @return	
///////////////////////////////////////////////////////////////////////////
void *Hunk_HighAllocName (int size, char *name)
{
	hunk_t	*h;
	
	if (size < 0)
		Sys_Error ("Hunk_HighAllocName: bad size: %i", size);
		
	if (hunk_tempactive)
	{
		Hunk_FreeToHighMark (hunk_tempmark);
		hunk_tempactive = false;
	}
	
#ifdef PARANOID
	Hunk_Check ();
#endif
	
	size = sizeof (hunk_t) + ( (size + 15) &~15);
	
	if (hunk_size - hunk_low_used - hunk_high_used < size)
	{
		Con_Printf ("Hunk_HighAlloc: failed on %i bytes\n", size);
		return NULL;
	}
	
	hunk_high_used += size;
	Cache_FreeHigh (hunk_high_used);
	
	h = (hunk_t *) (hunk_base + hunk_size - hunk_high_used);
	
	memset (h, 0, size);
	h->size = size;
	h->sentinal = HUNK_SENTINAL;
	Q_strncpy (h->name, name, 8);
	
	return (void *) (h + 1);
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup hunk_functions
/// @brief	Return space from the top of the hunk
/// @param	size
/// @return	
///////////////////////////////////////////////////////////////////////////
void *Hunk_TempAlloc (int size)
{
	void	*buf;
	
	size = (size + 15) &~15;
	
	if (hunk_tempactive)
	{
		Hunk_FreeToHighMark (hunk_tempmark);
		hunk_tempactive = false;
	}
	
	hunk_tempmark = Hunk_HighMark ();
	
	buf = Hunk_HighAllocName (size, "temp");
	
	hunk_tempactive = true;
	
	return buf;
}

/*
===============================================================================

CACHE MEMORY

===============================================================================
*/

///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_structures
/// @brief	
///////////////////////////////////////////////////////////////////////////
typedef struct cache_system_s
{
	int						size;					///< including this header
	cache_user_t			*user;
	char					name[16];
	struct cache_system_s	*prev, *next;
	struct cache_system_s	*lru_prev, *lru_next;	///< Least Recently Used. for LRU flushing
} cache_system_t;

cache_system_t *Cache_TryAlloc (int size, bool nobottom);

cache_system_t	cache_head;

///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
/// @brief	
/// @param	c	
///////////////////////////////////////////////////////////////////////////
void Cache_Move (cache_system_t *c)
{
	cache_system_t		*_new;
	
	// we are clearing up space at the bottom, so only allocate it late
	_new = Cache_TryAlloc (c->size, true);
	if (_new)
	{
//		Con_Printf ("cache_move ok\n");

		Q_memcpy (_new + 1, c + 1, c->size - sizeof (cache_system_t));
		_new->user = c->user;
		Q_memcpy (_new->name, c->name, sizeof (_new->name));
		Cache_Free (c->user);
		_new->user->data = (void *) (_new + 1);
	}
	else
	{
//		Con_Printf ("cache_move failed\n");

		Cache_Free (c->user);		// tough luck...
	}
}

///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
/// @brief	Throw things out until the hunk can be expanded to the given point.
/// @param	new_low_hunk 
///////////////////////////////////////////////////////////////////////////
void Cache_FreeLow (int new_low_hunk)
{
	cache_system_t *c;
	
	while (1)
	{
		c = cache_head.next;
		if (c == &cache_head)
			return;		// nothing in cache at all
		if ( (byte *) c >= hunk_base + new_low_hunk)
			return;		// there is space to grow the hunk
		Cache_Move (c);	// reclaim the space
	}
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
/// @brief	Throw things out until the hunk can be expanded to the given point
/// @param	new_high_hunk
///////////////////////////////////////////////////////////////////////////
void Cache_FreeHigh (int new_high_hunk)
{
	cache_system_t	*c, *prev;
	
	prev = NULL;
	while (1)
	{
		c = cache_head.prev;
		if (c == &cache_head)
			return;		// nothing in cache at all
		if ( (byte *) c + c->size <= hunk_base + hunk_size - new_high_hunk)
			return;		// there is space to grow the hunk
		if (c == prev)
			Cache_Free (c->user);	// didn't move out of the way
		else
		{
			Cache_Move (c);	// try to move it
			prev = c;
		}
	}
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
/// @brief	
/// @param	cs	
///////////////////////////////////////////////////////////////////////////
void Cache_UnlinkLRU (cache_system_t *cs)
{
	if (!cs->lru_next || !cs->lru_prev)
		Sys_Error ("Cache_UnlinkLRU: NULL link");
		
	cs->lru_next->lru_prev = cs->lru_prev;
	cs->lru_prev->lru_next = cs->lru_next;
	
	cs->lru_prev = cs->lru_next = NULL;
}

///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
/// @brief	
/// @param	cs	
///////////////////////////////////////////////////////////////////////////
void Cache_MakeLRU (cache_system_t *cs)
{
	if (cs->lru_next || cs->lru_prev)
		Sys_Error ("Cache_MakeLRU: active link");
		
	cache_head.lru_next->lru_prev = cs;
	cs->lru_next = cache_head.lru_next;
	cs->lru_prev = &cache_head;
	cache_head.lru_next = cs;
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
/// @brief	Looks for a free block of memory between the high and low hunk marks
///			Size should already include the header and padding
///	@param	size		
///	@param	nobottom	
///	@return	
///////////////////////////////////////////////////////////////////////////
cache_system_t *Cache_TryAlloc (int size, bool nobottom)
{
	cache_system_t	*cs, *_new;
	
// is the cache completely empty?

	if (!nobottom && cache_head.prev == &cache_head)
	{
		if (hunk_size - hunk_high_used - hunk_low_used < size)
			Sys_Error ("Cache_TryAlloc: %i is greater then free hunk", size);
			
		_new = (cache_system_t *) (hunk_base + hunk_low_used);
		memset (_new, 0, sizeof (*_new));
		_new->size = size;
		
		cache_head.prev = cache_head.next = _new;
		_new->prev = _new->next = &cache_head;
		
		Cache_MakeLRU (_new);
		return _new;
	}
	
// search from the bottom up for space

	_new = (cache_system_t *) (hunk_base + hunk_low_used);
	cs = cache_head.next;
	
	do
	{
		if (!nobottom || cs != cache_head.next)
		{
			if ( (byte *) cs - (byte *) _new >= size)
			{
				// found space
				memset (_new, 0, sizeof (*_new));
				_new->size = size;
				
				_new->next = cs;
				_new->prev = cs->prev;
				cs->prev->next = _new;
				cs->prev = _new;
				
				Cache_MakeLRU (_new);
				
				return _new;
			}
		}
		
		// continue looking
		_new = (cache_system_t *) ( (byte *) cs + cs->size);
		cs = cs->next;
		
	}
	while (cs != &cache_head);
	
// try to allocate one at the very end
	if (hunk_base + hunk_size - hunk_high_used - (byte *) _new >= size)
	{
		memset (_new, 0, sizeof (*_new));
		_new->size = size;
		
		_new->next = &cache_head;
		_new->prev = cache_head.prev;
		cache_head.prev->next = _new;
		cache_head.prev = _new;
		
		Cache_MakeLRU (_new);
		
		return _new;
	}
	
	return NULL;		// couldn't allocate
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
/// @brief	Throw everything out, so new data will be demand cached
///////////////////////////////////////////////////////////////////////////
void Cache_Flush (void)
{
	while (cache_head.next != &cache_head)
		Cache_Free (cache_head.next->user);	// reclaim the space
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
///////////////////////////////////////////////////////////////////////////
void Cache_Print (void)
{
	cache_system_t	*cd;
	
	for (cd = cache_head.next ; cd != &cache_head ; cd = cd->next)
	{
		Con_Printf ("%8i : %s\n", cd->size, cd->name);
	}
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
///////////////////////////////////////////////////////////////////////////
void Cache_Report (void)
{
	Con_DPrintf ("%4.1f megabyte data cache\n", (hunk_size - hunk_high_used - hunk_low_used) / (float) (1024 * 1024));
}

///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
///////////////////////////////////////////////////////////////////////////
void Cache_Compact (void)
{
}

///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
/// @brief	... and adds the @e flush command to the @b console
/// @todo	I have NO clue what this does.
///////////////////////////////////////////////////////////////////////////
void Cache_Init (void)
{
	/// Make cache_head point to itself
	cache_head.next = cache_head.prev = &cache_head;
	cache_head.lru_next = cache_head.lru_prev = &cache_head;
	
	/// Add the @e flush command, to empty out the cache memory.
	Cmd_AddCommand ("flush", Cache_Flush);
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
/// @brief	Frees the memory and removes it from the LRU list
/// @param	c	
///////////////////////////////////////////////////////////////////////////
void Cache_Free (cache_user_t *c)
{
	cache_system_t	*cs;
	
	if (!c->data)
		Sys_Error ("Cache_Free: not allocated");
		
	cs = ( (cache_system_t *) c->data) - 1;
	
	cs->prev->next = cs->next;
	cs->next->prev = cs->prev;
	cs->next = cs->prev = NULL;
	
	c->data = NULL;
	
	Cache_UnlinkLRU (cs);
}


///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
/// @brief	Returns the cached data, and moves to the head of the LRU list
///			if present, otherwise returns NULL
///	@param	c	
///	@return	
///////////////////////////////////////////////////////////////////////////
void *Cache_Check (cache_user_t *c)
{
	cache_system_t	*cs;
	
	if (!c->data)
		return NULL;
		
	cs = ( (cache_system_t *) c->data) - 1;
	
// move to head of LRU
	Cache_UnlinkLRU (cs);
	Cache_MakeLRU (cs);
	
	return c->data;
}

///////////////////////////////////////////////////////////////////////////
/// @ingroup cache_functions
/// @brief	Purge all data from the memory cache.
/// @param	c		
/// @param	size	
/// @param	name	
/// @return	@b NULL, If all purgeable data was tossed and there still
///			wasn't enough room.
///////////////////////////////////////////////////////////////////////////
void *Cache_Alloc (cache_user_t *c, int size, char *name)
{
	cache_system_t	*cs;
	
	if (c->data)
		Sys_Error ("Cache_Alloc: already allocated");
		
	if (size <= 0)
		Sys_Error ("Cache_Alloc: size %i", size);
		
	size = (size + sizeof (cache_system_t) + 15) & ~15;
	
	// find memory for it
	while (1)
	{
		cs = Cache_TryAlloc (size, false);
		if (cs)
		{
			strncpy (cs->name, name, sizeof (cs->name) - 1);
			c->data = (void *) (cs + 1);
			cs->user = c;
			break;
		}
		
		// free the least recently used cahedat
		if (cache_head.lru_prev == &cache_head)
			Sys_Error ("Cache_Alloc: out of memory");
		// not enough memory at all
		Cache_Free (cache_head.lru_prev->user);
	}
	
	return Cache_Check (c);
}

//============================================================================


///////////////////////////////////////////////////////////////////////////
/// @ingroup memory_functions
/// @brief	
/// @param	buf		
/// @param	size	
///////////////////////////////////////////////////////////////////////////
void Memory_Init (void *buf, int size)
{
	int p;
	int zonesize = DYNAMIC_SIZE;
	
	hunk_base = (byte *) buf;
	hunk_size = size;
	hunk_low_used = 0;
	hunk_high_used = 0;
	
	Cache_Init ();
	p = COM_CheckParm ("-zone");
	if (p)
	{
		if (p < com_argc - 1)
			zonesize = Q_atoi (com_argv[p+1]) * 1024;
		else
			Sys_Error ("Memory_Init: you must specify a size in KB after -zone");
	}
	mainzone = (memzone_t *) Hunk_AllocName (zonesize, "zone");
	Z_ClearZone (mainzone, zonesize);
}

