Merge pull request #496 from pietern/2.6-makeinstall

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

#define	JEMALLOC_MANGLE
#include "jemalloc_test.h"

/*
 * Avoid using the assert() from jemalloc_internal.h, since it requires
 * internal libjemalloc functionality.
 * */
#include <assert.h>

/*
 * Directly include the bitmap code, since it isn't exposed outside
 * libjemalloc.
 */
#include "../src/bitmap.c"

#if (LG_BITMAP_MAXBITS > 12)
#  define MAXBITS	4500
#else
#  define MAXBITS	(1U << LG_BITMAP_MAXBITS)
#endif

static void
test_bitmap_size(void)
{
	size_t i, prev_size;

	prev_size = 0;
	for (i = 1; i <= MAXBITS; i++) {
		size_t size = bitmap_size(i);
		assert(size >= prev_size);
		prev_size = size;
	}
}

static void
test_bitmap_init(void)
{
	size_t i;

	for (i = 1; i <= MAXBITS; i++) {
		bitmap_info_t binfo;
		bitmap_info_init(&binfo, i);
		{
			size_t j;
			bitmap_t bitmap[bitmap_info_ngroups(&binfo)];
			bitmap_init(bitmap, &binfo);

			for (j = 0; j < i; j++)
				assert(bitmap_get(bitmap, &binfo, j) == false);

		}
	}
}

static void
test_bitmap_set(void)
{
	size_t i;

	for (i = 1; i <= MAXBITS; i++) {
		bitmap_info_t binfo;
		bitmap_info_init(&binfo, i);
		{
			size_t j;
			bitmap_t bitmap[bitmap_info_ngroups(&binfo)];
			bitmap_init(bitmap, &binfo);

			for (j = 0; j < i; j++)
				bitmap_set(bitmap, &binfo, j);
			assert(bitmap_full(bitmap, &binfo));
		}
	}
}

static void
test_bitmap_unset(void)
{
	size_t i;

	for (i = 1; i <= MAXBITS; i++) {
		bitmap_info_t binfo;
		bitmap_info_init(&binfo, i);
		{
			size_t j;
			bitmap_t bitmap[bitmap_info_ngroups(&binfo)];
			bitmap_init(bitmap, &binfo);

			for (j = 0; j < i; j++)
				bitmap_set(bitmap, &binfo, j);
			assert(bitmap_full(bitmap, &binfo));
			for (j = 0; j < i; j++)
				bitmap_unset(bitmap, &binfo, j);
			for (j = 0; j < i; j++)
				bitmap_set(bitmap, &binfo, j);
			assert(bitmap_full(bitmap, &binfo));
		}
	}
}

static void
test_bitmap_sfu(void)
{
	size_t i;

	for (i = 1; i <= MAXBITS; i++) {
		bitmap_info_t binfo;
		bitmap_info_init(&binfo, i);
		{
			ssize_t j;
			bitmap_t bitmap[bitmap_info_ngroups(&binfo)];
			bitmap_init(bitmap, &binfo);

			/* Iteratively set bits starting at the beginning. */
			for (j = 0; j < i; j++)
				assert(bitmap_sfu(bitmap, &binfo) == j);
			assert(bitmap_full(bitmap, &binfo));

			/*
			 * Iteratively unset bits starting at the end, and
			 * verify that bitmap_sfu() reaches the unset bits.
			 */
			for (j = i - 1; j >= 0; j--) {
				bitmap_unset(bitmap, &binfo, j);
				assert(bitmap_sfu(bitmap, &binfo) == j);
				bitmap_unset(bitmap, &binfo, j);
			}
			assert(bitmap_get(bitmap, &binfo, 0) == false);

			/*
			 * Iteratively set bits starting at the beginning, and
			 * verify that bitmap_sfu() looks past them.
			 */
			for (j = 1; j < i; j++) {
				bitmap_set(bitmap, &binfo, j - 1);
				assert(bitmap_sfu(bitmap, &binfo) == j);
				bitmap_unset(bitmap, &binfo, j);
			}
			assert(bitmap_sfu(bitmap, &binfo) == i - 1);
			assert(bitmap_full(bitmap, &binfo));
		}
	}
}

int
main(void)
{
	fprintf(stderr, "Test begin\n");

	test_bitmap_size();
	test_bitmap_init();
	test_bitmap_set();
	test_bitmap_unset();
	test_bitmap_sfu();

	fprintf(stderr, "Test end\n");
	return (0);
}