]>
Commit | Line | Data |
---|---|---|
1a4d82fc | 1 | #define JEMALLOC_BITMAP_C_ |
970d7e83 LB |
2 | #include "jemalloc/internal/jemalloc_internal.h" |
3 | ||
4 | /******************************************************************************/ | |
970d7e83 | 5 | |
54a0048b SL |
6 | #ifdef USE_TREE |
7 | ||
970d7e83 LB |
8 | void |
9 | bitmap_info_init(bitmap_info_t *binfo, size_t nbits) | |
10 | { | |
11 | unsigned i; | |
12 | size_t group_count; | |
13 | ||
14 | assert(nbits > 0); | |
15 | assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS)); | |
16 | ||
17 | /* | |
18 | * Compute the number of groups necessary to store nbits bits, and | |
19 | * progressively work upward through the levels until reaching a level | |
20 | * that requires only one group. | |
21 | */ | |
22 | binfo->levels[0].group_offset = 0; | |
1a4d82fc | 23 | group_count = BITMAP_BITS2GROUPS(nbits); |
970d7e83 LB |
24 | for (i = 1; group_count > 1; i++) { |
25 | assert(i < BITMAP_MAX_LEVELS); | |
26 | binfo->levels[i].group_offset = binfo->levels[i-1].group_offset | |
27 | + group_count; | |
1a4d82fc | 28 | group_count = BITMAP_BITS2GROUPS(group_count); |
970d7e83 LB |
29 | } |
30 | binfo->levels[i].group_offset = binfo->levels[i-1].group_offset | |
31 | + group_count; | |
1a4d82fc | 32 | assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX); |
970d7e83 LB |
33 | binfo->nlevels = i; |
34 | binfo->nbits = nbits; | |
35 | } | |
36 | ||
54a0048b | 37 | static size_t |
970d7e83 LB |
38 | bitmap_info_ngroups(const bitmap_info_t *binfo) |
39 | { | |
40 | ||
54a0048b | 41 | return (binfo->levels[binfo->nlevels].group_offset); |
970d7e83 LB |
42 | } |
43 | ||
44 | void | |
45 | bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo) | |
46 | { | |
47 | size_t extra; | |
48 | unsigned i; | |
49 | ||
50 | /* | |
51 | * Bits are actually inverted with regard to the external bitmap | |
52 | * interface, so the bitmap starts out with all 1 bits, except for | |
53 | * trailing unused bits (if any). Note that each group uses bit 0 to | |
54 | * correspond to the first logical bit in the group, so extra bits | |
55 | * are the most significant bits of the last group. | |
56 | */ | |
54a0048b | 57 | memset(bitmap, 0xffU, bitmap_size(binfo)); |
970d7e83 LB |
58 | extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK)) |
59 | & BITMAP_GROUP_NBITS_MASK; | |
60 | if (extra != 0) | |
61 | bitmap[binfo->levels[1].group_offset - 1] >>= extra; | |
62 | for (i = 1; i < binfo->nlevels; i++) { | |
63 | size_t group_count = binfo->levels[i].group_offset - | |
64 | binfo->levels[i-1].group_offset; | |
65 | extra = (BITMAP_GROUP_NBITS - (group_count & | |
66 | BITMAP_GROUP_NBITS_MASK)) & BITMAP_GROUP_NBITS_MASK; | |
67 | if (extra != 0) | |
68 | bitmap[binfo->levels[i+1].group_offset - 1] >>= extra; | |
69 | } | |
70 | } | |
54a0048b SL |
71 | |
72 | #else /* USE_TREE */ | |
73 | ||
74 | void | |
75 | bitmap_info_init(bitmap_info_t *binfo, size_t nbits) | |
76 | { | |
77 | size_t i; | |
78 | ||
79 | assert(nbits > 0); | |
80 | assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS)); | |
81 | ||
82 | i = nbits >> LG_BITMAP_GROUP_NBITS; | |
83 | if (nbits % BITMAP_GROUP_NBITS != 0) | |
84 | i++; | |
85 | binfo->ngroups = i; | |
86 | binfo->nbits = nbits; | |
87 | } | |
88 | ||
89 | static size_t | |
90 | bitmap_info_ngroups(const bitmap_info_t *binfo) | |
91 | { | |
92 | ||
93 | return (binfo->ngroups); | |
94 | } | |
95 | ||
96 | void | |
97 | bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo) | |
98 | { | |
99 | size_t extra; | |
100 | ||
101 | memset(bitmap, 0xffU, bitmap_size(binfo)); | |
102 | extra = (binfo->nbits % (binfo->ngroups * BITMAP_GROUP_NBITS)); | |
103 | if (extra != 0) | |
104 | bitmap[binfo->ngroups - 1] >>= (BITMAP_GROUP_NBITS - extra); | |
105 | } | |
106 | ||
107 | #endif /* USE_TREE */ | |
108 | ||
109 | size_t | |
110 | bitmap_size(const bitmap_info_t *binfo) | |
111 | { | |
112 | ||
113 | return (bitmap_info_ngroups(binfo) << LG_SIZEOF_BITMAP); | |
114 | } |