home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / source / radsrc22 / src / common / objset.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-13  |  3.9 KB  |  210 lines
  1. /* Copyright (c) 1986 Regents of the University of California */
  2.  
  3. #ifndef lint
  4. static char SCCSid[] = "@(#)objset.c 2.3 7/13/92 LBL";
  5. #endif
  6.  
  7. /*
  8.  *  objset.c - routines for maintaining object sets.
  9.  *
  10.  *    7/28/85
  11.  */
  12.  
  13. #include  "standard.h"
  14.  
  15. #include  "octree.h"
  16.  
  17. #include  "object.h"
  18.  
  19. #include  "otypes.h"
  20.  
  21. #ifndef  OSTSIZ
  22. #ifdef  BIGMEM
  23. #define  OSTSIZ        56437        /* object table size (a prime!) */
  24. #else
  25. #define  OSTSIZ        12329        /* object table size (a prime!) */
  26. #endif
  27. #endif
  28.  
  29. static OBJECT  *ostable[OSTSIZ];    /* the object set table */
  30.  
  31.  
  32. insertelem(os, obj)        /* insert obj into os, no questions */
  33. register OBJECT  *os;
  34. OBJECT  obj;
  35. {
  36.     register int  i;
  37.     
  38.     for (i = os[0]++; i > 0; i--)
  39.         if (os[i] > obj)
  40.             os[i+1] = os[i];
  41.         else
  42.             break;
  43.     os[i+1] = obj;
  44. }
  45.  
  46.  
  47. deletelem(os, obj)        /* delete obj from os, no questions */
  48. register OBJECT  *os;
  49. OBJECT  obj;
  50. {
  51.     register int  i;
  52.  
  53.     i = (*os)--;
  54.     os++;
  55.     while (i > 0 && *os < obj) {
  56.         i--;
  57.         os++;
  58.     }
  59.     while (--i > 0) {
  60.         os[0] = os[1];
  61.         os++;
  62.     }
  63. }
  64.  
  65.  
  66. inset(os, obj)            /* determine if object is in set */
  67. register OBJECT  *os;
  68. OBJECT  obj;
  69. {
  70.     int  upper, lower;
  71.     register int  cm, i;
  72.  
  73.     lower = 1;
  74.     upper = cm = os[0] + 1;
  75.  
  76.     while ((i = (lower + upper) >> 1) != cm) {
  77.         cm = obj - os[i];
  78.         if (cm > 0)
  79.             lower = i;
  80.         else if (cm < 0)
  81.             upper = i;
  82.         else
  83.             return(1);
  84.         cm = i;
  85.     }
  86.     return(0);
  87. }
  88.  
  89.  
  90. setequal(os1, os2)        /* determine if two sets are equal */
  91. register OBJECT  *os1, *os2;
  92. {
  93.     register int  i;
  94.  
  95.     for (i = *os1; i-- >= 0; )
  96.         if (*os1++ != *os2++)
  97.             return(0);
  98.     return(1);
  99. }
  100.  
  101.  
  102. setcopy(os1, os2)        /* copy object set os2 into os1 */
  103. register OBJECT  *os1, *os2;
  104. {
  105.     register int  i;
  106.  
  107.     for (i = *os2; i-- >= 0; )
  108.         *os1++ = *os2++;
  109. }
  110.  
  111.  
  112. OCTREE
  113. fullnode(oset)            /* return octree for object set */
  114. OBJECT  *oset;
  115. {
  116.     int  osentry, ntries;
  117.     long  hval;
  118.     OCTREE  ot;
  119.     register int  i;
  120.     register OBJECT  *os;
  121.                     /* hash on set */
  122.     hval = 0;
  123.     os = oset;
  124.     i = *os++;
  125.     while (i-- > 0)
  126.         hval += *os++;
  127.     ntries = 0;
  128. tryagain:
  129.     osentry = (hval + (long)ntries*ntries) % OSTSIZ;
  130.     os = ostable[osentry];
  131.     if (os == NULL) {
  132.         os = ostable[osentry] = (OBJECT *)malloc(
  133.                 (unsigned)(oset[0]+2)*sizeof(OBJECT));
  134.         if (os == NULL)
  135.             goto memerr;
  136.         ot = oseti(osentry);
  137.     } else {
  138.                         /* look for set */
  139.         for (i = 0; *os > 0; i++, os += *os + 1)
  140.             if (setequal(os, oset))
  141.                 break;
  142.         ot = oseti(i*OSTSIZ + osentry);
  143.         if (*os > 0)            /* found it */
  144.             return(ot);
  145.         if (!isfull(ot))        /* entry overflow */
  146.             if (++ntries < OSTSIZ)
  147.                 goto tryagain;
  148.             else
  149.                 error(INTERNAL, "hash table overflow in fullnode");
  150.                         /* remember position */
  151.         i = os - ostable[osentry];
  152.         os = ostable[osentry] = (OBJECT *)realloc(
  153.                 (char *)ostable[osentry],
  154.                 (unsigned)(i+oset[0]+2)*sizeof(OBJECT));
  155.         if (os == NULL)
  156.             goto memerr;
  157.         os += i;            /* last entry */
  158.     }
  159.     setcopy(os, oset);        /* add new set */
  160.     os += *os + 1;
  161.     *os = 0;            /* terminator */
  162.     return(ot);
  163. memerr:
  164.     error(SYSTEM, "out of memory in fullnode");
  165. }
  166.  
  167.  
  168. objset(oset, ot)        /* get object set for full node */
  169. register OBJECT  *oset;
  170. OCTREE  ot;
  171. {
  172.     register OBJECT  *os;
  173.     register int  i;
  174.  
  175.     if (!isfull(ot))
  176.         goto noderr;
  177.     i = oseti(ot);
  178.     if ((os = ostable[i%OSTSIZ]) == NULL)
  179.         goto noderr;
  180.     for (i /= OSTSIZ; i--; os += *os + 1)
  181.         if (*os <= 0)
  182.             goto noderr;
  183.     for (i = *os; i-- >= 0; )        /* copy set here */
  184.         *oset++ = *os++;
  185.     return;
  186. noderr:
  187.     error(CONSISTENCY, "bad node in objset");
  188. }
  189.  
  190.  
  191. nonsurfinset(orig, nobjs)        /* check sets for non-surfaces */
  192. int  orig, nobjs;
  193. {
  194.     int  n;
  195.     register OBJECT  *os;
  196.     register OBJECT  i, s;
  197.  
  198.     for (n = 0; n < OSTSIZ; n++) {
  199.         if ((os = ostable[n]) == NULL)
  200.             continue;
  201.         while ((i = *os++) > 0)
  202.             do
  203.                 if ((s = *os++) >= orig && s < orig+nobjs &&
  204.                         ismodifier(objptr(s)->otype))
  205.                     return(1);
  206.             while (--i);
  207.     }
  208.     return(0);
  209. }
  210.