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