--- ray/src/util/glareval.c	1991/03/18 12:15:41	1.1
+++ ray/src/util/glareval.c	1991/04/05 14:57:28	1.11
@@ -20,7 +20,9 @@ static char SCCSid[] = "$SunId$ LBL";
 #define vfork		fork
 #endif
 
-#define NSCANS		16		/* number of scanlines to buffer */
+#define MAXSBUF		524268	/* maximum total size of scanline buffer */
+#define HSIZE		317	/* size of scanline hash table */
+#define NRETIRE		16	/* number of scanlines to retire at once */
 
 int	rt_pid = -1;		/* process id for rtrace */
 int	fd_tort, fd_fromrt;	/* pipe descriptors */
@@ -28,63 +30,131 @@ int	fd_tort, fd_fromrt;	/* pipe descriptors */
 FILE	*pictfp = NULL;		/* picture file pointer */
 double	exposure;		/* picture exposure */
 int	pxsiz, pysiz;		/* picture dimensions */
-int	curpos;			/* current scanline */
-long	*scanpos;		/* scanline positions */
-struct {
-	long	lused;		/* for LRU replacement */
+
+static int	curpos;		/* current scanline */
+static long	*scanpos;	/* scanline positions */
+
+typedef struct scan {
 	int	y;		/* scanline position */
-	COLR	*sl;		/* scanline contents */
-} scan[NSCANS];		/* buffered scanlines */
+	long	lused;		/* for LRU replacement */
+	struct scan	*next;	/* next in this hash or free list */
+	/* followed by the scanline data */
+} SCAN;			/* buffered scanline */
 
+#define	scandata(sl)	((COLR *)((sl)+1))
+#define shash(y)	((y)%HSIZE)
 
+static SCAN	*freelist;		/* scanline free list */
+static SCAN	*hashtab[HSIZE];	/* scanline hash table */
+
+static long	ncall = 0L;	/* number of calls to getpictscan */
+static long	nread = 0L;	/* number of scanlines read */
+
+SCAN	*scanretire();
+
+extern long	ftell();
+
+
+SCAN *
+claimscan(y)			/* claim scanline from buffers */
+int	y;
+{
+	int	hi = shash(y);
+	SCAN	*slast;
+	register SCAN	*sl;
+
+	for (sl = hashtab[hi]; sl != NULL; sl = sl->next)
+		if (sl->y == y)				/* active scanline */
+			return(sl);
+	for (slast = NULL, sl = freelist; sl != NULL; slast = sl, sl = sl->next)
+		if (sl->y == -1 || sl->y == y || sl->next == NULL) {
+			if (slast == NULL)		/* remove from free */
+				freelist = sl->next;
+			else
+				slast->next = sl->next;
+			if (sl->y == y) {		/* reclaim */
+				sl->next = hashtab[hi];
+				hashtab[hi] = sl;
+#ifdef DEBUG
+				if (verbose)
+					fprintf(stderr,
+						"%s: scanline %d reclaimed\n",
+							progname, y);
+#endif
+			}
+			return(sl);
+		}
+	return(scanretire());		/* need more free scanlines */
+}
+
+
 COLR *
 getpictscan(y)			/* get picture scanline */
 int	y;
 {
-	extern long	ftell();
-	static long	ncall = 0;
-	int	minused;
+	register SCAN	*sl;
 	register int	i;
 					/* first check our buffers */
-	ncall++;
-	minused = 0;
-	for (i = 0; i < NSCANS; i++) {
-		if (scan[i].y == y) {
-			scan[i].lused = ncall;
-			return(scan[i].sl);
-		}
-		if (scan[i].lused < scan[minused].lused)
-			minused = i;
-	}
-					/* not there, read it in */
-	if (scanpos[y] == -1) {			/* need to search */
-		if (verbose)
-			fprintf(stderr, "%s: reading picture...\n",
-					progname);
-		while (curpos > y) {
+	sl = claimscan(y);
+	if (sl == NULL)
+		memerr("claimscan()");
+	sl->lused = ncall++;
+	if (sl->y == y)			/* scan hit */
+		return(scandata(sl));
+					/* else read in replacement */
+	if (scanpos[y] < 0) {			/* need to search */
+		for (i = y+1; i < curpos; i++)
+			if (scanpos[i] >= 0) {
+				if (fseek(pictfp, scanpos[i], 0) < 0)
+					goto seekerr;
+				curpos = i;
+				break;
+			}
+		while (curpos >= y) {
 			scanpos[curpos] = ftell(pictfp);
-			if (freadcolrs(scan[minused].sl, pxsiz, pictfp) < 0)
+			if (freadcolrs(scandata(sl), pxsiz, pictfp) < 0)
 				goto readerr;
+			nread++;
 			curpos--;
 		}
-	} else if (fseek(pictfp, scanpos[y], 0) < 0) {
-		fprintf(stderr, "%s: picture seek error\n", progname);
-		exit(1);
+	} else {
+		if (curpos != y && fseek(pictfp, scanpos[y], 0) < 0)
+			goto seekerr;
+		if (freadcolrs(scandata(sl), pxsiz, pictfp) < 0)
+			goto readerr;
+		nread++;
+		curpos = y-1;
 	}
-	if (verbose)
-		fprintf(stderr, "%s: reading scanline %d...\n", progname, y);
-	if (freadcolrs(scan[minused].sl, pxsiz, pictfp) < 0)
-		goto readerr;
-	curpos = y-1;
-	scan[minused].lused = ncall;
-	scan[minused].y = y;
-	return(scan[minused].sl);
+	sl->y = y;
+	i = shash(y);			/* add to hash list */
+	sl->next = hashtab[i];
+	hashtab[i] = sl;
+	return(scandata(sl));
 readerr:
 	fprintf(stderr, "%s: picture read error\n", progname);
 	exit(1);
+seekerr:
+	fprintf(stderr, "%s: picture seek error\n", progname);
+	exit(1);
 }
 
 
+#ifdef DEBUG
+pict_stats()			/* print out picture read statistics */
+{
+	static long	lastcall = 0L;	/* ncall at last report */
+	static long	lastread = 0L;	/* nread at last report */
+
+	if (ncall == lastcall)
+		return;
+	fprintf(stderr, "%s: %ld scanlines read in %ld calls\n",
+			progname, nread-lastread, ncall-lastcall);
+	lastcall = ncall;
+	lastread = nread;
+}
+#endif
+
+
 double
 pict_val(vd)			/* find picture value for view direction */
 FVECT	vd;
@@ -116,10 +186,13 @@ int	vh, vv;
 
 	if (compdir(dir, vh, vv) < 0)
 		return(-1.0);
+	npixinvw++;
 	if ((res = pict_val(dir)) >= 0.0)
 		return(res);
-	if (rt_pid == -1)
+	if (rt_pid == -1) {
+		npixmiss++;
 		return(-1.0);
+	}
 	rt_buf[0] = ourview.vp[0];
 	rt_buf[1] = ourview.vp[1];
 	rt_buf[2] = ourview.vp[2];
@@ -136,44 +209,51 @@ int	vv;
 float	*vb;
 {
 	float	rt_buf[6*MAXPIX];	/* rtrace send/receive buffer */
-	int	npix_tort;		/* number of pixels in buffer */
+	register int	n;		/* number of pixels in buffer */
 	short	buf_vh[MAXPIX];		/* pixel positions */
 	FVECT	dir;
 	register int	vh;
-	register int	i;
 
+#ifdef DEBUG
 	if (verbose)
 		fprintf(stderr, "%s: computing view span at %d...\n",
 				progname, vv);
-	npix_tort = 0;
+#endif
+	n = 0;
 	for (vh = -hsize; vh <= hsize; vh++) {
 		if (compdir(dir, vh, vv) < 0) {	/* off viewable region */
 			vb[vh+hsize] = -1.0;
 			continue;
 		}
+		npixinvw++;
 		if ((vb[vh+hsize] = pict_val(dir)) >= 0.0)
 			continue;
-		if (rt_pid == -1)		/* missing information */
+		if (rt_pid == -1) {		/* missing information */
+			npixmiss++;
 			continue;
+		}
 						/* send to rtrace */
-		if (npix_tort >= MAXPIX) {		/* flush */
-			rt_compute(rt_buf, npix_tort);
-			for (i = 0; i < npix_tort; i++)
-				vb[buf_vh[i]+hsize] = luminance(rt_buf+3*i);
-			npix_tort = 0;
+		if (n >= MAXPIX) {			/* flush */
+			rt_compute(rt_buf, n);
+			while (n-- > 0)
+				vb[buf_vh[n]+hsize] = luminance(rt_buf+3*n);
 		}
-		rt_buf[npix_tort] = ourview.vp[0];
-		rt_buf[npix_tort+1] = ourview.vp[1];
-		rt_buf[npix_tort+2] = ourview.vp[2];
-		rt_buf[npix_tort+3] = dir[0];
-		rt_buf[npix_tort+4] = dir[1];
-		rt_buf[npix_tort+5] = dir[2];
-		buf_vh[npix_tort++] = vh;
+		rt_buf[6*n] = ourview.vp[0];
+		rt_buf[6*n+1] = ourview.vp[1];
+		rt_buf[6*n+2] = ourview.vp[2];
+		rt_buf[6*n+3] = dir[0];
+		rt_buf[6*n+4] = dir[1];
+		rt_buf[6*n+5] = dir[2];
+		buf_vh[n++] = vh;
 	}
-	if (npix_tort > 0) {			/* process pending buffer */
-		rt_compute(rt_buf, npix_tort);
-		for (i = 0; i < npix_tort; i++)
-			vb[buf_vh[i]+hsize] = luminance(rt_buf+3*i);
+#ifdef DEBUG
+	if (verbose)
+		pict_stats();
+#endif
+	if (n > 0) {				/* process pending buffer */
+		rt_compute(rt_buf, n);
+		while (n-- > 0)
+			vb[buf_vh[n]+hsize] = luminance(rt_buf+3*n);
 	}
 }
 
@@ -184,9 +264,11 @@ int	np;
 {
 	static float	nbuf[6] = {0.,0.,0.,0.,0.,0.};
 
+#ifdef DEBUG
 	if (verbose && np > 1)
 		fprintf(stderr, "%s: sending %d samples to rtrace...\n",
 				progname, np);
+#endif
 	if (writebuf(fd_tort,(char *)pb,6*sizeof(float)*np) < 6*sizeof(float)*np
 		|| writebuf(fd_tort,(char *)nbuf,sizeof(nbuf)) < sizeof(nbuf)) {
 		fprintf(stderr, "%s: error writing to rtrace process\n",
@@ -225,19 +307,7 @@ char	*fn;
 		fprintf("%s: bad picture resolution\n", fn);
 		exit(1);
 	}
-	scanpos = (long *)malloc(pysiz*sizeof(long));
-	if (scanpos == NULL)
-		memerr("scanline positions");
-	for (i = 0; i < pysiz; i++)
-		scanpos[i] = -1L;
-	for (i = 0; i < NSCANS; i++) {
-		scan[i].lused = -1;
-		scan[i].y = -1;
-		scan[i].sl = (COLR *)malloc(pxsiz*sizeof(COLR));
-		if (scan[i].sl == NULL)
-			memerr("scanline buffers");
-	}
-	curpos = pysiz-1;
+	initscans();
 }
 
 
@@ -248,9 +318,7 @@ close_pict()			/* done with picture */
 	if (pictfp == NULL)
 		return;
 	fclose(pictfp);
-	free((char *)scanpos);
-	for (i = 0; i < NSCANS; i++)
-		free((char *)scan[i].sl);
+	donescans();
 	pictfp = NULL;
 }
 
@@ -283,6 +351,8 @@ char	*av[];
 		perror(progname);
 		exit(1);
 	}
+	close(p0[0]);
+	close(p1[1]);
 	fd_tort = p0[1];
 	fd_fromrt = p1[0];
 }
@@ -339,4 +409,93 @@ int	siz;
 	if (cc < 0)
 		return(cc);
 	return(siz-nrem);
+}
+
+
+SCAN *
+scanretire()			/* retire old scanlines to free list */
+{
+	SCAN	*sold[NRETIRE];
+	int	n;
+	int	h;
+	register SCAN	*sl;
+	register int	i;
+					/* grab the NRETIRE oldest scanlines */
+	sold[n = 0] = NULL;
+	for (h = 0; h < HSIZE; h++)
+		for (sl = hashtab[h]; sl != NULL; sl = sl->next) {
+			for (i = n; i && sold[i-1]->lused > sl->lused; i--)
+				if (i < NRETIRE)
+					sold[i] = sold[i-1];
+			if (i < NRETIRE) {
+				sold[i] = sl;
+				if (n < NRETIRE)	/* grow list */
+					n++;
+			}
+		}
+					/* put scanlines into free list */
+	for (i = 0; i < n; i++) {
+		h = shash(sold[i]->y);
+		sl = hashtab[h];
+		if (sl == sold[i])
+			hashtab[h] = sl->next;
+		else {
+			while (sl->next != sold[i])	/* IS in list */
+				sl = sl->next;
+			sl->next = sold[i]->next;
+		}
+		if (i > 0) {		/* save oldest as return value */
+			sold[i]->next = freelist;
+			freelist = sold[i];
+		}
+	}
+	return(sold[0]);
+}
+
+
+static char	*scan_buf;
+
+
+initscans()				/* initialize scanline buffers */
+{
+	int	scansize;
+	register SCAN	*ptr;
+	register int	i;
+					/* initialize positions */
+	scanpos = (long *)malloc(pysiz*sizeof(long));
+	if (scanpos == NULL)
+		memerr("scanline positions");
+	for (i = pysiz-1; i >= 0; i--)
+		scanpos[i] = -1L;
+	curpos = pysiz-1;
+					/* clear hash table */
+	for (i = 0; i < HSIZE; i++)
+		hashtab[i] = NULL;
+					/* allocate scanline buffers */
+	scansize = sizeof(SCAN) + pxsiz*sizeof(COLR);
+#ifdef ALIGN
+	scansize = scansize+(sizeof(ALIGN)-1)) & ~(sizeof(ALIGN)-1);
+#endif
+	i = MAXSBUF / scansize;		/* compute number to allocate */
+	if (i > HSIZE)
+		i = HSIZE;
+	scan_buf = malloc(i*scansize);	/* get in one big chunk */
+	if (scan_buf == NULL)
+		memerr("scanline buffers");
+	ptr = (SCAN *)scan_buf;
+	freelist = NULL;		/* build our free list */
+	while (i-- > 0) {
+		ptr->y = -1;
+		ptr->lused = -1;
+		ptr->next = freelist;
+		freelist = ptr;
+		ptr = (SCAN *)((char *)ptr + scansize);	/* beware of C bugs */
+	}
+}
+
+
+donescans()				/* free up scanlines */
+{
+	free(scan_buf);
+	free((char *)scanpos);
 }