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