--- ray/src/hd/sm_usets.c	1998/12/28 17:53:06	3.1
+++ ray/src/hd/sm_usets.c	2003/06/30 14:59:12	3.5
@@ -1,15 +1,15 @@
-/* Copyright (c) 1998 Silicon Graphics, Inc. */
-
 #ifndef lint
-static char SCCSid[] = "$SunId$ SGI";
+static const char	RCSid[] = "$Id: sm_usets.c,v 3.5 2003/06/30 14:59:12 schorsch Exp $";
 #endif
-
 /*
  * Quadtree-specific set operations with unsorted sets.
  */
 
+#include <string.h>
+
 #include "standard.h"
 #include "sm_flag.h"
+#include "object.h"
 #include "sm_qtree.h"
 
 
@@ -23,7 +23,7 @@ static char SCCSid[] = "$SunId$ SGI";
 OBJECT	**qtsettab= NULL;		/* quadtree leaf node table */
 QUADTREE  qtnumsets=0;			/* number of used set indices */
 static int  qtfreesets = EMPTY;		/* free set index list */
-int4 *qtsetflag = NULL;
+int32 *qtsetflag = NULL;
 static int qtallocsets =0;
 
 qtclearsetflags()
@@ -32,7 +32,7 @@ qtclearsetflags()
   if(!qtsetflag)
     return;
 
-    bzero((char *)qtsetflag,FLAG_BYTES(qtallocsets));
+    memset((char *)qtsetflag, '\0', FLAG_BYTES(qtallocsets));
 }
 
 
@@ -48,19 +48,19 @@ OBJECT  *oset;
 		osi = qtfreesets;
 		qtfreesets = (int)qtsettab[osi];
 	} else if ((osi = qtnumsets++) % QTSETIBLK == 0) {
-		qtsettab = (OBJECT **)realloc((char *)qtsettab,
+		qtsettab = (OBJECT **)realloc((void *)qtsettab,
 				(unsigned)(osi+QTSETIBLK)*sizeof(OBJECT *));
 		if (qtsettab == NULL)
 			goto memerr;
-		qtsetflag = (int4 *)realloc((char *)qtsetflag,
+		qtsetflag = (int32 *)realloc((void *)qtsetflag,
 				   FLAG_BYTES(osi+ QTSETIBLK));
 		if (qtsetflag == NULL)
 			goto memerr;
 		if(qtallocsets)
-		  bzero((char *)((char *)(qtsetflag)+FLAG_BYTES(qtallocsets)),
+		  memset((char *)((char *)(qtsetflag)+FLAG_BYTES(qtallocsets)), '\0',
 		      FLAG_BYTES(osi+QTSETIBLK)-FLAG_BYTES(qtallocsets));
 		else
-		  bzero((char *)(qtsetflag),FLAG_BYTES(osi +QTSETIBLK));
+		  memset((char *)(qtsetflag), '\0', FLAG_BYTES(osi +QTSETIBLK));
 
 		qtallocsets = osi + QTSETIBLK; 
 	}
@@ -74,8 +74,66 @@ memerr:
 }
 
 
+deletuelem(os, obj)		/* delete obj from unsorted os, no questions */
+register OBJECT  *os;
+OBJECT  obj;
+{
+	register int  i,j;
+	OBJECT *optr;
+	/* Take 2nd to last and put in position of obj: move last down:
+	   want to preserve last added
+	 */
+	i = (*os)--;
+#ifdef DEBUG
+	if( i <= 0)
+	  error(CONSISTENCY,"deleteuelem():empty set\n");
+#endif
+	if(i < 3)
+	{
+	  if((i == 2) && (*(++os) == obj))
+	    *os = *(os+1);
+	  return;
+	}
+	optr = os + i;
+	os++;
+	while (i-- > 1 && *os != obj)
+	   os++;
+#ifdef DEBUG
+	if( *os != obj)
+	  error(CONSISTENCY,"deleteuelem():id not found\n");
+#endif
+	*os = *(optr-1);
+	*(optr-1) = *optr;
+}
 
 QUADTREE
+qtdeletuelem(qt, id)		/* delete element from unsorted leaf node */
+QUADTREE  qt;
+OBJECT  id;
+{
+	register QUADTREE  lf;
+#ifdef DEBUG
+	if(id < 0)
+		eputs("qtdeletuelem():Invalid triangle id\n");
+	if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
+		error(CONSISTENCY, "empty/bad node in qtdelelem");
+#else
+	lf = QT_SET_INDEX(qt);
+#endif
+	if (qtsettab[lf][0] <= 1) {		/* blow leaf away */
+		free((void *)qtsettab[lf]);
+		qtsettab[lf] = (OBJECT *)qtfreesets;
+		qtfreesets = lf;
+		return(EMPTY);
+	}
+	deletuelem(qtsettab[lf], id);
+	if (QTONTHRESH(qtsettab[lf][0]))
+		qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
+				QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
+	return(qt);
+}
+
+QUADTREE
 qtdelelem(qt, id)		/* delete element from leaf node */
 QUADTREE  qt;
 OBJECT  id;
@@ -98,14 +156,14 @@ OBJECT  id;
 	  return(qt);
 	}
 	if (qtsettab[lf][0] <= 1) {		/* blow leaf away */
-		free((char *)qtsettab[lf]);
+		free((void *)qtsettab[lf]);
 		qtsettab[lf] = (OBJECT *)qtfreesets;
 		qtfreesets = lf;
 		return(EMPTY);
 	}
 	deletelem(qtsettab[lf], id);
 	if (QTONTHRESH(qtsettab[lf][0]))
-		qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
+		qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
 				QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
 	return(qt);
 }
@@ -142,7 +200,7 @@ OBJECT  id;
 	  return(qt);
 	}
 	if (QTONTHRESH(qtsettab[lf][0])) {
-		qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
+		qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
 				QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
 		if (qtsettab[lf] == NULL)
 			error(SYSTEM, "out of memory in qtaddelem");
@@ -174,7 +232,7 @@ qtcompressuelem(qt,compress_set)
 	osize = os[0];
 	if((i=compress_set(os)) < osize)
 	{
-	  qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
+	  qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
 					   QTNODESIZ(i+1)*sizeof(OBJECT));
 	  if (qtsettab[lf] == NULL)
 	    error(SYSTEM, "out of memory in qtaddelem");
@@ -193,7 +251,7 @@ OBJECT  id;
 
 #ifdef DEBUG
 	if(id < 0)
-		eputs("qtaddelem():Invalid triangle id\n");
+		eputs("qtadduelem():Invalid sample id\n");
 #endif
 	if (QT_IS_EMPTY(qt)) {		/* create new leaf */
 		newset[0] = 1; newset[1] = id;
@@ -206,7 +264,7 @@ OBJECT  id;
 	lf = QT_SET_INDEX(qt);
 #endif
 	if (QTONTHRESH(qtsettab[lf][0])) {
-		qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
+		qtsettab[lf] = (OBJECT *)realloc((void *)qtsettab[lf],
 				QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
 		if (qtsettab[lf] == NULL)
 			error(SYSTEM, "out of memory in qtaddelem");
@@ -256,7 +314,7 @@ QUADTREE  qt;
 	osi = QT_SET_INDEX(qt);
 	if (osi >= qtnumsets)
 		return;
-	free((char *)qtsettab[osi]);
+	free((void *)qtsettab[osi]);
 	qtsettab[osi] = (OBJECT *)qtfreesets;
 	qtfreesets = osi;
 }
@@ -273,12 +331,12 @@ qtfreeleaves()			/* free ALL sets and leaf nodes */
 	}
 	for (i = qtnumsets; i--; )
 		if (qtsettab[i] != NULL)
-			free((char *)qtsettab[i]);
-	free((char *)qtsettab);
+			free((void *)qtsettab[i]);
+	free((void *)qtsettab);
 	qtsettab = NULL;
 	if(qtsetflag)
 	{
-	  free((char *)qtsetflag);
+	  free((void *)qtsetflag);
 	  qtsetflag=0;
 	}
 	qtnumsets = 0;