qset_r.h
Go to the documentation of this file.
1 /*<html><pre> -<a href="qh-set_r.htm"
2  >-------------------------------</a><a name="TOP">-</a>
3 
4  qset_r.h
5  header file for qset_r.c that implements set
6 
7  see qh-set_r.htm and qset_r.c
8 
9  only uses mem_r.c, malloc/free
10 
11  for error handling, writes message and calls
12  qh_errexit(qhT *qh, qhmem_ERRqhull, NULL, NULL);
13 
14  set operations satisfy the following properties:
15  - sets have a max size, the actual size (if different) is stored at the end
16  - every set is NULL terminated
17  - sets may be sorted or unsorted, the caller must distinguish this
18 
19  Copyright (c) 1993-2015 The Geometry Center.
20  $Id: //main/2015/qhull/src/libqhull_r/qset_r.h#3 $$Change: 2062 $
21  $DateTime: 2016/01/17 13:13:18 $$Author: bbarber $
22 */
23 
24 #ifndef qhDEFset
25 #define qhDEFset 1
26 
27 #include <stdio.h>
28 
29 /*================= -structures- ===============*/
30 
31 #ifndef DEFsetT
32 #define DEFsetT 1
33 typedef struct setT setT; /* a set is a sorted or unsorted array of pointers */
34 #endif
35 
36 #ifndef DEFqhT
37 #define DEFqhT 1
38 typedef struct qhT qhT; /* defined in libqhull_r.h */
39 #endif
40 
41 /* [jan'15] Decided not to use countT. Most sets are small. The code uses signed tests */
42 
43 /*-<a href="qh-set_r.htm#TOC"
44 >----------------------------------------</a><a name="setT">-</a>
45 
46 setT
47  a set or list of pointers with maximum size and actual size.
48 
49 variations:
50  unsorted, unique -- a list of unique pointers with NULL terminator
51  user guarantees uniqueness
52  sorted -- a sorted list of unique pointers with NULL terminator
53  qset_r.c guarantees uniqueness
54  unsorted -- a list of pointers terminated with NULL
55  indexed -- an array of pointers with NULL elements
56 
57 structure for set of n elements:
58 
59  --------------
60  | maxsize
61  --------------
62  | e[0] - a pointer, may be NULL for indexed sets
63  --------------
64  | e[1]
65 
66  --------------
67  | ...
68  --------------
69  | e[n-1]
70  --------------
71  | e[n] = NULL
72  --------------
73  | ...
74  --------------
75  | e[maxsize] - n+1 or NULL (determines actual size of set)
76  --------------
77 
78 */
79 
80 /*-- setelemT -- internal type to allow both pointers and indices
81 */
82 typedef union setelemT setelemT;
83 union setelemT {
84  void *p;
85  int i; /* integer used for e[maxSize] */
86 };
87 
88 struct setT {
89  int maxsize; /* maximum number of elements (except NULL) */
90  setelemT e[1]; /* array of pointers, tail is NULL */
91  /* last slot (unless NULL) is actual size+1
92  e[maxsize]==NULL or e[e[maxsize]-1]==NULL */
93  /* this may generate a warning since e[] contains
94  maxsize elements */
95 };
96 
97 /*=========== -constants- =========================*/
98 
99 /*-<a href="qh-set_r.htm#TOC"
100  >-----------------------------------</a><a name="SETelemsize">-</a>
101 
102  SETelemsize
103  size of a set element in bytes
104 */
105 #define SETelemsize ((int)sizeof(setelemT))
106 
107 
108 /*=========== -macros- =========================*/
109 
110 /*-<a href="qh-set_r.htm#TOC"
111  >-----------------------------------</a><a name="FOREACHsetelement_">-</a>
112 
113  FOREACHsetelement_(type, set, variable)
114  define FOREACH iterator
115 
116  declare:
117  assumes *variable and **variablep are declared
118  no space in "variable)" [DEC Alpha cc compiler]
119 
120  each iteration:
121  variable is set element
122  variablep is one beyond variable.
123 
124  to repeat an element:
125  variablep--; / *repeat* /
126 
127  at exit:
128  variable is NULL at end of loop
129 
130  example:
131  #define FOREACHfacet_( facets ) FOREACHsetelement_( facetT, facets, facet )
132 
133  notes:
134  use FOREACHsetelement_i_() if need index or include NULLs
135 
136  WARNING:
137  nested loops can't use the same variable (define another FOREACH)
138 
139  needs braces if nested inside another FOREACH
140  this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} )
141 */
142 #define FOREACHsetelement_(type, set, variable) \
143  if (((variable= NULL), set)) for (\
144  variable##p= (type **)&((set)->e[0].p); \
145  (variable= *variable##p++);)
146 
147 /*-<a href="qh-set_r.htm#TOC"
148  >----------------------------------------</a><a name="FOREACHsetelement_i_">-</a>
149 
150  FOREACHsetelement_i_(qh, type, set, variable)
151  define indexed FOREACH iterator
152 
153  declare:
154  type *variable, variable_n, variable_i;
155 
156  each iteration:
157  variable is set element, may be NULL
158  variable_i is index, variable_n is qh_setsize()
159 
160  to repeat an element:
161  variable_i--; variable_n-- repeats for deleted element
162 
163  at exit:
164  variable==NULL and variable_i==variable_n
165 
166  example:
167  #define FOREACHfacet_i_( qh, facets ) FOREACHsetelement_i_( qh, facetT, facets, facet )
168 
169  WARNING:
170  nested loops can't use the same variable (define another FOREACH)
171 
172  needs braces if nested inside another FOREACH
173  this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} )
174 */
175 #define FOREACHsetelement_i_(qh, type, set, variable) \
176  if (((variable= NULL), set)) for (\
177  variable##_i= 0, variable= (type *)((set)->e[0].p), \
178  variable##_n= qh_setsize(qh, set);\
179  variable##_i < variable##_n;\
180  variable= (type *)((set)->e[++variable##_i].p) )
181 
182 /*-<a href="qh-set_r.htm#TOC"
183  >--------------------------------------</a><a name="FOREACHsetelementreverse_">-</a>
184 
185  FOREACHsetelementreverse_(qh, type, set, variable)-
186  define FOREACH iterator in reverse order
187 
188  declare:
189  assumes *variable and **variablep are declared
190  also declare 'int variabletemp'
191 
192  each iteration:
193  variable is set element
194 
195  to repeat an element:
196  variabletemp++; / *repeat* /
197 
198  at exit:
199  variable is NULL
200 
201  example:
202  #define FOREACHvertexreverse_( vertices ) FOREACHsetelementreverse_( vertexT, vertices, vertex )
203 
204  notes:
205  use FOREACHsetelementreverse12_() to reverse first two elements
206  WARNING: needs braces if nested inside another FOREACH
207 */
208 #define FOREACHsetelementreverse_(qh, type, set, variable) \
209  if (((variable= NULL), set)) for (\
210  variable##temp= qh_setsize(qh, set)-1, variable= qh_setlast(qh, set);\
211  variable; variable= \
212  ((--variable##temp >= 0) ? SETelemt_(set, variable##temp, type) : NULL))
213 
214 /*-<a href="qh-set_r.htm#TOC"
215  >-----------------------------------</a><a name="FOREACHsetelementreverse12_">-</a>
216 
217  FOREACHsetelementreverse12_(type, set, variable)-
218  define FOREACH iterator with e[1] and e[0] reversed
219 
220  declare:
221  assumes *variable and **variablep are declared
222 
223  each iteration:
224  variable is set element
225  variablep is one after variable.
226 
227  to repeat an element:
228  variablep--; / *repeat* /
229 
230  at exit:
231  variable is NULL at end of loop
232 
233  example
234  #define FOREACHvertexreverse12_( vertices ) FOREACHsetelementreverse12_( vertexT, vertices, vertex )
235 
236  notes:
237  WARNING: needs braces if nested inside another FOREACH
238 */
239 #define FOREACHsetelementreverse12_(type, set, variable) \
240  if (((variable= NULL), set)) for (\
241  variable##p= (type **)&((set)->e[1].p); \
242  (variable= *variable##p); \
243  variable##p == ((type **)&((set)->e[0].p))?variable##p += 2: \
244  (variable##p == ((type **)&((set)->e[1].p))?variable##p--:variable##p++))
245 
246 /*-<a href="qh-set_r.htm#TOC"
247  >-----------------------------------</a><a name="FOREACHelem_">-</a>
248 
249  FOREACHelem_( set )-
250  iterate elements in a set
251 
252  declare:
253  void *elem, *elemp;
254 
255  each iteration:
256  elem is set element
257  elemp is one beyond
258 
259  to repeat an element:
260  elemp--; / *repeat* /
261 
262  at exit:
263  elem == NULL at end of loop
264 
265  example:
266  FOREACHelem_(set) {
267 
268  notes:
269  WARNING: needs braces if nested inside another FOREACH
270 */
271 #define FOREACHelem_(set) FOREACHsetelement_(void, set, elem)
272 
273 /*-<a href="qh-set_r.htm#TOC"
274  >-----------------------------------</a><a name="FOREACHset_">-</a>
275 
276  FOREACHset_( set )-
277  iterate a set of sets
278 
279  declare:
280  setT *set, **setp;
281 
282  each iteration:
283  set is set element
284  setp is one beyond
285 
286  to repeat an element:
287  setp--; / *repeat* /
288 
289  at exit:
290  set == NULL at end of loop
291 
292  example
293  FOREACHset_(sets) {
294 
295  notes:
296  WARNING: needs braces if nested inside another FOREACH
297 */
298 #define FOREACHset_(sets) FOREACHsetelement_(setT, sets, set)
299 
300 /*-<a href="qh-set_r.htm#TOC"
301  >-----------------------------------------</a><a name="SETindex_">-</a>
302 
303  SETindex_( set, elem )
304  return index of elem in set
305 
306  notes:
307  for use with FOREACH iteration
308  WARN64 -- Maximum set size is 2G
309 
310  example:
311  i= SETindex_(ridges, ridge)
312 */
313 #define SETindex_(set, elem) ((int)((void **)elem##p - (void **)&(set)->e[1].p))
314 
315 /*-<a href="qh-set_r.htm#TOC"
316  >---------------------------------------</a><a name="SETref_">-</a>
317 
318  SETref_( elem )
319  l.h.s. for modifying the current element in a FOREACH iteration
320 
321  example:
322  SETref_(ridge)= anotherridge;
323 */
324 #define SETref_(elem) (elem##p[-1])
325 
326 /*-<a href="qh-set_r.htm#TOC"
327  >---------------------------------------</a><a name="SETelem_">-</a>
328 
329  SETelem_(set, n)
330  return the n'th element of set
331 
332  notes:
333  assumes that n is valid [0..size] and that set is defined
334  use SETelemt_() for type cast
335 */
336 #define SETelem_(set, n) ((set)->e[n].p)
337 
338 /*-<a href="qh-set_r.htm#TOC"
339  >---------------------------------------</a><a name="SETelemt_">-</a>
340 
341  SETelemt_(set, n, type)
342  return the n'th element of set as a type
343 
344  notes:
345  assumes that n is valid [0..size] and that set is defined
346 */
347 #define SETelemt_(set, n, type) ((type*)((set)->e[n].p))
348 
349 /*-<a href="qh-set_r.htm#TOC"
350  >---------------------------------------</a><a name="SETelemaddr_">-</a>
351 
352  SETelemaddr_(set, n, type)
353  return address of the n'th element of a set
354 
355  notes:
356  assumes that n is valid [0..size] and set is defined
357 */
358 #define SETelemaddr_(set, n, type) ((type **)(&((set)->e[n].p)))
359 
360 /*-<a href="qh-set_r.htm#TOC"
361  >---------------------------------------</a><a name="SETfirst_">-</a>
362 
363  SETfirst_(set)
364  return first element of set
365 
366 */
367 #define SETfirst_(set) ((set)->e[0].p)
368 
369 /*-<a href="qh-set_r.htm#TOC"
370  >---------------------------------------</a><a name="SETfirstt_">-</a>
371 
372  SETfirstt_(set, type)
373  return first element of set as a type
374 
375 */
376 #define SETfirstt_(set, type) ((type*)((set)->e[0].p))
377 
378 /*-<a href="qh-set_r.htm#TOC"
379  >---------------------------------------</a><a name="SETsecond_">-</a>
380 
381  SETsecond_(set)
382  return second element of set
383 
384 */
385 #define SETsecond_(set) ((set)->e[1].p)
386 
387 /*-<a href="qh-set_r.htm#TOC"
388  >---------------------------------------</a><a name="SETsecondt_">-</a>
389 
390  SETsecondt_(set, type)
391  return second element of set as a type
392 */
393 #define SETsecondt_(set, type) ((type*)((set)->e[1].p))
394 
395 /*-<a href="qh-set_r.htm#TOC"
396  >---------------------------------------</a><a name="SETaddr_">-</a>
397 
398  SETaddr_(set, type)
399  return address of set's elements
400 */
401 #define SETaddr_(set,type) ((type **)(&((set)->e[0].p)))
402 
403 /*-<a href="qh-set_r.htm#TOC"
404  >---------------------------------------</a><a name="SETreturnsize_">-</a>
405 
406  SETreturnsize_(set, size)
407  return size of a set
408 
409  notes:
410  set must be defined
411  use qh_setsize(qhT *qh, set) unless speed is critical
412 */
413 #define SETreturnsize_(set, size) (((size)= ((set)->e[(set)->maxsize].i))?(--(size)):((size)= (set)->maxsize))
414 
415 /*-<a href="qh-set_r.htm#TOC"
416  >---------------------------------------</a><a name="SETempty_">-</a>
417 
418  SETempty_(set)
419  return true(1) if set is empty
420 
421  notes:
422  set may be NULL
423 */
424 #define SETempty_(set) (!set || (SETfirst_(set) ? 0 : 1))
425 
426 /*-<a href="qh-set_r.htm#TOC"
427  >-------------------------------<a name="SETsizeaddr_">-</a>
428 
429  SETsizeaddr_(set)
430  return pointer to 'actual size+1' of set (set CANNOT be NULL!!)
431  Its type is setelemT* for strict aliasing
432  All SETelemaddr_ must be cast to setelemT
433 
434 
435  notes:
436  *SETsizeaddr==NULL or e[*SETsizeaddr-1].p==NULL
437 */
438 #define SETsizeaddr_(set) (&((set)->e[(set)->maxsize]))
439 
440 /*-<a href="qh-set_r.htm#TOC"
441  >---------------------------------------</a><a name="SETtruncate_">-</a>
442 
443  SETtruncate_(set, size)
444  truncate set to size
445 
446  see:
447  qh_settruncate()
448 
449 */
450 #define SETtruncate_(set, size) {set->e[set->maxsize].i= size+1; /* maybe overwritten */ \
451  set->e[size].p= NULL;}
452 
453 /*======= prototypes in alphabetical order ============*/
454 
455 void qh_setaddsorted(qhT *qh, setT **setp, void *elem);
456 void qh_setaddnth(qhT *qh, setT **setp, int nth, void *newelem);
457 void qh_setappend(qhT *qh, setT **setp, void *elem);
458 void qh_setappend_set(qhT *qh, setT **setp, setT *setA);
459 void qh_setappend2ndlast(qhT *qh, setT **setp, void *elem);
460 void qh_setcheck(qhT *qh, setT *set, const char *tname, unsigned id);
461 void qh_setcompact(qhT *qh, setT *set);
462 setT *qh_setcopy(qhT *qh, setT *set, int extra);
463 void *qh_setdel(setT *set, void *elem);
464 void *qh_setdellast(setT *set);
465 void *qh_setdelnth(qhT *qh, setT *set, int nth);
466 void *qh_setdelnthsorted(qhT *qh, setT *set, int nth);
467 void *qh_setdelsorted(setT *set, void *newelem);
468 setT *qh_setduplicate(qhT *qh, setT *set, int elemsize);
469 void **qh_setendpointer(setT *set);
470 int qh_setequal(setT *setA, setT *setB);
471 int qh_setequal_except(setT *setA, void *skipelemA, setT *setB, void *skipelemB);
472 int qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB);
473 void qh_setfree(qhT *qh, setT **set);
474 void qh_setfree2(qhT *qh, setT **setp, int elemsize);
475 void qh_setfreelong(qhT *qh, setT **set);
476 int qh_setin(setT *set, void *setelem);
477 int qh_setindex(setT *set, void *setelem);
478 void qh_setlarger(qhT *qh, setT **setp);
479 void *qh_setlast(setT *set);
480 setT *qh_setnew(qhT *qh, int size);
481 setT *qh_setnew_delnthsorted(qhT *qh, setT *set, int size, int nth, int prepend);
482 void qh_setprint(qhT *qh, FILE *fp, const char* string, setT *set);
483 void qh_setreplace(qhT *qh, setT *set, void *oldelem, void *newelem);
484 int qh_setsize(qhT *qh, setT *set);
485 setT *qh_settemp(qhT *qh, int setsize);
486 void qh_settempfree(qhT *qh, setT **set);
487 void qh_settempfree_all(qhT *qh);
488 setT *qh_settemppop(qhT *qh);
489 void qh_settemppush(qhT *qh, setT *set);
490 void qh_settruncate(qhT *qh, setT *set, int size);
491 int qh_setunique(qhT *qh, setT **set, void *elem);
492 void qh_setzero(qhT *qh, setT *set, int idx, int size);
493 
494 
495 #endif /* qhDEFset */
qh_setindex
int qh_setindex(setT *set, void *setelem)
Definition: qset.c:821
qhT
Definition: libqhull.h:465
qh_setin
int qh_setin(setT *set, void *setelem)
Definition: qset.c:795
qh_setdel
void * qh_setdel(setT *set, void *elem)
Definition: qset.c:344
qh_setdelnth
void * qh_setdelnth(qhT *qh, setT *set, int nth)
Definition: qset_r.c:424
qh_setappend_set
void qh_setappend_set(qhT *qh, setT **setp, setT *setA)
Definition: qset_r.c:163
setT
Definition: qset.h:83
qh_setcheck
void qh_setcheck(qhT *qh, setT *set, const char *tname, unsigned id)
Definition: qset_r.c:234
qh_settruncate
void qh_settruncate(qhT *qh, setT *set, int size)
Definition: qset_r.c:1275
qh_setfree2
void qh_setfree2(qhT *qh, setT **setp, int elemsize)
Definition: qset_r.c:744
qh_setlarger
void qh_setlarger(qhT *qh, setT **setp)
Definition: qset_r.c:855
qh_setsize
int qh_setsize(qhT *qh, setT *set)
Definition: qset_r.c:1111
qh_setdelsorted
void * qh_setdelsorted(setT *set, void *newelem)
Definition: qset.c:504
qh_setlast
void * qh_setlast(setT *set)
Definition: qset.c:895
qh_setfree
void qh_setfree(qhT *qh, setT **set)
Definition: qset_r.c:716
qh_settemppush
void qh_settemppush(qhT *qh, setT *set)
Definition: qset_r.c:1247
qh_setnew
setT * qh_setnew(qhT *qh, int size)
Definition: qset_r.c:924
qh_settemppop
setT * qh_settemppop(qhT *qh)
Definition: qset_r.c:1221
qh
#define qh
Definition: libqhull.h:457
qh_setendpointer
void ** qh_setendpointer(setT *set)
Definition: qset.c:566
setelemT::p
void * p
Definition: qset.h:79
setelemT
Definition: qset.h:78
qh_settempfree
void qh_settempfree(qhT *qh, setT **set)
Definition: qset_r.c:1174
qh_setprint
void qh_setprint(qhT *qh, FILE *fp, const char *string, setT *set)
Definition: qset_r.c:1049
qh_setappend2ndlast
void qh_setappend2ndlast(qhT *qh, setT **setp, void *elem)
Definition: qset_r.c:207
qh_setequal
int qh_setequal(setT *setA, setT *setB)
Definition: qset.c:587
qh_setduplicate
setT * qh_setduplicate(qhT *qh, setT *set, int elemsize)
Definition: qset_r.c:541
qh_setunique
int qh_setunique(qhT *qh, setT **set, void *elem)
Definition: qset_r.c:1299
setelemT::i
int i
Definition: qset.h:80
qh_setcompact
void qh_setcompact(qhT *qh, setT *set)
Definition: qset_r.c:276
qh_setfreelong
void qh_setfreelong(qhT *qh, setT **set)
Definition: qset_r.c:770
qh_setaddsorted
void qh_setaddsorted(qhT *qh, setT **setp, void *elem)
Definition: qset_r.c:100
qh_setappend
void qh_setappend(qhT *qh, setT **setp, void *elem)
Definition: qset_r.c:131
qh_setzero
void qh_setzero(qhT *qh, setT *set, int idx, int size)
Definition: qset_r.c:1327
qh_setaddnth
void qh_setaddnth(qhT *qh, setT **setp, int nth, void *newelem)
Definition: qset_r.c:61
qh_setdellast
void * qh_setdellast(setT *set)
Definition: qset.c:384
qh_setcopy
setT * qh_setcopy(qhT *qh, setT *set, int extra)
Definition: qset_r.c:310
qh_settemp
setT * qh_settemp(qhT *qh, int setsize)
Definition: qset_r.c:1146
qh_setnew_delnthsorted
setT * qh_setnew_delnthsorted(qhT *qh, setT *set, int size, int nth, int prepend)
Definition: qset_r.c:967
qh_settempfree_all
void qh_settempfree_all(qhT *qh)
Definition: qset_r.c:1201
qh_setequal_except
int qh_setequal_except(setT *setA, void *skipelemA, setT *setB, void *skipelemB)
Definition: qset.c:629
qh_setequal_skip
int qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB)
Definition: qset.c:677
qh_setdelnthsorted
void * qh_setdelnthsorted(qhT *qh, setT *set, int nth)
Definition: qset_r.c:465
qh_setreplace
void qh_setreplace(qhT *qh, setT *set, void *oldelem, void *newelem)
Definition: qset_r.c:1080

hpp-fcl
Author(s):
autogenerated on Fri Jun 2 2023 02:39:02