1 /*
2 * Copyright © 2009 CNRS
3 * Copyright © 2009-2017 Inria. All rights reserved.
4 * Copyright © 2009-2012 Université Bordeaux
5 * Copyright © 2009-2011 Cisco Systems, Inc. All rights reserved.
6 * See COPYING in top-level directory.
7 */
8
9 /** \file
10 * \brief The bitmap API, for use in hwloc itself.
11 */
12
13 #ifndef HWLOC_BITMAP_H
14 #define HWLOC_BITMAP_H
15
16 #include <hwloc/autogen/config.h>
17 #include <assert.h>
18
19
20 #ifdef __cplusplus
21 extern "C" {
22 #endif
23
24
25 /** \defgroup hwlocality_bitmap The bitmap API
26 *
27 * The ::hwloc_bitmap_t type represents a set of objects, typically OS
28 * processors -- which may actually be hardware threads (represented
29 * by ::hwloc_cpuset_t, which is a typedef for ::hwloc_bitmap_t) -- or
30 * memory nodes (represented by ::hwloc_nodeset_t, which is also a
31 * typedef for ::hwloc_bitmap_t).
32 *
33 * <em>Both CPU and node sets are always indexed by OS physical number.</em>
34 *
35 * \note CPU sets and nodesets are described in \ref hwlocality_object_sets.
36 *
37 * A bitmap may be of infinite size (all bits are set after some point).
38 * A bitmap may even be full if all bits are set.
39 *
40 * \note Most functions below return an int that may be negative in case of
41 * error. The usual error case would be an internal failure to realloc/extend
42 * the storage of the bitmap (\p errno would be set to \c ENOMEM).
43 *
44 * \note Several examples of using the bitmap API are available under the
45 * doc/examples/ directory in the source tree.
46 * Regression tests such as tests/hwloc/hwloc_bitmap*.c also make intensive use
47 * of this API.
48 * @{
49 */
50
51
52 /** \brief
53 * Set of bits represented as an opaque pointer to an internal bitmap.
54 */
55 typedef struct hwloc_bitmap_s * hwloc_bitmap_t;
56 /** \brief a non-modifiable ::hwloc_bitmap_t */
57 typedef const struct hwloc_bitmap_s * hwloc_const_bitmap_t;
58
59
60 /*
61 * Bitmap allocation, freeing and copying.
62 */
63
64 /** \brief Allocate a new empty bitmap.
65 *
66 * \returns A valid bitmap or \c NULL.
67 *
68 * The bitmap should be freed by a corresponding call to
69 * hwloc_bitmap_free().
70 */
71 HWLOC_DECLSPEC hwloc_bitmap_t hwloc_bitmap_alloc(void) __hwloc_attribute_malloc;
72
73 /** \brief Allocate a new full bitmap. */
74 HWLOC_DECLSPEC hwloc_bitmap_t hwloc_bitmap_alloc_full(void) __hwloc_attribute_malloc;
75
76 /** \brief Free bitmap \p bitmap.
77 *
78 * If \p bitmap is \c NULL, no operation is performed.
79 */
80 HWLOC_DECLSPEC void hwloc_bitmap_free(hwloc_bitmap_t bitmap);
81
82 /** \brief Duplicate bitmap \p bitmap by allocating a new bitmap and copying \p bitmap contents.
83 *
84 * If \p bitmap is \c NULL, \c NULL is returned.
85 */
86 HWLOC_DECLSPEC hwloc_bitmap_t hwloc_bitmap_dup(hwloc_const_bitmap_t bitmap) __hwloc_attribute_malloc;
87
88 /** \brief Copy the contents of bitmap \p src into the already allocated bitmap \p dst */
89 HWLOC_DECLSPEC int hwloc_bitmap_copy(hwloc_bitmap_t dst, hwloc_const_bitmap_t src);
90
91
92 /*
93 * Bitmap/String Conversion
94 */
95
96 /** \brief Stringify a bitmap.
97 *
98 * Up to \p buflen characters may be written in buffer \p buf.
99 *
100 * If \p buflen is 0, \p buf may safely be \c NULL.
101 *
102 * \return the number of character that were actually written if not truncating,
103 * or that would have been written (not including the ending \\0).
104 */
105 HWLOC_DECLSPEC int hwloc_bitmap_snprintf(char * __hwloc_restrict buf, size_t buflen, hwloc_const_bitmap_t bitmap);
106
107 /** \brief Stringify a bitmap into a newly allocated string.
108 *
109 * \return -1 on error.
110 */
111 HWLOC_DECLSPEC int hwloc_bitmap_asprintf(char ** strp, hwloc_const_bitmap_t bitmap);
112
113 /** \brief Parse a bitmap string and stores it in bitmap \p bitmap.
114 */
115 HWLOC_DECLSPEC int hwloc_bitmap_sscanf(hwloc_bitmap_t bitmap, const char * __hwloc_restrict string);
116
117 /** \brief Stringify a bitmap in the list format.
118 *
119 * Lists are comma-separated indexes or ranges.
120 * Ranges are dash separated indexes.
121 * The last range may not have an ending indexes if the bitmap is infinitely set.
122 *
123 * Up to \p buflen characters may be written in buffer \p buf.
124 *
125 * If \p buflen is 0, \p buf may safely be \c NULL.
126 *
127 * \return the number of character that were actually written if not truncating,
128 * or that would have been written (not including the ending \\0).
129 */
130 HWLOC_DECLSPEC int hwloc_bitmap_list_snprintf(char * __hwloc_restrict buf, size_t buflen, hwloc_const_bitmap_t bitmap);
131
132 /** \brief Stringify a bitmap into a newly allocated list string.
133 *
134 * \return -1 on error.
135 */
136 HWLOC_DECLSPEC int hwloc_bitmap_list_asprintf(char ** strp, hwloc_const_bitmap_t bitmap);
137
138 /** \brief Parse a list string and stores it in bitmap \p bitmap.
139 */
140 HWLOC_DECLSPEC int hwloc_bitmap_list_sscanf(hwloc_bitmap_t bitmap, const char * __hwloc_restrict string);
141
142 /** \brief Stringify a bitmap in the taskset-specific format.
143 *
144 * The taskset command manipulates bitmap strings that contain a single
145 * (possible very long) hexadecimal number starting with 0x.
146 *
147 * Up to \p buflen characters may be written in buffer \p buf.
148 *
149 * If \p buflen is 0, \p buf may safely be \c NULL.
150 *
151 * \return the number of character that were actually written if not truncating,
152 * or that would have been written (not including the ending \\0).
153 */
154 HWLOC_DECLSPEC int hwloc_bitmap_taskset_snprintf(char * __hwloc_restrict buf, size_t buflen, hwloc_const_bitmap_t bitmap);
155
156 /** \brief Stringify a bitmap into a newly allocated taskset-specific string.
157 *
158 * \return -1 on error.
159 */
160 HWLOC_DECLSPEC int hwloc_bitmap_taskset_asprintf(char ** strp, hwloc_const_bitmap_t bitmap);
161
162 /** \brief Parse a taskset-specific bitmap string and stores it in bitmap \p bitmap.
163 */
164 HWLOC_DECLSPEC int hwloc_bitmap_taskset_sscanf(hwloc_bitmap_t bitmap, const char * __hwloc_restrict string);
165
166
167 /*
168 * Building bitmaps.
169 */
170
171 /** \brief Empty the bitmap \p bitmap */
172 HWLOC_DECLSPEC void hwloc_bitmap_zero(hwloc_bitmap_t bitmap);
173
174 /** \brief Fill bitmap \p bitmap with all possible indexes (even if those objects don't exist or are otherwise unavailable) */
175 HWLOC_DECLSPEC void hwloc_bitmap_fill(hwloc_bitmap_t bitmap);
176
177 /** \brief Empty the bitmap \p bitmap and add bit \p id */
178 HWLOC_DECLSPEC int hwloc_bitmap_only(hwloc_bitmap_t bitmap, unsigned id);
179
180 /** \brief Fill the bitmap \p and clear the index \p id */
181 HWLOC_DECLSPEC int hwloc_bitmap_allbut(hwloc_bitmap_t bitmap, unsigned id);
182
183 /** \brief Setup bitmap \p bitmap from unsigned long \p mask */
184 HWLOC_DECLSPEC int hwloc_bitmap_from_ulong(hwloc_bitmap_t bitmap, unsigned long mask);
185
186 /** \brief Setup bitmap \p bitmap from unsigned long \p mask used as \p i -th subset */
187 HWLOC_DECLSPEC int hwloc_bitmap_from_ith_ulong(hwloc_bitmap_t bitmap, unsigned i, unsigned long mask);
188
189
190 /*
191 * Modifying bitmaps.
192 */
193
194 /** \brief Add index \p id in bitmap \p bitmap */
195 HWLOC_DECLSPEC int hwloc_bitmap_set(hwloc_bitmap_t bitmap, unsigned id);
196
197 /** \brief Add indexes from \p begin to \p end in bitmap \p bitmap.
198 *
199 * If \p end is \c -1, the range is infinite.
200 */
201 HWLOC_DECLSPEC int hwloc_bitmap_set_range(hwloc_bitmap_t bitmap, unsigned begin, int end);
202
203 /** \brief Replace \p i -th subset of bitmap \p bitmap with unsigned long \p mask */
204 HWLOC_DECLSPEC int hwloc_bitmap_set_ith_ulong(hwloc_bitmap_t bitmap, unsigned i, unsigned long mask);
205
206 /** \brief Remove index \p id from bitmap \p bitmap */
207 HWLOC_DECLSPEC int hwloc_bitmap_clr(hwloc_bitmap_t bitmap, unsigned id);
208
209 /** \brief Remove indexes from \p begin to \p end in bitmap \p bitmap.
210 *
211 * If \p end is \c -1, the range is infinite.
212 */
213 HWLOC_DECLSPEC int hwloc_bitmap_clr_range(hwloc_bitmap_t bitmap, unsigned begin, int end);
214
215 /** \brief Keep a single index among those set in bitmap \p bitmap
216 *
217 * May be useful before binding so that the process does not
218 * have a chance of migrating between multiple logical CPUs
219 * in the original mask.
220 */
221 HWLOC_DECLSPEC int hwloc_bitmap_singlify(hwloc_bitmap_t bitmap);
222
223
224 /*
225 * Consulting bitmaps.
226 */
227
228 /** \brief Convert the beginning part of bitmap \p bitmap into unsigned long \p mask */
229 HWLOC_DECLSPEC unsigned long hwloc_bitmap_to_ulong(hwloc_const_bitmap_t bitmap) __hwloc_attribute_pure;
230
231 /** \brief Convert the \p i -th subset of bitmap \p bitmap into unsigned long mask */
232 HWLOC_DECLSPEC unsigned long hwloc_bitmap_to_ith_ulong(hwloc_const_bitmap_t bitmap, unsigned i) __hwloc_attribute_pure;
233
234 /** \brief Test whether index \p id is part of bitmap \p bitmap */
235 HWLOC_DECLSPEC int hwloc_bitmap_isset(hwloc_const_bitmap_t bitmap, unsigned id) __hwloc_attribute_pure;
236
237 /** \brief Test whether bitmap \p bitmap is empty */
238 HWLOC_DECLSPEC int hwloc_bitmap_iszero(hwloc_const_bitmap_t bitmap) __hwloc_attribute_pure;
239
240 /** \brief Test whether bitmap \p bitmap is completely full
241 *
242 * \note A full bitmap is always infinitely set.
243 */
244 HWLOC_DECLSPEC int hwloc_bitmap_isfull(hwloc_const_bitmap_t bitmap) __hwloc_attribute_pure;
245
246 /** \brief Compute the first index (least significant bit) in bitmap \p bitmap
247 *
248 * \return -1 if no index is set in \p bitmap.
249 */
250 HWLOC_DECLSPEC int hwloc_bitmap_first(hwloc_const_bitmap_t bitmap) __hwloc_attribute_pure;
251
252 /** \brief Compute the next index in bitmap \p bitmap which is after index \p prev
253 *
254 * If \p prev is -1, the first index is returned.
255 *
256 * \return -1 if no index with higher index is set in \p bitmap.
257 */
258 HWLOC_DECLSPEC int hwloc_bitmap_next(hwloc_const_bitmap_t bitmap, int prev) __hwloc_attribute_pure;
259
260 /** \brief Compute the last index (most significant bit) in bitmap \p bitmap
261 *
262 * \return -1 if no index is set in \p bitmap, or if \p bitmap is infinitely set.
263 */
264 HWLOC_DECLSPEC int hwloc_bitmap_last(hwloc_const_bitmap_t bitmap) __hwloc_attribute_pure;
265
266 /** \brief Compute the "weight" of bitmap \p bitmap (i.e., number of
267 * indexes that are in the bitmap).
268 *
269 * \return the number of indexes that are in the bitmap.
270 *
271 * \return -1 if \p bitmap is infinitely set.
272 */
273 HWLOC_DECLSPEC int hwloc_bitmap_weight(hwloc_const_bitmap_t bitmap) __hwloc_attribute_pure;
274
275 /** \brief Compute the first unset index (least significant bit) in bitmap \p bitmap
276 *
277 * \return -1 if no index is unset in \p bitmap.
278 */
279 HWLOC_DECLSPEC int hwloc_bitmap_first_unset(hwloc_const_bitmap_t bitmap) __hwloc_attribute_pure;
280
281 /** \brief Compute the next unset index in bitmap \p bitmap which is after index \p prev
282 *
283 * If \p prev is -1, the first unset index is returned.
284 *
285 * \return -1 if no index with higher index is unset in \p bitmap.
286 */
287 HWLOC_DECLSPEC int hwloc_bitmap_next_unset(hwloc_const_bitmap_t bitmap, int prev) __hwloc_attribute_pure;
288
289 /** \brief Compute the last unset index (most significant bit) in bitmap \p bitmap
290 *
291 * \return -1 if no index is unset in \p bitmap, or if \p bitmap is infinitely set.
292 */
293 HWLOC_DECLSPEC int hwloc_bitmap_last_unset(hwloc_const_bitmap_t bitmap) __hwloc_attribute_pure;
294
295 /** \brief Loop macro iterating on bitmap \p bitmap
296 *
297 * The loop must start with hwloc_bitmap_foreach_begin() and end
298 * with hwloc_bitmap_foreach_end() followed by a terminating ';'.
299 *
300 * \p index is the loop variable; it should be an unsigned int. The
301 * first iteration will set \p index to the lowest index in the bitmap.
302 * Successive iterations will iterate through, in order, all remaining
303 * indexes set in the bitmap. To be specific: each iteration will return a
304 * value for \p index such that hwloc_bitmap_isset(bitmap, index) is true.
305 *
306 * The assert prevents the loop from being infinite if the bitmap is infinitely set.
307 *
308 * \hideinitializer
309 */
310 #define hwloc_bitmap_foreach_begin(id, bitmap) \
311 do { \
312 assert(hwloc_bitmap_weight(bitmap) != -1); \
313 for (id = hwloc_bitmap_first(bitmap); \
314 (unsigned) id != (unsigned) -1; \
315 id = hwloc_bitmap_next(bitmap, id)) {
316
317 /** \brief End of loop macro iterating on a bitmap.
318 *
319 * Needs a terminating ';'.
320 *
321 * \sa hwloc_bitmap_foreach_begin()
322 * \hideinitializer
323 */
324 #define hwloc_bitmap_foreach_end() \
325 } \
326 } while (0)
327
328
329 /*
330 * Combining bitmaps.
331 */
332
333 /** \brief Or bitmaps \p bitmap1 and \p bitmap2 and store the result in bitmap \p res
334 *
335 * \p res can be the same as \p bitmap1 or \p bitmap2
336 */
337 HWLOC_DECLSPEC int hwloc_bitmap_or (hwloc_bitmap_t res, hwloc_const_bitmap_t bitmap1, hwloc_const_bitmap_t bitmap2);
338
339 /** \brief And bitmaps \p bitmap1 and \p bitmap2 and store the result in bitmap \p res
340 *
341 * \p res can be the same as \p bitmap1 or \p bitmap2
342 */
343 HWLOC_DECLSPEC int hwloc_bitmap_and (hwloc_bitmap_t res, hwloc_const_bitmap_t bitmap1, hwloc_const_bitmap_t bitmap2);
344
345 /** \brief And bitmap \p bitmap1 and the negation of \p bitmap2 and store the result in bitmap \p res
346 *
347 * \p res can be the same as \p bitmap1 or \p bitmap2
348 */
349 HWLOC_DECLSPEC int hwloc_bitmap_andnot (hwloc_bitmap_t res, hwloc_const_bitmap_t bitmap1, hwloc_const_bitmap_t bitmap2);
350
351 /** \brief Xor bitmaps \p bitmap1 and \p bitmap2 and store the result in bitmap \p res
352 *
353 * \p res can be the same as \p bitmap1 or \p bitmap2
354 */
355 HWLOC_DECLSPEC int hwloc_bitmap_xor (hwloc_bitmap_t res, hwloc_const_bitmap_t bitmap1, hwloc_const_bitmap_t bitmap2);
356
357 /** \brief Negate bitmap \p bitmap and store the result in bitmap \p res
358 *
359 * \p res can be the same as \p bitmap
360 */
361 HWLOC_DECLSPEC int hwloc_bitmap_not (hwloc_bitmap_t res, hwloc_const_bitmap_t bitmap);
362
363
364 /*
365 * Comparing bitmaps.
366 */
367
368 /** \brief Test whether bitmaps \p bitmap1 and \p bitmap2 intersects */
369 HWLOC_DECLSPEC int hwloc_bitmap_intersects (hwloc_const_bitmap_t bitmap1, hwloc_const_bitmap_t bitmap2) __hwloc_attribute_pure;
370
371 /** \brief Test whether bitmap \p sub_bitmap is part of bitmap \p super_bitmap.
372 *
373 * \note The empty bitmap is considered included in any other bitmap.
374 */
375 HWLOC_DECLSPEC int hwloc_bitmap_isincluded (hwloc_const_bitmap_t sub_bitmap, hwloc_const_bitmap_t super_bitmap) __hwloc_attribute_pure;
376
377 /** \brief Test whether bitmap \p bitmap1 is equal to bitmap \p bitmap2 */
378 HWLOC_DECLSPEC int hwloc_bitmap_isequal (hwloc_const_bitmap_t bitmap1, hwloc_const_bitmap_t bitmap2) __hwloc_attribute_pure;
379
380 /** \brief Compare bitmaps \p bitmap1 and \p bitmap2 using their lowest index.
381 *
382 * Smaller least significant bit is smaller.
383 * The empty bitmap is considered higher than anything.
384 */
385 HWLOC_DECLSPEC int hwloc_bitmap_compare_first(hwloc_const_bitmap_t bitmap1, hwloc_const_bitmap_t bitmap2) __hwloc_attribute_pure;
386
387 /** \brief Compare bitmaps \p bitmap1 and \p bitmap2 in lexicographic order.
388 *
389 * Lexicographic comparison of bitmaps, starting for their highest indexes.
390 * Compare last indexes first, then second, etc.
391 * The empty bitmap is considered lower than anything.
392 *
393 * \note This is different from the non-existing hwloc_bitmap_compare_last()
394 * which would only compare the highest index of each bitmap.
395 */
396 HWLOC_DECLSPEC int hwloc_bitmap_compare(hwloc_const_bitmap_t bitmap1, hwloc_const_bitmap_t bitmap2) __hwloc_attribute_pure;
397
398 /** @} */
399
400
401 #ifdef __cplusplus
402 } /* extern "C" */
403 #endif
404
405
406 #endif /* HWLOC_BITMAP_H */