Back to index

radiance  4R0+20100331
Defines | Functions | Variables
objset.c File Reference
#include "copyright.h"
#include "standard.h"
#include "octree.h"
#include "object.h"

Go to the source code of this file.

Defines

#define OSTSIZ   262139 /* object table size (a prime!) */

Functions

void insertelem (OBJECT *os, OBJECT obj)
void deletelem (OBJECT *os, OBJECT obj)
int inset (OBJECT *os, OBJECT obj)
int setequal (OBJECT *os1, OBJECT *os2)
void setcopy (OBJECT *os1, OBJECT *os2)
OBJECTsetsave (OBJECT *os)
void setunion (OBJECT *osr, OBJECT *os1, OBJECT *os2)
void setintersect (OBJECT *osr, OBJECT *os1, OBJECT *os2)
OCTREE fullnode (OBJECT *oset)
void objset (OBJECT *oset, OCTREE ot)
void donesets ()

Variables

static const char RCSid [] = "$Id: objset.c,v 2.16 2006/02/22 17:05:36 greg Exp $"
static OBJECTostable [OSTSIZ]

Define Documentation

#define OSTSIZ   262139 /* object table size (a prime!) */

Definition at line 22 of file objset.c.


Function Documentation

void deletelem ( OBJECT os,
OBJECT  obj 
)

Definition at line 46 of file objset.c.

{
       register int  i;

       i = (*os)--;
       os++;
       while (i > 0 && *os < obj) {
              i--;
              os++;
       }
       while (--i > 0) {
              os[0] = os[1];
              os++;
       }
}

Here is the caller graph for this function:

void donesets ( void  )

Definition at line 262 of file objset.c.

{
       register int  n;

       for (n = 0; n < OSTSIZ; n++) 
              if (ostable[n] != NULL) {
                     free((void *)ostable[n]);
                     ostable[n] = NULL;
              }
}

Here is the caller graph for this function:

OCTREE fullnode ( OBJECT oset)

Definition at line 180 of file objset.c.

{
       int  osentry, ntries;
       long  hval;
       OCTREE  ot;
       register int  i;
       register OBJECT  *os;
                                   /* hash on set */
       hval = 0;
       os = oset;
       i = *os++;
       while (i-- > 0)
              hval += *os++;
       ntries = 0;
tryagain:
       osentry = (hval + (long)ntries*ntries) % OSTSIZ;
       os = ostable[osentry];
       if (os == NULL) {
              os = ostable[osentry] = (OBJECT *)malloc(
                            (unsigned)(oset[0]+2)*sizeof(OBJECT));
              if (os == NULL)
                     goto memerr;
              ot = oseti(osentry);
       } else {
                                          /* look for set */
              for (i = 0; *os > 0; i++, os += *os + 1)
                     if (setequal(os, oset))
                            break;
              ot = oseti(i*OSTSIZ + osentry);
              if (*os > 0)                /* found it */
                     return(ot);
              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(
                            (void *)ostable[osentry],
                            (unsigned)(i+oset[0]+2)*sizeof(OBJECT));
              if (os == NULL)
                     goto memerr;
              os += i;                    /* last entry */
       }
       setcopy(os, oset);          /* add new set */
       os += *os + 1;
       *os = 0;                    /* terminator */
       return(ot);
memerr:
       error(SYSTEM, "out of memory in fullnode");
       return 0; /* pro forma return */
}

Here is the call graph for this function:

Here is the caller graph for this function:

void insertelem ( OBJECT os,
OBJECT  obj 
)

Definition at line 30 of file objset.c.

{
       register int  i;
       
       for (i = os[0]++; i > 0; i--)
              if (os[i] > obj)
                     os[i+1] = os[i];
              else
                     break;
       os[i+1] = obj;
}

Here is the caller graph for this function:

int inset ( OBJECT os,
OBJECT  obj 
)

Definition at line 66 of file objset.c.

{
       int  upper, lower;
       register 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 = i + 1;
                                   /* binary search algorithm */
       while ((i = (lower + upper) >> 1) != cm) {
              cm = obj - os[i];
              if (cm > 0)
                     lower = i;
              else if (cm < 0)
                     upper = i;
              else
                     return(1);
              cm = i;
       }
       return(0);
}

Here is the caller graph for this function:

void objset ( OBJECT oset,
OCTREE  ot 
)

Definition at line 238 of file objset.c.

{
       register OBJECT  *os;
       register int  i;

       if (!isfull(ot))
              goto noderr;
       ot = oseti(ot);
       if ((os = ostable[ot%OSTSIZ]) == NULL)
              goto noderr;
       for (i = ot/OSTSIZ; i--; os += *os + 1)
              if (*os <= 0)
                     goto noderr;
       for (i = *os; i-- >= 0; )          /* copy set here */
              *oset++ = *os++;
       return;
noderr:
       error(CONSISTENCY, "bad node in objset");
}

Here is the call graph for this function:

Here is the caller graph for this function:

void setcopy ( OBJECT os1,
OBJECT os2 
)

Definition at line 111 of file objset.c.

{
       register int  i;

       for (i = *os2; i-- >= 0; )
              *os1++ = *os2++;
}

Here is the caller graph for this function:

int setequal ( OBJECT os1,
OBJECT os2 
)

Definition at line 98 of file objset.c.

{
       register int  i;

       for (i = *os1; i-- >= 0; )
              if (*os1++ != *os2++)
                     return(0);
       return(1);
}

Here is the caller graph for this function:

void setintersect ( OBJECT osr,
OBJECT os1,
OBJECT os2 
)

Definition at line 158 of file objset.c.

{
       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++];
       }
}
OBJECT* setsave ( OBJECT os)

Definition at line 122 of file objset.c.

{
       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);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void setunion ( OBJECT osr,
OBJECT os1,
OBJECT os2 
)

Definition at line 138 of file objset.c.

{
       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++];
       }
}

Here is the caller graph for this function:


Variable Documentation

OBJECT* ostable[OSTSIZ] [static]

Definition at line 26 of file objset.c.

const char RCSid[] = "$Id: objset.c,v 2.16 2006/02/22 17:05:36 greg Exp $" [static]

Definition at line 2 of file objset.c.