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 17namespace BKernel { 18 19 20Bitmap::Bitmap(size_t bitCount) 21 : 22 fElementsCount(0), 23 fSize(0), 24 fBits(NULL) 25{ 26 Resize(bitCount); 27} 28 29 30Bitmap::~Bitmap() 31{ 32 free(fBits); 33} 34 35 36status_t 37Bitmap::InitCheck() 38{ 39 return (fBits != NULL) ? B_OK : B_NO_MEMORY; 40} 41 42 43status_t 44Bitmap::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 66void 67Bitmap::Shift(ssize_t bitCount) 68{ 69 return bitmap_shift<addr_t>(fBits, fSize, bitCount); 70} 71 72 73void 74Bitmap::SetRange(size_t index, size_t count) 75{ 76 // TODO: optimize 77 for (; count > 0; count--) 78 Set(index++); 79} 80 81 82void 83Bitmap::ClearRange(size_t index, size_t count) 84{ 85 // TODO: optimize 86 for (; count > 0; count--) 87 Clear(index++); 88} 89 90 91ssize_t 92Bitmap::GetLowestClear(size_t fromIndex) const 93{ 94 // TODO: optimize 95 96 for (size_t i = fromIndex; i < fSize; i++) { 97 if (!Get(i)) 98 return i; 99 } 100 return -1; 101} 102 103 104ssize_t 105Bitmap::GetLowestContiguousClear(size_t count, size_t fromIndex) const 106{ 107 // TODO: optimize 108 109 // nothing to find 110 if (count == 0) 111 return fromIndex; 112 113 for (;;) { 114 ssize_t index = GetLowestClear(fromIndex); 115 if (index < 0) 116 return index; 117 118 // overflow check 119 if ((size_t)index + count - 1 < (size_t)index) 120 return -1; 121 122 size_t curCount = 1; 123 while (curCount < count && Get(index + curCount)) 124 curCount++; 125 126 if (curCount == count) 127 return index; 128 129 fromIndex = index + curCount; 130 } 131} 132 133 134ssize_t 135Bitmap::GetHighestSet() const 136{ 137 size_t i = fElementsCount - 1; 138 while (i >= 0 && fBits[i] == 0) 139 i--; 140 141 if (i < 0) 142 return -1; 143 144 STATIC_ASSERT(sizeof(addr_t) == sizeof(uint64) 145 || sizeof(addr_t) == sizeof(uint32)); 146 if (sizeof(addr_t) == sizeof(uint32)) 147 return log2(fBits[i]) + i * kBitsPerElement; 148 149 uint32 v = (uint64)fBits[i] >> 32; 150 if (v != 0) 151 return log2(v) + sizeof(uint32) * 8 + i * kBitsPerElement; 152 return log2(fBits[i]) + i * kBitsPerElement; 153} 154 155 156} // namespace BKernel 157