--- ray/src/common/objset.c	1992/03/12 11:41:18	2.2
+++ ray/src/common/objset.c	2003/05/15 05:13:35	2.11
@@ -1,34 +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.11 2003/05/15 05:13:35 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		56437		/* object table size (a prime!) */
+#ifdef  SMLMEM
+#define  OSTSIZ		32749		/* object table size (a prime!) */
 #else
-#define  OSTSIZ		12329		/* object table size (a prime!) */
+#define  OSTSIZ		262139		/* object table size (a prime!) */
 #endif
 #endif
 
 static OBJECT  *ostable[OSTSIZ];	/* the object set table */
 
 
+void
 insertelem(os, obj)		/* insert obj into os, no questions */
 register OBJECT  *os;
 OBJECT  obj;
@@ -44,6 +42,7 @@ OBJECT  obj;
 }
 
 
+void
 deletelem(os, obj)		/* delete obj from os, no questions */
 register OBJECT  *os;
 OBJECT  obj;
@@ -63,6 +62,7 @@ OBJECT  obj;
 }
 
 
+int
 inset(os, obj)			/* determine if object is in set */
 register OBJECT  *os;
 OBJECT  obj;
@@ -70,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)
@@ -87,6 +94,7 @@ OBJECT  obj;
 }
 
 
+int
 setequal(os1, os2)		/* determine if two sets are equal */
 register OBJECT  *os1, *os2;
 {
@@ -99,6 +107,7 @@ register OBJECT  *os1, *os2;
 }
 
 
+void
 setcopy(os1, os2)		/* copy object set os2 into os1 */
 register OBJECT  *os1, *os2;
 {
@@ -109,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;
@@ -150,7 +217,7 @@ tryagain:
 						/* remember position */
 		i = os - ostable[osentry];
 		os = ostable[osentry] = (OBJECT *)realloc(
-				(char *)ostable[osentry],
+				(void *)ostable[osentry],
 				(unsigned)(i+oset[0]+2)*sizeof(OBJECT));
 		if (os == NULL)
 			goto memerr;
@@ -165,6 +232,7 @@ memerr:
 }
 
 
+void
 objset(oset, ot)		/* get object set for full node */
 register OBJECT  *oset;
 OCTREE  ot;
@@ -174,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 */
@@ -188,24 +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;
 	register OBJECT  *os;
-	register OBJECT  i, s;
 
 	for (n = 0; n < OSTSIZ; n++) {
 		if ((os = ostable[n]) == NULL)
 			continue;
-		while ((i = *os++) > 0)
-			while (i--) {
-				s = *os;
-				if (s >= orig && s < orig+nobjs &&
-						ismodifier(objptr(s)->otype))
-					return(1);
-				os++;
-			}
+		while (*os > 0) {
+			res += (*f)(os);
+			os += *os + 1;
+		}
 	}
-	return(0);
+	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;
+		}
 }