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 __BITPOOL_H
#define __BITPOOL_H
#include <stdint.h>
#include <stddef.h>
/*
* Fixed-size bit array shared by the IPv4/IPv6 address pool allocators.
*
* Semantics: bit == 1 => allocated/unavailable, bit == 0 => free. A freshly
* calloc'd map is therefore all-free. The caller is responsible for pre-setting
* to 1 any bit it never wants handed out:
* - "remainder" bits in the final word (indices >= count), and
* - reserved in-range bits (e.g. the p2p gateway collision),
* so the word-at-a-time scan can never return a non-existent unit.
*/
typedef unsigned long bm_word_t;
#define BM_WORD_BITS (8 * sizeof(bm_word_t))
#define BM_NWORDS(n) (((n) + BM_WORD_BITS - 1) / BM_WORD_BITS)
#define BM_INVALID ((uint64_t)-1)
static inline void bm_set(bm_word_t *bm, uint64_t i)
{
bm[i / BM_WORD_BITS] |= (bm_word_t)1 << (i % BM_WORD_BITS);
}
static inline void bm_clear(bm_word_t *bm, uint64_t i)
{
bm[i / BM_WORD_BITS] &= ~((bm_word_t)1 << (i % BM_WORD_BITS));
}
static inline int bm_test(const bm_word_t *bm, uint64_t i)
{
return (bm[i / BM_WORD_BITS] >> (i % BM_WORD_BITS)) & 1;
}
/*
* Find the first free (0) bit at or after `from`, wrapping once back to 0.
* `count` is the number of valid bits; remainder bits in the final word must
* already be set to 1 by the caller so they are never returned. Returns the
* bit index in [0,count), or BM_INVALID if every bit is used.
*
* Word-at-a-time: a fully-used word (~w == 0) is skipped in one branch, so the
* scan is O(1) amortized for a sparse pool and O(count/word) worst case.
*/
static inline uint64_t bm_find_free(const bm_word_t *bm, uint64_t count, uint64_t from)
{
uint64_t nwords, fw, i;
unsigned fb;
if (!count)
return BM_INVALID;
if (from >= count)
from = 0;
nwords = BM_NWORDS(count);
fw = from / BM_WORD_BITS;
fb = from % BM_WORD_BITS;
/* Probe nwords+1 times: the start word is examined first with its low bits
* (< from) masked off, and once more at the end with only those low bits,
* so every bit is considered exactly once across the wrap. */
for (i = 0; i <= nwords; i++) {
uint64_t word = fw + i;
bm_word_t inv;
if (word >= nwords)
word -= nwords;
inv = ~bm[word];
if (i == 0)
inv &= ~(((bm_word_t)1 << fb) - 1); /* skip bits below `from` */
else if (i == nwords)
inv &= ((bm_word_t)1 << fb) - 1; /* wrapped: only those skipped bits */
if (inv) {
uint64_t bit = word * BM_WORD_BITS + __builtin_ctzl(inv);
if (bit < count)
return bit;
}
}
return BM_INVALID;
}
#endif
|
