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-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 $ 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 /*-<a href="qh-set.htm#TOC" 37 >----------------------------------------</a><a name="setT">-</a> 38 39 setT 40 a set or list of pointers with maximum size and actual size. 41 42 variations: 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 49 50 structure for set of n elements: 51 52 -------------- 53 | maxsize 54 -------------- 55 | e[0] - a pointer, may be NULL for indexed sets 56 -------------- 57 | e[1] 58 59 -------------- 60 | ... 61 -------------- 62 | e[n-1] 63 -------------- 64 | e[n] = NULL 65 -------------- 66 | ... 67 -------------- 68 | e[maxsize] - n+1 or NULL (determines actual size of set) 69 -------------- 70 71 */ 72 73 /*-- setelemT -- internal type to allow both pointers and indices 74 */ 75 typedef union setelemT setelemT; 76 union setelemT { 77 void *p; 78 int i; /* integer used for e[maxSize] */ 79 }; 80 81 struct setT { 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 87 maxsize elements */ 88 }; 89 90 /*=========== -constants- =========================*/ 91 92 /*-<a href="qh-set.htm#TOC" 93 >-----------------------------------</a><a name="SETelemsize">-</a> 94 95 SETelemsize 96 size of a set element in bytes 97 */ 98 #define SETelemsize ((int)sizeof(setelemT)) 99 100 101 /*=========== -macros- =========================*/ 102 103 /*-<a href="qh-set.htm#TOC" 104 >-----------------------------------</a><a name="FOREACHsetelement_">-</a> 105 106 FOREACHsetelement_(type, set, variable) 107 define FOREACH iterator 108 109 declare: 110 assumes *variable and **variablep are declared 111 no space in "variable)" [DEC Alpha cc compiler] 112 113 each iteration: 114 variable is set element 115 variablep is one beyond variable. 116 117 to repeat an element: 118 variablep--; / *repeat* / 119 120 at exit: 121 variable is NULL at end of loop 122 123 example: 124 #define FOREACHfacet_( facets ) FOREACHsetelement_( facetT, facets, facet ) 125 126 notes: 127 use FOREACHsetelement_i_() if need index or include NULLs 128 129 WARNING: 130 nested loops can't use the same variable (define another FOREACH) 131 132 needs braces if nested inside another FOREACH 133 this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} ) 134 */ 135 #define FOREACHsetelement_(type, set, variable) \ 136 if (((variable= NULL), set)) for (\ 137 variable##p= (type **)&((set)->e[0].p); \ 138 (variable= *variable##p++);) 139 140 /*-<a href="qh-set.htm#TOC" 141 >----------------------------------------</a><a name="FOREACHsetelement_i_">-</a> 142 143 FOREACHsetelement_i_(type, set, variable) 144 define indexed FOREACH iterator 145 146 declare: 147 type *variable, variable_n, variable_i; 148 149 each iteration: 150 variable is set element, may be NULL 151 variable_i is index, variable_n is qh_setsize() 152 153 to repeat an element: 154 variable_i--; variable_n-- repeats for deleted element 155 156 at exit: 157 variable==NULL and variable_i==variable_n 158 159 example: 160 #define FOREACHfacet_i_( facets ) FOREACHsetelement_i_( facetT, facets, facet ) 161 162 WARNING: 163 nested loops can't use the same variable (define another FOREACH) 164 165 needs braces if nested inside another FOREACH 166 this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} ) 167 */ 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) ) 174 175 /*-<a href="qh-set.htm#TOC" 176 >--------------------------------------</a><a name="FOREACHsetelementreverse_">-</a> 177 178 FOREACHsetelementreverse_(type, set, variable)- 179 define FOREACH iterator in reverse order 180 181 declare: 182 assumes *variable and **variablep are declared 183 also declare 'int variabletemp' 184 185 each iteration: 186 variable is set element 187 188 to repeat an element: 189 variabletemp++; / *repeat* / 190 191 at exit: 192 variable is NULL 193 194 example: 195 #define FOREACHvertexreverse_( vertices ) FOREACHsetelementreverse_( vertexT, vertices, vertex ) 196 197 notes: 198 use FOREACHsetelementreverse12_() to reverse first two elements 199 WARNING: needs braces if nested inside another FOREACH 200 */ 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)) 206 207 /*-<a href="qh-set.htm#TOC" 208 >-----------------------------------</a><a name="FOREACHsetelementreverse12_">-</a> 209 210 FOREACHsetelementreverse12_(type, set, variable)- 211 define FOREACH iterator with e[1] and e[0] reversed 212 213 declare: 214 assumes *variable and **variablep are declared 215 216 each iteration: 217 variable is set element 218 variablep is one after variable. 219 220 to repeat an element: 221 variablep--; / *repeat* / 222 223 at exit: 224 variable is NULL at end of loop 225 226 example 227 #define FOREACHvertexreverse12_( vertices ) FOREACHsetelementreverse12_( vertexT, vertices, vertex ) 228 229 notes: 230 WARNING: needs braces if nested inside another FOREACH 231 */ 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++)) 238 239 /*-<a href="qh-set.htm#TOC" 240 >-----------------------------------</a><a name="FOREACHelem_">-</a> 241 242 FOREACHelem_( set )- 243 iterate elements in a set 244 245 declare: 246 void *elem, *elemp; 247 248 each iteration: 249 elem is set element 250 elemp is one beyond 251 252 to repeat an element: 253 elemp--; / *repeat* / 254 255 at exit: 256 elem == NULL at end of loop 257 258 example: 259 FOREACHelem_(set) { 260 261 notes: 262 WARNING: needs braces if nested inside another FOREACH 263 */ 264 #define FOREACHelem_(set) FOREACHsetelement_(void, set, elem) 265 266 /*-<a href="qh-set.htm#TOC" 267 >-----------------------------------</a><a name="FOREACHset_">-</a> 268 269 FOREACHset_( set )- 270 iterate a set of sets 271 272 declare: 273 setT *set, **setp; 274 275 each iteration: 276 set is set element 277 setp is one beyond 278 279 to repeat an element: 280 setp--; / *repeat* / 281 282 at exit: 283 set == NULL at end of loop 284 285 example 286 FOREACHset_(sets) { 287 288 notes: 289 WARNING: needs braces if nested inside another FOREACH 290 */ 291 #define FOREACHset_(sets) FOREACHsetelement_(setT, sets, set) 292 293 /*-<a href="qh-set.htm#TOC" 294 >-----------------------------------------</a><a name="SETindex_">-</a> 295 296 SETindex_( set, elem ) 297 return index of elem in set 298 299 notes: 300 for use with FOREACH iteration 301 WARN64 -- Maximum set size is 2G 302 303 example: 304 i= SETindex_(ridges, ridge) 305 */ 306 #define SETindex_(set, elem) ((int)((void **)elem##p - (void **)&(set)->e[1].p)) 307 308 /*-<a href="qh-set.htm#TOC" 309 >---------------------------------------</a><a name="SETref_">-</a> 310 311 SETref_( elem ) 312 l.h.s. for modifying the current element in a FOREACH iteration 313 314 example: 315 SETref_(ridge)= anotherridge; 316 */ 317 #define SETref_(elem) (elem##p[-1]) 318 319 /*-<a href="qh-set.htm#TOC" 320 >---------------------------------------</a><a name="SETelem_">-</a> 321 322 SETelem_(set, n) 323 return the n'th element of set 324 325 notes: 326 assumes that n is valid [0..size] and that set is defined 327 use SETelemt_() for type cast 328 */ 329 #define SETelem_(set, n) ((set)->e[n].p) 330 331 /*-<a href="qh-set.htm#TOC" 332 >---------------------------------------</a><a name="SETelemt_">-</a> 333 334 SETelemt_(set, n, type) 335 return the n'th element of set as a type 336 337 notes: 338 assumes that n is valid [0..size] and that set is defined 339 */ 340 #define SETelemt_(set, n, type) ((type*)((set)->e[n].p)) 341 342 /*-<a href="qh-set.htm#TOC" 343 >---------------------------------------</a><a name="SETelemaddr_">-</a> 344 345 SETelemaddr_(set, n, type) 346 return address of the n'th element of a set 347 348 notes: 349 assumes that n is valid [0..size] and set is defined 350 */ 351 #define SETelemaddr_(set, n, type) ((type **)(&((set)->e[n].p))) 352 353 /*-<a href="qh-set.htm#TOC" 354 >---------------------------------------</a><a name="SETfirst_">-</a> 355 356 SETfirst_(set) 357 return first element of set 358 359 */ 360 #define SETfirst_(set) ((set)->e[0].p) 361 362 /*-<a href="qh-set.htm#TOC" 363 >---------------------------------------</a><a name="SETfirstt_">-</a> 364 365 SETfirstt_(set, type) 366 return first element of set as a type 367 368 */ 369 #define SETfirstt_(set, type) ((type*)((set)->e[0].p)) 370 371 /*-<a href="qh-set.htm#TOC" 372 >---------------------------------------</a><a name="SETsecond_">-</a> 373 374 SETsecond_(set) 375 return second element of set 376 377 */ 378 #define SETsecond_(set) ((set)->e[1].p) 379 380 /*-<a href="qh-set.htm#TOC" 381 >---------------------------------------</a><a name="SETsecondt_">-</a> 382 383 SETsecondt_(set, type) 384 return second element of set as a type 385 */ 386 #define SETsecondt_(set, type) ((type*)((set)->e[1].p)) 387 388 /*-<a href="qh-set.htm#TOC" 389 >---------------------------------------</a><a name="SETaddr_">-</a> 390 391 SETaddr_(set, type) 392 return address of set's elements 393 */ 394 #define SETaddr_(set,type) ((type **)(&((set)->e[0].p))) 395 396 /*-<a href="qh-set.htm#TOC" 397 >---------------------------------------</a><a name="SETreturnsize_">-</a> 398 399 SETreturnsize_(set, size) 400 return size of a set 401 402 notes: 403 set must be defined 404 use qh_setsize(set) unless speed is critical 405 */ 406 #define SETreturnsize_(set, size) (((size)= ((set)->e[(set)->maxsize].i))?(--(size)):((size)= (set)->maxsize)) 407 408 /*-<a href="qh-set.htm#TOC" 409 >---------------------------------------</a><a name="SETempty_">-</a> 410 411 SETempty_(set) 412 return true(1) if set is empty 413 414 notes: 415 set may be NULL 416 */ 417 #define SETempty_(set) (!set || (SETfirst_(set) ? 0 : 1)) 418 419 /*-<a href="qh-set.htm#TOC" 420 >-------------------------------<a name="SETsizeaddr_">-</a> 421 422 SETsizeaddr_(set) 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 426 427 428 notes: 429 *SETsizeaddr==NULL or e[*SETsizeaddr-1].p==NULL 430 */ 431 #define SETsizeaddr_(set) (&((set)->e[(set)->maxsize])) 432 433 /*-<a href="qh-set.htm#TOC" 434 >---------------------------------------</a><a name="SETtruncate_">-</a> 435 436 SETtruncate_(set, size) 437 truncate set to size 438 439 see: 440 qh_settruncate() 441 442 */ 443 #define SETtruncate_(set, size) {set->e[set->maxsize].i= size+1; /* maybe overwritten */ \ 444 set->e[size].p= NULL;} 445 446 /*======= prototypes in alphabetical order ============*/ 447 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); 486 487 488 #endif /* qhDEFset */ 489