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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
#include <assert.h>
#include <kmalloc.h>
#include <lib/relist.h>
#include <math.h>
#include <string.h>
void relist_init(struct relist *list) {
list->num_entries = 0;
list->bitmap_capacity = 1;
list->bitmap = kcalloc(sizeof(u64), list->bitmap_capacity);
if (!list->bitmap) {
goto relist_init_error;
}
list->entries =
kallocarray(sizeof(void *) * sizeof(u64) * 8, list->bitmap_capacity);
if (!list->entries) {
kfree(list->bitmap);
goto relist_init_error;
}
return;
// Can't allocate now but future appends can try to allocate anyways so
// there is no reason to "fail" the init.
relist_init_error:
list->bitmap_capacity = 0;
list->entries = NULL;
list->bitmap = NULL;
return;
}
void relist_reset(struct relist *list) {
list->num_entries = 0;
memset(list->bitmap, 0, list->bitmap_capacity * sizeof(u64));
}
int relist_clone(struct relist *in, struct relist *out) {
out->bitmap_capacity = in->bitmap_capacity;
out->bitmap = kcalloc(sizeof(u64), out->bitmap_capacity);
if (!out->bitmap) {
goto relist_clone_error;
}
out->entries =
kallocarray(sizeof(void *) * sizeof(u64) * 8, out->bitmap_capacity);
if (!out->entries) {
kfree(out->bitmap);
goto relist_clone_error;
}
out->num_entries = in->num_entries;
memcpy(out->bitmap, in->bitmap, sizeof(u64) * out->bitmap_capacity);
memcpy(out->entries, in->entries,
sizeof(void *) * sizeof(u64) * 8 * out->bitmap_capacity);
return 1;
relist_clone_error:
out->num_entries = 0;
out->bitmap_capacity = 0;
out->entries = NULL;
out->bitmap = NULL;
return 0;
}
static int relist_find_free_entry(struct relist *list, u32 *entry) {
for (u32 i = 0; i < list->bitmap_capacity; i++) {
if (0 == ~(list->bitmap[i])) {
continue;
}
for (int c = 0; c < 64; c++) {
if (!(list->bitmap[i] & ((u64)1 << c))) {
*entry = i * 64 + c;
return 1;
}
}
}
*entry = 0;
return 0;
}
int relist_add(struct relist *list, void *value, u32 *index) {
u32 entry;
if (!relist_find_free_entry(list, &entry)) {
u32 new_capacity = list->bitmap_capacity + 1;
u64 *new_allocation = kcalloc(sizeof(u64), new_capacity);
if (!new_allocation) {
return 0;
}
void *new_entry = krecalloc(list->entries, sizeof(void *) * sizeof(u64) * 8,
new_capacity);
if (!new_entry) {
kfree(new_allocation);
return 0;
}
if (list->bitmap) {
size_t to_copy = min(list->bitmap_capacity, new_capacity) * sizeof(u64);
memcpy(new_allocation, list->bitmap, to_copy);
kfree(list->bitmap);
}
list->bitmap = new_allocation;
list->bitmap_capacity = new_capacity;
list->entries = new_entry;
assert(relist_find_free_entry(list, &entry));
}
list->entries[entry] = value;
if (index) {
*index = entry;
}
list->num_entries++;
list->bitmap[entry / 64] |= ((u64)1 << (entry % 64));
return 1;
}
int relist_remove(struct relist *list, u32 index) {
if (index >= list->bitmap_capacity * 64) {
assert(0);
return 0;
}
int is_used = (list->bitmap[index / 64] & ((u64)1 << (index % 64)));
if (!is_used) {
assert(0);
return 0;
}
list->num_entries--;
list->bitmap[index / 64] &= ~((u64)1 << (index % 64));
return 1;
}
int relist_set(struct relist *list, u32 index, void *value) {
if (index >= list->bitmap_capacity * 64) {
assert(0);
return 0;
}
int is_used = (list->bitmap[index / 64] & ((u64)1 << (index % 64)));
assert(is_used);
list->entries[index] = value;
return 1;
}
int relist_get(const struct relist *list, u32 index, void **out, int *end) {
if (end) {
*end = 0;
}
if (index >= list->bitmap_capacity * 64) {
if (end) {
*end = 1;
}
return 0;
}
int is_used = (list->bitmap[index / 64] & ((u64)1 << (index % 64)));
if (!is_used) {
return 0;
}
*out = list->entries[index];
return 1;
}
void relist_free(struct relist *list) {
list->num_entries = 0;
list->bitmap_capacity = 0;
kfree(list->entries);
kfree(list->bitmap);
list->entries = NULL;
list->bitmap = NULL;
}
|
