/*
 * Copyright 1987 Alan Kent
 *
 * Permission is granted to redistribute this code as long
 * as this message is retained in the code and the code is
 * not sold without written permission from the author.
 *
 * UUCP: {seismo,hplabs,mcvax,ukc,nttlab}!munnari!goanna.oz!ajk
 * ACSnet: ajk@goanna.oz
 * ARPA: munnari!goanna.oz!ajk@SEISMO.ARPA
 */


#include "hd.h"


#define CACHE_SIZE		40

/* Cache Node types */

#define NOT_IN_CACHE	0
#define CN_SPECIAL		1
#define CN_HISTORY		2
#define CN_DIRTY		3


#define HASH_SIZE		(CACHE_SIZE*3)
#define HASH(block)		(((block)&0x7fff)%HASH_SIZE)

static struct cache *	hash_table[ HASH_SIZE ];


static struct cache {

	struct Node node;
	struct cache *collision;
	struct posn posn;
	int			type;
	UBYTE		buf[ HD_SECTOR ];

} cache[ CACHE_SIZE ];


#define DIRTY_LIMIT		10
#define SPECIAL_LIMIT	( CACHE_SIZE - DIRTY_LIMIT - 7 )
#define MAX_BASES		10


extern struct cache *	cache_search ();
extern struct Node *	RemHead ();
extern struct Node *	RemTail ();
extern LONG				log_to_phys ();


static struct List	history;
static struct List	dirty;
static int			num_dirty;
static struct List	special;
static int			special_count;
static int			num_bases = 0;
static LONG			bases[ MAX_BASES ];


UBYTE *
read_cache ( posn )
struct posn *posn;
{
	register struct cache *c;
	int i;
	struct posn next_posn;


	/* see if sector is in special cache list */

	c = cache_search ( posn );
	if ( c != NULL ) {

		switch ( c->type ) {

		case CN_SPECIAL :

			/* special list still good for a bit longer! */
			
			special_count = 5;
			Remove ( c );
			AddHead ( &history , c );
			c->type = CN_HISTORY;
			return ( c->buf );

		case CN_DIRTY :

			/* yes, well have to leave it there! */

			return ( c->buf );

		case CN_HISTORY :
			Remove ( c );
			AddHead ( &history , c );	/* move to head of history */
			c->type = CN_HISTORY;
			return ( c->buf );
		}
	}

	/* see if the special_case is really being used for anything */

	if ( --special_count <= 0 ) {

		/* move everything left in the special cache over to the normal */
		/* cache - it does not seem to be needed anymore */

		while ( ( c = (struct cache *)special.lh_Head )->node.ln_Succ != NULL ) {
			Remove ( c );
			AddTail ( &history , c );
			c->type = CN_HISTORY;
		}
	}

	/* ok, well we have to actually go and read the sector! */

	/* if the special cache list is not empty, just read a sector */

	if ( special.lh_Head->ln_Succ != NULL ) {

		c = (struct cache *) RemTail ( &history );
		new_posn ( c , posn );
		flush_seek ( &c->posn );
		read_sector ( &c->posn , c->buf );
		analyse ( c , &next_posn );
		AddHead ( &history , c );
		c->type = CN_HISTORY;
		return ( c->buf );
	}

	/* ok!! now, the special list is EMPTY! Is the disk access we want */
	/* to do the NEXT of a recently accessed page? */

	for ( i = 0, c = (struct cache *) history.lh_Head;
	i < 5  &&  c->node.ln_Succ != NULL;
	i++, c = (struct cache *)c->node.ln_Succ ) {
		if ( is_next ( posn , c ) ) {

			/* GOODY! Looks like we have got something to pre-read! */

			/* first special entry will be what we asked for */
			next_posn = *posn;

			for ( i = 0; i < SPECIAL_LIMIT; i++ ) {

				/* if in any of the caches, dont re-read! */

				if ( cache_search ( &next_posn ) != NULL )
					break;

				c = (struct cache *) RemTail ( &history );
				new_posn ( c , &next_posn );
				flush_seek ( &c->posn );
				read_sector ( &c->posn , c->buf );
				analyse ( c , &next_posn );
				AddTail ( &special , c );
				c->type = CN_SPECIAL;

				/* end of list will set -ve values */

				if ( next_posn.cylinder < 0 )
					break;
			}
			c = (struct cache *) special.lh_Head;
			Remove ( c );
			AddHead ( &history , c );
			c->type = CN_HISTORY;
			special_count = 5;
			return ( c->buf );
		}
	}

	/* Oh well, its just a boring read then */

	c = (struct cache *) RemTail ( &history );
	new_posn ( c , posn );
	flush_seek ( &c->posn );
	read_sector ( &c->posn , c->buf );
	analyse ( c , &next_posn );
	AddHead ( &history , c );
	c->type = CN_HISTORY;
	return ( c->buf );
}


void
write_cache ( posn , buf )
struct posn *posn;
char *buf;
{
	register struct cache *c , *scan;


	/* is sector already in a cache? */

	c = cache_search ( posn );
	if ( c != NULL ) {

		if ( c->type == CN_DIRTY ) {

			/* dirty sectors can be left were they are */

			copy_sector ( buf , c->buf );
			return;
		}

		/* otherwise, fall through - it will have to be put in the */
		/* dirty list */

	}
	else {

		/* get a cache for the sector. */

		c = (struct cache *) history.lh_TailPred;
	}

	/* Ok, we have got a sector to put everything in */

	Remove ( c );
	new_posn ( c , posn );
	copy_sector ( buf , c->buf );

	/* now, we need a sorted insertion to keep dirty list sorted by cyl */

	if ( dirty.lh_Head->ln_Succ != NULL ) {
		for ( scan = (struct cache *)dirty.lh_Head;
		scan->node.ln_Succ != NULL;
		scan = (struct cache *) scan->node.ln_Succ ) {
			if ( scan->posn.cylinder > posn->cylinder )
				break;
		}
		Insert ( &dirty , c , scan->node.ln_Pred );
	}
	else {		/* only node in list */
		AddHead ( &dirty , c );
	}
	c->type = CN_DIRTY;
	num_dirty++;

	/* if too many dirty pages, probably should write some out */

	if ( num_dirty > DIRTY_LIMIT ) {

		/* try and find a close cylinder */

		for ( scan = (struct cache *)dirty.lh_Head;
		scan->node.ln_Succ != NULL;
		scan = (struct cache *)scan->node.ln_Succ ) {
			if ( scan->posn.cylinder >= cur_posn.cylinder )
				break;
		}

		/* if at end of list, just use last entry */

		if ( scan->node.ln_Succ == NULL )
			scan = (struct cache *) scan->node.ln_Pred;
		write_dirty ( scan );
	}
}



void
flush_all ()
{
	while ( dirty.lh_Head->ln_Succ != NULL )
		write_dirty ( dirty.lh_Head );
}


write_dirty ( c )
register struct cache *c;
{
	Remove ( c );
	num_dirty--;
	write_sector ( &c->posn , c->buf );
	AddTail ( &history , c );
	c->type = CN_HISTORY;
}


void
clear_all ()
{
	register int i;
	register struct cache *c;

	NewList ( &special );
	NewList ( &dirty );
	NewList ( &history );
	special_count = 0;
	num_dirty = 0;
	for ( i = 0; i < HASH_SIZE; i++ )
		hash_table[i] = NULL;
	for ( i = 0; i < CACHE_SIZE; i++ ) {
		c = &cache[i];
		c->posn.cylinder = -3;
		c->posn.sector = 0;
		c->posn.surface = 0;
		c->posn.block = -3 * first.sectors * first.heads;
		AddTail ( &history , c );
		c->type = CN_HISTORY;
		c->collision = hash_table[ HASH(c->posn.block) ];
		hash_table[ HASH(c->posn.block) ] = c;
	}
}


int
init_cache ()
{
	register int i;

	clear_all ();
	return ( 0 );
}


void
free_cache ()
{
	register int i;

	flush_all ();
}


struct cache *
cache_search ( posn )
register struct posn *posn;
{
	register struct cache *c;

	c = hash_table[ HASH(posn->block) ];
	while ( c != NULL ) {
		if ( posn->block == c->posn.block )
			return ( c );
		c = c->collision;
	}
	return ( NULL );
}


new_posn ( c , posn )
register struct cache *c;
struct posn *posn;
{
	register struct cache **old;
	register struct cache **h;

	/* first, remove from existing hash table position */

	old = &hash_table[ HASH(c->posn.block) ];
	while ( *old != NULL ) {
		if ( *old == c ) {				/* found pointer to c */
			*old = (*old)->collision;	/* unlink node */
			break;
		}
		old = &(*old)->collision;
	}

	/* now update the position */

	c->posn = *posn;

	/* now insert into hash table at new position */

	h = &hash_table[ HASH(c->posn.block) ];
	c->collision = *h;
	*h = c;
}



flush_seek ( posn ) /* write out all dirty tracks on way to posn */
struct posn *posn;
{
	register struct cache *c;

	if ( posn->cylinder > cur_posn.cylinder ) {
		for ( c = (struct cache *)dirty.lh_Head;
		c->node.ln_Succ != NULL;
		c = (struct cache *)c->node.ln_Succ ) {
			if ( c->posn.cylinder >= cur_posn.cylinder
			&&  c->posn.cylinder <= posn->cylinder ) {
				c = (struct cache *)c->node.ln_Pred;
				write_dirty ( c->node.ln_Succ );
			}
		}
	}
	else {
		for ( c = (struct cache *)dirty.lh_TailPred;
		c->node.ln_Pred != NULL;
		c = (struct cache *)c->node.ln_Pred ) {
			if ( c->posn.cylinder <= cur_posn.cylinder + 1
			&&  c->posn.cylinder >= posn->cylinder ) {
				c = (struct cache *)c->node.ln_Succ;
				write_dirty ( c->node.ln_Pred );
			}
		}
	}
}


/* have a look, check block # to see if any new partitions */
analyse ( c , next_posn )
register struct cache *c;
register struct posn *next_posn;
{
	LONG logical_block , base;
	LONG type , subtype;
	ULONG *buf;


	buf = (ULONG*) c->buf;
	type = buf[0];
	subtype = buf[127];

	if ( type == 2  &&  subtype == 2		/* File Header */
	||   type == 2  &&  subtype == -3 ) {	/* User Directory */

		/* these blocks point to themselves, so we can use block # */
		/* to work out where partitions start */

		base = c->posn.block - buf[1];

		/* see if we know about this base yet, if not add it */

		new_base ( base );
	}

	/* ok, now look for a next pointer */

	get_next ( c , next_posn );
}


get_next ( c , next_posn )
register struct cache *c;
register struct posn *next_posn;
{
	LONG type , subtype , next , block;
	ULONG *buf;

	buf = (ULONG *) c->buf;
	type = buf[0];
	subtype = buf[127];
	next = buf[4];

	next_posn->block = -1;
	next_posn->sector = -1;
	next_posn->surface = -1;
	next_posn->cylinder = -1;

	if ( type == 2  &&  subtype == -3		/* file header */
	||   type == 16 &&  subtype == -3		/* file extension */
	||   type == 8 ) {						/* data block */
		block = log_to_phys ( c->posn.block , next );
		if ( block >= 0
		&&  block < first.sectors * first.heads * first.cylinders ) {
			next_posn->block = block;
			next_posn->sector = block % first.sectors;
			next_posn->surface = ( block / first.sectors ) % first.heads;
			next_posn->cylinder = block / ( first.sectors * first.heads );
		}
	}
}


LONG
log_to_phys ( real , logical )
LONG real , logical;
{
	register int i;

	for ( i = num_bases - 1; i >= 0; i-- )
		if ( real >= bases[i] )
			return ( logical + bases[i] );
	return ( -1 );
}


new_base ( base )
LONG base;
{
	register int i , j;

	for ( i = num_bases - 1; i >= 0; i-- ) {
		if ( bases[i] == base )
			return;
		if ( bases[i] < base )
			break;
	}
	i++;
	for ( j = num_bases; j > i; j-- )
		bases[j] = bases[j-1];
	bases[i] = base;
	num_bases++;
}


is_next ( posn , c )
struct posn *posn;
struct cache *c;
{
	struct posn next_posn;

	get_next ( c , &next_posn );
	return ( posn->block == next_posn.block );
}