bitarray: Add first{clear,set}_skip

From: Olivier Brunel <jjk_at_jjacky.com>
Date: Sun, 27 Dec 2015 19:03:23 +0100

Hey Laurent,

So skalibs contains a few functions to work with bit arrays, but only some of
the supported operations can be done with an offset (unless I missed it). One
can obviously clear, set or peek at any bit within the array, but also set/clear
a group of bits from an offset via bitarray_clearsetn().

However, to get the first bit clear/set within a group, the functions
bitarray_first{clear,set}() do not support an offset, even though it might be
useful -- I certainly had the need for it recently.

I think it'd be a nice addition to support this. Since I had to do it, you'll
find below the code for it, feel free not to use it & implement this differently
as you wish ofc (I'm using git to send this as that's better to properly send
code, but this isn't a patch per-se, since I didn't do touch doc/deps or
nothing; Also this would make a terrible commit message :p), or point me to what
I missed to do so already, if that's the case.

For the record, I believe there might be more functions that do not support use
with such an offset, e.g. bitarray_countones(), but I didn't need any of that
so I didn't look further.

Cheers,
-j

---
 src/libstddjb/bitarray_firstclear_skip.c | 22 ++++++++++++++++++++++
 src/libstddjb/bitarray_firstset_skip.c   | 22 ++++++++++++++++++++++
 2 files changed, 44 insertions(+)
 create mode 100644 src/libstddjb/bitarray_firstclear_skip.c
 create mode 100644 src/libstddjb/bitarray_firstset_skip.c
diff --git a/src/libstddjb/bitarray_firstclear_skip.c b/src/libstddjb/bitarray_firstclear_skip.c
new file mode 100644
index 0000000..1361fb2
--- /dev/null
+++ b/src/libstddjb/bitarray_firstclear_skip.c
_at_@ -0,0 +1,22 @@
+
+#include <skalibs/bitarray.h>
+
+unsigned int
+bitarray_firstclear_skip (register unsigned char const *s, unsigned int max, unsigned int skip)
+{
+    unsigned int n = bitarray_div8(max) ;
+    register unsigned int i = bitarray_div8(skip) ;
+    if (i && s[i - 1] != 0xffU)
+    {
+        register unsigned int j = skip ;
+        skip = i << 3 ;
+        if (skip > max) skip = max ;
+        while ((j < skip) && bitarray_peek(s, j)) ++j ;
+        if (j < skip) return j ;
+    }
+    for (; i < n ; ++i) if (s[i] != 0xffU) break ;
+    if (i == n) return max ;
+    i <<= 3 ;
+    while ((i < max) && bitarray_peek(s, i)) ++i ;
+    return i ;
+}
diff --git a/src/libstddjb/bitarray_firstset_skip.c b/src/libstddjb/bitarray_firstset_skip.c
new file mode 100644
index 0000000..5d77a0c
--- /dev/null
+++ b/src/libstddjb/bitarray_firstset_skip.c
_at_@ -0,0 +1,22 @@
+
+#include <skalibs/bitarray.h>
+
+unsigned int
+bitarray_firstset_skip (register unsigned char const *s, unsigned int max, unsigned int skip)
+{
+    unsigned int n = bitarray_div8(max) ;
+    register unsigned int i = bitarray_div8(skip) ;
+    if (i && s[i - 1])
+    {
+        register unsigned int j = skip ;
+        skip = i << 3 ;
+        if (skip > max) skip = max ;
+        while ((j < skip) && !bitarray_peek(s, j)) ++j ;
+        if (j < skip) return j ;
+    }
+    for (; i < n ; ++i) if (s[i]) break ;
+    if (i == n) return max ;
+    i <<= 3 ;
+    while ((i < max) && !bitarray_peek(s, i)) ++i ;
+    return i ;
+}
-- 
2.6.4

Received on Sun Dec 27 2015 - 18:03:23 UTC