/

2007-10-17  Neal H. Walfield  <neal@gnu.org>

	* libbitarray: New directory.
	* configure.ac: m4_include libbitarray/headers.m4.
	(AC_CONFIGU_FILES): Add libbitarray/Makefile.
	* Makefile.am (SUBDIRS): Add libbitarray.

libbitarray/

2007-10-17  Neal H. Walfield  <neal@gnu.org>

	* ChangeLog: New file.
	* Makefile.am: Likewise.
	* bit-array.h: Likewise.
	* headers.m4: Likewise.
	* t-bit-array.c: Likewise.

5 files changed, 237 insertions, 0 deletions

diff --git a/libbitarray/ChangeLog b/libbitarray/ChangeLog
new file mode 100644
index 0000000..b410cb7
--- /dev/null
+++ b/libbitarray/ChangeLog
@@ -0,0 +1,8 @@
+2007-10-17  Neal H. Walfield  <neal@gnu.org>
+
+	* ChangeLog: New file.
+	* Makefile.am: Likewise.
+	* bit-array.h: Likewise.
+	* headers.m4: Likewise.
+	* t-bit-array.c: Likewise.
+
diff --git a/libbitarray/Makefile.am b/libbitarray/Makefile.am
new file mode 100644
index 0000000..ae10640
--- /dev/null
+++ b/libbitarray/Makefile.am
@@ -0,0 +1,28 @@
+# Makefile.am - Makefile template for libbitarray
+# Copyright (C) 2007 Free Software Foundation, Inc.
+# Written by Neal H. Walfield
+#
+# This file is part of the GNU Hurd.
+# 
+# The GNU Hurd 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 3 of the License, or
+# (at your option) any later version.
+# 
+# The GNU Hurd 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; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
+
+include_HEADERS = bit-array.h
+
+TESTS = t-bit-array
+check_PROGRAMS = $(TESTS)
+
+t_bit_array_CPPFLAGS = $(AM_CPPFLAGS)
+t_bit_array_SOURCES = t-bit-array.c
+
diff --git a/libbitarray/bit-array.h b/libbitarray/bit-array.h
new file mode 100644
index 0000000..605ffb3
--- /dev/null
+++ b/libbitarray/bit-array.h
@@ -0,0 +1,133 @@
+/* bit-array.h - Bit array manipulation functions.
+   Copyright (C) 2007 Free Software Foundation, Inc.
+   Written by Neal H. Walfield <neal@gnu.org>.
+
+   This file is part of the GNU Hurd.
+
+   The GNU Hurd 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 3 of the
+   License, or (at your option) any later version.
+
+   The GNU Hurd 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.  If not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef _BIT_ARRAY_H_
+#define _BIT_ARRAY_H_
+
+#include <stdbool.h>
+#include <assert.h>
+
+/* Set bit BIT in array ARRAY (which is SIZE bytes long).  Returns
+   true if bit was set, false otherwise.  */
+static inline bool
+bit_set (unsigned char *array, int size, int bit)
+{
+  assert (bit >= 0);
+  assert (bit < size * 8);
+
+  if ((array[bit / 8] & (1 << (bit & 0x7))))
+    /* Already set!  */
+    return false;
+
+  array[bit / 8] |= 1 << (bit & 0x7);
+  return true;  
+}
+
+/* Allocate the first free (zero) bit starting at bit START_BIT.  SIZE
+   is the size of ARRAY (in bytes).  Returns -1 on failure, otherwise
+   the bit allocated.  */
+static inline int
+bit_alloc (unsigned char *array, int size, int start_bit)
+{
+  int first_free_bit[]
+    = { /* 0000 */ 0, /* 0001 */ 1, /* 0010 */ 0, /* 0011 */ 2,
+        /* 0100 */ 0, /* 0101 */ 1, /* 0110 */ 0, /* 0111 */ 3,
+        /* 1000 */ 0, /* 1001 */ 1, /* 1010 */ 0, /* 1011 */ 2,
+        /* 1100 */ 0, /* 1101 */ 1, /* 1110 */ 0, /* 1111 */ -1 };
+
+  int check_byte (unsigned char byte)
+    {
+      /* Check the lower four bits.  */
+      int b = first_free_bit[byte & 0xf];
+      if (b != -1)
+	return b;
+
+      /* Check the uppoer four bits.  */
+      b = first_free_bit[byte >> 4];
+      if (b != -1)
+	return 4 + b;
+
+      return -1;
+    }
+
+  assert (0 <= start_bit);
+  assert (start_bit < size * 8);
+
+  int start_byte = start_bit / 8;
+  int byte = start_byte;
+  unsigned char b;
+
+  if ((start_bit & 0x7) != 0)
+    /* We don't start on a byte boundary.  */
+    {
+      b = array[byte] | ((1 << (start_bit & 0x7)) - 1);
+      goto check;
+    }
+
+  do
+    {
+      int bit;
+      b = array[byte];
+    check:
+      bit = check_byte (b);
+      if (bit != -1)
+	/* Got one!  */
+	{
+	  array[byte] |= 1 << bit;
+	  return byte * 8 + bit;
+	}
+
+      byte ++;
+      if (byte == size)
+	byte = 0;
+    }
+  while (byte != start_byte);
+
+  if ((start_bit & 0x7) != 0)
+    {
+      b = array[byte] | ~((1 << (start_bit & 0x7)) - 1);
+      int bit = check_byte (b);
+      if (bit != -1)
+	/* Got one!  */
+	{
+	  array[byte] |= 1 << bit;
+	  return byte * 8 + bit;
+	}
+    }
+
+  return -1;
+}
+
+static inline void
+bit_dealloc (unsigned char *array, int bit)
+{
+  assert ((array[bit / 8] & (1 << (bit & 0x7))));
+
+  /* Clear bit.  */
+  array[bit / 8] &= ~(1 << (bit & 0x7));
+}
+
+static inline bool
+bit_test (unsigned char *array, int bit)
+{
+  return !! (array[bit / 8] & (1 << (bit & 0x7)));
+}
+
+#endif
diff --git a/libbitarray/headers.m4 b/libbitarray/headers.m4
new file mode 100644
index 0000000..dc13857
--- /dev/null
+++ b/libbitarray/headers.m4
@@ -0,0 +1,13 @@
+# headers.m4 - Autoconf snippets to install links for header files.
+# Copyright 2007 Free Software Foundation, Inc.
+# Written by Neal H. Walfield <neal@gnu.org>.
+#
+# This file is free software; as a special exception the author gives
+# unlimited permission to copy and/or distribute it, with or without
+# modifications, as long as this notice is preserved.
+#
+# This file is distributed in the hope that it will be useful, but
+# WITHOUT ANY WARRANTY, to the extent permitted by law; without even the
+# implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+
+AC_CONFIG_LINKS([include/bit-array.h:libbitarray/bit-array.h])
diff --git a/libbitarray/t-bit-array.c b/libbitarray/t-bit-array.c
new file mode 100644
index 0000000..4d28275
--- /dev/null
+++ b/libbitarray/t-bit-array.c
@@ -0,0 +1,55 @@
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <assert.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "bit-array.h"
+
+static unsigned char array[16];
+
+int
+main (int argc, char *argv[])
+{
+  /* Make sure we can set all the bits when the bit to set is the one
+     under the hint.  */
+  int i;
+  for (i = 0; i < sizeof (array) * 8; i ++)
+    assert (bit_alloc (array, sizeof (array), i) == i);
+  assert (bit_alloc (array, sizeof (array), 1) == -1);
+
+  memset (array, 0, sizeof (array));
+
+  /* Make sure we can set all the bits when the bit to set is not
+     (necessarily) under the hint.  */
+  for (i = 0; i < sizeof (array) * 8; i ++)
+    {
+      int b = (10 + i) % (sizeof (array) * 8);
+      assert (bit_alloc (array, sizeof (array), 10) == b);
+    }
+  assert (bit_alloc (array, sizeof (array), 1) == -1);
+
+  /* Clear one bit and make sure that independent of the start hint,
+     we find that bit.  */
+  for (i = 0; i < sizeof (array) * 8; i ++)
+    {
+      bit_dealloc (array, 75);
+
+      assert (bit_alloc (array, sizeof (array), i) == 75);
+      assert (bit_alloc (array, sizeof (array), i) == -1);
+    }
+
+  /* See if we can set a bit in the middle of a byte.  */
+  bit_dealloc (array, 11);
+  assert (bit_set (array, sizeof (array), 11) == true);
+  assert (bit_set (array, sizeof (array), 11) == false);
+
+  /* And at the start of a byte.  */
+  bit_dealloc (array, 24);
+  assert (bit_set (array, sizeof (array), 24) == true);
+  assert (bit_set (array, sizeof (array), 24) == false);
+
+  return 0;
+}