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
|
#ifndef LIBNAGIOS_bitmap_h__
#define LIBNAGIOS_bitmap_h__
/**
* @file bitmap.h
* @brief Bit map API
*
* The bitmap api is useful for running set operations on objects
* indexed by unsigned integers.
* @{
*/
struct bitmap;
typedef struct bitmap bitmap;
/**
* Resize a bitmap
* If the bitmap is made smaller, data will silently be lost.
*
* @param bm The bitmap to resize
* @param size The new desired size of the bitmap
* @return 0 on success, -1 on errors.
*/
extern int bitmap_resize(bitmap *bm, unsigned long size);
/**
* Create a bitmaptor of size 'size'
* @param size Desired storage capacity
* @return A bitmap pointer on success, NULL on errors
*/
extern bitmap *bitmap_create(unsigned long size);
/**
* Destroy a bitmaptor by freeing all the memory it uses
* @param bm The bitmaptor to destroy
*/
extern void bitmap_destroy(bitmap *bm);
/**
* Copy a bitmaptor
* @param bm The bitmaptor to copy
* @return Pointer to an identical bitmap on success, NULL on errors
*/
extern bitmap *bitmap_copy(const bitmap *bm);
/**
* Set a bit in the map
* @param bm The bitmaptor to operate on
* @param pos Position of the bit to set
* @return 0 on success, -1 on errors
*/
extern int bitmap_set(bitmap *bm, unsigned long pos);
/**
* Check if a particular bit is set in the map
* @param bm The bitmaptor to check
* @param pos Position of the bit to check
* @return 1 if set, otherwise 0
*/
extern int bitmap_isset(const bitmap *bm, unsigned long pos);
/**
* Unset a particular bit in the map
* @param bm The bitmaptor to operate on
* @param pos Position of the bit to unset
*/
extern int bitmap_unset(bitmap *bm, unsigned long pos);
/**
* Obtain cardinality (max number of elements) of the bitmaptor
* @param bm The bitmaptor to check
* @return The cardinality of the bitmaptor
*/
extern unsigned long bitmap_cardinality(const bitmap *bm);
#define bitmap_size bitmap_cardinality
/**
* Count set bits in map. Completed in O(n/8) time.
* @param bm The bitmaptor to count bits in
* @return The number of set bits
*/
extern unsigned long bitmap_count_set_bits(const bitmap *bm);
/**
* Count unset bits in map. Completed in O(n/8) time.
* @param bm The bitmaptor to count bits in
* @return The number of set bits
*/
extern unsigned long bitmap_count_unset_bits(const bitmap *bm);
/**
* Unset all bits in a bitmap
* @param bm The bitmap to clear
*/
extern void bitmap_clear(bitmap *bm);
/**
* Calculate intersection of two bitmaps
* The intersection is defined as all bits that are members of
* both A and B. It's equivalent to bitwise AND.
* This function completes in O(n/sizeof(long)) operations.
* @param a The first bitmaptor
* @param b The second bitmaptor
* @return NULL on errors; A newly created bitmaptor on success.
*/
extern bitmap *bitmap_intersect(const bitmap *a, const bitmap *b);
/**
* Calculate union of two bitmaps
* The union is defined as all bits that are members of
* A or B or both A and B. It's equivalent to bitwise OR.
* This function completes in O(n/sizeof(long)) operations.
* @param a The first bitmaptor
* @param b The second bitmaptor
* @return NULL on errors; A newly created bitmaptor on success.
*/
extern bitmap *bitmap_union(const bitmap *a, const bitmap *b);
/**
* Calculate union of two bitmaps and store result in one of them
* @param res The first bitmap
* @param addme The bitmap to unite to the first bitmap
* @return NULL on errors, res on success
*/
extern bitmap *bitmap_unite(bitmap *res, const bitmap *addme);
/**
* Calculate set difference between two bitmaps
* The set difference of A / B is defined as all members of A
* that isn't members of B. Note that parameter ordering matters
* for this function.
* This function completes in O(n/sizeof(long)) operations.
* @param a The first bitmaptor (numerator)
* @param b The first bitmaptor (denominator)
* @return NULL on errors; A newly created bitmaptor on success.
*/
extern bitmap *bitmap_diff(const bitmap *a, const bitmap *b);
/**
* Calculate symmetric difference between two bitmaps
* The symmetric difference between A and B is the set that
* contains all elements in either set but not in both.
* This function completes in O(n/sizeof(long)) operations.
* @param a The first bitmaptor
* @param b The second bitmaptor
*/
extern bitmap *bitmap_symdiff(const bitmap *a, const bitmap *b);
/**
* Compare two bitmaps for equality
* @param a The first bitmaptor
* @param b The other bitmaptor
* @return Similar to memcmp(), with tiebreaks determined by cardinality
*/
extern int bitmap_cmp(const bitmap *a, const bitmap *b);
/** @} */
#endif /* LIBNAGIOS_bitmap_h__ */
|
