1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
#pragma once
#include "Assertions.h"
#include "StdLibExtras.h"
#include "Types.h"
#include "kmalloc.h"
namespace AK {
class Bitmap {
public:
// NOTE: A wrapping Bitmap won't try to free the wrapped data.
static Bitmap wrap(u8* data, int size)
{
return Bitmap(data, size);
}
static Bitmap create(int size, bool default_value = 0)
{
return Bitmap(size, default_value);
}
static Bitmap create()
{
return Bitmap();
}
~Bitmap()
{
if (m_owned)
kfree(m_data);
m_data = nullptr;
}
int size() const { return m_size; }
bool get(int index) const
{
ASSERT(index < m_size);
return 0 != (m_data[index / 8] & (1u << (index % 8)));
}
void set(int index, bool value) const
{
ASSERT(index < m_size);
if (value)
m_data[index / 8] |= static_cast<u8>((1u << (index % 8)));
else
m_data[index / 8] &= static_cast<u8>(~(1u << (index % 8)));
}
u8* data() { return m_data; }
const u8* data() const { return m_data; }
void grow(int size, bool default_value)
{
ASSERT(size > m_size);
auto previous_size_bytes = size_in_bytes();
auto previous_size = m_size;
auto previous_data = m_data;
m_size = size;
m_data = reinterpret_cast<u8*>(kmalloc(size_in_bytes()));
fill(default_value);
if (previous_data != nullptr) {
memcpy(m_data, previous_data, previous_size_bytes);
if ((previous_size % 8) != 0) {
if (default_value)
m_data[previous_size_bytes - 1] |= (0xff >> (previous_size % 8));
else
m_data[previous_size_bytes - 1] &= ~(0xff >> (previous_size % 8));
}
kfree(previous_data);
}
}
void fill(bool value)
{
memset(m_data, value ? 0xff : 0x00, size_in_bytes());
}
int find_first_set() const
{
int i = 0;
while (i < m_size / 8 && m_data[i] == 0x00)
i++;
int j = 0;
for (j = i * 8; j < m_size; j++)
if (get(j))
return j;
return -1;
}
int find_first_unset() const
{
int i = 0;
while (i < m_size / 8 && m_data[i] == 0xff)
i++;
int j = 0;
for (j = i * 8; j < m_size; j++)
if (!get(j))
return j;
return -1;
}
private:
explicit Bitmap()
: m_size(0)
, m_owned(true)
{
m_data = nullptr;
}
explicit Bitmap(int size, bool default_value)
: m_size(size)
, m_owned(true)
{
ASSERT(m_size != 0);
m_data = reinterpret_cast<u8*>(kmalloc(size_in_bytes()));
fill(default_value);
}
Bitmap(u8* data, int size)
: m_data(data)
, m_size(size)
, m_owned(false)
{
}
int size_in_bytes() const { return ceil_div(m_size, 8); }
u8* m_data { nullptr };
int m_size { 0 };
bool m_owned { false };
};
}
using AK::Bitmap;
|
