/*static char *SCCSID = "@(#)create.c	6.1 90/11/18";*/
/*static char *SCCSID = "@(#)create.c 13.5 90/03/13";*/
/***	CREATE.C - Routines to create files.
 *
 *	CHKDSK
 *	Gregory A. Jones
 *	Copyright 1988 Microsoft Corporation
 *
 *	Modification history:
 *	G.A. Jones	07/15/88     Translated from filesystem assembly.
 *	P.A. Williams	06/06/89     Changed chk_add_dirent and chk_namcmp
 *				     to use com_strcmpi instead of memcmp.
 */

#include "ldefs.h"
#include "ltypes.h"
#include "globals.h"
#include <pr_chk.h>
#include <pr_fsys.h>


/***	chk_find_ip - find insertion point
 *
 *	This function is called when promoting an entry to a higher-
 *	level DIRBLK.  It scans the parent of a DIRBLK for the down-
 *	pointer which points to that DIRBLK.  It then sets a pointer
 *	to point to the entry which owns the downpointer.
 *
 *	chk_find_ip (block, lsn, ptr)
 *
 *	ENTRY		block - pointer to DIRBLK to search
 *			lsn   - downpointer value to look for
 *			ptr   - address of a pointer to store insertion point in
 *
 *	EXIT		Returns non-zero if found, zero if not found
 *
 *	CALLS		None
 */
USHORT chk_find_ip (block, lsn, ptr)
   DIRBLK *block;
  ULONG lsn;
  UCHAR **ptr;
{
  union dp dp;

  dp.p = DIR_START (*block);

  while (DOWN_PTR (dp) != lsn) {
    if (dp.d->fFlags & DF_END)
      return (0);
    GETNEXT_ENTRY (dp);
  }
  *ptr = dp.p;
  return (1);
}

/***	chk_namcmp - compare two names
 *
 *	This function compares a name against a directory block entry
 *	to see if it is greater or less.  It assumes that the names
 *	are not equal;	it is only used in the phase of chk_add_dirent
 *	which finds insertion points, not when it's trying to see
 *	whether an entry already exists.
 *
 *	chk_namcmp (name, entry, len)
 *
 *	ENTRY		name  - pointer to name to compare
 *			entry - pointer to DIRENT to compare
 *			len   - length of the source name
 *
 *	EXIT		Returns non-zero if entry is greater than source name
 *			Returns zero if entry is less than source name
 *
 *	CALLS		strncmp
 */
USHORT chk_namcmp (name, cp_index, entry, len)
  UCHAR *name;
  USHORT cp_index;
   DIRENT *entry;
  USHORT len;
{
  int i;

#ifndef PAWa
  i = memcmp (name, entry->bName, len);
#else
  i = (entry->fFlags & DF_END)?-1:chk_strnicmp (name,
						  cp_index,
						  entry->bName,
						  entry->bCodePage,
						  len);
#endif

  if (i > 0)			/* name is greater than entry */
    return (0);
  else if (i < 0)		/* name is less than entry */
    return (1);

/*** nmc4: ***/
/* The names look equal, but we may have compared too far,
 * and gotten a falsely equal compare beyond the end of the
 * entry's name.  We use the lengths to determine what to
 * return.
 */

  if (len > entry->cchName)	/* compared extra bytes of entry */
    return (0);
  else				/* entry is longer, therefore greater */
    return (1);
}

/***	chk_makeroom - make room for a new entry in a DIRBLK
 *
 *	This function is called by chk_add_dirent to try to make room
 *	for a new DIRENT in a DIRBLK.  It examines the free space
 *	at the end of the DIRBLK to see if there's enough room left.
 *	If there is, the stuff from the insertion point on is shifted
 *	down to make room for the new entry, and a non-zero value is
 *	returned.  If there isn't enough room, a value of zero is returned.
 *
 *	chk_makeroom (len, block, entry)
 *
 *	ENTRY		len   - amount of room we need
 *			block - address of start of DIRBLK
 *			entry - point to insert space
 *
 *	EXIT		Returns non-zero if successful, zero if no room
 *
 *	CALLS		memmove
 *
 *	EFFECTS		Opens a hole in a DIRBLK
 */
USHORT chk_makeroom (len, block, entry)
  USHORT len;
   DIRBLK *block;
  UCHAR *entry;
{
  if (block->offulFirstFree + len > SECTORS_PER_DIRBLK * SECSIZE)
    return (0);				/* no room in this DIRBLK */

  memmove (entry+len, entry, (size_t)(block->offulFirstFree - (entry - (UCHAR *)block)));
  block->offulFirstFree += len;		/* update end pointer */
  return (1);				/* successfully made a hole */
}

/***	chk_split_dir - split a directory block in two
 *
 *	This function is called when a DIRENT will not fit into
 *	a DIRBLK.  The directory block must be split near the middle.
 *	First we find the first DIRENT which extends beyond the half-
 *	way point.  If this entry is taken as a delimiter, we now
 *	have three chunks:  the first half, the middle guy, and the
 *	second half.  We will move the second half to a new DIRBLK
 *	which we will allocate as close to ourselves as we can.  The
 *	first half stays where it is, possibly getting the middle
 *	entry's downpointer tacked onto its END record.  The middle
 *	entry is placed in a scratch buffer, so that it can be promoted
 *	into the parent block.
 *
 *	chk_split_dir (block, hdr, buffer)
 *
 *	ENTRY		block  - pointer to DIRBLK to split
 *			hdr    - buffer header for DIRBLK
 *			buffer - buffer to store middle DIRENT in
 *
 *	EXIT		Returns pointer to second half of DIRBLK,
 *			NULL if no disk space available
 *
 *	CALLS		allocate_dirblk
 *			allocate_near
 *			write_scratch
 *
 *	EFFECTS		Splits a directory block
 *			Allocates and deallocates memory
 */
 DIRBLK *chk_split_dir (block, hdr, buffer)
   DIRBLK *block;
   BUFNODE *hdr;
  UCHAR *buffer;
{
   DIRBLK *db;
   BUFNODE *hdr1;
  ULONG lsn, fre, down;
  union dp dp, dp2, dp3;
  UCHAR *mid;

  if (!(lsn=chk_write_data (block->lsnParent, block, SECTORS_PER_DIRBLK, TRUE)))
    return (NULL);				/* can't split if no space */

  /*
   *  Read the dirblk for the second half now;	this way, if
   *  the read fails, we don't have to back out so far.
   */
  db = (DIRBLK *)readbuf (lsn, &hdr1);

  if( db == NULL )
      return( NULL );

  hdr1->cusHolds++;			  /* hold that block */

  use_sectors (lsn, (ULONG)SECTORS_PER_DIRBLK, DISK_DIRBLK);

  dp.p = DIR_START (*block);
  mid = dp.p + (block->offulFirstFree >> 1);		/* mark halfway point */
  for (dp2.p = dp.p; dp2.p+dp2.d->cchThisEntry <= mid; dp2.p += dp2.d->cchThisEntry)
    ;

/*
 * Now dp2 points to the record to be promoted
 */

  memcpy (buffer, dp2.p, dp2.d->cchThisEntry);	/* copy middle record */
  fre = block->offulFirstFree;			/* get end pointer */
  block->offulFirstFree = dp2.p - (UCHAR *)block;	/* store new end ptr */
  fre -= block->offulFirstFree + dp2.d->cchThisEntry;	/* get length of second half */
  block->offulFirstFree += sizeof ( DIRENT);	  /* first half plus new end rec */
  dp3.p = dp2.p + dp2.d->cchThisEntry;		/* point to start of 2nd 1/2 */

/* Now we can set up a new end record for the first half.  We haven't
 * yet moved the second half somewhere;	 that's okay, since the end
 * record has no name and is therefore as small as a DIRENT can be;
 * copying one in cannot damage records other than the one we're
 * overlaying, which we've already copied into the holding buffer.
 */

  block->culChange += 2;			/* this dirblk has changed */
  dp.p = buffer;			/* point to the promoted entry */
  down = DOWN_PTR (dp);			/* get his downpointer */
  if (dp.d->fFlags & DF_BTP) {	      /* promoted guy had a downpointer */
    dp2.d->cchThisEntry = sizeof ( DIRENT) + 4;	  /* minimal DIRENT size */
    DOWN_PTR (dp2) = down;		/* set new end record's downpointer */
    dp2.d->fFlags = DF_END | DF_BTP;  /* this is the end with a downptr */
    dp2.d->fAttr  = 0;
    block->offulFirstFree += sizeof (long);	/* calc above didn't count downptr */
  }

/*** spd10: ***/

  else {				/* promoted guy had no downpointer */
    dp.d->cchThisEntry += sizeof (long);	/* he gets one now, so he's longer */
    dp.d->fFlags |= DF_BTP;	      /* show downpointer in flags */
    dp2.d->cchThisEntry = sizeof ( DIRENT);	  /* remove downptr from dp2 */
    dp2.d->fFlags = DF_END;	      /* this is the end with no downptr */
    dp2.d->fAttr  = 0;
  }
  DOWN_PTR (dp) = block->lsnThisDir;	/* set new downpointer */

/*** spd20: ***/

  dp2.d->cchName   = 1;		    /* end rec has a 1 char name */
  dp2.d->bName[0]  = 0xff;	    /* special end marker */
  dp2.d->bCodePage = 0;		    /* use default codepage */

  hdr->cusHolds++;		    /* hold top half */
  hdr->bDirtMask = TRUE;	    /* mark it dirty */

/* We have edited the first half of the DIRBLK.  We allocated
 * one for the second half earlier;  let's fill it in.
 */

  db->sig = DBSIGVAL;			/* set signature */
  db->offulFirstFree = 20 + fre;	/* length of 2nd half plus DB hdr */
  db->culChange = 0;			/* this block is NOT topmost */
  db->lsnParent = block->lsnParent;	/* parent is 1st half's parent */
  db->lsnThisDir = lsn;			/* this block's sector number */
  memcpy (DIR_START (*db), dp3.p, (USHORT)fre); /* copy in 2nd half */
  hdr1->bDirtMask = TRUE;
  return (db);				/* return pointer to new block */
}

/***	chk_add_dirent - insert a directory entry into a directory
 *
 *	This function is called both to create new files to recover
 *	lost data and to resort a corrupt directory.  It is passed
 *	a DIRENT structure and a memory image of the top level DIRBLK
 *	of a directory to insert the record into.  The DIRENT is
 *	inserted in lexical order into the BTREE, splitting if needed.
 *
 *	The algorithm used is a translation of the file system's LDE().
 *
 *	An error code will be returned if the entry cannot be inserted
 *	or if there is already an entry with the same name.
 *
 *	This function allocates a couple of scratch buffers on the stack.
 *	That's okay -- we're not deep inside function calls, this one's
 *	not recursive, and because other functions in CHKDSK *are*
 *	recursive, we've got lots of stack available.
 *
 *	chk_add_dirent (d, mem)
 *
 *	ENTRY		d   - pointer to DIRENT to insert
 *			mem - memory image of root of directory to insert into
 *
 *	EXIT		Returns zero if success, 1 if entry already exists,
 *			2 if no disk space available or read error
 *
 *	CALLS		allocate_near
 *			chk_find_ip
 *			chk_makeroom
 *			chk_namcmp
 *			read_scratch
 *			chk_split_dir
 *			write_scratch
 *
 *	EFFECTS		Inserts directory entry
 *			Allocates and deallocates memory
 */
USHORT chk_add_dirent (d, mem)
   DIRENT *d;
   DIRBLK *mem;
{
  union dp dp, dp2;
  UCHAR buf [MAX_NAME_LEN+sizeof ( DIRENT)+8]; /* max. size of a DIRENT */
  UCHAR *bufptr;			/* which buf/buf2 we're using */
  short i;
  ULONG lowlsn, highlsn, sect;
   DIRBLK *db_a, *db_b, *db;
   BUFNODE *hdr1, *hdr2;

  db_a = ( DIRBLK *)readbuf (mem->lsnThisDir, &hdr1);

  if( db_a == NULL ) {

    /*
     *	readbuf failed--either we've gotten a read fault or we've
     *	exhausted the cache.  In either case, we return the error.
     *
     *	The dirent we were adding becomes an instant orphan, and
     *	will have to be reclaimed by a future invocation of chkdsk.
     */
    return(2);
  }

  dp.p = DIR_START (*db_a);

/*** lde12: ***/

  while (TRUE) {

#ifdef DEBUG
    if (dp.d->cchThisEntry == 0) {
	   fprintf (stderr, "*** chk_add_dirent: looping forever ***\n");
	   fflush (stderr);
	   DOSBEEP
	   return (1);
	}
#endif

#ifndef PAWa
    i = memcmp (d->bName, dp.d->bName, d->cchName);
#else
    i = (dp.d->fFlags & DF_END)?-1:chk_strnicmp (d->bName,
		   d->bCodePage, dp.d->bName, dp.d->bCodePage, d->cchName);
#endif

    if (i > 0) {			/* new name > found name - not done */
      GETNEXT_ENTRY (dp);		   /* this is at lde10: in ASM */
      continue;				/* try the next name */
    }
    else if (!i) {			/* exact match! */
      if (d->cchName > dp.d->cchName) { /* spurious match */
	GETNEXT_ENTRY (dp);		   /* go to next entry */
	continue;
      }
      else if (d->cchName == dp.d->cchName)	/* a real match */
	return (1);			/* return error */
    }

/*
 * It looks like the string we found was greater than our new one,
 * which means we're done looking.  However, if the string we found
 * is shorter than the new one, we may have had a spurious "greater"
 * compare, so in that case we have to keep looking.
 */

    if ((dp.d->cchName < d->cchName) &&
#ifndef PAWa
	(memcmp (d->bName, dp.d->bName, dp.d->cchName) >= 0)) {
#else
	((((dp.d->fFlags & DF_END)?-1:chk_strnicmp (d->bName,
		     d->bCodePage, dp.d->bName,
		     dp.d->bCodePage, dp.d->cchName)) >= 0))) {
#endif

      GETNEXT_ENTRY (dp);
      continue;
    }

/*** lde24: ***/

    if (!(dp.d->fFlags & DF_BTP))     /* no btree pointer, item missing */
      break;				/* stop searching */

    else {				/* have a btree pointer - descend */
      sect = DOWN_PTR (dp);		/* get pointer */
      db_a = ( DIRBLK *)readbuf (sect, &hdr1);	  /* read descendant */

      if( db_a == NULL ) {
	return(2);
      }

      dp.p = DIR_START (*db_a);
      continue;				/* start searching child block */
    }
  }

/*** lde100: ***/
/* Entry not found.  That's good, since we're inserting a new entry.
 * We need to insert our entry in this block somewhere;	 first let's
 * see if we have room left in this block for it.  If not, we'll have
 * to split it.
 */

  if (chk_makeroom (d->cchThisEntry, db_a, dp.p)) { /* made room -- copy in */
    memcpy (dp.p, (UCHAR *)d, d->cchThisEntry);	/* copy our DIRENT in */
    hdr1->bDirtMask = TRUE;				/* mark him dirty */
    wipecache ();				/* flush the cache */
    read_scratch (mem->lsnThisDir, mem, SECTORS_PER_DIRBLK); /* reread mem image */
    return (0);					/* all done! */
  }

/*** lde150: ***/
/* Rats.  We didn't have room for the entry in this block.
 * We'll have to split it and put the entry in a child.
 */

  db_b = chk_split_dir (db_a, hdr1, buf);	/* split the DIRBLK */
  if (!db_b)					/* can't split */
    return (2);					/* tell caller no space left */

/* We split the DIRBLK.  Now we need to insert our new DIRENT
 * in the correct half of the subtree.
 */

  dp2.p = buf;					/* point to the promoted guy */
  db = (chk_namcmp (d->bName, d->bCodePage, dp2.d, d->cchThisEntry)) ?
       db_a :			/* insert < middle guy - put in first half */
       db_b;			/* insert > middle guy - put in second half */

/*** lde160: ***/
/* Now scan the half we want, looking for an insertion point.
 * db points to the DIRBLK we want.
 */

  dp2.p = DIR_START (*db);		/* point to the first entry */
  while (!chk_namcmp (d->bName, d->bCodePage, dp2.d, d->cchThisEntry))
    GETNEXT_ENTRY (dp2);

/*** lde165: ***/
/* We've found our spot.  Move everyone over to make room.
 * We got big problems if we still can't make room -- in that case,
 * we chuck all our changes (wipe the cache without flushing) and
 * return failure.
 */

  if (!chk_makeroom (d->cchThisEntry, db, dp2.p)) { /* make room for our DIRENT */
    for (i=0; i<CACHESIZE; i++) {
      sect = chk_cache [i].pblkData;
      memset (&chk_cache [i], '\0', sizeof ( BUFNODE));
      chk_cache [i].pblkData = sect;
    }
    return (2);					/* no room - bad error */
  }

  memcpy (dp2.p, (UCHAR *)d, d->cchThisEntry);	/* copy our DIRENT in */
  hdr2 = _adr_to_bhdr (db);
  hdr2->bDirtMask = TRUE;
  hdr2->cusHolds++;

/*** lde180: ***/
/* Okay, we inserted our DIRENT.  Now we need to promote that
 * middle guy that came out of the split.  This means finding
 * someplace to insert him -- which may cause further splits.
 */

  bufptr = buf;					/* we're using buf first */
  while (TRUE) {				/* we'll break out manually */
    lowlsn = db_a->lsnThisDir;			/* get sector # of lower half */
    highlsn = db_b->lsnThisDir;			/* get sector # of upper half */
    i = (USHORT)(db_a->culChange & 1);		/* test the "topmost" flag */
    db_a->culChange &= ~1;			/* and clear it */
    if (i)					/* we're topmost already */
      break;					/* get out right now */

    hdr2 = _adr_to_bhdr (db_a);			/* unhold the sub-blocks */
    hdr2->cusHolds--;
    hdr2 = _adr_to_bhdr (db_b);
    hdr2->cusHolds--;

    db_a = ( DIRBLK *)readbuf (db_a->lsnParent, &hdr1); /* read parent */
    if( db_a == NULL ) {
	return(2);
    }
    hdr1->cusHolds++;				/* hold the parent block */

    if (!chk_find_ip (db_a, lowlsn, &dp.p)) {	/* find downpointer in parent */
      for (i=0; i<CACHESIZE; i++) {
	sect = chk_cache [i].pblkData;
	memset (&chk_cache [i], '\0', sizeof ( BUFNODE));
	chk_cache [i].pblkData = sect;
      }
      return (2);				/* yikes!  it's not there! */
    }

/*
 * Make room for the promoted entry.  If there's room, copy him in.
 * Split_dir set his downpointer to point to the first half of the split.
 * The entry we're inserting the promotent before used to point to the
 * DIRBLK that we split.  We change his downpointer to point to the
 * second half of the split.
 */

    dp2.p = buf;
    if (chk_makeroom (dp2.d->cchThisEntry, db_a, dp.p)) { /* make room for middle guy */
      memcpy (dp.p, dp2.p, dp2.d->cchThisEntry);	/* copy promoted guy */
      GETNEXT_ENTRY (dp);			   /* move to following guy */
      DOWN_PTR (dp) = highlsn;			/* was splt blk, now lwr half */
      hdr1->bDirtMask = TRUE;			/* mark DIRBLK dirty */
      hdr1->cusHolds--;				/* unhold him */
      wipecache ();				/* flush changes to disk */
      read_scratch (mem->lsnThisDir, mem, SECTORS_PER_DIRBLK); /* reread mem image */
      return (0);				/* we created him! */
    }

/*** lde200: ***/
/* Not fun.  After splitting the DIRBLK, the guy we promoted
 * is too big to fit in the parent block.  We have to split
 * the parent and promote an entry out of it, etc...
 */

    insert (db_a, hdr1, ( DIRENT *)buf, highlsn); /* insert the entry */
    hdr1->cusHolds--;				/* unhold the block */
    hdr1->bDirtMask = TRUE;				/* it's very dirty now */
    wipecache ();				/* flush changes to disk */
    read_scratch (mem->lsnThisDir, mem, SECTORS_PER_DIRBLK); /* reread mem image */
    return (0);					/* success! */
  }

/*** lde300: ***/
/* We've split all the way to the topmost block, so we need to
 * add a brand-new DIRBLK to the tree, at the top.  We create
 * a minimal block with two downpointers and the promoted record.
 * We also need to adjust the FNODE to point to this guy instead
 * of the old tree root.
 */

  NewDirRoot (( DIRENT *)buf, db_a, db_b, &hdr2, &db);
  hdr1->bDirtMask = TRUE;			/* mark both dirty, just in case */
  hdr2->bDirtMask = TRUE;
  hdr1->cusHolds = hdr2->cusHolds = 0;	/* unhold the buffers */

  wipecache ();				/* flush all our changes to disk */
  read_scratch (mem->lsnThisDir, mem, SECTORS_PER_DIRBLK); /* reread mem image */
  return (0);				/* All done!  WHEW! */
}
