xref: /haiku/src/system/kernel/util/Bitmap.cpp (revision 7323d0a21daaded71c6231c5b7bcba9db4024a40)
1 /*
2  * Copyright 2013 Haiku, Inc. All rights reserved.
3  * Distributed under the terms of the MIT License.
4  *
5  * Authors:
6  *		Paweł Dziepak, pdziepak@quarnos.org
7  */
8 
9 
10 #include <util/Bitmap.h>
11 
12 #include <new>
13 
14 #include <string.h>
15 
16 #include <util/BitUtils.h>
17 
18 
19 const int Bitmap::kBitsPerElement = sizeof(addr_t) * 8;
20 
21 
22 Bitmap::Bitmap(int bitCount)
23 	:
24 	fInitStatus(B_OK),
25 	fElementsCount(0),
26 	fSize(bitCount)
27 {
28 	int count = fSize + kBitsPerElement - 1;
29 	count /= kBitsPerElement;
30 
31 	fBits = new(std::nothrow) addr_t[count];
32 	if (fBits == NULL) {
33 		fSize = 0;
34 		fInitStatus = B_NO_MEMORY;
35 	} else {
36 		fElementsCount = count;
37 		memset(fBits, 0, sizeof(addr_t) * count);
38 	}
39 }
40 
41 
42 Bitmap::~Bitmap()
43 {
44 	delete[] fBits;
45 }
46 
47 
48 int
49 Bitmap::GetHighestSet() const
50 {
51 	int i = fElementsCount - 1;
52 	while (i >= 0 && fBits[i] == 0)
53 		i--;
54 
55 	if (i < 0)
56 		return -1;
57 
58 	STATIC_ASSERT(sizeof(addr_t) == sizeof(uint64)
59 		|| sizeof(addr_t) == sizeof(uint32));
60 	if (sizeof(addr_t) == sizeof(uint32))
61 		return log2(fBits[i]) + i * kBitsPerElement;
62 
63 	uint32 v = (uint64)fBits[i] >> 32;
64 	if (v != 0)
65 		return log2(v) + sizeof(uint32) * 8 + i * kBitsPerElement;
66 	return log2(fBits[i]) + i * kBitsPerElement;
67 }
68 
69