Back to index

radiance  4R0+20100331
objset.c
Go to the documentation of this file.
00001 #ifndef lint
00002 static const char    RCSid[] = "$Id: objset.c,v 2.16 2006/02/22 17:05:36 greg Exp $";
00003 #endif
00004 /*
00005  *  objset.c - routines for maintaining object sets.
00006  *
00007  *  External symbols declared in object.h
00008  */
00009 
00010 #include "copyright.h"
00011 
00012 #include  "standard.h"
00013 
00014 #include  "octree.h"
00015 
00016 #include  "object.h"
00017 
00018 #ifndef  OSTSIZ
00019 #ifdef  SMLMEM
00020 #define  OSTSIZ             32749         /* object table size (a prime!) */
00021 #else
00022 #define  OSTSIZ             262139        /* object table size (a prime!) */
00023 #endif
00024 #endif
00025 
00026 static OBJECT  *ostable[OSTSIZ];   /* the object set table */
00027 
00028 
00029 void
00030 insertelem(os, obj)         /* insert obj into os, no questions */
00031 register OBJECT  *os;
00032 OBJECT  obj;
00033 {
00034        register int  i;
00035        
00036        for (i = os[0]++; i > 0; i--)
00037               if (os[i] > obj)
00038                      os[i+1] = os[i];
00039               else
00040                      break;
00041        os[i+1] = obj;
00042 }
00043 
00044 
00045 void
00046 deletelem(os, obj)          /* delete obj from os, no questions */
00047 register OBJECT  *os;
00048 OBJECT  obj;
00049 {
00050        register int  i;
00051 
00052        i = (*os)--;
00053        os++;
00054        while (i > 0 && *os < obj) {
00055               i--;
00056               os++;
00057        }
00058        while (--i > 0) {
00059               os[0] = os[1];
00060               os++;
00061        }
00062 }
00063 
00064 
00065 int
00066 inset(os, obj)                     /* determine if object is in set */
00067 register OBJECT  *os;
00068 OBJECT  obj;
00069 {
00070        int  upper, lower;
00071        register int  cm, i;
00072 
00073        if ((i = os[0]) <= 12) {    /* linear search algorithm */
00074               cm = obj;
00075               while (i-- > 0)
00076                      if (*++os == cm)
00077                             return(1);
00078               return(0);
00079        }
00080        lower = 1;
00081        upper = cm = i + 1;
00082                                    /* binary search algorithm */
00083        while ((i = (lower + upper) >> 1) != cm) {
00084               cm = obj - os[i];
00085               if (cm > 0)
00086                      lower = i;
00087               else if (cm < 0)
00088                      upper = i;
00089               else
00090                      return(1);
00091               cm = i;
00092        }
00093        return(0);
00094 }
00095 
00096 
00097 int
00098 setequal(os1, os2)          /* determine if two sets are equal */
00099 register OBJECT  *os1, *os2;
00100 {
00101        register int  i;
00102 
00103        for (i = *os1; i-- >= 0; )
00104               if (*os1++ != *os2++)
00105                      return(0);
00106        return(1);
00107 }
00108 
00109 
00110 void
00111 setcopy(os1, os2)           /* copy object set os2 into os1 */
00112 register OBJECT  *os1, *os2;
00113 {
00114        register int  i;
00115 
00116        for (i = *os2; i-- >= 0; )
00117               *os1++ = *os2++;
00118 }
00119 
00120 
00121 OBJECT *
00122 setsave(os)                 /* allocate space and save set */
00123 register OBJECT  *os;
00124 {
00125        OBJECT  *osnew;
00126        register OBJECT  *oset;
00127        register int  i;
00128 
00129        if ((osnew = oset = (OBJECT *)malloc((*os+1)*sizeof(OBJECT))) == NULL)
00130               error(SYSTEM, "out of memory in setsave\n");
00131        for (i = *os; i-- >= 0; )   /* inline setcopy */
00132               *oset++ = *os++;
00133        return(osnew);
00134 }
00135 
00136 
00137 void
00138 setunion(osr, os1, os2)            /* osr = os1 Union os2 */
00139 register OBJECT  *osr, *os1, *os2;
00140 {
00141        register int  i1, i2;
00142 
00143        osr[0] = 0;
00144        for (i1 = i2 = 1; i1 <= os1[0] || i2 <= os2[0]; ) {
00145               while (i1 <= os1[0] && (i2 > os2[0] || os1[i1] <= os2[i2])) {
00146                      osr[++osr[0]] = os1[i1];
00147                      if (i2 <= os2[0] && os2[i2] == os1[i1])
00148                             i2++;
00149                      i1++;
00150               }
00151               while (i2 <= os2[0] && (i1 > os1[0] || os2[i2] < os1[i1]))
00152                      osr[++osr[0]] = os2[i2++];
00153        }
00154 }
00155 
00156 
00157 void
00158 setintersect(osr, os1, os2) /* osr = os1 Intersect os2 */
00159 register OBJECT  *osr, *os1, *os2;
00160 {
00161        register int  i1, i2;
00162 
00163        osr[0] = 0;
00164        if (os1[0] <= 0)
00165               return;
00166        for (i1 = i2 = 1; i2 <= os2[0]; ) {
00167               while (os1[i1] < os2[i2])
00168                      if (++i1 > os1[0])
00169                             return;
00170               while (os2[i2] < os1[i1])
00171                      if (++i2 > os2[0])
00172                             return;
00173               if (os1[i1] == os2[i2])
00174                      osr[++osr[0]] = os2[i2++];
00175        }
00176 }
00177 
00178 
00179 OCTREE
00180 fullnode(oset)                     /* return octree for object set */
00181 OBJECT  *oset;
00182 {
00183        int  osentry, ntries;
00184        long  hval;
00185        OCTREE  ot;
00186        register int  i;
00187        register OBJECT  *os;
00188                                    /* hash on set */
00189        hval = 0;
00190        os = oset;
00191        i = *os++;
00192        while (i-- > 0)
00193               hval += *os++;
00194        ntries = 0;
00195 tryagain:
00196        osentry = (hval + (long)ntries*ntries) % OSTSIZ;
00197        os = ostable[osentry];
00198        if (os == NULL) {
00199               os = ostable[osentry] = (OBJECT *)malloc(
00200                             (unsigned)(oset[0]+2)*sizeof(OBJECT));
00201               if (os == NULL)
00202                      goto memerr;
00203               ot = oseti(osentry);
00204        } else {
00205                                           /* look for set */
00206               for (i = 0; *os > 0; i++, os += *os + 1)
00207                      if (setequal(os, oset))
00208                             break;
00209               ot = oseti(i*OSTSIZ + osentry);
00210               if (*os > 0)                /* found it */
00211                      return(ot);
00212               if (!isfull(ot)) {          /* entry overflow */
00213                      if (++ntries < OSTSIZ)
00214                             goto tryagain;
00215                      else
00216                             error(INTERNAL, "hash table overflow in fullnode");
00217               }
00218                                           /* remember position */
00219               i = os - ostable[osentry];
00220               os = ostable[osentry] = (OBJECT *)realloc(
00221                             (void *)ostable[osentry],
00222                             (unsigned)(i+oset[0]+2)*sizeof(OBJECT));
00223               if (os == NULL)
00224                      goto memerr;
00225               os += i;                    /* last entry */
00226        }
00227        setcopy(os, oset);          /* add new set */
00228        os += *os + 1;
00229        *os = 0;                    /* terminator */
00230        return(ot);
00231 memerr:
00232        error(SYSTEM, "out of memory in fullnode");
00233        return 0; /* pro forma return */
00234 }
00235 
00236 
00237 void
00238 objset(oset, ot)            /* get object set for full node */
00239 register OBJECT  *oset;
00240 OCTREE  ot;
00241 {
00242        register OBJECT  *os;
00243        register int  i;
00244 
00245        if (!isfull(ot))
00246               goto noderr;
00247        ot = oseti(ot);
00248        if ((os = ostable[ot%OSTSIZ]) == NULL)
00249               goto noderr;
00250        for (i = ot/OSTSIZ; i--; os += *os + 1)
00251               if (*os <= 0)
00252                      goto noderr;
00253        for (i = *os; i-- >= 0; )          /* copy set here */
00254               *oset++ = *os++;
00255        return;
00256 noderr:
00257        error(CONSISTENCY, "bad node in objset");
00258 }
00259 
00260 
00261 void
00262 donesets()                  /* free ALL SETS in our table */
00263 {
00264        register int  n;
00265 
00266        for (n = 0; n < OSTSIZ; n++) 
00267               if (ostable[n] != NULL) {
00268                      free((void *)ostable[n]);
00269                      ostable[n] = NULL;
00270               }
00271 }