diff options
Diffstat (limited to 'deps/jemalloc/include/jemalloc/internal/bitmap.h')
| -rw-r--r-- | deps/jemalloc/include/jemalloc/internal/bitmap.h | 76 |
1 files changed, 16 insertions, 60 deletions
diff --git a/deps/jemalloc/include/jemalloc/internal/bitmap.h b/deps/jemalloc/include/jemalloc/internal/bitmap.h index 36f38b59c..fcc6005c7 100644 --- a/deps/jemalloc/include/jemalloc/internal/bitmap.h +++ b/deps/jemalloc/include/jemalloc/internal/bitmap.h @@ -15,15 +15,6 @@ typedef unsigned long bitmap_t; #define BITMAP_GROUP_NBITS (ZU(1) << LG_BITMAP_GROUP_NBITS) #define BITMAP_GROUP_NBITS_MASK (BITMAP_GROUP_NBITS-1) -/* - * Do some analysis on how big the bitmap is before we use a tree. For a brute - * force linear search, if we would have to call ffs_lu() more than 2^3 times, - * use a tree instead. - */ -#if LG_BITMAP_MAXBITS - LG_BITMAP_GROUP_NBITS > 3 -# define USE_TREE -#endif - /* Number of groups required to store a given number of bits. */ #define BITMAP_BITS2GROUPS(nbits) \ ((nbits + BITMAP_GROUP_NBITS_MASK) >> LG_BITMAP_GROUP_NBITS) @@ -57,8 +48,6 @@ typedef unsigned long bitmap_t; /* * Maximum number of groups required to support LG_BITMAP_MAXBITS. */ -#ifdef USE_TREE - #if LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS # define BITMAP_GROUPS_MAX BITMAP_GROUPS_1_LEVEL(BITMAP_MAXBITS) #elif LG_BITMAP_MAXBITS <= LG_BITMAP_GROUP_NBITS * 2 @@ -76,12 +65,6 @@ typedef unsigned long bitmap_t; (LG_BITMAP_MAXBITS / LG_SIZEOF_BITMAP) \ + !!(LG_BITMAP_MAXBITS % LG_SIZEOF_BITMAP) -#else /* USE_TREE */ - -#define BITMAP_GROUPS_MAX BITMAP_BITS2GROUPS(BITMAP_MAXBITS) - -#endif /* USE_TREE */ - #endif /* JEMALLOC_H_TYPES */ /******************************************************************************/ #ifdef JEMALLOC_H_STRUCTS @@ -95,7 +78,6 @@ struct bitmap_info_s { /* Logical number of bits in bitmap (stored at bottom level). */ size_t nbits; -#ifdef USE_TREE /* Number of levels necessary for nbits. */ unsigned nlevels; @@ -104,10 +86,6 @@ struct bitmap_info_s { * bottom to top (e.g. the bottom level is stored in levels[0]). */ bitmap_level_t levels[BITMAP_MAX_LEVELS+1]; -#else /* USE_TREE */ - /* Number of groups necessary for nbits. */ - size_t ngroups; -#endif /* USE_TREE */ }; #endif /* JEMALLOC_H_STRUCTS */ @@ -115,8 +93,9 @@ struct bitmap_info_s { #ifdef JEMALLOC_H_EXTERNS void bitmap_info_init(bitmap_info_t *binfo, size_t nbits); +size_t bitmap_info_ngroups(const bitmap_info_t *binfo); +size_t bitmap_size(size_t nbits); void bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo); -size_t bitmap_size(const bitmap_info_t *binfo); #endif /* JEMALLOC_H_EXTERNS */ /******************************************************************************/ @@ -134,20 +113,10 @@ void bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit); JEMALLOC_INLINE bool bitmap_full(bitmap_t *bitmap, const bitmap_info_t *binfo) { -#ifdef USE_TREE - size_t rgoff = binfo->levels[binfo->nlevels].group_offset - 1; + unsigned rgoff = binfo->levels[binfo->nlevels].group_offset - 1; bitmap_t rg = bitmap[rgoff]; /* The bitmap is full iff the root group is 0. */ return (rg == 0); -#else - size_t i; - - for (i = 0; i < binfo->ngroups; i++) { - if (bitmap[i] != 0) - return (false); - } - return (true); -#endif } JEMALLOC_INLINE bool @@ -159,7 +128,7 @@ bitmap_get(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) assert(bit < binfo->nbits); goff = bit >> LG_BITMAP_GROUP_NBITS; g = bitmap[goff]; - return (!(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK)))); + return (!(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK)))); } JEMALLOC_INLINE void @@ -174,11 +143,10 @@ bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) goff = bit >> LG_BITMAP_GROUP_NBITS; gp = &bitmap[goff]; g = *gp; - assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))); - g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); + assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))); + g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); *gp = g; assert(bitmap_get(bitmap, binfo, bit)); -#ifdef USE_TREE /* Propagate group state transitions up the tree. */ if (g == 0) { unsigned i; @@ -187,14 +155,13 @@ bitmap_set(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) goff = bit >> LG_BITMAP_GROUP_NBITS; gp = &bitmap[binfo->levels[i].group_offset + goff]; g = *gp; - assert(g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))); - g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); + assert(g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))); + g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); *gp = g; if (g != 0) break; } } -#endif } /* sfu: set first unset. */ @@ -207,24 +174,15 @@ bitmap_sfu(bitmap_t *bitmap, const bitmap_info_t *binfo) assert(!bitmap_full(bitmap, binfo)); -#ifdef USE_TREE i = binfo->nlevels - 1; g = bitmap[binfo->levels[i].group_offset]; - bit = ffs_lu(g) - 1; + bit = jemalloc_ffsl(g) - 1; while (i > 0) { i--; g = bitmap[binfo->levels[i].group_offset + bit]; - bit = (bit << LG_BITMAP_GROUP_NBITS) + (ffs_lu(g) - 1); + bit = (bit << LG_BITMAP_GROUP_NBITS) + (jemalloc_ffsl(g) - 1); } -#else - i = 0; - g = bitmap[0]; - while ((bit = ffs_lu(g)) == 0) { - i++; - g = bitmap[i]; - } - bit = (i << LG_BITMAP_GROUP_NBITS) + (bit - 1); -#endif + bitmap_set(bitmap, binfo, bit); return (bit); } @@ -235,7 +193,7 @@ bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) size_t goff; bitmap_t *gp; bitmap_t g; - UNUSED bool propagate; + bool propagate; assert(bit < binfo->nbits); assert(bitmap_get(bitmap, binfo, bit)); @@ -243,11 +201,10 @@ bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) gp = &bitmap[goff]; g = *gp; propagate = (g == 0); - assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))) == 0); - g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); + assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))) == 0); + g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); *gp = g; assert(!bitmap_get(bitmap, binfo, bit)); -#ifdef USE_TREE /* Propagate group state transitions up the tree. */ if (propagate) { unsigned i; @@ -257,15 +214,14 @@ bitmap_unset(bitmap_t *bitmap, const bitmap_info_t *binfo, size_t bit) gp = &bitmap[binfo->levels[i].group_offset + goff]; g = *gp; propagate = (g == 0); - assert((g & (ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK))) + assert((g & (1LU << (bit & BITMAP_GROUP_NBITS_MASK))) == 0); - g ^= ZU(1) << (bit & BITMAP_GROUP_NBITS_MASK); + g ^= 1LU << (bit & BITMAP_GROUP_NBITS_MASK); *gp = g; if (!propagate) break; } } -#endif /* USE_TREE */ } #endif |