bufffile.c

b tree how to operate on b tr

/*JS*********************************************************************
*
*    Program : BUFFFILE
*    Language: ANSI-C + POSIX functions where available
*    Author  : Joerg Schoen
*    Purpose : Package to provide buffered access to arbitrary regions of
*              a file. The interface consists of the following routines:
*
*     bFileOpen, bFileClose:
*       Opens and closes the file for buffered access using a handle of
*       type BuffFile. Additionally the user may specify to use memory
*       mapped I/O for efficiency or that the file should be locked for
*       exclusive read/write.
*     bFileFlush:
*       Ensures that all dirty pages are written to disk.
*
*     bFileGet:
*       Gets a pointer to the specified region of the file. The returned
*       length may be smaller than the requested one if the region crosses a
*       page boundary. In that case multiple calls to bFileGet are necessary.
*       Writing is done by marking a buffer 'dirty'.
*     bFileSet:
*       Used to unprotect a region or to mark it dirty. This routine does
*       *not* load the pages, thus it works only after a single bFileGet for
*       the region or multiple bFileGet's that lock the region (to ensure
*       none of the buffers are reused).
*
*     bFileRead, bFileWrite, bFileByteSet,bFileByteCopy,bFileByteMove:
*       Reads and writes data, set and copys regions using multiple calls
*       to bFileGet.
*
*************************************************************************/

#ifndef lint
static const char rcsid[] = "$Id: bufffile.c,v 1.12 1998/02/26 17:50:45 joerg Stab joerg $";
#endif

/*********     INCLUDES                                         *********/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <jsconfig.h>

#include <jssubs.h>

#ifndef CONFIG_NO_POSIX
# include <sys/types.h>
# include <sys/stat.h>
# include <fcntl.h>
# include <unistd.h>
#endif

/*********     DEFINES                                          *********/
#ifndef BFILEMODE_PROT
/*  START-DEFINITIONS  */
#include <stdio.h>     /*  For "FILE" definition  */
#include <jsconfig.h>  /*  For configurational definitions  */

typedef struct BuffFilePage BuffFilePage;
struct BuffFilePage {
  BuffFilePage *BFP_Next; /*  pointer to next page in linked list  */

  /*  PageLen may be smaller than the pagesize for read pages at EOF  */
  long          BFP_PageNr,BFP_PageLen;

  /*  Actual page  */
  char         *BFP_Page;

  /*  multiple protections for a region are OK  */
  short         BFP_Flags,BFP_Prot;
};
#define BFP_DIRTY     (1<<0)  /*  page is dirty  */
#define BFP_REREAD    (1<<1)  /*  re-read  */

typedef struct BuffFile BuffFile;
struct BuffFile {
  int BF_Type;
#ifndef CONFIG_NO_POSIX
  int BF_Handle;
#else
  FILE *BF_Handle;
#endif
  int BF_PageShift;
  int BF_HashLen;

  BuffFilePage **BF_HashTab;

  /*  For memory mapped I/O  */
  char *BF_MMPage;
  long BF_MMPageLen;
  short BF_MMProt;
};

/*  For routine bFileOpen  */
#define BFILE_WRITE          (1<<0)  /*  Open for r/w (default is rd-only)  */
#define BFILE_CREATE         (1<<1)  /*  Create file, deleting old contents  */
#define BFILE_MMAP           (1<<2)  /*  Use memory mapped I/O if possible  */
#define BFILE_FLOCK          (1<<3)  /*  Lock the whole file after opening  */
#define BFILE_FLOCKW         (1<<4)  /*  Same as FLOCK, but wait for others  */
#define BFILE_MULTI          (1<<5)  /*  Multiuser support when accessing  */

/* ***  For bFileGet  *** */
#define BFILEMODE_PROT       (1<<0)  /*  Prevent reusage of the page buffer  */
#define BFILEMODE_UNPROT     (1<<1)  /*  Allow reusage of the page buffer  */
#define BFILEMODE_CLEARPROT  (1<<2)  /*  Clear any protections   */
#define BFILEMODE_DIRTY      (1<<3)  /*  Mark a page dirty  */
#define BFILEMODE_REREAD     (1<<4)  /*  Force re-read even if in memory  */
/*  If the caller of bFileGet expects the returned length
 *   to be identical to passed one
 */
#define BFILEMODE_FULLMAP    (1<<5)

/*  How to get the current file length. You have to flush the file first!  */
#ifndef CONFIG_NO_POSIX
# define bFileFLength(bfp)   fdFileLength((bfp)->BF_Handle)
#else
# define bFileFLength(bfp)   fpFileLength((bfp)->BF_Handle)
#endif
/*  END-DEFINITIONS  */
#endif

#ifndef CONFIG_NO_POSIX
# define CONFIG_USE_MMAP /*  SVR4 and BSD support it  */
#else
# undef CONFIG_USE_MMAP  /*  Don't try on non-POSIX systems  */
#endif

#ifdef CONFIG_USE_MMAP
# include <sys/mman.h>
#endif

/* Using the defaults, the maximum used memory for buffering is
 *  DEFAULT_HASHLEN * DEFAULT_MAXPAGES * 2^DEFAULT_PAGESHIFT = 512KByte
 */
#ifndef BUFFFILE_DEFHASHLEN
# define BUFFFILE_DEFHASHLEN     16
#endif

#ifndef BUFFFILE_DEFMAXPAGES
/*  Maximum number of pages in a hash chain
 *   before we start to steal pages.
 */
# define BUFFFILE_DEFMAXPAGES     4
#endif

#ifndef BUFFFILE_DEFPAGESHIFT
/*  Default size of pages is 2^13 = 8KByte chunks  */
# define BUFFFILE_DEFPAGESHIFT   13
#endif

/* **  Internal macros  ** */
#define BF_PAGESIZE(bfp)           (1 << (bfp)->BF_PageShift)
#define BF_PAGEOFFSET(bfp,pageNr)  ((pageNr) << (bfp)->BF_PageShift)

#define freePage(p)  (free((p)->BFP_Page),free(p))

#define Prototype extern
/*********     PROTOTYPES                                       *********/
Prototype BuffFile      *bFileOpen(const char *name,int hashLen,int pLenShift,
				   int mode);
Prototype int            bFileClose(BuffFile *bfp);
Prototype int            bFileFlush(BuffFile *bfp,int mode);
static int               flushPage(BuffFile *bfp,BuffFilePage *p);
Prototype int            bFileTruncate(BuffFile *bfp,long size);

Prototype char          *bFileGet(BuffFile *bfp,long offset,long *pLen,
				  int mode);
Prototype char          *bFileGet2(BuffFile *bfp,long offset,long len,int mode);

Prototype int            bFileSet(BuffFile *bfp,long offset,long len,int mode);

Prototype int            bFileRead(BuffFile *bfp,void *ptr,long offset,
				   long size);
Prototype int            bFileWrite(BuffFile *bfp,const void *ptr,long offset,
				    long size);

Prototype int            bFileByteSet(BuffFile *bfp,int c,long offset,
				      long size);
Prototype int            bFileByteCopy(BuffFile *bfp,long sOff,long dOff,
				       long size);
Prototype int            bFileByteMove(BuffFile *bfp,long sOff,long dOff,
				       long size);

Prototype long           bFileNLocks(BuffFile *bfp);

Prototype int            BuffFileMaxPage;

/*********     GLOBAL VARIABLES                                 *********/
int BuffFileMaxPage = BUFFFILE_DEFMAXPAGES;

/*JS*********************************************************************
*   Opens the named file for buffered I/O, using pLenShift for
*    determining the length of a page. mode specifies if the file is
*    opened for writing (BFILE_WRITE) or if memory mapped I/O should be
*    used if possible (BFILE_MMAP). File growth is not possible when
*    using memory mapped I/O.
*************************************************************************/

BuffFile *bFileOpen(const char *name,int hashLen,int pLenShift,int mode)

/************************************************************************/
{
  BuffFile *bfp;

  if((bfp = (BuffFile *)calloc(1,sizeof(*bfp))) == NULL) return(NULL);

  bfp->BF_Type = mode;

  bfp->BF_HashLen = hashLen ? hashLen : BUFFFILE_DEFHASHLEN;
  bfp->BF_PageShift = pLenShift ? pLenShift : BUFFFILE_DEFPAGESHIFT;
  bfp->BF_MMPage = NULL;

#ifndef CONFIG_NO_POSIX
  if((bfp->BF_Handle = open(name,(mode & BFILE_WRITE) ?
			    ((mode & BFILE_CREATE) ? (O_RDWR|O_CREAT|O_TRUNC) :
			     O_RDWR) : O_RDONLY,0666)) < 0)
    goto error;

  /*  If required, lock the whole file  */
  if(mode & (BFILE_FLOCK | BFILE_FLOCKW)) {
    struct flock lock;

    lock.l_type   = (mode & BFILE_WRITE) ? F_WRLCK : F_RDLCK;
    lock.l_start  = 0;
    lock.l_whence = SEEK_SET;
    lock.l_len    = 0;
    if(fcntl(bfp->BF_Handle,(mode & BFILE_FLOCKW) ? F_SETLKW : F_SETLK,
	     &lock) < 0)
      goto error;
  }

#ifdef CONFIG_USE_MMAP
  if(mode & BFILE_MMAP) {
    struct stat stbuf;

    if(fstat(bfp->BF_Handle,&stbuf)) goto error;

    if(stbuf.st_size > 0) {
      bfp->BF_MMPageLen = stbuf.st_size;

      /*  If we open file for writing, restrict memory mapped region to
       *   multiples of pages. This will ensure that additional pages
       *   that are allocated to enlarge the file start on page boundaries
       *   in the file.
       */
      if(mode & BFILE_WRITE) bfp->BF_MMPageLen &= ~(BF_PAGESIZE(bfp) - 1);

      /*  Do not try to map empty regions  */
      if(bfp->BF_MMPageLen == 0)
	bfp->BF_MMPage = NULL;
      else if((bfp->BF_MMPage = mmap(NULL,bfp->BF_MMPageLen,
				     (mode & BFILE_WRITE) ?
				     (PROT_WRITE | PROT_READ) : PROT_READ,
				     MAP_SHARED,bfp->BF_Handle,0)) ==
	      (void *)-1) goto error;
    }
  }
#endif
#else
  /*  Use ANSI-fopen function and prevent additional buffering by stdio  */
  if((bfp->BF_Handle = fopen(name,(mode & BFILE_WRITE) ?
			     ((mode & BFILE_CREATE) ? "wb+" : "rb+") : "rb"))
     == NULL ||
     setvbuf(bfp->BF_Handle,NULL,_IONBF,0))
    goto error;
#endif

  if((bfp->BF_HashTab = (BuffFilePage **)calloc(bfp->BF_HashLen,
						sizeof(*(bfp->BF_HashTab))))
     == NULL)
    goto error;

  return(bfp);
error:
#ifndef CONFIG_NO_POSIX
  if(bfp->BF_Handle >= 0) close(bfp->BF_Handle);
#ifdef CONFIG_USE_MMAP
  if(bfp->BF_MMPage) munmap(bfp->BF_MMPage,bfp->BF_MMPageLen);
#endif

#else
  if(bfp->BF_Handle) fclose(bfp->BF_Handle);
#endif

  if(bfp->BF_HashTab) free(bfp->BF_HashTab);
  free(bfp);

  return(NULL);
}

/*JS*********************************************************************
*   Closes the buffered file, flushing all data.
*************************************************************************/

int bFileClose(BuffFile *bfp)

/************************************************************************/
{
  int i,ret;

  ret = 0;

  if(bFileFlush(bfp,0) < 0) ret = -1;

  for(i = 0 ; i < bfp->BF_HashLen ; i++) {
    BuffFilePage *p,*n;

    for(p = bfp->BF_HashTab[i] ; p ; p = n) {
      n = p->BFP_Next;
      freePage(p);
    }
  }

  free(bfp->BF_HashTab);

#ifdef CONFIG_USE_MMAP
  if(bfp->BF_MMPage && munmap(bfp->BF_MMPage,bfp->BF_MMPageLen) < 0) ret = -1;
#endif

  if(
#ifndef CONFIG_NO_POSIX
    close(bfp->BF_Handle) < 0
#else
    fclose(bfp->BF_Handle)
#endif
    ) ret = -1;

  free(bfp);

  return(ret);
}

/*JS*********************************************************************
*   Flushes all dirty buffers to disk. If Bit 0 of mode is set, buffers
*    are freed if they exceed the maximum number of buffers. If Bit 1 of
*    mode is set, a memory mapped region is extended if necessary to cover
*    the whole file. If Bit 2 of mode is set, the dirty flag is not
*    deleted when a page is flushed.
*************************************************************************/

int bFileFlush(BuffFile *bfp,int mode)

/************************************************************************/
{
  int i;

  /*  Flush all pages  */
  for(i = 0 ; i < bfp->BF_HashLen ; i++) {
    BuffFilePage *p;
    int count,countUL;

    /*  Flush all pages, count whole and unlocked ones  */
    for(count = countUL = 0, p = bfp->BF_HashTab[i] ; p ;
	p = p->BFP_Next, count++) {
      if(p->BFP_Flags & BFP_DIRTY) {
	if(flushPage(bfp,p)) goto error;
	if(!(mode & 4)) p->BFP_Flags &= ~BFP_DIRTY;
      }
      if(p->BFP_Prot == 0) countUL++;
    }

    /*  Free pages?  */
    if((mode & 3) && count > BuffFileMaxPage && countUL > 0) {
      BuffFilePage *previous;

      /*  Start freeing pages (count >= 0) at the end of the list  */
      count -= BuffFileMaxPage + countUL;
      for(p = bfp->BF_HashTab[i], previous = NULL ; p ; count++)
	if(count >= 0 && p->BFP_Prot == 0) {
	  BuffFilePage *next = p->BFP_Next;

	  if(previous) {
	    previous->BFP_Next = next;
	  } else {
	    bfp->BF_HashTab[i] = next;
	  }
	  freePage(p);
	  p = next; /*  previous doesn't change  */
	} else {
	  previous = p;
	  p = p->BFP_Next;
	}
    }
  }

#ifdef CONFIG_USE_MMAP
  /*  Try to extend memory mapped region only if file is opened for r/w  */
  if((mode & 2) && (bfp->BF_Type & (BFILE_MMAP|BFILE_WRITE)) ==
     (BFILE_MMAP|BFILE_WRITE) && bfp->BF_MMProt == 0) {
    struct stat stbuf;
    long size;

    /*  Check if some pages are still locked. Otherwise we
     *   might have the memory mapped region and a page
     *   pointing to the same file location.
     */
    for(i = 0 ; i < bfp->BF_HashLen ; i++) {
      BuffFilePage *p;

      for(p = bfp->BF_HashTab[i] ; p ; p = p->BFP_Next) {
	if(p->BFP_Prot) goto ende;
	p->BFP_PageNr = -1; /*  mark this page unused  */
      }
    }

    if(fstat(bfp->BF_Handle,&stbuf)) goto error;

    /*  Restrict memory mapped region to multiples of pages  */
    size = stbuf.st_size & ~(BF_PAGESIZE(bfp) - 1);

    /*  Check if file size has changed  */
    if(size != bfp->BF_MMPageLen) {
      if(bfp->BF_MMPage && munmap(bfp->BF_MMPage,bfp->BF_MMPageLen) < 0)
	goto error;

      if((bfp->BF_MMPageLen = size) == 0)
	bfp->BF_MMPage = NULL;
      else if((bfp->BF_MMPage = mmap(NULL,bfp->BF_MMPageLen,
				     (PROT_WRITE | PROT_READ),MAP_SHARED,
				     bfp->BF_Handle,0)) == (void *)-1)
	goto error;
    }
  }
ende:

# if defined(__linux__)
  if((bfp->BF_Type & (BFILE_MMAP|BFILE_WRITE)) == (BFILE_MMAP|BFILE_WRITE)) {
    /*  Schedule memory mapped region for write  */
    if(msync(bfp->BF_MMPage,bfp->BF_MMPageLen,MS_ASYNC) < 0) goto error;
  }
# endif
#endif

  /*  Flush all data to disk  */
#ifndef CONFIG_NO_POSIX
#if 0  /*  Prevent to much I/O  */
  if(fsync(bfp->BF_Handle) < 0) goto error;
#endif
#else
  if(fflush(bfp->BF_Handle) == EOF) goto error;
#endif

  return(0);
error:
  return(-1);
}

/*JS*********************************************************************
*   Internal routine to flush contents of a page.
*************************************************************************/

static int flushPage(BuffFile *bfp,BuffFilePage *p)

/************************************************************************/
{
  if(
#ifndef CONFIG_NO_POSIX
     lseek(bfp->BF_Handle,BF_PAGEOFFSET(bfp,p->BFP_PageNr),SEEK_SET) < 0 ||
     write(bfp->BF_Handle,p->BFP_Page,p->BFP_PageLen) != p->BFP_PageLen
#else
     fseek(bfp->BF_Handle,BF_PAGEOFFSET(bfp,p->BFP_PageNr),SEEK_SET) ||
     fwrite(p->BFP_Page,1,p->BFP_PageLen,bfp->BF_Handle) != p->BFP_PageLen
#endif
     ) return(-1);

  return(0);
}

/* ERROR-DEFINITIONS from bFileTruncate label _ERR_BFILETRUNC ord 16
   Locked pages beyond file size found
*/

/*JS*********************************************************************
*
*************************************************************************/

int bFileTruncate(BuffFile *bfp,long size)

/************************************************************************/
{
  int i;

  for(i = 0 ; i < bfp->BF_HashLen ; i++) {
    BuffFilePage *p,*prev,*next;

    for(prev = NULL, p = bfp->BF_HashTab[i] ; p ; p = next) {