[mirror_frr.git] / lib / bitfield.h

// SPDX-License-Identifier: GPL-2.0-or-later
/* Bitfields
 * Copyright (C) 2016 Cumulus Networks, Inc.
 */
/**
 * A simple bit array implementation to allocate and free IDs. An example
 * of its usage is in allocating link state IDs for OSPFv3 as OSPFv3 has
 * removed all address semantics from LS ID. Another usage can be in
 * allocating IDs for BGP neighbors (and dynamic update groups) for
 * efficient storage of adj-rib-out.
 *
 * An example:
 * #include "bitfield.h"
 *
 * bitfield_t bitfield;
 *
 * bf_init(bitfield, 32);
 * ...
 * bf_assign_index(bitfield, id1);
 * bf_assign_index(bitfield, id2);
 * ...
 * bf_release_index(bitfield, id1);
 */

#ifndef _BITFIELD_H
#define _BITFIELD_H

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#ifdef __cplusplus
extern "C" {
#endif

typedef unsigned int word_t;
#define WORD_MAX 0xFFFFFFFF
#define WORD_SIZE (sizeof(word_t) * 8)

/**
 * The bitfield structure.
 * @data: the bits to manage.
 * @n: The current word number that is being used.
 * @m: total number of words in 'data'
 */
typedef struct {word_t *data; size_t n, m; } bitfield_t;

DECLARE_MTYPE(BITFIELD);

/**
 * Initialize the bits.
 * @v: an instance of bitfield_t struct.
 * @N: number of bits to start with, which equates to how many
 *     IDs can be allocated.
 */
#define bf_init(v, N)                                                          \
	do {                                                                   \
		(v).n = 0;                                                     \
		(v).m = ((N) / WORD_SIZE + 1);                                 \
		(v).data = (word_t *)XCALLOC(MTYPE_BITFIELD,                   \
					     ((v).m * sizeof(word_t)));        \
	} while (0)

/**
 * allocate and assign an id from bitfield v.
 */
#define bf_assign_index(v, id)                                                 \
	do {                                                                   \
		bf_find_bit(v, id);                                            \
		bf_set_bit(v, id);                                             \
	} while (0)

/*
 * allocate and assign 0th bit in the bitfiled.
 */
#define bf_assign_zero_index(v)                                                \
	do {                                                                   \
		int id = 0;                                                    \
		bf_assign_index(v, id);                                        \
	} while (0)

/*
 * return an id to bitfield v
 */
#define bf_release_index(v, id)                                                \
	(v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))

/* check if an id is in use */
#define bf_test_index(v, id)                                                \
	((v).data[bf_index(id)] & (1 << (bf_offset(id))))

/* check if the bit field has been setup */
#define bf_is_inited(v) ((v).data)

/* compare two bitmaps of the same length */
#define bf_cmp(v1, v2) (memcmp((v1).data, (v2).data, ((v1).m * sizeof(word_t))))

/*
 * return 0th index back to bitfield
 */
#define bf_release_zero_index(v) bf_release_index(v, 0)

#define bf_index(b) ((b) / WORD_SIZE)
#define bf_offset(b) ((b) % WORD_SIZE)

/**
 * Set a bit in the array. If it fills up that word and we are
 * out of words, extend it by one more word.
 */
#define bf_set_bit(v, b)                                                       \
	do {                                                                   \
		size_t w = bf_index(b);                                        \
		(v).data[w] |= 1 << (bf_offset(b));                            \
		(v).n += ((v).data[w] == WORD_MAX);                            \
		if ((v).n == (v).m) {                                          \
			(v).m = (v).m + 1;                                     \
			(v).data = realloc((v).data, (v).m * sizeof(word_t));  \
		}                                                              \
	} while (0)

/* Find a clear bit in v and assign it to b. */
#define bf_find_bit(v, b)                                                      \
	do {                                                                   \
		word_t word = 0;                                               \
		unsigned int w, sh;                                            \
		for (w = 0; w <= (v).n; w++) {                                 \
			if ((word = (v).data[w]) != WORD_MAX)                  \
				break;                                         \
		}                                                              \
		(b) = ((word & 0xFFFF) == 0xFFFF) << 4;                        \
		word >>= (b);                                                  \
		sh = ((word & 0xFF) == 0xFF) << 3;                             \
		word >>= sh;                                                   \
		(b) |= sh;                                                     \
		sh = ((word & 0xF) == 0xF) << 2;                               \
		word >>= sh;                                                   \
		(b) |= sh;                                                     \
		sh = ((word & 0x3) == 0x3) << 1;                               \
		word >>= sh;                                                   \
		(b) |= sh;                                                     \
		sh = ((word & 0x1) == 0x1) << 0;                               \
		word >>= sh;                                                   \
		(b) |= sh;                                                     \
		(b) += (w * WORD_SIZE);                                        \
	} while (0)

/*
 * Find a clear bit in v and return it
 * Start looking in the word containing bit position start_index.
 * If necessary, wrap around after bit position max_index.
 */
static inline unsigned int
bf_find_next_clear_bit_wrap(bitfield_t *v, word_t start_index, word_t max_index)
{
	int start_bit;
	unsigned long i, offset, scanbits, wordcount_max, index_max;

	if (start_index > max_index)
		start_index = 0;

	start_bit = start_index & (WORD_SIZE - 1);
	wordcount_max = bf_index(max_index) + 1;

	scanbits = WORD_SIZE;
	for (i = bf_index(start_index); i < v->m; ++i) {
		if (v->data[i] == WORD_MAX) {
			/* if the whole word is full move to the next */
			start_bit = 0;
			continue;
		}
		/* scan one word for clear bits */
		if ((i == v->m - 1) && (v->m >= wordcount_max))
			/* max index could be only part of word */
			scanbits = (max_index % WORD_SIZE) + 1;
		for (offset = start_bit; offset < scanbits; ++offset) {
			if (!((v->data[i] >> offset) & 1))
				return ((i * WORD_SIZE) + offset);
		}
		/* move to the next word */
		start_bit = 0;
	}

	if (v->m < wordcount_max) {
		/*
		 * We can expand bitfield, so no need to wrap.
		 * Return the index of the first bit of the next word.
		 * Assumption is that caller will call bf_set_bit which
		 * will allocate additional space.
		 */
		v->m += 1;
		v->data = (word_t *)realloc(v->data, v->m * sizeof(word_t));
		v->data[v->m - 1] = 0;
		return v->m * WORD_SIZE;
	}

	/*
	 * start looking for a clear bit at the start of the bitfield and
	 * stop when we reach start_index
	 */
	scanbits = WORD_SIZE;
	index_max = bf_index(start_index - 1);
	for (i = 0; i <= index_max; ++i) {
		if (i == index_max)
			scanbits = ((start_index - 1) % WORD_SIZE) + 1;
		for (offset = start_bit; offset < scanbits; ++offset) {
			if (!((v->data[i] >> offset) & 1))
				return ((i * WORD_SIZE) + offset);
		}
		/* move to the next word */
		start_bit = 0;
	}

	return WORD_MAX;
}

static inline unsigned int bf_find_next_set_bit(bitfield_t v,
		word_t start_index)
{
	int start_bit;
	unsigned long i, offset;

	start_bit = start_index & (WORD_SIZE - 1);

	for (i = bf_index(start_index); i < v.m; ++i) {
		if (v.data[i] == 0) {
			/* if the whole word is empty move to the next */
			start_bit = 0;
			continue;
		}
		/* scan one word for set bits */
		for (offset = start_bit; offset < WORD_SIZE; ++offset) {
			if ((v.data[i] >> offset) & 1)
				return ((i * WORD_SIZE) + offset);
		}
		/* move to the next word */
		start_bit = 0;
	}
	return WORD_MAX;
}

/* iterate through all the set bits */
#define bf_for_each_set_bit(v, b, max)                 \
	for ((b) = bf_find_next_set_bit((v), 0);           \
			(b) < max;                                 \
			(b) = bf_find_next_set_bit((v), (b) + 1))

/*
 * Free the allocated memory for data
 * @v: an instance of bitfield_t struct.
 */
#define bf_free(v)                                                             \
	do {                                                                   \
		XFREE(MTYPE_BITFIELD, (v).data);                               \
		(v).data = NULL;                                               \
	} while (0)

static inline bitfield_t bf_copy(bitfield_t src)
{
	bitfield_t dst;

	assert(bf_is_inited(src));
	bf_init(dst, WORD_SIZE * (src.m - 1));
	for (size_t i = 0; i < src.m; i++)
		dst.data[i] = src.data[i];
	dst.n = src.n;
	return dst;
}


#ifdef __cplusplus
}
#endif

#endif
Commit	Line	Data
acddc0ed	1	// SPDX-License-Identifier: GPL-2.0-or-later
50e24903 DS	2	/* Bitfields
50e24903 DS	3	* Copyright (C) 2016 Cumulus Networks, Inc.
50e24903	4	*/
c3c0ac83 DS	5	/**
	6	* A simple bit array implementation to allocate and free IDs. An example
	7	* of its usage is in allocating link state IDs for OSPFv3 as OSPFv3 has
	8	* removed all address semantics from LS ID. Another usage can be in
	9	* allocating IDs for BGP neighbors (and dynamic update groups) for
	10	* efficient storage of adj-rib-out.
	11	*
	12	* An example:
	13	* #include "bitfield.h"
	14	*
	15	* bitfield_t bitfield;
	16	*
	17	* bf_init(bitfield, 32);
	18	* ...
	19	* bf_assign_index(bitfield, id1);
	20	* bf_assign_index(bitfield, id2);
	21	* ...
	22	* bf_release_index(bitfield, id1);
	23	*/
	24
	25	#ifndef _BITFIELD_H
	26	#define _BITFIELD_H
	27
	28	#include <stdio.h>
	29	#include <string.h>
	30	#include <stdlib.h>
	31
5e244469 RW	32	#ifdef __cplusplus
	33	extern "C" {
	34	#endif
	35
c3c0ac83 DS	36	typedef unsigned int word_t;
	37	#define WORD_MAX 0xFFFFFFFF
	38	#define WORD_SIZE (sizeof(word_t) * 8)
	39
	40	/**
	41	* The bitfield structure.
	42	* @data: the bits to manage.
	43	* @n: The current word number that is being used.
	44	* @m: total number of words in 'data'
	45	*/
89fbf168	46	typedef struct {word_t *data; size_t n, m; } bitfield_t;
c3c0ac83	47
0e2deb58 PR	48	DECLARE_MTYPE(BITFIELD);
0e2deb58 PR	49
c3c0ac83 DS	50	/**
	51	* Initialize the bits.
	52	* @v: an instance of bitfield_t struct.
	53	* @N: number of bits to start with, which equates to how many
	54	* IDs can be allocated.
	55	*/
d62a17ae	56	#define bf_init(v, N) \
	57	do { \
	58	(v).n = 0; \
	59	(v).m = ((N) / WORD_SIZE + 1); \
c86a3252 HS	60	(v).data = (word_t *)XCALLOC(MTYPE_BITFIELD, \
c86a3252 HS	61	((v).m * sizeof(word_t))); \
d62a17ae	62	} while (0)
c3c0ac83 DS	63
	64	/**
	65	* allocate and assign an id from bitfield v.
	66	*/
d62a17ae	67	#define bf_assign_index(v, id) \
	68	do { \
	69	bf_find_bit(v, id); \
	70	bf_set_bit(v, id); \
	71	} while (0)
c3c0ac83	72
4e9da201	73	/*
	74	* allocate and assign 0th bit in the bitfiled.
	75	*/
d62a17ae	76	#define bf_assign_zero_index(v) \
	77	do { \
	78	int id = 0; \
	79	bf_assign_index(v, id); \
	80	} while (0)
4e9da201	81
4e9da201	82	/*
c3c0ac83 DS	83	* return an id to bitfield v
c3c0ac83 DS	84	*/
d62a17ae	85	#define bf_release_index(v, id) \
d62a17ae	86	(v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
c3c0ac83	87
89fbf168 AK	88	/* check if an id is in use */
	89	#define bf_test_index(v, id) \
	90	((v).data[bf_index(id)] & (1 << (bf_offset(id))))
	91
	92	/* check if the bit field has been setup */
	93	#define bf_is_inited(v) ((v).data)
	94
	95	/* compare two bitmaps of the same length */
	96	#define bf_cmp(v1, v2) (memcmp((v1).data, (v2).data, ((v1).m * sizeof(word_t))))
	97
4e9da201	98	/*
	99	* return 0th index back to bitfield
	100	*/
d62a17ae	101	#define bf_release_zero_index(v) bf_release_index(v, 0)
4e9da201	102
c3c0ac83 DS	103	#define bf_index(b) ((b) / WORD_SIZE)
	104	#define bf_offset(b) ((b) % WORD_SIZE)
	105
	106	/**
	107	* Set a bit in the array. If it fills up that word and we are
	108	* out of words, extend it by one more word.
	109	*/
d62a17ae	110	#define bf_set_bit(v, b) \
	111	do { \
	112	size_t w = bf_index(b); \
	113	(v).data[w] \|= 1 << (bf_offset(b)); \
	114	(v).n += ((v).data[w] == WORD_MAX); \
	115	if ((v).n == (v).m) { \
	116	(v).m = (v).m + 1; \
	117	(v).data = realloc((v).data, (v).m * sizeof(word_t)); \
	118	} \
	119	} while (0)
c3c0ac83 DS	120
c3c0ac83 DS	121	/* Find a clear bit in v and assign it to b. */
d62a17ae	122	#define bf_find_bit(v, b) \
	123	do { \
	124	word_t word = 0; \
	125	unsigned int w, sh; \
	126	for (w = 0; w <= (v).n; w++) { \
	127	if ((word = (v).data[w]) != WORD_MAX) \
	128	break; \
	129	} \
	130	(b) = ((word & 0xFFFF) == 0xFFFF) << 4; \
	131	word >>= (b); \
	132	sh = ((word & 0xFF) == 0xFF) << 3; \
	133	word >>= sh; \
	134	(b) \|= sh; \
	135	sh = ((word & 0xF) == 0xF) << 2; \
	136	word >>= sh; \
	137	(b) \|= sh; \
	138	sh = ((word & 0x3) == 0x3) << 1; \
	139	word >>= sh; \
	140	(b) \|= sh; \
	141	sh = ((word & 0x1) == 0x1) << 0; \
	142	word >>= sh; \
	143	(b) \|= sh; \
	144	(b) += (w * WORD_SIZE); \
	145	} while (0)
c3c0ac83	146
80853c2e PZ	147	/*
	148	* Find a clear bit in v and return it
	149	* Start looking in the word containing bit position start_index.
	150	* If necessary, wrap around after bit position max_index.
	151	*/
	152	static inline unsigned int
	153	bf_find_next_clear_bit_wrap(bitfield_t *v, word_t start_index, word_t max_index)
	154	{
	155	int start_bit;
	156	unsigned long i, offset, scanbits, wordcount_max, index_max;
	157
	158	if (start_index > max_index)
	159	start_index = 0;
	160
	161	start_bit = start_index & (WORD_SIZE - 1);
	162	wordcount_max = bf_index(max_index) + 1;
	163
	164	scanbits = WORD_SIZE;
	165	for (i = bf_index(start_index); i < v->m; ++i) {
	166	if (v->data[i] == WORD_MAX) {
	167	/* if the whole word is full move to the next */
	168	start_bit = 0;
	169	continue;
	170	}
	171	/* scan one word for clear bits */
	172	if ((i == v->m - 1) && (v->m >= wordcount_max))
	173	/* max index could be only part of word */
	174	scanbits = (max_index % WORD_SIZE) + 1;
	175	for (offset = start_bit; offset < scanbits; ++offset) {
	176	if (!((v->data[i] >> offset) & 1))
	177	return ((i * WORD_SIZE) + offset);
	178	}
	179	/* move to the next word */
	180	start_bit = 0;
	181	}
	182
	183	if (v->m < wordcount_max) {
	184	/*
	185	* We can expand bitfield, so no need to wrap.
	186	* Return the index of the first bit of the next word.
	187	* Assumption is that caller will call bf_set_bit which
	188	* will allocate additional space.
	189	*/
	190	v->m += 1;
	191	v->data = (word_t )realloc(v->data, v->m sizeof(word_t));
	192	v->data[v->m - 1] = 0;
	193	return v->m * WORD_SIZE;
	194	}
	195
	196	/*
	197	* start looking for a clear bit at the start of the bitfield and
	198	* stop when we reach start_index
	199	*/
	200	scanbits = WORD_SIZE;
	201	index_max = bf_index(start_index - 1);
	202	for (i = 0; i <= index_max; ++i) {
	203	if (i == index_max)
	204	scanbits = ((start_index - 1) % WORD_SIZE) + 1;
	205	for (offset = start_bit; offset < scanbits; ++offset) {
	206	if (!((v->data[i] >> offset) & 1))
	207	return ((i * WORD_SIZE) + offset);
	208	}
	209	/* move to the next word */
	210	start_bit = 0;
211	}
212
213	return WORD_MAX;
214	}
215
89fbf168 AK	216	static inline unsigned int bf_find_next_set_bit(bitfield_t v,
	217	word_t start_index)
	218	{
	219	int start_bit;
	220	unsigned long i, offset;
	221
	222	start_bit = start_index & (WORD_SIZE - 1);
	223
	224	for (i = bf_index(start_index); i < v.m; ++i) {
	225	if (v.data[i] == 0) {
	226	/* if the whole word is empty move to the next */
	227	start_bit = 0;
	228	continue;
	229	}
	230	/* scan one word for set bits */
	231	for (offset = start_bit; offset < WORD_SIZE; ++offset) {
	232	if ((v.data[i] >> offset) & 1)
	233	return ((i * WORD_SIZE) + offset);
	234	}
	235	/* move to the next word */
	236	start_bit = 0;
	237	}
	238	return WORD_MAX;
	239	}
	240
	241	/* iterate through all the set bits */
	242	#define bf_for_each_set_bit(v, b, max) \
	243	for ((b) = bf_find_next_set_bit((v), 0); \
	244	(b) < max; \
	245	(b) = bf_find_next_set_bit((v), (b) + 1))
	246
4e9da201	247	/*
	248	* Free the allocated memory for data
	249	* @v: an instance of bitfield_t struct.
	250	*/
d62a17ae	251	#define bf_free(v) \
d62a17ae	252	do { \
0e2deb58	253	XFREE(MTYPE_BITFIELD, (v).data); \
1ac10b15	254	(v).data = NULL; \
d62a17ae	255	} while (0)
4e9da201	256
c86a3252 HS	257	static inline bitfield_t bf_copy(bitfield_t src)
	258	{
	259	bitfield_t dst;
	260
	261	assert(bf_is_inited(src));
	262	bf_init(dst, WORD_SIZE * (src.m - 1));
	263	for (size_t i = 0; i < src.m; i++)
	264	dst.data[i] = src.data[i];
	265	dst.n = src.n;
	266	return dst;
	267	}
	268
	269
5e244469 RW	270	#ifdef __cplusplus
	271	}
	272	#endif
	273
c3c0ac83	274	#endif