[Nagios-checkins] SF.net SVN: nagios:[2081] nagioscore/trunk/lib

[<ag...@us...>]

Revision: 2081
          http://nagios.svn.sourceforge.net/nagios/?rev=2081&view=rev
Author:   ageric
Date:     2012-08-20 16:27:12 +0000 (Mon, 20 Aug 2012)
Log Message:
-----------
Add bitmap library to libnagios

This is insanely useful for calculating dependency graphs now that
each object has a unique id, and will briefly be used to do exactly
that.

Actually, it's insanely useful to flag just about anything with an
id in constant time and very little space, but we'll initially be
using it to check for circular paths in service dependencies.

Signed-off-by: Andreas Ericsson <ae...@op...>

Modified Paths:
--------------
    nagioscore/trunk/lib/.gitignore
    nagioscore/trunk/lib/Makefile.in
    nagioscore/trunk/lib/libnagios.h

Added Paths:
-----------
    nagioscore/trunk/lib/bitmap.c
    nagioscore/trunk/lib/bitmap.h
    nagioscore/trunk/lib/test-bitmap.c

Modified: nagioscore/trunk/lib/.gitignore
===================================================================
--- nagioscore/trunk/lib/.gitignore	2012-08-20 16:26:47 UTC (rev 2080)
+++ nagioscore/trunk/lib/.gitignore	2012-08-20 16:27:12 UTC (rev 2081)
@@ -2,4 +2,5 @@
 test-kvvec
 test-iocache
 test-iobroker
+test-bitmap
 wproc

Modified: nagioscore/trunk/lib/Makefile.in
===================================================================
--- nagioscore/trunk/lib/Makefile.in	2012-08-20 16:26:47 UTC (rev 2080)
+++ nagioscore/trunk/lib/Makefile.in	2012-08-20 16:27:12 UTC (rev 2081)
@@ -8,7 +8,7 @@
 all: $(LIBNAME)
 
 SNPRINTF_O=@SNPRINTF_O@
-TESTED_SRC_C := squeue.c kvvec.c iocache.c iobroker.c
+TESTED_SRC_C := squeue.c kvvec.c iocache.c iobroker.c bitmap.c
 SRC_C := $(TESTED_SRC_C) pqueue.c runcmd.c worker.c skiplist.c
 SRC_O := $(patsubst %.c,%.o,$(SRC_C)) $(SNPRINTF_O)
 TESTS := $(patsubst %.c,test-%,$(TESTED_SRC_C))

Added: nagioscore/trunk/lib/bitmap.c
===================================================================
--- nagioscore/trunk/lib/bitmap.c	                        (rev 0)
+++ nagioscore/trunk/lib/bitmap.c	2012-08-20 16:27:12 UTC (rev 2081)
@@ -0,0 +1,261 @@
+#include <assert.h>
+#include "bitmap.h"
+#include <stdlib.h>
+#include <unistd.h>
+
+#ifndef CHAR_BIT
+# define CHAR_BIT 8
+#endif
+
+typedef unsigned int bmap;
+
+#define MAPSIZE (sizeof(bmap) * CHAR_BIT)
+#define MAPMASK (MAPSIZE - 1) /* bits - 1, so 63 for 64-bit machines */
+#define SHIFTOUT (MAPSIZE == 64 ? 6 : 5) /* log2(bits) */
+
+struct bitmap {
+	bmap *vector;
+	unsigned int alloc;
+};
+
+static bitmap *bitmap_init(bitmap *bm, unsigned long size)
+{
+	if (!bm)
+		return NULL;
+
+	/* be tight on space */
+	bm->alloc = (size >> SHIFTOUT) + !!(size & MAPMASK);
+	bm->vector = calloc(1, bm->alloc * sizeof(bmap));
+#if 0
+	printf("bitmap created with %lu bytes of storage and capacity %lu\n",
+		   bm->alloc * sizeof(bmap), bm->alloc * MAPSIZE);
+#endif
+	return bm;
+}
+
+bitmap *bitmap_create(unsigned long size)
+{
+	return bitmap_init(calloc(1, sizeof(bitmap)), size);
+}
+
+void bitmap_destroy(bitmap *bm)
+{
+	if (!bm)
+		return;
+	if (bm->vector)
+		free(bm->vector);
+	free(bm);
+}
+
+bitmap *bitmap_copy(const bitmap *bm)
+{
+	bitmap *ret;
+
+	if (!bm)
+		return NULL;
+	ret = bitmap_create(bitmap_cardinality(bm));
+	if (!ret)
+		return NULL;
+
+	memcpy(ret->vector, bm->vector, bitmap_size(bm));
+	return ret;
+}
+
+static inline unsigned int l_bits(bmap map)
+{
+	unsigned int i, tot_bits = 0;
+
+	/*
+	 * bits per byte. A 16k entry table would be slightly faster
+	 * on most archs but a damn sight uglier on all of them
+	 */
+	const unsigned char bpb[256] = {
+		0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
+		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+		1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+		2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
+		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+		3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
+		4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
+	};
+
+	if (0 && map)
+		printf("0x%08x\n", map);
+	for (i = 0; i < sizeof(bmap); i++) {
+		const unsigned char ch = (map >> (i * CHAR_BIT)) & 0xff;
+		const unsigned char cbits = bpb[ch];
+		tot_bits += cbits;
+		if (0 && cbits)
+			printf("%d: top char: 0x%02x; bits: %u; tot_bits: %u\n",
+				   i, ch, cbits, tot_bits);
+	}
+
+	return tot_bits;
+}
+
+
+int bitmap_set(bitmap *bm, unsigned long pos)
+{
+	const bmap l = pos >> SHIFTOUT;
+	const unsigned int bit = pos & MAPMASK;
+
+	if (!bm)
+		return 0;
+	if (l > bm->alloc)
+		return -1;
+
+	bm->vector[l] |= (1 << bit);
+	return 0;
+}
+
+int bitmap_isset(const bitmap *bm, unsigned long pos)
+{
+	const bmap l = pos >> SHIFTOUT;
+	const int bit = pos & MAPMASK;
+	int set;
+
+	if (!bm || l > bm->alloc)
+		return 0;
+
+	set = !!(bm->vector[l] & (1 << bit));
+	return set;
+}
+
+int bitmap_unset(bitmap *bm, unsigned long pos)
+{
+	const bmap l = pos >> SHIFTOUT;
+	const int bit = pos & MAPMASK;
+	const int val = bitmap_isset(bm, pos);
+
+	bm->vector[l] &= ~(1 << bit);
+	return val;
+}
+
+unsigned long bitmap_cardinality(const bitmap *bm)
+{
+	if (!bm)
+		return 0;
+
+	return bm->alloc * MAPSIZE;
+}
+
+/*
+ * count set bits in alloc * (mapsize / 8) ops
+ */
+unsigned long bitmap_count_set_bits(const bitmap *bm)
+{
+	unsigned long i, set_bits = 0;
+
+	if (!bm)
+		return 0;
+
+	for (i = 0; i < bm->alloc; i++) {
+		set_bits += l_bits(bm->vector[i]);
+	}
+
+	return set_bits;
+}
+
+unsigned long bitmap_count_unset_bits(const bitmap *bm)
+{
+	return bitmap_cardinality(bm) - bitmap_count_set_bits(bm);
+}
+
+#define BITMAP_MATH(a, b) \
+	int i; \
+	bitmap *bm; \
+	/* a->alloc has to be smallest */ \
+	if (a->alloc > b->alloc) { \
+		const bitmap *temp = b; \
+		b = a; \
+		a = temp; \
+	} \
+	bm = bitmap_create(bitmap_cardinality(b)); \
+	if (!bm) \
+		return NULL; \
+	for (i = 0; i < a->alloc; i++)
+
+bitmap *bitmap_intersect(const bitmap *a, const bitmap *b)
+{
+	BITMAP_MATH(a, b) {
+		bm->vector[i] = a->vector[i] & b->vector[i];
+	}
+
+	return bm;
+}
+
+
+bitmap *bitmap_union(const bitmap *a, const bitmap *b)
+{
+	BITMAP_MATH(a, b) {
+		bm->vector[i] = a->vector[i] | b->vector[i];
+	}
+
+	return bm;
+}
+
+/* 
+ * Remove all elements from a that are also in b.
+ */
+bitmap *bitmap_minus(const bitmap *a, const bitmap *b)
+{
+	BITMAP_MATH(a, b) {
+		bm->vector[i] = a->vector[i] & ~(b->vector[i]);
+	}
+	return bm;
+}
+
+/*
+ * set difference gets everything in A that isn't also in B. A is the
+ * numerator, so if it's larger we must include any overflow in the
+ * resulting set.
+ */
+bitmap *bitmap_diff(const bitmap *a, const bitmap *b)
+{
+	const bitmap *a_ = a, *b_ = b;
+
+	BITMAP_MATH(a, b) {
+		bm->vector[i] = a->vector[i] & ~(b->vector[i]);
+	}
+	if (a_->alloc > b_->alloc) {
+		memcpy(&bm->vector[i], &b->vector[i], (b->alloc - a->alloc) * MAPSIZE);
+	}
+	return bm;
+}
+
+/*
+ * symmetric set difference lists all items only present in one set
+ */
+bitmap *bitmap_symdiff(const bitmap *a, const bitmap *b)
+{
+	BITMAP_MATH(a, b) {
+		bm->vector[i] = (a->vector[i] | b->vector[i]) ^ (a->vector[i] & b->vector[i]);
+	}
+	if (b->alloc > a->alloc) {
+		memcpy(&bm->vector[i], &b->vector[i], (b->alloc - a->alloc) * MAPSIZE);
+	}
+	return bm;
+}
+
+#define min(a, b) (a > b ? b : a)
+int bitmap_cmp(const bitmap *a, const bitmap *b)
+{
+	int ret;
+
+	ret = memcmp(a->vector, b->vector, min(a->alloc, b->alloc) * MAPSIZE);
+	if (ret || a->alloc == b->alloc) {
+		return ret;
+	}
+	if (a->alloc > b->alloc)
+		return 1;
+	return -1;
+}

Added: nagioscore/trunk/lib/bitmap.h
===================================================================
--- nagioscore/trunk/lib/bitmap.h	                        (rev 0)
+++ nagioscore/trunk/lib/bitmap.h	2012-08-20 16:27:12 UTC (rev 2081)
@@ -0,0 +1,134 @@
+#ifndef LIBNAGIOS_bitmap_h__
+#define LIBNAGIOS_bitmap_h__
+/**
+ * @file bitmap.h
+ * @brief Bit vector API
+ * @{
+ */
+struct bitmap;
+typedef struct bitmap bitmap;
+
+/**
+ * Create a bitmaptor of size 'size'
+ * @param size Desired storage capacity
+ * @return A bitmap pointer on success, NULL on errors
+ */
+extern bitmap *bitmap_create(unsigned long size);
+
+/**
+ * Destroy a bitmaptor by freeing all the memory it uses
+ * @param bm The bitmaptor to destroy
+ */
+extern void bitmap_destroy(bitmap *bm);
+
+/**
+ * Copy a bitmaptor
+ * @param bm The bitmaptor to copy
+ * @return Pointer to an identical bitmap on success, NULL on errors
+ */
+extern bitmap *bitmap_copy(const bitmap *bm);
+
+/**
+ * Set a bit in the vector
+ * @param bm The bitmaptor to operate on
+ * @param pos Position of the bit to set
+ * @return 0 on success, -1 on errors
+ */
+extern int bitmap_set(bitmap *bm, unsigned long pos);
+
+/**
+ * Check if a particular bit is set in the vector
+ * @param bm The bitmaptor to check
+ * @param pos Position of the bit to check
+ * @return 1 if set, otherwise 0
+ */
+extern int bitmap_isset(const bitmap *bm, unsigned long pos);
+
+/**
+ * Unset a particular bit in the vector
+ * @param bm The bitmaptor to operate on
+ * @param pos Position of the bit to unset
+ */
+extern int bitmap_unset(bitmap *bm, unsigned long pos);
+
+/**
+ * Obtain cardinality (max number of elements) of the bitmaptor
+ * @param bm The bitmaptor to check
+ * @return The cardinality of the bitmaptor
+ */
+extern unsigned long bitmap_cardinality(const bitmap *bm);
+#define bitmap_size bitmap_cardinality
+
+/**
+ * Count set bits in vector. Completed in O(n/8) time.
+ * @param bm The bitmaptor to count bits in
+ * @return The number of set bits
+ */
+extern unsigned long bitmap_count_set_bits(const bitmap *bm);
+
+/**
+ * Count unset bits in vector. Completed in O(n/8) time.
+ * @param bm The bitmaptor to count bits in
+ * @return The number of set bits
+ */
+extern unsigned long bitmap_count_unset_bits(const bitmap *bm);
+
+/**
+ * Unset all bits in a bitmaptor
+ * @param bm The bitmaptor to clear
+ */
+extern bitmap *bitmap_clear(bitmap *bm);
+
+/**
+ * Calculate intersection of two bitmaptors
+ * The intersection is defined as all bits that are members of
+ * both A and B. It's equivalent to bitwise AND.
+ * This function completes in O(n/sizeof(long)) operations.
+ * @param a The first bitmaptor
+ * @param b The second bitmaptor
+ * @return NULL on errors; A newly created bitmaptor on success.
+ */
+extern bitmap *bitmap_intersect(const bitmap *a, const bitmap *b);
+
+/**
+ * Calculate union of two bitmaptors
+ * The union is defined as all bits that are members of
+ * A or B or both A and B. It's equivalent to bitwise OR.
+ * This function completes in O(n/sizeof(long)) operations.
+ * @param a The first bitmaptor
+ * @param b The second bitmaptor
+ * @return NULL on errors; A newly created bitmaptor on success.
+ */
+extern bitmap *bitmap_union(const bitmap *a, const bitmap *b);
+
+/**
+ * Calculate set difference between two bitmaptors
+ * The set difference of A / B is defined as all members of A
+ * that isn't members of B. Note that parameter ordering matters
+ * for this function.
+ * This function completes in O(n/sizeof(long)) operations.
+ * @param a The first bitmaptor (numerator)
+ * @param b The first bitmaptor (denominator)
+ * @return NULL on errors; A newly created bitmaptor on success.
+ */
+extern bitmap *bitmap_diff(const bitmap *a, const bitmap *b);
+
+/**
+ * Calculate symmetric difference between two bitmaptors
+ * The symmetric difference between A and B is the set that
+ * contains all elements in either set but not in both.
+ * This function completes in O(n/sizeof(long)) operations.
+ * @param a The first bitmaptor
+ * @param b The second bitmaptor
+ */
+extern bitmap *bitmap_symdiff(const bitmap *a, const bitmap *b);
+
+/**
+ * Compare two bitmaptors for equality
+ * @param a The first bitmaptor
+ * @param b The other bitmaptor
+ * @return Similar to memcmp(), with tiebreaks determined by cardinality
+ */
+extern int bitmap_cmp(const bitmap *a, const bitmap *b);
+/** @} */
+#endif /* LIBNAGIOS_bitmap_h__ */

Modified: nagioscore/trunk/lib/libnagios.h
===================================================================
--- nagioscore/trunk/lib/libnagios.h	2012-08-20 16:26:47 UTC (rev 2080)
+++ nagioscore/trunk/lib/libnagios.h	2012-08-20 16:27:12 UTC (rev 2081)
@@ -13,6 +13,7 @@
 #include "iobroker.h"
 #include "iocache.h"
 #include "runcmd.h"
+#include "bitmap.h"
 #include "worker.h"
 #include "skiplist.h"
 #endif /* LIB_libnagios_h__ */

Added: nagioscore/trunk/lib/test-bitmap.c
===================================================================
--- nagioscore/trunk/lib/test-bitmap.c	                        (rev 0)
+++ nagioscore/trunk/lib/test-bitmap.c	2012-08-20 16:27:12 UTC (rev 2081)
@@ -0,0 +1,66 @@
+#include "t-utils.h"
+#include "lnag-utils.h"
+#include "bitmap.c"
+
+#define PRIME 2089
+int main(int argc, char **argv)
+{
+	bitmap *a = NULL, *b, *r_union, *r_diff, *r_symdiff, *r_intersect;
+	int i;
+	int sa[] = {    2, 3, 4, 1783, 1784, 1785 };
+	int sb[] = { 1, 2, 3,          1784, 1785, 1786, 1790, 1791, 1792 };
+	/*
+	 * intersect:   2, 3,          1784, 1785
+	 * union:    1, 2, 3, 4, 1783, 1784, 1785, 1786, 1790, 1791, 1792
+	 * diff A/B:          4, 1783
+	 * diff B/A: 1,                            1786, 1790, 1791, 1792
+	 * symdiff:  1,          1783,             1786, 1790, 1791, 1792
+	 */
+
+	ok_int(bitmap_count_set_bits(a), 0, "counting bits in null vector a");
+	a = bitmap_create(PRIME);
+	b = bitmap_create(PRIME);
+	ok_int(bitmap_count_set_bits(b), 0, "counting bits in empty vector b");
+
+	t_set_colors(0);
+	ok_int(bitmap_cardinality(a) > PRIME, 1, "bitmap cardinality test");
+	for (i = 0; i < veclen(sa); i++) {
+		bitmap_set(a, sa[i]);
+	}
+	ok_int(bitmap_count_set_bits(a), veclen(sa), "counting set bits for a");
+
+	for (i = 0; i < veclen(sb); i++) {
+		ok_int(0, bitmap_isset(b, sb[i]), "checking unset bit");
+		bitmap_set(b, sb[i]);
+		if (!ok_int(1, bitmap_isset(b, sb[i]), "set and isset should work"))
+			printf("sb[i]: %d\n", sb[i]);
+	}
+	if (!ok_int(bitmap_count_set_bits(b), veclen(sb), "counting set bits for b")) {
+		for (i = 0; i < PRIME; i++) {
+			if (bitmap_isset(b, i)) {
+				;
+			}
+		}
+	}
+
+	r_union = bitmap_union(a, b);
+	ok_int(bitmap_count_set_bits(r_union), 11, "bitmap union sets the right amount of bits");
+	for (i = 0; i < veclen(sa); i++) {
+		ok_int(1, bitmap_isset(r_union, sa[i]), "union should have bits from a");
+	}
+	for (i = 0; i < veclen(sb); i++) {
+		ok_int(1, bitmap_isset(r_union, sb[i]), "union should have bits from b");
+	}
+
+	r_diff = bitmap_diff(a, b);
+	ok_int(bitmap_count_set_bits(r_diff), 2, "diff must set right amount of bits");
+
+	r_symdiff = bitmap_symdiff(a, b);
+	ok_int(bitmap_count_set_bits(r_symdiff), 7, "symdiff must set right amount of bits");
+
+	r_intersect = bitmap_intersect(a, b);
+	ok_int(bitmap_count_set_bits(r_intersect), 4, "intersect must set right amount of bits");
+
+	t_end();
+	return 0;
+}

This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.