bitmap.c 3.42 KB
Newer Older
Andreas Schmidt's avatar
Andreas Schmidt committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stddef.h>
#include <malloc.h>
#include <string.h>
#include <math.h>
#include "bitmap.h"
#include "dbg.h"
#include "common.h"

Bitmap *Bitmap_create(bool initialValue, uint32_t elementCount)
{
    Bitmap* bitmap = calloc(1, sizeof(Bitmap));
    check_mem(bitmap);
    bitmap->count = elementCount;

15
    uint32_t blockCount = (elementCount + 31) / 32;
Andreas Schmidt's avatar
Andreas Schmidt committed
16
17

    bitmap->data = calloc(blockCount, sizeof(uint32_t));
18
	check_mem(bitmap->data);
Andreas Schmidt's avatar
Andreas Schmidt committed
19
20
21
22
23
24
25
26
27
28
    if(initialValue == true) {
        memset(bitmap->data, -1, blockCount * sizeof(uint32_t));
    }
    return bitmap;

    error:
        PERROR("Could not create bitmap.%s", "");
        return NULL;
}

29
void Bitmap_set_range_0(Bitmap *bitmap, uint32_t start, uint32_t length)
Andreas Schmidt's avatar
Andreas Schmidt committed
30
{
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
    uint32_t start_byte = start / 32;
    uint32_t start_bit = start % 32;
    uint32_t end_byte = (start + length) / 32;
    uint32_t end_bit = (start + length) % 32;
    uint32_t full_mask = ~0u;

    if (start_byte == end_byte) {
        uint32_t mask = (full_mask << end_bit) ^ (full_mask << start_bit);
        bitmap->data[start_byte] ^= (bitmap->data[start_byte] & mask);
    } else {
        uint32_t start_mask = full_mask << start_bit;
        bitmap->data[start_byte] ^= (bitmap->data[start_byte] & start_mask);
        for (uint32_t current_byte = start_byte + 1; current_byte < end_byte; ++current_byte) {
            bitmap->data[current_byte] = 0;
        }
        uint32_t end_mask = ~(full_mask << end_bit);
        bitmap->data[end_byte] ^= (bitmap->data[end_byte] & end_mask);
    }
Andreas Schmidt's avatar
Andreas Schmidt committed
49
50
}

51
void Bitmap_set_range_1(Bitmap *bitmap, uint32_t start, uint32_t length)
Andreas Schmidt's avatar
Andreas Schmidt committed
52
{
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
    uint32_t start_byte = start / 32;
    uint32_t start_bit = start % 32;
    uint32_t end_byte = (start + length) / 32;
    uint32_t end_bit = (start + length) % 32;
    uint32_t full_mask = ~0u;

    if (start_byte == end_byte) {
        uint32_t mask = (full_mask << end_bit) ^ (full_mask << start_bit);
        bitmap->data[start_byte] |= mask;
    } else {
        uint32_t start_mask = full_mask << start_bit;
        bitmap->data[start_byte] |= start_mask;
        for (uint32_t current_byte = start_byte + 1; current_byte < end_byte; ++current_byte) {
            bitmap->data[current_byte] = full_mask;
        }
        uint32_t end_mask = ~(full_mask << end_bit);
        bitmap->data[end_byte] |= end_mask;
    }
Andreas Schmidt's avatar
Andreas Schmidt committed
71
72
73
74
}

uint32_t Bitmap_sum_ones(Bitmap *bitmap, uint32_t start, uint32_t length)
{
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
    uint32_t start_byte = start / 32;
    uint32_t start_bit = start % 32;
    uint32_t end_byte = (start + length) / 32;
    uint32_t end_bit = (start + length) % 32;
    uint32_t full_mask = ~0u;

    if (start_byte == end_byte) {
        uint32_t mask = (full_mask << end_bit) ^ (full_mask << start_bit);
        return __builtin_popcount(bitmap->data[start_byte] & mask);
    } else {
        uint32_t start_mask = full_mask << start_bit;
        uint32_t sum = __builtin_popcount(bitmap->data[start_byte] & start_mask);
        for (uint32_t current_byte = start_byte + 1; current_byte < end_byte; ++current_byte) {
            sum += __builtin_popcount(bitmap->data[current_byte]);
        }
        uint32_t end_mask = ~(full_mask << end_bit);
        sum += __builtin_popcount(bitmap->data[end_byte] & end_mask);

        return sum;
Andreas Schmidt's avatar
Andreas Schmidt committed
94
95
96
97
98
    }
}

uint32_t Bitmap_sum_zeros(Bitmap *bitmap, uint32_t start, uint32_t length)
{
99
    return length - Bitmap_sum_ones(bitmap, start, length);
Andreas Schmidt's avatar
Andreas Schmidt committed
100
101
102
103
104
}

bool Bitmap_destroy(Bitmap *bitmap)
{
    free(bitmap->data);
Andreas Schmidt's avatar
Andreas Schmidt committed
105
    free(bitmap);
Andreas Schmidt's avatar
Andreas Schmidt committed
106
107
    return true;
}