1 /* -*- Mode: C; c-basic-offset:4 ; -*- */
2 /*
3 * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
4 * University Research and Technology
5 * Corporation. All rights reserved.
6 * Copyright (c) 2004-2014 The University of Tennessee and The University
7 * of Tennessee Research Foundation. All rights
8 * reserved.
9 * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
10 * University of Stuttgart. All rights reserved.
11 * Copyright (c) 2004-2005 The Regents of the University of California.
12 * All rights reserved.
13 * Copyright (c) 2007 Cisco Systems, Inc. All rights reserved.
14 * Copyright (c) 2010-2012 Oak Ridge National Labs. All rights reserved.
15 * Copyright (c) 2018 Intel, Inc. All rights reserved.
16 * $COPYRIGHT$
17 *
18 * Additional copyrights may follow
19 *
20 * $HEADER$
21 *
22 */
23
24 /** @file
25 *
26 * A bitmap implementation. The bits start off with 0, so this bitmap
27 * has bits numbered as bit 0, bit 1, bit 2 and so on. This bitmap
28 * has auto-expansion capabilities, that is once the size is set
29 * during init, it can be automatically expanded by setting the bit
30 * beyond the current size. But note, this is allowed just when the
31 * bit is set -- so the valid functions are set_bit and
32 * find_and_set_bit. Other functions like clear, if passed a bit
33 * outside the initialized range will result in an error.
34 *
35 * To allow these bitmaps to track fortran handles (which MPI defines
36 * to be Fortran INTEGER), we offer a pmix_bitmap_set_max_size, so that
37 * the upper layer can ask to never have more than
38 * OMPI_FORTRAN_HANDLE_MAX, which is min(INT_MAX, fortran INTEGER max).
39 */
40
41 #ifndef PMIX_BITMAP_H
42 #define PMIX_BITMAP_H
43
44 #include <src/include/pmix_config.h>
45
46 #include <string.h>
47
48 #include "src/class/pmix_object.h"
49
50 BEGIN_C_DECLS
51
52 struct pmix_bitmap_t {
53 pmix_object_t super; /**< Subclass of pmix_object_t */
54 uint64_t *bitmap; /**< The actual bitmap array of characters */
55 int array_size; /**< The actual array size that maintains the bitmap */
56 int max_size; /**< The maximum size that this bitmap may grow (optional) */
57 };
58
59 typedef struct pmix_bitmap_t pmix_bitmap_t;
60
61 PMIX_EXPORT PMIX_CLASS_DECLARATION(pmix_bitmap_t);
62
63 /**
64 * Set the maximum size of the bitmap.
65 * May be reset any time, but HAS TO BE SET BEFORE pmix_bitmap_init!
66 *
67 * @param bitmap The input bitmap (IN)
68 * @param max_size The maximum size of the bitmap in terms of bits (IN)
69 * @return PMIX error code or success
70 *
71 */
72 PMIX_EXPORT int pmix_bitmap_set_max_size (pmix_bitmap_t *bm, int max_size);
73
74
75 /**
76 * Initializes the bitmap and sets its size. This must be called
77 * before the bitmap can be actually used
78 *
79 * @param bitmap The input bitmap (IN)
80 * @param size The initial size of the bitmap in terms of bits (IN)
81 * @return PMIX error code or success
82 *
83 */
84 PMIX_EXPORT int pmix_bitmap_init (pmix_bitmap_t *bm, int size);
85
86
87 /**
88 * Set a bit of the bitmap. If the bit asked for is beyond the current
89 * size of the bitmap, then the bitmap is extended to accomodate the
90 * bit
91 *
92 * @param bitmap The input bitmap (IN)
93 * @param bit The bit which is to be set (IN)
94 * @return PMIX error code or success
95 *
96 */
97 PMIX_EXPORT int pmix_bitmap_set_bit(pmix_bitmap_t *bm, int bit);
98
99
100 /**
101 * Clear/unset a bit of the bitmap. If the bit is beyond the current
102 * size of the bitmap, an error is returned
103 *
104 * @param bitmap The input bitmap (IN)
105 * @param bit The bit which is to be cleared (IN)
106 * @return PMIX error code if the bit is out of range, else success
107 *
108 */
109 PMIX_EXPORT int pmix_bitmap_clear_bit(pmix_bitmap_t *bm, int bit);
110
111
112 /**
113 * Find out if a bit is set in the bitmap
114 *
115 * @param bitmap The input bitmap (IN)
116 * @param bit The bit which is to be checked (IN)
117 * @return true if the bit is set
118 * false if the bit is not set OR the index
119 * is outside the bounds of the provided
120 * bitmap
121 *
122 */
123 PMIX_EXPORT bool pmix_bitmap_is_set_bit(pmix_bitmap_t *bm, int bit);
124
125
126 /**
127 * Find the first clear bit in the bitmap and set it
128 *
129 * @param bitmap The input bitmap (IN)
130 * @param position Position of the first clear bit (OUT)
131
132 * @return err PMIX_SUCCESS on success
133 */
134 PMIX_EXPORT int pmix_bitmap_find_and_set_first_unset_bit(pmix_bitmap_t *bm,
135 int *position);
136
137
138 /**
139 * Clear all bits in the bitmap
140 *
141 * @param bitmap The input bitmap (IN)
142 * @return PMIX error code if bm is NULL
143 *
144 */
145 PMIX_EXPORT int pmix_bitmap_clear_all_bits(pmix_bitmap_t *bm);
146
147
148 /**
149 * Set all bits in the bitmap
150 * @param bitmap The input bitmap (IN)
151 * @return PMIX error code if bm is NULL
152 *
153 */
154 PMIX_EXPORT int pmix_bitmap_set_all_bits(pmix_bitmap_t *bm);
155
156
157 /**
158 * Gives the current size (number of bits) in the bitmap. This is the
159 * legal (accessible) number of bits
160 *
161 * @param bitmap The input bitmap (IN)
162 * @return PMIX error code if bm is NULL
163 *
164 */
165 static inline int pmix_bitmap_size(pmix_bitmap_t *bm)
166 {
167 return (NULL == bm) ? 0 : (bm->array_size * ((int) (sizeof(*bm->bitmap) * 8)));
168 }
169
170
171 /**
172 * Copy a bitmap
173 *
174 * @param dest Pointer to the destination bitmap
175 * @param src Pointer to the source bitmap
176 * @ return PMIX error code if something goes wrong
177 */
178 static inline void pmix_bitmap_copy(pmix_bitmap_t *dest, pmix_bitmap_t *src)
179 {
180 if( dest->array_size < src->array_size ) {
181 if( NULL != dest->bitmap) free(dest->bitmap);
182 dest->max_size = src->max_size;
183 dest->bitmap = (uint64_t*)malloc(src->array_size*sizeof(uint64_t));
184 }
185 memcpy(dest->bitmap, src->bitmap, src->array_size * sizeof(uint64_t));
186 dest->array_size = src->array_size;
187 }
188
189 /**
190 * Bitwise AND operator (inplace)
191 *
192 * @param dest Pointer to the bitmap that should be modified
193 * @param right Point to the other bitmap in the operation
194 * @return PMIX error code if the length of the two bitmaps is not equal or one is NULL.
195 */
196 PMIX_EXPORT int pmix_bitmap_bitwise_and_inplace(pmix_bitmap_t *dest, pmix_bitmap_t *right);
197
198 /**
199 * Bitwise OR operator (inplace)
200 *
201 * @param dest Pointer to the bitmap that should be modified
202 * @param right Point to the other bitmap in the operation
203 * @return PMIX error code if the length of the two bitmaps is not equal or one is NULL.
204 */
205 PMIX_EXPORT int pmix_bitmap_bitwise_or_inplace(pmix_bitmap_t *dest, pmix_bitmap_t *right);
206
207 /**
208 * Bitwise XOR operator (inplace)
209 *
210 * @param dest Pointer to the bitmap that should be modified
211 * @param right Point to the other bitmap in the operation
212 * @return PMIX error code if the length of the two bitmaps is not equal or one is NULL.
213 */
214 PMIX_EXPORT int pmix_bitmap_bitwise_xor_inplace(pmix_bitmap_t *dest, pmix_bitmap_t *right);
215
216 /**
217 * If the bitmaps are different
218 *
219 * @param left Pointer to a bitmap
220 * @param right Pointer to another bitmap
221 * @return true if different, false if the same
222 */
223 PMIX_EXPORT bool pmix_bitmap_are_different(pmix_bitmap_t *left, pmix_bitmap_t *right);
224
225 /**
226 * Get a string representation of the bitmap.
227 * Useful for debugging.
228 *
229 * @param bitmap Point to the bitmap to represent
230 * @return Pointer to the string (caller must free if not NULL)
231 */
232 PMIX_EXPORT char * pmix_bitmap_get_string(pmix_bitmap_t *bitmap);
233
234 /**
235 * Return the number of 'unset' bits, upto the specified length
236 *
237 * @param bitmap Pointer to the bitmap
238 * @param len Number of bits to check
239 * @return Integer
240 */
241 PMIX_EXPORT int pmix_bitmap_num_unset_bits(pmix_bitmap_t *bm, int len);
242
243 /**
244 * Return the number of 'set' bits, upto the specified length
245 *
246 * @param bitmap Pointer to the bitmap
247 * @param len Number of bits to check
248 * @return Integer
249 */
250 PMIX_EXPORT int pmix_bitmap_num_set_bits(pmix_bitmap_t *bm, int len);
251
252 /**
253 * Check a bitmap to see if any bit is set
254 */
255 PMIX_EXPORT bool pmix_bitmap_is_clear(pmix_bitmap_t *bm);
256
257 END_C_DECLS
258
259 #endif