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 void 74 Bitmap::SetRange(size_t index, size_t count) 75 { 76 // TODO: optimize 77 for (; count > 0; count--) 78 Set(index++); 79 } 80 81 82 void 83 Bitmap::ClearRange(size_t index, size_t count) 84 { 85 // TODO: optimize 86 for (; count > 0; count--) 87 Clear(index++); 88 } 89 90 91 ssize_t 92 Bitmap::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 104 ssize_t 105 Bitmap::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 134 ssize_t 135 Bitmap::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