1 /*<html><pre>  -<a                             href="qh-set.htm"
2   >-------------------------------</a><a name="TOP">-</a>
3 
4    qset.c
5    implements set manipulations needed for quickhull
6 
7    see qh-set.htm and qset.h
8 
9    copyright (c) 1993-2003 The Geometry Center
10 */
11 
12 #include <stdio.h>
13 #include <string.h>
14 /*** uncomment here and qhull_a.h
15      if string.h does not define memcpy()
16 #include <memory.h>
17 */
18 #include "qset.h"
19 #include "mem.h"
20 
21 #ifndef qhDEFqhull
22 typedef struct ridgeT ridgeT;
23 typedef struct facetT facetT;
24 void    qh_errexit(int exitcode, facetT *, ridgeT *);
25 #endif
26 
27 /*=============== internal macros ===========================*/
28 
29 /*-<a                             href="qh-set.htm#TOC"
30   >-------------------------------<a name="SETsizeaddr_">-</a>
31 
32   SETsizeaddr_(set)
33     return pointer to actual size+1 of set (set CANNOT be NULL!!)
34 
35   notes:
36     *SETsizeaddr==NULL or e[*SETsizeaddr-1].p==NULL
37 */
38 #define SETsizeaddr_(set) (&((set)->e[(set)->maxsize].i))
39 
40 /*============ functions in alphabetical order ===================*/
41 
42 /*-<a                             href="qh-set.htm#TOC"
43   >--------------------------------<a name="setaddnth">-</a>
44 
45   qh_setaddnth( setp, nth, newelem)
46     adds newelem as n'th element of sorted or unsorted *setp
47 
48   notes:
49     *setp and newelem must be defined
50     *setp may be a temp set
51     nth=0 is first element
52     errors if nth is out of bounds
53 
54   design:
55     expand *setp if empty or full
56     move tail of *setp up one
57     insert newelem
58 */
qh_setaddnth(setT ** setp,int nth,void * newelem)59 void qh_setaddnth(setT **setp, int nth, void *newelem) {
60   int *sizep, oldsize, i;
61   void **oldp, **newp;
62 
63   if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
64     qh_setlarger(setp);
65     sizep= SETsizeaddr_(*setp);
66   }
67   oldsize= *sizep - 1;
68   if (nth < 0 || nth > oldsize) {
69     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
70     qh_setprint (qhmem.ferr, "", *setp);
71     qh_errexit (qhmem_ERRqhull, NULL, NULL);
72   }
73   (*sizep)++;
74   oldp= SETelemaddr_(*setp, oldsize, void);   /* NULL */
75   newp= oldp+1;
76   for (i= oldsize-nth+1; i--; )  /* move at least NULL  */
77     *(newp--)= *(oldp--);       /* may overwrite *sizep */
78   *newp= newelem;
79 } /* setaddnth */
80 
81 
82 /*-<a                              href="qh-set.htm#TOC"
83   >--------------------------------<a name="setaddsorted">-</a>
84 
85   setaddsorted( setp, newelem )
86     adds an newelem into sorted *setp
87 
88   notes:
89     *setp and newelem must be defined
90     *setp may be a temp set
91     nop if newelem already in set
92 
93   design:
94     find newelem's position in *setp
95     insert newelem
96 */
qh_setaddsorted(setT ** setp,void * newelem)97 void qh_setaddsorted(setT **setp, void *newelem) {
98   int newindex=0;
99   void *elem, **elemp;
100 
101   FOREACHelem_(*setp) {          /* could use binary search instead */
102     if (elem < newelem)
103       newindex++;
104     else if (elem == newelem)
105       return;
106     else
107       break;
108   }
109   qh_setaddnth(setp, newindex, newelem);
110 } /* setaddsorted */
111 
112 
113 /*-<a                             href="qh-set.htm#TOC"
114   >-------------------------------<a name="setappend">-</a>
115 
116   qh_setappend( setp, newelem)
117     append newelem to *setp
118 
119   notes:
120     *setp may be a temp set
121     *setp and newelem may be NULL
122 
123   design:
124     expand *setp if empty or full
125     append newelem to *setp
126 
127 */
qh_setappend(setT ** setp,void * newelem)128 void qh_setappend(setT **setp, void *newelem) {
129   int *sizep;
130   void **endp;
131 
132   if (!newelem)
133     return;
134   if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
135     qh_setlarger(setp);
136     sizep= SETsizeaddr_(*setp);
137   }
138   *(endp= &((*setp)->e[(*sizep)++ - 1].p))= newelem;
139   *(++endp)= NULL;
140 } /* setappend */
141 
142 /*-<a                             href="qh-set.htm#TOC"
143   >-------------------------------<a name="setappend_set">-</a>
144 
145   qh_setappend_set( setp, setA)
146     appends setA to *setp
147 
148   notes:
149     *setp can not be a temp set
150     *setp and setA may be NULL
151 
152   design:
153     setup for copy
154     expand *setp if it is too small
155     append all elements of setA to *setp
156 */
qh_setappend_set(setT ** setp,setT * setA)157 void qh_setappend_set(setT **setp, setT *setA) {
158   int *sizep, sizeA, size;
159   setT *oldset;
160 
161   if (!setA)
162     return;
163   SETreturnsize_(setA, sizeA);
164   if (!*setp)
165     *setp= qh_setnew (sizeA);
166   sizep= SETsizeaddr_(*setp);
167   if (!(size= *sizep))
168     size= (*setp)->maxsize;
169   else
170     size--;
171   if (size + sizeA > (*setp)->maxsize) {
172     oldset= *setp;
173     *setp= qh_setcopy (oldset, sizeA);
174     qh_setfree (&oldset);
175     sizep= SETsizeaddr_(*setp);
176   }
177   *sizep= size+sizeA+1;   /* memcpy may overwrite */
178   if (sizeA > 0)
179     memcpy((char *)&((*setp)->e[size].p), (char *)&(setA->e[0].p), SETelemsize *(sizeA+1));
180 } /* setappend_set */
181 
182 
183 /*-<a                             href="qh-set.htm#TOC"
184   >-------------------------------<a name="setappend2ndlast">-</a>
185 
186   qh_setappend2ndlast( setp, newelem )
187     makes newelem the next to the last element in *setp
188 
189   notes:
190     *setp must have at least one element
191     newelem must be defined
192     *setp may be a temp set
193 
194   design:
195     expand *setp if empty or full
196     move last element of *setp up one
197     insert newelem
198 */
qh_setappend2ndlast(setT ** setp,void * newelem)199 void qh_setappend2ndlast(setT **setp, void *newelem) {
200   int *sizep;
201   void **endp, **lastp;
202 
203   if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
204     qh_setlarger(setp);
205     sizep= SETsizeaddr_(*setp);
206   }
207   endp= SETelemaddr_(*setp, (*sizep)++ -1, void); /* NULL */
208   lastp= endp-1;
209   *(endp++)= *lastp;
210   *endp= NULL;    /* may overwrite *sizep */
211   *lastp= newelem;
212 } /* setappend2ndlast */
213 
214 
215 /*-<a                             href="qh-set.htm#TOC"
216   >-------------------------------<a name="setcheck">-</a>
217 
218   qh_setcheck( set, typename, id )
219     check set for validity
220     report errors with typename and id
221 
222   design:
223     checks that maxsize, actual size, and NULL terminator agree
224 */
qh_setcheck(setT * set,char * tname,int id)225 void qh_setcheck(setT *set, char *tname, int id) {
226   int maxsize, size;
227   int waserr= 0;
228 
229   if (!set)
230     return;
231   SETreturnsize_(set, size);
232   maxsize= set->maxsize;
233   if (size > maxsize || !maxsize) {
234     fprintf (qhmem.ferr, "qhull internal error (qh_setcheck): actual size %d of %s%d is greater than max size %d\n",
235 	     size, tname, id, maxsize);
236     waserr= 1;
237   }else if (set->e[size].p) {
238     fprintf (qhmem.ferr, "qhull internal error (qh_setcheck): %s%d (size %d max %d) is not null terminated.\n",
239 	     tname, id, maxsize, size-1);
240     waserr= 1;
241   }
242   if (waserr) {
243     qh_setprint (qhmem.ferr, "ERRONEOUS", set);
244     qh_errexit (qhmem_ERRqhull, NULL, NULL);
245   }
246 } /* setcheck */
247 
248 
249 /*-<a                             href="qh-set.htm#TOC"
250   >-------------------------------<a name="setcompact">-</a>
251 
252   qh_setcompact( set )
253     remove internal NULLs from an unsorted set
254 
255   returns:
256     updated set
257 
258   notes:
259     set may be NULL
260     it would be faster to swap tail of set into holes, like qh_setdel
261 
262   design:
263     setup pointers into set
264     skip NULLs while copying elements to start of set
265     update the actual size
266 */
qh_setcompact(setT * set)267 void qh_setcompact(setT *set) {
268   int size;
269   void **destp, **elemp, **endp, **firstp;
270 
271   if (!set)
272     return;
273   SETreturnsize_(set, size);
274   destp= elemp= firstp= SETaddr_(set, void);
275   endp= destp + size;
276   while (1) {
277     if (!(*destp++ = *elemp++)) {
278       destp--;
279       if (elemp > endp)
280 	break;
281     }
282   }
283   qh_settruncate (set, destp-firstp);
284 } /* setcompact */
285 
286 
287 /*-<a                             href="qh-set.htm#TOC"
288   >-------------------------------<a name="setcopy">-</a>
289 
290   qh_setcopy( set, extra )
291     make a copy of a sorted or unsorted set with extra slots
292 
293   returns:
294     new set
295 
296   design:
297     create a newset with extra slots
298     copy the elements to the newset
299 
300 */
qh_setcopy(setT * set,int extra)301 setT *qh_setcopy(setT *set, int extra) {
302   setT *newset;
303   int size;
304 
305   if (extra < 0)
306     extra= 0;
307   SETreturnsize_(set, size);
308   newset= qh_setnew(size+extra);
309   *SETsizeaddr_(newset)= size+1;    /* memcpy may overwrite */
310   memcpy((char *)&(newset->e[0].p), (char *)&(set->e[0].p), SETelemsize *(size+1));
311   return (newset);
312 } /* setcopy */
313 
314 
315 /*-<a                             href="qh-set.htm#TOC"
316   >-------------------------------<a name="setdel">-</a>
317 
318   qh_setdel( set, oldelem )
319     delete oldelem from an unsorted set
320 
321   returns:
322     returns oldelem if found
323     returns NULL otherwise
324 
325   notes:
326     set may be NULL
327     oldelem must not be NULL;
328     only deletes one copy of oldelem in set
329 
330   design:
331     locate oldelem
332     update actual size if it was full
333     move the last element to the oldelem's location
334 */
qh_setdel(setT * set,void * oldelem)335 void *qh_setdel(setT *set, void *oldelem) {
336   void **elemp, **lastp;
337   int *sizep;
338 
339   if (!set)
340     return NULL;
341   elemp= SETaddr_(set, void);
342   while (*elemp != oldelem && *elemp)
343     elemp++;
344   if (*elemp) {
345     sizep= SETsizeaddr_(set);
346     if (!(*sizep)--)         /*  if was a full set */
347       *sizep= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */
348     lastp= SETelemaddr_(set, *sizep-1, void);
349     *elemp= *lastp;      /* may overwrite itself */
350     *lastp= NULL;
351     return oldelem;
352   }
353   return NULL;
354 } /* setdel */
355 
356 
357 /*-<a                             href="qh-set.htm#TOC"
358   >-------------------------------<a name="setdellast">-</a>
359 
360   qh_setdellast( set)
361     return last element of set or NULL
362 
363   notes:
364     deletes element from set
365     set may be NULL
366 
367   design:
368     return NULL if empty
369     if full set
370       delete last element and set actual size
371     else
372       delete last element and update actual size
373 */
qh_setdellast(setT * set)374 void *qh_setdellast(setT *set) {
375   int setsize;  /* actually, actual_size + 1 */
376   int maxsize;
377   int *sizep;
378   void *returnvalue;
379 
380   if (!set || !(set->e[0].p))
381     return NULL;
382   sizep= SETsizeaddr_(set);
383   if ((setsize= *sizep)) {
384     returnvalue= set->e[setsize - 2].p;
385     set->e[setsize - 2].p= NULL;
386     (*sizep)--;
387   }else {
388     maxsize= set->maxsize;
389     returnvalue= set->e[maxsize - 1].p;
390     set->e[maxsize - 1].p= NULL;
391     *sizep= maxsize;
392   }
393   return returnvalue;
394 } /* setdellast */
395 
396 
397 /*-<a                             href="qh-set.htm#TOC"
398   >-------------------------------<a name="setdelnth">-</a>
399 
400   qh_setdelnth( set, nth )
401     deletes nth element from unsorted set
402     0 is first element
403 
404   returns:
405     returns the element (needs type conversion)
406 
407   notes:
408     errors if nth invalid
409 
410   design:
411     setup points and check nth
412     delete nth element and overwrite with last element
413 */
qh_setdelnth(setT * set,int nth)414 void *qh_setdelnth(setT *set, int nth) {
415   void **elemp, **lastp, *elem;
416   int *sizep;
417 
418 
419   elemp= SETelemaddr_(set, nth, void);
420   sizep= SETsizeaddr_(set);
421   if (!(*sizep)--)         /*  if was a full set */
422     *sizep= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */
423   if (nth < 0 || nth >= *sizep) {
424     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
425     qh_setprint (qhmem.ferr, "", set);
426     qh_errexit (qhmem_ERRqhull, NULL, NULL);
427   }
428   lastp= SETelemaddr_(set, *sizep-1, void);
429   elem= *elemp;
430   *elemp= *lastp;      /* may overwrite itself */
431   *lastp= NULL;
432   return elem;
433 } /* setdelnth */
434 
435 /*-<a                             href="qh-set.htm#TOC"
436   >-------------------------------<a name="setdelnthsorted">-</a>
437 
438   qh_setdelnthsorted( set, nth )
439     deletes nth element from sorted set
440 
441   returns:
442     returns the element (use type conversion)
443 
444   notes:
445     errors if nth invalid
446 
447   see also:
448     setnew_delnthsorted
449 
450   design:
451     setup points and check nth
452     copy remaining elements down one
453     update actual size
454 */
qh_setdelnthsorted(setT * set,int nth)455 void *qh_setdelnthsorted(setT *set, int nth) {
456   void **newp, **oldp, *elem;
457   int *sizep;
458 
459   sizep= SETsizeaddr_(set);
460   if (nth < 0 || (*sizep && nth >= *sizep-1) || nth >= set->maxsize) {
461     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
462     qh_setprint (qhmem.ferr, "", set);
463     qh_errexit (qhmem_ERRqhull, NULL, NULL);
464   }
465   newp= SETelemaddr_(set, nth, void);
466   elem= *newp;
467   oldp= newp+1;
468   while ((*(newp++)= *(oldp++)))
469     ; /* copy remaining elements and NULL */
470   if (!(*sizep)--)         /*  if was a full set */
471     *sizep= set->maxsize;  /*     *sizep= (max size-1)+ 1 */
472   return elem;
473 } /* setdelnthsorted */
474 
475 
476 /*-<a                             href="qh-set.htm#TOC"
477   >-------------------------------<a name="setdelsorted">-</a>
478 
479   qh_setdelsorted( set, oldelem )
480     deletes oldelem from sorted set
481 
482   returns:
483     returns oldelem if it was deleted
484 
485   notes:
486     set may be NULL
487 
488   design:
489     locate oldelem in set
490     copy remaining elements down one
491     update actual size
492 */
qh_setdelsorted(setT * set,void * oldelem)493 void *qh_setdelsorted(setT *set, void *oldelem) {
494   void **newp, **oldp;
495   int *sizep;
496 
497   if (!set)
498     return NULL;
499   newp= SETaddr_(set, void);
500   while(*newp != oldelem && *newp)
501     newp++;
502   if (*newp) {
503     oldp= newp+1;
504     while ((*(newp++)= *(oldp++)))
505       ; /* copy remaining elements */
506     sizep= SETsizeaddr_(set);
507     if (!(*sizep)--)    /*  if was a full set */
508       *sizep= set->maxsize;  /*     *sizep= (max size-1)+ 1 */
509     return oldelem;
510   }
511   return NULL;
512 } /* setdelsorted */
513 
514 
515 /*-<a                             href="qh-set.htm#TOC"
516   >-------------------------------<a name="setduplicate">-</a>
517 
518   qh_setduplicate( set, elemsize )
519     duplicate a set of elemsize elements
520 
521   notes:
522     use setcopy if retaining old elements
523 
524   design:
525     create a new set
526     for each elem of the old set
527       create a newelem
528       append newelem to newset
529 */
qh_setduplicate(setT * set,int elemsize)530 setT *qh_setduplicate (setT *set, int elemsize) {
531   void		*elem, **elemp, *newElem;
532   setT		*newSet;
533   int		size;
534 
535   if (!(size= qh_setsize (set)))
536     return NULL;
537   newSet= qh_setnew (size);
538   FOREACHelem_(set) {
539     newElem= qh_memalloc (elemsize);
540     memcpy (newElem, elem, elemsize);
541     qh_setappend (&newSet, newElem);
542   }
543   return newSet;
544 } /* setduplicate */
545 
546 
547 /*-<a                             href="qh-set.htm#TOC"
548   >-------------------------------<a name="setequal">-</a>
549 
550   qh_setequal(  )
551     returns 1 if two sorted sets are equal, otherwise returns 0
552 
553   notes:
554     either set may be NULL
555 
556   design:
557     check size of each set
558     setup pointers
559     compare elements of each set
560 */
qh_setequal(setT * setA,setT * setB)561 int qh_setequal(setT *setA, setT *setB) {
562   void **elemAp, **elemBp;
563   int sizeA, sizeB;
564 
565   SETreturnsize_(setA, sizeA);
566   SETreturnsize_(setB, sizeB);
567   if (sizeA != sizeB)
568     return 0;
569   if (!sizeA)
570     return 1;
571   elemAp= SETaddr_(setA, void);
572   elemBp= SETaddr_(setB, void);
573   if (!memcmp((char *)elemAp, (char *)elemBp, sizeA*SETelemsize))
574     return 1;
575   return 0;
576 } /* setequal */
577 
578 
579 /*-<a                             href="qh-set.htm#TOC"
580   >-------------------------------<a name="setequal_except">-</a>
581 
582   qh_setequal_except( setA, skipelemA, setB, skipelemB )
583     returns 1 if sorted setA and setB are equal except for skipelemA & B
584 
585   returns:
586     false if either skipelemA or skipelemB are missing
587 
588   notes:
589     neither set may be NULL
590 
591     if skipelemB is NULL,
592       can skip any one element of setB
593 
594   design:
595     setup pointers
596     search for skipelemA, skipelemB, and mismatches
597     check results
598 */
qh_setequal_except(setT * setA,void * skipelemA,setT * setB,void * skipelemB)599 int qh_setequal_except (setT *setA, void *skipelemA, setT *setB, void *skipelemB) {
600   void **elemA, **elemB;
601   int skip=0;
602 
603   elemA= SETaddr_(setA, void);
604   elemB= SETaddr_(setB, void);
605   while (1) {
606     if (*elemA == skipelemA) {
607       skip++;
608       elemA++;
609     }
610     if (skipelemB) {
611       if (*elemB == skipelemB) {
612         skip++;
613         elemB++;
614       }
615     }else if (*elemA != *elemB) {
616       skip++;
617       if (!(skipelemB= *elemB++))
618         return 0;
619     }
620     if (!*elemA)
621       break;
622     if (*elemA++ != *elemB++)
623       return 0;
624   }
625   if (skip != 2 || *elemB)
626     return 0;
627   return 1;
628 } /* setequal_except */
629 
630 
631 /*-<a                             href="qh-set.htm#TOC"
632   >-------------------------------<a name="setequal_skip">-</a>
633 
634   qh_setequal_skip( setA, skipA, setB, skipB )
635     returns 1 if sorted setA and setB are equal except for elements skipA & B
636 
637   returns:
638     false if different size
639 
640   notes:
641     neither set may be NULL
642 
643   design:
644     setup pointers
645     search for mismatches while skipping skipA and skipB
646 */
qh_setequal_skip(setT * setA,int skipA,setT * setB,int skipB)647 int qh_setequal_skip (setT *setA, int skipA, setT *setB, int skipB) {
648   void **elemA, **elemB, **skipAp, **skipBp;
649 
650   elemA= SETaddr_(setA, void);
651   elemB= SETaddr_(setB, void);
652   skipAp= SETelemaddr_(setA, skipA, void);
653   skipBp= SETelemaddr_(setB, skipB, void);
654   while (1) {
655     if (elemA == skipAp)
656       elemA++;
657     if (elemB == skipBp)
658       elemB++;
659     if (!*elemA)
660       break;
661     if (*elemA++ != *elemB++)
662       return 0;
663   }
664   if (*elemB)
665     return 0;
666   return 1;
667 } /* setequal_skip */
668 
669 
670 /*-<a                             href="qh-set.htm#TOC"
671   >-------------------------------<a name="setfree">-</a>
672 
673   qh_setfree( setp )
674     frees the space occupied by a sorted or unsorted set
675 
676   returns:
677     sets setp to NULL
678 
679   notes:
680     set may be NULL
681 
682   design:
683     free array
684     free set
685 */
qh_setfree(setT ** setp)686 void qh_setfree(setT **setp) {
687   int size;
688   void **freelistp;  /* used !qh_NOmem */
689 
690   if (*setp) {
691     size= sizeof(setT) + ((*setp)->maxsize)*SETelemsize;
692     if (size <= qhmem.LASTsize) {
693       qh_memfree_(*setp, size, freelistp);
694     }else
695       qh_memfree (*setp, size);
696     *setp= NULL;
697   }
698 } /* setfree */
699 
700 
701 /*-<a                             href="qh-set.htm#TOC"
702   >-------------------------------<a name="setfree2">-</a>
703 
704   qh_setfree2( setp, elemsize )
705     frees the space occupied by a set and its elements
706 
707   notes:
708     set may be NULL
709 
710   design:
711     free each element
712     free set
713 */
qh_setfree2(setT ** setp,int elemsize)714 void qh_setfree2 (setT **setp, int elemsize) {
715   void		*elem, **elemp;
716 
717   FOREACHelem_(*setp)
718     qh_memfree (elem, elemsize);
719   qh_setfree (setp);
720 } /* setfree2 */
721 
722 
723 
724 /*-<a                             href="qh-set.htm#TOC"
725   >-------------------------------<a name="setfreelong">-</a>
726 
727   qh_setfreelong( setp )
728     frees a set only if it's in long memory
729 
730   returns:
731     sets setp to NULL if it is freed
732 
733   notes:
734     set may be NULL
735 
736   design:
737     if set is large
738       free it
739 */
qh_setfreelong(setT ** setp)740 void qh_setfreelong(setT **setp) {
741   int size;
742 
743   if (*setp) {
744     size= sizeof(setT) + ((*setp)->maxsize)*SETelemsize;
745     if (size > qhmem.LASTsize) {
746       qh_memfree (*setp, size);
747       *setp= NULL;
748     }
749   }
750 } /* setfreelong */
751 
752 
753 /*-<a                             href="qh-set.htm#TOC"
754   >-------------------------------<a name="setin">-</a>
755 
756   qh_setin( set, setelem )
757     returns 1 if setelem is in a set, 0 otherwise
758 
759   notes:
760     set may be NULL or unsorted
761 
762   design:
763     scans set for setelem
764 */
qh_setin(setT * set,void * setelem)765 int qh_setin(setT *set, void *setelem) {
766   void *elem, **elemp;
767 
768   FOREACHelem_(set) {
769     if (elem == setelem)
770       return 1;
771   }
772   return 0;
773 } /* setin */
774 
775 
776 /*-<a                             href="qh-set.htm#TOC"
777   >-------------------------------<a name="setindex">-</a>
778 
779   qh_setindex( set, atelem )
780     returns the index of atelem in set.
781     returns -1, if not in set or maxsize wrong
782 
783   notes:
784     set may be NULL and may contain nulls.
785 
786   design:
787     checks maxsize
788     scans set for atelem
789 */
qh_setindex(setT * set,void * atelem)790 int qh_setindex(setT *set, void *atelem) {
791   void **elem;
792   int size, i;
793 
794   SETreturnsize_(set, size);
795   if (size > set->maxsize)
796     return -1;
797   elem= SETaddr_(set, void);
798   for (i=0; i < size; i++) {
799     if (*elem++ == atelem)
800       return i;
801   }
802   return -1;
803 } /* setindex */
804 
805 
806 /*-<a                             href="qh-set.htm#TOC"
807   >-------------------------------<a name="setlarger">-</a>
808 
809   qh_setlarger( oldsetp )
810     returns a larger set that contains all elements of *oldsetp
811 
812   notes:
813     the set is at least twice as large
814     if temp set, updates qhmem.tempstack
815 
816   design:
817     creates a new set
818     copies the old set to the new set
819     updates pointers in tempstack
820     deletes the old set
821 */
qh_setlarger(setT ** oldsetp)822 void qh_setlarger(setT **oldsetp) {
823   int size= 1, *sizep;
824   setT *newset, *set, **setp, *oldset;
825   void **oldp, **newp;
826 
827   if (*oldsetp) {
828     oldset= *oldsetp;
829     SETreturnsize_(oldset, size);
830     qhmem.cntlarger++;
831     qhmem.totlarger += size+1;
832     newset= qh_setnew(2 * size);
833     oldp= SETaddr_(oldset, void);
834     newp= SETaddr_(newset, void);
835     memcpy((char *)newp, (char *)oldp, (size+1) * SETelemsize);
836     sizep= SETsizeaddr_(newset);
837     *sizep= size+1;
838     FOREACHset_((setT *)qhmem.tempstack) {
839       if (set == oldset)
840 	*(setp-1)= newset;
841     }
842     qh_setfree(oldsetp);
843   }else
844     newset= qh_setnew(3);
845   *oldsetp= newset;
846 } /* setlarger */
847 
848 
849 /*-<a                             href="qh-set.htm#TOC"
850   >-------------------------------<a name="setlast">-</a>
851 
852   qh_setlast(  )
853     return last element of set or NULL (use type conversion)
854 
855   notes:
856     set may be NULL
857 
858   design:
859     return last element
860 */
qh_setlast(setT * set)861 void *qh_setlast(setT *set) {
862   int size;
863 
864   if (set) {
865     size= *SETsizeaddr_(set);
866     if (!size)
867       return SETelem_(set, set->maxsize - 1);
868     else if (size > 1)
869       return SETelem_(set, size - 2);
870   }
871   return NULL;
872 } /* setlast */
873 
874 
875 /*-<a                             href="qh-set.htm#TOC"
876   >-------------------------------<a name="setnew">-</a>
877 
878   qh_setnew( setsize )
879     creates and allocates space for a set
880 
881   notes:
882     setsize means the number of elements (NOT including the NULL terminator)
883     use qh_settemp/qh_setfreetemp if set is temporary
884 
885   design:
886     allocate memory for set
887     roundup memory if small set
888     initialize as empty set
889 */
qh_setnew(int setsize)890 setT *qh_setnew(int setsize) {
891   setT *set;
892   int sizereceived; /* used !qh_NOmem */
893   int size;
894   void **freelistp; /* used !qh_NOmem */
895 
896   if (!setsize)
897     setsize++;
898   size= sizeof(setT) + setsize * SETelemsize;
899   if ((unsigned) size <= (unsigned) qhmem.LASTsize) {
900     qh_memalloc_(size, freelistp, set, setT);
901 #ifndef qh_NOmem
902     sizereceived= qhmem.sizetable[ qhmem.indextable[size]];
903     if (sizereceived > size)
904       setsize += (sizereceived - size)/SETelemsize;
905 #endif
906   }else
907     set= (setT*)qh_memalloc (size);
908   set->maxsize= setsize;
909   set->e[setsize].i= 1;
910   set->e[0].p= NULL;
911   return (set);
912 } /* setnew */
913 
914 
915 /*-<a                             href="qh-set.htm#TOC"
916   >-------------------------------<a name="setnew_delnthsorted">-</a>
917 
918   qh_setnew_delnthsorted( set, size, nth, prepend )
919     creates a sorted set not containing nth element
920     if prepend, the first prepend elements are undefined
921 
922   notes:
923     set must be defined
924     checks nth
925     see also: setdelnthsorted
926 
927   design:
928     create new set
929     setup pointers and allocate room for prepend'ed entries
930     append head of old set to new set
931     append tail of old set to new set
932 */
qh_setnew_delnthsorted(setT * set,int size,int nth,int prepend)933 setT *qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend) {
934   setT *newset;
935   void **oldp, **newp;
936   int tailsize= size - nth -1, newsize;
937 
938   if (tailsize < 0) {
939     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
940     qh_setprint (qhmem.ferr, "", set);
941     qh_errexit (qhmem_ERRqhull, NULL, NULL);
942   }
943   newsize= size-1 + prepend;
944   newset= qh_setnew(newsize);
945   newset->e[newset->maxsize].i= newsize+1;  /* may be overwritten */
946   oldp= SETaddr_(set, void);
947   newp= SETaddr_(newset, void) + prepend;
948   switch (nth) {
949   case 0:
950     break;
951   case 1:
952     *(newp++)= *oldp++;
953     break;
954   case 2:
955     *(newp++)= *oldp++;
956     *(newp++)= *oldp++;
957     break;
958   case 3:
959     *(newp++)= *oldp++;
960     *(newp++)= *oldp++;
961     *(newp++)= *oldp++;
962     break;
963   case 4:
964     *(newp++)= *oldp++;
965     *(newp++)= *oldp++;
966     *(newp++)= *oldp++;
967     *(newp++)= *oldp++;
968     break;
969   default:
970     memcpy((char *)newp, (char *)oldp, nth * SETelemsize);
971     newp += nth;
972     oldp += nth;
973     break;
974   }
975   oldp++;
976   switch (tailsize) {
977   case 0:
978     break;
979   case 1:
980     *(newp++)= *oldp++;
981     break;
982   case 2:
983     *(newp++)= *oldp++;
984     *(newp++)= *oldp++;
985     break;
986   case 3:
987     *(newp++)= *oldp++;
988     *(newp++)= *oldp++;
989     *(newp++)= *oldp++;
990     break;
991   case 4:
992     *(newp++)= *oldp++;
993     *(newp++)= *oldp++;
994     *(newp++)= *oldp++;
995     *(newp++)= *oldp++;
996     break;
997   default:
998     memcpy((char *)newp, (char *)oldp, tailsize * SETelemsize);
999     newp += tailsize;
1000   }
1001   *newp= NULL;
1002   return(newset);
1003 } /* setnew_delnthsorted */
1004 
1005 
1006 /*-<a                             href="qh-set.htm#TOC"
1007   >-------------------------------<a name="setprint">-</a>
1008 
1009   qh_setprint( fp, string, set )
1010     print set elements to fp with identifying string
1011 
1012   notes:
1013     never errors
1014 */
qh_setprint(FILE * fp,char * string,setT * set)1015 void qh_setprint(FILE *fp, char* string, setT *set) {
1016   int size, k;
1017 
1018   if (!set)
1019     fprintf (fp, "%s set is null\n", string);
1020   else {
1021     SETreturnsize_(set, size);
1022     fprintf (fp, "%s set=%p maxsize=%d size=%d elems=",
1023 	     string, set, set->maxsize, size);
1024     if (size > set->maxsize)
1025       size= set->maxsize+1;
1026     for (k=0; k < size; k++)
1027       fprintf(fp, " %p", set->e[k].p);
1028     fprintf(fp, "\n");
1029   }
1030 } /* setprint */
1031 
1032 /*-<a                             href="qh-set.htm#TOC"
1033   >-------------------------------<a name="setreplace">-</a>
1034 
1035   qh_setreplace( set, oldelem, newelem )
1036     replaces oldelem in set with newelem
1037 
1038   notes:
1039     errors if oldelem not in the set
1040     newelem may be NULL, but it turns the set into an indexed set (no FOREACH)
1041 
1042   design:
1043     find oldelem
1044     replace with newelem
1045 */
qh_setreplace(setT * set,void * oldelem,void * newelem)1046 void qh_setreplace(setT *set, void *oldelem, void *newelem) {
1047   void **elemp;
1048 
1049   elemp= SETaddr_(set, void);
1050   while(*elemp != oldelem && *elemp)
1051     elemp++;
1052   if (*elemp)
1053     *elemp= newelem;
1054   else {
1055     fprintf (qhmem.ferr, "qhull internal error (qh_setreplace): elem %p not found in set\n",
1056        oldelem);
1057     qh_setprint (qhmem.ferr, "", set);
1058     qh_errexit (qhmem_ERRqhull, NULL, NULL);
1059   }
1060 } /* setreplace */
1061 
1062 
1063 /*-<a                             href="qh-set.htm#TOC"
1064   >-------------------------------<a name="setsize">-</a>
1065 
1066   qh_setsize( set )
1067     returns the size of a set
1068 
1069   notes:
1070     errors if set's maxsize is incorrect
1071     same as SETreturnsize_(set)
1072 
1073   design:
1074     determine actual size of set from maxsize
1075 */
qh_setsize(setT * set)1076 int qh_setsize(setT *set) {
1077   int size, *sizep;
1078 
1079   if (!set)
1080     return (0);
1081   sizep= SETsizeaddr_(set);
1082   if ((size= *sizep)) {
1083     size--;
1084     if (size > set->maxsize) {
1085       fprintf (qhmem.ferr, "qhull internal error (qh_setsize): current set size %d is greater than maximum size %d\n",
1086 	       size, set->maxsize);
1087       qh_setprint (qhmem.ferr, "set: ", set);
1088       qh_errexit (qhmem_ERRqhull, NULL, NULL);
1089     }
1090   }else
1091     size= set->maxsize;
1092   return size;
1093 } /* setsize */
1094 
1095 /*-<a                             href="qh-set.htm#TOC"
1096   >-------------------------------<a name="settemp">-</a>
1097 
1098   qh_settemp( setsize )
1099     return a stacked, temporary set of upto setsize elements
1100 
1101   notes:
1102     use settempfree or settempfree_all to release from qhmem.tempstack
1103     see also qh_setnew
1104 
1105   design:
1106     allocate set
1107     append to qhmem.tempstack
1108 
1109 */
qh_settemp(int setsize)1110 setT *qh_settemp(int setsize) {
1111   setT *newset;
1112 
1113   newset= qh_setnew (setsize);
1114   qh_setappend ((setT **)&qhmem.tempstack, newset);
1115   if (qhmem.IStracing >= 5)
1116     fprintf (qhmem.ferr, "qh_settemp: temp set %p of %d elements, depth %d\n",
1117        newset, newset->maxsize, qh_setsize ((setT*)qhmem.tempstack));
1118   return newset;
1119 } /* settemp */
1120 
1121 /*-<a                             href="qh-set.htm#TOC"
1122   >-------------------------------<a name="settempfree">-</a>
1123 
1124   qh_settempfree( set )
1125     free temporary set at top of qhmem.tempstack
1126 
1127   notes:
1128     nop if set is NULL
1129     errors if set not from previous   qh_settemp
1130 
1131   to locate errors:
1132     use 'T2' to find source and then find mis-matching qh_settemp
1133 
1134   design:
1135     check top of qhmem.tempstack
1136     free it
1137 */
qh_settempfree(setT ** set)1138 void qh_settempfree(setT **set) {
1139   setT *stackedset;
1140 
1141   if (!*set)
1142     return;
1143   stackedset= qh_settemppop ();
1144   if (stackedset != *set) {
1145     qh_settemppush(stackedset);
1146     fprintf (qhmem.ferr, "qhull internal error (qh_settempfree): set %p (size %d) was not last temporary allocated (depth %d, set %p, size %d)\n",
1147 	     *set, qh_setsize(*set), qh_setsize((setT*)qhmem.tempstack)+1,
1148 	     stackedset, qh_setsize(stackedset));
1149     qh_errexit (qhmem_ERRqhull, NULL, NULL);
1150   }
1151   qh_setfree (set);
1152 } /* settempfree */
1153 
1154 /*-<a                             href="qh-set.htm#TOC"
1155   >-------------------------------<a name="settempfree_all">-</a>
1156 
1157   qh_settempfree_all(  )
1158     free all temporary sets in qhmem.tempstack
1159 
1160   design:
1161     for each set in tempstack
1162       free set
1163     free qhmem.tempstack
1164 */
qh_settempfree_all(void)1165 void qh_settempfree_all(void) {
1166   setT *set, **setp;
1167 
1168   FOREACHset_((setT *)qhmem.tempstack)
1169     qh_setfree(&set);
1170   qh_setfree((setT **)&qhmem.tempstack);
1171 } /* settempfree_all */
1172 
1173 /*-<a                             href="qh-set.htm#TOC"
1174   >-------------------------------<a name="settemppop">-</a>
1175 
1176   qh_settemppop(  )
1177     pop and return temporary set from qhmem.tempstack
1178 
1179   notes:
1180     the returned set is permanent
1181 
1182   design:
1183     pop and check top of qhmem.tempstack
1184 */
qh_settemppop(void)1185 setT *qh_settemppop(void) {
1186   setT *stackedset;
1187 
1188   stackedset= (setT*)qh_setdellast((setT *)qhmem.tempstack);
1189   if (!stackedset) {
1190     fprintf (qhmem.ferr, "qhull internal error (qh_settemppop): pop from empty temporary stack\n");
1191     qh_errexit (qhmem_ERRqhull, NULL, NULL);
1192   }
1193   if (qhmem.IStracing >= 5)
1194     fprintf (qhmem.ferr, "qh_settemppop: depth %d temp set %p of %d elements\n",
1195        qh_setsize((setT*)qhmem.tempstack)+1, stackedset, qh_setsize(stackedset));
1196   return stackedset;
1197 } /* settemppop */
1198 
1199 /*-<a                             href="qh-set.htm#TOC"
1200   >-------------------------------<a name="settemppush">-</a>
1201 
1202   qh_settemppush( set )
1203     push temporary set unto qhmem.tempstack (makes it temporary)
1204 
1205   notes:
1206     duplicates settemp() for tracing
1207 
1208   design:
1209     append set to tempstack
1210 */
qh_settemppush(setT * set)1211 void qh_settemppush(setT *set) {
1212 
1213   qh_setappend ((setT**)&qhmem.tempstack, set);
1214   if (qhmem.IStracing >= 5)
1215     fprintf (qhmem.ferr, "qh_settemppush: depth %d temp set %p of %d elements\n",
1216     qh_setsize((setT*)qhmem.tempstack), set, qh_setsize(set));
1217 } /* settemppush */
1218 
1219 
1220 /*-<a                             href="qh-set.htm#TOC"
1221   >-------------------------------<a name="settruncate">-</a>
1222 
1223   qh_settruncate( set, size )
1224     truncate set to size elements
1225 
1226   notes:
1227     set must be defined
1228 
1229   see:
1230     SETtruncate_
1231 
1232   design:
1233     check size
1234     update actual size of set
1235 */
qh_settruncate(setT * set,int size)1236 void qh_settruncate (setT *set, int size) {
1237 
1238   if (size < 0 || size > set->maxsize) {
1239     fprintf (qhmem.ferr, "qhull internal error (qh_settruncate): size %d out of bounds for set:\n", size);
1240     qh_setprint (qhmem.ferr, "", set);
1241     qh_errexit (qhmem_ERRqhull, NULL, NULL);
1242   }
1243   set->e[set->maxsize].i= size+1;   /* maybe overwritten */
1244   set->e[size].p= NULL;
1245 } /* settruncate */
1246 
1247 /*-<a                             href="qh-set.htm#TOC"
1248   >-------------------------------<a name="setunique">-</a>
1249 
1250   qh_setunique( set, elem )
1251     add elem to unsorted set unless it is already in set
1252 
1253   notes:
1254     returns 1 if it is appended
1255 
1256   design:
1257     if elem not in set
1258       append elem to set
1259 */
qh_setunique(setT ** set,void * elem)1260 int qh_setunique (setT **set, void *elem) {
1261 
1262   if (!qh_setin (*set, elem)) {
1263     qh_setappend (set, elem);
1264     return 1;
1265   }
1266   return 0;
1267 } /* setunique */
1268 
1269 /*-<a                             href="qh-set.htm#TOC"
1270   >-------------------------------<a name="setzero">-</a>
1271 
1272   qh_setzero( set, index, size )
1273     zero elements from index on
1274     set actual size of set to size
1275 
1276   notes:
1277     set must be defined
1278     the set becomes an indexed set (can not use FOREACH...)
1279 
1280   see also:
1281     qh_settruncate
1282 
1283   design:
1284     check index and size
1285     update actual size
1286     zero elements starting at e[index]
1287 */
qh_setzero(setT * set,int index,int size)1288 void qh_setzero (setT *set, int index, int size) {
1289   int count;
1290 
1291   if (index < 0 || index >= size || size > set->maxsize) {
1292     fprintf (qhmem.ferr, "qhull internal error (qh_setzero): index %d or size %d out of bounds for set:\n", index, size);
1293     qh_setprint (qhmem.ferr, "", set);
1294     qh_errexit (qhmem_ERRqhull, NULL, NULL);
1295   }
1296   set->e[set->maxsize].i=  size+1;  /* may be overwritten */
1297   count= size - index + 1;   /* +1 for NULL terminator */
1298   memset ((char *)SETelemaddr_(set, index, void), 0, count * SETelemsize);
1299 } /* setzero */
1300 
1301 
1302