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
177
|
#ifndef TARANTOOL_LIB_BITSET_BITSET_H_INCLUDED
#define TARANTOOL_LIB_BITSET_BITSET_H_INCLUDED
/*
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the following
* conditions are met:
*
* 1. Redistributions of source code must retain the above
* copyright notice, this list of conditions and the
* following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials
* provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY <COPYRIGHT HOLDER> ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
* <COPYRIGHT HOLDER> OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
* INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
* BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
* LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
* THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
/**
* @file
* @brief Module to work with arrays of bits (bitsets)
*
* Bitset is an array of bits where each bit can be set or unset
* independently. The bits of a @link bitset @endlink are indexed
* by \a size_t position number. Initially all bits are set to
* false. You can use any values in range [0,SIZE_MAX). The
* container grows automatically.
*/
#include "tarantool/config.h"
#include <stddef.h>
#include <stdint.h>
#include <stdbool.h>
#include <limits.h>
#if defined(DEBUG)
#include <stdio.h> /* for dumping debug output to FILE */
#endif /* defined(DEBUG) */
/** @cond false */
#define RB_COMPACT 1
#include <third_party/rb.h>
/** @endcond */
#include <lib/bit/bit.h>
#if defined(__cplusplus)
extern "C" {
#endif /* defined(__cplusplus) */
/** @cond false */
struct bitset_page {
size_t first_pos;
rb_node(struct bitset_page) node;
size_t cardinality;
uint8_t data[0];
};
typedef rb_tree(struct bitset_page) bitset_pages_t;
/** @endcond */
/**
* Bitset
*/
struct bitset {
/** @cond false */
bitset_pages_t pages;
size_t cardinality;
void *(*realloc)(void *ptr, size_t size);
/** @endcond */
};
/**
* @brief Construct \a bitset
* @param bitset bitset
* @param realloc memory allocator to use
*/
void
bitset_create(struct bitset *bitset, void *(*realloc)(void *ptr, size_t size));
/**
* @brief Destruct \a bitset
* @param bitset bitset
*/
void
bitset_destroy(struct bitset *bitset);
/**
* @brief Test bit \a pos in \a bitset
* @param bitset bitset
* @param pos bit number
* @retval true if \a pos is set in \a bitset
* @retval false if \a pos is not set in \a bitset
*/
bool
bitset_test(struct bitset *bitset, size_t pos);
/**
* @brief Set bit \a pos in \a bitset
* @param bitset bitset
* @param pos bit number
* @retval 1 on success if previous value of \a pos was true
* @retval 0 on success if previous value of \a pos was false
* @retval -1 on memory error
*/
int
bitset_set(struct bitset *bitset, size_t pos);
/**
* @brief Clear bit \a pos in \a bitset
* @param bitset bitset
* @param pos bit number
* @retval 1 on success if previous value of \a pos was true
* @retval 0 on success if previous value of \a pos was false
* @retval -1 on memory error
*/
int
bitset_clear(struct bitset *bitset, size_t pos);
/**
* @brief Return the number of bits set to \a true in \a bitset.
* @param bitset bitset
* @return returns the number of bits set to \a true in \a bitset.
*/
inline size_t
bitset_cardinality(const struct bitset *bitset) {
return bitset->cardinality;
}
/**
* @brief Bitset Information structure
* @see bitset_info
*/
struct bitset_info {
/** Number of allocated pages */
size_t pages;
/** Data (payload) size of one page (in bytes) */
size_t page_data_size;
/** Full size of one page (in bytes, including padding and tree data) */
size_t page_total_size;
/** A multiplier by which an address of page data is aligned **/
size_t page_data_alignment;
};
/**
* @brief Fill information about \a bitset
* @param bitset bitset
* @param stat structure to fill
*/
void
bitset_info(struct bitset *bitset, struct bitset_info *info);
#if defined(DEBUG)
void
bitset_dump(struct bitset *bitset, int verbose, FILE *stream);
#endif /* defined(DEBUG) */
#if defined(__cplusplus)
} /* extern "C" */
#endif /* defined(__cplusplus) */
#endif /* TARANTOOL_LIB_BITSET_BITSET_H_INCLUDED */
|
