Skip to content

AFNI/NIfTI Server

Sections
Personal tools
You are here: Home » AFNI » Documentation
 

Doxygen Source Code Documentation

Main Page   Alphabetical List   Data Structures   File List   Data Fields   Globals   Search  

qset.c

Go to the documentation of this file.
00001 /*<html><pre>  -<a                             href="qh-set.htm"
00002   >-------------------------------</a><a name="TOP">-</a>
00003 
00004    qset.c 
00005    implements set manipulations needed for quickhull 
00006 
00007    see qh-set.htm and qset.h
00008 
00009    copyright (c) 1993-2001 The Geometry Center        
00010 */
00011 
00012 #include <stdio.h>
00013 #include <string.h>
00014 /*** uncomment here and qhull_a.h 
00015      if string.h does not define memcpy()
00016 #include <memory.h>
00017 */
00018 #include "qset.h"
00019 #include "mem.h"
00020 
00021 #ifndef qhDEFqhull
00022 typedef struct ridgeT ridgeT;
00023 typedef struct facetT facetT;
00024 void    qh_errexit(int exitcode, facetT *, ridgeT *);
00025 #endif
00026 
00027 /*=============== internal macros ===========================*/
00028 
00029 /*-<a                             href="qh-set.htm#TOC"
00030   >-------------------------------<a name="SETsizeaddr_">-</a>
00031    
00032   SETsizeaddr_(set) 
00033     return pointer to actual size+1 of set (set CANNOT be NULL!!)
00034       
00035   notes:
00036     *SETsizeaddr==NULL or e[*SETsizeaddr-1].p==NULL
00037 */
00038 #define SETsizeaddr_(set) (&((set)->e[(set)->maxsize].i))
00039 
00040 /*============ functions in alphabetical order ===================*/
00041   
00042 /*-<a                             href="qh-set.htm#TOC"
00043   >--------------------------------<a name="setaddnth">-</a>
00044    
00045   qh_setaddnth( setp, nth, newelem)
00046     adds newelem as n'th element of sorted or unsorted *setp
00047       
00048   notes:
00049     *setp and newelem must be defined
00050     *setp may be a temp set
00051     nth=0 is first element
00052     errors if nth is out of bounds
00053    
00054   design:
00055     expand *setp if empty or full
00056     move tail of *setp up one
00057     insert newelem
00058 */
00059 void qh_setaddnth(setT **setp, int nth, void *newelem) {
00060   int *sizep, oldsize, i;
00061   void **oldp, **newp;
00062 
00063   if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
00064     qh_setlarger(setp);
00065     sizep= SETsizeaddr_(*setp);
00066   }
00067   oldsize= *sizep - 1;
00068   if (nth < 0 || nth > oldsize) {
00069     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
00070     qh_setprint (qhmem.ferr, "", *setp);
00071     qh_errexit (qhmem_ERRqhull, NULL, NULL);
00072   }
00073   (*sizep)++;
00074   oldp= SETelemaddr_(*setp, oldsize, void);   /* NULL */
00075   newp= oldp+1;
00076   for (i= oldsize-nth+1; i--; )  /* move at least NULL  */
00077     *(newp--)= *(oldp--);       /* may overwrite *sizep */
00078   *newp= newelem;
00079 } /* setaddnth */
00080 
00081 
00082 /*-<a                              href="qh-set.htm#TOC"
00083   >--------------------------------<a name="setaddsorted">-</a>
00084    
00085   setaddsorted( setp, newelem )
00086     adds an newelem into sorted *setp
00087       
00088   notes:
00089     *setp and newelem must be defined
00090     *setp may be a temp set
00091     nop if newelem already in set
00092   
00093   design:
00094     find newelem's position in *setp
00095     insert newelem
00096 */
00097 void qh_setaddsorted(setT **setp, void *newelem) {
00098   int newindex=0;
00099   void *elem, **elemp;
00100 
00101   FOREACHelem_(*setp) {          /* could use binary search instead */
00102     if (elem < newelem)
00103       newindex++;
00104     else if (elem == newelem)
00105       return;
00106     else
00107       break;
00108   }
00109   qh_setaddnth(setp, newindex, newelem);
00110 } /* setaddsorted */
00111 
00112 
00113 /*-<a                             href="qh-set.htm#TOC"
00114   >-------------------------------<a name="setappend">-</a>
00115   
00116   qh_setappend( setp, newelem)
00117     append newelem to *setp
00118 
00119   notes:
00120     *setp may be a temp set
00121     *setp and newelem may be NULL
00122 
00123   design:
00124     expand *setp if empty or full
00125     append newelem to *setp
00126     
00127 */
00128 void qh_setappend(setT **setp, void *newelem) {
00129   int *sizep;
00130   void **endp;
00131 
00132   if (!newelem)
00133     return;
00134   if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
00135     qh_setlarger(setp);
00136     sizep= SETsizeaddr_(*setp);
00137   }
00138   *(endp= &((*setp)->e[(*sizep)++ - 1].p))= newelem;
00139   *(++endp)= NULL;
00140 } /* setappend */
00141 
00142 /*-<a                             href="qh-set.htm#TOC"
00143   >-------------------------------<a name="setappend_set">-</a>
00144   
00145   qh_setappend_set( setp, setA) 
00146     appends setA to *setp
00147 
00148   notes:
00149     *setp and setA may be NULL
00150     *setp can not be a temp set
00151 
00152   design:
00153     setup for copy
00154     expand *setp if it is too small
00155     append all elements of setA to *setp 
00156 */
00157 void qh_setappend_set(setT **setp, setT *setA) {
00158   int *sizep, sizeA, size;
00159   setT *oldset;
00160 
00161   if (!setA)
00162     return;
00163   SETreturnsize_(setA, sizeA);
00164   if (!*setp)
00165     *setp= qh_setnew (sizeA);
00166   sizep= SETsizeaddr_(*setp);
00167   if (!(size= *sizep))
00168     size= (*setp)->maxsize;
00169   else
00170     size--;
00171   if (size + sizeA > (*setp)->maxsize) {
00172     oldset= *setp;
00173     *setp= qh_setcopy (oldset, sizeA);
00174     qh_setfree (&oldset);
00175     sizep= SETsizeaddr_(*setp);
00176   }
00177   *sizep= size+sizeA+1;   /* memcpy may overwrite */
00178   if (sizeA > 0) 
00179     memcpy((char *)&((*setp)->e[size].p), (char *)&(setA->e[0].p), SETelemsize *(sizeA+1));
00180 } /* setappend_set */
00181 
00182 
00183 /*-<a                             href="qh-set.htm#TOC"
00184   >-------------------------------<a name="setappend2ndlast">-</a>
00185   
00186   qh_setappend2ndlast( setp, newelem )
00187     makes newelem the next to the last element in *setp
00188 
00189   notes:
00190     *setp must have at least one element
00191     newelem must be defined
00192     *setp may be a temp set
00193 
00194   design:
00195     expand *setp if empty or full
00196     move last element of *setp up one
00197     insert newelem
00198 */
00199 void qh_setappend2ndlast(setT **setp, void *newelem) {
00200   int *sizep;
00201   void **endp, **lastp;
00202   
00203   if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
00204     qh_setlarger(setp);
00205     sizep= SETsizeaddr_(*setp);
00206   }
00207   endp= SETelemaddr_(*setp, (*sizep)++ -1, void); /* NULL */
00208   lastp= endp-1;
00209   *(endp++)= *lastp;
00210   *endp= NULL;    /* may overwrite *sizep */
00211   *lastp= newelem;
00212 } /* setappend2ndlast */
00213 
00214 
00215 /*-<a                             href="qh-set.htm#TOC"
00216   >-------------------------------<a name="setcheck">-</a>
00217   
00218   qh_setcheck( set, typename, id ) 
00219     check set for validity
00220     report errors with typename and id
00221 
00222   design:
00223     checks that maxsize, actual size, and NULL terminator agree
00224 */
00225 void qh_setcheck(setT *set, char *tname, int id) {
00226   int maxsize, size;
00227   int waserr= 0;
00228 
00229   if (!set)
00230     return;
00231   SETreturnsize_(set, size);
00232   maxsize= set->maxsize;
00233   if (size > maxsize || !maxsize) {
00234     fprintf (qhmem.ferr, "qhull internal error (qh_setcheck): actual size %d of %s%d is greater than max size %d\n",
00235              size, tname, id, maxsize);
00236     waserr= 1;
00237   }else if (set->e[size].p) {
00238     fprintf (qhmem.ferr, "qhull internal error (qh_setcheck): %s%d (size %d max %d) is not null terminated.\n",
00239              tname, id, maxsize, size-1);
00240     waserr= 1;
00241   }
00242   if (waserr) {
00243     qh_setprint (qhmem.ferr, "ERRONEOUS", set);
00244     qh_errexit (qhmem_ERRqhull, NULL, NULL);
00245   }
00246 } /* setcheck */
00247 
00248 
00249 /*-<a                             href="qh-set.htm#TOC"
00250   >-------------------------------<a name="setcompact">-</a>
00251   
00252   qh_setcompact( set )
00253     remove internal NULLs from an unsorted set
00254 
00255   returns:
00256     updated set
00257 
00258   notes:
00259     set may be NULL
00260     it would be faster to swap tail of set into holes, like qh_setdel
00261 
00262   design:
00263     setup pointers into set
00264     skip NULLs while copying elements to start of set 
00265     update the actual size
00266 */
00267 void qh_setcompact(setT *set) {
00268   int size;
00269   void **destp, **elemp, **endp, **firstp;
00270 
00271   if (!set)
00272     return;
00273   SETreturnsize_(set, size);
00274   destp= elemp= firstp= SETaddr_(set, void);
00275   endp= destp + size;
00276   while (1) {
00277     if (!(*destp++ = *elemp++)) {
00278       destp--;
00279       if (elemp > endp)
00280         break;
00281     }
00282   }
00283   qh_settruncate (set, destp-firstp);
00284 } /* setcompact */
00285 
00286 
00287 /*-<a                             href="qh-set.htm#TOC"
00288   >-------------------------------<a name="setcopy">-</a>
00289   
00290   qh_setcopy( set, extra )
00291     make a copy of a sorted or unsorted set with extra slots
00292 
00293   returns:
00294     new set
00295 
00296   design:
00297     create a newset with extra slots
00298     copy the elements to the newset
00299     
00300 */
00301 setT *qh_setcopy(setT *set, int extra) {
00302   setT *newset;
00303   int size;
00304 
00305   if (extra < 0)
00306     extra= 0;
00307   SETreturnsize_(set, size);
00308   newset= qh_setnew(size+extra);
00309   *SETsizeaddr_(newset)= size+1;    /* memcpy may overwrite */
00310   memcpy((char *)&(newset->e[0].p), (char *)&(set->e[0].p), SETelemsize *(size+1));
00311   return (newset);
00312 } /* setcopy */
00313 
00314 
00315 /*-<a                             href="qh-set.htm#TOC"
00316   >-------------------------------<a name="setdel">-</a>
00317   
00318   qh_setdel( set, oldelem )
00319     delete oldelem from an unsorted set
00320 
00321   returns:
00322     returns oldelem if found
00323     returns NULL otherwise
00324     
00325   notes:
00326     set may be NULL
00327     oldelem must not be NULL;
00328     only deletes one copy of oldelem in set
00329      
00330   design:
00331     locate oldelem
00332     update actual size if it was full
00333     move the last element to the oldelem's location
00334 */
00335 void *qh_setdel(setT *set, void *oldelem) {
00336   void **elemp, **lastp;
00337   int *sizep;
00338 
00339   if (!set)
00340     return NULL;
00341   elemp= SETaddr_(set, void);
00342   while (*elemp != oldelem && *elemp)
00343     elemp++;
00344   if (*elemp) {
00345     sizep= SETsizeaddr_(set);
00346     if (!(*sizep)--)         /*  if was a full set */
00347       *sizep= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */
00348     lastp= SETelemaddr_(set, *sizep-1, void);
00349     *elemp= *lastp;      /* may overwrite itself */
00350     *lastp= NULL;
00351     return oldelem;
00352   }
00353   return NULL;
00354 } /* setdel */
00355 
00356 
00357 /*-<a                             href="qh-set.htm#TOC"
00358   >-------------------------------<a name="setdellast">-</a>
00359   
00360   qh_setdellast( set) 
00361     return last element of set or NULL
00362 
00363   notes:
00364     deletes element from set
00365     set may be NULL
00366 
00367   design:
00368     return NULL if empty
00369     if full set
00370       delete last element and set actual size
00371     else
00372       delete last element and update actual size 
00373 */
00374 void *qh_setdellast(setT *set) {
00375   int setsize;  /* actually, actual_size + 1 */
00376   int maxsize;
00377   int *sizep;
00378   void *returnvalue;
00379   
00380   if (!set || !(set->e[0].p))
00381     return NULL;
00382   sizep= SETsizeaddr_(set);
00383   if ((setsize= *sizep)) {
00384     returnvalue= set->e[setsize - 2].p;
00385     set->e[setsize - 2].p= NULL;
00386     (*sizep)--;
00387   }else {
00388     maxsize= set->maxsize;
00389     returnvalue= set->e[maxsize - 1].p;
00390     set->e[maxsize - 1].p= NULL;
00391     *sizep= maxsize;
00392   }
00393   return returnvalue;
00394 } /* setdellast */
00395 
00396 
00397 /*-<a                             href="qh-set.htm#TOC"
00398   >-------------------------------<a name="setdelnth">-</a>
00399   
00400   qh_setdelnth( set, nth )
00401     deletes nth element from unsorted set 
00402     0 is first element
00403 
00404   returns:
00405     returns the element (needs type conversion)
00406 
00407   notes:
00408     errors if nth invalid
00409 
00410   design:
00411     setup points and check nth
00412     delete nth element and overwrite with last element
00413 */
00414 void *qh_setdelnth(setT *set, int nth) {
00415   void **elemp, **lastp, *elem;
00416   int *sizep;
00417 
00418 
00419   elemp= SETelemaddr_(set, nth, void);
00420   sizep= SETsizeaddr_(set);
00421   if (!(*sizep)--)         /*  if was a full set */
00422     *sizep= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */
00423   if (nth < 0 || nth >= *sizep) {
00424     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
00425     qh_setprint (qhmem.ferr, "", set);
00426     qh_errexit (qhmem_ERRqhull, NULL, NULL);
00427   }
00428   lastp= SETelemaddr_(set, *sizep-1, void);
00429   elem= *elemp;
00430   *elemp= *lastp;      /* may overwrite itself */
00431   *lastp= NULL;
00432   return elem;
00433 } /* setdelnth */
00434 
00435 /*-<a                             href="qh-set.htm#TOC"
00436   >-------------------------------<a name="setdelnthsorted">-</a>
00437   
00438   qh_setdelnthsorted( set, nth )
00439     deletes nth element from sorted set
00440 
00441   returns:
00442     returns the element (use type conversion)
00443   
00444   notes:
00445     errors if nth invalid
00446     
00447   see also: 
00448     setnew_delnthsorted
00449 
00450   design:
00451     setup points and check nth
00452     copy remaining elements down one
00453     update actual size  
00454 */
00455 void *qh_setdelnthsorted(setT *set, int nth) {
00456   void **newp, **oldp, *elem;
00457   int *sizep;
00458 
00459   sizep= SETsizeaddr_(set);
00460   if (nth < 0 || (*sizep && nth >= *sizep-1) || nth >= set->maxsize) {
00461     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
00462     qh_setprint (qhmem.ferr, "", set);
00463     qh_errexit (qhmem_ERRqhull, NULL, NULL);
00464   }
00465   newp= SETelemaddr_(set, nth, void);
00466   elem= *newp;
00467   oldp= newp+1;
00468   while ((*(newp++)= *(oldp++)))
00469     ; /* copy remaining elements and NULL */
00470   if (!(*sizep)--)         /*  if was a full set */
00471     *sizep= set->maxsize;  /*     *sizep= (max size-1)+ 1 */
00472   return elem;
00473 } /* setdelnthsorted */
00474 
00475 
00476 /*-<a                             href="qh-set.htm#TOC"
00477   >-------------------------------<a name="setdelsorted">-</a>
00478   
00479   qh_setdelsorted( set, oldelem )
00480     deletes oldelem from sorted set
00481 
00482   returns:
00483     returns oldelem if it was deleted
00484   
00485   notes:
00486     set may be NULL
00487 
00488   design:
00489     locate oldelem in set
00490     copy remaining elements down one
00491     update actual size  
00492 */
00493 void *qh_setdelsorted(setT *set, void *oldelem) {
00494   void **newp, **oldp;
00495   int *sizep;
00496 
00497   if (!set)
00498     return NULL;
00499   newp= SETaddr_(set, void);
00500   while(*newp != oldelem && *newp)
00501     newp++;
00502   if (*newp) {
00503     oldp= newp+1;
00504     while ((*(newp++)= *(oldp++)))
00505       ; /* copy remaining elements */
00506     sizep= SETsizeaddr_(set);
00507     if (!(*sizep)--)    /*  if was a full set */
00508       *sizep= set->maxsize;  /*     *sizep= (max size-1)+ 1 */
00509     return oldelem;
00510   }
00511   return NULL;
00512 } /* setdelsorted */
00513 
00514 
00515 /*-<a                             href="qh-set.htm#TOC"
00516   >-------------------------------<a name="setduplicate">-</a>
00517   
00518   qh_setduplicate( set, elemsize )
00519     duplicate a set of elemsize elements
00520 
00521   notes:
00522     use setcopy if retaining old elements
00523 
00524   design:
00525     create a new set
00526     for each elem of the old set
00527       create a newelem
00528       append newelem to newset
00529 */
00530 setT *qh_setduplicate (setT *set, int elemsize) {
00531   void          *elem, **elemp, *newElem;
00532   setT          *newSet;
00533   int           size;
00534   
00535   if (!(size= qh_setsize (set)))
00536     return NULL;
00537   newSet= qh_setnew (size);
00538   FOREACHelem_(set) {
00539     newElem= qh_memalloc (elemsize);
00540     memcpy (newElem, elem, elemsize);
00541     qh_setappend (&newSet, newElem);
00542   }
00543   return newSet;
00544 } /* setduplicate */
00545 
00546 
00547 /*-<a                             href="qh-set.htm#TOC"
00548   >-------------------------------<a name="setequal">-</a>
00549   
00550   qh_setequal(  )
00551     returns 1 if two sorted sets are equal, otherwise returns 0
00552 
00553   notes:
00554     either set may be NULL
00555 
00556   design:
00557     check size of each set
00558     setup pointers
00559     compare elements of each set
00560 */
00561 int qh_setequal(setT *setA, setT *setB) {
00562   void **elemAp, **elemBp;
00563   int sizeA, sizeB;
00564   
00565   SETreturnsize_(setA, sizeA);
00566   SETreturnsize_(setB, sizeB);
00567   if (sizeA != sizeB)
00568     return 0;
00569   if (!sizeA)
00570     return 1;
00571   elemAp= SETaddr_(setA, void);
00572   elemBp= SETaddr_(setB, void);
00573   if (!memcmp((char *)elemAp, (char *)elemBp, sizeA*SETelemsize))
00574     return 1;
00575   return 0;
00576 } /* setequal */
00577 
00578 
00579 /*-<a                             href="qh-set.htm#TOC"
00580   >-------------------------------<a name="setequal_except">-</a>
00581   
00582   qh_setequal_except( setA, skipelemA, setB, skipelemB )
00583     returns 1 if sorted setA and setB are equal except for skipelemA & B
00584 
00585   returns:
00586     false if either skipelemA or skipelemB are missing
00587   
00588   notes:
00589     neither set may be NULL
00590 
00591     if skipelemB is NULL, 
00592       can skip any one element of setB
00593 
00594   design:
00595     setup pointers
00596     search for skipelemA, skipelemB, and mismatches
00597     check results
00598 */
00599 int qh_setequal_except (setT *setA, void *skipelemA, setT *setB, void *skipelemB) {
00600   void **elemA, **elemB;
00601   int skip=0;
00602 
00603   elemA= SETaddr_(setA, void);
00604   elemB= SETaddr_(setB, void);
00605   while (1) {
00606     if (*elemA == skipelemA) {
00607       skip++;
00608       elemA++;
00609     }
00610     if (skipelemB) {
00611       if (*elemB == skipelemB) {
00612         skip++;
00613         elemB++;
00614       }
00615     }else if (*elemA != *elemB) {
00616       skip++;
00617       if (!(skipelemB= *elemB++))
00618         return 0;
00619     }
00620     if (!*elemA)
00621       break;
00622     if (*elemA++ != *elemB++) 
00623       return 0;
00624   }
00625   if (skip != 2 || *elemB)
00626     return 0;
00627   return 1;
00628 } /* setequal_except */
00629   
00630 
00631 /*-<a                             href="qh-set.htm#TOC"
00632   >-------------------------------<a name="setequal_skip">-</a>
00633   
00634   qh_setequal_skip( setA, skipA, setB, skipB )
00635     returns 1 if sorted setA and setB are equal except for elements skipA & B
00636 
00637   returns:
00638     false if different size
00639 
00640   notes:
00641     neither set may be NULL
00642 
00643   design:
00644     setup pointers
00645     search for mismatches while skipping skipA and skipB
00646 */
00647 int qh_setequal_skip (setT *setA, int skipA, setT *setB, int skipB) {
00648   void **elemA, **elemB, **skipAp, **skipBp;
00649 
00650   elemA= SETaddr_(setA, void);
00651   elemB= SETaddr_(setB, void);
00652   skipAp= SETelemaddr_(setA, skipA, void);
00653   skipBp= SETelemaddr_(setB, skipB, void);
00654   while (1) {
00655     if (elemA == skipAp)
00656       elemA++;
00657     if (elemB == skipBp)
00658       elemB++;
00659     if (!*elemA)
00660       break;
00661     if (*elemA++ != *elemB++) 
00662       return 0;
00663   }
00664   if (*elemB)
00665     return 0;
00666   return 1;
00667 } /* setequal_skip */
00668   
00669 
00670 /*-<a                             href="qh-set.htm#TOC"
00671   >-------------------------------<a name="setfree">-</a>
00672   
00673   qh_setfree( setp )
00674     frees the space occupied by a sorted or unsorted set
00675 
00676   returns:
00677     sets setp to NULL
00678     
00679   notes:
00680     set may be NULL
00681 
00682   design:
00683     free array
00684     free set
00685 */
00686 void qh_setfree(setT **setp) {
00687   int size;
00688   void **freelistp;  /* used !qh_NOmem */
00689   
00690   if (*setp) {
00691     size= sizeof(setT) + ((*setp)->maxsize)*SETelemsize; 
00692     if (size <= qhmem.LASTsize) {
00693       qh_memfree_(*setp, size, freelistp);
00694     }else
00695       qh_memfree (*setp, size);
00696     *setp= NULL;
00697   }
00698 } /* setfree */
00699 
00700 
00701 /*-<a                             href="qh-set.htm#TOC"
00702   >-------------------------------<a name="setfree2">-</a>
00703   
00704   qh_setfree2( setp, elemsize )
00705     frees the space occupied by a set and its elements
00706 
00707   notes:
00708     set may be NULL
00709 
00710   design:
00711     free each element
00712     free set 
00713 */
00714 void qh_setfree2 (setT **setp, int elemsize) {
00715   void          *elem, **elemp;
00716   
00717   FOREACHelem_(*setp)
00718     qh_memfree (elem, elemsize);
00719   qh_setfree (setp);
00720 } /* setfree2 */
00721 
00722 
00723       
00724 /*-<a                             href="qh-set.htm#TOC"
00725   >-------------------------------<a name="setfreelong">-</a>
00726   
00727   qh_setfreelong( setp )
00728     frees a set only if it's in long memory
00729 
00730   returns:
00731     sets setp to NULL if it is freed
00732     
00733   notes:
00734     set may be NULL
00735 
00736   design:
00737     if set is large
00738       free it    
00739 */
00740 void qh_setfreelong(setT **setp) {
00741   int size;
00742   
00743   if (*setp) {
00744     size= sizeof(setT) + ((*setp)->maxsize)*SETelemsize; 
00745     if (size > qhmem.LASTsize) {
00746       qh_memfree (*setp, size);
00747       *setp= NULL;
00748     }
00749   }
00750 } /* setfreelong */
00751 
00752 
00753 /*-<a                             href="qh-set.htm#TOC"
00754   >-------------------------------<a name="setin">-</a>
00755   
00756   qh_setin( set, setelem )
00757     returns 1 if setelem is in a set, 0 otherwise
00758 
00759   notes:
00760     set may be NULL or unsorted
00761 
00762   design:
00763     scans set for setelem
00764 */
00765 int qh_setin(setT *set, void *setelem) {
00766   void *elem, **elemp;
00767 
00768   FOREACHelem_(set) {
00769     if (elem == setelem)
00770       return 1;
00771   }
00772   return 0;
00773 } /* setin */
00774 
00775 
00776 /*-<a                             href="qh-set.htm#TOC"
00777   >-------------------------------<a name="setindex">-</a>
00778   
00779   qh_setindex( set, atelem )
00780     returns the index of atelem in set.   
00781     returns -1, if not in set or maxsize wrong
00782 
00783   notes:
00784     set may be NULL and may contain nulls.
00785 
00786   design:
00787     checks maxsize
00788     scans set for atelem
00789 */
00790 int qh_setindex(setT *set, void *atelem) {
00791   void **elem;
00792   int size, i;
00793 
00794   SETreturnsize_(set, size);
00795   if (size > set->maxsize)
00796     return -1;
00797   elem= SETaddr_(set, void);
00798   for (i=0; i < size; i++) {
00799     if (*elem++ == atelem)
00800       return i;
00801   }
00802   return -1;
00803 } /* setindex */
00804 
00805 
00806 /*-<a                             href="qh-set.htm#TOC"
00807   >-------------------------------<a name="setlarger">-</a>
00808   
00809   qh_setlarger( oldsetp )
00810     returns a larger set that contains all elements of *oldsetp
00811 
00812   notes:
00813     the set is at least twice as large
00814     if temp set, updates qhmem.tempstack
00815 
00816   design:
00817     creates a new set
00818     copies the old set to the new set
00819     updates pointers in tempstack
00820     deletes the old set
00821 */
00822 void qh_setlarger(setT **oldsetp) {
00823   int size= 1, *sizep;
00824   setT *newset, *set, **setp, *oldset;
00825   void **oldp, **newp;
00826 
00827   if (*oldsetp) {
00828     oldset= *oldsetp;
00829     SETreturnsize_(oldset, size);
00830     qhmem.cntlarger++;
00831     qhmem.totlarger += size+1;
00832     newset= qh_setnew(2 * size);
00833     oldp= SETaddr_(oldset, void);
00834     newp= SETaddr_(newset, void);
00835     memcpy((char *)newp, (char *)oldp, (size+1) * SETelemsize);
00836     sizep= SETsizeaddr_(newset);
00837     *sizep= size+1;
00838     FOREACHset_((setT *)qhmem.tempstack) {
00839       if (set == oldset)
00840         *(setp-1)= newset;
00841     }
00842     qh_setfree(oldsetp);
00843   }else 
00844     newset= qh_setnew(3);
00845   *oldsetp= newset;
00846 } /* setlarger */
00847 
00848 
00849 /*-<a                             href="qh-set.htm#TOC"
00850   >-------------------------------<a name="setlast">-</a>
00851   
00852   qh_setlast(  )
00853     return last element of set or NULL (use type conversion)
00854 
00855   notes:
00856     set may be NULL
00857 
00858   design:
00859     return last element  
00860 */
00861 void *qh_setlast(setT *set) {
00862   int size;
00863 
00864   if (set) {
00865     size= *SETsizeaddr_(set);
00866     if (!size) 
00867       return SETelem_(set, set->maxsize - 1);
00868     else if (size > 1)
00869       return SETelem_(set, size - 2);
00870   }
00871   return NULL;
00872 } /* setlast */
00873 
00874 
00875 /*-<a                             href="qh-set.htm#TOC"
00876   >-------------------------------<a name="setnew">-</a>
00877   
00878   qh_setnew( setsize )
00879     creates and allocates space for a set
00880 
00881   notes:
00882     setsize means the number of elements (NOT including the NULL terminator)
00883     use qh_settemp/qh_setfreetemp if set is temporary
00884 
00885   design:
00886     allocate memory for set
00887     roundup memory if small set
00888     initialize as empty set
00889 */
00890 setT *qh_setnew(int setsize) {
00891   setT *set;
00892   int sizereceived; /* used !qh_NOmem */
00893   int size;
00894   void **freelistp; /* used !qh_NOmem */
00895 
00896   if (!setsize)
00897     setsize++;
00898   size= sizeof(setT) + setsize * SETelemsize;
00899   if ((unsigned) size <= (unsigned) qhmem.LASTsize) {
00900     qh_memalloc_(size, freelistp, set, setT);
00901 #ifndef qh_NOmem
00902     sizereceived= qhmem.sizetable[ qhmem.indextable[size]];
00903     if (sizereceived > size) 
00904       setsize += (sizereceived - size)/SETelemsize;
00905 #endif
00906   }else
00907     set= (setT*)qh_memalloc (size);
00908   set->maxsize= setsize;
00909   set->e[setsize].i= 1;
00910   set->e[0].p= NULL;
00911   return (set);
00912 } /* setnew */
00913 
00914 
00915 /*-<a                             href="qh-set.htm#TOC"
00916   >-------------------------------<a name="setnew_delnthsorted">-</a>
00917   
00918   qh_setnew_delnthsorted( set, size, nth, prepend )
00919     creates a sorted set not containing nth element
00920     if prepend, the first prepend elements are undefined
00921 
00922   notes:
00923     set must be defined
00924     checks nth
00925     see also: setdelnthsorted
00926 
00927   design:
00928     create new set
00929     setup pointers and allocate room for prepend'ed entries
00930     append head of old set to new set
00931     append tail of old set to new set
00932 */
00933 setT *qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend) {
00934   setT *newset;
00935   void **oldp, **newp;
00936   int tailsize= size - nth -1, newsize;
00937 
00938   if (tailsize < 0) {
00939     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
00940     qh_setprint (qhmem.ferr, "", set);
00941     qh_errexit (qhmem_ERRqhull, NULL, NULL);
00942   }
00943   newsize= size-1 + prepend;
00944   newset= qh_setnew(newsize);
00945   newset->e[newset->maxsize].i= newsize+1;  /* may be overwritten */
00946   oldp= SETaddr_(set, void);
00947   newp= SETaddr_(newset, void) + prepend;
00948   switch (nth) {
00949   case 0:
00950     break;
00951   case 1:
00952     *(newp++)= *oldp++;
00953     break;
00954   case 2:
00955     *(newp++)= *oldp++;
00956     *(newp++)= *oldp++;
00957     break;
00958   case 3:
00959     *(newp++)= *oldp++;
00960     *(newp++)= *oldp++;
00961     *(newp++)= *oldp++;
00962     break;
00963   case 4:
00964     *(newp++)= *oldp++;
00965     *(newp++)= *oldp++;
00966     *(newp++)= *oldp++;
00967     *(newp++)= *oldp++;
00968     break;
00969   default:
00970     memcpy((char *)newp, (char *)oldp, nth * SETelemsize);
00971     newp += nth;
00972     oldp += nth;
00973     break;
00974   }
00975   oldp++;
00976   switch (tailsize) {
00977   case 0:
00978     break;
00979   case 1:
00980     *(newp++)= *oldp++;
00981     break;
00982   case 2:
00983     *(newp++)= *oldp++;
00984     *(newp++)= *oldp++;
00985     break;
00986   case 3:
00987     *(newp++)= *oldp++;
00988     *(newp++)= *oldp++;
00989     *(newp++)= *oldp++;
00990     break;
00991   case 4:
00992     *(newp++)= *oldp++;
00993     *(newp++)= *oldp++;
00994     *(newp++)= *oldp++;
00995     *(newp++)= *oldp++;
00996     break;
00997   default:
00998     memcpy((char *)newp, (char *)oldp, tailsize * SETelemsize);
00999     newp += tailsize;
01000   }
01001   *newp= NULL;
01002   return(newset);
01003 } /* setnew_delnthsorted */
01004 
01005 
01006 /*-<a                             href="qh-set.htm#TOC"
01007   >-------------------------------<a name="setprint">-</a>
01008   
01009   qh_setprint( fp, string, set )
01010     print set elements to fp with identifying string
01011 
01012   notes:
01013     never errors
01014 */
01015 void qh_setprint(FILE *fp, char* string, setT *set) {
01016   int size, k;
01017 
01018   if (!set)
01019     fprintf (fp, "%s set is null\n", string);
01020   else {
01021     SETreturnsize_(set, size);
01022     fprintf (fp, "%s set=%p maxsize=%d size=%d elems=",
01023              string, set, set->maxsize, size);
01024     if (size > set->maxsize)
01025       size= set->maxsize+1;
01026     for (k=0; k < size; k++)
01027       fprintf(fp, " %p", set->e[k].p);
01028     fprintf(fp, "\n");
01029   }
01030 } /* setprint */
01031 
01032 /*-<a                             href="qh-set.htm#TOC"
01033   >-------------------------------<a name="setreplace">-</a>
01034   
01035   qh_setreplace( set, oldelem, newelem )
01036     replaces oldelem in set with newelem
01037 
01038   notes:
01039     errors if oldelem not in the set
01040     newelem may be NULL, but it turns the set into an indexed set (no FOREACH)
01041 
01042   design:
01043     find oldelem
01044     replace with newelem
01045 */
01046 void qh_setreplace(setT *set, void *oldelem, void *newelem) {
01047   void **elemp;
01048   
01049   elemp= SETaddr_(set, void);
01050   while(*elemp != oldelem && *elemp)
01051     elemp++;
01052   if (*elemp)
01053     *elemp= newelem;
01054   else {
01055     fprintf (qhmem.ferr, "qhull internal error (qh_setreplace): elem %p not found in set\n",
01056        oldelem);
01057     qh_setprint (qhmem.ferr, "", set);
01058     qh_errexit (qhmem_ERRqhull, NULL, NULL);
01059   }
01060 } /* setreplace */
01061 
01062 
01063 /*-<a                             href="qh-set.htm#TOC"
01064   >-------------------------------<a name="setsize">-</a>
01065   
01066   qh_setsize( set )
01067     returns the size of a set
01068 
01069   notes:
01070     errors if set's maxsize is incorrect
01071     same as SETreturnsize_(set)
01072 
01073   design:
01074     determine actual size of set from maxsize
01075 */
01076 int qh_setsize(setT *set) {
01077   int size, *sizep;
01078   
01079   if (!set)
01080     return (0);
01081   sizep= SETsizeaddr_(set);
01082   if ((size= *sizep)) {
01083     size--;
01084     if (size > set->maxsize) {
01085       fprintf (qhmem.ferr, "qhull internal error (qh_setsize): current set size %d is greater than maximum size %d\n",
01086                size, set->maxsize);
01087       qh_setprint (qhmem.ferr, "set: ", set);
01088       qh_errexit (qhmem_ERRqhull, NULL, NULL);
01089     }
01090   }else
01091     size= set->maxsize;
01092   return size;
01093 } /* setsize */
01094 
01095 /*-<a                             href="qh-set.htm#TOC"
01096   >-------------------------------<a name="settemp">-</a>
01097   
01098   qh_settemp( setsize )
01099     return a stacked, temporary set of upto setsize elements
01100 
01101   notes:
01102     use settempfree or settempfree_all to release from qhmem.tempstack
01103     see also qh_setnew
01104 
01105   design:
01106     allocate set
01107     append to qhmem.tempstack
01108     
01109 */
01110 setT *qh_settemp(int setsize) {
01111   setT *newset;
01112   
01113   newset= qh_setnew (setsize);
01114   qh_setappend ((setT **)&qhmem.tempstack, newset);
01115   if (qhmem.IStracing >= 5)
01116     fprintf (qhmem.ferr, "qh_settemp: temp set %p of %d elements, depth %d\n",
01117        newset, newset->maxsize, qh_setsize ((setT*)qhmem.tempstack));
01118   return newset;
01119 } /* settemp */
01120 
01121 /*-<a                             href="qh-set.htm#TOC"
01122   >-------------------------------<a name="settempfree">-</a>
01123   
01124   qh_settempfree( set )
01125     free temporary set at top of qhmem.tempstack
01126 
01127   notes:
01128     nop if set is NULL
01129     errors if set not from previous   qh_settemp
01130   
01131   to locate errors:
01132     use 'T2' to find source and then find mis-matching qh_settemp
01133 
01134   design:
01135     check top of qhmem.tempstack
01136     free it
01137 */
01138 void qh_settempfree(setT **set) {
01139   setT *stackedset;
01140 
01141   if (!*set)
01142     return;
01143   stackedset= qh_settemppop ();
01144   if (stackedset != *set) {
01145     qh_settemppush(stackedset);
01146     fprintf (qhmem.ferr, "qhull internal error (qh_settempfree): set %p (size %d) was not last temporary allocated (depth %d, set %p, size %d)\n",
01147              *set, qh_setsize(*set), qh_setsize((setT*)qhmem.tempstack)+1,
01148              stackedset, qh_setsize(stackedset));
01149     qh_errexit (qhmem_ERRqhull, NULL, NULL);
01150   }
01151   qh_setfree (set);
01152 } /* settempfree */
01153 
01154 /*-<a                             href="qh-set.htm#TOC"
01155   >-------------------------------<a name="settempfree_all">-</a>
01156   
01157   qh_settempfree_all(  )
01158     free all temporary sets in qhmem.tempstack
01159 
01160   design:
01161     for each set in tempstack
01162       free set
01163     free qhmem.tempstack
01164 */
01165 void qh_settempfree_all(void) {
01166   setT *set, **setp;
01167 
01168   FOREACHset_((setT *)qhmem.tempstack) 
01169     qh_setfree(&set);
01170   qh_setfree((setT **)&qhmem.tempstack);
01171 } /* settempfree_all */
01172 
01173 /*-<a                             href="qh-set.htm#TOC"
01174   >-------------------------------<a name="settemppop">-</a>
01175   
01176   qh_settemppop(  )
01177     pop and return temporary set from qhmem.tempstack 
01178 
01179   notes:
01180     the returned set is permanent
01181     
01182   design:
01183     pop and check top of qhmem.tempstack
01184 */
01185 setT *qh_settemppop(void) {
01186   setT *stackedset;
01187   
01188   stackedset= (setT*)qh_setdellast((setT *)qhmem.tempstack);
01189   if (!stackedset) {
01190     fprintf (qhmem.ferr, "qhull internal error (qh_settemppop): pop from empty temporary stack\n");
01191     qh_errexit (qhmem_ERRqhull, NULL, NULL);
01192   }
01193   if (qhmem.IStracing >= 5)
01194     fprintf (qhmem.ferr, "qh_settemppop: depth %d temp set %p of %d elements\n",
01195        qh_setsize((setT*)qhmem.tempstack)+1, stackedset, qh_setsize(stackedset));
01196   return stackedset;
01197 } /* settemppop */
01198 
01199 /*-<a                             href="qh-set.htm#TOC"
01200   >-------------------------------<a name="settemppush">-</a>
01201   
01202   qh_settemppush( set )
01203     push temporary set unto qhmem.tempstack (makes it temporary)
01204 
01205   notes:
01206     duplicates settemp() for tracing
01207 
01208   design:
01209     append set to tempstack  
01210 */
01211 void qh_settemppush(setT *set) {
01212   
01213   qh_setappend ((setT**)&qhmem.tempstack, set);
01214   if (qhmem.IStracing >= 5)
01215     fprintf (qhmem.ferr, "qh_settemppush: depth %d temp set %p of %d elements\n",
01216     qh_setsize((setT*)qhmem.tempstack), set, qh_setsize(set));
01217 } /* settemppush */
01218 
01219  
01220 /*-<a                             href="qh-set.htm#TOC"
01221   >-------------------------------<a name="settruncate">-</a>
01222   
01223   qh_settruncate( set, size )
01224     truncate set to size elements
01225 
01226   notes:
01227     set must be defined
01228 
01229   design:
01230     check size
01231     update actual size of set
01232 */
01233 void qh_settruncate (setT *set, int size) {
01234 
01235   if (size < 0 || size > set->maxsize) {
01236     fprintf (qhmem.ferr, "qhull internal error (qh_settruncate): size %d out of bounds for set:\n", size);
01237     qh_setprint (qhmem.ferr, "", set);
01238     qh_errexit (qhmem_ERRqhull, NULL, NULL);
01239   }
01240   set->e[set->maxsize].i= size+1;   /* maybe overwritten */
01241   set->e[size].p= NULL;
01242 } /* settruncate */
01243     
01244 /*-<a                             href="qh-set.htm#TOC"
01245   >-------------------------------<a name="setunique">-</a>
01246   
01247   qh_setunique( set, elem )
01248     add elem to unsorted set unless it is already in set
01249 
01250   notes:
01251     returns 1 if it is appended
01252 
01253   design:
01254     if elem not in set
01255       append elem to set
01256 */
01257 int qh_setunique (setT **set, void *elem) {
01258 
01259   if (!qh_setin (*set, elem)) {
01260     qh_setappend (set, elem);
01261     return 1;
01262   }
01263   return 0;
01264 } /* setunique */
01265     
01266 /*-<a                             href="qh-set.htm#TOC"
01267   >-------------------------------<a name="setzero">-</a>
01268   
01269   qh_setzero( set, index, size )
01270     zero elements from index on
01271     set actual size of set to size
01272 
01273   notes:
01274     set must be defined
01275     the set becomes an indexed set (can not use FOREACH...)
01276   
01277   see also:
01278     qh_settruncate
01279     
01280   design:
01281     check index and size
01282     update actual size
01283     zero elements starting at e[index]   
01284 */
01285 void qh_setzero (setT *set, int index, int size) {
01286   int count;
01287 
01288   if (index < 0 || index >= size || size > set->maxsize) {
01289     fprintf (qhmem.ferr, "qhull internal error (qh_setzero): index %d or size %d out of bounds for set:\n", index, size);
01290     qh_setprint (qhmem.ferr, "", set);
01291     qh_errexit (qhmem_ERRqhull, NULL, NULL);
01292   }
01293   set->e[set->maxsize].i=  size+1;  /* may be overwritten */
01294   count= size - index + 1;   /* +1 for NULL terminator */
01295   memset ((char *)SETelemaddr_(set, index, void), 0, count * SETelemsize);
01296 } /* setzero */
01297 
01298
 
Powered by Plone

This site conforms to the following standards: