1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
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: */
|
