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

libqhull
Author(s): Robert Krug
autogenerated on Tue Jun 18 2013 12:38:50