cppp/src/bitmap.h at master · AlgoLab/cppp · GitHub

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
/* Licensed under LGPLv2+
   Originally from CCAN bitmap.h
*/

#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <gc.h>


typedef uint64_t bitmap_word;

#define BITMAP_WORD_BITS        64
#define LOG_BITMAP_WORD_BITS    6
#define BITMAP_BIT_PLACE(_n)    ((_n) >> LOG_BITMAP_WORD_BITS)
#define BITMAP_BIT_OFFSET(_n)   ((_n) & (BITMAP_WORD_BITS - 1))
#define BITMAP_NWORDS(_n)       (((_n) + BITMAP_WORD_BITS - 1) >> LOG_BITMAP_WORD_BITS)
#define BITMAP_HEADWORDS(_n)    ((_n) / BITMAP_WORD_BITS)
#define BITMAP_TAILWORD(_bm,_n) ((_bm)[BITMAP_HEADWORDS(_n)])
#define BITMAP_HASTAIL(_n)      (((_n) % BITMAP_WORD_BITS) != 0)
#define BITMAP_TAILBITS(_n)     (~(-1UL >> ((_n) % BITMAP_WORD_BITS)))
#define BITMAP_TAIL(_bm,_n)     (BITMAP_TAILWORD(_bm, _n) & BITMAP_TAILBITS(_n))
#define BITMAP_WORD(_bm,_n)     ((_bm)[(_n) >> LOG_BITMAP_WORD_BITS])
#define BITMAP_BIT_MASK(_n)     (1UL << (BITMAP_BIT_OFFSET(_n)))

static inline size_t bitmap_sizeof(unsigned long nbits) {
        return BITMAP_NWORDS(nbits) * sizeof(bitmap_word);
}

static inline bitmap_word *bitmap_alloc(unsigned long nbits) {
        return GC_MALLOC(bitmap_sizeof(nbits));
}

static inline void bitmap_zero(bitmap_word *bitmap, unsigned long nbits) {
        memset(bitmap, 0, bitmap_sizeof(nbits));
}

static inline bitmap_word *bitmap_alloc0(unsigned long nbits) {
        bitmap_word *bitmap;
        bitmap = bitmap_alloc(nbits);
        bitmap_zero(bitmap, nbits);
        return bitmap;
}

static inline void bitmap_set_bit(bitmap_word *bitmap, unsigned long n) {
        BITMAP_WORD(bitmap, n) |= BITMAP_BIT_MASK(n);
}

static inline bool bitmap_get_bit(bitmap_word *bitmap, unsigned long n) {
        return ((BITMAP_WORD(bitmap, n) & BITMAP_BIT_MASK(n))  > 0);
}

static inline void bitmap_clear_bit(bitmap_word *bitmap, unsigned long n) {
        BITMAP_WORD(bitmap, n) &= ~BITMAP_BIT_MASK(n);
}

static inline void bitmap_copy(bitmap_word *dst, const bitmap_word *src, unsigned long nbits) {
        memcpy(dst, src, bitmap_sizeof(nbits));
}

static inline bool bitmap_includes(bitmap_word *src1, const bitmap_word *src2, unsigned long nbits) {
        unsigned long i;
        for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
                if (src1[i]  & ~src2[i])
                        return false;
        }

        if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits)))
                return false;
        return true;
}


/**
   \brief true if the first array includes the second
*/
static inline bool
bool_array_includes(bool* a1, bool* a2, uint32_t n) {
        for (uint32_t i = 0; i < n; i++)
                if (a2[i] && !a1[i])
                        return false;
        return true;
}


/**
   \brief true if the two arrays are the same
*/
static inline bool
bool_array_equal(bool* a1, bool* a2, uint32_t n) {
        for (uint32_t i = 0; i < n; i++)
                if (a1[i] != a2[i])
                        return false;
        return true;
}


/**
   \brief computes the difference a1-a2 of two sets a1, a2, receiving the
   characteristics function of those two sets.
*/
static inline bool*
bool_array_difference(const bool* a1, const bool* a2, uint32_t n) {
        bool* b = GC_MALLOC(n * sizeof(bool));
        for (uint32_t i = 0; i < n; i++)
                b[i] = (a1[i] && !a2[i]);
        return b;
}