summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--NEWS2
-rw-r--r--README.md1
-rw-r--r--doc/Doxyfile.in1
-rw-r--r--include/zix/bitset.h129
-rw-r--r--include/zix/zix.h1
-rw-r--r--meson.build5
-rw-r--r--src/bitset.c107
-rw-r--r--test/cpp/test_headers_cpp.cpp1
-rw-r--r--test/headers/test_headers.c1
-rw-r--r--test/test_bitset.c71
10 files changed, 2 insertions, 317 deletions
diff --git a/NEWS b/NEWS
index 4f67966..b619e92 100644
--- a/NEWS
+++ b/NEWS
@@ -1,4 +1,4 @@
-zix (0.3.0) unstable; urgency=medium
+zix (0.3.1) unstable; urgency=medium
* Initial release
diff --git a/README.md b/README.md
index 829a72c..6aaa4ba 100644
--- a/README.md
+++ b/README.md
@@ -8,7 +8,6 @@ Components
* `ZixAllocator`: A customizable allocator.
* `ZixBumpAllocator`: A simple realtime-safe "bump-pointer" allocator.
- * `ZixBitset`: A packed set of bits of arbitrary length.
* `ZixBTree`: A page-allocated B-tree.
* `ZixHash`: An open-addressing hash table.
* `ZixRing`: A lock-free realtime-safe ring buffer.
diff --git a/doc/Doxyfile.in b/doc/Doxyfile.in
index 13e8ca0..cce012f 100644
--- a/doc/Doxyfile.in
+++ b/doc/Doxyfile.in
@@ -57,7 +57,6 @@ INPUT = @ZIX_SRCDIR@/include/zix/zix.h \
\
@ZIX_SRCDIR@/include/zix/digest.h \
\
- @ZIX_SRCDIR@/include/zix/bitset.h \
@ZIX_SRCDIR@/include/zix/btree.h \
@ZIX_SRCDIR@/include/zix/hash.h \
@ZIX_SRCDIR@/include/zix/ring.h \
diff --git a/include/zix/bitset.h b/include/zix/bitset.h
deleted file mode 100644
index 491346d..0000000
--- a/include/zix/bitset.h
+++ /dev/null
@@ -1,129 +0,0 @@
-// Copyright 2014-2022 David Robillard <d@drobilla.net>
-// SPDX-License-Identifier: ISC
-
-#ifndef ZIX_BITSET_H
-#define ZIX_BITSET_H
-
-#include "zix/attributes.h"
-
-#include <limits.h>
-#include <stdbool.h>
-#include <stddef.h>
-#include <stdint.h>
-
-/**
- @defgroup zix_bitset Bitset
- @ingroup zix_data_structures
- @{
-*/
-
-/**
- A bitset element.
-
- A bitset is an array that is always referred to by pointer. This type is
- the type of an element of that array (which stores some number of bits), so
- a pointer to this type is a pointer to a bitset.
-*/
-typedef unsigned long ZixBitset;
-
-/**
- Tally of the number of bits in one ZixBitset element.
-
- Like #ZixBitset, this is the type of one element of a tally, which is a
- parallel array to the bitset one, also always referred to by pointer.
-*/
-typedef uint8_t ZixBitsetTally;
-
-/// The number of bits per ZixBitset array element
-#define ZIX_BITSET_BITS_PER_ELEM (CHAR_BIT * sizeof(ZixBitset))
-
-/// The number of bitset elements needed for the given number of bits
-#define ZIX_BITSET_ELEMS(n_bits) \
- (((n_bits) / ZIX_BITSET_BITS_PER_ELEM) + \
- (((n_bits) % ZIX_BITSET_BITS_PER_ELEM) ? 1 : 0))
-
-/**
- Clear a bitset.
-
- @param b The bitset to clear.
- @param t The tally for `b` to update.
- @param n_bits The number of bits in `b`.
-*/
-ZIX_API
-void
-zix_bitset_clear(ZixBitset* ZIX_NONNULL b,
- ZixBitsetTally* ZIX_NONNULL t,
- size_t n_bits);
-
-/**
- Set bit `i` in `b`.
-
- @param b The bitset to set bit `i` in.
- @param t The tally for `b` to update.
- @param i The index of the bit to set.
-*/
-ZIX_API
-void
-zix_bitset_set(ZixBitset* ZIX_NONNULL b,
- ZixBitsetTally* ZIX_NONNULL t,
- size_t i);
-
-/**
- Clear bit `i` in `b`.
-
- @param b The bitset to set bit `i` in.
- @param t The tally for `b` to update.
- @param i The index of the bit to set.
-*/
-ZIX_API
-void
-zix_bitset_reset(ZixBitset* ZIX_NONNULL b,
- ZixBitsetTally* ZIX_NONNULL t,
- size_t i);
-
-/**
- Return the bit at index `i` in `b`.
-
- @param b The bitset to access.
- @param i The index of the bit to return.
- @return True if the bit is set (1), false otherwise (0).
-*/
-ZIX_PURE_API
-bool
-zix_bitset_get(const ZixBitset* ZIX_NONNULL b, size_t i);
-
-/**
- Return the number of set bits in `b` up to bit `i`.
-
- The returned count is non-inclusive, that is, doesn't include bit `i`.
-
- @param b The bitset to count.
- @param t The tally for `b`.
- @param i The end index to stop counting at.
- @return The number of set bits in `b` from bit 0 to bit `i - 1`.
-*/
-ZIX_PURE_API
-size_t
-zix_bitset_count_up_to(const ZixBitset* ZIX_NONNULL b,
- const ZixBitsetTally* ZIX_NONNULL t,
- size_t i);
-
-/**
- Return the number of set bits in `b` up to bit `i` if it is set.
-
- The returned count is non-inclusive, that is, doesn't include bit `i`.
-
- @return The number of set bits in `b` from bit 0 to bit `i - 1` if bit `i`
- is set, otherwise, `(size_t)-1`.
-*/
-ZIX_PURE_API
-size_t
-zix_bitset_count_up_to_if(const ZixBitset* ZIX_NONNULL b,
- const ZixBitsetTally* ZIX_NONNULL t,
- size_t i);
-
-/**
- @}
-*/
-
-#endif /* ZIX_BITSET_H */
diff --git a/include/zix/zix.h b/include/zix/zix.h
index d0ac943..ca72d35 100644
--- a/include/zix/zix.h
+++ b/include/zix/zix.h
@@ -43,7 +43,6 @@
@{
*/
-#include "zix/bitset.h"
#include "zix/btree.h"
#include "zix/hash.h"
#include "zix/ring.h"
diff --git a/meson.build b/meson.build
index 4fb2abb..bbf63d0 100644
--- a/meson.build
+++ b/meson.build
@@ -2,7 +2,7 @@
# SPDX-License-Identifier: 0BSD OR ISC
project('zix', ['c'],
- version: '0.3.0',
+ version: '0.3.1',
license: 'ISC',
meson_version: '>= 0.56.0',
default_options: [
@@ -190,7 +190,6 @@ include_dirs = include_directories(['include'])
c_headers = files(
'include/zix/allocator.h',
'include/zix/attributes.h',
- 'include/zix/bitset.h',
'include/zix/btree.h',
'include/zix/bump_allocator.h',
'include/zix/digest.h',
@@ -208,7 +207,6 @@ c_headers = files(
sources = files(
'src/allocator.c',
- 'src/bitset.c',
'src/btree.c',
'src/bump_allocator.c',
'src/digest.c',
@@ -340,7 +338,6 @@ install_headers(c_headers, subdir: versioned_name / 'zix')
sequential_tests = [
'allocator',
- 'bitset',
'btree',
'digest',
'hash',
diff --git a/src/bitset.c b/src/bitset.c
deleted file mode 100644
index d180ccd..0000000
--- a/src/bitset.c
+++ /dev/null
@@ -1,107 +0,0 @@
-// Copyright 2014-2020 David Robillard <d@drobilla.net>
-// SPDX-License-Identifier: ISC
-
-#include "zix/bitset.h"
-
-#ifdef _MSC_VER
-# include <intrin.h>
-#endif
-
-#include <string.h>
-
-/// Number of bits per ZixBitset element (ala CHAR_BIT)
-#define ZIX_BITSET_ELEM_BIT (CHAR_BIT * sizeof(ZixBitset))
-
-static inline size_t
-zix_bitset_popcount(const ZixBitset value)
-{
-#ifdef _MSC_VER
- return (size_t)__popcnt(value);
-#else
- return (size_t)__builtin_popcountl(value);
-#endif
-}
-
-void
-zix_bitset_clear(ZixBitset* b, ZixBitsetTally* t, size_t n_bits)
-{
- memset(b, 0, ZIX_BITSET_ELEMS(n_bits) * sizeof(ZixBitset));
- memset(t, 0, ZIX_BITSET_ELEMS(n_bits) * sizeof(ZixBitsetTally));
-}
-
-void
-zix_bitset_set(ZixBitset* b, ZixBitsetTally* t, size_t i)
-{
- const size_t e = i / ZIX_BITSET_ELEM_BIT;
- const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
- const ZixBitset mask = (ZixBitset)1 << ebit;
- const bool is_set = (b[e] & mask);
-
- t[e] = (ZixBitsetTally)(t[e] + !is_set);
- b[e] |= mask;
-}
-
-void
-zix_bitset_reset(ZixBitset* b, ZixBitsetTally* t, size_t i)
-{
- const size_t e = i / ZIX_BITSET_ELEM_BIT;
- const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
- const ZixBitset mask = (ZixBitset)1 << ebit;
- const bool is_set = b[e] & mask;
-
- t[e] = (ZixBitsetTally)(t[e] - is_set);
- b[e] &= ~mask;
-}
-
-bool
-zix_bitset_get(const ZixBitset* b, size_t i)
-{
- const size_t e = i / ZIX_BITSET_ELEM_BIT;
- const size_t ebit = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
- const ZixBitset mask = (ZixBitset)1 << ebit;
-
- return b[e] & mask;
-}
-
-size_t
-zix_bitset_count_up_to(const ZixBitset* b, const ZixBitsetTally* t, size_t i)
-{
- const size_t full_elems = i / ZIX_BITSET_ELEM_BIT;
- const size_t extra = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
-
- size_t count = 0;
- for (size_t e = 0; e < full_elems; ++e) {
- count += t[e];
- }
-
- if (extra) {
- const ZixBitset mask = ~(~(ZixBitset)0U << extra);
- count += zix_bitset_popcount(b[full_elems] & mask);
- }
-
- return count;
-}
-
-size_t
-zix_bitset_count_up_to_if(const ZixBitset* b, const ZixBitsetTally* t, size_t i)
-{
- const size_t full_elems = i / ZIX_BITSET_ELEM_BIT;
- const size_t extra = i & (ZIX_BITSET_ELEM_BIT - 1); // i % ELEM_BIT
-
- const ZixBitset get_mask = (ZixBitset)1 << extra;
- if (!(b[full_elems] & get_mask)) {
- return (size_t)-1;
- }
-
- size_t count = 0;
- for (size_t e = 0; e < full_elems; ++e) {
- count += t[e];
- }
-
- if (extra) {
- const ZixBitset mask = ~(~(ZixBitset)0 << extra);
- count += zix_bitset_popcount(b[full_elems] & mask);
- }
-
- return count;
-}
diff --git a/test/cpp/test_headers_cpp.cpp b/test/cpp/test_headers_cpp.cpp
index d637988..3fabe6e 100644
--- a/test/cpp/test_headers_cpp.cpp
+++ b/test/cpp/test_headers_cpp.cpp
@@ -7,7 +7,6 @@
#include "zix/allocator.h" // IWYU pragma: keep
#include "zix/attributes.h" // IWYU pragma: keep
-#include "zix/bitset.h" // IWYU pragma: keep
#include "zix/btree.h" // IWYU pragma: keep
#include "zix/bump_allocator.h" // IWYU pragma: keep
#include "zix/digest.h" // IWYU pragma: keep
diff --git a/test/headers/test_headers.c b/test/headers/test_headers.c
index 265c9a2..a610600 100644
--- a/test/headers/test_headers.c
+++ b/test/headers/test_headers.c
@@ -3,7 +3,6 @@
#include "zix/allocator.h" // IWYU pragma: keep
#include "zix/attributes.h" // IWYU pragma: keep
-#include "zix/bitset.h" // IWYU pragma: keep
#include "zix/btree.h" // IWYU pragma: keep
#include "zix/bump_allocator.h" // IWYU pragma: keep
#include "zix/digest.h" // IWYU pragma: keep
diff --git a/test/test_bitset.c b/test/test_bitset.c
deleted file mode 100644
index 67f6567..0000000
--- a/test/test_bitset.c
+++ /dev/null
@@ -1,71 +0,0 @@
-// Copyright 2014-2020 David Robillard <d@drobilla.net>
-// SPDX-License-Identifier: ISC
-
-#undef NDEBUG
-
-#include "zix/bitset.h"
-
-#include <assert.h>
-#include <stddef.h>
-
-#define N_BITS 256U
-#define N_ELEMS (ZIX_BITSET_ELEMS(N_BITS))
-
-#define MIN(a, b) (((a) < (b)) ? (a) : (b))
-
-int
-main(void)
-{
- ZixBitset b[N_ELEMS];
- ZixBitsetTally t[N_ELEMS];
-
- zix_bitset_clear(b, t, N_BITS);
- assert(zix_bitset_count_up_to(b, t, N_BITS) == 0);
-
- for (size_t i = 0; i < N_BITS; ++i) {
- zix_bitset_set(b, t, i);
- assert(zix_bitset_get(b, i));
-
- const size_t count = zix_bitset_count_up_to(b, t, N_BITS);
- assert(count == i + 1);
- }
-
- for (size_t i = 0; i <= N_BITS; ++i) {
- const size_t count = zix_bitset_count_up_to(b, t, i);
- assert(count == i);
- }
-
- for (size_t i = 0; i <= N_BITS; ++i) {
- if (i < N_BITS) {
- zix_bitset_reset(b, t, i);
- }
-
- const size_t count = zix_bitset_count_up_to(b, t, i);
- assert(count == 0);
- }
-
- zix_bitset_clear(b, t, N_BITS);
- for (size_t i = 0; i < N_BITS; i += 2) {
- zix_bitset_set(b, t, i);
-
- const size_t count = zix_bitset_count_up_to(b, t, i + 1);
- const size_t result = MIN(N_BITS / 2, i / 2 + 1);
-
- assert(count == result);
- }
-
- zix_bitset_clear(b, t, N_BITS);
- for (size_t i = 0; i < N_BITS; ++i) {
- if (i % 2 == 0) {
- zix_bitset_set(b, t, i);
-
- const size_t count = zix_bitset_count_up_to_if(b, t, i);
- const size_t result = MIN(N_BITS / 2, i / 2);
- assert(count == result);
- } else {
- assert(zix_bitset_count_up_to_if(b, t, i) == (size_t)-1);
- }
- }
-
- return 0;
-}
generated by cgit v1.2.1 (git 2.18.0) at 2024-06-30 07:22:26 +0000