diff options
Diffstat (limited to 'generic/tkIntSet.h')
| -rw-r--r-- | generic/tkIntSet.h | 176 |
1 files changed, 176 insertions, 0 deletions
diff --git a/generic/tkIntSet.h b/generic/tkIntSet.h new file mode 100644 index 0000000..b858d8d --- /dev/null +++ b/generic/tkIntSet.h @@ -0,0 +1,176 @@ +/* + * tkSet.h -- + * + * This module implements an integer set. + * + * Copyright (c) 2015-2017 Gregor Cramer + * + * See the file "license.terms" for information on usage and redistribution of + * this file, and for a DISCLAIMER OF ALL WARRANTIES. + */ + +#ifndef _TKINTSET +#define _TKINTSET + +#ifndef _TK +#include "tk.h" +#endif + +#include "tkInt.h" /* required for inline support */ +#include "tkBool.h" + +#if defined(__GNUC__) || defined(__clang__) +# define __warn_unused__ __attribute__((warn_unused_result)) +#else +# define __warn_unused__ +#endif + +struct TkBitField; + + +typedef uint32_t TkIntSetType; + +/* + * The struct below will be shared with the struct TkBitField, so the first two + * members must exactly match the first two members in struct TkBitField. In this + * way we have a struct inheritance, based on the first two members. This + * is portable due to C99 section 6.7.2.1 bullet point 13: + * + * Within a structure object, the non-bit-field members and the units + * in which bit-fields reside have addresses that increase in the order + * in which they are declared. A pointer to a structure object, suitably + * converted, points to its initial member (or if that member is a + * bit-field, then to the unit in which it resides), and vice versa. + * There may be unnamed padding within a structure object, but not at + * beginning. + * + * This inheritance concept is also used in the portable GTK library. + */ + +typedef struct TkIntSet { + uint32_t refCount:31; + uint32_t isSetFlag:1; + TkIntSetType *end; + TkIntSetType *curr; /* mutable */ + TkIntSetType buf[1]; +} TkIntSet; + + +#define TK_SET_NPOS ((unsigned) -1) + + +TkIntSet *TkIntSetNew(); +TkIntSet *TkIntSetFromBits(const struct TkBitField *bf); +void TkIntSetDestroy(TkIntSet **setPtr); + +inline unsigned TkIntSetByteSize(const TkIntSet *set); +inline const unsigned char *TkIntSetData(const TkIntSet *set); + +TkIntSet *TkIntSetCopy(const TkIntSet *set) __warn_unused__; + +TkIntSet *TkIntSetJoin(TkIntSet *dst, const TkIntSet *src) __warn_unused__; +TkIntSet *TkIntSetIntersect(TkIntSet *dst, const TkIntSet *src) __warn_unused__; +TkIntSet *TkIntSetRemove(TkIntSet *dst, const TkIntSet *src) __warn_unused__; + +TkIntSet *TkIntSetJoinBits(TkIntSet *dst, const struct TkBitField *src) __warn_unused__; +TkIntSet *TkIntSetIntersectBits(TkIntSet *dst, const struct TkBitField *src) __warn_unused__; +TkIntSet *TkIntSetRemoveBits(TkIntSet *dst, const struct TkBitField *src) __warn_unused__; +/* dst := src - dst */ +TkIntSet *TkIntSetComplementToBits(TkIntSet *dst, const struct TkBitField *src) __warn_unused__; + +/* dst := dst + set1 + set2 */ +TkIntSet *TkIntSetJoin2(TkIntSet *dst, const TkIntSet *set1, const TkIntSet *set2) __warn_unused__; +/* dst := src - dst */ +TkIntSet *TkIntSetComplementTo(TkIntSet *dst, const TkIntSet *src) __warn_unused__; +/* dst := dst + (set2 - set1) */ +TkIntSet *TkIntSetJoinComplementTo(TkIntSet *dst, const TkIntSet *set1, const TkIntSet *set2) + __warn_unused__; +/* dst := dst + (set1 - set2) + (set2 - set1) */ +TkIntSet *TkIntSetJoinNonIntersection(TkIntSet *dst, const TkIntSet *set1, const TkIntSet *set2) + __warn_unused__; +/* dst := dst + add + ((set1 + set2) - (set1 & set2)) */ +TkIntSet *TkIntSetJoin2ComplementToIntersection(TkIntSet *dst, + const TkIntSet *add, const TkIntSet *set1, const TkIntSet *set2) __warn_unused__; +/* dst := (dst - set1) + (set1 - set2) */ +TkIntSet *TkIntSetJoinOfDifferences(TkIntSet *dst, const TkIntSet *set1, const TkIntSet *set2) + __warn_unused__; + +inline bool TkIntSetIsEmpty(const TkIntSet *set); +inline unsigned TkIntSetSize(const TkIntSet *set); +inline unsigned TkIntSetMax(const TkIntSet *set); + +inline unsigned TkIntSetRefCount(const TkIntSet *set); +inline void TkIntSetIncrRefCount(TkIntSet *set); +inline unsigned TkIntSetDecrRefCount(TkIntSet *set); + +inline TkIntSetType TkIntSetAccess(const TkIntSet *set, unsigned index); + +inline bool TkIntSetTest(const TkIntSet *set, unsigned n); +inline bool TkIntSetNone(const TkIntSet *set); +inline bool TkIntSetAny(const TkIntSet *set); + +inline bool TkIntSetIsEqual(const TkIntSet *set1, const TkIntSet *set2); +inline bool TkIntSetContains(const TkIntSet *set1, const TkIntSet *set2); +inline bool TkIntSetDisjunctive(const TkIntSet *set1, const TkIntSet *set2); +inline bool TkIntSetIntersects(const TkIntSet *set1, const TkIntSet *set2); + +bool TkIntSetIntersectionIsEqual(const TkIntSet *set1, const TkIntSet *set2, + const struct TkBitField *del); +bool TkIntSetIsEqualBits(const TkIntSet *set, const struct TkBitField *bf); +bool TkIntSetContainsBits(const TkIntSet *set, const struct TkBitField *bf); +bool TkIntSetDisjunctiveBits(const TkIntSet *set, const struct TkBitField *bf); +bool TkIntSetIntersectionIsEqualBits(const TkIntSet *set, const struct TkBitField *bf, + const struct TkBitField *del); +bool TkIntSetIsContainedBits(const TkIntSet *set, const struct TkBitField *bf); + +inline unsigned TkIntSetFindFirst(const TkIntSet *set); +inline unsigned TkIntSetFindNext(const TkIntSet *set); + +unsigned TkIntSetFindFirstInIntersection(const TkIntSet *set, const struct TkBitField *bf); + +TkIntSet *TkIntSetAdd(TkIntSet *set, unsigned n) __warn_unused__; +TkIntSet *TkIntSetErase(TkIntSet *set, unsigned n) __warn_unused__; +TkIntSet *TkIntSetTestAndSet(TkIntSet *set, unsigned n) __warn_unused__; +TkIntSet *TkIntSetTestAndUnset(TkIntSet *set, unsigned n) __warn_unused__; +inline TkIntSet *TkIntSetAddOrErase(TkIntSet *set, unsigned n, bool add) __warn_unused__; +TkIntSet *TkIntSetClear(TkIntSet *set) __warn_unused__; + +#ifndef NDEBUG +void TkIntSetPrint(const TkIntSet *set); +#endif + + +#if TK_UNUSED_INTSET_FUNCTIONS + +/* + * These functions are not needed anymore, but shouldn't be removed, because sometimes + * any of these functions might be useful. + */ + +/* dst := (dst + (set - sub)) & set */ +TkIntSet *TkIntSetInnerJoinDifference(TkIntSet *dst, const TkIntSet *set, const TkIntSet *sub) + __warn_unused__; +/* ((set + (add - sub)) & add) == nil */ +bool TkIntSetInnerJoinDifferenceIsEmpty(const TkIntSet *set, const TkIntSet *add, const TkIntSet *sub); +/* set1 == set2 - sub2 */ +bool TkIntSetIsEqualToDifference(const TkIntSet *set1, const TkIntSet *set2, const TkIntSet *sub2); +/* set1 == set2 + (add2 & set2) */ +bool TkIntSetIsEqualToInnerJoin(const TkIntSet *set1, const TkIntSet *set2, const TkIntSet *add2); +/* set1 == ((set2 + (add2 - sub2)) & add2) */ +bool TkIntSetIsEqualToInnerJoinDifference(const TkIntSet *set1, const TkIntSet *set2, + const TkIntSet *add2, const TkIntSet *sub2); +/* ((set1 + (add - sub)) & add) == ((set2 + (add - sub)) & add) */ +bool TkIntSetInnerJoinDifferenceIsEqual(const TkIntSet *set1, const TkIntSet *set2, + const TkIntSet *add, const TkIntSet *sub); + +#endif /* TK_UNUSED_INTSET_FUNCTIONS */ + + +#undef __warn_unused__ + +#ifdef TK_C99_INLINE_SUPPORT +# define _TK_NEED_IMPLEMENTATION +# include "tkIntSetPriv.h" +#endif +#endif /* _TKINTSET */ +/* vi:set ts=8 sw=4: */ |