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 return bitmap_shift<addr_t>(fBits, fSize, bitCount); 70 } 71 72 73 ssize_t 74 Bitmap::GetHighestSet() const 75 { 76 size_t i = fElementsCount - 1; 77 while (i >= 0 && fBits[i] == 0) 78 i--; 79 80 if (i < 0) 81 return -1; 82 83 STATIC_ASSERT(sizeof(addr_t) == sizeof(uint64) 84 || sizeof(addr_t) == sizeof(uint32)); 85 if (sizeof(addr_t) == sizeof(uint32)) 86 return log2(fBits[i]) + i * kBitsPerElement; 87 88 uint32 v = (uint64)fBits[i] >> 32; 89 if (v != 0) 90 return log2(v) + sizeof(uint32) * 8 + i * kBitsPerElement; 91 return log2(fBits[i]) + i * kBitsPerElement; 92 } 93 94 95 } // namespace BKernel 96