1 /*
2 * virbitmap.c: Simple bitmap operations
3 *
4 * Copyright (C) 2010-2013 Red Hat, Inc.
5 * Copyright (C) 2010 Novell, Inc.
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library. If not, see
19 * <http://www.gnu.org/licenses/>.
20 */
21
22 #include <config.h>
23
24 #include <sys/types.h>
25
26 #include "virbitmap.h"
27 #include "viralloc.h"
28 #include "virbuffer.h"
29 #include "virstring.h"
30 #include "virerror.h"
31
32 #define VIR_FROM_THIS VIR_FROM_NONE
33
34 struct _virBitmap {
35 size_t nbits;
36 size_t map_len;
37 size_t map_alloc;
38
39 /* Note that code below depends on the fact that unused bits of the bitmap
40 * are not set. Any function decreasing the size of the map needs clear
41 * bits which don't belong to the bitmap any more. */
42 unsigned long *map;
43 };
44
45
46 #define VIR_BITMAP_BITS_PER_UNIT ((int) sizeof(unsigned long) * CHAR_BIT)
47 #define VIR_BITMAP_UNIT_OFFSET(b) ((b) / VIR_BITMAP_BITS_PER_UNIT)
48 #define VIR_BITMAP_BIT_OFFSET(b) ((b) % VIR_BITMAP_BITS_PER_UNIT)
49 #define VIR_BITMAP_BIT(b) (1UL << VIR_BITMAP_BIT_OFFSET(b))
50
51
52 /**
53 * virBitmapNew:
54 * @size: number of bits
55 *
56 * Allocate a bitmap capable of containing @size bits.
57 *
58 * Returns a pointer to the allocated bitmap.
59 */
60 virBitmap *
virBitmapNew(size_t size)61 virBitmapNew(size_t size)
62 {
63 virBitmap *bitmap;
64 size_t sz;
65
66 if (SIZE_MAX - VIR_BITMAP_BITS_PER_UNIT < size) {
67 /* VIR_DIV_UP would overflow, let's overallocate by 1 entry instead of
68 * the potential overflow */
69 sz = (size / VIR_BITMAP_BITS_PER_UNIT) + 1;
70 } else {
71 sz = VIR_DIV_UP(size, VIR_BITMAP_BITS_PER_UNIT);
72 }
73
74 bitmap = g_new0(virBitmap, 1);
75
76 if (size == 0)
77 return bitmap;
78
79 bitmap->map = g_new0(unsigned long, sz);
80 bitmap->nbits = size;
81 bitmap->map_len = sz;
82 bitmap->map_alloc = sz;
83 return bitmap;
84 }
85
86
87 /**
88 * virBitmapFree:
89 * @bitmap: previously allocated bitmap
90 *
91 * Free @bitmap previously allocated by virBitmapNew.
92 */
93 void
virBitmapFree(virBitmap * bitmap)94 virBitmapFree(virBitmap *bitmap)
95 {
96 if (bitmap) {
97 g_free(bitmap->map);
98 g_free(bitmap);
99 }
100 }
101
102
103 /**
104 * virBitmapSetBit:
105 * @bitmap: Pointer to bitmap
106 * @b: bit position to set
107 *
108 * Set bit position @b in @bitmap
109 *
110 * Returns 0 on if bit is successfully set, -1 on error.
111 */
112 int
virBitmapSetBit(virBitmap * bitmap,size_t b)113 virBitmapSetBit(virBitmap *bitmap,
114 size_t b)
115 {
116 if (bitmap->nbits <= b)
117 return -1;
118
119 bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] |= VIR_BITMAP_BIT(b);
120 return 0;
121 }
122
123
124 /**
125 * virBitmapExpand:
126 * @map: Pointer to bitmap
127 * @b: bit position to include in bitmap
128 *
129 * Resizes the bitmap so that bit @b will fit into it. This shall be called only
130 * if @b would not fit into the map.
131 *
132 * Returns 0 on success, -1 on error.
133 */
134 static int
virBitmapExpand(virBitmap * map,size_t b)135 virBitmapExpand(virBitmap *map,
136 size_t b)
137 {
138 size_t new_len = VIR_DIV_UP(b + 1, VIR_BITMAP_BITS_PER_UNIT);
139
140 /* resize the memory if necessary */
141 if (map->map_len < new_len) {
142 VIR_RESIZE_N(map->map, map->map_alloc, map->map_len,
143 new_len - map->map_len);
144 }
145
146 map->nbits = b + 1;
147 map->map_len = new_len;
148
149 return 0;
150 }
151
152
153 /**
154 * virBitmapSetBitExpand:
155 * @bitmap: Pointer to bitmap
156 * @b: bit position to set
157 *
158 * Set bit position @b in @bitmap. Expands the bitmap as necessary so that @b is
159 * included in the map.
160 *
161 * Returns 0 on if bit is successfully set, -1 on error.
162 */
163 int
virBitmapSetBitExpand(virBitmap * bitmap,size_t b)164 virBitmapSetBitExpand(virBitmap *bitmap,
165 size_t b)
166 {
167 if (bitmap->nbits <= b && virBitmapExpand(bitmap, b) < 0)
168 return -1;
169
170 bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] |= VIR_BITMAP_BIT(b);
171 return 0;
172 }
173
174
175 /**
176 * virBitmapClearBit:
177 * @bitmap: Pointer to bitmap
178 * @b: bit position to clear
179 *
180 * Clear bit position @b in @bitmap
181 *
182 * Returns 0 on if bit is successfully clear, -1 on error.
183 */
184 int
virBitmapClearBit(virBitmap * bitmap,size_t b)185 virBitmapClearBit(virBitmap *bitmap,
186 size_t b)
187 {
188 if (bitmap->nbits <= b)
189 return -1;
190
191 bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] &= ~VIR_BITMAP_BIT(b);
192 return 0;
193 }
194
195
196 /**
197 * virBitmapClearBitExpand:
198 * @bitmap: Pointer to bitmap
199 * @b: bit position to set
200 *
201 * Clear bit position @b in @bitmap. Expands the bitmap as necessary so that
202 * @b is included in the map.
203 *
204 * Returns 0 on if bit is successfully cleared, -1 on error.
205 */
206 int
virBitmapClearBitExpand(virBitmap * bitmap,size_t b)207 virBitmapClearBitExpand(virBitmap *bitmap,
208 size_t b)
209 {
210 if (bitmap->nbits <= b) {
211 if (virBitmapExpand(bitmap, b) < 0)
212 return -1;
213 } else {
214 bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] &= ~VIR_BITMAP_BIT(b);
215 }
216
217 return 0;
218 }
219
220
221 /* Helper function. caller must ensure b < bitmap->nbits */
222 static bool
virBitmapIsSet(virBitmap * bitmap,size_t b)223 virBitmapIsSet(virBitmap *bitmap, size_t b)
224 {
225 return !!(bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] & VIR_BITMAP_BIT(b));
226 }
227
228
229 /**
230 * virBitmapIsBitSet:
231 * @bitmap: Pointer to bitmap
232 * @b: bit position to get
233 *
234 * Get setting of bit position @b in @bitmap.
235 *
236 * If @b is in the range of @bitmap, returns the value of the bit.
237 * Otherwise false is returned.
238 */
239 bool
virBitmapIsBitSet(virBitmap * bitmap,size_t b)240 virBitmapIsBitSet(virBitmap *bitmap,
241 size_t b)
242 {
243 if (bitmap->nbits <= b)
244 return false;
245
246 return virBitmapIsSet(bitmap, b);
247 }
248
249
250 /**
251 * virBitmapGetBit:
252 * @bitmap: Pointer to bitmap
253 * @b: bit position to get
254 * @result: bool pointer to receive bit setting
255 *
256 * Get setting of bit position @b in @bitmap and store in @result
257 *
258 * On success, @result will contain the setting of @b and 0 is
259 * returned. On failure, -1 is returned and @result is unchanged.
260 */
261 int
virBitmapGetBit(virBitmap * bitmap,size_t b,bool * result)262 virBitmapGetBit(virBitmap *bitmap,
263 size_t b,
264 bool *result)
265 {
266 if (bitmap->nbits <= b)
267 return -1;
268
269 *result = virBitmapIsSet(bitmap, b);
270 return 0;
271 }
272
273
274 /**
275 * virBitmapToString:
276 * @bitmap: Pointer to bitmap
277 *
278 * Convert @bitmap to a number where the bit with highest position/index in
279 * @bitmap represents the most significant bit and return the number in form
280 * of a hexadecimal string.
281 *
282 * Returns pointer to the string or NULL on error.
283 */
284 char *
virBitmapToString(virBitmap * bitmap)285 virBitmapToString(virBitmap *bitmap)
286 {
287 g_auto(virBuffer) buf = VIR_BUFFER_INITIALIZER;
288 size_t sz;
289 size_t len;
290 size_t diff;
291 char *ret = NULL;
292
293 sz = bitmap->map_len;
294
295 /* initialize buffer to return empty string for 0 length bitmap */
296 virBufferAdd(&buf, "", -1);
297
298 while (sz--) {
299 virBufferAsprintf(&buf, "%0*lx",
300 VIR_BITMAP_BITS_PER_UNIT / 4,
301 bitmap->map[sz]);
302 }
303
304 ret = virBufferContentAndReset(&buf);
305 if (!ret)
306 return NULL;
307
308 if (bitmap->nbits != bitmap->map_len * VIR_BITMAP_BITS_PER_UNIT) {
309 char *tmp = ret;
310
311 len = strlen(tmp);
312 sz = VIR_DIV_UP(bitmap->nbits, 4);
313 diff = len - sz;
314
315 if (diff)
316 memmove(tmp, tmp + diff, sz + 1);
317 }
318
319 return ret;
320 }
321
322
323 /**
324 * virBitmapFormat:
325 * @bitmap: the bitmap
326 *
327 * This function is the counterpart of virBitmapParse. This function creates
328 * a human-readable string representing the bits in bitmap.
329 *
330 * See virBitmapParse for the format of @str.
331 *
332 * If bitmap is NULL or it has no bits set, an empty string is returned.
333 *
334 * Returns the string on success or NULL otherwise. Caller should call
335 * VIR_FREE to free the string.
336 */
337 char *
virBitmapFormat(virBitmap * bitmap)338 virBitmapFormat(virBitmap *bitmap)
339 {
340 g_auto(virBuffer) buf = VIR_BUFFER_INITIALIZER;
341 bool first = true;
342 int start, cur, prev;
343
344 if (!bitmap || (cur = virBitmapNextSetBit(bitmap, -1)) < 0) {
345 char *ret;
346 ret = g_strdup("");
347 return ret;
348 }
349
350 start = prev = cur;
351 while (prev >= 0) {
352 cur = virBitmapNextSetBit(bitmap, prev);
353
354 if (cur == prev + 1) {
355 prev = cur;
356 continue;
357 }
358
359 /* cur < 0 or cur > prev + 1 */
360
361 if (!first)
362 virBufferAddLit(&buf, ",");
363 else
364 first = false;
365
366 if (prev == start)
367 virBufferAsprintf(&buf, "%d", start);
368 else
369 virBufferAsprintf(&buf, "%d-%d", start, prev);
370
371 start = prev = cur;
372 }
373
374 return virBufferContentAndReset(&buf);
375 }
376
377
378 /**
379 * virBitmapParseSeparator:
380 * @str: points to a string representing a human-readable bitmap
381 * @terminator: character separating the bitmap to parse
382 * @bitmap: a bitmap created from @str
383 * @bitmapSize: the upper limit of num of bits in created bitmap
384 *
385 * This function is the counterpart of virBitmapFormat. This function creates
386 * a bitmap, in which bits are set according to the content of @str.
387 *
388 * @str is a comma separated string of fields N, which means a number of bit
389 * to set, and ^N, which means to unset the bit, and N-M for ranges of bits
390 * to set.
391 *
392 * To allow parsing of bitmaps within larger strings it is possible to set
393 * a termination character in the argument @terminator. When the character
394 * in @terminator is encountered in @str, the parsing of the bitmap stops.
395 * Pass 0 as @terminator if it is not needed. Whitespace characters may not
396 * be used as terminators.
397 *
398 * Returns 0 on success, or -1 in case of error.
399 */
400 int
virBitmapParseSeparator(const char * str,char terminator,virBitmap ** bitmap,size_t bitmapSize)401 virBitmapParseSeparator(const char *str,
402 char terminator,
403 virBitmap **bitmap,
404 size_t bitmapSize)
405 {
406 bool neg = false;
407 const char *cur = str;
408 char *tmp;
409 size_t i;
410 int start, last;
411
412 *bitmap = virBitmapNew(bitmapSize);
413
414 if (!str)
415 goto error;
416
417 virSkipSpaces(&cur);
418
419 if (*cur == '\0')
420 goto error;
421
422 while (*cur != 0 && *cur != terminator) {
423 /*
424 * 3 constructs are allowed:
425 * - N : a single CPU number
426 * - N-M : a range of CPU numbers with N < M
427 * - ^N : remove a single CPU number from the current set
428 */
429 if (*cur == '^') {
430 cur++;
431 neg = true;
432 }
433
434 if (!g_ascii_isdigit(*cur))
435 goto error;
436
437 if (virStrToLong_i(cur, &tmp, 10, &start) < 0)
438 goto error;
439 if (start < 0)
440 goto error;
441
442 cur = tmp;
443
444 virSkipSpaces(&cur);
445
446 if (*cur == ',' || *cur == 0 || *cur == terminator) {
447 if (neg) {
448 if (virBitmapClearBit(*bitmap, start) < 0)
449 goto error;
450 } else {
451 if (virBitmapSetBit(*bitmap, start) < 0)
452 goto error;
453 }
454 } else if (*cur == '-') {
455 if (neg)
456 goto error;
457
458 cur++;
459 virSkipSpaces(&cur);
460
461 if (virStrToLong_i(cur, &tmp, 10, &last) < 0)
462 goto error;
463 if (last < start)
464 goto error;
465
466 cur = tmp;
467
468 for (i = start; i <= last; i++) {
469 if (virBitmapSetBit(*bitmap, i) < 0)
470 goto error;
471 }
472
473 virSkipSpaces(&cur);
474 }
475
476 if (*cur == ',') {
477 cur++;
478 virSkipSpaces(&cur);
479 neg = false;
480 } else if (*cur == 0 || *cur == terminator) {
481 break;
482 } else {
483 goto error;
484 }
485 }
486
487 return 0;
488
489 error:
490 virReportError(VIR_ERR_INVALID_ARG,
491 _("Failed to parse bitmap '%s'"), str);
492 virBitmapFree(*bitmap);
493 *bitmap = NULL;
494 return -1;
495 }
496
497
498 /**
499 * virBitmapParse:
500 * @str: points to a string representing a human-readable bitmap
501 * @bitmap: a bitmap created from @str
502 * @bitmapSize: the upper limit of num of bits in created bitmap
503 *
504 * This function is the counterpart of virBitmapFormat. This function creates
505 * a bitmap, in which bits are set according to the content of @str.
506 *
507 * @str is a comma separated string of fields N, which means a number of bit
508 * to set, and ^N, which means to unset the bit, and N-M for ranges of bits
509 * to set.
510 *
511 * Returns 0 on success, or -1 in case of error.
512 */
513 int
virBitmapParse(const char * str,virBitmap ** bitmap,size_t bitmapSize)514 virBitmapParse(const char *str,
515 virBitmap **bitmap,
516 size_t bitmapSize)
517 {
518 return virBitmapParseSeparator(str, '\0', bitmap, bitmapSize);
519 }
520
521
522 /**
523 * virBitmapParseUnlimited:
524 * @str: points to a string representing a human-readable bitmap
525 *
526 * This function is the counterpart of virBitmapFormat. This function creates
527 * a bitmap, in which bits are set according to the content of @str.
528 *
529 * The bitmap is expanded to accommodate all the bits.
530 *
531 * @str is a comma separated string of fields N, which means a number of bit
532 * to set, and ^N, which means to unset the bit, and N-M for ranges of bits
533 * to set.
534 *
535 * Returns @bitmap on success, or NULL in case of error
536 */
537 virBitmap *
virBitmapParseUnlimited(const char * str)538 virBitmapParseUnlimited(const char *str)
539 {
540 virBitmap *bitmap = virBitmapNew(0);
541 bool neg = false;
542 const char *cur = str;
543 char *tmp;
544 size_t i;
545 int start, last;
546
547 if (!str)
548 goto error;
549
550 virSkipSpaces(&cur);
551
552 if (*cur == '\0')
553 goto error;
554
555 while (*cur != 0) {
556 /*
557 * 3 constructs are allowed:
558 * - N : a single CPU number
559 * - N-M : a range of CPU numbers with N < M
560 * - ^N : remove a single CPU number from the current set
561 */
562 if (*cur == '^') {
563 cur++;
564 neg = true;
565 }
566
567 if (!g_ascii_isdigit(*cur))
568 goto error;
569
570 if (virStrToLong_i(cur, &tmp, 10, &start) < 0)
571 goto error;
572 if (start < 0)
573 goto error;
574
575 cur = tmp;
576
577 virSkipSpaces(&cur);
578
579 if (*cur == ',' || *cur == 0) {
580 if (neg) {
581 if (virBitmapClearBitExpand(bitmap, start) < 0)
582 goto error;
583 } else {
584 if (virBitmapSetBitExpand(bitmap, start) < 0)
585 goto error;
586 }
587 } else if (*cur == '-') {
588 if (neg)
589 goto error;
590
591 cur++;
592 virSkipSpaces(&cur);
593
594 if (virStrToLong_i(cur, &tmp, 10, &last) < 0)
595 goto error;
596 if (last < start)
597 goto error;
598
599 cur = tmp;
600
601 for (i = start; i <= last; i++) {
602 if (virBitmapSetBitExpand(bitmap, i) < 0)
603 goto error;
604 }
605
606 virSkipSpaces(&cur);
607 }
608
609 if (*cur == ',') {
610 cur++;
611 virSkipSpaces(&cur);
612 neg = false;
613 } else if (*cur == 0) {
614 break;
615 } else {
616 goto error;
617 }
618 }
619
620 return bitmap;
621
622 error:
623 virReportError(VIR_ERR_INVALID_ARG,
624 _("Failed to parse bitmap '%s'"), NULLSTR(str));
625 virBitmapFree(bitmap);
626 return NULL;
627 }
628
629
630 /**
631 * virBitmapNewCopy:
632 * @src: the source bitmap.
633 *
634 * Returns a copy of bitmap @src.
635 */
636 virBitmap *
virBitmapNewCopy(virBitmap * src)637 virBitmapNewCopy(virBitmap *src)
638 {
639 virBitmap *dst = virBitmapNew(src->nbits);
640
641 memcpy(dst->map, src->map, src->map_len * sizeof(src->map[0]));
642
643 return dst;
644 }
645
646
647 /**
648 * virBitmapNewData:
649 * @data: the data
650 * @len: length of @data in bytes
651 *
652 * Allocate a bitmap from a chunk of data containing bits
653 * information
654 *
655 * Returns a pointer to the allocated bitmap or NULL if
656 * memory cannot be allocated.
657 */
658 virBitmap *
virBitmapNewData(const void * data,int len)659 virBitmapNewData(const void *data,
660 int len)
661 {
662 virBitmap *bitmap;
663 size_t i, j;
664 unsigned long *p;
665 const unsigned char *bytes = data;
666
667 bitmap = virBitmapNew(len * CHAR_BIT);
668
669 /* le64toh is not available, so we do the conversion by hand */
670 p = bitmap->map;
671 for (i = j = 0; i < len; i++, j++) {
672 if (j == sizeof(*p)) {
673 j = 0;
674 p++;
675 }
676 *p |= (unsigned long) bytes[i] << (j * CHAR_BIT);
677 }
678
679 return bitmap;
680 }
681
682
683 /**
684 * virBitmapToData:
685 * @data: the data
686 * @len: len of @data in byte
687 *
688 * Convert a bitmap to a chunk of data containing bits information.
689 * Data consists of sequential bytes, with lower bytes containing
690 * lower bits. This function allocates @data.
691 *
692 * Returns 0 on success, -1 otherwise.
693 */
694 int
virBitmapToData(virBitmap * bitmap,unsigned char ** data,int * dataLen)695 virBitmapToData(virBitmap *bitmap,
696 unsigned char **data,
697 int *dataLen)
698 {
699 ssize_t len;
700
701 if ((len = virBitmapLastSetBit(bitmap)) < 0)
702 len = 1;
703 else
704 len = (len + CHAR_BIT) / CHAR_BIT;
705
706 *data = g_new0(unsigned char, len);
707 *dataLen = len;
708
709 virBitmapToDataBuf(bitmap, *data, *dataLen);
710
711 return 0;
712 }
713
714
715 /**
716 * virBitmapToDataBuf:
717 * @bytes: pointer to memory to fill
718 * @len: len of @bytes in byte
719 *
720 * Convert a bitmap to a chunk of data containing bits information.
721 * Data consists of sequential bytes, with lower bytes containing
722 * lower bits.
723 */
724 void
virBitmapToDataBuf(virBitmap * bitmap,unsigned char * bytes,size_t len)725 virBitmapToDataBuf(virBitmap *bitmap,
726 unsigned char *bytes,
727 size_t len)
728 {
729 size_t nbytes = bitmap->map_len * (VIR_BITMAP_BITS_PER_UNIT / CHAR_BIT);
730 unsigned long *l;
731 size_t i, j;
732
733 memset(bytes, 0, len);
734
735 /* If bitmap and buffer differ in size, only fill to the smaller length */
736 len = MIN(len, nbytes);
737
738 /* htole64 is not available, so we do the conversion by hand */
739 l = bitmap->map;
740 for (i = j = 0; i < len; i++, j++) {
741 if (j == sizeof(*l)) {
742 j = 0;
743 l++;
744 }
745 bytes[i] = *l >> (j * CHAR_BIT);
746 }
747 }
748
749
750 /**
751 * virBitmapEqual:
752 * @b1: bitmap 1
753 * @b2: bitmap 2
754 *
755 * Compares two bitmaps, whose lengths can be different from each other.
756 *
757 * Returns true if two bitmaps have exactly the same set of bits set,
758 * otherwise false.
759 */
760 bool
virBitmapEqual(virBitmap * b1,virBitmap * b2)761 virBitmapEqual(virBitmap *b1,
762 virBitmap *b2)
763 {
764 virBitmap *tmp;
765 size_t i;
766
767 if (!b1 && !b2)
768 return true;
769
770 if (!b1 || !b2)
771 return false;
772
773 if (b1->nbits > b2->nbits) {
774 tmp = b1;
775 b1 = b2;
776 b2 = tmp;
777 }
778
779 /* Now b1 is the smaller one, if not equal */
780
781 for (i = 0; i < b1->map_len; i++) {
782 if (b1->map[i] != b2->map[i])
783 return false;
784 }
785
786 for (; i < b2->map_len; i++) {
787 if (b2->map[i])
788 return false;
789 }
790
791 return true;
792 }
793
794
795 /**
796 * virBitmapSize:
797 * @bitmap: virBitmap to inspect
798 *
799 * Returns number of bits @bitmap can store.
800 */
801 size_t
virBitmapSize(virBitmap * bitmap)802 virBitmapSize(virBitmap *bitmap)
803 {
804 return bitmap->nbits;
805 }
806
807
808 /**
809 * virBitmapSetAll:
810 * @bitmap: the bitmap
811 *
812 * set all bits in @bitmap.
813 */
virBitmapSetAll(virBitmap * bitmap)814 void virBitmapSetAll(virBitmap *bitmap)
815 {
816 int tail = bitmap->nbits % VIR_BITMAP_BITS_PER_UNIT;
817
818 memset(bitmap->map, 0xff,
819 bitmap->map_len * (VIR_BITMAP_BITS_PER_UNIT / CHAR_BIT));
820
821 /* Ensure tail bits are clear. */
822 if (tail)
823 bitmap->map[bitmap->map_len - 1] &=
824 -1UL >> (VIR_BITMAP_BITS_PER_UNIT - tail);
825 }
826
827
828 /**
829 * virBitmapClearAll:
830 * @bitmap: the bitmap
831 *
832 * clear all bits in @bitmap.
833 */
834 void
virBitmapClearAll(virBitmap * bitmap)835 virBitmapClearAll(virBitmap *bitmap)
836 {
837 memset(bitmap->map, 0,
838 bitmap->map_len * (VIR_BITMAP_BITS_PER_UNIT / CHAR_BIT));
839 }
840
841
842 /**
843 * virBitmapIsAllSet:
844 * @bitmap: the bitmap to check
845 *
846 * check if all bits in @bitmap are set.
847 */
848 bool
virBitmapIsAllSet(virBitmap * bitmap)849 virBitmapIsAllSet(virBitmap *bitmap)
850 {
851 size_t i;
852 int unusedBits;
853 size_t sz;
854
855 unusedBits = bitmap->map_len * VIR_BITMAP_BITS_PER_UNIT - bitmap->nbits;
856
857 sz = bitmap->map_len;
858 if (unusedBits > 0)
859 sz--;
860
861 for (i = 0; i < sz; i++)
862 if (bitmap->map[i] != -1)
863 return false;
864
865 if (unusedBits > 0) {
866 if ((bitmap->map[sz] & ((1UL << (VIR_BITMAP_BITS_PER_UNIT - unusedBits)) - 1))
867 != ((1UL << (VIR_BITMAP_BITS_PER_UNIT - unusedBits)) - 1))
868 return false;
869 }
870
871 return true;
872 }
873
874
875 /**
876 * virBitmapIsAllClear:
877 * @bitmap: the bitmap to check
878 *
879 * check if all bits in @bitmap are clear
880 */
881 bool
virBitmapIsAllClear(virBitmap * bitmap)882 virBitmapIsAllClear(virBitmap *bitmap)
883 {
884 size_t i;
885
886 for (i = 0; i < bitmap->map_len; i++)
887 if (bitmap->map[i] != 0)
888 return false;
889
890 return true;
891 }
892
893
894 /**
895 * virBitmapNextSetBit:
896 * @bitmap: the bitmap
897 * @pos: the position after which to search for a set bit
898 *
899 * Search for the first set bit after position @pos in bitmap @bitmap.
900 * @pos can be -1 to search for the first set bit. Position starts
901 * at 0.
902 *
903 * Returns the position of the found bit, or -1 if no bit found.
904 */
905 ssize_t
virBitmapNextSetBit(virBitmap * bitmap,ssize_t pos)906 virBitmapNextSetBit(virBitmap *bitmap,
907 ssize_t pos)
908 {
909 size_t nl;
910 size_t nb;
911 unsigned long bits;
912
913 if (pos < 0)
914 pos = -1;
915
916 pos++;
917
918 if (pos >= bitmap->nbits)
919 return -1;
920
921 nl = pos / VIR_BITMAP_BITS_PER_UNIT;
922 nb = pos % VIR_BITMAP_BITS_PER_UNIT;
923
924 bits = bitmap->map[nl] & ~((1UL << nb) - 1);
925
926 while (bits == 0 && ++nl < bitmap->map_len)
927 bits = bitmap->map[nl];
928
929 if (bits == 0)
930 return -1;
931
932 return __builtin_ffsl(bits) - 1 + nl * VIR_BITMAP_BITS_PER_UNIT;
933 }
934
935
936 /**
937 * virBitmapLastSetBit:
938 * @bitmap: the bitmap
939 *
940 * Search for the last set bit in bitmap @bitmap.
941 *
942 * Returns the position of the found bit, or -1 if no bit is set.
943 */
944 ssize_t
virBitmapLastSetBit(virBitmap * bitmap)945 virBitmapLastSetBit(virBitmap *bitmap)
946 {
947 ssize_t i;
948 int unusedBits;
949 ssize_t sz;
950 unsigned long bits;
951
952 /* If bitmap is empty then there is no set bit */
953 if (bitmap->map_len == 0)
954 return -1;
955
956 unusedBits = bitmap->map_len * VIR_BITMAP_BITS_PER_UNIT - bitmap->nbits;
957
958 sz = bitmap->map_len - 1;
959 if (unusedBits > 0) {
960 bits = bitmap->map[sz] & (VIR_BITMAP_BIT(VIR_BITMAP_BITS_PER_UNIT - unusedBits) - 1);
961 if (bits != 0)
962 goto found;
963
964 sz--;
965 }
966
967 for (; sz >= 0; sz--) {
968 bits = bitmap->map[sz];
969 if (bits != 0)
970 goto found;
971 }
972
973 /* Only reached if no set bit was found */
974 return -1;
975
976 found:
977 for (i = VIR_BITMAP_BITS_PER_UNIT - 1; i >= 0; i--) {
978 if (bits & 1UL << i)
979 return i + sz * VIR_BITMAP_BITS_PER_UNIT;
980 }
981
982 return -1;
983 }
984
985
986 /**
987 * virBitmapNextClearBit:
988 * @bitmap: the bitmap
989 * @pos: the position after which to search for a clear bit
990 *
991 * Search for the first clear bit after position @pos in bitmap @bitmap.
992 * @pos can be -1 to search for the first set bit. Position starts
993 * at 0.
994 *
995 * Returns the position of the found bit, or -1 if no bit found.
996 */
997 ssize_t
virBitmapNextClearBit(virBitmap * bitmap,ssize_t pos)998 virBitmapNextClearBit(virBitmap *bitmap,
999 ssize_t pos)
1000 {
1001 size_t nl;
1002 size_t nb;
1003 unsigned long bits;
1004
1005 if (pos < 0)
1006 pos = -1;
1007
1008 pos++;
1009
1010 if (pos >= bitmap->nbits)
1011 return -1;
1012
1013 nl = pos / VIR_BITMAP_BITS_PER_UNIT;
1014 nb = pos % VIR_BITMAP_BITS_PER_UNIT;
1015
1016 bits = ~bitmap->map[nl] & ~((1UL << nb) - 1);
1017
1018 while (bits == 0 && ++nl < bitmap->map_len)
1019 bits = ~bitmap->map[nl];
1020
1021 if (nl == bitmap->map_len - 1) {
1022 /* Ensure tail bits are ignored. */
1023 int tail = bitmap->nbits % VIR_BITMAP_BITS_PER_UNIT;
1024
1025 if (tail)
1026 bits &= -1UL >> (VIR_BITMAP_BITS_PER_UNIT - tail);
1027 }
1028 if (bits == 0)
1029 return -1;
1030
1031 return __builtin_ffsl(bits) - 1 + nl * VIR_BITMAP_BITS_PER_UNIT;
1032 }
1033
1034
1035 /**
1036 * virBitmapCountBits:
1037 * @bitmap: bitmap to inspect
1038 *
1039 * Return the number of bits currently set in @bitmap.
1040 */
1041 size_t
virBitmapCountBits(virBitmap * bitmap)1042 virBitmapCountBits(virBitmap *bitmap)
1043 {
1044 size_t i;
1045 size_t ret = 0;
1046
1047 for (i = 0; i < bitmap->map_len; i++)
1048 ret += __builtin_popcountl(bitmap->map[i]);
1049
1050 return ret;
1051 }
1052
1053
1054 /**
1055 * virBitmapNewString:
1056 * @string: the string to be converted to a bitmap
1057 *
1058 * Allocate a bitmap and populate it from @string representing a number in
1059 * hexadecimal format. Note that the most significant bit of the number
1060 * represented by @string will correspond to the highest index/position in the
1061 * bitmap. The size of the returned bitmap corresponds to 4 * the length of
1062 * @string.
1063 *
1064 * Returns a pointer to the allocated bitmap or NULL and reports an error if
1065 * @string can't be converted.
1066 */
1067 virBitmap *
virBitmapNewString(const char * string)1068 virBitmapNewString(const char *string)
1069 {
1070 virBitmap *bitmap;
1071 size_t i = 0;
1072 size_t len = strlen(string);
1073
1074 if (strspn(string, "0123456789abcdefABCDEF") != len) {
1075 virReportError(VIR_ERR_INVALID_ARG,
1076 _("Invalid hexadecimal string '%s'"), string);
1077 return NULL;
1078 }
1079
1080 bitmap = virBitmapNew(len * 4);
1081
1082 for (i = 0; i < len; i++) {
1083 unsigned long nibble = g_ascii_xdigit_value(string[len - i - 1]);
1084 nibble <<= VIR_BITMAP_BIT_OFFSET(i * 4);
1085 bitmap->map[VIR_BITMAP_UNIT_OFFSET(i * 4)] |= nibble;
1086 }
1087
1088 return bitmap;
1089 }
1090
1091
1092 /**
1093 * virBitmapDataFormat:
1094 * @data: the data
1095 * @len: length of @data in bytes
1096 *
1097 * Convert a chunk of data containing bits information to a human
1098 * readable string, e.g.: 0-1,4
1099 *
1100 * Returns: a string representation of the data, or NULL on error
1101 */
1102 char *
virBitmapDataFormat(const void * data,int len)1103 virBitmapDataFormat(const void *data,
1104 int len)
1105 {
1106 g_autoptr(virBitmap) map = NULL;
1107
1108 if (!(map = virBitmapNewData(data, len)))
1109 return NULL;
1110
1111 return virBitmapFormat(map);
1112 }
1113
1114
1115 /**
1116 * virBitmapOverlaps:
1117 * @b1: virBitmap to inspect
1118 * @b2: virBitmap to inspect
1119 *
1120 * Returns true if at least one bit with the same index is set both in @b1 and
1121 * @b2.
1122 */
1123 bool
virBitmapOverlaps(virBitmap * b1,virBitmap * b2)1124 virBitmapOverlaps(virBitmap *b1,
1125 virBitmap *b2)
1126 {
1127 size_t i;
1128
1129 if (b1->nbits > b2->nbits) {
1130 virBitmap *tmp = b1;
1131 b1 = b2;
1132 b2 = tmp;
1133 }
1134
1135 for (i = 0; i < b1->map_len; i++) {
1136 if (b1->map[i] & b2->map[i])
1137 return true;
1138 }
1139
1140 return false;
1141 }
1142
1143
1144 /**
1145 * virBitmapIntersect:
1146 * @a: bitmap, modified to contain result
1147 * @b: bitmap
1148 *
1149 * Performs intersection of two bitmaps: a = intersect(a, b)
1150 */
1151 void
virBitmapIntersect(virBitmap * a,virBitmap * b)1152 virBitmapIntersect(virBitmap *a,
1153 virBitmap *b)
1154 {
1155 size_t i;
1156 size_t max = a->map_len;
1157
1158 if (max > b->map_len)
1159 max = b->map_len;
1160
1161 for (i = 0; i < max; i++)
1162 a->map[i] &= b->map[i];
1163 }
1164
1165
1166 /**
1167 * virBitmapUnion:
1168 * @a: bitmap, modified to contain result
1169 * @b: other bitmap
1170 *
1171 * Performs union of two bitmaps: a = union(a, b)
1172 *
1173 * Returns 0 on success, <0 on failure.
1174 */
1175 int
virBitmapUnion(virBitmap * a,const virBitmap * b)1176 virBitmapUnion(virBitmap *a,
1177 const virBitmap *b)
1178 {
1179 size_t i;
1180
1181 if (a->nbits < b->nbits &&
1182 virBitmapExpand(a, b->nbits - 1) < 0) {
1183 return -1;
1184 }
1185
1186 for (i = 0; i < b->map_len; i++)
1187 a->map[i] |= b->map[i];
1188
1189 return 0;
1190 }
1191
1192
1193 /**
1194 * virBitmapSubtract:
1195 * @a: minuend/result
1196 * @b: subtrahend
1197 *
1198 * Performs subtraction of two bitmaps: a = a - b
1199 */
1200 void
virBitmapSubtract(virBitmap * a,virBitmap * b)1201 virBitmapSubtract(virBitmap *a,
1202 virBitmap *b)
1203 {
1204 size_t i;
1205 size_t max = a->map_len;
1206
1207 if (max > b->map_len)
1208 max = b->map_len;
1209
1210 for (i = 0; i < max; i++)
1211 a->map[i] &= ~b->map[i];
1212 }
1213
1214
1215 /**
1216 * virBitmapShrink:
1217 * @map: Pointer to bitmap
1218 * @b: Size to reduce the bitmap to
1219 *
1220 * Reduces the bitmap to size @b. Nothing will change if the size is already
1221 * smaller than or equal to @b.
1222 */
1223 void
virBitmapShrink(virBitmap * map,size_t b)1224 virBitmapShrink(virBitmap *map,
1225 size_t b)
1226 {
1227 size_t toremove;
1228 size_t nl = 0;
1229 size_t nb = 0;
1230
1231 if (!map)
1232 return;
1233
1234 if (map->nbits >= b)
1235 map->nbits = b;
1236
1237 nl = map->nbits / VIR_BITMAP_BITS_PER_UNIT;
1238 nb = map->nbits % VIR_BITMAP_BITS_PER_UNIT;
1239 map->map[nl] &= ((1UL << nb) - 1);
1240
1241 toremove = map->map_alloc - (nl + 1);
1242
1243 if (toremove == 0)
1244 return;
1245
1246 VIR_SHRINK_N(map->map, map->map_alloc, toremove);
1247
1248 /* length needs to be fixed as well */
1249 map->map_len = map->map_alloc;
1250 }
1251