include/libqhull/qset.h

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