qset.h
Go to the documentation of this file.
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 */


libqhull-ours
Author(s): Robert Krug
autogenerated on Mon Jan 6 2014 11:32:11