1// SPDX-License-Identifier: GPL-3.0-or-later
2
3#include <mos/lib/structures/bitmap.hpp>
4#include <mos_stdlib.hpp>
5#include <mos_string.hpp>
6
7bitmap_line_t *bitmap_create(size_t size)
8{
9 size_t nlines = BITMAP_LINE_COUNT(size);
10 bitmap_line_t *bitmap = kcalloc<bitmap_line_t>(n_members: nlines);
11 bitmap_zero(bitmap, bitmap_nlines: nlines);
12 return bitmap;
13}
14
15void bitmap_zero(bitmap_line_t *bitmap, size_t bitmap_nlines)
16{
17 memzero(s: bitmap, n: bitmap_nlines * sizeof(bitmap_line_t));
18}
19
20bool bitmap_set(bitmap_line_t *bitmap, size_t bitmap_nlines, size_t index)
21{
22 size_t line = index / BITMAP_LINE_BITS;
23 size_t bit = index % BITMAP_LINE_BITS;
24 if (line >= bitmap_nlines)
25 return false;
26
27 bool original = bitmap_get(bitmap, bitmap_nlines, index);
28 bitmap[line] |= ((bitmap_line_t) 1 << bit);
29
30 return original == false;
31}
32
33bool bitmap_clear(bitmap_line_t *bitmap, size_t bitmap_nlines, size_t index)
34{
35 size_t line = index / BITMAP_LINE_BITS;
36 size_t bit = index % BITMAP_LINE_BITS;
37 if (line >= bitmap_nlines)
38 return false;
39
40 bool original = bitmap_get(bitmap, bitmap_nlines, index);
41 bitmap[line] &= ~((bitmap_line_t) 1 << bit);
42
43 return original == true;
44}
45
46bool bitmap_get(const bitmap_line_t *bitmap, size_t bitmap_nlines, size_t index)
47{
48 size_t line = index / BITMAP_LINE_BITS;
49 size_t bit = index % BITMAP_LINE_BITS;
50 if (line >= bitmap_nlines)
51 return false;
52 return bitmap[line] & ((bitmap_line_t) 1 << bit);
53}
54
55size_t bitmap_find_first_free_n(bitmap_line_t *bitmap, size_t bitmap_nlines, size_t begin_bit, size_t n_bits)
56{
57 size_t target_starting_line = begin_bit / BITMAP_LINE_BITS;
58 size_t target_starting_bit = begin_bit % BITMAP_LINE_BITS;
59 size_t free_bits = 0;
60
61 for (size_t line_i = target_starting_line; free_bits < n_bits; line_i++)
62 {
63 if (line_i >= bitmap_nlines)
64 return -1;
65
66 bitmap_line_t line = bitmap[line_i];
67
68 if (line == 0)
69 {
70 free_bits += BITMAP_LINE_BITS;
71 continue;
72 }
73 else if (line == (bitmap_line_t) ~0)
74 {
75 // a full line of occupied bits
76 target_starting_line = line_i + 1;
77 free_bits = 0;
78 target_starting_bit = 0;
79 continue;
80 }
81
82 for (size_t bit = 0; bit < BITMAP_LINE_BITS; bit++)
83 {
84 if (free_bits >= n_bits)
85 break;
86
87 if (!bitmap_get(bitmap: &line, bitmap_nlines, index: bit))
88 {
89 // we have found a free line
90 free_bits++;
91 }
92 else
93 {
94 // this bit is occupied
95 free_bits = 0;
96 target_starting_bit = bit + 1;
97 target_starting_line = line_i;
98 }
99 }
100 }
101
102 return target_starting_line * BITMAP_LINE_BITS + target_starting_bit;
103}
104
105void bitmap_set_range(bitmap_line_t *bitmap, size_t bitmap_nlines, size_t start_bit, size_t end_bit, bool value)
106{
107 size_t start_line = start_bit / BITMAP_LINE_BITS;
108 size_t start_bit_in_line = start_bit % BITMAP_LINE_BITS;
109 size_t end_line = end_bit / BITMAP_LINE_BITS;
110 size_t end_bit_in_line = end_bit % BITMAP_LINE_BITS;
111
112 if (start_line >= bitmap_nlines || end_line >= bitmap_nlines)
113 return;
114
115 if (start_line == end_line)
116 {
117 bitmap_line_t line = bitmap[start_line];
118 bitmap_line_t mask = ((bitmap_line_t) 1 << (end_bit_in_line - start_bit_in_line + 1)) - 1;
119 mask <<= start_bit_in_line;
120 if (value)
121 line |= mask;
122 else
123 line &= ~mask;
124 bitmap[start_line] = line;
125 return;
126 }
127
128 bitmap_line_t line = bitmap[start_line];
129 bitmap_line_t mask = ((bitmap_line_t) 1 << (BITMAP_LINE_BITS - start_bit_in_line)) - 1;
130 mask <<= start_bit_in_line;
131 if (value)
132 line |= mask;
133 else
134 line &= ~mask;
135 bitmap[start_line] = line;
136
137 for (size_t i = start_line + 1; i < end_line; i++)
138 {
139 if (value)
140 bitmap[i] = (bitmap_line_t) ~0;
141 else
142 bitmap[i] = 0;
143 }
144
145 line = bitmap[end_line];
146 mask = ((bitmap_line_t) 1 << (end_bit_in_line + 1)) - 1;
147 if (value)
148 line |= mask;
149 else
150 line &= ~mask;
151 bitmap[end_line] = line;
152}
153