jemalloc source added

[redis.git] / deps / jemalloc / src / bitmap.c

diff --git a/deps/jemalloc/src/bitmap.c b/deps/jemalloc/src/bitmap.c
new file mode 100644 (file)
index 0000000..b47e262
--- /dev/null
+++ b/deps/jemalloc/src/bitmap.c
@@ -0,0 +1,90 @@
+#define JEMALLOC_BITMAP_C_
+#include "jemalloc/internal/jemalloc_internal.h"
+
+/******************************************************************************/
+/* Function prototypes for non-inline static functions. */
+
+static size_t  bits2groups(size_t nbits);
+
+/******************************************************************************/
+
+static size_t
+bits2groups(size_t nbits)
+{
+
+       return ((nbits >> LG_BITMAP_GROUP_NBITS) +
+           !!(nbits & BITMAP_GROUP_NBITS_MASK));
+}
+
+void
+bitmap_info_init(bitmap_info_t *binfo, size_t nbits)
+{
+       unsigned i;
+       size_t group_count;
+
+       assert(nbits > 0);
+       assert(nbits <= (ZU(1) << LG_BITMAP_MAXBITS));
+
+       /*
+        * Compute the number of groups necessary to store nbits bits, and
+        * progressively work upward through the levels until reaching a level
+        * that requires only one group.
+        */
+       binfo->levels[0].group_offset = 0;
+       group_count = bits2groups(nbits);
+       for (i = 1; group_count > 1; i++) {
+               assert(i < BITMAP_MAX_LEVELS);
+               binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
+                   + group_count;
+               group_count = bits2groups(group_count);
+       }
+       binfo->levels[i].group_offset = binfo->levels[i-1].group_offset
+           + group_count;
+       binfo->nlevels = i;
+       binfo->nbits = nbits;
+}
+
+size_t
+bitmap_info_ngroups(const bitmap_info_t *binfo)
+{
+
+       return (binfo->levels[binfo->nlevels].group_offset << LG_SIZEOF_BITMAP);
+}
+
+size_t
+bitmap_size(size_t nbits)
+{
+       bitmap_info_t binfo;
+
+       bitmap_info_init(&binfo, nbits);
+       return (bitmap_info_ngroups(&binfo));
+}
+
+void
+bitmap_init(bitmap_t *bitmap, const bitmap_info_t *binfo)
+{
+       size_t extra;
+       unsigned i;
+
+       /*
+        * Bits are actually inverted with regard to the external bitmap
+        * interface, so the bitmap starts out with all 1 bits, except for
+        * trailing unused bits (if any).  Note that each group uses bit 0 to
+        * correspond to the first logical bit in the group, so extra bits
+        * are the most significant bits of the last group.
+        */
+       memset(bitmap, 0xffU, binfo->levels[binfo->nlevels].group_offset <<
+           LG_SIZEOF_BITMAP);
+       extra = (BITMAP_GROUP_NBITS - (binfo->nbits & BITMAP_GROUP_NBITS_MASK))
+           & BITMAP_GROUP_NBITS_MASK;
+       if (extra != 0)
+               bitmap[binfo->levels[1].group_offset - 1] >>= extra;
+       for (i = 1; i < binfo->nlevels; i++) {
+               size_t group_count = binfo->levels[i].group_offset -
+                   binfo->levels[i-1].group_offset;
+               extra = (BITMAP_GROUP_NBITS - (group_count &
+                   BITMAP_GROUP_NBITS_MASK)) & BITMAP_GROUP_NBITS_MASK;
+               if (extra != 0)
+                       bitmap[binfo->levels[i+1].group_offset - 1] >>= extra;
+       }
+}