--- ray/src/common/objset.c 1991/10/23 11:52:55 1.8 +++ ray/src/common/objset.c 2015/04/28 16:56:10 2.17 @@ -1,39 +1,45 @@ -/* 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.17 2015/04/28 16:56:10 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 +#undef xtra_long +#ifdef _WIN64 +typedef unsigned long long int xtra_long; +#else +typedef unsigned long int xtra_long; +#endif + static OBJECT *ostable[OSTSIZ]; /* the object set table */ -insertelem(os, obj) /* insert obj into os, no questions */ -register OBJECT *os; -OBJECT obj; +void +insertelem( /* insert obj into os, no questions */ + OBJECT *os, + OBJECT obj +) { - register int i; + int i; for (i = os[0]++; i > 0; i--) if (os[i] > obj) @@ -44,11 +50,13 @@ OBJECT obj; } -deletelem(os, obj) /* delete obj from os, no questions */ -register OBJECT *os; -OBJECT obj; +void +deletelem( /* delete obj from os, no questions */ + OBJECT *os, + OBJECT obj +) { - register int i; + int i; i = (*os)--; os++; @@ -63,16 +71,25 @@ OBJECT obj; } -inset(os, obj) /* determine if object is in set */ -register OBJECT *os; -OBJECT obj; +int +inset( /* determine if object is in set */ + OBJECT *os, + OBJECT obj +) { int upper, lower; - register int cm, i; + int cm, i; + if ((i = os[0]) <= 12) { /* 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,10 +104,13 @@ OBJECT obj; } -setequal(os1, os2) /* determine if two sets are equal */ -register OBJECT *os1, *os2; +int +setequal( /* determine if two sets are equal */ + OBJECT *os1, + OBJECT *os2 +) { - register int i; + int i; for (i = *os1; i-- >= 0; ) if (*os1++ != *os2++) @@ -99,25 +119,94 @@ register OBJECT *os1, *os2; } -setcopy(os1, os2) /* copy object set os2 into os1 */ -register OBJECT *os1, *os2; +void +setcopy( /* copy object set os2 into os1 */ + OBJECT *os1, + OBJECT *os2 +) { - register int i; + int i; for (i = *os2; i-- >= 0; ) *os1++ = *os2++; } +OBJECT * +setsave( /* allocate space and save set */ + OBJECT *os +) +{ + OBJECT *osnew; + OBJECT *oset; + 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 Union os2 */ + OBJECT *osr, + OBJECT *os1, + OBJECT *os2 +) +{ + 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 Intersect os2 */ + OBJECT *osr, + OBJECT *os1, + OBJECT *os2 +) +{ + 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; +fullnode( /* return octree for object set */ + OBJECT *oset +) { - int osentry, ntries; - long hval; + unsigned int ntries; + xtra_long hval; OCTREE ot; - register int i; - register OBJECT *os; + int osentry, i; + OBJECT *os; /* hash on set */ hval = 0; os = oset; @@ -126,7 +215,7 @@ OBJECT *oset; hval += *os++; ntries = 0; tryagain: - osentry = (hval + (long)ntries*ntries) % OSTSIZ; + osentry = (hval + (xtra_long)ntries*ntries) % OSTSIZ; os = ostable[osentry]; if (os == NULL) { os = ostable[osentry] = (OBJECT *)malloc( @@ -142,15 +231,16 @@ tryagain: ot = oseti(i*OSTSIZ + osentry); if (*os > 0) /* found it */ return(ot); - if (!isfull(ot)) /* entry overflow */ + if (!isfull(ot)) { /* entry overflow */ if (++ntries < OSTSIZ) goto tryagain; else error(INTERNAL, "hash table overflow in fullnode"); + } /* 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; @@ -162,22 +252,25 @@ tryagain: return(ot); memerr: error(SYSTEM, "out of memory in fullnode"); + return 0; /* pro forma return */ } -objset(oset, ot) /* get object set for full node */ -register OBJECT *oset; -OCTREE ot; +void +objset( /* get object set for full node */ + OBJECT *oset, + OCTREE ot +) { - register OBJECT *os; - register int i; + OBJECT *os; + int i; 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 +281,14 @@ noderr: } -nonsurfinset(orig, nobjs) /* check sets for non-surfaces */ -int orig, nobjs; +void +donesets(void) /* free ALL SETS in our table */ { 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 && - !issurface(objptr(s)->otype)) - return(1); - os++; - } - } - return(0); + for (n = 0; n < OSTSIZ; n++) + if (ostable[n] != NULL) { + free((void *)ostable[n]); + ostable[n] = NULL; + } }