--- ray/src/common/objset.c	1990/09/06 23:32:41	1.2
+++ ray/src/common/objset.c	2003/02/25 02:47:21	2.9
@@ -1,28 +1,32 @@
-/* Copyright (c) 1986 Regents of the University of California */
-
 #ifndef lint
-static char SCCSid[] = "$SunId$ LBL";
+static const char	RCSid[] = "$Id: objset.c,v 2.9 2003/02/25 02:47:21 greg Exp $";
 #endif
-
 /*
  *  objset.c - routines for maintaining object sets.
  *
- *	7/28/85
+ *  External symbols declared in object.h
  */
 
+#include "copyright.h"
+
 #include  "standard.h"
 
 #include  "octree.h"
 
 #include  "object.h"
 
-#include  "otypes.h"
+#ifndef  OSTSIZ
+#ifdef  BIGMEM
+#define  OSTSIZ		262139		/* object table size (a prime!) */
+#else
+#define  OSTSIZ		32749		/* object table size (a prime!) */
+#endif
+#endif
 
-#define  OSTSIZ		3037		/* object table size (a prime!) */
-
 static OBJECT  *ostable[OSTSIZ];	/* the object set table */
 
 
+void
 insertelem(os, obj)		/* insert obj into os, no questions */
 register OBJECT  *os;
 OBJECT  obj;
@@ -38,14 +42,19 @@ OBJECT  obj;
 }
 
 
+void
 deletelem(os, obj)		/* delete obj from os, no questions */
 register OBJECT  *os;
 OBJECT  obj;
 {
 	register int  i;
 
-	for (i = (*os++)--; i > 0 && *os < obj; i--, os++)
-		;
+	i = (*os)--;
+	os++;
+	while (i > 0 && *os < obj) {
+		i--;
+		os++;
+	}
 	while (--i > 0) {
 		os[0] = os[1];
 		os++;
@@ -53,6 +62,7 @@ OBJECT  obj;
 }
 
 
+int
 inset(os, obj)			/* determine if object is in set */
 register OBJECT  *os;
 OBJECT  obj;
@@ -60,9 +70,16 @@ OBJECT  obj;
 	int  upper, lower;
 	register int  cm, i;
 
+	if ((i = os[0]) <= 6) {		/* linear search algorithm */
+		cm = obj;
+		while (i-- > 0)
+			if (*++os == cm)
+				return(1);
+		return(0);
+	}
 	lower = 1;
-	upper = cm = os[0] + 1;
-
+	upper = cm = i + 1;
+					/* binary search algorithm */
 	while ((i = (lower + upper) >> 1) != cm) {
 		cm = obj - os[i];
 		if (cm > 0)
@@ -77,6 +94,7 @@ OBJECT  obj;
 }
 
 
+int
 setequal(os1, os2)		/* determine if two sets are equal */
 register OBJECT  *os1, *os2;
 {
@@ -89,6 +107,7 @@ register OBJECT  *os1, *os2;
 }
 
 
+void
 setcopy(os1, os2)		/* copy object set os2 into os1 */
 register OBJECT  *os1, *os2;
 {
@@ -99,6 +118,64 @@ register OBJECT  *os1, *os2;
 }
 
 
+OBJECT *
+setsave(os)			/* allocate space and save set */
+register OBJECT  *os;
+{
+	OBJECT  *osnew;
+	register OBJECT  *oset;
+	register int  i;
+
+	if ((osnew = oset = (OBJECT *)malloc((*os+1)*sizeof(OBJECT))) == NULL)
+		error(SYSTEM, "out of memory in setsave\n");
+	for (i = *os; i-- >= 0; )	/* inline setcopy */
+		*oset++ = *os++;
+	return(osnew);
+}
+
+
+void
+setunion(osr, os1, os2)		/* osr = os1 Union os2 */
+register OBJECT  *osr, *os1, *os2;
+{
+	register int	i1, i2;
+
+	osr[0] = 0;
+	for (i1 = i2 = 1; i1 <= os1[0] || i2 <= os2[0]; ) {
+		while (i1 <= os1[0] && (i2 > os2[0] || os1[i1] <= os2[i2])) {
+			osr[++osr[0]] = os1[i1];
+			if (i2 <= os2[0] && os2[i2] == os1[i1])
+				i2++;
+			i1++;
+		}
+		while (i2 <= os2[0] && (i1 > os1[0] || os2[i2] < os1[i1]))
+			osr[++osr[0]] = os2[i2++];
+	}
+}
+
+
+void
+setintersect(osr, os1, os2)	/* osr = os1 Intersect os2 */
+register OBJECT  *osr, *os1, *os2;
+{
+	register int	i1, i2;
+
+	osr[0] = 0;
+	if (os1[0] <= 0)
+		return;
+	for (i1 = i2 = 1; i2 <= os2[0]; ) {
+		while (os1[i1] < os2[i2])
+			if (++i1 > os1[0])
+				return;
+		while (os2[i2] < os1[i1])
+			if (++i2 > os2[0])
+				return;
+		if (os1[i1] == os2[i2])
+			osr[++osr[0]] = os2[i2++];
+	}
+}
+
+
 OCTREE
 fullnode(oset)			/* return octree for object set */
 OBJECT  *oset;
@@ -155,6 +232,7 @@ memerr:
 }
 
 
+void
 objset(oset, ot)		/* get object set for full node */
 register OBJECT  *oset;
 OCTREE  ot;
@@ -164,10 +242,10 @@ OCTREE  ot;
 
 	if (!isfull(ot))
 		goto noderr;
-	i = oseti(ot);
-	if ((os = ostable[i%OSTSIZ]) == NULL)
+	ot = oseti(ot);
+	if ((os = ostable[ot%OSTSIZ]) == NULL)
 		goto noderr;
-	for (i /= OSTSIZ; i--; os += *os + 1)
+	for (i = ot/OSTSIZ; i--; os += *os + 1)
 		if (*os <= 0)
 			goto noderr;
 	for (i = *os; i-- >= 0; )		/* copy set here */
@@ -178,43 +256,34 @@ noderr:
 }
 
 
-nonsurfinset(orig, nobjs)		/* check sets for non-surfaces */
-int  orig, nobjs;
+int
+dosets(f)				/* loop through all sets */
+int	(*f)();
 {
+	int  res = 0;
 	int  n;
-	OBJECT  *nonset;
 	register OBJECT  *os;
-	register OBJECT  i;
-						/* count non-surfaces */
-	n = 0;
-	for (i = orig; i < orig+nobjs; i++)
-		if (!issurface(objptr(i)->otype))
-			n++;
-	if (n <= 0)
-		return(0);
-						/* allocate set */
-	if ((nonset = (OBJECT *)malloc((n+1)*sizeof(OBJECT))) == NULL)
-		return(0);		/* give up if we haven't enough mem */
-						/* fill set */
-	os = nonset;
-	*os = n;
-	for (i = orig; i < orig+nobjs; i++)
-		if (!issurface(objptr(i)->otype))
-			*++os = i;
-						/* now check all sets */
+
 	for (n = 0; n < OSTSIZ; n++) {
 		if ((os = ostable[n]) == NULL)
 			continue;
-		while ((i = *os++) > 0)
-			while (i--) {
-				if (*os >= nonset[1]
-						&& *os <= nonset[nonset[0]]
-						&& inset(nonset, *os))
-					goto done;
-				os++;
-			}
+		while (*os > 0) {
+			res += (*f)(os);
+			os += *os + 1;
+		}
 	}
-done:
-	free((char *)nonset);
-	return(n < OSTSIZ);
+	return(res);
+}
+
+
+void
+donesets()			/* free ALL SETS in our table */
+{
+	register int  n;
+
+	for (n = 0; n < OSTSIZ; n++) 
+		if (ostable[n] != NULL) {
+			free((void *)ostable[n]);
+			ostable[n] = NULL;
+		}
 }