--- ray/src/hd/holofile.c	1997/12/12 21:29:34	3.13
+++ ray/src/hd/holofile.c	1997/12/29 15:17:45	3.15
@@ -21,9 +21,10 @@ static char SCCSid[] = "$SunId$ SGI";
 #ifndef PCTFREE
 #define PCTFREE		20	/* maximum fraction to free (%) */
 #endif
+#ifndef MAXFRAG
+#define MAXFRAG		131000	/* maximum fragments/file to track (0==inf) */
+#endif
 
-/* define MAXFRAG if you want to limit fragment tracking memory */
-
 #ifndef BSD
 #define write	writebuf	/* safe i/o routines */
 #define read	readbuf
@@ -31,7 +32,7 @@ static char SCCSid[] = "$SunId$ SGI";
 
 #define FRAGBLK		64	/* number of fragments to allocate at a time */
 
-int	hdcachesize = CACHESIZE*1024*1024;	/* target cache size (bytes) */
+unsigned	hdcachesize = CACHESIZE*1024*1024;	/* target cache size */
 unsigned long	hdclock;	/* clock value */
 
 HOLO	*hdlist[HDMAX+1];	/* holodeck pointers (NULL term.) */
@@ -177,7 +178,7 @@ int	all;
 		return(n);
 	}
 					/* sync the beams */
-	for (j = all ? nbeams(hp) : 0; j > 0; j--)
+	for (j = (all ? nbeams(hp) : 0); j > 0; j--)
 		if (hp->bl[j] != NULL)
 			hdsyncbeam(hp, j);
 	if (!hp->dirty)			/* directory clean? */
@@ -193,7 +194,7 @@ int	all;
 }
 
 
-long
+unsigned
 hdmemuse(all)		/* return memory usage (in bytes) */
 int	all;			/* include overhead (painful) */
 {
@@ -308,8 +309,8 @@ int	nr;			/* number of new rays desired */
 	p = hdbray(hp->bl[i]) + hp->bl[i]->nrm;
 	hp->bl[i]->nrm += nr;			/* update in-core structure */
 	bzero((char *)p, nr*sizeof(RAYVAL));
-	hp->bl[i]->tick = ++hdclock;		/* update LRU clock */
-	blglob(hp)->tick = hdclock;
+	hp->bl[i]->tick = hdclock;		/* update LRU clock */
+	blglob(hp)->tick = hdclock++;
 	return(p);				/* point to new rays */
 memerr:
 	error(SYSTEM, "out of memory in hdnewrays");
@@ -340,13 +341,67 @@ register int	i;
 		if (read(hp->fd, (char *)hdbray(hp->bl[i]), n) != n)
 			error(SYSTEM, "error reading beam from holodeck file");
 	}
-	hp->bl[i]->tick = ++hdclock;	/* update LRU clock */
-	blglob(hp)->tick = hdclock;
+	hp->bl[i]->tick = hdclock;	/* update LRU clock */
+	blglob(hp)->tick = hdclock++;
 	return(hp->bl[i]);
 }
 
 
 int
+hdfilord(hb1, hb2)	/* order beams for optimal loading */
+register HDBEAMI	*hb1, *hb2;
+{
+	register int	c;
+				/* sort by file descriptor first */
+	if ((c = hb1->h->fd - hb2->h->fd))
+		return(c);
+				/* then by position in file */
+	return(hb1->h->bi[hb1->b].fo - hb2->h->bi[hb2->b].fo);
+}
+
+
+hdloadbeams(hb, n, bf)	/* load a list of beams in optimal order */
+register HDBEAMI	*hb;	/* list gets sorted by hdfilord() */
+int	n;			/* list length */
+int	(*bf)();		/* callback function (optional) */
+{
+	unsigned	origcachesize, memuse;
+	register BEAM	*bp;
+	int	bytesloaded, needbytes, bytes2free;
+	register int	i;
+					/* precheck consistency */
+	for (i = n; i--; )
+		if (hb[i].h == NULL || hb[i].b < 1 | hb[i].b > nbeams(hb[i].h))
+			error(CONSISTENCY, "bad beam in hdloadbeams");
+					/* sort list for optimal access */
+	qsort((char *)hb, n, sizeof(HDBEAMI), hdfilord);
+	bytesloaded = needbytes = 0;	/* figure out memory needs */
+	if ((origcachesize = hdcachesize) > 0) {
+		for (i = n; i--; )
+			if ((bp = hb[i].h->bl[hb[i].b]) != NULL) {
+				bp->tick = hdclock;	/* preempt swap */
+				bytesloaded += bp->nrm;
+			} else				/* prepare to load */
+				needbytes += hb[i].h->bi[hb[i].b].nrd;
+		bytesloaded *= sizeof(RAYVAL);
+		needbytes *= sizeof(RAYVAL);
+		do {				/* free enough memory */
+			memuse = hdmemuse(0);
+			bytes2free = needbytes - (signed)(hdcachesize-memuse);
+			if (bytes2free > (signed)(memuse - bytesloaded))
+				bytes2free = memuse - bytesloaded;
+		} while (bytes2free > 0 &&
+				hdfreecache(100*bytes2free/memuse, NULL) < 0);
+	}
+	hdcachesize = 0;		/* load the ordered beams w/o swap */
+	for (i = 0; i < n; i++)
+		if ((bp = hdgetbeam(hb[i].h, hb[i].b)) != NULL && bf != NULL)
+			(*bf)(bp, hb[i].h, hb[i].b);
+	hdcachesize = origcachesize;	/* resume dynamic swapping */
+}
+
+
+int
 hdsyncbeam(hp, i)		/* sync beam in memory with beam on disk */
 register HOLO	*hp;
 register int	i;
@@ -378,7 +433,7 @@ register int	i;
 					/* relinquish old fragment */
 		if (hp->bi[i].nrd) {
 			j = f->nfrags++;
-#ifdef MAXFRAG
+#if MAXFRAG
 			if (j >= MAXFRAG-1)
 				f->nfrags--;
 #endif
@@ -399,24 +454,22 @@ register int	i;
 					f->fi[j].nrd = hp->bi[i].nrd;
 					break;
 				}
-				copystruct(f->fi+j, f->fi+j-1);
+				copystruct(f->fi+j, f->fi+(j-1));
 			}
 					/* coalesce adjacent fragments */
-			for (j = k = 0; k < f->nfrags; j++, k++) {
-				if (k > j)
-					copystruct(f->fi+j, f->fi+k);
-				while (k+1 < f->nfrags && f->fi[k+1].fo +
-						f->fi[k+1].nrd*sizeof(RAYVAL)
-							== f->fi[j].fo) {
-					f->fi[j].fo -=
-						f->fi[++k].nrd*sizeof(RAYVAL);
-					f->fi[j].nrd += f->fi[k].nrd;
-				}
+			if (j && f->fi[j-1].fo == f->fi[j].fo +
+					f->fi[j].nrd*sizeof(RAYVAL)) {
+				f->fi[j].nrd += f->fi[j-1].nrd;
+				f->fi[j-1].nrd = 0;
 			}
-			f->nfrags = j;
+			if (j+1 < f->nfrags && f->fi[j].fo == f->fi[j+1].fo +
+					f->fi[j+1].nrd*sizeof(RAYVAL)) {
+				f->fi[j+1].nrd += f->fi[j].nrd;
+				f->fi[j].nrd = 0;
+			}
 		}
 		k = -1;			/* find closest-sized fragment */
-		for (j = nrays ? f->nfrags : 0; j-- > 0; )
+		for (j = (nrays ? f->nfrags : 0); j-- > 0; )
 			if (f->fi[j].nrd >= nrays &&
 					(k < 0 || f->fi[j].nrd < f->fi[k].nrd))
 				if (f->fi[k=j].nrd == nrays)
@@ -426,15 +479,19 @@ register int	i;
 			f->flen += nrays*sizeof(RAYVAL);
 		} else {		/* else use fragment */
 			nfo = f->fi[k].fo;
-			if (f->fi[k].nrd == nrays) {	/* delete fragment */
-				f->nfrags--;
-				for (j = k; j < f->nfrags; j++)
-					copystruct(f->fi+j, f->fi+j+1);
-			} else {			/* else shrink it */
-				f->fi[k].fo += nrays*sizeof(RAYVAL);
-				f->fi[k].nrd -= nrays;
-			}
+			f->fi[k].fo += nrays*sizeof(RAYVAL);
+			f->fi[k].nrd -= nrays;
 		}
+					/* delete empty remnants */
+		for (j = k = 0; k < f->nfrags; j++, k++) {
+			while (f->fi[k].nrd == 0)
+				if (++k >= f->nfrags)
+					goto endloop;
+			if (k > j)
+				copystruct(f->fi+j, f->fi+k);
+		}
+	endloop:
+		f->nfrags = j;
 	}
 	if (nrays) {		/* write the new fragment */
 		errno = 0;
@@ -537,67 +594,68 @@ register int	i;
 }
 
 
-hdlrulist(ha, ba, n, hp)	/* add beams from holodeck to LRU list */
-register HOLO	*ha[];			/* section list (NULL terminated) */
-register int	ba[];			/* beam index to go with section */
-int	n;				/* length of arrays minus 1 */
+int
+hdlrulist(hb, nents, n, hp)	/* add beams from holodeck to LRU list */
+register HDBEAMI	*hb;		/* beam list */
+int	nents;				/* current list length */
+int	n;				/* maximum list length */
 register HOLO	*hp;			/* section we're adding from */
 {
 	register int	i, j;
-	int	nents;
-					/* find last entry in LRU list */
-	for (j = 0; ha[j] != NULL; j++)
-		;
-	nents = j;
 					/* insert each beam from hp */
 	for (i = nbeams(hp); i > 0; i--) {
 		if (hp->bl[i] == NULL)		/* check if loaded */
 			continue;
-		if ((j = ++nents) > n)		/* grow list if we can */
+#if 0
+		if (hp->bl[i]->tick == hdclock)	/* preempt swap? */
+			continue;
+#endif
+		if ((j = ++nents) >= n)		/* grow list if we can */
 			nents--;
 		for ( ; ; ) {			/* bubble into place */
 			if (!--j || hp->bl[i]->tick >=
-					ha[j-1]->bl[ba[j-1]]->tick) {
-				ha[j] = hp;
-				ba[j] = i;
+					hb[j-1].h->bl[hb[j-1].b]->tick) {
+				hb[j].h = hp;
+				hb[j].b = i;
 				break;
 			}
-			ha[j] = ha[j-1];
-			ba[j] = ba[j-1];
+			copystruct(hb+j, hb+(j-1));
 		}
 	}
-	ha[nents] = NULL;		/* all done */
-	ba[nents] = 0;
+	return(nents);			/* return new list length */
 }
 
 
+int
 hdfreecache(pct, honly)		/* free up cache space, writing changes */
 int	pct;				/* maximum percentage to free */
 register HOLO	*honly;			/* NULL means check all */
 {
-	HOLO	*hp[FREEBEAMS+1];
-	int	bn[FREEBEAMS+1];
+	HDBEAMI	hb[FREEBEAMS];
 	int	freetarget;
+	int	n;
 	register int	i;
 						/* compute free target */
 	freetarget = (honly != NULL) ? blglob(honly)->nrm :
 			hdmemuse(0)/sizeof(RAYVAL) ;
 	freetarget = freetarget*pct/100;
+	if (freetarget <= 0)
+		return(0);
 						/* find least recently used */
-	hp[0] = NULL;
-	bn[0] = 0;
+	n = 0;
 	if (honly != NULL)
-		hdlrulist(hp, bn, FREEBEAMS, honly);
+		n = hdlrulist(hb, n, FREEBEAMS, honly);
 	else
 		for (i = 0; hdlist[i] != NULL; i++)
-			hdlrulist(hp, bn, FREEBEAMS, hdlist[i]);
+			n = hdlrulist(hb, n, FREEBEAMS, hdlist[i]);
 						/* free LRU beams */
-	for (i = 0; hp[i] != NULL; i++) {
-		hdfreebeam(hp[i], bn[i]);
-		if ((freetarget -= hp[i]->bi[bn[i]].nrd) <= 0)
+	for (i = 0; i < n; i++) {
+		hdfreebeam(hb[i].h, hb[i].b);
+		if ((freetarget -= hb[i].h->bi[hb[i].b].nrd) <= 0)
 			break;
 	}
 	hdsync(honly, 0);	/* synchronize directories as necessary */
+	return(-freetarget);	/* return how far past goal we went */
 }