#include <stdio.h>

#include "teeny.h"
#include "db.h"

/*
Copyright(C) 1990, Andrew Molitor, All Rights Reserved.
This software may be freely used, modified, and redistributed,
as long as this copyright message is left intact, and this
software is not used to develop any commercial product, or used
in any product that is provided on a pay-for-use basis.

No warranties whatsoever. This is not guaranteed to compile, nor,
in the event that it does compile to binaries, are these binaries
guaranteed to perform any function whatsoever.
*/


/*
	Cache management stuff. Also handles allocating chunks from the
chunkfile and so on. Note: This DOES NOT mess with the disk, only with internal
data structures. Basically the low level object management. Messes with
descriptors to indicate whether things are or are not in cache.

	This also has routines for managing descriptors efficiently.
malloc()ing them one at a time is death, 'cause we have absolutely
*fuckloads* of them around.

*/
/*
#define CACHEDEBUG
*/

/* 
The cache is stored as a chain, in order by most recently used. Use 
touch() to indicate a usage.
*/

struct obj_data *main_cache = NULL;
int cache_usage = 0;  /* Total cache usage at present */
long cache_size;

/*
If this is a 1, cache_trim() will NOT freeze things to disk. This
can be used to protect the chunkfile from writes for a bit, if you are copyinf
it around.
*/

int cache_locked = 0;

/*
The free chunks are stored as a list of descriptors, biggest chunk first.
This leads to a fast worst-fit algorithm. Forward points toward less recently
used objects.
*/

struct dsc *free_chunks = NULL;
long chunk_eof = 0L;  /* Contains the offset of the end of the chunkfile */


/*
	Initialize the cache to some size or other.
*/

initialize_cache(size)

long size;

{
	cache_size = size;
	cache_usage = 0;
}
/*
	Deletes an object from cache.
*/

cache_delete(obj)

struct obj_data *obj;

{
	if(obj == obj->back){ /* Only thing here.. */
		main_cache = NULL;
		return;
	}

	if(main_cache == obj){
		main_cache = obj->fwd;
	}

	/* Unlink this sucker */

	(obj->back)->fwd = obj->fwd;
	(obj->fwd)->back = obj->back;

	cache_usage -= DSC_SIZE(obj->descriptor);
#ifdef CACHEDEBUG
	printf("cache_delete ");
	cache_dump();
#endif
}

/*
	This moves an object to the head of the usage list, making it the most
recently used. Call this whenever you reference an object.

*/

touch(obj)

struct obj_data *obj;

{
	if(obj == main_cache){  /* Already at the top */
		return;
	} 

	/* Unlink it */

	(obj->back)->fwd = obj->fwd;
	(obj->fwd)->back = obj->back;

	/* Link it back in at the head. Remember, fwd is */
	/* the next most recently used object. */

	obj->fwd = main_cache;
	obj->back = main_cache->back;
	(main_cache->back)->fwd = obj;
	main_cache->back = obj;

	/* This is now the most recently used. */

	main_cache = obj;
#ifdef CACHEDEBUG
	printf("touch: ");
	cache_dump();
#endif
}

/*
	This stuffs the object into cache, and then trims the cache down.
All cache 'size' data goes by the size field on the descriptor, which is *on
disk* size, not actual in memory size. Too bad.

	This and cache_flush() are the only things that should *ever* freeze an
object to disk. Do it otherwise, and you better have a good reason.

	NOTE: The object better NOT be in cache when this is called.
*/

cache_insert(obj)
struct obj_data *obj;

{
	if(main_cache == NULL){ /* Empty cache */
		main_cache = obj->back = obj->fwd = obj;
		cache_usage = DSC_SIZE(obj->descriptor);
		return;
	}

	/* Stuff it in at the head -- it's the most recently used. */

	obj->fwd = main_cache;
	obj->back = main_cache->back;
	(main_cache->back)->fwd = obj;
	main_cache->back = obj;

	/* This is now the most recently used. */

	main_cache = obj;

	/* Now update cache usage, and trim the cache down to size */

	cache_usage += DSC_SIZE(obj->descriptor);
	cache_trim();
#ifdef CACHEDEBUG
	printf("cache_insert");
	cache_dump();
#endif
}

#ifdef CACHEDEBUG
cache_dump()
{
	struct obj_data *obj;

	obj = main_cache;
	if(obj == NULL){
		printf("cache is empty\n");
		return;
	}
	do {
		printf(" %s",DSC_NAME(obj->descriptor));
		obj = obj->fwd;
	} while(obj != main_cache);
	printf("\n");
}
#endif
/*
	Locks the cache so stuff is guaranteed to remain resident.
*/

lock_cache()
{
	cache_locked = 1;
}

/*
	Unlocks the cache so things can get flushed to disk.
*/

void unlock_cache()
{
	cache_locked = 0;
}
/*
	Trims the cache down to size, unless it's locked.
*/

cache_trim()
{
	struct obj_data *obj;
	struct dsc *thedsc;

	if(cache_locked)
		return;

	while(cache_usage > cache_size){

		/* Unlink the object back of the head */

		obj = main_cache->back;
		if(obj == main_cache){
			warning("cache_trim","cache WAY too small!");
			return;
		}
		(obj->back)->fwd = obj->fwd;
		(obj->fwd)->back = obj->back;

		thedsc = obj->descriptor;
		cache_usage -= DSC_SIZE(thedsc);

		/* Chill this object */

		disk_freeze(obj->descriptor);
	}

}

/*
	This flushes the entire cache to disk (for dump-like purposes).
*/

cache_flush()

{
	struct obj_data *obj,*next;

	if(main_cache == NULL){
		warning("cache_flush","trying to flush empty cache?");
		return;
	}

	obj = main_cache;
	do {
		/* Be careful here. disk_freeze() blows away the obj */

		next = obj->fwd;
		disk_freeze(obj->descriptor);
		obj = next;
	} while(obj != main_cache);

	main_cache = NULL;
	cache_usage = 0;
}

/*
	Places a descriptor on the free chunk list.
*/

free_chunk(dsc)
struct dsc *dsc;

{
	struct dsc *current,*last,*here;
	long start,end;

	if(free_chunks == NULL){
		(dsc->ptr).next = NULL;
		free_chunks = dsc;
		return;
	}

	current = free_chunks;
	last = here = NULL;

	/* Charge down the list, seeing if this amalgamates with any   */
	/* existing free blocks. Track where to insert it, in case not */

	start = DSC_CHUNK(dsc);
	end = start + DSC_SIZE(dsc);

	while(current != NULL){

		/* If no amalgamation, insert it here? If the first    */
		/* chunk is smaller, or if all the chunks are bigger   */
		/* here will be NULL. Be careful at the end, therefore */

		if(here == NULL && DSC_SIZE(current) < DSC_SIZE(dsc)){
			here = last;
		}

		/* Now see if it amalgamates. */

		if(start == (DSC_CHUNK(current) + DSC_SIZE(current))){
			DSC_SIZE(current) += DSC_SIZE(dsc);
			free_descriptor(dsc);
			del_free_chunk(current,last);
			free_chunk(current);
			return;

		} else if (end == DSC_CHUNK(current)){
			DSC_SIZE(dsc) += DSC_SIZE(current);
			del_free_chunk(current,last);
			free_descriptor(current);
			free_chunk(dsc);
			return;
		}
		last = current;
		current = (current->ptr).next;
	}

	/* Post mortem. Only get here we didn't amalgamate */

	if(here == NULL){
		/* Either it gos in at the head, or at the tail. */

		if(DSC_SIZE(last) > DSC_SIZE(dsc)){
			/* Tail */
			(dsc->ptr).next = NULL;
			(last->ptr).next = dsc;
		} else {
			/* Head */
			(dsc->ptr).next = free_chunks;
			free_chunks = dsc;
		}
	} else {
		/* Insert it immediately after here */

		(dsc->ptr).next = (here->ptr).next;
		(here->ptr).next = dsc;
	}
}

/*
	This allocates a chunk from the free list of chunks, if it can,
otherwise it just specifies the and of the chunkfile. It returns an offset to
write at, in either case. In particular it DOES NOT return a descriptor.

*/

long get_chunk(n)
int n;
{
	long ret;
	struct dsc *tmp;

	if(free_chunks == NULL){ /* No free chunks. */
#ifdef CACHEDEBUG
      		printf("No free chunks. Allocating from EOF\n");
#endif
		ret = chunk_eof;
		chunk_eof += n;
		return(ret);
	}

	/* See if the first (biggest) chunk is big enough. */

	tmp = free_chunks;
	if(DSC_SIZE(tmp) > n){

		/* Return the offset of the start */
#ifdef CACHEDEBUG
		printf("Biggest chunk was big enough. Pruning it.");
#endif
		ret = DSC_CHUNK(tmp);

		/* Adjust the size & offset, unlink it, and re-insert it
			in order */

		DSC_SIZE(tmp) -= n;
		DSC_CHUNK(tmp) += n;
		free_chunks = (tmp->ptr).next;
		free_chunk(tmp);
		return(ret);

	} else if(DSC_SIZE(tmp) == n){  /* Exact match! */
		/* Nuke this descriptor completely */
#ifdef CACHEDEBUG
		printf("Biggest chunk was exact match, allocating it\n");
#endif
		ret = DSC_CHUNK(tmp);
		free_chunks = (tmp->ptr).next;
		free_descriptor(tmp);
		return(ret);
	}

	/* If we can't find a big enough chunk, do this */
#ifdef CACHEDEBUG
	printf("No big enough chunks. Allocating from EOF.\n");
#endif
	ret = chunk_eof;
	chunk_eof += n;
	return(ret);
}

/*
	deletes a descriptor from the list of free chunk descriptors.
*/

del_free_chunk(dsc,last)

struct dsc *dsc;
struct dsc *last;

{
	if(free_chunks == dsc){
		free_chunks = (dsc->ptr).next;
		return;
	}

	/* Last had better only be NULL when dsc == free_chunks */

	(last->ptr).next = (dsc->ptr).next;
}

/*
	Descriptor management code.
*/

struct dsc *free_descriptors = NULL;

/*
	Allocate a bunch of descriptors, and shove them on the free descriptor
list.

*/

alloc_dsc(n)

int n;

{
	struct dsc *tmp1,*tmp2;

	tmp1 = tmp2 = (struct dsc *) ty_malloc(n * sizeof(struct dsc)
				,"alloc_dsc");

	/* String them together into a list */

	for(; n > 1;n--){
		(tmp2->ptr).next = &(tmp2[1]); /* Point at the next */
		tmp2++;
	}

	/* Link this mess in */

	(tmp2->ptr).next = free_descriptors;
	free_descriptors = tmp1;
}

/*
	Grab a descriptor

*/

struct dsc *get_descriptor()

{
	struct dsc *ret;

	if(free_descriptors == NULL){
		alloc_dsc(32);		/* Get a bunch more */
	}

	ret = free_descriptors;
	free_descriptors = (ret->ptr).next; /* Might be NULL. OK. */

	return(ret);
}

/*
	Give a descriptor back.
*/

free_descriptor(dsc)

struct dsc *dsc;

{
	(dsc->ptr).next = free_descriptors;
	free_descriptors = dsc;
}