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