Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Analysis.AlgorithmBehavior/qhull-2012.1/src/libqhull/qset.c @ 11303

Last change on this file since 11303 was 10207, checked in by ascheibe, 11 years ago

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