blob: de3618a2e4d5e38bafd911ae223a3be0e7dcd8c2 (
plain)
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
|
#ifndef _TREEBITVEC_H
#define _TREEBITVEC_H
#include <linux/kernel.h>
/* d-ary tree laid out in an array */
#define BITSHIFT ilog2(BITS_PER_LONG)
struct treebitvec {
size_t size;
size_t leaf_offset;
unsigned depth;
unsigned long *bits;
};
static inline size_t treebitvec_up(size_t n)
{
return n = (n - 1) >> BITSHIFT;
}
static inline size_t treebitvec_down(size_t n)
{
return (n << BITSHIFT) + 1;
}
static inline void treebitvec_set(struct treebitvec *bv, size_t n)
{
unsigned bit;
bit = n & (BITS_PER_LONG - 1);
n = (bit >> BITSHIFT) + bv->leaf_offset;
while (!(bv->bits[n] & (1UL << bit))) {
bv->bits[n] |= (1UL << bit);
if (!n)
break;
bit = n & (BITS_PER_LONG - 1);
n = treebitvec_up(n);
}
}
static inline size_t treebitvec_next_set_bit(struct treebitvec *bv, size_t n)
{
unsigned bit;
n = (n >> BITSHIFT) + bv->leaf_offset;
while (1) {
if (!bv->bits[n]) {
if (!n)
return SIZE_MAX;
n = treebitvec_up(n);
continue;
}
bit = __ffs(bv->bits[n]);
bv->bits[n] &= ~(1UL << bit);
if (n >= bv->leaf_offset)
return ((n - bv->leaf_offset) << BITSHIFT) + bit;
n = treebitvec_down(n) + bit;
}
}
static inline int treebitvec_init(struct treebitvec *bv, size_t size)
{
size_t buf_size;
bv->size = size;
bv->depth = ilog2(size - 1) / ilog2(BITS_PER_LONG);
bv->leaf_offset = ((1UL << ((bv->depth + 1) * BITSHIFT)) - 1) /
(BITS_PER_LONG - 1);
buf_size = DIV_ROUND_UP(size, BITS_PER_LONG) + bv->leaf_offset;
bv->bits = kcalloc(buf_size, sizeof(unsigned long), GFP_KERNEL);
if (!bv->bits)
return -ENOMEM;
return 0;
}
#endif
|
