[mirror_frr.git] / lib / bitfield.h

/* Bitfields
 * Copyright (C) 2016 Cumulus Networks, Inc.
 *
 * This file is part of Quagga.
 *
 * Quagga is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2, or (at your option) any
 * later version.
 *
 * Quagga is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; see the file COPYING; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */
/**
 * 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;

/**
 * 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 = calloc(1, ((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)

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 {                                                                   \
		free((v).data);                                                \
		(v).data = NULL;                                               \
	} while (0)

#ifdef __cplusplus
}
#endif

#endif
Commit	Line	Data
50e24903 DS	1	/* Bitfields
	2	* Copyright (C) 2016 Cumulus Networks, Inc.
	3	*
	4	* This file is part of Quagga.
	5	*
	6	* Quagga is free software; you can redistribute it and/or modify it
	7	* under the terms of the GNU General Public License as published by the
	8	* Free Software Foundation; either version 2, or (at your option) any
	9	* later version.
	10	*
	11	* Quagga is distributed in the hope that it will be useful, but
	12	* WITHOUT ANY WARRANTY; without even the implied warranty of
	13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	14	* General Public License for more details.
	15	*
896014f4 DL	16	* You should have received a copy of the GNU General Public License along
	17	* with this program; see the file COPYING; if not, write to the Free Software
	18	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
50e24903	19	*/
c3c0ac83 DS	20	/**
	21	* A simple bit array implementation to allocate and free IDs. An example
	22	* of its usage is in allocating link state IDs for OSPFv3 as OSPFv3 has
	23	* removed all address semantics from LS ID. Another usage can be in
	24	* allocating IDs for BGP neighbors (and dynamic update groups) for
	25	* efficient storage of adj-rib-out.
	26	*
	27	* An example:
	28	* #include "bitfield.h"
	29	*
	30	* bitfield_t bitfield;
	31	*
	32	* bf_init(bitfield, 32);
	33	* ...
	34	* bf_assign_index(bitfield, id1);
	35	* bf_assign_index(bitfield, id2);
	36	* ...
	37	* bf_release_index(bitfield, id1);
	38	*/
	39
	40	#ifndef _BITFIELD_H
	41	#define _BITFIELD_H
	42
	43	#include <stdio.h>
	44	#include <string.h>
	45	#include <stdlib.h>
	46
5e244469 RW	47	#ifdef __cplusplus
	48	extern "C" {
	49	#endif
	50
c3c0ac83 DS	51	typedef unsigned int word_t;
	52	#define WORD_MAX 0xFFFFFFFF
	53	#define WORD_SIZE (sizeof(word_t) * 8)
	54
	55	/**
	56	* The bitfield structure.
	57	* @data: the bits to manage.
	58	* @n: The current word number that is being used.
	59	* @m: total number of words in 'data'
	60	*/
89fbf168	61	typedef struct {word_t *data; size_t n, m; } bitfield_t;
c3c0ac83 DS	62
	63	/**
	64	* Initialize the bits.
	65	* @v: an instance of bitfield_t struct.
	66	* @N: number of bits to start with, which equates to how many
	67	* IDs can be allocated.
	68	*/
d62a17ae	69	#define bf_init(v, N) \
	70	do { \
	71	(v).n = 0; \
	72	(v).m = ((N) / WORD_SIZE + 1); \
	73	(v).data = calloc(1, ((v).m * sizeof(word_t))); \
	74	} while (0)
c3c0ac83 DS	75
	76	/**
	77	* allocate and assign an id from bitfield v.
	78	*/
d62a17ae	79	#define bf_assign_index(v, id) \
	80	do { \
	81	bf_find_bit(v, id); \
	82	bf_set_bit(v, id); \
	83	} while (0)
c3c0ac83	84
4e9da201	85	/*
	86	* allocate and assign 0th bit in the bitfiled.
	87	*/
d62a17ae	88	#define bf_assign_zero_index(v) \
	89	do { \
	90	int id = 0; \
	91	bf_assign_index(v, id); \
	92	} while (0)
4e9da201	93
4e9da201	94	/*
c3c0ac83 DS	95	* return an id to bitfield v
c3c0ac83 DS	96	*/
d62a17ae	97	#define bf_release_index(v, id) \
d62a17ae	98	(v).data[bf_index(id)] &= ~(1 << (bf_offset(id)))
c3c0ac83	99
89fbf168 AK	100	/* check if an id is in use */
	101	#define bf_test_index(v, id) \
	102	((v).data[bf_index(id)] & (1 << (bf_offset(id))))
	103
	104	/* check if the bit field has been setup */
	105	#define bf_is_inited(v) ((v).data)
	106
	107	/* compare two bitmaps of the same length */
	108	#define bf_cmp(v1, v2) (memcmp((v1).data, (v2).data, ((v1).m * sizeof(word_t))))
	109
4e9da201	110	/*
	111	* return 0th index back to bitfield
	112	*/
d62a17ae	113	#define bf_release_zero_index(v) bf_release_index(v, 0)
4e9da201	114
c3c0ac83 DS	115	#define bf_index(b) ((b) / WORD_SIZE)
	116	#define bf_offset(b) ((b) % WORD_SIZE)
	117
	118	/**
	119	* Set a bit in the array. If it fills up that word and we are
	120	* out of words, extend it by one more word.
	121	*/
d62a17ae	122	#define bf_set_bit(v, b) \
	123	do { \
	124	size_t w = bf_index(b); \
	125	(v).data[w] \|= 1 << (bf_offset(b)); \
	126	(v).n += ((v).data[w] == WORD_MAX); \
	127	if ((v).n == (v).m) { \
	128	(v).m = (v).m + 1; \
	129	(v).data = realloc((v).data, (v).m * sizeof(word_t)); \
	130	} \
	131	} while (0)
c3c0ac83 DS	132
c3c0ac83 DS	133	/* Find a clear bit in v and assign it to b. */
d62a17ae	134	#define bf_find_bit(v, b) \
	135	do { \
	136	word_t word = 0; \
	137	unsigned int w, sh; \
	138	for (w = 0; w <= (v).n; w++) { \
	139	if ((word = (v).data[w]) != WORD_MAX) \
	140	break; \
	141	} \
	142	(b) = ((word & 0xFFFF) == 0xFFFF) << 4; \
	143	word >>= (b); \
	144	sh = ((word & 0xFF) == 0xFF) << 3; \
	145	word >>= sh; \
	146	(b) \|= sh; \
	147	sh = ((word & 0xF) == 0xF) << 2; \
	148	word >>= sh; \
	149	(b) \|= sh; \
	150	sh = ((word & 0x3) == 0x3) << 1; \
	151	word >>= sh; \
	152	(b) \|= sh; \
	153	sh = ((word & 0x1) == 0x1) << 0; \
	154	word >>= sh; \
	155	(b) \|= sh; \
	156	(b) += (w * WORD_SIZE); \
	157	} while (0)
c3c0ac83	158
89fbf168 AK	159	static inline unsigned int bf_find_next_set_bit(bitfield_t v,
	160	word_t start_index)
	161	{
	162	int start_bit;
	163	unsigned long i, offset;
	164
	165	start_bit = start_index & (WORD_SIZE - 1);
	166
	167	for (i = bf_index(start_index); i < v.m; ++i) {
	168	if (v.data[i] == 0) {
	169	/* if the whole word is empty move to the next */
	170	start_bit = 0;
	171	continue;
	172	}
	173	/* scan one word for set bits */
	174	for (offset = start_bit; offset < WORD_SIZE; ++offset) {
	175	if ((v.data[i] >> offset) & 1)
	176	return ((i * WORD_SIZE) + offset);
	177	}
	178	/* move to the next word */
	179	start_bit = 0;
	180	}
	181	return WORD_MAX;
	182	}
	183
	184	/* iterate through all the set bits */
	185	#define bf_for_each_set_bit(v, b, max) \
	186	for ((b) = bf_find_next_set_bit((v), 0); \
	187	(b) < max; \
	188	(b) = bf_find_next_set_bit((v), (b) + 1))
	189
4e9da201	190	/*
	191	* Free the allocated memory for data
	192	* @v: an instance of bitfield_t struct.
	193	*/
d62a17ae	194	#define bf_free(v) \
d62a17ae	195	do { \
1ac10b15 QY	196	free((v).data); \
1ac10b15 QY	197	(v).data = NULL; \
d62a17ae	198	} while (0)
4e9da201	199
5e244469 RW	200	#ifdef __cplusplus
	201	}
	202	#endif
	203
c3c0ac83	204	#endif