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

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