1
/*<html><pre> -<a href="qh-set.htm"
2
>-------------------------------</a><a name="TOP">-</a>
5
header file for qset.c that implements set
7
see qh-set.htm and qset.c
9
only uses mem.c, malloc/free
11
for error handling, writes message and calls
12
qh_errexit(qhmem_ERRqhull, NULL, NULL);
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
19
Copyright (c) 1993-2012 The Geometry Center.
20
$Id: //main/2011/qhull/src/libqhull/qset.h#4 $$Change: 1464 $
21
$DateTime: 2012/01/25 22:58:41 $$Author: bbarber $
29
/*================= -structures- ===============*/
33
typedef struct setT setT; /* a set is a sorted or unsorted array of pointers */
36
/*-<a href="qh-set.htm#TOC"
37
>----------------------------------------</a><a name="setT">-</a>
40
a set or list of pointers with maximum size and actual size.
43
unsorted, unique -- a list of unique pointers with NULL terminator
44
user guarantees uniqueness
45
sorted -- a sorted list of unique pointers with NULL terminator
46
qset.c guarantees uniqueness
47
unsorted -- a list of pointers terminated with NULL
48
indexed -- an array of pointers with NULL elements
50
structure for set of n elements:
55
| e[0] - a pointer, may be NULL for indexed sets
68
| e[maxsize] - n+1 or NULL (determines actual size of set)
73
/*-- setelemT -- internal type to allow both pointers and indices
75
typedef union setelemT setelemT;
78
int i; /* integer used for e[maxSize] */
82
int maxsize; /* maximum number of elements (except NULL) */
83
setelemT e[1]; /* array of pointers, tail is NULL */
84
/* last slot (unless NULL) is actual size+1
85
e[maxsize]==NULL or e[e[maxsize]-1]==NULL */
86
/* this may generate a warning since e[] contains
90
/*=========== -constants- =========================*/
92
/*-<a href="qh-set.htm#TOC"
93
>-----------------------------------</a><a name="SETelemsize">-</a>
96
size of a set element in bytes
98
#define SETelemsize ((int)sizeof(setelemT))
101
/*=========== -macros- =========================*/
103
/*-<a href="qh-set.htm#TOC"
104
>-----------------------------------</a><a name="FOREACHsetelement_">-</a>
106
FOREACHsetelement_(type, set, variable)
107
define FOREACH iterator
110
assumes *variable and **variablep are declared
111
no space in "variable)" [DEC Alpha cc compiler]
114
variable is set element
115
variablep is one beyond variable.
117
to repeat an element:
118
variablep--; / *repeat* /
121
variable is NULL at end of loop
124
#define FOREACHfacet_( facets ) FOREACHsetelement_( facetT, facets, facet )
127
use FOREACHsetelement_i_() if need index or include NULLs
130
nested loops can't use the same variable (define another FOREACH)
132
needs braces if nested inside another FOREACH
133
this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} )
135
#define FOREACHsetelement_(type, set, variable) \
136
if (((variable= NULL), set)) for (\
137
variable##p= (type **)&((set)->e[0].p); \
138
(variable= *variable##p++);)
140
/*-<a href="qh-set.htm#TOC"
141
>----------------------------------------</a><a name="FOREACHsetelement_i_">-</a>
143
FOREACHsetelement_i_(type, set, variable)
144
define indexed FOREACH iterator
147
type *variable, variable_n, variable_i;
150
variable is set element, may be NULL
151
variable_i is index, variable_n is qh_setsize()
153
to repeat an element:
154
variable_i--; variable_n-- repeats for deleted element
157
variable==NULL and variable_i==variable_n
160
#define FOREACHfacet_i_( facets ) FOREACHsetelement_i_( facetT, facets, facet )
163
nested loops can't use the same variable (define another FOREACH)
165
needs braces if nested inside another FOREACH
166
this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} )
168
#define FOREACHsetelement_i_(type, set, variable) \
169
if (((variable= NULL), set)) for (\
170
variable##_i= 0, variable= (type *)((set)->e[0].p), \
171
variable##_n= qh_setsize(set);\
172
variable##_i < variable##_n;\
173
variable= (type *)((set)->e[++variable##_i].p) )
175
/*-<a href="qh-set.htm#TOC"
176
>--------------------------------------</a><a name="FOREACHsetelementreverse_">-</a>
178
FOREACHsetelementreverse_(type, set, variable)-
179
define FOREACH iterator in reverse order
182
assumes *variable and **variablep are declared
183
also declare 'int variabletemp'
186
variable is set element
188
to repeat an element:
189
variabletemp++; / *repeat* /
195
#define FOREACHvertexreverse_( vertices ) FOREACHsetelementreverse_( vertexT, vertices, vertex )
198
use FOREACHsetelementreverse12_() to reverse first two elements
199
WARNING: needs braces if nested inside another FOREACH
201
#define FOREACHsetelementreverse_(type, set, variable) \
202
if (((variable= NULL), set)) for (\
203
variable##temp= qh_setsize(set)-1, variable= qh_setlast(set);\
204
variable; variable= \
205
((--variable##temp >= 0) ? SETelemt_(set, variable##temp, type) : NULL))
207
/*-<a href="qh-set.htm#TOC"
208
>-----------------------------------</a><a name="FOREACHsetelementreverse12_">-</a>
210
FOREACHsetelementreverse12_(type, set, variable)-
211
define FOREACH iterator with e[1] and e[0] reversed
214
assumes *variable and **variablep are declared
217
variable is set element
218
variablep is one after variable.
220
to repeat an element:
221
variablep--; / *repeat* /
224
variable is NULL at end of loop
227
#define FOREACHvertexreverse12_( vertices ) FOREACHsetelementreverse12_( vertexT, vertices, vertex )
230
WARNING: needs braces if nested inside another FOREACH
232
#define FOREACHsetelementreverse12_(type, set, variable) \
233
if (((variable= NULL), set)) for (\
234
variable##p= (type **)&((set)->e[1].p); \
235
(variable= *variable##p); \
236
variable##p == ((type **)&((set)->e[0].p))?variable##p += 2: \
237
(variable##p == ((type **)&((set)->e[1].p))?variable##p--:variable##p++))
239
/*-<a href="qh-set.htm#TOC"
240
>-----------------------------------</a><a name="FOREACHelem_">-</a>
243
iterate elements in a set
252
to repeat an element:
253
elemp--; / *repeat* /
256
elem == NULL at end of loop
262
WARNING: needs braces if nested inside another FOREACH
264
#define FOREACHelem_(set) FOREACHsetelement_(void, set, elem)
266
/*-<a href="qh-set.htm#TOC"
267
>-----------------------------------</a><a name="FOREACHset_">-</a>
270
iterate a set of sets
279
to repeat an element:
283
set == NULL at end of loop
289
WARNING: needs braces if nested inside another FOREACH
291
#define FOREACHset_(sets) FOREACHsetelement_(setT, sets, set)
293
/*-<a href="qh-set.htm#TOC"
294
>-----------------------------------------</a><a name="SETindex_">-</a>
296
SETindex_( set, elem )
297
return index of elem in set
300
for use with FOREACH iteration
301
WARN64 -- Maximum set size is 2G
304
i= SETindex_(ridges, ridge)
306
#define SETindex_(set, elem) ((int)((void **)elem##p - (void **)&(set)->e[1].p))
308
/*-<a href="qh-set.htm#TOC"
309
>---------------------------------------</a><a name="SETref_">-</a>
312
l.h.s. for modifying the current element in a FOREACH iteration
315
SETref_(ridge)= anotherridge;
317
#define SETref_(elem) (elem##p[-1])
319
/*-<a href="qh-set.htm#TOC"
320
>---------------------------------------</a><a name="SETelem_">-</a>
323
return the n'th element of set
326
assumes that n is valid [0..size] and that set is defined
327
use SETelemt_() for type cast
329
#define SETelem_(set, n) ((set)->e[n].p)
331
/*-<a href="qh-set.htm#TOC"
332
>---------------------------------------</a><a name="SETelemt_">-</a>
334
SETelemt_(set, n, type)
335
return the n'th element of set as a type
338
assumes that n is valid [0..size] and that set is defined
340
#define SETelemt_(set, n, type) ((type*)((set)->e[n].p))
342
/*-<a href="qh-set.htm#TOC"
343
>---------------------------------------</a><a name="SETelemaddr_">-</a>
345
SETelemaddr_(set, n, type)
346
return address of the n'th element of a set
349
assumes that n is valid [0..size] and set is defined
351
#define SETelemaddr_(set, n, type) ((type **)(&((set)->e[n].p)))
353
/*-<a href="qh-set.htm#TOC"
354
>---------------------------------------</a><a name="SETfirst_">-</a>
357
return first element of set
360
#define SETfirst_(set) ((set)->e[0].p)
362
/*-<a href="qh-set.htm#TOC"
363
>---------------------------------------</a><a name="SETfirstt_">-</a>
365
SETfirstt_(set, type)
366
return first element of set as a type
369
#define SETfirstt_(set, type) ((type*)((set)->e[0].p))
371
/*-<a href="qh-set.htm#TOC"
372
>---------------------------------------</a><a name="SETsecond_">-</a>
375
return second element of set
378
#define SETsecond_(set) ((set)->e[1].p)
380
/*-<a href="qh-set.htm#TOC"
381
>---------------------------------------</a><a name="SETsecondt_">-</a>
383
SETsecondt_(set, type)
384
return second element of set as a type
386
#define SETsecondt_(set, type) ((type*)((set)->e[1].p))
388
/*-<a href="qh-set.htm#TOC"
389
>---------------------------------------</a><a name="SETaddr_">-</a>
392
return address of set's elements
394
#define SETaddr_(set,type) ((type **)(&((set)->e[0].p)))
396
/*-<a href="qh-set.htm#TOC"
397
>---------------------------------------</a><a name="SETreturnsize_">-</a>
399
SETreturnsize_(set, size)
404
use qh_setsize(set) unless speed is critical
406
#define SETreturnsize_(set, size) (((size)= ((set)->e[(set)->maxsize].i))?(--(size)):((size)= (set)->maxsize))
408
/*-<a href="qh-set.htm#TOC"
409
>---------------------------------------</a><a name="SETempty_">-</a>
412
return true(1) if set is empty
417
#define SETempty_(set) (!set || (SETfirst_(set) ? 0 : 1))
419
/*-<a href="qh-set.htm#TOC"
420
>-------------------------------<a name="SETsizeaddr_">-</a>
423
return pointer to 'actual size+1' of set (set CANNOT be NULL!!)
424
Its type is setelemT* for strict aliasing
425
All SETelemaddr_ must be cast to setelemT
429
*SETsizeaddr==NULL or e[*SETsizeaddr-1].p==NULL
431
#define SETsizeaddr_(set) (&((set)->e[(set)->maxsize]))
433
/*-<a href="qh-set.htm#TOC"
434
>---------------------------------------</a><a name="SETtruncate_">-</a>
436
SETtruncate_(set, size)
443
#define SETtruncate_(set, size) {set->e[set->maxsize].i= size+1; /* maybe overwritten */ \
444
set->e[size].p= NULL;}
446
/*======= prototypes in alphabetical order ============*/
448
void qh_setaddsorted(setT **setp, void *elem);
449
void qh_setaddnth(setT **setp, int nth, void *newelem);
450
void qh_setappend(setT **setp, void *elem);
451
void qh_setappend_set(setT **setp, setT *setA);
452
void qh_setappend2ndlast(setT **setp, void *elem);
453
void qh_setcheck(setT *set, const char *tname, unsigned id);
454
void qh_setcompact(setT *set);
455
setT *qh_setcopy(setT *set, int extra);
456
void *qh_setdel(setT *set, void *elem);
457
void *qh_setdellast(setT *set);
458
void *qh_setdelnth(setT *set, int nth);
459
void *qh_setdelnthsorted(setT *set, int nth);
460
void *qh_setdelsorted(setT *set, void *newelem);
461
setT *qh_setduplicate( setT *set, int elemsize);
462
int qh_setequal(setT *setA, setT *setB);
463
int qh_setequal_except(setT *setA, void *skipelemA, setT *setB, void *skipelemB);
464
int qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB);
465
void **qh_setendpointer(setT *set);
466
void qh_setfree(setT **set);
467
void qh_setfree2( setT **setp, int elemsize);
468
void qh_setfreelong(setT **set);
469
int qh_setin(setT *set, void *setelem);
470
int qh_setindex(setT *set, void *setelem);
471
void qh_setlarger(setT **setp);
472
void *qh_setlast(setT *set);
473
setT *qh_setnew(int size);
474
setT *qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend);
475
void qh_setprint(FILE *fp, const char* string, setT *set);
476
void qh_setreplace(setT *set, void *oldelem, void *newelem);
477
int qh_setsize(setT *set);
478
setT *qh_settemp(int setsize);
479
void qh_settempfree(setT **set);
480
void qh_settempfree_all(void);
481
setT *qh_settemppop(void);
482
void qh_settemppush(setT *set);
483
void qh_settruncate(setT *set, int size);
484
int qh_setunique(setT **set, void *elem);
485
void qh_setzero(setT *set, int idx, int size);
488
#endif /* qhDEFset */
added
removed
src/libqhull/qset.h
