bird/lib/bitmap.c

198 lines
3.2 KiB
C
Raw Permalink Normal View History

/*
* BIRD Library -- Bitmaps
*
* (c) 2019 Ondrej Zajicek <santiago@crfreenet.org>
* (c) 2019 CZ.NIC z.s.p.o.
*
* Can be freely distributed and used under the terms of the GNU GPL.
*/
#include <stdlib.h>
#include "nest/bird.h"
#include "lib/bitmap.h"
#include "lib/bitops.h"
#include "lib/resource.h"
/*
* Basic bitmap
*/
void
bmap_init(struct bmap *b, pool *p, uint size)
{
b->size = BIRD_ALIGN(size, 4);
b->data = mb_allocz(p, b->size);
}
void
bmap_reset(struct bmap *b, uint size)
{
b->size = BIRD_ALIGN(size, 4);
memset(b->data, 0, b->size);
}
void
bmap_grow(struct bmap *b, uint need)
{
uint size = b->size * 2;
while (size < need)
size *= 2;
uint old_size = b->size;
b->size = size;
b->data = mb_realloc(b->data, b->size);
ASSERT(size >= old_size);
memset(b->data + (old_size / 4), 0, size - old_size);
}
void
bmap_free(struct bmap *b)
{
mb_free(b->data);
b->size = 0;
b->data = NULL;
}
/*
* Hierarchical bitmap
*/
#define B256_SIZE(b) BIRD_ALIGN(b, 32)
#define B256_STEP(b) (BIRD_ALIGN(b, 8192) >> 8)
void
hmap_init(struct hmap *b, pool *p, uint size)
{
b->size[0] = B256_SIZE(size);
b->size[1] = B256_STEP(b->size[0]);
b->size[2] = B256_STEP(b->size[1]);
b->size[3] = sizeof(b->root);
b->data[0] = mb_allocz(p, b->size[0]);
b->data[1] = mb_allocz(p, b->size[1]);
b->data[2] = mb_allocz(p, b->size[2]);
b->data[3] = b->root;
memset(b->root, 0, sizeof(b->root));
}
static void
hmap_grow(struct hmap *b, uint need)
{
uint size = b->size[0] * 2;
while (size < need)
size *= 2;
for (uint i = 0; i < 3; i++)
{
uint old_size = b->size[i];
b->size[i] = size;
b->data[i] = mb_realloc(b->data[i], b->size[i]);
ASSERT(size >= old_size);
memset(b->data[i] + (old_size / 4), 0, size - old_size);
size = B256_STEP(size);
}
}
void
hmap_free(struct hmap *b)
{
mb_free(b->data[0]);
mb_free(b->data[1]);
mb_free(b->data[2]);
memset(b, 0, sizeof(struct hmap));
}
static inline int
b256_and(u32 *p)
{
for (int i = 0; i < 8; i++)
if (~p[i])
return 0;
return 1;
}
void
hmap_set(struct hmap *b, uint n)
{
if (n >= hmap_max(b))
hmap_grow(b, n/8 + 1);
for (int i = 0; i < 4; i++)
{
BIT32_SET(b->data[i], n);
n = n >> 8;
/* Continue if all bits in 256-bit block are set */
if (! b256_and(b->data[i] + 8*n))
break;
}
}
void
hmap_clear(struct hmap *b, uint n)
{
if (n >= hmap_max(b))
return;
for (int i = 0; i < 4; i++)
{
BIT32_CLR(b->data[i], n);
n = n >> 8;
}
}
static inline int
b256_first_zero(u32 *p)
{
for (int i = 0; i < 8; i++)
if (~p[i])
return 32*i + u32_ctz(~p[i]);
return 256;
}
u32
hmap_first_zero(struct hmap *b)
{
u32 n = 0;
for (int i = 3; i >= 0; i--)
{
if (32*n >= b->size[i])
return hmap_max(b);
u32 *p = b->data[i] + 8*n;
n = (n << 8) + b256_first_zero(p);
}
return n;
}
void
hmap_check(struct hmap *b)
{
for (int i = 0; i < 2; i++)
{
int max = b->size[i] / 32;
for (int j = 0; j < max; j++)
{
int x = b256_and(b->data[i] + 8*j);
int y = !!BIT32_TEST(b->data[i+1], j);
if (x != y)
bug("Inconsistent data on %d:%d (%d vs %d)", i, j, x, y);
}
}
}