include/libqhull_r/qset_r.h

0001 /*<html><pre>  -<a                             href="qh-set_r.htm"
0002   >-------------------------------</a><a name="TOP">-</a>
0003
0004    qset_r.h
0005      header file for qset_r.c that implements set
0006
0007    see qh-set_r.htm and qset_r.c
0008
0009    only uses mem_r.c, malloc/free
0010
0011    for error handling, writes message and calls
0012       qh_errexit(qhT *qh, qhmem_ERRqhull, NULL, NULL);
0013
0014    set operations satisfy the following properties:
0015     - sets have a max size, the actual size (if different) is stored at the end
0016     - every set is NULL terminated
0017     - sets may be sorted or unsorted, the caller must distinguish this
0018
0019    Copyright (c) 1993-2020 The Geometry Center.
0020    $Id: //main/2019/qhull/src/libqhull_r/qset_r.h#4 $$Change: 2953 $
0021    $DateTime: 2020/05/21 22:05:32 $$Author: bbarber $
0022 */
0023
0024 #ifndef qhDEFset
0025 #define qhDEFset 1
0026
0027 #include <stdio.h>
0028
0029 /*================= -structures- ===============*/
0030
0031 #ifndef DEFsetT
0032 #define DEFsetT 1
0033 typedef struct setT setT;   /* a set is a sorted or unsorted array of pointers */
0034 #endif
0035
0036 #ifndef DEFqhT
0037 #define DEFqhT 1
0038 typedef struct qhT qhT;          /* defined in libqhull_r.h */
0039 #endif
0040
0041 /* [jan'15] Decided not to use countT.  Most sets are small.  The code uses signed tests */
0042
0043 /*-<a                                      href="qh-set_r.htm#TOC"
0044 >----------------------------------------</a><a name="setT">-</a>
0045
0046 setT
0047   a set or list of pointers with maximum size and actual size.
0048
0049 variations:
0050   unsorted, unique   -- a list of unique pointers with NULL terminator
0051                            user guarantees uniqueness
0052   sorted             -- a sorted list of unique pointers with NULL terminator
0053                            qset_r.c guarantees uniqueness
0054   unsorted           -- a list of pointers terminated with NULL
0055   indexed            -- an array of pointers with NULL elements
0056
0057 structure for set of n elements:
0058
0059         --------------
0060         |  maxsize
0061         --------------
0062         |  e[0] - a pointer, may be NULL for indexed sets
0063         --------------
0064         |  e[1]
0065
0066         --------------
0067         |  ...
0068         --------------
0069         |  e[n-1]
0070         --------------
0071         |  e[n] = NULL
0072         --------------
0073         |  ...
0074         --------------
0075         |  e[maxsize] - n+1 or NULL (determines actual size of set)
0076         --------------
0077
0078 */
0079
0080 /*-- setelemT -- internal type to allow both pointers and indices
0081 */
0082 typedef union setelemT setelemT;
0083 union setelemT {
0084   void    *p;
0085   int   i;         /* integer used for e[maxSize] */
0086 };
0087
0088 struct setT {
0089   int maxsize;          /* maximum number of elements (except NULL) */
0090   setelemT e[1];        /* array of pointers, tail is NULL */
0091                         /* last slot (unless NULL) is actual size+1
0092                            e[maxsize]==NULL or e[e[maxsize]-1]==NULL */
0093                         /* this may generate a warning since e[] contains
0094                            maxsize elements */
0095 };
0096
0097 /*=========== -constants- =========================*/
0098
0099 /*-<a                                 href="qh-set_r.htm#TOC"
0100   >-----------------------------------</a><a name="SETelemsize">-</a>
0101
0102   SETelemsize
0103     size of a set element in bytes
0104 */
0105 #define SETelemsize ((int)sizeof(setelemT))
0106
0107
0108 /*=========== -macros- =========================*/
0109
0110 /*-<a                                 href="qh-set_r.htm#TOC"
0111   >-----------------------------------</a><a name="FOREACHsetelement_">-</a>
0112
0113    FOREACHsetelement_(type, set, variable)
0114      define FOREACH iterator
0115
0116    declare:
0117      assumes *variable and **variablep are declared
0118      no space in "variable)" [DEC Alpha cc compiler]
0119
0120    each iteration:
0121      variable is set element
0122      variablep is one beyond variable.
0123
0124    to repeat an element:
0125      variablep--; / *repeat* /
0126
0127    at exit:
0128      variable is NULL at end of loop
0129
0130    example:
0131      #define FOREACHfacet_(facets) FOREACHsetelement_(facetT, facets, facet)
0132
0133    notes:
0134      use FOREACHsetelement_i_() if need index or include NULLs
0135      assumes set is not modified
0136
0137    WARNING:
0138      nested loops can't use the same variable (define another FOREACH)
0139
0140      needs braces if nested inside another FOREACH
0141      this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} )
0142 */
0143 #define FOREACHsetelement_(type, set, variable) \
0144         if (((variable= NULL), set)) for (\
0145           variable##p= (type **)&((set)->e[0].p); \
0146           (variable= *variable##p++);)
0147
0148 /*-<a                                      href="qh-set_r.htm#TOC"
0149   >----------------------------------------</a><a name="FOREACHsetelement_i_">-</a>
0150
0151    FOREACHsetelement_i_(qh, type, set, variable)
0152      define indexed FOREACH iterator
0153
0154    declare:
0155      type *variable, variable_n, variable_i;
0156
0157    each iteration:
0158      variable is set element, may be NULL
0159      variable_i is index, variable_n is qh_setsize()
0160
0161    to repeat an element:
0162      variable_i--; variable_n-- repeats for deleted element
0163
0164    at exit:
0165      variable==NULL and variable_i==variable_n
0166
0167    example:
0168      #define FOREACHfacet_i_(qh, facets) FOREACHsetelement_i_(qh, facetT, facets, facet)
0169
0170    WARNING:
0171      nested loops can't use the same variable (define another FOREACH)
0172
0173      needs braces if nested inside another FOREACH
0174      this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} )
0175 */
0176 #define FOREACHsetelement_i_(qh, type, set, variable) \
0177         if (((variable= NULL), set)) for (\
0178           variable##_i= 0, variable= (type *)((set)->e[0].p), \
0179                    variable##_n= qh_setsize(qh, set);\
0180           variable##_i < variable##_n;\
0181           variable= (type *)((set)->e[++variable##_i].p) )
0182
0183 /*-<a                                    href="qh-set_r.htm#TOC"
0184   >--------------------------------------</a><a name="FOREACHsetelementreverse_">-</a>
0185
0186    FOREACHsetelementreverse_(qh, type, set, variable)-
0187      define FOREACH iterator in reverse order
0188
0189    declare:
0190      assumes *variable and **variablep are declared
0191      also declare 'int variabletemp'
0192
0193    each iteration:
0194      variable is set element
0195
0196    to repeat an element:
0197      variabletemp++; / *repeat* /
0198
0199    at exit:
0200      variable is NULL
0201
0202    example:
0203      #define FOREACHvertexreverse_(vertices) FOREACHsetelementreverse_(vertexT, vertices, vertex)
0204
0205    notes:
0206      use FOREACHsetelementreverse12_() to reverse first two elements
0207      WARNING: needs braces if nested inside another FOREACH
0208 */
0209 #define FOREACHsetelementreverse_(qh, type, set, variable) \
0210         if (((variable= NULL), set)) for (\
0211            variable##temp= qh_setsize(qh, set)-1, variable= qh_setlast(qh, set);\
0212            variable; variable= \
0213            ((--variable##temp >= 0) ? SETelemt_(set, variable##temp, type) : NULL))
0214
0215 /*-<a                                 href="qh-set_r.htm#TOC"
0216   >-----------------------------------</a><a name="FOREACHsetelementreverse12_">-</a>
0217
0218    FOREACHsetelementreverse12_(type, set, variable)-
0219      define FOREACH iterator with e[1] and e[0] reversed
0220
0221    declare:
0222      assumes *variable and **variablep are declared
0223
0224    each iteration:
0225      variable is set element
0226      variablep is one after variable.
0227
0228    to repeat an element:
0229      variablep--; / *repeat* /
0230
0231    at exit:
0232      variable is NULL at end of loop
0233
0234    example
0235      #define FOREACHvertexreverse12_(vertices) FOREACHsetelementreverse12_(vertexT, vertices, vertex)
0236
0237    notes:
0238      WARNING: needs braces if nested inside another FOREACH
0239 */
0240 #define FOREACHsetelementreverse12_(type, set, variable) \
0241         if (((variable= NULL), set)) for (\
0242           variable##p= (type **)&((set)->e[1].p); \
0243           (variable= *variable##p); \
0244           variable##p == ((type **)&((set)->e[0].p))?variable##p += 2: \
0245               (variable##p == ((type **)&((set)->e[1].p))?variable##p--:variable##p++))
0246
0247 /*-<a                                 href="qh-set_r.htm#TOC"
0248   >-----------------------------------</a><a name="FOREACHelem_">-</a>
0249
0250    FOREACHelem_( set )-
0251      iterate elements in a set
0252
0253    declare:
0254      void *elem, *elemp;
0255
0256    each iteration:
0257      elem is set element
0258      elemp is one beyond
0259
0260    to repeat an element:
0261      elemp--; / *repeat* /
0262
0263    at exit:
0264      elem == NULL at end of loop
0265
0266    example:
0267      FOREACHelem_(set) {
0268
0269    notes:
0270      assumes set is not modified
0271      WARNING: needs braces if nested inside another FOREACH
0272 */
0273 #define FOREACHelem_(set) FOREACHsetelement_(void, set, elem)
0274
0275 /*-<a                                 href="qh-set_r.htm#TOC"
0276   >-----------------------------------</a><a name="FOREACHset_">-</a>
0277
0278    FOREACHset_( set )-
0279      iterate a set of sets
0280
0281    declare:
0282      setT *set, **setp;
0283
0284    each iteration:
0285      set is set element
0286      setp is one beyond
0287
0288    to repeat an element:
0289      setp--; / *repeat* /
0290
0291    at exit:
0292      set == NULL at end of loop
0293
0294    example
0295      FOREACHset_(sets) {
0296
0297    notes:
0298      WARNING: needs braces if nested inside another FOREACH
0299 */
0300 #define FOREACHset_(sets) FOREACHsetelement_(setT, sets, set)
0301
0302 /*-<a                                       href="qh-set_r.htm#TOC"
0303   >-----------------------------------------</a><a name="SETindex_">-</a>
0304
0305    SETindex_( set, elem )
0306      return index of elem in set
0307
0308    notes:
0309      for use with FOREACH iteration
0310      WARN64 -- Maximum set size is 2G
0311
0312    example:
0313      i= SETindex_(ridges, ridge)
0314 */
0315 #define SETindex_(set, elem) ((int)((void **)elem##p - (void **)&(set)->e[1].p))
0316
0317 /*-<a                                     href="qh-set_r.htm#TOC"
0318   >---------------------------------------</a><a name="SETref_">-</a>
0319
0320    SETref_( elem )
0321      l.h.s. for modifying the current element in a FOREACH iteration
0322
0323    example:
0324      SETref_(ridge)= anotherridge;
0325 */
0326 #define SETref_(elem) (elem##p[-1])
0327
0328 /*-<a                                     href="qh-set_r.htm#TOC"
0329   >---------------------------------------</a><a name="SETelem_">-</a>
0330
0331    SETelem_(set, n)
0332      return the n'th element of set
0333
0334    notes:
0335       assumes that n is valid [0..size] and that set is defined
0336       use SETelemt_() for type cast
0337 */
0338 #define SETelem_(set, n)           ((set)->e[n].p)
0339
0340 /*-<a                                     href="qh-set_r.htm#TOC"
0341   >---------------------------------------</a><a name="SETelemt_">-</a>
0342
0343    SETelemt_(set, n, type)
0344      return the n'th element of set as a type
0345
0346    notes:
0347       assumes that n is valid [0..size] and that set is defined
0348 */
0349 #define SETelemt_(set, n, type)    ((type *)((set)->e[n].p))
0350
0351 /*-<a                                     href="qh-set_r.htm#TOC"
0352   >---------------------------------------</a><a name="SETelemaddr_">-</a>
0353
0354    SETelemaddr_(set, n, type)
0355      return address of the n'th element of a set
0356
0357    notes:
0358       assumes that n is valid [0..size] and set is defined
0359 */
0360 #define SETelemaddr_(set, n, type) ((type **)(&((set)->e[n].p)))
0361
0362 /*-<a                                     href="qh-set_r.htm#TOC"
0363   >---------------------------------------</a><a name="SETfirst_">-</a>
0364
0365    SETfirst_(set)
0366      return first element of set
0367
0368 */
0369 #define SETfirst_(set)             ((set)->e[0].p)
0370
0371 /*-<a                                     href="qh-set_r.htm#TOC"
0372   >---------------------------------------</a><a name="SETfirstt_">-</a>
0373
0374    SETfirstt_(set, type)
0375      return first element of set as a type
0376
0377 */
0378 #define SETfirstt_(set, type)      ((type *)((set)->e[0].p))
0379
0380 /*-<a                                     href="qh-set_r.htm#TOC"
0381   >---------------------------------------</a><a name="SETsecond_">-</a>
0382
0383    SETsecond_(set)
0384      return second element of set
0385
0386 */
0387 #define SETsecond_(set)            ((set)->e[1].p)
0388
0389 /*-<a                                     href="qh-set_r.htm#TOC"
0390   >---------------------------------------</a><a name="SETsecondt_">-</a>
0391
0392    SETsecondt_(set, type)
0393      return second element of set as a type
0394 */
0395 #define SETsecondt_(set, type)     ((type *)((set)->e[1].p))
0396
0397 /*-<a                                     href="qh-set_r.htm#TOC"
0398   >---------------------------------------</a><a name="SETaddr_">-</a>
0399
0400    SETaddr_(set, type)
0401        return address of set's elements
0402 */
0403 #define SETaddr_(set,type)         ((type **)(&((set)->e[0].p)))
0404
0405 /*-<a                                     href="qh-set_r.htm#TOC"
0406   >---------------------------------------</a><a name="SETreturnsize_">-</a>
0407
0408    SETreturnsize_(set, size)
0409      return size of a set
0410
0411    notes:
0412       set must be defined
0413       use qh_setsize(qhT *qh, set) unless speed is critical
0414 */
0415 #define SETreturnsize_(set, size) (((size)= ((set)->e[(set)->maxsize].i))?(--(size)):((size)= (set)->maxsize))
0416
0417 /*-<a                                     href="qh-set_r.htm#TOC"
0418   >---------------------------------------</a><a name="SETempty_">-</a>
0419
0420    SETempty_(set)
0421      return true(1) if set is empty (i.e., FOREACHsetelement_ is empty)
0422
0423    notes:
0424       set may be NULL
0425       qh_setsize may be non-zero if first element is NULL
0426 */
0427 #define SETempty_(set)            (!set || (SETfirst_(set) ? 0 : 1))
0428
0429 /*-<a                             href="qh-set_r.htm#TOC"
0430   >-------------------------------<a name="SETsizeaddr_">-</a>
0431
0432   SETsizeaddr_(set)
0433     return pointer to 'actual size+1' of set (set CANNOT be NULL!!)
0434     Its type is setelemT* for strict aliasing
0435     All SETelemaddr_ must be cast to setelemT
0436
0437
0438   notes:
0439     *SETsizeaddr==NULL or e[*SETsizeaddr-1].p==NULL
0440 */
0441 #define SETsizeaddr_(set) (&((set)->e[(set)->maxsize]))
0442
0443 /*-<a                                     href="qh-set_r.htm#TOC"
0444   >---------------------------------------</a><a name="SETtruncate_">-</a>
0445
0446    SETtruncate_(set, size)
0447      truncate set to size
0448
0449    see:
0450      qh_settruncate()
0451
0452 */
0453 #define SETtruncate_(set, size) {set->e[set->maxsize].i= size+1; /* maybe overwritten */ \
0454       set->e[size].p= NULL;}
0455
0456 /*======= prototypes in alphabetical order ============*/
0457
0458 #ifdef __cplusplus
0459 extern "C" {
0460 #endif
0461
0462 void  qh_setaddsorted(qhT *qh, setT **setp, void *elem);
0463 void  qh_setaddnth(qhT *qh, setT **setp, int nth, void *newelem);
0464 void  qh_setappend(qhT *qh, setT **setp, void *elem);
0465 void  qh_setappend_set(qhT *qh, setT **setp, setT *setA);
0466 void  qh_setappend2ndlast(qhT *qh, setT **setp, void *elem);
0467 void  qh_setcheck(qhT *qh, setT *set, const char *tname, unsigned int id);
0468 void  qh_setcompact(qhT *qh, setT *set);
0469 setT *qh_setcopy(qhT *qh, setT *set, int extra);
0470 void *qh_setdel(setT *set, void *elem);
0471 void *qh_setdellast(setT *set);
0472 void *qh_setdelnth(qhT *qh, setT *set, int nth);
0473 void *qh_setdelnthsorted(qhT *qh, setT *set, int nth);
0474 void *qh_setdelsorted(setT *set, void *newelem);
0475 setT *qh_setduplicate(qhT *qh, setT *set, int elemsize);
0476 void **qh_setendpointer(setT *set);
0477 int   qh_setequal(setT *setA, setT *setB);
0478 int   qh_setequal_except(setT *setA, void *skipelemA, setT *setB, void *skipelemB);
0479 int   qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB);
0480 void  qh_setfree(qhT *qh, setT **set);
0481 void  qh_setfree2(qhT *qh, setT **setp, int elemsize);
0482 void  qh_setfreelong(qhT *qh, setT **set);
0483 int   qh_setin(setT *set, void *setelem);
0484 int   qh_setindex(setT *set, void *setelem);
0485 void  qh_setlarger(qhT *qh, setT **setp);
0486 int   qh_setlarger_quick(qhT *qh, int setsize, int *newsize);
0487 void *qh_setlast(setT *set);
0488 setT *qh_setnew(qhT *qh, int size);
0489 setT *qh_setnew_delnthsorted(qhT *qh, setT *set, int size, int nth, int prepend);
0490 void  qh_setprint(qhT *qh, FILE *fp, const char* string, setT *set);
0491 void  qh_setreplace(qhT *qh, setT *set, void *oldelem, void *newelem);
0492 int   qh_setsize(qhT *qh, setT *set);
0493 setT *qh_settemp(qhT *qh, int setsize);
0494 void  qh_settempfree(qhT *qh, setT **set);
0495 void  qh_settempfree_all(qhT *qh);
0496 setT *qh_settemppop(qhT *qh);
0497 void  qh_settemppush(qhT *qh, setT *set);
0498 void  qh_settruncate(qhT *qh, setT *set, int size);
0499 int   qh_setunique(qhT *qh, setT **set, void *elem);
0500 void  qh_setzero(qhT *qh, setT *set, int idx, int size);
0501
0502 #ifdef __cplusplus
0503 } /* extern "C" */
0504 #endif
0505
0506 #endif /* qhDEFset */