/* $XConsortium: xf86bcache.c,v 1.2 94/10/12 19:48:30 kaleb Exp $ */
/* $XFree86: xc/programs/Xserver/hw/xfree86/accel/cache/xf86bcache.c,v 3.3 1995/01/28 16:57:41 dawes Exp $ */
/*
 * Based on the S3 block allocator code in XFree86-2.0 by Jon Tombs.
 * The original copyright is reproduced below.
 *
 * Copyright 1993 by Jon Tombs. Oxford University
 * 
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the name of Jon Tombs or Oxford University shall
 * not be used in advertising or publicity pertaining to distribution of the
 * software without specific, written prior permission. The authors  make no
 * representations about the suitability of this software for any purpose. It
 * is provided "as is" without express or implied warranty.
 * 
 * JON TOMBS DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 * ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
 * THE AUTHORS BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES
 * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
 * WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
 * ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
 * SOFTWARE.
 * 
 */

/*
 * Adapted to XFree86 in X11R6 by Hans Nasten. ( nasten@everyware.se ).
 *
 * The cache memory is managed in a tree structure 4 levels deep.
 * At the top level is a CachePool structure, containing a linked list
 * of CacheRec structures.
 * There can be an arbitrary number of Cache Pools, each used for a
 * different purpose. ( font cache, stipple cache or pixmap cache ).
 * A CachePool structure is allocated on each call to the
 * xf86CreateCachePool function and a pointer to the CachePool struct is
 * returned to the caller. All other block allocator functions requires
 * this pointer as a argument in order to identify the Cache Pool to be
 * affected by the call.
 *
 * The list of Cacherec structures each points at a linked list of
 * BitMapRow structures describing a row of memory.
 * A CacheRec structure is allocated for each invocation of the
 * xf86AddToCachePool function and is then linked to the Cache Pool
 * identified by the Pool argument.
 * A CacheRec struct can be used for a single or an arbitrary number of
 * bitplanes. The caller supplies a 32-bit id number that is stored in
 * the various data structures and is passed on when doing callbacks to
 * hw driver code. ( the only callback from the block allocator is for
 * compacting a memory row. Callbacks from font cache code etc. must also
 * pass on this id number when appropriate ).
 * The block allocator does not use the id number internally, it's expected
 * use is to enable hw driver code to identify which bitplanes that are to
 * be affected by hw driver code.
 * 
 * Each BitMapRow structure contains a linked list of BitMapBlock structures
 * describing a row of cache memory.
 *
 * Each BitMapBlock structure describes a allocated piece of cache memory.
 * The BitMapBlock struct contains a reference field used when allowing the
 * cache allocator to reuse already used cache blocks. This is used by the
 * font cache code to let the cache allocator take care of keeping the most
 * recently used fonts in the cache. The higher layer ( font cache etc. ) has
 * to keep the lru field updated if this reallocation scheme is to work.
 * If the reference field is left untouched, ( it's initialized to NULL ),
 * the allocator does not attempt to reuse already allocated cache blocks.
 */

#include	"X.h"
#include	"Xmd.h"
#include	"misc.h"
#include        "xf86.h"
#include        "xf86bcache.h"
#define XCONFIG_FLAGS_ONLY
#include        "xf86_Config.h"


#ifdef DEBUG_FCACHE
static void xf86showcache();
#endif

static void (*xf86CacheMoveBlockFunc)();
static struct CachePoolRec *xf86PoolList = NULL;

/*
 * Init the static pointers.
 */

void xf86InitCache( CacheMoveBlockFunc )
void (*CacheMoveBlockFunc)();

{

    xf86CacheMoveBlockFunc = CacheMoveBlockFunc;

}


/*
 * Create a data structure to keep info about a cache memory pool.
 * A pointer to this structure is the used to identify the pool.
 */

CachePool xf86CreateCachePool( Alignment )
unsigned int Alignment;

{
  CachePool CPool;

    if(( CPool = (CachePool)Xcalloc( sizeof (struct CachePoolRec) )) == NULL )
      return( NULL );

    CPool->alignment = Alignment - 1;
    CPool->next = xf86PoolList;
    xf86PoolList = CPool;
    return( CPool );

}


/*
 * Add a cache memory area to a pool.
 * Each area added to the pool is pointed at by a CacheRec structure
 * that is linked to the CachePool structure.
 */

#ifdef __STDC__
void xf86AddToCachePool( CachePool Pool, short x, short y, 
			 short Width, short Height, unsigned int Id )
#else
void xf86AddToCachePool( Pool, x, y, Width, Height, Id )
CachePool Pool;
short x, y, Width, Height;
unsigned int Id;
#endif

{
  bitMapRowPtr bptr;
  CacheRecPtr CrPtr;

    /*
     * Create a linked list of all rows. Initially there
     * is only one row.
     */
    bptr = (bitMapRowPtr) Xcalloc(sizeof(bitMapRowRec));
    bptr->x = x;
    bptr->y = y;
    bptr->freew = Width;
    bptr->h = Height;
    bptr->id = Id;

    /*
     * Link the new row to the pool via the CacheRec list.
     */
    CrPtr = (CacheRecPtr) Xcalloc( sizeof( struct _cacherec ) );
    CrPtr->width = Width;
    CrPtr->height = Height;
    CrPtr->blocks = bptr;
    CrPtr->next = Pool->crecs;
    Pool->crecs = CrPtr;
    bptr->crchain = (pointer *) CrPtr;
}


/*
 * Return a block to the parent row:
 * Several cases can arise.
 * - We are the last block of the linked list, in which case just add our
 *   length to the free length.
 * - We are the only block in a row. The row is now empty, so if another
 *   empty row exists below or above we merge.
 * - we are a block in the middle of the list of blocks. This is nasty.
 *   we shuffle the blocks that follow by shifting them to the left our length.
 *   This keeps the free space at the right hand end.
 */

#ifdef __STDC__
void xf86ReleaseToCachePool( CachePool Pool, CacheBlock Block )
#else
void xf86ReleaseToCachePool( Pool, Block )
CachePool Pool;
CacheBlock Block;
#endif
{
  bitMapBlockPtr line, tmpb;
  bitMapRowPtr bptr, tmpr;

  bptr = Block->daddy;
  line = bptr->blocks;

  ERROR_F(("free block: (%dx%d):\n", bptr->h, Block->w));
  SHOWCACHE();
  bptr->freew += Block->w;	/* this much we can be sure of */

  if (Block->next == NULL) {	/* we are the last block in a row */

    if (Block == line) {	/* we are the row */
      if ((bptr->prev != NULL) && (bptr->id == bptr->prev->id)
	     && (bptr->prev->blocks == NULL)) {
	/* we are not first in plane so cut ourselves out upward */
	ERROR_F(("returning row to above"));
	bptr->prev->h += bptr->h;
	bptr->prev->next = bptr->next;
	if (bptr->next) { /* don't go off the end of the last row */
	  bptr->next->prev = bptr->prev;
	  tmpr = bptr->next;
	  if( tmpr->blocks == NULL
	      && tmpr->id == tmpr->prev->id ) {
			/* If the row below is empty, merge downwards. */
	    ERROR_F((" and to below"));
	    tmpr->prev->h += tmpr->h;
	    tmpr->prev->next = tmpr->next;
	    if( tmpr->next )
	      tmpr->next->prev = tmpr->prev;
	    Xfree(tmpr);
	  }
	}
	ERROR_F(("\n"));
	Xfree(bptr);
      } else if ((bptr->next != NULL)
		&& (bptr->id == bptr->next->id)
		&& (bptr->next->blocks == NULL)) {
	/* we are not last in plane and the row below is empty, so cut
	 * ourselves out merging with the row below.
	 */
	bptr->next->h += bptr->h;
	bptr->next->prev = bptr->prev;
	bptr->next->y = bptr->y;
	if (bptr->prev) {		/* we are not the head row */
	  bptr->prev->next = bptr->next;
	} else {	  /* promote the row below to new head row */
	  ((CacheRecPtr)(bptr->crchain))->blocks = bptr->next; 
	}
	Xfree(bptr);
       	ERROR_F(("returning row to below\n"));
      } else {  /* just zero our length */
	ERROR_F(("left empty row %d high\n",bptr->h));
	bptr->blocks = NULL;
      }
    } else {
      /* simply loose the end of the line */
      tmpb = line;
	 
      while (tmpb->next != Block)
	tmpb = tmpb->next;

      tmpb->next = NULL;
      ERROR_F(("returning end of line\n"));
    }
  } else { /* we are not the last block in the row */
    int len;
    len = 0;
    tmpb = Block->next;

    /* find the length of blocks behind and adjust there x co-ordinate
     * by our width
     */
    while (tmpb != NULL) {
      len += tmpb->w;	 
      tmpb->x -= Block->w;
      tmpb = tmpb->next;
    }
    if (xf86VTSema) {  /* now shift the following block using a plane copy */
      (xf86CacheMoveBlockFunc)( Block->x + Block->w, Block->y, Block->x,
				 Block->y, bptr->h, len, Block->id );
    }

    /* reconnect the new list of blocks */
    if (Block == line)
      bptr->blocks = Block->next;
    else {
      tmpb = line;
      while (tmpb->next != Block)
	tmpb = tmpb->next;

      tmpb->next = Block->next;
    }
  }
  ERROR_F(("----------To---------------\n"));
  SHOWCACHE();
  /* This allows us to remove the reference to this block even if we don't
   * know where that is. This is used for when we need to free a block in
   * order to store a new one.
   */
  if( Block->reference != NULL )
    *(Block->reference)=NULL; 

  Xfree(Block);

}

/*
 * Go through the linked list of rows looking for a row with height big
 * enough for the requested block.
 * If the height is OK then we check that the free length is also big enough
 * and if so add the block to a linked list in blocks in that row.
 *
 * We also look for any space that is currently in use that would have been
 * big enough. If none of the rows have room, one of these is removed from
 * the cache (subject to its lru value), and the function recurses, knowing
 * this time it will meet success.
 * If we didn't even find a block in use big enough we return NULL and the
 * caller code must throw out some other blocks to make room.
 */

#ifdef __STDC__
CacheBlock xf86AllocFromCachePool( CachePool Pool, short Width, short Height )
#else
CacheBlock xf86AllocFromCachePool( Pool, Width, Height )
CachePool Pool;
short Width, Height;
#endif

{
  CacheRecPtr CrPtr = Pool->crecs;
  bitMapRowPtr bptr;
  bitMapBlockPtr candidate = NULL;
  int oldest=0x7fffffff;   

  Width = ( Width + Pool->alignment ) & ~Pool->alignment;
  while( CrPtr != NULL ) {
    if( Width <= CrPtr->width && Height <= CrPtr->height ) {
      bptr = CrPtr->blocks;
        while( bptr != NULL ) {
        if (bptr->h >= Height ) {
          if (bptr->blocks == NULL) {    /* First use of this row. */
	    bptr->blocks = (bitMapBlockPtr) Xcalloc(sizeof(bitMapBlockRec));
	    bptr->blocks->x = bptr->x;
	    bptr->blocks->y = bptr->y;
	    bptr->blocks->h = Height;
	    bptr->blocks->w = Width;
	    bptr->blocks->daddy = bptr; /* so we can trace a block back to its
					 * parent row.  
					 */
	    if (bptr->h > Height) { /* split the row. We create a new row with
	                             * the unused height of the first.
				     */
	      bitMapRowPtr nbptr=(bitMapRowPtr) Xcalloc(sizeof(bitMapRowRec));

	      nbptr->h = bptr->h - Height;
	      nbptr->freew = bptr->freew;
	      nbptr->x = bptr->x;
	      nbptr->y = bptr->y + Height;
	      nbptr->id = bptr->id;
	      nbptr->crchain = bptr->crchain;
	      if( ( nbptr->next = bptr->next ) != NULL )
	        nbptr->next->prev = nbptr;

	      bptr->next = nbptr;
	      nbptr->prev = bptr;
	      bptr->h = Height;
	    }
	    bptr->freew -= Width;   /* reduce the free space of this row */
	    bptr->blocks->id = bptr->id;
	    SHOWCACHE();
	    return bptr->blocks;
          } else {		        /* This row already contains a block */
	    if (bptr->freew >= Width) {   /* is the space left big enough? */
	      bitMapBlockPtr bbptr = bptr->blocks;

	      while (bbptr->next != NULL) /* find the last block */
	        bbptr = bbptr->next; 

	      /* and add this block onto the end */
	      bbptr->next = (bitMapBlockPtr) Xcalloc(sizeof(bitMapBlockRec));
	      bbptr->next->x = bbptr->x + bbptr->w;
	      bbptr->next->y = bptr->y;
	      bbptr->next->h = Height;
	      bbptr->next->w = Width;
	      bbptr->next->daddy = bptr;
	      bbptr->next->id = bptr->id;
	      bptr->freew -= Width;
	      SHOWCACHE();
	      return bbptr->next;
	    } else { /* see if any slot is big enough anyway */
	      bitMapBlockPtr bbptr = bptr->blocks;
	      while (bbptr/*->next*/ != NULL)  {
	        if (bbptr->w >= Width && bbptr->lru < oldest
		   && bbptr->lru > 1 && bbptr->reference != NULL) {
	          oldest = bbptr->lru;
	          candidate = bbptr; /* Our prime candidate to remove
				      * if no space is found.
				      * ( don't remove blocks that has
				      *   no valid reference pointer ).
				      */
		  ERROR_F(("Want h=%d w=%d Candidate %d h=%d w=%d lru=%d\n",
			   Height,Width,bbptr,bptr->h,bbptr->w,bbptr->lru));
	        }
	        bbptr = bbptr->next;
	      }
	    }
          }
        }
        bptr = bptr->next;	/* Next row. */
      }
    }
    CrPtr = CrPtr->next;	/* Next CacheRec struct. */
  }
  /* If we get here then there are no slots left
   * We throw out the least used block if we found one big enough.
   * else we return null and let the calling code do something about it.
   */
  if (candidate != NULL) {
    ERROR_F(("forced block return\n"));
    xf86ReleaseToCachePool( Pool, candidate );
    return xf86AllocFromCachePool( Pool, Width, Height);
  } else {
    ERROR_F(("no block available, returning NULL\n"));
    return NULL;	/* shouldn't happen unless you try very hard */
  }

}

#ifdef DEBUG_FCACHE
/*
 * debugging print out, this give a nice picture of the current structure
 * of linked lists - believe it or not.
 */
static void xf86showcache()
{
    bitMapBlockPtr tmpb;
    bitMapRowPtr brptr;
    CacheRecPtr CrPtr;
    struct CachePoolRec *PPtr;

    for( PPtr = xf86PoolList; PPtr != NULL; PPtr = PPtr->next ) {
      ErrorF("----- Cache Pool %d Alignment %d -----\n",
	     PPtr, PPtr->alignment + 1);
      for( CrPtr = PPtr->crecs; CrPtr != NULL; CrPtr = CrPtr->next ) {
	for (brptr = CrPtr->blocks; brptr != NULL; brptr = brptr->next) {
          ErrorF("id %d freew %d h %d y %d: ", brptr->id,
	         brptr->freew, brptr->h, brptr->y);
          for (tmpb = brptr->blocks; tmpb != NULL; tmpb = tmpb->next)
	    ErrorF(" block x=%d w=%d y=%d h=%d",
		   tmpb->x, tmpb->w, tmpb->y, tmpb->h);

	  ErrorF(":\n");
        }
      }
    }

}
#endif