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
|
/*
* bitset.h -- some simple bit vector set operations.
*
* This is useful for sets of small non-negative integers. There are
* some obvious set operations that are not implemented because I
* don't need them right now.
*
* These functions represent sets as arrays of unsigned 32-bit
* integers allocated on the heap. The first entry contains the set
* cardinality (number of elements allowed), followed by one or more
* words containing bit vectors.
*
* $Id: bitset.h,v 1.2 2005/11/23 11:24:29 letz Exp $
*/
/*
* Copyright (C) 2005 Jack O'Quin
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
* published by the Free Software Foundation; either version 2 of the
* License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/
#ifndef __bitset_h__
#define __bitset_h__
#include <inttypes.h> /* POSIX standard fixed-size types */
#include <assert.h> /* `#define NDEBUG' to disable */
/* On some 64-bit machines, this implementation may be slightly
* inefficient, depending on how compilers allocate space for
* uint32_t. For the set sizes I currently need, this is acceptable.
* It should not be hard to pack the bits better, if that becomes
* worthwhile.
*/
typedef uint32_t _bitset_word_t;
typedef _bitset_word_t *bitset_t;
#define WORD_SIZE(cardinality) (1+((cardinality)+31)/32)
#define BYTE_SIZE(cardinality) (WORD_SIZE(cardinality)*sizeof(_bitset_word_t))
#define WORD_INDEX(element) (1+(element)/32)
#define BIT_INDEX(element) ((element)&037)
static inline void
bitset_add(bitset_t set
, unsigned int element)
{
assert(element < set
[0]);
set
[WORD_INDEX(element)] |= (1 << BIT_INDEX(element));
}
static inline void
bitset_copy(bitset_t to_set, bitset_t from_set)
{
assert(to_set[0] == from_set[0]);
memcpy(to_set, from_set, BYTE_SIZE(to_set[0]));
}
static inline void
bitset_create(bitset_t *set
, unsigned int cardinality)
{
*set
= (bitset_t) calloc(WORD_SIZE(cardinality),
sizeof(_bitset_word_t));
assert(*set
);
*set
[0] = cardinality;
}
static inline void
bitset_destroy(bitset_t *set
)
{
if (*set
) {
free(*set
);
*set
= (bitset_t) 0;
}
}
static inline int
bitset_empty(bitset_t set
)
{
int i;
_bitset_word_t result = 0;
int nwords = WORD_SIZE(set
[0]);
for (i = 1; i < nwords; i++) {
result |= set
[i];
}
return (result == 0);
}
static inline int
bitset_contains(bitset_t set
, unsigned int element)
{
assert(element < set
[0]);
return (0 != (set
[WORD_INDEX(element)] & (1 << BIT_INDEX(element))));
}
static inline void
bitset_remove(bitset_t set
, unsigned int element)
{
assert(element < set
[0]);
set
[WORD_INDEX(element)] &= ~(1 << BIT_INDEX(element));
}
#endif /* __bitset_h__ */
|