1#define JEMALLOC_BITMAP_C_
2#include "jemalloc/internal/jemalloc_internal.h"
3
4/******************************************************************************/
5
6#ifdef USE_TREE
7
8void
9bitmap_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;
23 group_count = BITMAP_BITS2GROUPS(nbits);
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;
28 group_count = BITMAP_BITS2GROUPS(group_count);
29 }
30 binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
31 + group_count;
32 assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX);
33 binfo->nlevels = i;
34 binfo->nbits = nbits;
35}
36
37static size_t
38bitmap_info_ngroups(const bitmap_info_t *binfo)
39{
40
41 return (binfo->levels[binfo->nlevels].group_offset);
42}
43
44void
45bitmap_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 */
57 memset(bitmap, 0xffU, bitmap_size(binfo));
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}
71
72#else /* USE_TREE */
73
74void
75bitmap_info_init(bitmap_info_t *binfo, size_t nbits)
76{
| 1#define JEMALLOC_BITMAP_C_
2#include "jemalloc/internal/jemalloc_internal.h"
3
4/******************************************************************************/
5
6#ifdef USE_TREE
7
8void
9bitmap_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;
23 group_count = BITMAP_BITS2GROUPS(nbits);
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;
28 group_count = BITMAP_BITS2GROUPS(group_count);
29 }
30 binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
31 + group_count;
32 assert(binfo->levels[i].group_offset <= BITMAP_GROUPS_MAX);
33 binfo->nlevels = i;
34 binfo->nbits = nbits;
35}
36
37static size_t
38bitmap_info_ngroups(const bitmap_info_t *binfo)
39{
40
41 return (binfo->levels[binfo->nlevels].group_offset);
42}
43
44void
45bitmap_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 */
57 memset(bitmap, 0xffU, bitmap_size(binfo));
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}
71
72#else /* USE_TREE */
73
74void
75bitmap_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
| 77
78 assert(nbits > 0);
79 assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));
80
|
82 i = nbits >> LG_BITMAP_GROUP_NBITS;
83 if (nbits % BITMAP_GROUP_NBITS != 0)
84 i++;
85 binfo->ngroups = i;
| 81 binfo->ngroups = BITMAP_BITS2GROUPS(nbits);
|
86 binfo->nbits = nbits;
87}
88
89static size_t
90bitmap_info_ngroups(const bitmap_info_t *binfo)
91{
92
93 return (binfo->ngroups);
94}
95
96void
97bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo)
98{
99 size_t extra;
100
101 memset(bitmap, 0xffU, bitmap_size(binfo));
| 82 binfo->nbits = nbits;
83}
84
85static size_t
86bitmap_info_ngroups(const bitmap_info_t *binfo)
87{
88
89 return (binfo->ngroups);
90}
91
92void
93bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo)
94{
95 size_t extra;
96
97 memset(bitmap, 0xffU, bitmap_size(binfo));
|
102 extra = (binfo->nbits % (binfo->ngroups * BITMAP_GROUP_NBITS));
| 98 extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK))
99 & BITMAP_GROUP_NBITS_MASK;
|
103 if (extra != 0)
| 100 if (extra != 0)
|
104 bitmap[binfo->ngroups - 1] >>= (BITMAP_GROUP_NBITS - extra);
| 101 bitmap[binfo->ngroups - 1] >>= extra;
|
105}
106
107#endif /* USE_TREE */
108
109size_t
110bitmap_size(const bitmap_info_t *binfo)
111{
112
113 return (bitmap_info_ngroups(binfo) << LG_SIZEOF_BITMAP);
114}
| 102}
103
104#endif /* USE_TREE */
105
106size_t
107bitmap_size(const bitmap_info_t *binfo)
108{
109
110 return (bitmap_info_ngroups(binfo) << LG_SIZEOF_BITMAP);
111}
|