To deduplicate the adj-rib-out in bgpd I want to use a bitmap per prefix
to store all the peers that have that prefix in the adj-rib-out.
The idea is that this uses 1 bit per peer instead of sizeof(struct
adjout_prefix) per peer. Which is a massive win when you have many peers.

Here is the bitmap API that I bolted together. I had a look at the API we
have in libc but decided against it since it is not dynamic enough for my
needs.

The bitmap I want to use needs to scale dynamically up but should also be
minimal for small sets (most bgpd users have less than 100 peers).
Because of this I came up with a new API.

Functions include:
- set, test, clear: set, test and clear a bit in the map
- empty: check if a bitmap is empty (has no bit set).
- id_get: return the lowest free id in map
- id_put: return an id to the map, aka clear
- init, reset: initialize and free a map

The first 127 elements are put directly into struct bitmap without further
allocation. For maps with more than 127 elements external memory is allocated
in the set function. This memory is only freed by reset which must be called
before an object is removed containing a bitmap.
It is not possible to set bit 0 of a bitmap since that bit is used to
differentiate between access modes. In my use cases this is perfectly fine
since most code already treats 0 in a special way.

-- 
:wq Claudio

? obj
Index: Makefile
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/Makefile,v
diff -u -p -r1.44 Makefile
--- Makefile	18 Nov 2025 16:39:36 -0000	1.44
+++ Makefile	10 Dec 2025 12:53:47 -0000
@@ -2,6 +2,7 @@
 
 PROG=	bgpd
 SRCS=	bgpd.c
+SRCS+=	bitmap.c
 SRCS+=	carp.c
 SRCS+=	chash.c
 SRCS+=	config.c
Index: bgpd.h
===================================================================
RCS file: /cvs/src/usr.sbin/bgpd/bgpd.h,v
diff -u -p -r1.525 bgpd.h
--- bgpd.h	10 Dec 2025 12:36:51 -0000	1.525
+++ bgpd.h	10 Dec 2025 12:53:48 -0000
@@ -253,6 +253,10 @@ TAILQ_HEAD(timer_head, timer);
 TAILQ_HEAD(listen_addrs, listen_addr);
 TAILQ_HEAD(filter_set_head, filter_set);
 
+struct bitmap {
+	uint64_t	data[2];
+};
+
 struct peer;
 RB_HEAD(peer_head, peer);
 
@@ -1581,6 +1585,18 @@ void	filterset_copy(struct filter_set_he
 const char	*filterset_name(enum action_types);
 int	filterset_send(struct imsgbuf *, struct filter_set_head *);
 void	filterset_recv(struct imsg *, struct filter_set_head *);
+
+/* bitmap.c */
+int		 bitmap_set(struct bitmap *, uint32_t);
+int		 bitmap_test(struct bitmap *, uint32_t);
+void		 bitmap_clear(struct bitmap *, uint32_t);
+int		 bitmap_empty(struct bitmap *);
+
+int		 bitmap_id_get(struct bitmap *, uint32_t *);
+void		 bitmap_id_put(struct bitmap *, uint32_t);
+
+void		 bitmap_init(struct bitmap *);
+void		 bitmap_reset(struct bitmap *);
 
 /* rde_sets.c */
 struct as_set	*as_sets_lookup(struct as_set_head *, const char *);
Index: bitmap.c
===================================================================
RCS file: bitmap.c
diff -N bitmap.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ bitmap.c	10 Dec 2025 12:53:48 -0000
@@ -0,0 +1,229 @@
+/*	$OpenBSD$	*/
+/*
+ * Copyright (c) 2025 Claudio Jeker <claudio@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <errno.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <strings.h>
+
+#include "bgpd.h"
+
+#define BITMAP_BITS		64
+#define BITMAP_ALLOCBITS	(4 * BITMAP_BITS)
+#define BITMAP_ROUNDUP(x, y)	((((x) + (y) - 1)/(y)) * (y))
+#define BITMAP_SETPTR(x)	((uint64_t)(x) | 0x1)
+#define BITMAP_GETPTR(x)	(uint64_t *)((x) & ~0x1)
+
+static inline void
+bitmap_getset(struct bitmap *map, uint64_t **ptr, uint32_t *max)
+{
+	if ((map->data[0] & 0x1) == 0) {
+		*ptr = map->data;
+		*max = nitems(map->data) * BITMAP_BITS;
+	} else {
+		*ptr = BITMAP_GETPTR(map->data[0]);
+		*max = map->data[1];
+	}
+}
+
+static int
+bitmap_resize(struct bitmap *map, uint32_t bid)
+{
+	uint64_t *ptr, *new;
+	uint32_t elm, max, newmax;
+
+	bitmap_getset(map, &ptr, &max);
+
+	/* get new map */
+	newmax = BITMAP_ROUNDUP(bid + 1, BITMAP_ALLOCBITS);
+	if ((new = malloc(newmax / 8)) == NULL)
+		return -1;
+
+	/* copy data over */
+	max /= BITMAP_BITS;
+	for (elm = 0; elm < max; elm++)
+		new[elm] = ptr[elm];
+	max = newmax / BITMAP_BITS;
+	for ( ; elm < max; elm++)
+		new[elm] = 0;
+
+	/* free old data */
+	if (map->data[0] & 0x1)
+		free(BITMAP_GETPTR(map->data[0]));
+
+	map->data[0] = BITMAP_SETPTR(new);
+	map->data[1] = newmax;
+
+	return 0;
+}
+
+/*
+ * Set bit at position bid in map. Extending map if needed.
+ * Returns 0 on success and -1 on failure.
+ */
+int
+bitmap_set(struct bitmap *map, uint32_t bid)
+{
+	uint64_t *ptr;
+	uint32_t  max, elm;
+
+	bitmap_getset(map, &ptr, &max);
+
+	if (bid == 0) {
+		errno = EINVAL;
+		return -1;
+	}
+
+	if (bid >= max) {
+		if (bitmap_resize(map, bid) == -1)
+			return -1;
+		bitmap_getset(map, &ptr, &max);
+	}
+
+	elm = bid / BITMAP_BITS;
+	bid %= BITMAP_BITS;
+
+	ptr[elm] |= (1ULL << bid);
+	return 0;
+}
+
+/*
+ * Test if bit at position bid is set in map.
+ */
+int
+bitmap_test(struct bitmap *map, uint32_t bid)
+{
+	uint64_t *ptr;
+	uint32_t  max, elm;
+
+	bitmap_getset(map, &ptr, &max);
+
+	if (bid >= max || bid == 0)
+		return 0;
+
+	elm = bid / BITMAP_BITS;
+	bid %= BITMAP_BITS;
+
+	return (ptr[elm] & (1ULL << bid)) != 0;
+}
+
+/*
+ * Clear bit at position bid in map.
+ */
+void
+bitmap_clear(struct bitmap *map, uint32_t bid)
+{
+	uint64_t *ptr;
+	uint32_t  max, elm;
+
+	bitmap_getset(map, &ptr, &max);
+
+	if (bid >= max || bid == 0)
+		return;
+
+	elm = bid / BITMAP_BITS;
+	bid %= BITMAP_BITS;
+
+	ptr[elm] &= ~(1ULL << bid);
+}
+
+/*
+ * Check if bitmap has nothing set (all zero).
+ * Returns 1 if empty else 0.
+ */
+int
+bitmap_empty(struct bitmap *map)
+{
+	uint64_t *ptr, m;
+	uint32_t elm, max, end;
+
+	bitmap_getset(map, &ptr, &max);
+
+	end = max / BITMAP_BITS;
+	for (elm = 0; elm < end; elm++) {
+		m = ptr[elm];
+		if (elm == 0)
+			m &= ~0x1;	/* skip inline marker */
+		if (m != 0)
+			return 0;
+	}
+	return 1;
+}
+
+/*
+ * Allocate the lowest free id in a map.
+ */
+int
+bitmap_id_get(struct bitmap *map, uint32_t *bid)
+{
+	uint64_t *ptr, m;
+	uint32_t elm, max, end;
+
+	bitmap_getset(map, &ptr, &max);
+
+	end = max / BITMAP_BITS;
+	for (elm = 0; elm < end; elm++) {
+		m = ~ptr[elm];
+		if (elm == 0)
+			m &= ~0x1;	/* skip inline marker */
+		if (m == 0)
+			continue;
+
+		*bid = elm * BITMAP_BITS + ffsll(m) - 1;
+		if (bitmap_set(map, *bid) == -1)
+			return -1;
+		return 0;
+	}
+
+	if (bitmap_set(map, max) == -1)
+		return -1;
+
+	*bid = max;
+	return 0;
+}
+
+/*
+ * Release an id, so it can be reallocated.
+ */
+void
+bitmap_id_put(struct bitmap *map, uint32_t bid)
+{
+	bitmap_clear(map, bid);
+}
+
+/*
+ * Init a map by setting both data values to 0.
+ */
+void
+bitmap_init(struct bitmap *map)
+{
+	map->data[0] = 0;
+	map->data[1] = 0;
+}
+
+/*
+ * Reset a map back to initial state, freeing any memory that was allocated.
+ */
+void
+bitmap_reset(struct bitmap *map)
+{
+	if (map->data[0] & 0x1)
+		free(BITMAP_GETPTR(map->data[0]));
+
+	bitmap_init(map);
+}