00001 /*<html><pre> -<a href="qh-set.htm" 00002 >-------------------------------</a><a name="TOP">-</a> 00003 00004 qset.h 00005 header file for qset.c that implements set 00006 00007 see qh-set.htm and qset.c 00008 00009 only uses mem.c, malloc/free 00010 00011 for error handling, writes message and calls 00012 qh_errexit(qhmem_ERRqhull, NULL, NULL); 00013 00014 set operations satisfy the following properties: 00015 - sets have a max size, the actual size (if different) is stored at the end 00016 - every set is NULL terminated 00017 - sets may be sorted or unsorted, the caller must distinguish this 00018 00019 Copyright (c) 1993-2011 The Geometry Center. 00020 $Id: //main/2011/qhull/src/libqhull/qset.h#2 $$Change: 1342 $ 00021 $DateTime: 2011/03/07 21:55:47 $$Author: bbarber $ 00022 */ 00023 00024 #ifndef qhDEFset 00025 #define qhDEFset 1 00026 00027 #include <stdio.h> 00028 00029 /*================= -structures- ===============*/ 00030 00031 #ifndef DEFsetT 00032 #define DEFsetT 1 00033 typedef struct setT setT; /* a set is a sorted or unsorted array of pointers */ 00034 #endif 00035 00036 /*-<a href="qh-set.htm#TOC" 00037 >----------------------------------------</a><a name="setT">-</a> 00038 00039 setT 00040 a set or list of pointers with maximum size and actual size. 00041 00042 variations: 00043 unsorted, unique -- a list of unique pointers with NULL terminator 00044 user guarantees uniqueness 00045 sorted -- a sorted list of unique pointers with NULL terminator 00046 qset.c guarantees uniqueness 00047 unsorted -- a list of pointers terminated with NULL 00048 indexed -- an array of pointers with NULL elements 00049 00050 structure for set of n elements: 00051 00052 -------------- 00053 | maxsize 00054 -------------- 00055 | e[0] - a pointer, may be NULL for indexed sets 00056 -------------- 00057 | e[1] 00058 00059 -------------- 00060 | ... 00061 -------------- 00062 | e[n-1] 00063 -------------- 00064 | e[n] = NULL 00065 -------------- 00066 | ... 00067 -------------- 00068 | e[maxsize] - n+1 or NULL (determines actual size of set) 00069 -------------- 00070 00071 */ 00072 00073 /*-- setelemT -- internal type to allow both pointers and indices 00074 */ 00075 typedef union setelemT setelemT; 00076 union setelemT { 00077 void *p; 00078 int i; /* integer used for e[maxSize] */ 00079 }; 00080 00081 struct setT { 00082 int maxsize; /* maximum number of elements (except NULL) */ 00083 setelemT e[1]; /* array of pointers, tail is NULL */ 00084 /* last slot (unless NULL) is actual size+1 00085 e[maxsize]==NULL or e[e[maxsize]-1]==NULL */ 00086 /* this may generate a warning since e[] contains 00087 maxsize elements */ 00088 }; 00089 00090 /*=========== -constants- =========================*/ 00091 00092 /*-<a href="qh-set.htm#TOC" 00093 >-----------------------------------</a><a name="SETelemsize">-</a> 00094 00095 SETelemsize 00096 size of a set element in bytes 00097 */ 00098 #define SETelemsize ((int)sizeof(setelemT)) 00099 00100 00101 /*=========== -macros- =========================*/ 00102 00103 /*-<a href="qh-set.htm#TOC" 00104 >-----------------------------------</a><a name="FOREACHsetelement_">-</a> 00105 00106 FOREACHsetelement_(type, set, variable) 00107 define FOREACH iterator 00108 00109 declare: 00110 assumes *variable and **variablep are declared 00111 no space in "variable)" [DEC Alpha cc compiler] 00112 00113 each iteration: 00114 variable is set element 00115 variablep is one beyond variable. 00116 00117 to repeat an element: 00118 variablep--; / *repeat* / 00119 00120 at exit: 00121 variable is NULL at end of loop 00122 00123 example: 00124 #define FOREACHfacet_( facets ) FOREACHsetelement_( facetT, facets, facet ) 00125 00126 notes: 00127 use FOREACHsetelement_i_() if need index or include NULLs 00128 00129 WARNING: 00130 nested loops can't use the same variable (define another FOREACH) 00131 00132 needs braces if nested inside another FOREACH 00133 this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} ) 00134 */ 00135 #define FOREACHsetelement_(type, set, variable) \ 00136 if (((variable= NULL), set)) for (\ 00137 variable##p= (type **)&((set)->e[0].p); \ 00138 (variable= *variable##p++);) 00139 00140 /*-<a href="qh-set.htm#TOC" 00141 >----------------------------------------</a><a name="FOREACHsetelement_i_">-</a> 00142 00143 FOREACHsetelement_i_(type, set, variable) 00144 define indexed FOREACH iterator 00145 00146 declare: 00147 type *variable, variable_n, variable_i; 00148 00149 each iteration: 00150 variable is set element, may be NULL 00151 variable_i is index, variable_n is qh_setsize() 00152 00153 to repeat an element: 00154 variable_i--; variable_n-- repeats for deleted element 00155 00156 at exit: 00157 variable==NULL and variable_i==variable_n 00158 00159 example: 00160 #define FOREACHfacet_i_( facets ) FOREACHsetelement_i_( facetT, facets, facet ) 00161 00162 WARNING: 00163 nested loops can't use the same variable (define another FOREACH) 00164 00165 needs braces if nested inside another FOREACH 00166 this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} ) 00167 */ 00168 #define FOREACHsetelement_i_(type, set, variable) \ 00169 if (((variable= NULL), set)) for (\ 00170 variable##_i= 0, variable= (type *)((set)->e[0].p), \ 00171 variable##_n= qh_setsize(set);\ 00172 variable##_i < variable##_n;\ 00173 variable= (type *)((set)->e[++variable##_i].p) ) 00174 00175 /*-<a href="qh-set.htm#TOC" 00176 >--------------------------------------</a><a name="FOREACHsetelementreverse_">-</a> 00177 00178 FOREACHsetelementreverse_(type, set, variable)- 00179 define FOREACH iterator in reverse order 00180 00181 declare: 00182 assumes *variable and **variablep are declared 00183 also declare 'int variabletemp' 00184 00185 each iteration: 00186 variable is set element 00187 00188 to repeat an element: 00189 variabletemp++; / *repeat* / 00190 00191 at exit: 00192 variable is NULL 00193 00194 example: 00195 #define FOREACHvertexreverse_( vertices ) FOREACHsetelementreverse_( vertexT, vertices, vertex ) 00196 00197 notes: 00198 use FOREACHsetelementreverse12_() to reverse first two elements 00199 WARNING: needs braces if nested inside another FOREACH 00200 */ 00201 #define FOREACHsetelementreverse_(type, set, variable) \ 00202 if (((variable= NULL), set)) for (\ 00203 variable##temp= qh_setsize(set)-1, variable= qh_setlast(set);\ 00204 variable; variable= \ 00205 ((--variable##temp >= 0) ? SETelemt_(set, variable##temp, type) : NULL)) 00206 00207 /*-<a href="qh-set.htm#TOC" 00208 >-----------------------------------</a><a name="FOREACHsetelementreverse12_">-</a> 00209 00210 FOREACHsetelementreverse12_(type, set, variable)- 00211 define FOREACH iterator with e[1] and e[0] reversed 00212 00213 declare: 00214 assumes *variable and **variablep are declared 00215 00216 each iteration: 00217 variable is set element 00218 variablep is one after variable. 00219 00220 to repeat an element: 00221 variablep--; / *repeat* / 00222 00223 at exit: 00224 variable is NULL at end of loop 00225 00226 example 00227 #define FOREACHvertexreverse12_( vertices ) FOREACHsetelementreverse12_( vertexT, vertices, vertex ) 00228 00229 notes: 00230 WARNING: needs braces if nested inside another FOREACH 00231 */ 00232 #define FOREACHsetelementreverse12_(type, set, variable) \ 00233 if (((variable= NULL), set)) for (\ 00234 variable##p= (type **)&((set)->e[1].p); \ 00235 (variable= *variable##p); \ 00236 variable##p == ((type **)&((set)->e[0].p))?variable##p += 2: \ 00237 (variable##p == ((type **)&((set)->e[1].p))?variable##p--:variable##p++)) 00238 00239 /*-<a href="qh-set.htm#TOC" 00240 >-----------------------------------</a><a name="FOREACHelem_">-</a> 00241 00242 FOREACHelem_( set )- 00243 iterate elements in a set 00244 00245 declare: 00246 void *elem, *elemp; 00247 00248 each iteration: 00249 elem is set element 00250 elemp is one beyond 00251 00252 to repeat an element: 00253 elemp--; / *repeat* / 00254 00255 at exit: 00256 elem == NULL at end of loop 00257 00258 example: 00259 FOREACHelem_(set) { 00260 00261 notes: 00262 WARNING: needs braces if nested inside another FOREACH 00263 */ 00264 #define FOREACHelem_(set) FOREACHsetelement_(void, set, elem) 00265 00266 /*-<a href="qh-set.htm#TOC" 00267 >-----------------------------------</a><a name="FOREACHset_">-</a> 00268 00269 FOREACHset_( set )- 00270 iterate a set of sets 00271 00272 declare: 00273 setT *set, **setp; 00274 00275 each iteration: 00276 set is set element 00277 setp is one beyond 00278 00279 to repeat an element: 00280 setp--; / *repeat* / 00281 00282 at exit: 00283 set == NULL at end of loop 00284 00285 example 00286 FOREACHset_(sets) { 00287 00288 notes: 00289 WARNING: needs braces if nested inside another FOREACH 00290 */ 00291 #define FOREACHset_(sets) FOREACHsetelement_(setT, sets, set) 00292 00293 /*-<a href="qh-set.htm#TOC" 00294 >-----------------------------------------</a><a name="SETindex_">-</a> 00295 00296 SETindex_( set, elem ) 00297 return index of elem in set 00298 00299 notes: 00300 for use with FOREACH iteration 00301 WARN64 -- Maximum set size is 2G 00302 00303 example: 00304 i= SETindex_(ridges, ridge) 00305 */ 00306 #define SETindex_(set, elem) ((int)((void **)elem##p - (void **)&(set)->e[1].p)) 00307 00308 /*-<a href="qh-set.htm#TOC" 00309 >---------------------------------------</a><a name="SETref_">-</a> 00310 00311 SETref_( elem ) 00312 l.h.s. for modifying the current element in a FOREACH iteration 00313 00314 example: 00315 SETref_(ridge)= anotherridge; 00316 */ 00317 #define SETref_(elem) (elem##p[-1]) 00318 00319 /*-<a href="qh-set.htm#TOC" 00320 >---------------------------------------</a><a name="SETelem_">-</a> 00321 00322 SETelem_(set, n) 00323 return the n'th element of set 00324 00325 notes: 00326 assumes that n is valid [0..size] and that set is defined 00327 use SETelemt_() for type cast 00328 */ 00329 #define SETelem_(set, n) ((set)->e[n].p) 00330 00331 /*-<a href="qh-set.htm#TOC" 00332 >---------------------------------------</a><a name="SETelemt_">-</a> 00333 00334 SETelemt_(set, n, type) 00335 return the n'th element of set as a type 00336 00337 notes: 00338 assumes that n is valid [0..size] and that set is defined 00339 */ 00340 #define SETelemt_(set, n, type) ((type*)((set)->e[n].p)) 00341 00342 /*-<a href="qh-set.htm#TOC" 00343 >---------------------------------------</a><a name="SETelemaddr_">-</a> 00344 00345 SETelemaddr_(set, n, type) 00346 return address of the n'th element of a set 00347 00348 notes: 00349 assumes that n is valid [0..size] and set is defined 00350 */ 00351 #define SETelemaddr_(set, n, type) ((type **)(&((set)->e[n].p))) 00352 00353 /*-<a href="qh-set.htm#TOC" 00354 >---------------------------------------</a><a name="SETfirst_">-</a> 00355 00356 SETfirst_(set) 00357 return first element of set 00358 00359 */ 00360 #define SETfirst_(set) ((set)->e[0].p) 00361 00362 /*-<a href="qh-set.htm#TOC" 00363 >---------------------------------------</a><a name="SETfirstt_">-</a> 00364 00365 SETfirstt_(set, type) 00366 return first element of set as a type 00367 00368 */ 00369 #define SETfirstt_(set, type) ((type*)((set)->e[0].p)) 00370 00371 /*-<a href="qh-set.htm#TOC" 00372 >---------------------------------------</a><a name="SETsecond_">-</a> 00373 00374 SETsecond_(set) 00375 return second element of set 00376 00377 */ 00378 #define SETsecond_(set) ((set)->e[1].p) 00379 00380 /*-<a href="qh-set.htm#TOC" 00381 >---------------------------------------</a><a name="SETsecondt_">-</a> 00382 00383 SETsecondt_(set, type) 00384 return second element of set as a type 00385 */ 00386 #define SETsecondt_(set, type) ((type*)((set)->e[1].p)) 00387 00388 /*-<a href="qh-set.htm#TOC" 00389 >---------------------------------------</a><a name="SETaddr_">-</a> 00390 00391 SETaddr_(set, type) 00392 return address of set's elements 00393 */ 00394 #define SETaddr_(set,type) ((type **)(&((set)->e[0].p))) 00395 00396 /*-<a href="qh-set.htm#TOC" 00397 >---------------------------------------</a><a name="SETreturnsize_">-</a> 00398 00399 SETreturnsize_(set, size) 00400 return size of a set 00401 00402 notes: 00403 set must be defined 00404 use qh_setsize(set) unless speed is critical 00405 */ 00406 #define SETreturnsize_(set, size) (((size)= ((set)->e[(set)->maxsize].i))?(--(size)):((size)= (set)->maxsize)) 00407 00408 /*-<a href="qh-set.htm#TOC" 00409 >---------------------------------------</a><a name="SETempty_">-</a> 00410 00411 SETempty_(set) 00412 return true(1) if set is empty 00413 00414 notes: 00415 set may be NULL 00416 */ 00417 #define SETempty_(set) (!set || (SETfirst_(set) ? 0 : 1)) 00418 00419 /*-<a href="qh-set.htm#TOC" 00420 >-------------------------------<a name="SETsizeaddr_">-</a> 00421 00422 SETsizeaddr_(set) 00423 return pointer to 'actual size+1' of set (set CANNOT be NULL!!) 00424 00425 notes: 00426 *SETsizeaddr==NULL or e[*SETsizeaddr-1].p==NULL 00427 */ 00428 #define SETsizeaddr_(set) (&((set)->e[(set)->maxsize].i)) 00429 00430 /*-<a href="qh-set.htm#TOC" 00431 >---------------------------------------</a><a name="SETtruncate_">-</a> 00432 00433 SETtruncate_(set) 00434 return first element of set 00435 00436 see: 00437 qh_settruncate() 00438 00439 */ 00440 #define SETtruncate_(set, size) {set->e[set->maxsize].i= size+1; /* maybe overwritten */ \ 00441 set->e[size].p= NULL;} 00442 00443 /*======= prototypes in alphabetical order ============*/ 00444 00445 void qh_setaddsorted(setT **setp, void *elem); 00446 void qh_setaddnth(setT **setp, int nth, void *newelem); 00447 void qh_setappend(setT **setp, void *elem); 00448 void qh_setappend_set(setT **setp, setT *setA); 00449 void qh_setappend2ndlast(setT **setp, void *elem); 00450 void qh_setcheck(setT *set, const char *tname, unsigned id); 00451 void qh_setcompact(setT *set); 00452 setT *qh_setcopy(setT *set, int extra); 00453 void *qh_setdel(setT *set, void *elem); 00454 void *qh_setdellast(setT *set); 00455 void *qh_setdelnth(setT *set, int nth); 00456 void *qh_setdelnthsorted(setT *set, int nth); 00457 void *qh_setdelsorted(setT *set, void *newelem); 00458 setT *qh_setduplicate( setT *set, int elemsize); 00459 int qh_setequal(setT *setA, setT *setB); 00460 int qh_setequal_except(setT *setA, void *skipelemA, setT *setB, void *skipelemB); 00461 int qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB); 00462 void qh_setfree(setT **set); 00463 void qh_setfree2( setT **setp, int elemsize); 00464 void qh_setfreelong(setT **set); 00465 int qh_setin(setT *set, void *setelem); 00466 int qh_setindex(setT *set, void *setelem); 00467 void qh_setlarger(setT **setp); 00468 void *qh_setlast(setT *set); 00469 setT *qh_setnew(int size); 00470 setT *qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend); 00471 void qh_setprint(FILE *fp, const char* string, setT *set); 00472 void qh_setreplace(setT *set, void *oldelem, void *newelem); 00473 int qh_setsize(setT *set); 00474 setT *qh_settemp(int setsize); 00475 void qh_settempfree(setT **set); 00476 void qh_settempfree_all(void); 00477 setT *qh_settemppop(void); 00478 void qh_settemppush(setT *set); 00479 void qh_settruncate(setT *set, int size); 00480 int qh_setunique(setT **set, void *elem); 00481 void qh_setzero(setT *set, int idx, int size); 00482 00483 00484 #endif /* qhDEFset */