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

hpp-fcl
Author(s):
autogenerated on Sat Nov 23 2024 03:44:59