[qemu.git] / tests / test-hbitmap.c

/*
 * Hierarchical bitmap unit-tests.
 *
 * Copyright (C) 2012 Red Hat Inc.
 *
 * Author: Paolo Bonzini <[email protected]>
 *
 * This work is licensed under the terms of the GNU GPL, version 2 or later.
 * See the COPYING file in the top-level directory.
 */

#include <glib.h>
#include <stdarg.h>
#include "qemu/hbitmap.h"

#define LOG_BITS_PER_LONG          (BITS_PER_LONG == 32 ? 5 : 6)

#define L1                         BITS_PER_LONG
#define L2                         (BITS_PER_LONG * L1)
#define L3                         (BITS_PER_LONG * L2)

typedef struct TestHBitmapData {
    HBitmap       *hb;
    unsigned long *bits;
    size_t         size;
    int            granularity;
} TestHBitmapData;


/* Check that the HBitmap and the shadow bitmap contain the same data,
 * ignoring the same "first" bits.
 */
static void hbitmap_test_check(TestHBitmapData *data,
                               uint64_t first)
{
    uint64_t count = 0;
    size_t pos;
    int bit;
    HBitmapIter hbi;
    int64_t i, next;

    hbitmap_iter_init(&hbi, data->hb, first);

    i = first;
    for (;;) {
        next = hbitmap_iter_next(&hbi);
        if (next < 0) {
            next = data->size;
        }

        while (i < next) {
            pos = i >> LOG_BITS_PER_LONG;
            bit = i & (BITS_PER_LONG - 1);
            i++;
            g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
        }

        if (next == data->size) {
            break;
        }

        pos = i >> LOG_BITS_PER_LONG;
        bit = i & (BITS_PER_LONG - 1);
        i++;
        count++;
        g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
    }

    if (first == 0) {
        g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
    }
}

/* This is provided instead of a test setup function so that the sizes
   are kept in the test functions (and not in main()) */
static void hbitmap_test_init(TestHBitmapData *data,
                              uint64_t size, int granularity)
{
    size_t n;
    data->hb = hbitmap_alloc(size, granularity);

    n = (size + BITS_PER_LONG - 1) / BITS_PER_LONG;
    if (n == 0) {
        n = 1;
    }
    data->bits = g_new0(unsigned long, n);
    data->size = size;
    data->granularity = granularity;
    if (size) {
        hbitmap_test_check(data, 0);
    }
}

static void hbitmap_test_teardown(TestHBitmapData *data,
                                  const void *unused)
{
    if (data->hb) {
        hbitmap_free(data->hb);
        data->hb = NULL;
    }
    if (data->bits) {
        g_free(data->bits);
        data->bits = NULL;
    }
}

/* Set a range in the HBitmap and in the shadow "simple" bitmap.
 * The two bitmaps are then tested against each other.
 */
static void hbitmap_test_set(TestHBitmapData *data,
                             uint64_t first, uint64_t count)
{
    hbitmap_set(data->hb, first, count);
    while (count-- != 0) {
        size_t pos = first >> LOG_BITS_PER_LONG;
        int bit = first & (BITS_PER_LONG - 1);
        first++;

        data->bits[pos] |= 1UL << bit;
    }

    if (data->granularity == 0) {
        hbitmap_test_check(data, 0);
    }
}

/* Reset a range in the HBitmap and in the shadow "simple" bitmap.
 */
static void hbitmap_test_reset(TestHBitmapData *data,
                               uint64_t first, uint64_t count)
{
    hbitmap_reset(data->hb, first, count);
    while (count-- != 0) {
        size_t pos = first >> LOG_BITS_PER_LONG;
        int bit = first & (BITS_PER_LONG - 1);
        first++;

        data->bits[pos] &= ~(1UL << bit);
    }

    if (data->granularity == 0) {
        hbitmap_test_check(data, 0);
    }
}

static void hbitmap_test_check_get(TestHBitmapData *data)
{
    uint64_t count = 0;
    uint64_t i;

    for (i = 0; i < data->size; i++) {
        size_t pos = i >> LOG_BITS_PER_LONG;
        int bit = i & (BITS_PER_LONG - 1);
        unsigned long val = data->bits[pos] & (1UL << bit);
        count += hbitmap_get(data->hb, i);
        g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
    }
    g_assert_cmpint(count, ==, hbitmap_count(data->hb));
}

static void test_hbitmap_zero(TestHBitmapData *data,
                               const void *unused)
{
    hbitmap_test_init(data, 0, 0);
}

static void test_hbitmap_unaligned(TestHBitmapData *data,
                                   const void *unused)
{
    hbitmap_test_init(data, L3 + 23, 0);
    hbitmap_test_set(data, 0, 1);
    hbitmap_test_set(data, L3 + 22, 1);
}

static void test_hbitmap_iter_empty(TestHBitmapData *data,
                                    const void *unused)
{
    hbitmap_test_init(data, L1, 0);
}

static void test_hbitmap_iter_partial(TestHBitmapData *data,
                                      const void *unused)
{
    hbitmap_test_init(data, L3, 0);
    hbitmap_test_set(data, 0, L3);
    hbitmap_test_check(data, 1);
    hbitmap_test_check(data, L1 - 1);
    hbitmap_test_check(data, L1);
    hbitmap_test_check(data, L1 * 2 - 1);
    hbitmap_test_check(data, L2 - 1);
    hbitmap_test_check(data, L2);
    hbitmap_test_check(data, L2 + 1);
    hbitmap_test_check(data, L2 + L1);
    hbitmap_test_check(data, L2 + L1 * 2 - 1);
    hbitmap_test_check(data, L2 * 2 - 1);
    hbitmap_test_check(data, L2 * 2);
    hbitmap_test_check(data, L2 * 2 + 1);
    hbitmap_test_check(data, L2 * 2 + L1);
    hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1);
    hbitmap_test_check(data, L3 / 2);
}

static void test_hbitmap_set_all(TestHBitmapData *data,
                                 const void *unused)
{
    hbitmap_test_init(data, L3, 0);
    hbitmap_test_set(data, 0, L3);
}

static void test_hbitmap_get_all(TestHBitmapData *data,
                                 const void *unused)
{
    hbitmap_test_init(data, L3, 0);
    hbitmap_test_set(data, 0, L3);
    hbitmap_test_check_get(data);
}

static void test_hbitmap_get_some(TestHBitmapData *data,
                                  const void *unused)
{
    hbitmap_test_init(data, 2 * L2, 0);
    hbitmap_test_set(data, 10, 1);
    hbitmap_test_check_get(data);
    hbitmap_test_set(data, L1 - 1, 1);
    hbitmap_test_check_get(data);
    hbitmap_test_set(data, L1, 1);
    hbitmap_test_check_get(data);
    hbitmap_test_set(data, L2 - 1, 1);
    hbitmap_test_check_get(data);
    hbitmap_test_set(data, L2, 1);
    hbitmap_test_check_get(data);
}

static void test_hbitmap_set_one(TestHBitmapData *data,
                                 const void *unused)
{
    hbitmap_test_init(data, 2 * L2, 0);
    hbitmap_test_set(data, 10, 1);
    hbitmap_test_set(data, L1 - 1, 1);
    hbitmap_test_set(data, L1, 1);
    hbitmap_test_set(data, L2 - 1, 1);
    hbitmap_test_set(data, L2, 1);
}

static void test_hbitmap_set_two_elem(TestHBitmapData *data,
                                      const void *unused)
{
    hbitmap_test_init(data, 2 * L2, 0);
    hbitmap_test_set(data, L1 - 1, 2);
    hbitmap_test_set(data, L1 * 2 - 1, 4);
    hbitmap_test_set(data, L1 * 4, L1 + 1);
    hbitmap_test_set(data, L1 * 8 - 1, L1 + 1);
    hbitmap_test_set(data, L2 - 1, 2);
    hbitmap_test_set(data, L2 + L1 - 1, 8);
    hbitmap_test_set(data, L2 + L1 * 4, L1 + 1);
    hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1);
}

static void test_hbitmap_set(TestHBitmapData *data,
                             const void *unused)
{
    hbitmap_test_init(data, L3 * 2, 0);
    hbitmap_test_set(data, L1 - 1, L1 + 2);
    hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
    hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
    hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1);
    hbitmap_test_set(data, L2 - 1, L1 + 2);
    hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2);
    hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1);
    hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1);
    hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2);
}

static void test_hbitmap_set_twice(TestHBitmapData *data,
                                   const void *unused)
{
    hbitmap_test_init(data, L1 * 3, 0);
    hbitmap_test_set(data, 0, L1 * 3);
    hbitmap_test_set(data, L1, 1);
}

static void test_hbitmap_set_overlap(TestHBitmapData *data,
                                     const void *unused)
{
    hbitmap_test_init(data, L3 * 2, 0);
    hbitmap_test_set(data, L1 - 1, L1 + 2);
    hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
    hbitmap_test_set(data, 0, L1 * 3);
    hbitmap_test_set(data, L1 * 8 - 1, L2);
    hbitmap_test_set(data, L2, L1);
    hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2);
    hbitmap_test_set(data, L2, L3 - L2 + 1);
    hbitmap_test_set(data, L3 - L1, L1 * 3);
    hbitmap_test_set(data, L3 - 1, 3);
    hbitmap_test_set(data, L3 - 1, L2);
}

static void test_hbitmap_reset_empty(TestHBitmapData *data,
                                     const void *unused)
{
    hbitmap_test_init(data, L3, 0);
    hbitmap_test_reset(data, 0, L3);
}

static void test_hbitmap_reset(TestHBitmapData *data,
                               const void *unused)
{
    hbitmap_test_init(data, L3 * 2, 0);
    hbitmap_test_set(data, L1 - 1, L1 + 2);
    hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
    hbitmap_test_set(data, 0, L1 * 3);
    hbitmap_test_reset(data, L1 * 8 - 1, L2);
    hbitmap_test_set(data, L2, L1);
    hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2);
    hbitmap_test_set(data, L2, L3 - L2 + 1);
    hbitmap_test_reset(data, L3 - L1, L1 * 3);
    hbitmap_test_set(data, L3 - 1, 3);
    hbitmap_test_reset(data, L3 - 1, L2);
    hbitmap_test_set(data, 0, L3 * 2);
    hbitmap_test_reset(data, 0, L1);
    hbitmap_test_reset(data, 0, L2);
    hbitmap_test_reset(data, L3, L3);
    hbitmap_test_set(data, L3 / 2, L3);
}

static void test_hbitmap_granularity(TestHBitmapData *data,
                                     const void *unused)
{
    /* Note that hbitmap_test_check has to be invoked manually in this test.  */
    hbitmap_test_init(data, L1, 1);
    hbitmap_test_set(data, 0, 1);
    g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
    hbitmap_test_check(data, 0);
    hbitmap_test_set(data, 2, 1);
    g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
    hbitmap_test_check(data, 0);
    hbitmap_test_set(data, 0, 3);
    g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
    hbitmap_test_reset(data, 0, 1);
    g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
}

static void test_hbitmap_iter_granularity(TestHBitmapData *data,
                                          const void *unused)
{
    HBitmapIter hbi;

    /* Note that hbitmap_test_check has to be invoked manually in this test.  */
    hbitmap_test_init(data, 131072 << 7, 7);
    hbitmap_iter_init(&hbi, data->hb, 0);
    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);

    hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
    hbitmap_iter_init(&hbi, data->hb, 0);
    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);

    hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);

    hbitmap_test_set(data, (131072 << 7) - 8, 8);
    hbitmap_iter_init(&hbi, data->hb, 0);
    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);

    hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
    g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
}

static void hbitmap_test_add(const char *testpath,
                                   void (*test_func)(TestHBitmapData *data, const void *user_data))
{
    g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
               hbitmap_test_teardown);
}

int main(int argc, char **argv)
{
    g_test_init(&argc, &argv, NULL);
    hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
    hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
    hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
    hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
    hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
    hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
    hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
    hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
    hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
    hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
    hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
    hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
    hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
    hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
    hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
    hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
    g_test_run();

    return 0;
}
Commit	Line	Data
e7c033c3 PB	1	/*
	2	* Hierarchical bitmap unit-tests.
	3	*
	4	* Copyright (C) 2012 Red Hat Inc.
	5	*
	6	* Author: Paolo Bonzini <[email protected]>
	7	*
	8	* This work is licensed under the terms of the GNU GPL, version 2 or later.
	9	* See the COPYING file in the top-level directory.
	10	*/
	11
	12	#include <glib.h>
	13	#include <stdarg.h>
	14	#include "qemu/hbitmap.h"
	15
	16	#define LOG_BITS_PER_LONG (BITS_PER_LONG == 32 ? 5 : 6)
	17
	18	#define L1 BITS_PER_LONG
	19	#define L2 (BITS_PER_LONG * L1)
	20	#define L3 (BITS_PER_LONG * L2)
	21
	22	typedef struct TestHBitmapData {
	23	HBitmap *hb;
	24	unsigned long *bits;
	25	size_t size;
	26	int granularity;
	27	} TestHBitmapData;
	28
	29
	30	/* Check that the HBitmap and the shadow bitmap contain the same data,
	31	* ignoring the same "first" bits.
	32	*/
	33	static void hbitmap_test_check(TestHBitmapData *data,
	34	uint64_t first)
	35	{
	36	uint64_t count = 0;
	37	size_t pos;
	38	int bit;
	39	HBitmapIter hbi;
	40	int64_t i, next;
	41
	42	hbitmap_iter_init(&hbi, data->hb, first);
	43
	44	i = first;
	45	for (;;) {
	46	next = hbitmap_iter_next(&hbi);
	47	if (next < 0) {
	48	next = data->size;
	49	}
	50
	51	while (i < next) {
	52	pos = i >> LOG_BITS_PER_LONG;
	53	bit = i & (BITS_PER_LONG - 1);
	54	i++;
	55	g_assert_cmpint(data->bits[pos] & (1UL << bit), ==, 0);
	56	}
	57
	58	if (next == data->size) {
	59	break;
	60	}
	61
	62	pos = i >> LOG_BITS_PER_LONG;
	63	bit = i & (BITS_PER_LONG - 1);
	64	i++;
65	count++;
66	g_assert_cmpint(data->bits[pos] & (1UL << bit), !=, 0);
67	}
68
69	if (first == 0) {
70	g_assert_cmpint(count << data->granularity, ==, hbitmap_count(data->hb));
71	}
72	}
73
74	/* This is provided instead of a test setup function so that the sizes
75	are kept in the test functions (and not in main()) */
76	static void hbitmap_test_init(TestHBitmapData *data,
77	uint64_t size, int granularity)
78	{
79	size_t n;
80	data->hb = hbitmap_alloc(size, granularity);
81
82	n = (size + BITS_PER_LONG - 1) / BITS_PER_LONG;
83	if (n == 0) {
84	n = 1;
85	}
86	data->bits = g_new0(unsigned long, n);
87	data->size = size;
88	data->granularity = granularity;
1b095244 PB	89	if (size) {
	90	hbitmap_test_check(data, 0);
	91	}
e7c033c3 PB	92	}
	93
	94	static void hbitmap_test_teardown(TestHBitmapData *data,
	95	const void *unused)
	96	{
	97	if (data->hb) {
	98	hbitmap_free(data->hb);
	99	data->hb = NULL;
	100	}
	101	if (data->bits) {
	102	g_free(data->bits);
	103	data->bits = NULL;
	104	}
	105	}
	106
	107	/* Set a range in the HBitmap and in the shadow "simple" bitmap.
	108	* The two bitmaps are then tested against each other.
	109	*/
	110	static void hbitmap_test_set(TestHBitmapData *data,
	111	uint64_t first, uint64_t count)
	112	{
	113	hbitmap_set(data->hb, first, count);
	114	while (count-- != 0) {
	115	size_t pos = first >> LOG_BITS_PER_LONG;
	116	int bit = first & (BITS_PER_LONG - 1);
	117	first++;
	118
	119	data->bits[pos] \|= 1UL << bit;
	120	}
	121
	122	if (data->granularity == 0) {
	123	hbitmap_test_check(data, 0);
	124	}
	125	}
	126
	127	/* Reset a range in the HBitmap and in the shadow "simple" bitmap.
	128	*/
	129	static void hbitmap_test_reset(TestHBitmapData *data,
	130	uint64_t first, uint64_t count)
	131	{
	132	hbitmap_reset(data->hb, first, count);
	133	while (count-- != 0) {
	134	size_t pos = first >> LOG_BITS_PER_LONG;
	135	int bit = first & (BITS_PER_LONG - 1);
	136	first++;
	137
	138	data->bits[pos] &= ~(1UL << bit);
	139	}
	140
	141	if (data->granularity == 0) {
	142	hbitmap_test_check(data, 0);
	143	}
	144	}
	145
	146	static void hbitmap_test_check_get(TestHBitmapData *data)
	147	{
	148	uint64_t count = 0;
	149	uint64_t i;
	150
	151	for (i = 0; i < data->size; i++) {
	152	size_t pos = i >> LOG_BITS_PER_LONG;
	153	int bit = i & (BITS_PER_LONG - 1);
	154	unsigned long val = data->bits[pos] & (1UL << bit);
	155	count += hbitmap_get(data->hb, i);
156	g_assert_cmpint(hbitmap_get(data->hb, i), ==, val != 0);
157	}
158	g_assert_cmpint(count, ==, hbitmap_count(data->hb));
159	}
160
161	static void test_hbitmap_zero(TestHBitmapData *data,
162	const void *unused)
163	{
164	hbitmap_test_init(data, 0, 0);
165	}
166
167	static void test_hbitmap_unaligned(TestHBitmapData *data,
168	const void *unused)
169	{
170	hbitmap_test_init(data, L3 + 23, 0);
171	hbitmap_test_set(data, 0, 1);
172	hbitmap_test_set(data, L3 + 22, 1);
173	}
174
175	static void test_hbitmap_iter_empty(TestHBitmapData *data,
176	const void *unused)
177	{
178	hbitmap_test_init(data, L1, 0);
179	}
180
181	static void test_hbitmap_iter_partial(TestHBitmapData *data,
182	const void *unused)
183	{
184	hbitmap_test_init(data, L3, 0);
185	hbitmap_test_set(data, 0, L3);
186	hbitmap_test_check(data, 1);
187	hbitmap_test_check(data, L1 - 1);
188	hbitmap_test_check(data, L1);
189	hbitmap_test_check(data, L1 * 2 - 1);
190	hbitmap_test_check(data, L2 - 1);
191	hbitmap_test_check(data, L2);
192	hbitmap_test_check(data, L2 + 1);
193	hbitmap_test_check(data, L2 + L1);
194	hbitmap_test_check(data, L2 + L1 * 2 - 1);
195	hbitmap_test_check(data, L2 * 2 - 1);
196	hbitmap_test_check(data, L2 * 2);
197	hbitmap_test_check(data, L2 * 2 + 1);
198	hbitmap_test_check(data, L2 * 2 + L1);
199	hbitmap_test_check(data, L2 * 2 + L1 * 2 - 1);
200	hbitmap_test_check(data, L3 / 2);
201	}
202
e7c033c3 PB	203	static void test_hbitmap_set_all(TestHBitmapData *data,
	204	const void *unused)
	205	{
	206	hbitmap_test_init(data, L3, 0);
	207	hbitmap_test_set(data, 0, L3);
	208	}
	209
	210	static void test_hbitmap_get_all(TestHBitmapData *data,
	211	const void *unused)
	212	{
	213	hbitmap_test_init(data, L3, 0);
	214	hbitmap_test_set(data, 0, L3);
	215	hbitmap_test_check_get(data);
	216	}
	217
	218	static void test_hbitmap_get_some(TestHBitmapData *data,
	219	const void *unused)
	220	{
	221	hbitmap_test_init(data, 2 * L2, 0);
	222	hbitmap_test_set(data, 10, 1);
	223	hbitmap_test_check_get(data);
	224	hbitmap_test_set(data, L1 - 1, 1);
	225	hbitmap_test_check_get(data);
	226	hbitmap_test_set(data, L1, 1);
	227	hbitmap_test_check_get(data);
	228	hbitmap_test_set(data, L2 - 1, 1);
	229	hbitmap_test_check_get(data);
	230	hbitmap_test_set(data, L2, 1);
	231	hbitmap_test_check_get(data);
	232	}
	233
	234	static void test_hbitmap_set_one(TestHBitmapData *data,
	235	const void *unused)
	236	{
	237	hbitmap_test_init(data, 2 * L2, 0);
	238	hbitmap_test_set(data, 10, 1);
	239	hbitmap_test_set(data, L1 - 1, 1);
	240	hbitmap_test_set(data, L1, 1);
	241	hbitmap_test_set(data, L2 - 1, 1);
	242	hbitmap_test_set(data, L2, 1);
	243	}
	244
	245	static void test_hbitmap_set_two_elem(TestHBitmapData *data,
	246	const void *unused)
	247	{
	248	hbitmap_test_init(data, 2 * L2, 0);
	249	hbitmap_test_set(data, L1 - 1, 2);
	250	hbitmap_test_set(data, L1 * 2 - 1, 4);
	251	hbitmap_test_set(data, L1 * 4, L1 + 1);
	252	hbitmap_test_set(data, L1 * 8 - 1, L1 + 1);
	253	hbitmap_test_set(data, L2 - 1, 2);
	254	hbitmap_test_set(data, L2 + L1 - 1, 8);
	255	hbitmap_test_set(data, L2 + L1 * 4, L1 + 1);
	256	hbitmap_test_set(data, L2 + L1 * 8 - 1, L1 + 1);
	257	}
	258
	259	static void test_hbitmap_set(TestHBitmapData *data,
	260	const void *unused)
	261	{
	262	hbitmap_test_init(data, L3 * 2, 0);
	263	hbitmap_test_set(data, L1 - 1, L1 + 2);
	264	hbitmap_test_set(data, L1 * 3 - 1, L1 + 2);
	265	hbitmap_test_set(data, L1 * 5, L1 * 2 + 1);
	266	hbitmap_test_set(data, L1 * 8 - 1, L1 * 2 + 1);
267	hbitmap_test_set(data, L2 - 1, L1 + 2);
268	hbitmap_test_set(data, L2 + L1 * 2 - 1, L1 + 2);
269	hbitmap_test_set(data, L2 + L1 * 4, L1 * 2 + 1);
270	hbitmap_test_set(data, L2 + L1 * 7 - 1, L1 * 2 + 1);
271	hbitmap_test_set(data, L2 * 2 - 1, L3 * 2 - L2 * 2);
272	}
273
274	static void test_hbitmap_set_twice(TestHBitmapData *data,
275	const void *unused)
276	{
277	hbitmap_test_init(data, L1 * 3, 0);
278	hbitmap_test_set(data, 0, L1 * 3);
279	hbitmap_test_set(data, L1, 1);
280	}
281
282	static void test_hbitmap_set_overlap(TestHBitmapData *data,
283	const void *unused)
284	{
285	hbitmap_test_init(data, L3 * 2, 0);
286	hbitmap_test_set(data, L1 - 1, L1 + 2);
287	hbitmap_test_set(data, L1 * 2 - 1, L1 * 2 + 2);
288	hbitmap_test_set(data, 0, L1 * 3);
289	hbitmap_test_set(data, L1 * 8 - 1, L2);
290	hbitmap_test_set(data, L2, L1);
291	hbitmap_test_set(data, L2 - L1 - 1, L1 * 8 + 2);
292	hbitmap_test_set(data, L2, L3 - L2 + 1);
293	hbitmap_test_set(data, L3 - L1, L1 * 3);
294	hbitmap_test_set(data, L3 - 1, 3);
295	hbitmap_test_set(data, L3 - 1, L2);
296	}
297
298	static void test_hbitmap_reset_empty(TestHBitmapData *data,
299	const void *unused)
300	{
301	hbitmap_test_init(data, L3, 0);
302	hbitmap_test_reset(data, 0, L3);
303	}
304
305	static void test_hbitmap_reset(TestHBitmapData *data,
306	const void *unused)
307	{
308	hbitmap_test_init(data, L3 * 2, 0);
309	hbitmap_test_set(data, L1 - 1, L1 + 2);
310	hbitmap_test_reset(data, L1 * 2 - 1, L1 * 2 + 2);
311	hbitmap_test_set(data, 0, L1 * 3);
312	hbitmap_test_reset(data, L1 * 8 - 1, L2);
313	hbitmap_test_set(data, L2, L1);
314	hbitmap_test_reset(data, L2 - L1 - 1, L1 * 8 + 2);
315	hbitmap_test_set(data, L2, L3 - L2 + 1);
316	hbitmap_test_reset(data, L3 - L1, L1 * 3);
317	hbitmap_test_set(data, L3 - 1, 3);
318	hbitmap_test_reset(data, L3 - 1, L2);
319	hbitmap_test_set(data, 0, L3 * 2);
320	hbitmap_test_reset(data, 0, L1);
321	hbitmap_test_reset(data, 0, L2);
322	hbitmap_test_reset(data, L3, L3);
323	hbitmap_test_set(data, L3 / 2, L3);
324	}
325
326	static void test_hbitmap_granularity(TestHBitmapData *data,
327	const void *unused)
328	{
329	/* Note that hbitmap_test_check has to be invoked manually in this test. */
330	hbitmap_test_init(data, L1, 1);
331	hbitmap_test_set(data, 0, 1);
332	g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
333	hbitmap_test_check(data, 0);
334	hbitmap_test_set(data, 2, 1);
335	g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
336	hbitmap_test_check(data, 0);
337	hbitmap_test_set(data, 0, 3);
338	g_assert_cmpint(hbitmap_count(data->hb), ==, 4);
339	hbitmap_test_reset(data, 0, 1);
340	g_assert_cmpint(hbitmap_count(data->hb), ==, 2);
341	}
342
343	static void test_hbitmap_iter_granularity(TestHBitmapData *data,
344	const void *unused)
345	{
346	HBitmapIter hbi;
347
348	/* Note that hbitmap_test_check has to be invoked manually in this test. */
349	hbitmap_test_init(data, 131072 << 7, 7);
350	hbitmap_iter_init(&hbi, data->hb, 0);
351	g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
352
353	hbitmap_test_set(data, ((L2 + L1 + 1) << 7) + 8, 8);
354	hbitmap_iter_init(&hbi, data->hb, 0);
355	g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
356	g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
357
358	hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
359	g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
360
361	hbitmap_test_set(data, (131072 << 7) - 8, 8);
362	hbitmap_iter_init(&hbi, data->hb, 0);
363	g_assert_cmpint(hbitmap_iter_next(&hbi), ==, (L2 + L1 + 1) << 7);
364	g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
365	g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
366
367	hbitmap_iter_init(&hbi, data->hb, (L2 + L1 + 2) << 7);
368	g_assert_cmpint(hbitmap_iter_next(&hbi), ==, 131071 << 7);
369	g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
370	}
371
372	static void hbitmap_test_add(const char *testpath,
373	void (test_func)(TestHBitmapData data, const void *user_data))
374	{
375	g_test_add(testpath, TestHBitmapData, NULL, NULL, test_func,
376	hbitmap_test_teardown);
377	}
378
379	int main(int argc, char **argv)
380	{
381	g_test_init(&argc, &argv, NULL);
382	hbitmap_test_add("/hbitmap/size/0", test_hbitmap_zero);
383	hbitmap_test_add("/hbitmap/size/unaligned", test_hbitmap_unaligned);
384	hbitmap_test_add("/hbitmap/iter/empty", test_hbitmap_iter_empty);
e7c033c3 PB	385	hbitmap_test_add("/hbitmap/iter/partial", test_hbitmap_iter_partial);
	386	hbitmap_test_add("/hbitmap/iter/granularity", test_hbitmap_iter_granularity);
	387	hbitmap_test_add("/hbitmap/get/all", test_hbitmap_get_all);
	388	hbitmap_test_add("/hbitmap/get/some", test_hbitmap_get_some);
	389	hbitmap_test_add("/hbitmap/set/all", test_hbitmap_set_all);
	390	hbitmap_test_add("/hbitmap/set/one", test_hbitmap_set_one);
	391	hbitmap_test_add("/hbitmap/set/two-elem", test_hbitmap_set_two_elem);
	392	hbitmap_test_add("/hbitmap/set/general", test_hbitmap_set);
	393	hbitmap_test_add("/hbitmap/set/twice", test_hbitmap_set_twice);
	394	hbitmap_test_add("/hbitmap/set/overlap", test_hbitmap_set_overlap);
	395	hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
	396	hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
	397	hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
	398	g_test_run();
	399
	400	return 0;
	401	}