1 /* 2 * Copyright 2013-2022, Haiku, Inc. All rights reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * Paweł Dziepak, pdziepak@quarnos.org 7 * Augustin Cavalier <waddlesplash> 8 */ 9 #include <util/Bitmap.h> 10 11 #include <stdlib.h> 12 #include <string.h> 13 14 #include <util/BitUtils.h> 15 16 17 namespace BKernel { 18 19 20 Bitmap::Bitmap(size_t bitCount) 21 : 22 fElementsCount(0), 23 fSize(0), 24 fBits(NULL) 25 { 26 Resize(bitCount); 27 } 28 29 30 Bitmap::~Bitmap() 31 { 32 free(fBits); 33 } 34 35 36 status_t 37 Bitmap::InitCheck() 38 { 39 return (fBits != NULL) ? B_OK : B_NO_MEMORY; 40 } 41 42 43 status_t 44 Bitmap::Resize(size_t bitCount) 45 { 46 const size_t count = (bitCount + kBitsPerElement - 1) / kBitsPerElement; 47 if (count == fElementsCount) { 48 fSize = bitCount; 49 return B_OK; 50 } 51 52 void* bits = realloc(fBits, sizeof(addr_t) * count); 53 if (bits == NULL) 54 return B_NO_MEMORY; 55 fBits = (addr_t*)bits; 56 57 if (fElementsCount < count) 58 memset(&fBits[fElementsCount], 0, sizeof(addr_t) * (count - fElementsCount)); 59 60 fSize = bitCount; 61 fElementsCount = count; 62 return B_OK; 63 } 64 65 66 void 67 Bitmap::Shift(ssize_t bitCount) 68 { 69 if (bitCount == 0) 70 return; 71 72 const size_t shift = (bitCount > 0) ? bitCount : -bitCount; 73 const size_t nElements = shift / kBitsPerElement, nBits = shift % kBitsPerElement; 74 if (nElements != 0) { 75 if (bitCount > 0) { 76 // "Left" shift. 77 memmove(&fBits[nElements], fBits, sizeof(addr_t) * (fElementsCount - nElements)); 78 memset(fBits, 0, sizeof(addr_t) * nElements); 79 } else if (bitCount < 0) { 80 // "Right" shift. 81 memmove(fBits, &fBits[nElements], sizeof(addr_t) * (fElementsCount - nElements)); 82 memset(&fBits[fElementsCount - nElements], 0, sizeof(addr_t) * nElements); 83 } 84 } 85 86 // If the shift was by a multiple of the element size, nothing more to do. 87 if (nBits == 0) 88 return; 89 90 // One set of bits comes from the "current" element and are shifted in the 91 // direction of the shift; the other set comes from the next-processed 92 // element and are shifted in the opposite direction. 93 if (bitCount > 0) { 94 // "Left" shift. 95 for (ssize_t i = fElementsCount - 1; i >= 0; i--) { 96 addr_t low = 0; 97 if (i != 0) 98 low = fBits[i - 1] >> (kBitsPerElement - nBits); 99 const addr_t high = fBits[i] << nBits; 100 fBits[i] = low | high; 101 } 102 } else if (bitCount < 0) { 103 // "Right" shift. 104 for (size_t i = 0; i < fElementsCount; i++) { 105 const addr_t low = fBits[i] >> nBits; 106 addr_t high = 0; 107 if (i != (fElementsCount - 1)) 108 high = fBits[i + 1] << (kBitsPerElement - nBits); 109 fBits[i] = low | high; 110 } 111 } 112 } 113 114 115 ssize_t 116 Bitmap::GetHighestSet() const 117 { 118 size_t i = fElementsCount - 1; 119 while (i >= 0 && fBits[i] == 0) 120 i--; 121 122 if (i < 0) 123 return -1; 124 125 STATIC_ASSERT(sizeof(addr_t) == sizeof(uint64) 126 || sizeof(addr_t) == sizeof(uint32)); 127 if (sizeof(addr_t) == sizeof(uint32)) 128 return log2(fBits[i]) + i * kBitsPerElement; 129 130 uint32 v = (uint64)fBits[i] >> 32; 131 if (v != 0) 132 return log2(v) + sizeof(uint32) * 8 + i * kBitsPerElement; 133 return log2(fBits[i]) + i * kBitsPerElement; 134 } 135 136 137 } // namespace BKernel 138