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