Skip to content

Instantly share code, notes, and snippets.

@lhuemill

lhuemill/.gitignore

Last active August 14, 2020 11:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lhuemill/3fdcdd2f74635fab566f5e2ecc9b1dce to your computer and use it in GitHub Desktop.
Save lhuemill/3fdcdd2f74635fab566f5e2ecc9b1dce to your computer and use it in GitHub Desktop.
Download ZIP
sparsebit_c - A C-Language Implementation of a Sparse Bit Array
Raw
.gitignore
*.swp
build/
target/
Raw
LICENSE
Apache License
Version 2.0, January 2004
http://www.apache.org/licenses/
TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
1. Definitions.
"License" shall mean the terms and conditions for use, reproduction,
and distribution as defined by Sections 1 through 9 of this document.
"Licensor" shall mean the copyright owner or entity authorized by
the copyright owner that is granting the License.
"Legal Entity" shall mean the union of the acting entity and all
other entities that control, are controlled by, or are under common
control with that entity. For the purposes of this definition,
"control" means (i) the power, direct or indirect, to cause the
direction or management of such entity, whether by contract or
otherwise, or (ii) ownership of fifty percent (50%) or more of the
outstanding shares, or (iii) beneficial ownership of such entity.
"You" (or "Your") shall mean an individual or Legal Entity
exercising permissions granted by this License.
"Source" form shall mean the preferred form for making modifications,
including but not limited to software source code, documentation
source, and configuration files.
"Object" form shall mean any form resulting from mechanical
transformation or translation of a Source form, including but
not limited to compiled object code, generated documentation,
and conversions to other media types.
"Work" shall mean the work of authorship, whether in Source or
Object form, made available under the License, as indicated by a
copyright notice that is included in or attached to the work
(an example is provided in the Appendix below).
"Derivative Works" shall mean any work, whether in Source or Object
form, that is based on (or derived from) the Work and for which the
editorial revisions, annotations, elaborations, or other modifications
represent, as a whole, an original work of authorship. For the purposes
of this License, Derivative Works shall not include works that remain
separable from, or merely link (or bind by name) to the interfaces of,
the Work and Derivative Works thereof.
"Contribution" shall mean any work of authorship, including
the original version of the Work and any modifications or additions
to that Work or Derivative Works thereof, that is intentionally
submitted to Licensor for inclusion in the Work by the copyright owner
or by an individual or Legal Entity authorized to submit on behalf of
the copyright owner. For the purposes of this definition, "submitted"
means any form of electronic, verbal, or written communication sent
to the Licensor or its representatives, including but not limited to
communication on electronic mailing lists, source code control systems,
and issue tracking systems that are managed by, or on behalf of, the
Licensor for the purpose of discussing and improving the Work, but
excluding communication that is conspicuously marked or otherwise
designated in writing by the copyright owner as "Not a Contribution."
"Contributor" shall mean Licensor and any individual or Legal Entity
on behalf of whom a Contribution has been received by Licensor and
subsequently incorporated within the Work.
2. Grant of Copyright License. Subject to the terms and conditions of
this License, each Contributor hereby grants to You a perpetual,
worldwide, non-exclusive, no-charge, royalty-free, irrevocable
copyright license to reproduce, prepare Derivative Works of,
publicly display, publicly perform, sublicense, and distribute the
Work and such Derivative Works in Source or Object form.
3. Grant of Patent License. Subject to the terms and conditions of
this License, each Contributor hereby grants to You a perpetual,
worldwide, non-exclusive, no-charge, royalty-free, irrevocable
(except as stated in this section) patent license to make, have made,
use, offer to sell, sell, import, and otherwise transfer the Work,
where such license applies only to those patent claims licensable
by such Contributor that are necessarily infringed by their
Contribution(s) alone or by combination of their Contribution(s)
with the Work to which such Contribution(s) was submitted. If You
institute patent litigation against any entity (including a
cross-claim or counterclaim in a lawsuit) alleging that the Work
or a Contribution incorporated within the Work constitutes direct
or contributory patent infringement, then any patent licenses
granted to You under this License for that Work shall terminate
as of the date such litigation is filed.
4. Redistribution. You may reproduce and distribute copies of the
Work or Derivative Works thereof in any medium, with or without
modifications, and in Source or Object form, provided that You
meet the following conditions:
(a) You must give any other recipients of the Work or
Derivative Works a copy of this License; and
(b) You must cause any modified files to carry prominent notices
stating that You changed the files; and
(c) You must retain, in the Source form of any Derivative Works
that You distribute, all copyright, patent, trademark, and
attribution notices from the Source form of the Work,
excluding those notices that do not pertain to any part of
the Derivative Works; and
(d) If the Work includes a "NOTICE" text file as part of its
distribution, then any Derivative Works that You distribute must
include a readable copy of the attribution notices contained
within such NOTICE file, excluding those notices that do not
pertain to any part of the Derivative Works, in at least one
of the following places: within a NOTICE text file distributed
as part of the Derivative Works; within the Source form or
documentation, if provided along with the Derivative Works; or,
within a display generated by the Derivative Works, if and
wherever such third-party notices normally appear. The contents
of the NOTICE file are for informational purposes only and
do not modify the License. You may add Your own attribution
notices within Derivative Works that You distribute, alongside
or as an addendum to the NOTICE text from the Work, provided
that such additional attribution notices cannot be construed
as modifying the License.
You may add Your own copyright statement to Your modifications and
may provide additional or different license terms and conditions
for use, reproduction, or distribution of Your modifications, or
for any such Derivative Works as a whole, provided Your use,
reproduction, and distribution of the Work otherwise complies with
the conditions stated in this License.
5. Submission of Contributions. Unless You explicitly state otherwise,
any Contribution intentionally submitted for inclusion in the Work
by You to the Licensor shall be under the terms and conditions of
this License, without any additional terms or conditions.
Notwithstanding the above, nothing herein shall supersede or modify
the terms of any separate license agreement you may have executed
with Licensor regarding such Contributions.
6. Trademarks. This License does not grant permission to use the trade
names, trademarks, service marks, or product names of the Licensor,
except as required for reasonable and customary use in describing the
origin of the Work and reproducing the content of the NOTICE file.
7. Disclaimer of Warranty. Unless required by applicable law or
agreed to in writing, Licensor provides the Work (and each
Contributor provides its Contributions) on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied, including, without limitation, any warranties or conditions
of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
PARTICULAR PURPOSE. You are solely responsible for determining the
appropriateness of using or redistributing the Work and assume any
risks associated with Your exercise of permissions under this License.
8. Limitation of Liability. In no event and under no legal theory,
whether in tort (including negligence), contract, or otherwise,
unless required by applicable law (such as deliberate and grossly
negligent acts) or agreed to in writing, shall any Contributor be
liable to You for damages, including any direct, indirect, special,
incidental, or consequential damages of any character arising as a
result of this License or out of the use or inability to use the
Work (including but not limited to damages for loss of goodwill,
work stoppage, computer failure or malfunction, or any and all
other commercial damages or losses), even if such Contributor
has been advised of the possibility of such damages.
9. Accepting Warranty or Additional Liability. While redistributing
the Work or Derivative Works thereof, You may choose to offer,
and charge a fee for, acceptance of support, warranty, indemnity,
or other liability obligations and/or rights consistent with this
License. However, in accepting such obligations, You may act only
on Your own behalf and on Your sole responsibility, not on behalf
of any other Contributor, and only if You agree to indemnify,
defend, and hold each Contributor harmless for any liability
incurred by, or claims asserted against, such Contributor by reason
of your accepting any such warranty or additional liability.
END OF TERMS AND CONDITIONS
APPENDIX: How to apply the Apache License to your work.
To apply the Apache License to your work, attach the following
boilerplate notice, with the fields enclosed by brackets "[]"
replaced with your own identifying information. (Don't include
the brackets!) The text should be enclosed in the appropriate
comment syntax for the file format. We also recommend that a
file or class name and description of purpose be included on the
same "printed page" as the copyright notice for easier
identification within third-party archives.
Copyright [yyyy] [name of copyright owner]
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
Raw
Makefile
#
# sparsebit_c/Makefile
#
# Copyright 2020 Louis Huemiller Jr.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
all: libs tests util
.PHONY: clean
clean: ## Remove build artifacts
rm -rf ./build/ *.pyc __pycache__/ *stackdump
.PHONY: clobber
clobber: clean ## Remove built items and build artifacts
rm -rf ./target/
./build/:
mkdir -p ./build/
./target/:
mkdir -p ./target/
./target/lib/:
mkdir -p ./target/lib/
./target/util/:
mkdir -p ./target/util/
.PHONY: libs
libs: ./build/ ./target/lib/ ./target/lib/libsparsebit_c.a
# Need to touch libsparsebit_c.a after it was created, so that its
# last modification time is later than the last modification time of
# the subdirectory containing it.
./target/lib/libsparsebit_c.a : ./target/lib/ ./build/sparsebit_c.o
ar rc ./target/lib/libsparsebit_c.a ./build/sparsebit_c.o
touch ./target/lib/libsparsebit_c.a
./build/sparsebit_c.o: ./build/ ./sparsebit_c.c ./sparsebit_c.h
gcc -c -std=c99 -o ./build/sparsebit_c.o sparsebit_c.c
.PHONY: tests
tests: ./target/ ./target/test_unit ./target/test_adjacent ./target/test_prand
./target/test_unit: ./test_unit.c ./target/lib/libsparsebit_c.a
gcc -std=c99 -D SB_TEST -o ./target/test_unit ./test_unit.c -L ./target/lib/ -l sparsebit_c -l cunit
./target/test_adjacent: ./test_adjacent.c ./target/lib/libsparsebit_c.a
gcc -std=c99 -D SB_TEST -o ./target/test_adjacent ./test_adjacent.c -L ./target/lib/ -l sparsebit_c -l cunit
./target/test_prand: ./test_prand.c ./target/lib/libsparsebit_c.a
gcc -std=c99 -D SB_TEST -o ./target/test_prand ./test_prand.c -L ./target/lib/ -l sparsebit_c -l cunit
.PHONY: util
util: ./target/ ./target/util/ ./target/util/op_sieve
./target/util/op_sieve: ./op_sieve.c ./target/lib/libsparsebit_c.a
gcc -g -std=c99 -D SB_TEST -o ./target/util/op_sieve ./op_sieve.c -L ./target/lib/ -l sparsebit_c
.PHONY: smoketest
smoketest: tests
./target/test_unit
./target/test_adjacent
./target/test_prand 0 999
.PHONY: presubmit
presubmit: smoketest
./target/test_adjacent -n4
./target/test_prand 0 99999
Raw
op_sieve.c
/* Copyright 2020 Louis Huemiller Jr.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#define _POSIX_C_SOURCE 200809L // For getline(3) and ssize_t
#include <argz.h> // Included for definition of error_t on Arm based systems.
#include <assert.h>
#include <errno.h>
#include <malloc.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include "sparsebit_c.h"
#define NUM(a) (sizeof(a)/sizeof((a)[0]))
#define MEMCLEAR(p, n) memset((p), 0, (n))
#define PREFIX_HEX "0x"
#define PREFIX_IDX "idx: "
#define PREFIX_NUM "num: "
#define PREFIX_NTH_IDX "nth_idx: "
enum OP {
SET_BIT = 132,
SET_NUM,
CLEAR_BIT,
CLEAR_NUM,
QUERY_ANYSET,
QUERY_NUMSET,
QUERY_ISSET,
QUERY_FIRSTSET,
QUERY_NEXTSET,
QUERY_PREVSET,
QUERY_ANYCLEARED,
QUERY_NUMCLEARED,
QUERY_ISCLEARED,
QUERY_FIRSTCLEARED,
QUERY_NEXTCLEARED,
QUERY_PREVCLEARED,
QUERY_NTHSET,
};
struct op_trait {
enum OP op;
char *nemonic;
} op_traits[] = {
{SET_BIT, "SET_BIT"},
{SET_NUM, "SET_NUM"},
{CLEAR_BIT, "CLEAR_BIT"},
{CLEAR_NUM, "CLEAR_NUM"},
{QUERY_ANYSET, "QUERY_ANYSET"},
{QUERY_NUMSET, "QUERY_NUMSET"},
{QUERY_ISSET, "QUERY_ISSET"},
{QUERY_FIRSTSET, "QUERY_FIRSTSET"},
{QUERY_NEXTSET, "QUERY_NEXTSET"},
{QUERY_PREVSET, "QUERY_PREVSET"},
{QUERY_ANYCLEARED, "QUERY_ANYCLEARED"},
{QUERY_NUMCLEARED, "QUERY_NUMCLEARED"},
{QUERY_ISCLEARED, "QUERY_ISCLEARED"},
{QUERY_FIRSTCLEARED, "QUERY_FIRSTCLEARED"},
{QUERY_NEXTCLEARED, "QUERY_NEXTCLEARED"},
{QUERY_PREVCLEARED, "QUERY_PREVCLEARED"},
{QUERY_NTHSET, "QUERY_NTHSET"},
};
struct operation {
enum OP op;
sb_idx_t idx;
sb_num_t num;
sb_idx_t nth_idx;
bool perform;
char *line;
size_t trait_idx;
};
struct operation *operations = NULL;
size_t operations_num = 0;
static void perform_operations(sb_t *sb);
static sb_pdynstr_t validate(sb_t *sb);
static sb_idx_t ops_ranges_idx_first(void);
static sb_idx_t ops_ranges_idx_next(sb_idx_t idx);
static bool ops_performed_any(void);
static bool ops_expected_isset(sb_idx_t idx);
static sb_num_t ops_expected_numset(void);
static sb_idx_t ops_expected_nextset(sb_idx_t idx_start);
static sb_idx_t ops_expected_nextcleared(sb_idx_t idx_start);
static sb_idx_t ops_expected_prevset(sb_idx_t idx_start);
static sb_idx_t ops_expected_prevcleared(sb_idx_t idx_start);
static sb_idx_t ops_expected_nthset(sb_idx_t nth_idx);
int main(void)
{
char *chptr, *endptr;
struct operation *opptr;
char *line = NULL;
size_t line_sz = 0;
ssize_t len; // Does not include trailing '\0'.
sb_pdynstr_t err_string;
operations = malloc(sizeof(struct operation) * operations_num);
if (operations == NULL) {
fputs("Insufficient Memory\n", stderr);
exit(1);
}
do {
// Read next line from stdin.
if (line != NULL) {
free(line);
line = NULL;
}
len = getline(&line, &line_sz, stdin);
if (len == -1) {
if (errno == 0) {
break;
}
printf("getline error errno: %i\n", errno);
exit(1);
}
// If present, remove trailing newline.
if ((len > 1) && (line[len - 1] == '\n')) {
line[len - 1] = '\0';
len--;
}
// Ignore lines that begin with a '#'.
if ((len >= 1) && (line[0] == '#')) {
continue;
}
// Determine opcode based on finding its nemonic in the line.
struct op_trait *traits = NULL;
size_t trait_idx;
for (trait_idx = 0; trait_idx < NUM(op_traits); trait_idx++) {
traits = &op_traits[trait_idx];
char *nemonic = strstr(line, traits->nemonic);
if (nemonic != NULL) {
break;
}
}
if (trait_idx >= NUM(op_traits)) {
fprintf(stderr, "No opcode nemonic found\n"
" line: %s\n", line);
exit(2);
}
// Determine index if specified on line.
sb_idx_t idx = 0;
chptr = strstr(line, PREFIX_IDX);
if (chptr != NULL) {
if (strncmp(chptr + sizeof(PREFIX_IDX) - 1, PREFIX_HEX,
sizeof(PREFIX_HEX) - 1) == 0) {
idx = strtoull(chptr + sizeof(PREFIX_IDX) - 1
+ sizeof(PREFIX_HEX) - 1, &endptr, 16);
} else {
idx = strtoull(chptr + sizeof(PREFIX_IDX) - 1, &endptr, 10);
}
}
// Determine num if specified on line.
sb_num_t num = 0;
chptr = strstr(line, PREFIX_NUM);
if (chptr != NULL) {
if (strncmp(chptr + sizeof(PREFIX_NUM) - 1, PREFIX_HEX,
sizeof(PREFIX_HEX) - 1) == 0) {
num = strtoull(chptr + sizeof(PREFIX_NUM) - 1
+ sizeof(PREFIX_HEX) - 1, &endptr, 16);
} else {
num = strtoull(chptr + sizeof(PREFIX_NUM) - 1, &endptr, 10);
}
}
// Determine Nth index if specified on line.
sb_idx_t nth_idx = 0;
chptr = strstr(line, PREFIX_NTH_IDX);
if (chptr != NULL) {
if (strncmp(chptr + sizeof(PREFIX_NTH_IDX) - 1, PREFIX_HEX,
sizeof(PREFIX_HEX) - 1) == 0) {
idx = strtoull(chptr + sizeof(PREFIX_NTH_IDX) - 1
+ sizeof(PREFIX_HEX) - 1, &endptr, 16);
} else {
idx = strtoull(chptr + sizeof(PREFIX_NTH_IDX) - 1, &endptr, 10);
}
}
// Add to dynamically allocated array of operations.
operations = realloc(operations,
sizeof(struct operation) * (operations_num + 1));
if (operations == NULL) {
fputs("Insufficient Memory\n", stderr);
exit(5);
}
operations_num++;
opptr = &operations[operations_num - 1];
MEMCLEAR(opptr, sizeof(*opptr));
opptr->line = line;
line = NULL;
opptr->op = traits->op;
opptr->idx = idx;
opptr->num = num;
opptr->trait_idx = traits - op_traits;
} while (true);
// Determine initial minimum sequence of operations that need to
// be performed to create a detected issue.
for (opptr = operations; opptr < operations + operations_num; opptr++) {
opptr->perform = true;
sb_t *sb = sb_create();
if (sb == NULL) {
fputs("Insufficient Memory\n", stderr);
exit(6);
}
perform_operations(sb);
err_string = validate(sb);
if (err_string) {
sb_dynstr_free(err_string);
sb_delete(sb);
break;
}
sb_delete(sb);
}
if (opptr >= (operations + operations_num)) {
// All operations were performed. Was a validate() detected issue
// produced by the final operation? If not, then this sequence of
// operations does not produce a detected issue.
sb_t *sb = sb_create();
if (sb == NULL) {
fputs("Insufficient Memory\n", stderr);
exit(6);
}
perform_operations(sb);
err_string = validate(sb);
if (err_string == NULL) {
fputs("No issue detected, even after executing all operations.\n",
stderr);
exit(7);
} else {
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
// Selectively turn off perform flags for individual operations that
// don't need to be performed to reproduce the validate() issue.
for (opptr = operations; opptr < operations + operations_num; opptr++) {
if (opptr->perform) {
opptr->perform = false;
sb_t *sb = sb_create();
if (sb == NULL) {
fputs("Insufficient Memory\n", stderr);
exit(6);
}
perform_operations(sb);
err_string = validate(sb);
if (err_string == NULL) {
// No issue detected, thus this operation is needed
// to reproduce the detected issue. Turn this operations
// perform flag back on, so as to get back into a state
// that produces the detected issue.
opptr->perform = true;
} else {
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
}
// Display operations that still have perform flag set.
puts("operations:");
for (opptr = operations; opptr < operations + operations_num; opptr++) {
if (opptr->perform) {
puts(opptr->line);
}
}
// Regenerate and display error string.
sb_t *sb = sb_create();
if (sb == NULL) {
fputs("Insufficient Memory\n", stderr);
exit(7);
}
perform_operations(sb);
err_string = validate(sb);
assert(err_string != NULL);
printf("Failed: %s\n", err_string);
sb_dynstr_free(err_string);
sb_delete(sb);
return 0;
}
static void perform_operations(sb_t *sb)
{
for (struct operation *opptr = operations;
opptr < operations + operations_num; opptr++) {
if (opptr->perform) {
sb_idx_t idx = opptr->idx;
sb_num_t num = opptr->num;
sb_idx_t nth_idx = opptr->nth_idx;
switch (opptr->op) {
case SET_BIT:
sb_set(sb, idx);
break;
case SET_NUM:
sb_setnum(sb, idx, num);
break;
case QUERY_ANYSET:
(void) sb_anyset(sb);
break;
case QUERY_NUMSET:
(void) sb_numset(sb);
break;
case QUERY_ISSET:
(void) sb_isset(sb, idx);
break;
case QUERY_FIRSTSET:
(void) sb_firstset(sb);
break;
case QUERY_NEXTSET:
(void) sb_nextset(sb, idx);
break;
case QUERY_PREVSET:
(void) sb_prevset(sb, idx);
break;
case CLEAR_BIT:
sb_clear(sb, idx);
break;
case CLEAR_NUM:
sb_clearnum(sb, idx, num);
break;
case QUERY_ANYCLEARED:
(void) sb_anycleared(sb);
break;
case QUERY_NUMCLEARED:
(void) sb_numcleared(sb);
break;
case QUERY_ISCLEARED:
(void) sb_iscleared(sb, idx);
break;
case QUERY_FIRSTCLEARED:
(void) sb_firstcleared(sb);
case QUERY_NEXTCLEARED:
(void) sb_nextcleared(sb, idx);
break;
case QUERY_PREVCLEARED:
(void) sb_prevcleared(sb, idx);
break;
case QUERY_NTHSET:
(void) sb_nthset(sb, nth_idx);
break;
default:
assert(false); // Unexpected operation
}
}
}
}
sb_pdynstr_t validate(sb_t *sb)
{
// Is the sparse bit array internally consistent?
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string != NULL) {
return err_string;
}
// Correct number set?
sb_num_t expected_numset = ops_expected_numset();
sb_num_t actual_numset = sb_numset(sb);
if (actual_numset != expected_numset) {
return sb_dyn_sprintf("Unexpected numset,\n"
" actual: %#" SB_PRI_NUM " expected: %#" SB_PRI_NUM,
actual_numset, expected_numset);
}
// Do each of the bits, within all the operation ranges,
// have the expected setting?
bool first_pass = true;
for (sb_idx_t idx = ops_ranges_idx_first(); first_pass || idx != 0;
idx = ops_ranges_idx_next(idx)) {
bool expected_isset = ops_expected_isset(idx);
bool actual_isset = sb_isset(sb, idx);
if (actual_isset != expected_isset) {
return sb_dyn_sprintf("Unexpected isset,\n"
" idx: $#" SB_PRI_IDX "actual: %u expected: %u");
}
first_pass = false;
}
// Validate sb_nextset() and sb_nextcleared().
sb_idx_t idx_edge = ops_ranges_idx_first();
do {
for (int offset = -1; offset <= 1; offset++) {
sb_idx_t idx = idx_edge + offset;
sb_idx_t expected_nextset = ops_expected_nextset(idx);
sb_idx_t expected_nextcleared = ops_expected_nextcleared(idx);
sb_idx_t actual_nextset = sb_nextset(sb, idx);
sb_idx_t actual_nextcleared = sb_nextcleared(sb, idx);
if (actual_nextset != expected_nextset) {
return sb_dyn_sprintf("Unexpected nextset,\n"
" idx: %#" SB_PRI_IDX " actual: %#" SB_PRI_IDX
" expected: %#" SB_PRI_IDX,
idx, actual_nextset, expected_nextset);
}
if (actual_nextcleared != expected_nextcleared) {
return sb_dyn_sprintf("Unexpected nextcleared,\n"
" idx: %#" SB_PRI_IDX " actual: %#" SB_PRI_IDX
" expected: %#" SB_PRI_IDX,
idx, actual_nextcleared, expected_nextcleared);
}
}
idx_edge = ops_ranges_idx_next(idx_edge);
} while (idx_edge != 0);
// Validate sb_prevset() and sb_prevcleared().
idx_edge = ops_ranges_idx_first();
do {
for (int offset = -1; offset <= 1; offset++) {
sb_idx_t idx = idx_edge + offset;
sb_idx_t expected_prevset = ops_expected_prevset(idx);
sb_idx_t expected_prevcleared = ops_expected_prevcleared(idx);
sb_idx_t actual_prevset = sb_prevset(sb, idx);
sb_idx_t actual_prevcleared = sb_prevcleared(sb, idx);
if (actual_prevset != expected_prevset) {
return sb_dyn_sprintf("Unexpected prevset,\n"
" idx: %#" SB_PRI_IDX " actual: %#" SB_PRI_IDX
" expected: %#" SB_PRI_IDX,
idx, actual_prevset, expected_prevset);
}
if (actual_prevcleared != expected_prevcleared) {
return sb_dyn_sprintf("Unexpected prevcleared,\n"
" idx: %#" SB_PRI_IDX " actual: %#" SB_PRI_IDX
" expected: %#" SB_PRI_IDX,
idx, actual_prevcleared, expected_prevcleared);
}
}
idx_edge = ops_ranges_idx_next(idx_edge);
} while (idx_edge != 0);
// Validate sb_nthset() for nth index of each set bit, plus
// 3 beyond the number of set bits.
for (sb_idx_t nth_idx = 0; nth_idx <= ops_expected_numset() + 3; nth_idx++) {
sb_idx_t expected_rv = ops_expected_nthset(nth_idx);
error_t orig_errno = ESRCH + 5;
error_t expected_errno = (nth_idx < ops_expected_numset())
? orig_errno : ESRCH;
errno = orig_errno;
sb_idx_t actual_rv = sb_nthset(sb, nth_idx);
error_t actual_errno = errno;
if (actual_rv != expected_rv) {
return sb_dyn_sprintf("Unexpected nthset rv,\n"
" nth_idx: %#" SB_PRI_IDX " actual_rv: %#" SB_PRI_IDX
" expected_rv: %#" SB_PRI_IDX,
nth_idx, actual_rv, expected_rv);
}
if (actual_errno != expected_errno) {
return sb_dyn_sprintf("Unexpected nthset errno,\n"
" nth_idx: %#" SB_PRI_IDX " actual_errno: %u"
" expected_errno: %u",
nth_idx, actual_errno, expected_errno);
}
}
return NULL;
}
static sb_idx_t ops_ranges_idx_first(void)
{
sb_idx_t first_idx = SB_IDX_MAX;
for (struct operation *opptr = operations;
opptr < operations + operations_num; opptr++) {
// Skip operations that are not to be performed.
if (!opptr->perform) {
continue;
}
if (opptr->idx < first_idx) {
first_idx = opptr->idx;
}
}
return first_idx;
}
static sb_idx_t ops_ranges_idx_next(sb_idx_t idx)
{
bool found = false;
sb_idx_t next_idx = SB_IDX_MAX;
if (idx == SB_IDX_MAX) {
return 0;
}
for (struct operation *opptr = operations;
opptr < operations + operations_num; opptr++) {
// Skip operations that are not to be performed.
if (!opptr->perform) {
continue;
}
sb_idx_t start = opptr->idx;
sb_idx_t end = start + ((opptr->num == 0) ? 1 : opptr->num) - 1;
if (end > idx) {
if (start <= idx) {
return idx + 1;
}
if (!found || (start < next_idx)) {
next_idx = start;
found = true;
}
}
}
return (found) ? next_idx : 0;
}
static bool ops_performed_any(void)
{
for (struct operation *opptr = operations;
opptr < operations + operations_num; opptr++) {
if (opptr->perform) {
return true;
}
}
return false;
}
static bool ops_expected_isset(sb_idx_t idx)
{
bool isset = false;
for (struct operation *opptr = operations;
opptr < operations + operations_num; opptr++) {
// Skip operations that are not to be performed.
if (!opptr->perform) {
continue;
}
switch (opptr->op) {
case SET_BIT:
if (opptr->idx == idx) {
isset = true;
}
break;
case SET_NUM:
if ((idx >= opptr->idx) && (idx <= (opptr->idx + opptr->num - 1))) {
isset = true;
}
break;
case CLEAR_BIT:
if (opptr->idx == idx) {
isset = false;
}
break;
case CLEAR_NUM:
if ((idx >= opptr->idx) && (idx <= (opptr->idx + opptr->num - 1))) {
isset = false;
}
break;
}
}
return isset;
}
static sb_num_t ops_expected_numset(void)
{
sb_num_t num = 0;
sb_idx_t idx = ops_ranges_idx_first();
do {
if (ops_expected_isset(idx)) {
num++;
}
idx = ops_ranges_idx_next(idx);
} while (idx != 0);
return num;
}
static sb_idx_t ops_expected_nextset(sb_idx_t idx_start)
{
sb_idx_t idx_edge = ops_ranges_idx_first();
do {
for (int offset = -1; offset <= 1; offset++) {
sb_idx_t idx = idx_edge + offset;
if ((offset > 0) && (idx < idx_edge)) {
continue;
}
if ((offset < 0) && (idx > idx_edge)) {
continue;
}
if (idx <= idx_start) {
continue;
}
if (ops_expected_isset(idx)) {
return idx;
}
}
idx_edge = ops_ranges_idx_next(idx_edge);
} while (idx_edge != 0);
return 0;
}
static sb_idx_t ops_expected_nextcleared(sb_idx_t idx_start)
{
if (!ops_performed_any()) {
return idx_start + 1;
}
if (!ops_expected_isset(idx_start + 1)) {
return idx_start + 1;
}
sb_idx_t idx_edge = ops_ranges_idx_first();
do {
for (int offset = -1; offset <= 1; offset++) {
sb_idx_t idx = idx_edge + offset;
if ((offset > 0) && (idx < idx_edge)) {
continue;
}
if ((offset < 0) && (idx > idx_edge)) {
continue;
}
if (idx <= idx_start) {
continue;
}
if (!ops_expected_isset(idx)) {
return idx;
}
}
idx_edge = ops_ranges_idx_next(idx_edge);
} while (idx_edge != 0);
return 0;
}
static sb_idx_t ops_expected_prevset(sb_idx_t idx_start)
{
sb_idx_t idx_rv = 0;
sb_idx_t idx_edge = ops_ranges_idx_first();
do {
for (int offset = -1; offset <= 1; offset++) {
sb_idx_t idx = idx_edge + offset;
if ((offset > 0) && (idx < idx_edge)) {
continue;
}
if ((offset < 0) && (idx > idx_edge)) {
continue;
}
if (idx >= idx_start) { break; }
if (ops_expected_isset(idx)) {
if (idx > idx_rv) {
idx_rv = idx;
}
}
}
idx_edge = ops_ranges_idx_next(idx_edge);
} while (idx_edge != 0);
return idx_rv;
}
static sb_idx_t ops_expected_prevcleared(sb_idx_t idx_start)
{
sb_idx_t idx_rv = 0;
if (idx_start == 0) { return 0; }
if (!ops_expected_isset(idx_start - 1)) { idx_rv = idx_start - 1; }
sb_idx_t idx_edge = ops_ranges_idx_first();
do {
for (int offset = -1; offset <= 1; offset++) {
sb_idx_t idx = idx_edge + offset;
if ((offset > 0) && (idx < idx_edge)) {
continue;
}
if ((offset < 0) && (idx > idx_edge)) {
continue;
}
if (idx >= idx_start) { break; }
if (!ops_expected_isset(idx)) {
if (idx > idx_rv) {
idx_rv = idx;
}
}
}
idx_edge = ops_ranges_idx_next(idx_edge);
} while (idx_edge != 0);
return idx_rv;
}
static sb_idx_t ops_expected_nthset(sb_idx_t nth_idx)
{
if (nth_idx >= ops_expected_numset()) {
return 0;
}
sb_idx_t idx = (ops_expected_isset(0)) ? 0 : ops_expected_nextset(0);
sb_num_t num = 0;
while ((num < nth_idx) && ((num + 1) < ops_expected_numset())) {
idx = ops_expected_nextset(idx);
num++;
}
return idx;
}
Raw
sparsebit_c.c
/* Copyright 2020 Louis Huemiller Jr.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include <assert.h>
#include <errno.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define SB_TEST
#include "sparsebit_c.h"
#define BITS_PER_BYTE 8
#define MEMCLEAR(p, n) memset((p), 0, (n))
// Complete definition of sparsebit root structure.
struct node;
typedef struct node node_t;
struct sb {
node_t *root;
node_t *hint;
};
enum node_color {
BLACK = false,
RED = true,
};
typedef uint64_t mask_t;
#define NODE_PRI_MASK PRIx64
#define NUM_MASK_BITS (sizeof(mask_t) * BITS_PER_BYTE)
#define MASK_BOUNDARY(idx) ((idx) - ((idx) % NUM_MASK_BITS))
struct node {
sb_idx_t idx_start; // Index of first bit in mask.
mask_t mask;
sb_num_t set_after; // Number of contiguously set bits, after last mask bit.
sb_num_t num_set_subtree; // Number of bits set in this node plus all of
// its children, even children of children.
// Note: Nodes always have at least 1 set bit,
// so a num_set_subtree value of 0, actually
// represents SB_NUM_MAX + 1 set bits.
enum node_color color;
node_t *parent;
node_t *left;
node_t *right;
};
static node_t *node_find(sb_t *sb, sb_idx_t idx);
static node_t *node_find_or_next(sb_t *sb, sb_idx_t idx);
static node_t *node_find_or_prev(sb_t *sb, sb_idx_t idx);
static node_t *node_find_or_create(sb_t *sb, sb_idx_t idx);
static const node_t *node_find_const(const sb_t *sb_const, sb_idx_t idx);
static const node_t *node_find_or_next_const(const sb_t *sb_const,
sb_idx_t idx);
static const node_t *node_find_or_prev_const(const sb_t *sb_const,
sb_idx_t idx);
static bool node_supports_idx(const node_t *node, sb_idx_t idx);
static int node_cmp(node_t *node1, node_t *node2);
static int node_cmp_idx(node_t *node, sb_idx_t idx);
static bool node_prev_adj(node_t *node);
static node_t *node_split(sb_t *sb, node_t *node, sb_idx_t at);
static void node_merge(sb_t *sb, node_t *prev, node_t *next);
static void node_adjacent_fixup(sb_t *sb, sb_idx_t idx_start, sb_idx_t idx_end);
static bool node_any_set(const node_t *node);
static bool mask_any_set(mask_t mask);
static bool mask_only_leading(mask_t mask);
static unsigned int num_set_mask(mask_t mask);
static sb_num_t num_set_node(const node_t *node);
static sb_num_t num_set_subtree(const node_t *node);
static void num_set_adjust(node_t *node, sb_num_t amt, bool positive);
static bool node_is_bud(node_t *node);
static unsigned int node_depth(const node_t *node);
static unsigned int node_depth_black(const node_t *node);
static node_t *node_sibling(node_t *node);
static node_t *node_grandparent(node_t *node);
static node_t *node_uncle(node_t *node);
static node_t *node_minimum(node_t *node);
static node_t *node_maximum(node_t *node);
static node_t *node_next(node_t *node);
static node_t *node_prev(node_t *node);
static const node_t *node_minimum_const(const node_t *nodep_const);
static const node_t *node_maximum_const(const node_t *nodep_const);
static const node_t *node_next_const(const node_t *nodep_const);
static const node_t *node_prev_const(const node_t *nodep_const);
static void node_rotate_left(sb_t *sb, node_t *x);
static void node_rotate_right(sb_t *sb, node_t *x);
static void node_transplant(sb_t *sb, node_t *u, node_t *v);
static void node_insert(sb_t *sb, node_t *parent, node_t *node);
static void node_delete(sb_t *sb, node_t *node);
static void node_delete_fixup(sb_t *sb, node_t *node);
static sb_pdynstr_t dump_subtree(const sb_t *sb, const node_t *node,
unsigned int indent);
sb_t *sb_create(void)
{
sb_t *p = calloc(1, sizeof(sb_t));
if (p == NULL) {
errno = ENOMEM;
return NULL;
}
return p;
}
void sb_delete(sb_t* sb)
{
while (sb->root) {
sb->root->mask = 0;
sb->root->set_after = 0;
node_delete(sb, sb->root);
}
free(sb);
}
int sb_copy(sb_t *dest, const sb_t *src)
{
// Nothing to do if source and destination are the same.
if (src == dest) {
return 0;
}
// Delete any nodes that currently exist at destination.
while (dest->root) {
node_delete(dest, dest->root);
}
dest->hint = NULL;
// For each node in the source, create and add to source a
// duplicate of the node.
if (src->root != NULL) {
for (const node_t *node_src = node_minimum(src->root);
// TODO: create const version of node_next().
node_src != NULL; node_src = (const node_t *) node_next(
(node_t *) node_src)) {
node_t *node_dest = calloc(1, sizeof(node_t));
node_dest->idx_start = node_src->idx_start;
node_dest->mask = node_src->mask;
node_dest->set_after = node_src->set_after;
node_t *parent = dest->root;
while (parent != NULL) {
assert(!node_supports_idx(parent, node_dest->idx_start));
if (node_dest->idx_start < parent->idx_start) {
if (parent->left) {
parent = parent->left;
continue;
} else {
break;
}
} else {
if (parent->right) {
parent = parent->right;
continue;
} else {
break;
}
}
}
node_insert(dest, parent, node_dest);
}
}
return 0;
}
// ==== Set Operations
int sb_set(sb_t* sb, sb_idx_t idx)
{
sb_idx_t idx_boundary = MASK_BOUNDARY(idx);
node_t *node = node_find_or_create(sb, idx_boundary);
if (node == NULL) {
errno = ENOMEM;
return -1;
}
// Is idx beyond nodes mask bits (e.g. part of set_after)?
if ((idx - node->idx_start) >= NUM_MASK_BITS) {
// Is the bit already set?
if (idx <= (node->idx_start + NUM_MASK_BITS + node->set_after - 1)) {
return 0;
}
// Is bit just 1 beyond the bits described by the node's set_after value?
if (idx == (node->idx_start + NUM_MASK_BITS + node->set_after)) {
node->set_after++;
num_set_adjust(node, 1, true);
node_adjacent_fixup(sb, idx, idx);
return 0;
}
// Gap between last bit set via node->set_after and index of bit
// to be set.
node = node_split(sb, node, MASK_BOUNDARY(idx));
if (node == NULL) {
errno = ENOMEM;
return -1;
}
}
mask_t mask = (mask_t)1 << (idx - node->idx_start);
if ((node->mask & mask) == 0) {
node->mask |= mask;
num_set_adjust(node, 1, true);
}
node_adjacent_fixup(sb, idx, idx);
return 0;
}
int sb_setnum(sb_t* sb, sb_idx_t idx_start, sb_num_t num)
{
if (num == 0) {
return 0;
}
// Does range extended beyond the maximum index?
if ((idx_start + num - 1) < idx_start) {
errno = EINVAL;
return -1;
}
node_t *node_start = node_find_or_create(sb, MASK_BOUNDARY(idx_start));
if (node_start == NULL) {
errno = ENOMEM;
return -1;
}
if (idx_start > (node_start->idx_start + NUM_MASK_BITS
+ node_start->set_after - 1)) {
node_start = node_split(sb, node_start, MASK_BOUNDARY(idx_start));
if (node_start == NULL) {
node_adjacent_fixup(sb, idx_start, idx_start + num - 1);
errno = ENOMEM;
return -1;
}
}
sb_idx_t idx_end = idx_start + num - 1;
node_t *node_end = node_find_or_create(sb, MASK_BOUNDARY(idx_end));
if (node_end == NULL) {
// Was a new empty node for the start created? If so, need to
// remove that empty node, before returning the ENOMEM indication
// for the end node.
if (num_set_node(node_start) == 0) {
node_delete(sb, node_start);
}
errno = ENOMEM;
return -1;
}
// TODO: Don't split if end can be handled by just increasing
// the current node_end->set_after value.
if (node_end->idx_start != MASK_BOUNDARY(idx_end)) {
node_t *tmp = node_end;
node_end = node_split(sb, node_end, MASK_BOUNDARY(idx_end));
if (node_end == NULL) {
node_adjacent_fixup(sb, idx_start, idx_start + num - 1);
errno = ENOMEM;
return -1;
}
}
// Remove any intermediate nodes, between the start and end nodes.
while ((node_start != node_end) && (node_next(node_start) != node_end)) {
node_t *node = node_next(node_start);
assert(sb_numset(sb) >= num_set_node(node));
assert(num_set_node(node) >= 1);
num_set_adjust(node, num_set_node(node), false);
node_delete(sb, node);
}
// As needed, set mask bits from the start until the next mask boundary.
sb_idx_t idx = idx_start;
sb_num_t num_mask_set = 0;
while ((idx <= idx_end) && (idx >= idx_start)
&& ((idx - node_start->idx_start) < NUM_MASK_BITS)) {
unsigned int offset = idx - node_start->idx_start;
assert(offset < NUM_MASK_BITS);
mask_t mask = (mask_t)1 << offset;
if ((mask & node_start->mask) == 0) {
node_start->mask |= mask;
num_mask_set++;
}
idx++;
}
num_set_adjust(node_start, num_mask_set, true);
// As needed, handle bits from last mask boundary to ending index.
if (idx <= idx_end) {
idx = (node_end->idx_start > idx_start)
? node_end->idx_start : idx_start;
num_mask_set = 0;
while ((idx <= idx_end) && (idx >= node_end->idx_start)
&& ((idx - node_end->idx_start) < NUM_MASK_BITS)) {
unsigned int offset = idx - node_end->idx_start;
assert(offset < NUM_MASK_BITS);
mask_t mask = (mask_t)1 << offset;
if ((mask & node_end->mask) == 0) {
node_end->mask |= mask;
num_mask_set++;
}
idx++;
}
num_set_adjust(node_end, num_mask_set, true);
}
// If needed, set all bits in gap between start and end nodes.
if (node_start != node_end) {
if ((node_start->idx_start + NUM_MASK_BITS + node_start->set_after)
!= node_end->idx_start) {
assert((node_start->idx_start + NUM_MASK_BITS + node_start->set_after)
< node_end->idx_start);
sb_num_t num = node_end->idx_start - (node_start->idx_start
+ NUM_MASK_BITS + node_start->set_after);
node_start->set_after += num;
num_set_adjust(node_start, num, true);
}
}
node_adjacent_fixup(sb, idx_start, idx_start + num - 1);
return 0;
}
bool sb_anyset(const sb_t* sb)
{
if (sb->root) {
return true;
}
return false;
}
bool sb_allset(const sb_t* sb)
{
if (sb->root && (sb->root->num_set_subtree == 0)) {
assert(sb->root->idx_start == 0);
assert(sb->root->mask == ~((mask_t) 0));
assert(sb->root->set_after == (((sb_num_t) 0) - NUM_MASK_BITS));
assert(sb->root->left == NULL);
assert(sb->root->right == NULL);
return true;
}
return false;
}
sb_num_t sb_numset(const sb_t* sb)
{
return (sb->root != NULL) ? sb->root->num_set_subtree : 0;
}
bool sb_isset(const sb_t* sb, sb_idx_t idx)
{
const node_t *node = node_find_const(sb, idx);
if (node == NULL) {
return false;
}
if ((idx - node->idx_start) < NUM_MASK_BITS) {
return node->mask & ((mask_t)1 << (idx - node->idx_start));
} else {
// Index of bit is within range of bits specified by setting of
// set_after and thus is set.
return true;
}
// NOT REACHED
assert(false);
}
sb_idx_t sb_firstset(const sb_t* sb)
{
if (sb->root != NULL) {
node_t *node = node_minimum(sb->root);
for (sb_idx_t n = 0; n < NUM_MASK_BITS; n++) {
if (node->mask & ((mask_t)1 << n)) {
return node->idx_start + n;
}
}
assert(0); // Node with no mask bits set.
}
return 0;
}
sb_idx_t sb_nextset(const sb_t* sb, sb_idx_t idx)
{
const node_t *node = node_find_or_next_const(sb, idx);
// No node with idx or a node after that, so there is no next set bit.
if (node == NULL) {
return 0;
}
// Does node point to the node supporting idx?
if (node_supports_idx(node, idx)) {
// Is idx within the mask or part of the set_after range?
if ((idx - node->idx_start) < NUM_MASK_BITS) {
// Is there another set bit within the mask beyond the mask bit for the
// idx?
for (unsigned int n = (idx - node->idx_start) + 1;
n < NUM_MASK_BITS; n++) {
if (node->mask & ((mask_t)1 << n)) {
return node->idx_start + n;
}
}
// If there are any set_after bits, return the index of the first
// set_after bit.
if (node->set_after > 0) {
return node->idx_start + NUM_MASK_BITS;
}
} else {
// If there is another set_after bit beyond the one at idx,
// return the index of the next set_after bit.
if (((idx + 1) > idx) && ((idx + 1)
<= (node->idx_start + NUM_MASK_BITS + node->set_after - 1))) {
return idx + 1;
}
}
// Node supports idx, but there are no mask bits beyond the mask bit for
// idx that are set. As such, next set bit beyond idx will be the first
// set bit in the next node.
node = node_next_const(node);
if (node == NULL) {
return 0;
}
}
// The node pointer points to the first node after the node supporting
// idx. The first mask bit set in node, will be for the first set bit
// after idx.
for (unsigned int n = 0; n < NUM_MASK_BITS; n++) {
if (node->mask & ((mask_t)1 << n)) {
return node->idx_start + n;
}
}
assert(0); // Node with no mask bits set.
return 0;
}
sb_idx_t sb_prevset(const sb_t* sb, sb_idx_t idx)
{
const node_t *node = node_find_or_prev_const(sb, idx);
// No node with idx or a node prior that, so there is no previously set bit.
if (node == NULL) {
return 0;
}
((sb_t *)sb)->hint = (node_t *) node;
// Does node point to the node supporting idx?
if (node_supports_idx(node, idx)) {
// Is idx part of the node's set_after bits and not
// the first set_after bit?
if ((idx - node->idx_start) > NUM_MASK_BITS) {
return idx - 1;
}
// Idx is either the first set_after bit or within the node's mask.
// If present, return index of first set mask bit before the bit
// of idx.
for (int n = (idx - node->idx_start) - 1; n >= 0; n--) {
if (node->mask & ((mask_t)1 << n)) {
return node->idx_start + n;
}
}
// Node supports idx, but there are no mask bits before the mask bit for
// idx that are set. As such, previous set bit of idx will be the last
// set bit of the previous node.
node = node_prev_const(node);
if (node == NULL) {
return 0;
}
}
// The node pointer points to the first node supporting bits bits idx.
// If that node has any set after bits, return the index to the highest
// set after bit. Otherwise return index of highest set mask bit.
if (node->set_after) {
return node->idx_start + NUM_MASK_BITS + node->set_after - 1;
}
for (int n = NUM_MASK_BITS - 1; n >= 0; n--) {
if (node->mask & ((mask_t)1 << n)) {
return node->idx_start + n;
}
}
assert(0); // Node with no mask bits set.
return 0;
}
// On success returns index of zero-based Nth set bit.
// When there are not enough set bits, errno is set equal to ESRCH
// and an index of 0 is returned.
sb_idx_t sb_nthset(const sb_t* sb, sb_idx_t nth)
{
if ((nth >= sb_numset(sb)) && !sb_allset(sb)) {
errno = ESRCH;
return 0;
}
if (sb_allset(sb)) {
return nth;
}
const node_t *node = sb->root;
assert(node != NULL);
sb_num_t num = nth;
do {
sb_num_t low = (node->left) ? node->left->num_set_subtree
: (node->num_set_subtree
- ((node->right) ? node->right->num_set_subtree : 0)
- num_set_node(node));
sb_num_t high = node->num_set_subtree
- ((node->right) ? node->right->num_set_subtree : 0) - 1;
if (num < low) {
assert(node->left != NULL);
node = node->left;
} else if (num > high) {
sb_num_t amt = node->num_set_subtree - node->right->num_set_subtree;
assert(num >= amt);
num -= amt;
assert(node->right != NULL);
node = node->right;
} else {
unsigned int num_mask_set = 0;
for (unsigned int mask_idx = 0; mask_idx < NUM_MASK_BITS; mask_idx++) {
if (node->mask & ((mask_t)1 << mask_idx)) {
num_mask_set++;
}
if ((num + 1) == (low + num_mask_set)) {
return node->idx_start + mask_idx;
}
}
return (node->idx_start + NUM_MASK_BITS) + (num - (low + num_mask_set));
}
} while (true);
}
// ==== Clear/Cleared Operations
int sb_clear(sb_t* sb, sb_idx_t idx)
{
node_t *node = node_find(sb, idx);
if (node == NULL) {
return 0;
}
// Is bit to be cleared described by nodes set_after value?
if ((idx - node->idx_start) >= NUM_MASK_BITS) {
node = node_split(sb, node, MASK_BOUNDARY(idx));
if (node == NULL) {
errno = ENOMEM;
return -1;
}
}
mask_t mask = (mask_t)1 << (idx - node->idx_start);
if (node->mask & mask) {
node->mask &= ~mask;
num_set_adjust(node, 1, false);
}
// Are all the mask bits cleared?
if (!mask_any_set(node->mask)) {
// If no set_after bits, then just need to delete the node.
if (node->set_after == 0) {
node_delete(sb, node);
node = NULL;
} else {
// Node still has some set_after bits. Move up to NUM_MASK_BITS
// worth of set_after bits into the nodes mask.
assert(node->mask == 0);
assert((node->idx_start + NUM_MASK_BITS) > node->idx_start);
node->idx_start += NUM_MASK_BITS;
for (unsigned int bit_idx = 0; (bit_idx < NUM_MASK_BITS)
&& (node->set_after > 0); bit_idx++) {
node->mask |= (mask_t)1 << bit_idx;
node->set_after--;
}
}
}
sb_idx_t next_set = sb_nextset(sb, idx);
next_set = (next_set == 0) ? SB_IDX_MAX : next_set;
node_adjacent_fixup(sb, idx, next_set);
return 0;
}
int sb_clearnum(sb_t* sb, sb_idx_t idx_start, sb_num_t num)
{
if (num == 0) {
return 0;
}
// Does range extended beyond the maximum index?
sb_idx_t idx_end = idx_start + num - 1;
if ((idx_start + num - 1) < idx_start) {
errno = EINVAL;
return -1;
}
if (sb->root == NULL) {
return 0;
}
node_t *node_start = node_find_or_next(sb, idx_start);
if (node_start == NULL) {
return 0;
}
if (node_start->idx_start > idx_end) {
return 0;
}
// Is idx_start part of the set_after portion of node_start?
// If so, split node_start so that idx_start is within the
// mask portion of a node.
if (node_supports_idx(node_start, idx_start)
&& (idx_start > (node_start->idx_start + NUM_MASK_BITS - 1))) {
node_start = node_split(sb, node_start, MASK_BOUNDARY(idx_start));
if (node_start == NULL) {
node_adjacent_fixup(sb, idx_start, idx_start + num - 1);
errno = ENOMEM;
return -1;
}
}
node_t *node_end = node_find_or_next(sb, MASK_BOUNDARY(idx_end));
// Is idx_end part of the set_after portion of node_end?
// If so, split node_end so that idx_end is within the
// mask portion of a node.
if ((node_end != NULL) && node_supports_idx(node_end, MASK_BOUNDARY(idx_end))
&& (idx_end > (node_end->idx_start + NUM_MASK_BITS - 1))) {
node_end = node_split(sb, node_end, MASK_BOUNDARY(idx_end));
if (node_end == NULL) {
node_adjacent_fixup(sb, idx_start, idx_start + num - 1);
errno = ENOMEM;
return -1;
}
}
// As needed, remove intermediate nodes between node_start and node_end.
while ((node_start != node_end) && (node_next(node_start) != node_end)) {
node_t *node = node_next(node_start);
assert(sb_numset(sb) >= num_set_node(node));
node_delete(sb, node);
}
// Remove node_start in cases where there is no node that supports
// idx_start and node_start doesn't point to the same node as the
// node that supports idx_end. In such cases, node_start will point
// to the next node beyond where a node to support idx_start would be.
if ((node_start != node_end) && !node_supports_idx(node_start, idx_start)) {
assert(sb_numset(sb) >= num_set_node(node_start));
node_delete(sb, node_start);
node_start = node_end;
if (node_start == NULL) {
node_adjacent_fixup(sb, idx_start, idx_start + num - 1);
return 0;
}
}
// As needed, clear mask bits from the start until the next mask boundary.
if ((idx_start >= node_start->idx_start)
&& (idx_start <= (node_start->idx_start + NUM_MASK_BITS - 1))) {
sb_idx_t idx = idx_start;
sb_num_t num_cleared = 0;
while ((idx <= idx_end) && (idx >= idx_start)
&& ((idx - node_start->idx_start) < NUM_MASK_BITS)) {
unsigned int offset = idx - node_start->idx_start;
assert(offset < NUM_MASK_BITS);
mask_t mask = (mask_t)1 << offset;
if ((mask & node_start->mask) != 0) {
node_start->mask &= ~mask;
num_cleared++;
if (!mask_any_set(node_start->mask)) {
break;
}
}
idx++;
}
if ((node_start != node_end) && (node_start->set_after > 0)) {
assert(sb_numset(sb) >= node_start->set_after);
num_cleared += node_start->set_after;
node_start->set_after = 0;
}
num_set_adjust(node_start, num_cleared, false);
if (!mask_any_set(node_start->mask)) {
// If no set_after bits, then just need to delete the node.
if (node_start->set_after == 0) {
node_delete(sb, node_start);
if (node_end == node_start) {
node_end = NULL;
}
node_start = NULL;
} else {
// Node still has some set_after bits. Move up to NUM_MASK_BITS
// worth of set_after bits into the nodes mask.
assert(node_start->mask == 0);
assert((node_start->idx_start + NUM_MASK_BITS)
> node_start->idx_start);
node_start->idx_start += NUM_MASK_BITS;
for (unsigned int bit_idx = 0; (bit_idx < NUM_MASK_BITS)
&& (node_start->set_after > 0); bit_idx++) {
node_start->mask |= (mask_t)1 << bit_idx;
node_start->set_after--;
}
}
}
}
// As needed, handle bits from last mask boundary to ending index.
if ((node_end != NULL)
&& ((node_start != node_end) || (idx_start < node_end->idx_start))) {
sb_idx_t idx = MASK_BOUNDARY(idx_end);
sb_num_t num_cleared = 0;
while ((idx <= idx_end) && (idx >= node_end->idx_start)
&& ((idx - node_end->idx_start) < NUM_MASK_BITS)) {
unsigned int offset = idx - node_end->idx_start;
assert(offset < NUM_MASK_BITS);
mask_t mask = (mask_t)1 << offset;
if ((mask & node_end->mask) != 0) {
node_end->mask &= ~mask;
num_cleared++;
}
if (!mask_any_set(node_end->mask)) {
break;
}
idx++;
}
num_set_adjust(node_end, num_cleared, false);
if (!mask_any_set(node_end->mask)) {
// If no set_after bits, then just need to delete the node.
if (node_end->set_after == 0) {
node_delete(sb, node_end);
node_end = NULL;
} else {
// Node still has some set_after bits. Move up to NUM_MASK_BITS
// worth of set_after bits into the nodes mask.
assert(node_end->mask == 0);
assert((node_end->idx_start + NUM_MASK_BITS)
> node_end->idx_start);
node_end->idx_start += NUM_MASK_BITS;
for (unsigned int bit_idx = 0; (bit_idx < NUM_MASK_BITS)
&& (node_end->set_after > 0); bit_idx++) {
node_end->mask |= (mask_t)1 << bit_idx;
node_end->set_after--;
}
}
}
}
node_adjacent_fixup(sb, idx_start, idx_end);
return 0;
}
bool sb_anycleared(const sb_t* sb)
{
// sb_numcleared() returns 0 both when all bits are set and all bits
// are cleared, because there are a total of ~(sb_num_t)0 + 1 bits.
// With overflow, one more than ~(sb_num_t)0 is 0.
return sb_numcleared(sb) || (sb->root == NULL);
}
sb_num_t sb_numcleared(const sb_t* sb)
{
return (sb_num_t)0 - sb_numset(sb);
}
bool sb_iscleared(const sb_t* sb, sb_idx_t idx)
{
return !sb_isset(sb, idx);
}
sb_idx_t sb_firstcleared(const sb_t* sb)
{
if (sb->root != NULL) {
sb_idx_t prev_node_idx_end = (sb_idx_t)0 - 1;
// First gap in node starting index or a node with a mask that contains
// a cleared bit will determine the index of the first cleared bit.
for (node_t * node = node_minimum(sb->root); node != NULL;
node = node_next(node)) {
// Is there a gap in the node starting index.
if (node->idx_start != (prev_node_idx_end + 1)) {
return prev_node_idx_end + 1;
}
if (node->mask != ~(mask_t)0) {
for (sb_idx_t n = 0; n < NUM_MASK_BITS; n++) {
if ((node->mask & ((mask_t)1 << n)) == 0) {
return node->idx_start + n;
}
}
assert(0); // Cleared bit not found.
}
prev_node_idx_end = node->idx_start + NUM_MASK_BITS + node->set_after - 1;
}
return prev_node_idx_end + 1;
}
return 0;
}
sb_idx_t sb_nextcleared(const sb_t* sb, sb_idx_t idx)
{
if (idx == SB_IDX_MAX) {
return 0;
}
const node_t *node = node_find_const(sb, idx + 1);
if (node == NULL) {
// No node that supports idx.
return idx + 1;
} else {
// Node supports idx + 1. Is there a cleared bit at or beyond the mask
// bit for idx + 1?
for (unsigned int n = (idx + 1) - node->idx_start;
n < NUM_MASK_BITS; n++) {
if ((node->mask & ((mask_t)1 << n)) == 0) {
return node->idx_start + n;
}
}
}
// No cleared bits in mask after mask bit for idx.
// Is there a cleared bit after bits described by next_set and the
// potential next node?
if ((node->set_after % NUM_MASK_BITS) != 0) {
return node->idx_start + NUM_MASK_BITS + node->set_after;
}
// Next cleared bit will be in the the next node with a cleared mask bit
// or first index supported by a gap in the node ranges.
for (sb_idx_t idx2 = node->idx_start + node->set_after
+ (NUM_MASK_BITS - (node->set_after % NUM_MASK_BITS));
idx2 > idx; idx2 += NUM_MASK_BITS) {
node = node_find_const(sb, idx2);
if (node == NULL) {
// Gap in indexes supported by nodes.
return idx2;
} else {
// Any cleared bits in the node?
if (node->mask != ~(mask_t)0) {
for (unsigned int n = 0; n < NUM_MASK_BITS; n++) {
if ((node->mask & ((mask_t)1 << n)) == 0) {
return node->idx_start + n;
}
}
assert(0); // Mask asyncronously changed. No longer has a
// cleared mask bit.
}
// Is there a gap between this and the next node. If so, return
// index of last bit set in this node plus one.
const node_t *node2 = node_next_const(node);
if ((node2 == NULL) || (node2->idx_start != (node->idx_start
+ NUM_MASK_BITS + node->set_after))) {
return node->idx_start + NUM_MASK_BITS + node->set_after;
}
}
}
return 0;
}
sb_idx_t sb_prevcleared(const sb_t* sb, sb_idx_t idx)
{
if (idx == 0) {
return 0;
}
const node_t *node = node_find_const(sb, idx - 1);
if (node == NULL) {
// No node that supports idx - 1.
return idx - 1;
}
((sb_t *)sb)->hint = (node_t *)node;
// Node supports idx - 1. Is there a cleared bit at or before the mask
// bit for idx - 1?
for (int n = (((idx - 1) - node->idx_start) >= NUM_MASK_BITS)
? NUM_MASK_BITS - 1
: (idx - 1) - node->idx_start; n >= 0; n--) {
if ((node->mask & ((mask_t)1 << n)) == 0) {
return node->idx_start + n;
}
}
// No cleared bit in mask before mask bit for idx - 1.
do {
const node_t *prev = node_prev_const(node);
if (prev == NULL) {
return (node->idx_start != 0) ? node->idx_start - 1 : 0;
}
// If there is a gap between current and previous node, return
// starting index of current node minus 1.
if ((prev->idx_start + NUM_MASK_BITS + prev->set_after)
!= node->idx_start) {
assert((prev->idx_start + NUM_MASK_BITS + prev->set_after)
< node->idx_start);
return node->idx_start - 1;
}
for (int n = NUM_MASK_BITS - 1; n >= 0; n--) {
if ((prev->mask & ((mask_t)1 << n)) == 0) {
return prev->idx_start + n;
}
}
node = prev;
} while (node != NULL);
// Is there a cleared bit after bits described by next_set and the
// potential next node?
if ((node->set_after % NUM_MASK_BITS) != 0) {
return node->idx_start + NUM_MASK_BITS + node->set_after;
}
// Next cleared bit will be in the the next node with a cleared mask bit
// or first index supported by a gap in the node ranges.
for (sb_idx_t idx2 = node->idx_start + node->set_after
+ (NUM_MASK_BITS - (node->set_after % NUM_MASK_BITS));
idx2 > idx; idx2 += NUM_MASK_BITS) {
node = node_find_const(sb, idx2);
if (node == NULL) {
// Gap in indexes supported by nodes.
return idx2;
} else {
// Any cleared bits in the node?
if (node->mask != ~(mask_t)0) {
for (unsigned int n = 0; n < NUM_MASK_BITS; n++) {
if ((node->mask & ((mask_t)1 << n)) == 0) {
return node->idx_start + n;
}
}
assert(0); // Mask asyncronously changed. No longer has a
// cleared mask bit.
}
// Is there a gap between this and the next node. If so, return
// index of last bit set in this node plus one.
const node_t *node2 = node_next_const(node);
if ((node2 == NULL) || (node2->idx_start != (node->idx_start
+ NUM_MASK_BITS + node->set_after))) {
return node->idx_start + NUM_MASK_BITS + node->set_after;
}
}
}
return 0;
}
// ==== Sparsebit Node Operations ====
static node_t *node_find(sb_t *sb, sb_idx_t idx)
{
node_t *node;
if ((sb->hint != NULL) && node_supports_idx(sb->hint, idx)) {
return sb->hint;
}
node = sb->root;
while ((node != NULL) && (!node_supports_idx(node, idx))) {
int cmp_rv = node_cmp_idx(node, idx);
assert(cmp_rv != 0); // Only in this loop when node doesn't support idx,
// so why does node->idx_start == idx?
if (cmp_rv > 0) {
node = node->left;
} else {
node = node->right;
}
}
sb->hint = node;
return node;
}
static node_t *node_find_or_next(sb_t *sb, sb_idx_t idx)
{
node_t *node;
if ((sb->hint != NULL) && node_supports_idx(sb->hint, idx)) {
return sb->hint;
}
node = sb->root;
while ((node != NULL) && (!node_supports_idx(node, idx))) {
int cmp_rv = node_cmp_idx(node, idx);
assert(cmp_rv != 0); // Only in this loop when node doesn't support idx,
// so why does node->idx_start == idx?
if (cmp_rv > 0) {
if (node->left == NULL) {
sb->hint = node;
return node;
}
node = node->left;
} else {
if (node->right == NULL) {
node = node_next(node);
sb->hint = node;
return node;
}
node = node->right;
}
}
sb->hint = node;
return node;
}
static node_t *node_find_or_prev(sb_t *sb, sb_idx_t idx)
{
node_t *node;
if ((sb->hint != NULL) && node_supports_idx(sb->hint, idx)) {
return sb->hint;
}
node = sb->root;
while ((node != NULL) && (!node_supports_idx(node, idx))) {
int cmp_rv = node_cmp_idx(node, idx);
assert(cmp_rv != 0); // Only in this loop when node doesn't support idx,
// so why does node->idx_start == idx?
if (cmp_rv > 0) {
if (node->left == NULL) {
node = node_prev(node);
sb->hint = node;
return node;
}
node = node->left;
} else {
if (node->right == NULL) {
sb->hint = node;
return node;
}
node = node->right;
}
}
sb->hint = node;
return node;
}
static node_t *node_find_or_create(sb_t *sb, sb_idx_t idx)
{
node_t *node;
if ((sb->hint != NULL) && node_supports_idx(sb->hint, idx)) {
return sb->hint;
}
// Create root node, if it doesn't already exist.
if (sb->root == NULL) {
node = calloc(1, sizeof(node_t));
node->idx_start = MASK_BOUNDARY(idx);
node_insert(sb, NULL, node);
sb->hint = node;
return node;
}
node = sb->root;
while (!node_supports_idx(node, idx)) {
if (idx < node->idx_start) {
if (node->left) {
node = node->left;
continue;
}
node_t *parent = node;
node_t *child = calloc(1, sizeof(node_t));
if (child != NULL) {
child->idx_start = MASK_BOUNDARY(idx);
node_insert(sb, parent, child);
}
assert((child == NULL) || node_supports_idx(child, idx));
sb->hint = child;
return child;
} else {
if (node->right) {
node = node->right;
continue;
}
node_t *parent = node;
node_t *child = calloc(1, sizeof(node_t));
if (child != NULL) {
child->idx_start = MASK_BOUNDARY(idx);
node_insert(sb, parent, child);
}
assert((child == NULL) || node_supports_idx(child, idx));
sb->hint = child;
return child;
}
}
assert((node != NULL) && node_supports_idx(node, idx));
sb->hint = node;
return node;
}
static const node_t *node_find_const(const sb_t *sb_const, sb_idx_t idx) {
return (const node_t *) node_find((sb_t *) sb_const, idx);
}
static const node_t *node_find_or_next_const(const sb_t *sb_const, sb_idx_t idx)
{
return (const node_t *) node_find_or_next((sb_t *) sb_const, idx);
}
static const node_t *node_find_or_prev_const(const sb_t *sb_const, sb_idx_t idx)
{
return (const node_t *) node_find_or_prev((sb_t *) sb_const, idx);
}
static bool node_supports_idx(const node_t *node, sb_idx_t idx)
{
if ((idx >= node->idx_start)
&& (idx <= (node->idx_start + NUM_MASK_BITS + node->set_after - 1))) {
return true;
}
return false;
}
static int node_cmp(node_t *node1, node_t *node2)
{
if (node1->idx_start < node2->idx_start) {
return -1;
} else if (node1->idx_start > node2->idx_start) {
return 1;
}
assert(node1->idx_start == node2->idx_start);
return 0;
}
static int node_cmp_idx(node_t *node, sb_idx_t idx)
{
if (node->idx_start < idx) {
return -1;
} else if (node->idx_start > idx) {
return 1;
}
assert(node->idx_start == idx);
return 0;
}
// Returns true if nodes left or right pointer doesn't point to another
// node.
static bool node_is_bud(node_t *node)
{
if ((node->left == NULL) || (node->right == NULL)) {
return true;
}
return false;
}
static unsigned int node_depth(const node_t *node)
{
unsigned int depth = 0;
const node_t *p = node;
while (p->parent) {
p = p->parent;
depth++;
}
return depth;
}
static unsigned int node_depth_black(const node_t *node)
{
unsigned int depth_black = 0;
while (node != NULL) {
if (node->color == BLACK) {
depth_black++;
}
node = node->parent;
}
return depth_black;
}
static node_t *node_sibling(node_t *node)
{
if (node->parent) {
return (node == node->parent->left)
? node->parent->right : node->parent->left;
}
return NULL;
}
static node_t *node_grandparent(node_t *node)
{
if (node->parent && node->parent->parent) {
return node->parent->parent;
}
return NULL;
}
static node_t *node_uncle(node_t *node)
{
node_t *grandparent = node_grandparent(node);
if (grandparent) {
return (grandparent->left == node->parent)
? grandparent->right
: grandparent->left;
}
return NULL;
}
static node_t *node_minimum(node_t *node)
{
while (node->left != NULL) {
node = node->left;
}
return node;
}
static node_t *node_maximum(node_t *node)
{
while (node->right != NULL) {
node = node->right;
}
return node;
}
static node_t *node_next(node_t *node)
{
if (node->right != NULL) {
return node_minimum(node->right);
}
node_t *y = node->parent;
while ((y != NULL) && (node == y->right)) {
node = y;
y = y->parent;
}
return y;
}
static node_t *node_prev(node_t *node)
{
if (node->left != NULL) {
return node_maximum(node->left);
}
node_t *y = node->parent;
while ((y != NULL) && (node == y->left)) {
node = y;
y = y->parent;
}
return y;
}
static const node_t *node_minimum_const(const node_t *nodep_const)
{
return (const node_t *) node_minimum((node_t *) nodep_const);
}
static const node_t *node_maximum_const(const node_t *nodep_const)
{
return (const node_t *) node_maximum((node_t *) nodep_const);
}
static const node_t *node_next_const(const node_t *nodep_const)
{
return (const node_t *) node_next((node_t *) nodep_const);
}
static const node_t *node_prev_const(const node_t *nodep_const)
{
return (const node_t *) node_prev((node_t *) nodep_const);
}
// | |
// +---+ +---+
// | y | | x |
// +---+ +---+
// / \ / \
// +---+ c <-- rotate_left(x) a +---+
// | x | | y |
// +---+ +---+
// / \ / \
// a b b c
//
static void node_rotate_left(sb_t *sb, node_t *x)
{
node_t *y = x->right;
x->right = y->left;
if (y->left != NULL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == NULL) {
sb->root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
x->num_set_subtree = num_set_node(x);
x->num_set_subtree += (x->left) ? x->left->num_set_subtree : 0;
x->num_set_subtree += (x->right) ? x->right->num_set_subtree : 0;
y->num_set_subtree = num_set_node(y);
y->num_set_subtree += (y->left) ? y->left->num_set_subtree : 0;
y->num_set_subtree += (y->right) ? y->right->num_set_subtree : 0;
}
// | |
// +---+ +---+
// | y | | x |
// +---+ +---+
// / \ / \
// +---+ c rotate_right(y) --> a +---+
// | x | | y |
// +---+ +---+
// / \ / \
// a b b c
//
static void node_rotate_right(sb_t *sb, node_t *y)
{
node_t *x = y->left;
y->left = x->right;
if (x->right != NULL) {
x->right->parent = y;
}
x->parent = y->parent;
if (y->parent == NULL) {
sb->root = x;
} else if (y == y->parent->right) {
y->parent->right = x;
} else {
y->parent->left = x;
}
x->right = y;
y->parent = x;
y->num_set_subtree = num_set_node(y);
y->num_set_subtree += (y->left) ? y->left->num_set_subtree : 0;
y->num_set_subtree += (y->right) ? y->right->num_set_subtree : 0;
x->num_set_subtree = num_set_node(x);
x->num_set_subtree += (x->left) ? x->left->num_set_subtree : 0;
x->num_set_subtree += (x->right) ? x->right->num_set_subtree : 0;
}
static void node_transplant(sb_t *sb, node_t *u, node_t *v)
{
if (v && v->num_set_subtree) {
num_set_adjust(v, v->num_set_subtree, false);
}
if (u->num_set_subtree) {
num_set_adjust(u, u->num_set_subtree, false);
}
if (u->parent == NULL) {
sb->root = v;
} else if (u == u->parent->left) {
u->parent->left = v;
} else {
u->parent->right = v;
}
if (v != NULL) {
v->parent = u->parent;
num_set_adjust(v, num_set_node(v)
+ ((v->left) ? v->left->num_set_subtree : 0)
+ ((v->right) ? v->right->num_set_subtree : 0),
true);
}
return;
}
static void node_insert(sb_t *sb, node_t *parent, node_t *node)
{
node->parent = parent;
if (parent == NULL) {
assert(sb->root == NULL);
node->color = BLACK;
sb->root = node;
} else {
int cmp_rv = node_cmp(node, parent);
if (cmp_rv < 0) {
assert(parent->left == NULL);
parent->left = node;
} else if (cmp_rv > 0) {
assert(parent->right == NULL);
parent->right = node;
} else {
assert(false); // Node to be inserted compares equal to parent.
}
}
node->left = NULL;
node->right = NULL;
node->color = RED;
num_set_adjust(node, num_set_node(node), true);
// Node Insert Fixup
assert(node->color == RED); // Newly inserted nodes are always colored RED.
while (node->parent && node_grandparent(node)
&& (node->parent->color == RED)) {
node_t *grandparent = node_grandparent(node);
// Both node and node's parent are RED, which is a violation
// of RED nodes only have BLACK children.
assert(node->color == RED);
assert(node->parent->color == RED);
if (node->parent == grandparent->left) {
node_t *uncle = node_uncle(node);
if (uncle && uncle->color == RED) { // Case 1 - Parent and uncle are
// both red.
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
} else {
if (node == node->parent->right) { // Case 2 - Parent is red,
// uncle is black.
node = node->parent;
node_rotate_left(sb, node);
}
node->parent->color = BLACK; // Case 3 - Node is left child,
// uncle is black.
node->parent->parent->color = RED;
node_rotate_right(sb, node->parent->parent);
}
} else {
node_t *uncle = node_uncle(node);
if (uncle && uncle->color == RED) { // Case 1
node->parent->color = BLACK;
uncle->color = BLACK;
node->parent->parent->color = RED;
node = node->parent->parent;
} else {
if (node == node->parent->left) { // Case 2
node = node->parent;
node_rotate_right(sb, node);
}
node->parent->color = BLACK; // Case 3
node->parent->parent->color = RED;
node_rotate_left(sb, node->parent->parent);
}
}
}
sb->root->color = BLACK;
}
static void node_delete(sb_t *sb, node_t *node)
{
node_t *y = node; // Points to node either removed or moved.
node_t *x;
node_t sentinel;
MEMCLEAR(&sentinel, sizeof(sentinel));
assert(sentinel.color == BLACK);
enum node_color y_orig_color = y->color;
if (node->left == NULL) {
if (node->right == NULL) {
sentinel.parent = node;
node->right = &sentinel;
}
x = node->right;
node_transplant(sb, node, node->right);
} else if (node->right == NULL) {
if (node->left == NULL) {
sentinel.parent = node;
node->left = &sentinel;
}
x = node->left;
node_transplant(sb, node, node->left);
} else {
y = node_minimum(node->right);
y_orig_color = y->color;
if (y->right == NULL) {
sentinel.parent = y->parent;
y->right = &sentinel;
}
x = y->right;
if (y->parent == node) {
sb_num_t num = num_set_node(x);
x->parent = y;
} else {
node_transplant(sb, y, y->right);
y->right = node->right;
y->right->parent = y;
}
node_transplant(sb, node, y);
if (y->left) {
num_set_adjust(y->left, y->left->num_set_subtree, false);
}
y->left = node->left;
y->left->parent = y;
y->color = node->color;
num_set_adjust(y, y->left->num_set_subtree, true);
}
if (y_orig_color == BLACK) {
node_delete_fixup(sb, x);
}
// If node points to sentinel, set its pointer to NULL, before the
// sentinel variable goes out-of-scope.
if (sentinel.parent != NULL) {
if (sentinel.parent->left == &sentinel) {
sentinel.parent->left = NULL;
}
if (sentinel.parent->right == &sentinel) {
sentinel.parent->right = NULL;
}
}
if (sb->root == &sentinel) {
sb->root = NULL;
}
sb->hint = NULL;
free(node);
}
static void node_delete_fixup(sb_t *sb, node_t *node)
{
while ((node != sb->root) && (node->color == BLACK)) {
if (node == node->parent->left) {
node_t *w = node->parent->right;
if (w->color == RED) {
w->color = BLACK;
node->parent->color = RED;
node_rotate_left(sb, node->parent);
w = node->parent->right;
}
if (((w->left == NULL) || (w->left->color == BLACK))
&& ((w->right == NULL) || (w->right->color == BLACK))) {
w->color = RED;
node = node->parent;
} else {
if ((w->right == NULL) || (w->right->color == BLACK)) {
w->left->color = BLACK;
w->color = RED;
node_rotate_right(sb, w);
w = node->parent->right;
}
w->color = node->parent->color;
node->parent->color = BLACK;
w->right->color = BLACK;
node_rotate_left(sb, node->parent);
node = sb->root;
}
} else {
node_t *w = node->parent->left;
if (w->color == RED) {
w->color = BLACK;
node->parent->color = RED;
node_rotate_right(sb, node->parent);
// node_rotate_right(sb, node);
w = node->parent->left;
}
if (((w->right == NULL) || (w->right->color == BLACK))
&& ((w->left == NULL) || (w->left->color == BLACK))) {
w->color = RED;
node = node->parent;
} else {
if ((w->left == NULL) || (w->left->color == BLACK)) {
w->right->color = BLACK;
w->color = RED;
node_rotate_left(sb, w);
// node_rotate_left(sb, w->parent);
w = node->parent->left;
}
w->color = node->parent->color;
node->parent->color = BLACK;
w->left->color = BLACK;
node_rotate_right(sb, node->parent);
// node_rotate_right(sb, node);
node = sb->root;
}
}
}
node->color = BLACK;
}
sb_num_t sb_nodes_num(const sb_t *sb)
{
sb_num_t num = 0;
if (sb->root != NULL) {
for (const node_t *node = node_minimum_const(sb->root); node != NULL;
node = node_next_const(node)) {
num++;
}
}
return num;
}
// Current implementation only has one type of node, which always
// has a mask with NUM_MASK_BITS bits;
sb_num_t sb_mask_bits_min(void)
{
return NUM_MASK_BITS;
}
sb_num_t sb_mask_bits_max(void)
{
return NUM_MASK_BITS;
}
// Returns NULL on sucess, otherwise returns a pointer to a dynamically
// allocated error message.
sb_pdynstr_t sb_validate(const sb_t* sb)
{
sb_num_t sum_pernode_set = 0;
node_t *highest_bud = NULL;
node_t *lowest_bud = NULL;
node_t *first_bud = NULL;
// When it exists, the root node should be BLACK.
if ((sb->root) && (sb->root->color != BLACK)) {
return sb_dyn_sprintf("Root node (%p) color is not BLACK",
sb->root->color);
}
// For each node.
if (sb->root) {
node_t *prev = NULL;
for (node_t *node = node_minimum(sb->root); node != NULL;
node = node_next(node)) {
// Validate node start index is on a mask boundary.
if ((node->idx_start % NUM_MASK_BITS) != 0) {
return sb_dyn_sprintf("Node start index not on mask boundary,\n"
" node: %p idx_start: %#" SB_PRI_IDX " NUM_MASK_BITS: %u",
node, node->idx_start, NUM_MASK_BITS);
}
if (prev != NULL) {
// Validate current node has starting index greater than the
// previous node.
if (prev->idx_start >= node->idx_start) {
return sb_dyn_sprintf("Node start index not greater than previous "
"node index,\n"
" prev: %p prev->idx_start: %#" SB_PRI_IDX "\n"
" node: %p node->idx_start: %#" SB_PRI_IDX "",
prev, prev->idx_start, node, node->idx_start);
}
// Validate a non-zero previous node set_after value doesn't
// cause the bits it supports to overlap with the start index
// of the current node.
if ((prev->idx_start + NUM_MASK_BITS + prev->set_after - 1)
>= node->idx_start) {
return sb_dyn_sprintf("Previous node's set_after bits overlap with "
"the current node,\n"
" NUM_MASK_BITS: %u\n"
" prev: %p prev->idx_start: %#" SB_PRI_IDX
" prev->set_after: %#" SB_PRI_NUM "\n"
" node: %p node->idx_start: %#" SB_PRI_IDX "",
NUM_MASK_BITS,
prev, prev->idx_start,
prev->set_after,
node, node->idx_start);
}
// Is this node adjacent to the mask or set_after bits of the
// previous node. If so and this node has only leading mask bits,
// those bits should have been part of the prvious nodes set_after
// bits.
if (node_prev_adj(node) && mask_only_leading(node->mask)) {
return sb_dyn_sprintf("Nodes leading bits should be part of "
"adjacent nodes set_after,\n"
" prev: %p prev->idx_start: %#" SB_PRI_IDX
" prev->set_after: %#" SB_PRI_NUM "\n"
" node: %p node->idx_start: %#" SB_PRI_IDX
" node->mask: %#018" NODE_PRI_MASK "\n",
prev, prev->idx_start,
prev->set_after,
node, node->idx_start,
node->mask);
}
}
// Is this a higher bud node? Node where there is no child
// to the left or right.
if (node_is_bud(node) && ((highest_bud == NULL)
|| (node_depth(node) < node_depth(highest_bud))) ) {
highest_bud = node;
}
// Is this a lower bud node?
if (node_is_bud(node) && ((lowest_bud == NULL)
|| (node_depth(node) > node_depth(lowest_bud))) ) {
lowest_bud = node;
}
// Add to total sum of bits set, the number of bits set in this node.
sum_pernode_set += num_set_node(node);
// Nodes should only exist if they represent at least 1 set bit.
if (num_set_node(node) == 0) {
return sb_dyn_sprintf("Node doesn't represent any set bits,\n"
" node: %p mask: %#" NODE_PRI_MASK "",
node, node->mask);
}
// Direct children of red nodes should not also be red.
if (node->color == RED) {
if (node->left && (node->left->color == RED)) {
return sb_dyn_sprintf("Red node: %p has a left child node: %p\n"
"that is also Red.", node, node->left);
}
if (node->right && (node->right->color == RED)) {
return sb_dyn_sprintf("Red node: %p has a right child "
"node: %p that is also Red.", node, node->right);
}
}
// All nodes with any leaves (left == NULL or right == NULL)
// should have the same number of black nodes on path to
// the root node.
if (node_is_bud(node)) {
unsigned int this_depth_black = node_depth_black(node);
if (first_bud != NULL) {
if (this_depth_black != node_depth_black(first_bud)) {
return sb_dyn_sprintf("Bud node: %p has a black depth of %u,\n"
" which is different from bud node: %p black depth of %u",
node, this_depth_black, first_bud, node_depth_black(first_bud));
}
} else {
first_bud = node;
}
}
// Validate nodes subtree num set value is equal to the number of
// bits set in this node plus all its children.
sb_num_t expected_subtree_num = num_set_node(node);
expected_subtree_num += (node->left) ? num_set_subtree(node->left) : 0;
expected_subtree_num += (node->right) ? num_set_subtree(node->right) : 0;
if (node->num_set_subtree != expected_subtree_num) {
return sb_dyn_sprintf("Unexpected num_set_subtree\n"
" node->idx_start: %#" SB_PRI_IDX
" node->mask: %#018" NODE_PRI_MASK
" node->set_after: %#" SB_PRI_NUM "\n"
" left_num_set_subtree: %#" SB_PRI_NUM "\n"
" right_num_set_subtree: %#" SB_PRI_NUM "\n"
" num_set_mask: %u"
" node->num_set_subtree: %#" SB_PRI_NUM "\n"
" expected_subtree_num: %#" SB_PRI_NUM "\n",
node->idx_start, node->mask, node->set_after,
(node->left) ? num_set_subtree(node->left) : (sb_num_t) 0,
(node->right) ? num_set_subtree(node->right) : (sb_num_t) 0,
num_set_mask(node->mask), node->num_set_subtree,
expected_subtree_num);
}
prev = node;
}
}
// Is the tree sufficiently balanced? Implementation uses a Red-Black
// binary-tree. For such a binary-tree the lowest leaf should be no
// more than twice the depth of the highest leaf. Only kepth track of
// the highest and lowest bud nodes, bud nodes have a leaf or leaves,
// so need to add 1 to get the depth of the leaf attached to a bud node.
if (highest_bud) {
if ((node_depth(lowest_bud) + 1)
> (2 * (node_depth(highest_bud) + 1))) {
return sb_dyn_sprintf("lowest_node: %p at more than twice the\n"
" depth of the highest_bud: %p\n"
" lowest_depth: %u hightest_depth: %u",
lowest_bud, highest_bud, node_depth(lowest_bud) + 1,
node_depth(highest_bud) + 1);
}
}
// Is the sum of bits set across all the nodes equal to the total
// maintained in the sparsebit structure.
if (sum_pernode_set != sb_numset(sb)) {
return sb_dyn_sprintf("sb->num_set: %llu not equal to "
"sum_pernode_set: %llu", sb_numset(sb), sum_pernode_set);
}
return NULL;
}
// Returns a pointer to a dynamically allocated string, that represents
// the current state of the sparsebit array pointed to by sb.
sb_pdynstr_t sb_dump(const sb_t* sb)
{
sb_pdynstr_t rv_str = sb_dyn_sprintf("sb: %p\n"
"root: %p\n", sb, sb->root);
if (sb->root) {
sb_pdynstr_t tmp_str = dump_subtree(sb, sb->root, 2);
rv_str = sb_dyn_sprintf("%s%s", rv_str, tmp_str);
free(tmp_str);
}
return rv_str;
}
static bool node_prev_adj(node_t *node)
{
node_t *prev = node_prev(node);
if (prev != NULL) {
if ((prev->idx_start + NUM_MASK_BITS + prev->set_after)
== node->idx_start) {
return true;
}
}
return false;
}
static node_t *node_split(sb_t *sb, node_t *node, sb_idx_t at)
{
node_t *first = node;
node_t *second = calloc(1, sizeof(node_t));
if (second == NULL) {
return second;
}
second->idx_start = MASK_BOUNDARY(at);
second->set_after = first->set_after
- (second->idx_start - (first->idx_start + NUM_MASK_BITS));
first->set_after -= second->set_after;
for (unsigned int bit_idx = 0; (second->set_after > 0)
&& (bit_idx < NUM_MASK_BITS); bit_idx++) {
second->mask |= (mask_t)1 << bit_idx;
second->set_after--;
}
num_set_adjust(first, num_set_node(second), false);
node_t *parent = sb->root;
while (parent != NULL) {
int cmp_rv = node_cmp_idx(parent, at);
assert(cmp_rv != 0); // Only in this loop when second node, which
// has not been inserted yet, supports idx. So
// no node should be found already within the
// sb->root tree, that supports that index.
if (cmp_rv > 0) {
if (parent->left == NULL) {
break;
}
parent = parent->left;
} else {
if (parent->right == NULL) {
break;
}
parent = parent->right;
}
}
node_insert(sb, parent, second);
sb->hint = second;
return second;
}
static void node_merge(sb_t *sb, node_t *prev, node_t *next)
{
assert(node_prev_adj(next));
assert(mask_only_leading(next->mask));
sb_num_t adj_amt = 0;
sb_num_t num_cleared = 0;
if (next->mask == ~(mask_t)0) {
// Merge all of next node, both its mask and set_after bits, into
// the previous node.
prev->set_after += NUM_MASK_BITS + next->set_after;
num_set_adjust(prev, NUM_MASK_BITS + next->set_after, true);
node_delete(sb, next);
} else {
// Add next nodes contigously set leading mask bits
// to previous nodes set_after value.
for (unsigned int n = 0; n < NUM_MASK_BITS; n++) {
if ((((mask_t)1 << n) & next->mask) != 0) {
prev->set_after++;
adj_amt++;
num_cleared++;
} else {
break;
}
}
num_set_adjust(next, num_cleared, false);
next->mask = 0;
next->idx_start += NUM_MASK_BITS;
num_set_adjust(prev, adj_amt, true);
adj_amt = 0;
if (next->set_after > 0) {
for (unsigned int n = 0; (n < NUM_MASK_BITS)
&& (next->set_after > 0); n++) {
next->mask |= (mask_t)1 << n;
next->set_after--;
}
} else {
assert(next->mask == 0);
assert(next->set_after == 0);
node_delete(sb, next);
}
}
num_set_adjust(prev, adj_amt, true);
node_t *next2 = node_next(prev);
if ((next2 != NULL) && node_prev_adj(next2)
&& mask_only_leading(next2->mask)) {
node_merge(sb, prev, next2);
}
}
static void node_adjacent_fixup(sb_t *sb, sb_idx_t idx_start, sb_idx_t idx_end)
{
node_t *node;
if (sb->root == NULL) {
return;
}
// Determine last index that fixup needs to be checked for.
// If bit is set at caller specified idx_end, then just need
// to check nodes up to that address. If bit at caller specified
// idx_end is not set, then need to check until index of next set
// bit, if it exists. If it doesn't exist, because there is no set
// bit at or after idx_end, then just need to check to first set bit
// before idx_end, but will instead check until caller specified idx_end.
sb_idx_t fixup_end_idx = idx_end;
if (!sb_isset(sb, fixup_end_idx)) {
sb_idx_t next_idx = sb_nextset(sb, fixup_end_idx);
if (next_idx > fixup_end_idx) {
fixup_end_idx = next_idx;
}
}
node = node_find_or_next(sb, idx_start);
if (node != NULL) {
node_t *prev = node_prev(node);
if (prev != NULL) {
node = prev;
}
}
bool unconditional_process = true;
bool first_pass = true;
while ((node != NULL) && (unconditional_process
|| (node->idx_start <= ((fixup_end_idx != SB_IDX_MAX)
? (fixup_end_idx + 1) : SB_IDX_MAX))) ) {
unconditional_process = false;
node_t *next = node_next(node);
if ((next != NULL) && mask_only_leading(next->mask)
&& node_prev_adj(next)) {
node_merge(sb, node, next);
unconditional_process = true;
}
if (first_pass) {
unconditional_process = true;
first_pass = false;
}
node = node_next(node);
}
}
static bool node_any_set(const node_t *node)
{
return mask_any_set(node->mask) || node->set_after;
}
static bool mask_any_set(mask_t mask)
{
if (mask != 0) {
return true;
}
return false;
}
static bool mask_only_leading(mask_t mask)
{
if ((mask != 0) && (((mask + 1) & (mask)) == 0)) {
return true;
}
return false;
}
static unsigned int num_set_mask(mask_t mask)
{
sb_num_t num = 0;
// TODO: Where available, use machine instruction that returns
// num set bits, otherwise use non-loop method described in the
// book Hacker's Delight.
for (unsigned int n = 0; n < NUM_MASK_BITS; n++) {
if (mask & ((mask_t)1 << n)) {
num++;
}
}
return num;
}
static sb_num_t num_set_node(const node_t *node)
{
return num_set_mask(node->mask) + node->set_after;
}
static sb_num_t num_set_subtree(const node_t *node)
{
sb_num_t sum = 0;
sum += num_set_node(node);
sum += (node->left) ? num_set_subtree(node->left) : 0;
sum += (node->right) ? num_set_subtree(node->right) : 0;
return sum;
}
static void num_set_adjust(node_t *node, sb_num_t amt, bool positive)
{
if (amt == 0) { return; }
for (; node != NULL; node = node->parent) {
if (positive) {
assert(((node->num_set_subtree + amt) > node->num_set_subtree)
|| ((node->num_set_subtree + amt) == 0));
node->num_set_subtree += amt;
} else {
assert((node->num_set_subtree >= amt)
|| (node->num_set_subtree == 0));
node->num_set_subtree -= amt;
}
}
}
static sb_pdynstr_t dump_subtree(const sb_t *sb, const node_t *node,
unsigned int indent)
{
sb_pdynstr_t rv_str;
sb_pdynstr_t node_str = sb_dyn_sprintf(
"%*snode: %p idx_start: %#" SB_PRI_IDX " mask: %#018" NODE_PRI_MASK
" set_after: %#" SB_PRI_NUM "\n"
"%*scolor: %s depth: %u parent: %p left: %p right: %p\n"
"%*snum_set_subtree: %#" SB_PRI_NUM "\n",
indent, "", node, node->idx_start, node->mask, node->set_after,
indent + 2, "", (node->color == RED) ? "RED " : "BLACK",
node_depth(node), node->parent, node->left, node->right,
indent + 2, "", node->num_set_subtree);
sb_pdynstr_t left_str = NULL, right_str = NULL;
if (node->left) {
left_str = dump_subtree(sb, node->left, indent + 2);
}
if (node->right) {
right_str = dump_subtree(sb, node->right, indent + 2);
}
rv_str = sb_dyn_sprintf("%s%s%s", node_str,
(left_str) ? left_str : "", (right_str) ? right_str : "");
sb_dynstr_free(node_str);
if (left_str) {
sb_dynstr_free(left_str);
}
if (right_str) {
sb_dynstr_free(right_str);
}
return rv_str;
}
sb_pdynstr_t sb_dyn_sprintf(const char *format, ...)
{
int n;
size_t s_allocated;
va_list ap;
char *s;
// Determine size of string, if the caller doesn't change any of the
// argument values, while this call is being performed.
va_start(ap, format);
n = vsnprintf(s, 0, format, ap);
va_end(ap);
// For now, just get a pointer to any allocated memory. Later, the loop
// below will reallocate to the anticipated size.
s = malloc(0);
if (s == NULL) {
errno = ENOMEM;
return NULL;
}
do {
// Reallocate to anticipated size, plus two extra bytes. One for the
// trailing \0 and another so as to know if enough was allocated.
s_allocated = n + 2;
s = realloc(s, s_allocated);
va_start(ap, format);
n = vsnprintf(s, s_allocated, format, ap);
va_end(ap);
} while (n >= s_allocated);
return s;
}
void sb_dynstr_free(sb_pdynstr_t pdynstr)
{
free(pdynstr);
}
Raw
sparsebit_c.h
/* Copyright 2020 Louis Huemiller Jr.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include <inttypes.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
struct sb; // Intentional incomplete structure definition.
// Concrete private definition only available within
// private library implementation.
typedef struct sb sb_t;
typedef uint64_t sb_idx_t;
#define SB_PRI_IDX PRIx64
typedef uint64_t sb_num_t;
#define SB_PRI_NUM PRIx64
#define SB_IDX_MAX (~(sb_idx_t)0)
#define SB_NUM_MAX (~(sb_num_t)0)
sb_t *sb_create(void);
void sb_delete(sb_t* sb);
int sb_copy(sb_t *dest, const sb_t *src);
// ==== Set Operations ====
int sb_set(sb_t* sb, sb_idx_t idx);
int sb_setnum(sb_t* sb, sb_idx_t idx_start, sb_num_t num);
bool sb_anyset(const sb_t* sb);
bool sb_allset(const sb_t* sb);
sb_num_t sb_numset(const sb_t* sb);
bool sb_isset(const sb_t* sb, sb_idx_t idx);
sb_idx_t sb_firstset(const sb_t* sb);
sb_idx_t sb_nextset(const sb_t* sb, sb_idx_t idx);
sb_idx_t sb_prevset(const sb_t* sb, sb_idx_t idx);
sb_idx_t sb_nthset(const sb_t* sb, sb_idx_t nth);
// ==== Clear/Cleared Operations ====
int sb_clear(sb_t* sb, sb_idx_t idx);
int sb_clearnum(sb_t* sb, sb_idx_t idx_start, sb_num_t num);
bool sb_anycleared(const sb_t* sb);
sb_num_t sb_numcleared(const sb_t* sb);
bool sb_iscleared(const sb_t* sb, sb_idx_t idx);
sb_idx_t sb_firstcleared(const sb_t* sb);
sb_idx_t sb_nextcleared(const sb_t* sb, sb_idx_t idx);
sb_idx_t sb_prevcleared(const sb_t* sb, sb_idx_t idx);
#ifdef SB_TEST
sb_num_t sb_nodes_num(const sb_t *sb);
size_t sb_mask_bits_min(void);
size_t sb_mask_bits_max(void);
typedef char * sb_pdynstr_t; // Dynamically allocated \0 terminated string.
// Caller is responsible for calling
// sb_dynstr_free() once caller is done
// with the string.
sb_pdynstr_t sb_dyn_sprintf(const char *format, ...);
void sb_dynstr_free(sb_pdynstr_t pdynstr);
sb_pdynstr_t sb_validate(const sb_t* sb);
sb_pdynstr_t sb_dump(const sb_t* sb);
#endif
Raw
test_adjacent.c
/* Copyright 2020 Louis Huemiller Jr.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "sparsebit_c.h" // Intentionally included first, to aid in
// detection of includes, that may be missing
// within sparsebit_c.h.
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <getopt.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#define DEFAULT_NODES_NUM (3)
#define DEFAULT_EDGE_MARGIN (1)
#define MASK_BITS (64)
#define NODES_BASE_IDX (0x3a000)
#define MEMCLEAR(p, n) memset((p), 0, (n))
#define NUM(a) (sizeof(a)/sizeof((a)[0]))
enum MASK_TYP {
MASK0 = 0,
MASK1_LEADING,
MASK2_LEADING,
MASK2_TRAILING,
MASK1_TRAILING,
MASK1_CLEARED,
};
struct mask_typ_attr {
enum MASK_TYP typ;
char *str;
uint64_t val;
} mask_typ_attrs[] = {
{MASK0, "Zero", 0x0},
{MASK1_LEADING, "1Leading", 0x1},
{MASK2_LEADING, "2Leading", 0x3},
{MASK2_TRAILING, "2Trailing", 0xC000000000000000llu},
{MASK1_TRAILING, "1Trailing", 0x8000000000000000llu},
{MASK1_CLEARED, "1Cleared", 0xFFFFFFFFFDFFFFFFllu},
};
#define MASK_TYP_FIRST (mask_typ_attrs[0].typ)
#define MASK_TYP_LAST (mask_typ_attrs[NUM(mask_typ_attrs) - 1].typ)
#define MASK_TYP_NUM (NUM(mask_typ_attrs))
enum SETAFTER_TYP {
SETAFTER0 = 0,
SETAFTER1,
SETAFTER2,
SETAFTER63,
SETAFTER64,
};
struct setafter_typ_attr {
enum SETAFTER_TYP typ;
sb_num_t val;
} setafter_typ_attrs[] = {
{SETAFTER0, 0},
{SETAFTER1, 1},
{SETAFTER2, 2},
{SETAFTER63, 63},
{SETAFTER64, 64},
};
#define SETAFTER_TYP_FIRST (setafter_typ_attrs[0].typ)
#define SETAFTER_TYP_LAST (setafter_typ_attrs[NUM(setafter_typ_attrs) - 1].typ)
#define SETAFTER_TYP_NUM (NUM(setafter_typ_attrs))
struct node {
// Type/Counter values
enum MASK_TYP mask_typ;
enum SETAFTER_TYP set_after_typ;
// Node attributes, based on counter values.
sb_idx_t idx_start;
uint64_t mask;
sb_num_t set_after;
};
struct node *nodes = NULL;
unsigned long nodes_num = DEFAULT_NODES_NUM;
unsigned long edge_margin = DEFAULT_EDGE_MARGIN;
static void nodes_setup(void);
static sb_t *node_sb_create(sb_pdynstr_t *p_ops);
static int range_set(sb_idx_t start, sb_idx_t end,
sb_t **p_sb, sb_pdynstr_t *p_ops);
static sb_idx_t *nodes_tst_indexes(ssize_t margin, size_t *pnum);
static bool nodes_expected_isset(sb_idx_t idx);
static sb_idx_t *dyn_add_index_unique(sb_idx_t idx, ssize_t offset,
sb_idx_t *indexes, size_t *pnum);
static int idx_cmp(const void *elem1, const void *elem2);
static void usage(FILE *stream);
static void help(FILE *stream);
int main(int argc, char *argv[])
{
int rv;
sb_pdynstr_t err_string;
// Command-line Parsing
static const struct option options[] = {
{"nodes_num", required_argument, 0, 'n'},
{"edge_margin", required_argument, 0, 'm'},
{} // End-of-Array Marker
};
int opt;
bool error;
char *endptr;
while ((opt = getopt_long(argc, argv, "n:m:h?", options, NULL)) != EOF) {
switch (opt) {
case 'n':
nodes_num = strtoul(optarg, &endptr, 10);
if ((*endptr != '\0') || (strchr(optarg, '-') != NULL)) {
fprintf(stderr, "Invalid --nodes_num value of: %s\n", optarg);
exit(20);
}
break;
case 'm':
edge_margin = strtoul(optarg, &endptr, 10);
if ((*endptr != '\0') || (strchr(optarg, '-') != NULL)) {
fprintf(stderr, "Invalid --edge_margin value of: %s\n", optarg);
exit(21);
}
break;
case 'h':
case '?':
default:
error = ((optopt != 0) && (optopt != '?') && (optopt != 'h'));
if (error) {
usage(stderr);
} else {
help(stdout);
return 0;
}
exit(22);
}
}
if ((argc - optind) > 0) {
fputs("Unexpected positional command-line arguments", stderr);
exit(23);
}
printf("nodes_num: %lu\n", nodes_num);
printf("edge_margin: %lu\n", edge_margin);
unsigned long long iter_total = 1;
for (unsigned int i = 0; i < nodes_num; i++) {
iter_total *= (MASK_TYP_NUM * SETAFTER_TYP_NUM);
}
printf("total_iterations: %llu\n", iter_total);
nodes = malloc(nodes_num * sizeof(*nodes));
if (nodes == NULL) {
fputs("Insufficient Memory", stderr);
exit(22);
}
bool first_pass = true;
unsigned long long iter;
for (iter = 0; ; iter++) {
if ((iter % 1000) == 0) {
printf("iteration %llu of %llu\n", iter, iter_total);
}
if (first_pass) {
MEMCLEAR(nodes, sizeof(*nodes) * nodes_num);
first_pass = false;
} else {
// Increment to next combination.
struct node *nodep;
for (nodep = nodes; nodep < (nodes + nodes_num); nodep++) {
nodep->set_after_typ++;
if (nodep->set_after_typ > SETAFTER_TYP_LAST) {
nodep->set_after_typ = SETAFTER_TYP_FIRST;
nodep->mask_typ++;
if (nodep->mask_typ > MASK_TYP_LAST) {
nodep->mask_typ = MASK_TYP_FIRST;
continue;
}
}
break;
}
assert(nodep <= nodes + nodes_num);
if (nodep == (nodes + nodes_num)) {
break;
}
}
bool skip = false;
// Skip when all mask and set-after are zero.
struct node *nodep;
for (nodep = nodes; nodep < (nodes + nodes_num); nodep++) {
if ((nodep->mask_typ != MASK0)
|| (setafter_typ_attrs[nodep->set_after_typ].val != 0)) {
break;
}
}
if (nodep == (nodes + nodes_num)) {
skip = true;
continue;
}
// Skip cases where mask of zero is before a non-zero mask.
bool any_mask0 = false;
for (nodep = nodes; nodep < (nodes + nodes_num); nodep++) {
if (nodep->mask_typ == MASK0) {
any_mask0 = true;
} else {
if (any_mask0) {
skip = true;
break;
}
}
}
if (skip) { continue; }
// Skip cases with mask of zero and a non-zero set-after value.
for (nodep = nodes; nodep < (nodes + nodes_num); nodep++) {
if ((nodep->mask_typ == MASK0)
&& (setafter_typ_attrs[nodep->set_after_typ].val != 0)) {
skip = true;
break;
}
}
if (skip) { continue; }
// Skip cases of only leading mask bits and previous node
// has set-after that is divisable by the mask size.
for (nodep = nodes + 1; nodep < (nodes + nodes_num); nodep++) {
if ((strstr(mask_typ_attrs[nodep->mask_typ].str, "Leading") != NULL)
&& ((setafter_typ_attrs[(nodep - 1)->set_after_typ].val % MASK_BITS)
== 0)) {
skip = true;
break;
}
}
if (skip) { continue; }
nodes_setup();
sb_pdynstr_t ops = sb_dyn_sprintf("");
if (ops == NULL) {
fprintf(stderr, "Error: Ops string initialization, errno: %i\n", errno);
exit(30);
}
sb_t *sb_initial = node_sb_create(&ops);
if (sb_initial == NULL) {
fprintf(stderr, "Error: sb_initial creation, errno: %i\n", errno);
exit(31);
}
size_t tst_indexes_num;
sb_idx_t *tst_indexes = nodes_tst_indexes(edge_margin, &tst_indexes_num);
// For each test index.
for (size_t i1 = 0; i1 < tst_indexes_num; i1++) {
sb_idx_t idx1 = *(tst_indexes + i1);
// ==== Perform and validate sb_set() ====
sb_t *sb_op_set = sb_create();
if (sb_op_set == NULL) {
fprintf(stderr, "Error: sb_op_set creation, errno: %i\n", errno);
exit(40);
}
rv = sb_copy(sb_op_set, sb_initial);
if (rv != 0) {
fprintf(stderr, "Error: sb_copy sb_initial to sb_op_set, errno: %i\n",
errno);
exit(41);
}
err_string = sb_validate(sb_op_set);
if (err_string) {
printf("FAILED: Validation Error - "
"Inconsitent Internal State:\n%s\n", err_string);
exit(44);
}
sb_set(sb_op_set, idx1);
err_string = sb_validate(sb_op_set);
if (err_string) {
fprintf(stderr, "FAILED: Validation Error - "
"Inconsitent Internal State:\n%s\n", err_string);
fprintf(stderr, "Operations:\n%s"
" SET_BIT idx: %#" SB_PRI_IDX "\n", ops, idx1);
fputs(sb_dump(sb_op_set), stderr);
exit(42);
}
for (size_t i = 0; i < tst_indexes_num; i++) {
sb_idx_t idx_check = *(tst_indexes + i);
bool expected = (idx_check == idx1) ? true
: nodes_expected_isset(idx_check);
bool actual = sb_isset(sb_op_set, idx_check);
if (actual != expected) {
fprintf(stderr, "FAILED: Validation Error - "
"Unexpected bit setting:\n"
" idx: %#" SB_PRI_IDX " actual: %u expected: %u\n",
idx_check, actual, expected);
fprintf(stderr, "Operations:\n%s"
" SET_BIT idx: %#" SB_PRI_IDX "\n", ops, idx1);
fputs(sb_dump(sb_op_set), stderr);
exit(43);
}
}
sb_delete(sb_op_set);
// ==== Perform and validate sb_clear() ====
sb_t *sb_op_clear = sb_create();
if (sb_op_clear == NULL) {
fprintf(stderr, "Error: sb_op_clear creation, errno: %i\n", errno);
exit(50);
}
rv = sb_copy(sb_op_clear, sb_initial);
if (rv != 0) {
fprintf(stderr, "Error: sb_copy sb_initial to sb_op_clear, errno: %i\n",
errno);
exit(51);
}
err_string = sb_validate(sb_op_clear);
if (err_string) {
printf("FAILED: Validation Error - "
"Inconsitent Internal State:\n%s\n", err_string);
exit(54);
}
sb_clear(sb_op_clear, idx1);
err_string = sb_validate(sb_op_clear);
if (err_string) {
fprintf(stderr, "FAILED: Validation Error - "
"Inconsitent Internal State:\n%s\n", err_string);
fprintf(stderr, "Operations:\n%s"
" CLEAR_BIT idx: %#" SB_PRI_IDX "\n", ops, idx1);
fputs(sb_dump(sb_op_clear), stderr);
exit(52);
}
for (size_t i = 0; i < tst_indexes_num; i++) {
sb_idx_t idx_check = *(tst_indexes + i);
bool expected = (idx_check == idx1) ? false
: nodes_expected_isset(idx_check);
bool actual = sb_isset(sb_op_clear, idx_check);
if (actual != expected) {
fprintf(stderr, "FAILED: Validation Error - "
"Unexpected bit setting:\n"
" idx: %#" SB_PRI_IDX " actual: %u expected: %u\n",
idx_check, actual, expected);
fprintf(stderr, "Operations:\n%s"
" CLEAR_BIT idx: %#" SB_PRI_IDX "\n", ops, idx1);
fputs(sb_dump(sb_op_set), stderr);
exit(53);
}
}
sb_delete(sb_op_clear);
// For each range of indexes.
for (size_t i2 = i1; i2 < tst_indexes_num; i2++) {
sb_idx_t idx2 = *(tst_indexes + i2);
sb_num_t num = (idx2 - idx1) + 1;
// ==== Perform and validate sb_setnum() ====
sb_t *sb_op_setnum = sb_create();
if (sb_op_setnum == NULL) {
fprintf(stderr, "Error: sb_op_setnum creation, errno: %i\n", errno);
exit(60);
}
rv = sb_copy(sb_op_setnum, sb_initial);
if (rv != 0) {
fprintf(stderr, "Error: sb_copy sb_initial to sb_op_setnum, "
"errno: %i\n", errno);
exit(61);
}
err_string = sb_validate(sb_op_setnum);
if (err_string) {
printf("FAILED: Validation Error - "
"Inconsitent Internal State:\n%s\n", err_string);
exit(64);
}
sb_setnum(sb_op_setnum, idx1, num);
err_string = sb_validate(sb_op_setnum);
if (err_string) {
fprintf(stderr, "FAILED: Validation Error - "
"Inconsitent Internal State:\n%s\n", err_string);
fprintf(stderr, "Operations:\n%s"
" SET_NUM idx: %#" SB_PRI_IDX " num: %#" SB_PRI_NUM "\n", ops,
idx1, num);
fputs(sb_dump(sb_op_setnum), stderr);
exit(62);
}
for (size_t i = 0; i < tst_indexes_num; i++) {
sb_idx_t idx_check = *(tst_indexes + i);
bool expected = ((idx_check >= idx1)
&& (idx_check <= idx2)) ? true
: nodes_expected_isset(idx_check);
bool actual = sb_isset(sb_op_setnum, idx_check);
if (actual != expected) {
fprintf(stderr, "FAILED: Validation Error - "
"Unexpected bit setting:\n"
" idx: %#" SB_PRI_IDX " actual: %u expected: %u\n",
idx_check, actual, expected);
fprintf(stderr, "Operations:\n%s"
" SET_NUM idx: %#" SB_PRI_IDX " num: %#" SB_PRI_NUM "\n", ops,
idx1, num);
fputs(sb_dump(sb_op_set), stderr);
exit(63);
}
}
sb_delete(sb_op_setnum);
// ==== Perform and validate sb_clearnum() ====
sb_t *sb_op_clearnum = sb_create();
if (sb_op_clearnum == NULL) {
fprintf(stderr, "Error: sb_op_clearnum creation, errno: %i\n", errno);
exit(70);
}
rv = sb_copy(sb_op_clearnum, sb_initial);
if (rv != 0) {
fprintf(stderr, "Error: sb_copy sb_initial to sb_op_clearnum, "
"errno: %i\n", errno);
exit(71);
}
err_string = sb_validate(sb_op_clearnum);
if (err_string) {
printf("FAILED: Validation Error - "
"Inconsitent Internal State:\n%s\n", err_string);
exit(74);
}
sb_clearnum(sb_op_clearnum, idx1, num);
err_string = sb_validate(sb_op_clearnum);
if (err_string) {
fprintf(stderr, "FAILED: Validation Error - "
"Inconsitent Internal State:\n%s\n", err_string);
fprintf(stderr, "Operations:\n%s"
" CLEAR_NUM idx: %#" SB_PRI_IDX " num: %#" SB_PRI_NUM "\n", ops,
idx1, num);
fputs(sb_dump(sb_op_clearnum), stderr);
exit(72);
}
for (size_t i = 0; i < tst_indexes_num; i++) {
sb_idx_t idx_check = *(tst_indexes + i);
bool expected = ((idx_check >= idx1)
&& (idx_check <= idx2)) ? false
: nodes_expected_isset(idx_check);
bool actual = sb_isset(sb_op_clearnum, idx_check);
if (actual != expected) {
fprintf(stderr, "FAILED: Validation Error - "
"Unexpected bit setting:\n"
" idx: %#" SB_PRI_IDX " actual: %u expected: %u\n",
idx_check, actual, expected);
fprintf(stderr, "Operations:\n%s"
" CLEAR_NUM idx: %#" SB_PRI_IDX " num: %#" SB_PRI_NUM "\n", ops,
idx1, num);
fputs(sb_dump(sb_op_set), stderr);
exit(73);
}
}
sb_delete(sb_op_clearnum);
}
}
free(tst_indexes);
sb_delete(sb_initial);
}
return 0;
}
// For each node, sets its values based on the mask_typ and set_after_typ,
// counter values.
static void nodes_setup(void)
{
uint64_t mask;
sb_num_t set_after;
// Set mask and set_after values, in each node.
for (struct node *nodep = nodes; nodep < (nodes + nodes_num); nodep++) {
nodep->mask = mask_typ_attrs[nodep->mask_typ].val;
nodep->set_after = setafter_typ_attrs[nodep->set_after_typ].val;
}
// Determine the start index of each node.
sb_idx_t idx = NODES_BASE_IDX;
for (struct node *nodep = nodes; nodep < (nodes + nodes_num); nodep++) {
if (nodep->mask_typ != MASK0) {
nodep->idx_start = idx;
} else {
break;
}
idx += MASK_BITS;
sb_num_t setafter = setafter_typ_attrs[nodep->set_after_typ].val;
if (setafter != 0) {
idx += setafter;
if (setafter % MASK_BITS) {
idx += MASK_BITS - (setafter % MASK_BITS);
}
}
}
}
static sb_t *node_sb_create(sb_pdynstr_t *p_ops)
{
int rv;
sb_t *sb = sb_create();
if (sb == NULL) {
return sb;
}
bool within_range = false; // True when within a range of set bits,
// Searching for the end of the range.
sb_idx_t idx_start, idx_end; // Valid only when within_range is true.
for (struct node *nodep = nodes; nodep < (nodes + nodes_num); nodep++) {
if (nodep->mask == MASK0) {
break;
}
// Handle node mask bits.
for (unsigned int mask_idx = 0; mask_idx < MASK_BITS; mask_idx++) {
if (nodep->mask & (1llu << mask_idx)) {
if (!within_range) {
idx_start = idx_end = nodep->idx_start + mask_idx;
within_range = true;
} else {
idx_end = nodep->idx_start + mask_idx;
}
} else {
if (within_range) {
int rv = range_set(idx_start, idx_end, &sb, p_ops);
if (rv != 0) {
fprintf(stderr, "range_set failed, errno: %i\n", errno);
}
within_range = false;
}
}
}
if (within_range && (nodep->set_after == 0)) {
int rv = range_set(idx_start, idx_end, &sb, p_ops);
if (rv != 0) {
fprintf(stderr, "range_set failed, errno: %i\n", errno);
}
within_range = false;
}
// If needed, handle node set_after.
if (nodep->set_after != 0) {
if (!within_range) {
idx_start = nodep->idx_start + MASK_BITS;
within_range = true;
}
idx_end = nodep->idx_start + MASK_BITS - 1 + nodep->set_after;
// Is there a gap between this and the next node?
if (((nodep + 1) < (nodes + nodes_num))
&& ((idx_end) != (nodep->idx_start - 1))) {
int rv = range_set(idx_start, idx_end, &sb, p_ops);
if (rv != 0) {
fprintf(stderr, "range_set failed, errno: %i\n", errno);
}
within_range = false;
}
}
}
if (within_range) {
int rv = range_set(idx_start, idx_end, &sb, p_ops);
if (rv != 0) {
fprintf(stderr, "range_set failed, errno: %i\n", errno);
}
within_range = false;
}
return sb;
}
static int range_set(sb_idx_t start, sb_idx_t end,
sb_t **p_sb, sb_pdynstr_t *p_ops)
{
int rv;
sb_pdynstr_t ops;
if (start == end) {
// Set a single bit.
rv = sb_set(*p_sb, start);
if (rv != 0) {
sb_delete(*p_sb);
*p_sb = NULL;
sb_dynstr_free(*p_ops);
*p_ops = NULL;
return -1;
}
ops = sb_dyn_sprintf("%s SET_BIT idx: %#" SB_PRI_IDX "\n", *p_ops,
start);
if (ops == NULL) {
sb_delete(*p_sb);
*p_sb = NULL;
sb_dynstr_free(*p_ops);
*p_ops = NULL;
errno = ENOMEM;
return -1;
}
sb_dynstr_free(*p_ops);
*p_ops = ops;
} else {
// Set a range of bits.
rv = sb_setnum(*p_sb, start, end - start + 1);
if (rv != 0) {
sb_delete(*p_sb);
*p_sb = NULL;
sb_dynstr_free(*p_ops);
*p_ops = NULL;
return -1;
}
ops = sb_dyn_sprintf("%s SET_NUM idx: %#" SB_PRI_IDX
" num: %#" SB_PRI_NUM "\n", *p_ops, start, end - start + 1);
if (ops == NULL) {
sb_delete(*p_sb);
*p_sb = NULL;
sb_dynstr_free(*p_ops);
*p_ops = NULL;
errno = ENOMEM;
return -1;
}
sb_dynstr_free(*p_ops);
*p_ops = ops;
}
return 0;
}
static sb_idx_t *nodes_tst_indexes(ssize_t margin, size_t *pnum)
{
sb_idx_t *indexes = NULL;
size_t num = 0;
for (struct node *nodep = nodes; nodep < (nodes + nodes_num); nodep++) {
if (nodep->mask == MASK0) {
break;
}
sb_idx_t idx = nodep->idx_start;
// Add indexes around start and end of mask.
for (ssize_t offset = -margin; offset <= margin; offset++) {
indexes = dyn_add_index_unique(idx, offset, indexes, &num);
indexes = dyn_add_index_unique(idx + MASK_BITS - 1, offset,
indexes, &num);
}
// Add indexes for mask bits with settings different from previous
// mask bit.
for (unsigned int i = 1; i < MASK_BITS; i++) {
if ((bool)(nodep->mask & (1llu << (i - 1)))
!= (bool)(nodep->mask & (1llu << i))) {
for (ssize_t offset = -margin; offset <= margin; offset++) {
indexes = dyn_add_index_unique(idx + i, offset, indexes, &num);
}
}
}
// If needed add indexes abround end of set_after.
if (nodep->set_after != 0) {
for (ssize_t offset = -margin; offset <= margin; offset++) {
indexes = dyn_add_index_unique(idx + MASK_BITS +
nodep->set_after - 1, offset, indexes, &num);
}
}
}
qsort(indexes, num, sizeof(*indexes), idx_cmp);
*pnum = num;
return indexes;
}
static bool nodes_expected_isset(sb_idx_t idx)
{
for (struct node *nodep = nodes; nodep < (nodes + nodes_num); nodep++) {
if (nodep->mask == MASK0) {
break;
}
if ((idx >= nodep->idx_start)
&& (idx <= (nodep->idx_start + MASK_BITS - 1))) {
return (nodep->mask & (1llu << (idx - nodep->idx_start))) ? true : false;
}
if (nodep->set_after >= 1) {
if ((idx >= (nodep->idx_start + MASK_BITS))
&& (idx <= (nodep->idx_start + MASK_BITS + nodep->set_after - 1))) {
return true;
}
}
}
return false;
}
static sb_idx_t *dyn_add_index_unique(sb_idx_t idx, ssize_t offset,
sb_idx_t *indexes, size_t *pnum)
{
sb_idx_t *ptr;
sb_idx_t index = idx + offset;
// Skip if index + offset overflows.
if (((offset < 0) && (index > idx))
|| ((offset > 0) && (index < idx))) {
return indexes;
}
// Is idx already present.
for (ptr = indexes; ptr < (indexes + *pnum); ptr++) {
if (*ptr == index) {
// Index to be added is already present, so just need to return
// address to current index array.
return indexes;
}
}
// The index is not already present, so grow the array size by 1
// and add it.
ptr = realloc(indexes, sizeof(sb_idx_t) * (*pnum + 1));
if (ptr == NULL) {
fputs("Insufficient Memory\n", stderr);
exit(28);
}
(*pnum)++;
*(ptr + (*pnum - 1)) = index;
return ptr;
}
static int idx_cmp(const void *elem1, const void *elem2)
{
sb_idx_t idx1 = *((sb_idx_t *)elem1);
sb_idx_t idx2 = *((sb_idx_t *)elem2);
if (idx1 > idx2) return 1;
if (idx1 < idx2) return -1;
return 0;
}
static void usage(FILE *stream)
{
fputs("usage: test_adjacent [-n nodes_num] [-m edge_margin] [-h?]\n",
stream);
}
static void help(FILE *stream)
{
usage(stream);
fputs("Sparsebit_c Adjacent Test\n", stream);
fputs(" -n, --nodes_num=NUM: Number of adjacent nodes\n", stream);
fputs(" -m, --edge_margin=NUM: Size of edge margin\n", stream);
fputs(" -?h,--help: Help\n", stream);
}
Raw
test_prand.c
/* Copyright 2020 Louis Huemiller Jr.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "sparsebit_c.h" // Intentionally included first, to aid in
// detection of includes, that may be missing
// within sparsebit_c.h.
#include <argz.h> // Included for definition of error_t on Arm based systems.
#include <assert.h>
#include <errno.h>
#include <getopt.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#define DEFAULT_PASS_START 0
#define DEFAULT_PASS_END 10000
#define PASSED_DISPLAY_STRIDE 100
#define NUM_TEST_RANGES 6
#define BITS_PER_TEST_RANGE 300
#define PER_PASS_NUM_OPS 1000
#define NTH_IDX_PREFERRED_RANGE 100
#define MEMCLEAR(p, n) memset((p), 0, (n))
#define NUM(a) (sizeof(a)/sizeof((a)[0]))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define USE_DEFAULT_RANGE_THRESHOLD ((int)((float)RAND_MAX * 0.05))
sb_idx_t default_ranges[] = {
0,
(SB_IDX_MAX / 2) - (BITS_PER_TEST_RANGE / 2),
(SB_IDX_MAX - BITS_PER_TEST_RANGE) + 1,
};
#define RAND_IDX() (((rand() & (((sb_idx_t)1 << 32) - 1)) << 32) | rand())
struct test_range {
sb_idx_t start_idx;
bool expected[BITS_PER_TEST_RANGE];
};
struct test_range test_ranges[NUM_TEST_RANGES];
enum OP {
SET_BIT = 132,
SET_NUM,
CLEAR_BIT,
CLEAR_NUM,
QUERY_ANYSET,
QUERY_NUMSET,
QUERY_ISSET,
QUERY_FIRSTSET,
QUERY_NEXTSET,
QUERY_PREVSET,
QUERY_ANYCLEARED,
QUERY_NUMCLEARED,
QUERY_ISCLEARED,
QUERY_FIRSTCLEARED,
QUERY_NEXTCLEARED,
QUERY_PREVCLEARED,
QUERY_NTHSET,
};
struct op_str {
enum OP op;
char *str;
} op_strings[] = {
{SET_BIT, "SET_BIT"},
{SET_NUM, "SET_NUM"},
{CLEAR_BIT, "CLEAR_BIT"},
{CLEAR_NUM, "CLEAR_NUM"},
{QUERY_ANYSET, "QUERY_ANYSET"},
{QUERY_NUMSET, "QUERY_NUMSET"},
{QUERY_ISSET, "QUERY_ISSET"},
{QUERY_FIRSTSET, "QUERY_FIRSTSET"},
{QUERY_NEXTSET, "QUERY_NEXTSET"},
{QUERY_PREVSET, "QUERY_PREVSET"},
{QUERY_ANYCLEARED, "QUERY_ANYCLEARED"},
{QUERY_NUMCLEARED, "QUERY_NUMCLEARED"},
{QUERY_ISCLEARED, "QUERY_ISCLEARED"},
{QUERY_FIRSTCLEARED, "QUERY_FIRSTCLEARED"},
{QUERY_NEXTCLEARED, "QUERY_NEXTCLEARED"},
{QUERY_PREVCLEARED, "QUERY_PREVCLEARED"},
{QUERY_NTHSET, "QUERY_NTHSET"},
};
#define OP_TYPE_FIRST (op_strings[0].op)
#define OP_TYPE_LAST (op_strings[NUM(op_strings) - 1].op)
#define OP_TYPE_NUM (OP_TYPE_LAST - OP_TYPE_FIRST + 1)
struct operation {
unsigned int range_idx;
enum OP op;
unsigned int offset;
sb_num_t num;
sb_idx_t nth_idx;
};
struct operation operations[PER_PASS_NUM_OPS];
static void usage(FILE *stream);
static void help(FILE *stream);
static void display_passed_passes(long *palready_displayed, long last_passed);
static void display_operations(FILE *stream);
static const char *op_string(enum OP op);
static int range_idx_cmp(const void *elem1, const void *elem2);
static sb_num_t range_numset(unsigned int range_idx);
static sb_idx_t range_firstset(unsigned int range_idx);
static bool range_supports_idx(unsigned int range_idx, sb_idx_t idx);
static bool expected_isset(sb_idx_t idx);
static sb_num_t expected_numset(void);
static sb_idx_t expected_firstset(void);
static sb_idx_t expected_nextset(sb_idx_t start_idx);
static sb_idx_t expected_prevset(sb_idx_t start_idx);
static sb_idx_t expected_firstcleared(void);
static sb_idx_t expected_nextcleared(sb_idx_t start_idx);
static sb_idx_t expected_prevcleared(sb_idx_t start_idx);
static sb_idx_t expected_nthset_rv(sb_idx_t nth_idx);
int main(int argc, char *argv[])
{
// Command-line Parsing
long pass_start = DEFAULT_PASS_START;
long pass_end = DEFAULT_PASS_END;
static const struct option options[] = {
{} // End-of-Array Marker
};
int opt;
bool error;
while ((opt = getopt_long(argc, argv, "h?", options, NULL)) != EOF) {
switch (opt) {
case 'h':
case '?':
default:
error = ((optopt != 0) && (optopt != '?') && (optopt != 'h'));
if (error) {
usage(stderr);
} else {
help(stdout);
return 0;
}
exit(20);
}
}
if ((argc - optind) > 2) {
fputs("Unexpected positional command-line arguments", stderr);
exit(21);
}
if ((argc - optind) >= 1) {
char *endptr;
pass_start = strtol(argv[optind], &endptr, 10);
if ((endptr == argv[optind]) || (*endptr != '\0') || (pass_start < 0)) {
fprintf(stderr, "Invalid pass_start of %s\n", argv[optind]);
exit(22);
}
if ((argc - optind) == 2) {
pass_end = strtol(argv[optind + 1], &endptr, 10);
if ((endptr == argv[optind + 1]) || (*endptr != '\0') || (pass_end < 0)) {
fprintf(stderr, "Invalid pass_end of %s\n", argv[optind + 1]);
exit(23);
}
} else {
pass_end = pass_start;
}
}
printf("pass_start: %lu\n", pass_start);
printf("pass_end: %lu\n", pass_end);
puts("");
if (pass_end < pass_start) {
fputs("Pass_start must be before pass_end\n", stderr);
exit(24);
}
long pass, passed_last_displayed = pass_start - 1;
for (pass = pass_start; pass <= pass_end; pass++) {
unsigned int num_ops;
// Per-pass initilization
srand(pass);
MEMCLEAR(&test_ranges, sizeof(test_ranges));
// Pseudo-randomly select the start of the ranges. Typically cause the
// first three ranges to be at the beginning, across the exact middle, and
// end of supported range of indexes. These ranges are more likely to
// have index specific issues due to warp-around/overflow between
// the highest to lowest index and improper use of a signed versus
// unsigned index.
// bool force_default_ranges =
bool use_default_ranges = (rand() >= USE_DEFAULT_RANGE_THRESHOLD)
? true : false;
for (unsigned int range_idx = 0; range_idx < NUM(test_ranges);
range_idx++) {
bool idx_overlaps = false;
sb_idx_t idx;
do {
idx_overlaps = false;
idx = ((use_default_ranges)
&& (range_idx < NUM(default_ranges)))
? default_ranges[range_idx] : RAND_IDX();
// Does the chosen starting index desribe a range that extends
// beyond the maximum supported index?
if ((((idx + BITS_PER_TEST_RANGE) - 1) > SB_IDX_MAX)
|| (((idx + BITS_PER_TEST_RANGE) - 1) < idx) ) {
idx_overlaps = true;
continue;
}
// Does chosen idx overlap with any of the ranges already setup?
for (unsigned int range_idx2 = 0; range_idx2 < range_idx;
range_idx2++) {
if ((idx >= test_ranges[range_idx2].start_idx)
&& (idx < test_ranges[range_idx2].start_idx
+ BITS_PER_TEST_RANGE)) {
idx_overlaps = true;
break;
}
}
} while (idx_overlaps);
test_ranges[range_idx].start_idx = idx;
}
// Sort the range indexes into asscending order.
qsort(test_ranges, NUM(test_ranges), sizeof(*test_ranges),
range_idx_cmp);
// Pseudo-Randomly determine the operations to be performed.
MEMCLEAR(operations, sizeof(operations));
for (unsigned int op_idx = 0; op_idx < NUM(operations); op_idx++) {
operations[op_idx].range_idx = rand() % NUM(test_ranges);
operations[op_idx].op = OP_TYPE_FIRST + (rand() % OP_TYPE_NUM);
operations[op_idx].offset = rand() % BITS_PER_TEST_RANGE;
if ((operations[op_idx].op == SET_NUM)
|| (operations[op_idx].op == CLEAR_NUM)) {
operations[op_idx].num = rand()
% ((BITS_PER_TEST_RANGE - operations[op_idx].offset) + 1);
}
if (operations[op_idx].op == QUERY_NTHSET) {
// Half the time, select an Nth index within the preferred
// Nth index range, otherwise use a range of the maximum
// number of test bits that could be ever be set.
sb_num_t nth_idx_range = (rand() % 2) ? NTH_IDX_PREFERRED_RANGE
: (BITS_PER_TEST_RANGE * NUM_TEST_RANGES);
operations[op_idx].nth_idx = rand() % nth_idx_range;
}
}
// ==== Perform ====
sb_t *sb = sb_create();
if (sb == NULL) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: sb_create() failed\n", pass);
exit(30);
}
// Perform the pseudo-randomly selected operations.
for (struct operation *p_op = operations;
p_op < (operations + NUM(operations)); p_op++) {
bool expected_bool;
sb_idx_t expected_idx;
sb_idx_t expected_idx_rv;
sb_num_t expected_num;
bool actual_bool;
sb_idx_t actual_idx;
sb_idx_t actual_idx_rv;
sb_num_t actual_num;
error_t errno_orig;
error_t expected_errno;
error_t actual_errno;
sb_idx_t idx = test_ranges[p_op->range_idx].start_idx + p_op->offset;
switch (p_op->op) {
case SET_BIT:
sb_set(sb, idx);
test_ranges[p_op->range_idx].expected[p_op->offset] = true;
break;
case SET_NUM:
sb_setnum(sb, idx, p_op->num);
for (unsigned int n1 = 0; n1 < p_op->num; n1++) {
test_ranges[p_op->range_idx].expected[p_op->offset + n1] = true;
}
break;
case QUERY_ANYSET:
expected_bool = (expected_numset() > 0) ? true : false;
actual_bool = sb_anyset(sb);
if (expected_bool != actual_bool) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_ANYSET Unexpected Any Set:\n"
" actual: %i expected: %i\n",
pass, actual_bool, expected_bool);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(40);
}
break;
case QUERY_NUMSET:
expected_num = expected_numset();
actual_num = sb_numset(sb);
if (expected_num != actual_num) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_NUMSET Unexpected Num Set:\n"
" actual: %#" SB_PRI_NUM " expected: %#" SB_PRI_NUM "\n",
pass, actual_num, expected_num);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(41);
}
break;
case QUERY_ISSET:
expected_bool = expected_isset(idx);
actual_bool = sb_isset(sb, idx);
if (expected_bool != actual_bool) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_ISSET Unexpected Is Set:\n"
" actual: %i expected: %i idx: %#" SB_PRI_IDX "\n",
pass, actual_bool, expected_bool, idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(42);
}
break;
case QUERY_FIRSTSET:
expected_idx = expected_firstset();
actual_idx = sb_firstset(sb);
if (expected_idx != actual_idx) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_FIRSTSET Unexpected First Set:\n"
" actual: %#" SB_PRI_IDX " expected: %#" SB_PRI_IDX "\n",
pass, actual_idx, expected_idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(43);
}
break;
case QUERY_NEXTSET:
expected_idx = expected_nextset(idx);
actual_idx = sb_nextset(sb, idx);
if (expected_idx != actual_idx) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_NEXTSET Unexpected Next Set:\n"
" actual: %#" SB_PRI_IDX " expected: %#" SB_PRI_IDX
" idx: %#" SB_PRI_IDX "\n",
pass, actual_idx, expected_idx, idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(44);
}
break;
case QUERY_PREVSET:
expected_idx = expected_prevset(idx);
actual_idx = sb_prevset(sb, idx);
if (expected_idx != actual_idx) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_PREVSET Unexpected Previous Set:\n"
" actual: %#" SB_PRI_IDX " expected: %#" SB_PRI_IDX
" idx: %#" SB_PRI_IDX "\n",
pass, actual_idx, expected_idx, idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(45);
}
break;
case CLEAR_BIT:
sb_clear(sb, idx);
test_ranges[p_op->range_idx].expected[p_op->offset] = false;
break;
case CLEAR_NUM:
sb_clearnum(sb, idx, p_op->num);
for (unsigned int n1 = 0; n1 < p_op->num; n1++) {
test_ranges[p_op->range_idx].expected[p_op->offset + n1] = false;
}
break;
case QUERY_ANYCLEARED:
expected_bool = true; // There are always at least some cleared
// bits between the test ranges. So far
// the implementation of this test
// never sets all bits.
actual_bool = sb_anycleared(sb);
if (expected_bool != actual_bool) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_ANYCLEARED Unexpected Any Cleared:\n"
" actual: %i expected: %i\n",
pass, actual_bool, expected_bool);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(50);
}
break;
case QUERY_NUMCLEARED:
expected_num = (sb_num_t) 0 - expected_numset();
actual_num = sb_numcleared(sb);
if (expected_num != actual_num) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_NUMCLEARED Unexpected Num Cleared:\n"
" actual: %#" SB_PRI_NUM " expected: %#" SB_PRI_NUM "\n",
pass, actual_num, expected_num);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(51);
}
break;
case QUERY_ISCLEARED:
expected_bool = !expected_isset(idx);
actual_bool = sb_iscleared(sb, idx);
if (expected_bool != actual_bool) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_ISCLEARED Unexpected Is Cleared:\n"
" actual: %i expected: %i idx: %#" SB_PRI_IDX "\n",
pass, actual_bool, expected_bool, idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(52);
}
break;
case QUERY_FIRSTCLEARED:
expected_idx = expected_firstcleared();
actual_idx = sb_firstcleared(sb);
if (expected_idx != actual_idx) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_FIRSTCLEARED Unexpected First Cleared:\n"
" actual: %#" SB_PRI_IDX " expected: %#" SB_PRI_IDX "\n",
pass, actual_idx, expected_idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(53);
}
break;
case QUERY_NEXTCLEARED:
expected_idx = expected_nextcleared(idx);
actual_idx = sb_nextcleared(sb, idx);
if (expected_idx != actual_idx) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_NEXTCLEARED Unexpected Next Cleared:\n"
" actual: %#" SB_PRI_IDX " expected: %#" SB_PRI_IDX
" idx: %#" SB_PRI_IDX "\n",
pass, actual_idx, expected_idx, idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(54);
}
break;
case QUERY_PREVCLEARED:
expected_idx = expected_prevcleared(idx);
actual_idx = sb_prevcleared(sb, idx);
if (expected_idx != actual_idx) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_PREVCLEARED Unexpected Previous Cleared:\n"
" actual: %#" SB_PRI_IDX " expected: %#" SB_PRI_IDX
" idx: %#" SB_PRI_IDX "\n",
pass, actual_idx, expected_idx, idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(55);
}
break;
case QUERY_NTHSET:
errno_orig = MAX((p_op - operations) % 100, 1);
expected_idx_rv = expected_nthset_rv(p_op->nth_idx);
error_t expected_errno = (p_op->nth_idx >= expected_numset())
? ESRCH : errno_orig;
errno = errno_orig;
actual_idx_rv = sb_nthset(sb, p_op->nth_idx);
actual_errno = errno;
if (actual_idx_rv != expected_idx_rv) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_NTHSET Unexpected Return Value:\n"
" actual: %#" SB_PRI_IDX " expected: %#" SB_PRI_IDX
" nth_idx: %#" SB_PRI_IDX "\n",
pass, actual_idx_rv, expected_idx_rv, p_op->nth_idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(56);
}
if (actual_errno != expected_errno) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"QUERY_NTHSET Unexpected errno Value:\n"
" actual: %u expected: %u"
" nth_idx: %#" SB_PRI_IDX "\n",
pass, actual_errno, expected_errno, p_op->nth_idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(57);
}
break;
default:
assert(false); // Unexpected operation
}
}
// ==== Validation ====
// Validate internal state.
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"Inconsitent Internal State:\n%s\n", pass, err_string);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(31);
}
// Validate Individual Bit Settings
// within the expected bit array of each range.
for (unsigned int range_idx = 0; range_idx < NUM(test_ranges);
range_idx++) {
for (unsigned int bit_idx = 0;
bit_idx < NUM(test_ranges[range_idx].expected); bit_idx++) {
sb_idx_t idx = test_ranges[range_idx].start_idx + bit_idx;
bool expected = expected_isset(idx);
bool actual = sb_isset(sb, idx) ? true : false;
if (actual != expected) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"Unexpected Bit Setting:\n"
" idx: %#" SB_PRI_IDX " actual: %i expected: %i\n",
pass, idx, actual, expected);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(32);
}
}
}
// Validate Num Set Bits
sb_num_t expected_num = expected_numset();
sb_num_t actual_num = sb_numset(sb);
if (actual_num != expected_num) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"Unexpected Num Bits Set:\n"
" actual: %#" SB_PRI_NUM " expected: %#" SB_PRI_NUM "\n",
pass, actual_num, expected_num);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(33);
}
// Validate sb_firstset()
sb_idx_t expected_idx = expected_firstset();
sb_idx_t actual_firstset = sb_firstset(sb);
if (actual_firstset != expected_idx) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"Unexpected First Set:\n"
" actual: %#" SB_PRI_IDX " expected: %#" SB_PRI_IDX "\n",
pass, actual_firstset, expected_idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(34);
}
// Validate sb_nextset()
// Will validate sb_nextset() for every bit index within a range, plus
// where valid the bit indexes for two bits immediately before and
// immediately after each range.
for (unsigned int range_idx = 0; range_idx < NUM(test_ranges);
range_idx++) {
struct test_range *p_range = &test_ranges[range_idx];
for (int bit_idx = -2; bit_idx < ((int)NUM(p_range->expected) + 2);
bit_idx++) {
sb_idx_t idx1 = p_range->start_idx + bit_idx;
if ((bit_idx < 0) && (idx1 > p_range->start_idx) ) {
continue;
}
if ((bit_idx > 0) && (idx1 < p_range->start_idx) ) {
continue;
}
expected_idx = expected_nextset(idx1);
sb_idx_t actual = sb_nextset(sb, idx1);
if (actual != expected_idx) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"Unexpected Next Set:\n"
" idx1: %#" SB_PRI_IDX " actual: %#" SB_PRI_IDX
" expected: %#" SB_PRI_IDX "\n",
pass, idx1, actual, expected_idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(35);
}
}
}
// Validate sb_nextcleared()
// Will validate sb_nextcleared() for every bit index within a range, plus
// where valid the bit indexes for two bits immediately before and
// immediately after each range.
for (unsigned int range_idx = 0; range_idx < NUM(test_ranges);
range_idx++) {
struct test_range *p_range = &test_ranges[range_idx];
for (int bit_idx = -2; bit_idx < ((int)NUM(p_range->expected) + 2);
bit_idx++) {
sb_idx_t idx1 = p_range->start_idx + bit_idx;
if ((bit_idx < 0) && (idx1 > p_range->start_idx) ) {
continue;
}
if ((bit_idx > 0) && (idx1 < p_range->start_idx) ) {
continue;
}
expected_idx = expected_nextcleared(idx1);
sb_idx_t actual = sb_nextcleared(sb, idx1);
if (actual != expected_idx) {
display_passed_passes(&passed_last_displayed, pass - 1);
fprintf(stderr, "Pass %li: Validation Error - "
"Unexpected Next Cleared:\n"
" idx1: %#" SB_PRI_IDX " actual: %#" SB_PRI_IDX
" expected: %#" SB_PRI_IDX "\n",
pass, idx1, actual, expected_idx);
display_operations(stderr);
fputs(sb_dump(sb), stderr);
exit(36);
}
}
}
sb_delete(sb);
// Every stride worth of passes, display which passes have passed.
if ((pass != 0) && (pass % PASSED_DISPLAY_STRIDE) == 0) {
display_passed_passes(&passed_last_displayed, pass);
}
}
display_passed_passes(&passed_last_displayed, pass - 1);
return 0;
}
static void usage(FILE *stream)
{
fputs("usage: test_prand [-h?] [pass_start [pass_end]]\n", stream);
}
static void help(FILE *stream)
{
usage(stream);
fputs("Sparsebit_c Pseudo-Random Test\n", stream);
fputs(" -?h,--help Help\n", stream);
fputs(" pass_start: Starting pass number (default: 0)\n", stream);
fputs(" pass_end: Ending pass number (default: 10000)\n", stream);
}
static void display_passed_passes(long *palready_displayed, long last_passed)
{
if (last_passed <= *palready_displayed) {
// Display of passed passes already up to date.
return;
}
// Need to display 1 or a range of passed passes?
if (last_passed == (*palready_displayed + 1)) {
printf("Pass %6li: Passed\n", last_passed);
} else {
printf("Passes %6li to %6li: Passed\n", *palready_displayed + 1,
last_passed);
}
fflush(stdout);
*palready_displayed = last_passed;
return;
}
static void display_operations(FILE *stream)
{
fputs("Operations:\n", stderr);
for (unsigned int opt_idx = 0; opt_idx < NUM(operations); opt_idx++) {
fprintf(stderr, " %3u %u (%s)%*s idx: %#" SB_PRI_IDX
" num: %#" SB_PRI_NUM
" nth_idx: %#" SB_PRI_IDX "\n",
opt_idx, operations[opt_idx].op,
op_string(operations[opt_idx].op),
(int) (18 - strlen(op_string(operations[opt_idx].op))), "",
test_ranges[operations[opt_idx].range_idx].start_idx
+ operations[opt_idx].offset,
operations[opt_idx].num,
operations[opt_idx].nth_idx);
}
}
static const char *op_string(enum OP op)
{
static const char *unknown_str = "Unknown";
for (unsigned int n1 = 0; n1 < NUM(op_strings); n1++) {
if (op_strings[n1].op == op) {
return op_strings[n1].str;
}
}
return unknown_str;
}
static int range_idx_cmp(const void *elem1, const void *elem2)
{
sb_idx_t idx1 = ((struct test_range*)elem1)->start_idx;
sb_idx_t idx2 = ((struct test_range*)elem2)->start_idx;
if (idx1 > idx2) return 1;
if (idx1 < idx2) return -1;
return 0;
}
static sb_num_t range_numset(unsigned int range_idx)
{
sb_num_t total = 0;
struct test_range *p_range = &test_ranges[range_idx];
for (unsigned int n1 = 0; n1 < NUM(p_range->expected); n1++) {
if (p_range->expected[n1]) {
total++;
}
}
return total;
}
static sb_idx_t range_firstset(unsigned int range_idx)
{
struct test_range *p_range = &test_ranges[range_idx];
for (unsigned int n1 = 0; n1 < NUM(p_range->expected); n1++) {
if (p_range->expected[n1]) {
return p_range->start_idx + n1;
}
}
assert(0); // Caller should only call range_firstset, when range has
// atleast one set bit.
}
static bool range_supports_idx(unsigned int range_idx, sb_idx_t idx)
{
assert(range_idx < NUM(test_ranges));
struct test_range *p_range = &test_ranges[range_idx];
if ((idx >= p_range->start_idx)
&& (idx <= ((p_range->start_idx + NUM(p_range->expected)) - 1)) ) {
return true;
}
return false;
}
static bool expected_isset(sb_idx_t idx)
{
for (unsigned int range_idx = 0; range_idx < NUM(test_ranges); range_idx++) {
// Does this range maintain the expected state of idx?
if ((idx >= test_ranges[range_idx].start_idx)
&& (idx <= (test_ranges[range_idx].start_idx
+ NUM(test_ranges[range_idx].expected) - 1))) {
return test_ranges[range_idx].expected[idx
- test_ranges[range_idx].start_idx];
}
}
// No range that maintains the expected setting of the bit at index idx,
// so the bit should always be cleared.
return false;
}
static sb_num_t expected_numset(void)
{
sb_num_t expected_numset = 0;
for (unsigned int range_idx = 0; range_idx < NUM(test_ranges); range_idx++) {
expected_numset += range_numset(range_idx);
}
return expected_numset;
}
static sb_idx_t expected_firstset(void)
{
for (unsigned int range_idx = 0; range_idx < NUM(test_ranges); range_idx++) {
if (range_numset(range_idx)) {
return range_firstset(range_idx);
}
}
// No set bits, in any range.
return 0;
}
static sb_idx_t expected_nextset(sb_idx_t start_idx)
{
for (unsigned int range_idx = 0; range_idx < NUM(test_ranges); range_idx++) {
struct test_range *p_range = &test_ranges[range_idx];
for (unsigned int bit_idx = 0; bit_idx < NUM(p_range->expected);
bit_idx++) {
sb_idx_t idx = p_range->start_idx + bit_idx;
if (idx <= start_idx) {
continue;
}
if (p_range->expected[bit_idx]) {
return idx;
}
}
}
return 0;
}
static sb_idx_t expected_prevset(sb_idx_t start_idx)
{
for (int range_idx = NUM(test_ranges) - 1; range_idx >= 0; range_idx--) {
struct test_range *p_range = &test_ranges[range_idx];
if (p_range->start_idx >= start_idx) { continue; }
for (int bit_idx = NUM(p_range->expected) - 1; bit_idx >= 0; bit_idx--) {
sb_idx_t idx = p_range->start_idx + bit_idx;
if (idx >= start_idx) {
continue;
}
if (p_range->expected[bit_idx]) {
return idx;
}
}
}
return 0;
}
static sb_idx_t expected_firstcleared(void)
{
if (test_ranges[0].start_idx != 0) {
// Fix test range starts at an index > 0. All bits before the start
// of that range are cleared, including the bit at index 0.
return 0;
}
for (unsigned int range_idx = 0; range_idx < NUM(test_ranges); range_idx++) {
for (int bit_idx = 0; bit_idx
< NUM(test_ranges[range_idx].expected); bit_idx++) {
if (!test_ranges[range_idx].expected[bit_idx]) {
return test_ranges[range_idx].start_idx + bit_idx;
}
}
// Is there a gap between this and the next test range?
if ((range_idx + 1) < NUM(test_ranges)) {
// There is a gap. Return index of first bit within the gap.
return test_ranges[range_idx].start_idx
+ NUM(test_ranges[range_idx].expected);
} else {
// First cleared bit will be the first bit index after the last
// test range.
assert(range_idx == (NUM(test_ranges) - 1));
assert((test_ranges[range_idx].start_idx
+ NUM(test_ranges[range_idx].expected)) != 0);
return test_ranges[range_idx].start_idx
+ NUM(test_ranges[range_idx].expected);
}
}
assert(false); // So far the implementation of this testcase does not
// allow all bits to be set. Thus there should always
// be at least one cleared bit.
// NOT REACHED
}
static sb_idx_t expected_nextcleared(sb_idx_t start_idx)
{
if (start_idx == SB_IDX_MAX) {
return 0;
}
// If start_idx + 1 is not supported by any test range, then
// start_idx + 1 is the next cleared bit.
unsigned int range_idx;
for (range_idx = 0; range_idx < NUM(test_ranges); range_idx++) {
if (range_supports_idx(range_idx, start_idx + 1)) {
break;
}
}
if (range_idx >= NUM(test_ranges)) {
assert(range_idx == NUM(test_ranges));
return start_idx + 1;
}
// First cleared bit within a test range > start_idx is the next
// cleared bit.
for (unsigned int range_idx = 0; range_idx < NUM(test_ranges); range_idx++) {
struct test_range *p_range = &test_ranges[range_idx];
if (!range_supports_idx(range_idx, start_idx + 1)) {
continue;
}
for (int bit_idx = 0; bit_idx < NUM(p_range->expected);
bit_idx++) {
sb_idx_t idx = p_range->start_idx + bit_idx;
if ((idx > start_idx) && !p_range->expected[bit_idx]) {
return idx;
}
}
// If next range not adjacent, then return index of first bit within
// the gap between this and the next range.
if ((range_idx == NUM(test_ranges) - 1)
|| ((p_range->start_idx + BITS_PER_TEST_RANGE)
!= (p_range + 1)->start_idx) ) {
return p_range->start_idx + BITS_PER_TEST_RANGE;
}
}
return 0;
}
static sb_idx_t expected_prevcleared(sb_idx_t start_idx)
{
for (int range_idx = NUM(test_ranges) - 1; range_idx >= 0; range_idx--) {
struct test_range *p_range = &test_ranges[range_idx];
if (p_range->start_idx > start_idx) { continue; }
for (int bit_idx = NUM(p_range->expected) - 1; bit_idx >= 0; bit_idx--) {
sb_idx_t idx = p_range->start_idx + bit_idx;
if (idx >= start_idx) {
continue;
}
if (!p_range->expected[bit_idx]) {
return idx;
}
}
// If gap between current and previous range, return index of highest
// bit in the gap.
if (range_idx >= 1) {
struct test_range *p_range_prev = &test_ranges[range_idx - 1];
if ((p_range_prev->start_idx + NUM(p_range_prev->expected))
< p_range->start_idx) {
assert(p_range->start_idx >= 1);
return p_range->start_idx - 1;
}
}
}
return (test_ranges[0].start_idx >= 1)
? test_ranges[0].start_idx - 1 : 0;
}
static sb_idx_t expected_nthset_rv(sb_idx_t nth_idx)
{
sb_num_t num = 0;
// For each test range.
for (struct test_range *p_range = test_ranges;
p_range < test_ranges + NUM(test_ranges); p_range++) {
// For each bit in the current test range.
for (unsigned int bit_idx = 0; bit_idx < NUM(p_range->expected);
bit_idx++) {
if (p_range->expected[bit_idx]) {
if (num == nth_idx) {
return p_range->start_idx + bit_idx;
}
num++;
}
}
}
return 0;
}
Raw
test_unit.c
/* Copyright 2020 Louis Huemiller Jr.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "sparsebit_c.h" // Intentionally included first, to aid in
// detection of includes, that may be missing
// within sparsebit_c.h.
#include <argz.h> // Included for definition of error_t on Arm based systems.
#include <assert.h>
#include <errno.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <CUnit/Basic.h>
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define NUM(a) (sizeof(a)/sizeof((a)[0]))
#define MEMCLEAR(p, n) memset((p), 0, (n))
void test_create_delete(void)
{
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
void test_set(void)
{
int rv;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set bit at index 5.
rv = sb_set(sb, 5);
CU_ASSERT_EQUAL_FATAL(rv, 0);
CU_ASSERT_FALSE(sb_isset(sb, 0));
CU_ASSERT_FALSE(!sb_iscleared(sb, 0));
CU_ASSERT_FALSE(sb_isset(sb, 1));
CU_ASSERT_FALSE(!sb_iscleared(sb, 1));
CU_ASSERT_FALSE(sb_isset(sb, 2));
CU_ASSERT_FALSE(!sb_iscleared(sb, 2));
CU_ASSERT_FALSE(sb_isset(sb, 3));
CU_ASSERT_FALSE(!sb_iscleared(sb, 3));
CU_ASSERT_FALSE(sb_isset(sb, 4));
CU_ASSERT_FALSE(!sb_iscleared(sb, 4));
CU_ASSERT_TRUE(sb_isset(sb, 5));
CU_ASSERT_TRUE(!sb_iscleared(sb, 5));
CU_ASSERT_FALSE(sb_isset(sb, 6));
CU_ASSERT_FALSE(!sb_iscleared(sb, 6));
CU_ASSERT_FALSE(sb_isset(sb, 7));
CU_ASSERT_FALSE(!sb_iscleared(sb, 7));
CU_ASSERT_FALSE(sb_isset(sb, 8));
CU_ASSERT_FALSE(!sb_iscleared(sb, 8));
CU_ASSERT_FALSE(sb_isset(sb, 9));
CU_ASSERT_FALSE(!sb_iscleared(sb, 9));
CU_ASSERT_FALSE(sb_isset(sb, 10));
CU_ASSERT_FALSE(!sb_iscleared(sb, 10));
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
void test_clear(void)
{
int rv;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set a few bits.
rv = sb_set(sb, 2);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_set(sb, 4);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_set(sb, 8);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_set(sb, 9);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_set(sb, 10);
CU_ASSERT_EQUAL_FATAL(rv, 0);
// Clear a few bits, including one that is already cleared.
rv = sb_clear(sb, 4);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_clear(sb, 6);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_clear(sb, 9);
CU_ASSERT_EQUAL_FATAL(rv, 0);
CU_ASSERT_FALSE(sb_isset(sb, 0));
CU_ASSERT_FALSE(!sb_iscleared(sb, 0));
CU_ASSERT_FALSE(sb_isset(sb, 1));
CU_ASSERT_FALSE(!sb_iscleared(sb, 1));
CU_ASSERT_TRUE(sb_isset(sb, 2));
CU_ASSERT_TRUE(!sb_iscleared(sb, 2));
CU_ASSERT_FALSE(sb_isset(sb, 3));
CU_ASSERT_FALSE(!sb_iscleared(sb, 3));
CU_ASSERT_FALSE(sb_isset(sb, 4));
CU_ASSERT_FALSE(!sb_iscleared(sb, 4));
CU_ASSERT_FALSE(sb_isset(sb, 5));
CU_ASSERT_FALSE(!sb_iscleared(sb, 5));
CU_ASSERT_FALSE(sb_isset(sb, 6));
CU_ASSERT_FALSE(!sb_iscleared(sb, 6));
CU_ASSERT_FALSE(sb_isset(sb, 7));
CU_ASSERT_FALSE(!sb_iscleared(sb, 7));
CU_ASSERT_TRUE(sb_isset(sb, 8));
CU_ASSERT_TRUE(!sb_iscleared(sb, 8));
CU_ASSERT_FALSE(sb_isset(sb, 9));
CU_ASSERT_FALSE(!sb_iscleared(sb, 9));
CU_ASSERT_TRUE(sb_isset(sb, 10));
CU_ASSERT_TRUE(!sb_iscleared(sb, 10));
CU_ASSERT_FALSE(sb_isset(sb, 11));
CU_ASSERT_FALSE(!sb_iscleared(sb, 11));
CU_ASSERT_FALSE(sb_isset(sb, 12));
CU_ASSERT_FALSE(!sb_iscleared(sb, 12));
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
void test_multinode(void)
{
int rv;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set two bits, with indexes sufficently different that their state
// can't be described in the mask of a single node.
sb_idx_t idx1 = 73;
sb_idx_t idx2 = 173;
rv = sb_set(sb, idx1);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_set(sb, idx2);
CU_ASSERT_EQUAL_FATAL(rv, 0);
unsigned int pad = 10;
for (sb_idx_t idx = (MIN(idx1, idx2) - pad);
idx < (MAX(idx1, idx2) + pad); idx++) {
if ((idx != idx1) && (idx != idx2)) {
CU_ASSERT_FALSE(sb_isset(sb, idx));
CU_ASSERT_TRUE(sb_iscleared(sb, idx));
} else {
CU_ASSERT_TRUE(sb_isset(sb, idx));
CU_ASSERT_FALSE(sb_iscleared(sb, idx));
}
}
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
void test_clear_two_nodes(void)
{
int rv;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Create 5 distinct nodes.
sb_idx_t idx1 = 20;
sb_idx_t idx2 = 328;
sb_idx_t idx3 = 732;
sb_idx_t idx4 = 923;
sb_idx_t idx5 = 2056;
rv = sb_set(sb, idx1);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_set(sb, idx2);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_set(sb, idx3);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_set(sb, idx4);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_set(sb, idx5);
CU_ASSERT_EQUAL_FATAL(rv, 0);
// Delete two of the nodes, by clearing all the bits described by the nodes.
rv = sb_clear(sb, idx2);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_clear(sb, idx4);
CU_ASSERT_EQUAL_FATAL(rv, 0);
// Check that bits not cleared are still set.
unsigned int pad = 10;
for (sb_idx_t idx = idx1 - pad; idx < idx2 + pad; idx++) {
if ((idx != idx1) && (idx != idx3) && (idx != idx5)) {
CU_ASSERT_FALSE(sb_isset(sb, idx));
CU_ASSERT_TRUE(sb_iscleared(sb, idx));
} else {
CU_ASSERT_TRUE(sb_isset(sb, idx));
CU_ASSERT_FALSE(sb_iscleared(sb, idx));
}
}
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
void test_first_next_set(void)
{
int rv;
sb_idx_t idx;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set some bits, including ones at the lowest and highest indexes.
sb_idx_t idx_set[] = {
0, 1, 2,
74, 256, 512 - 1,
SB_IDX_MAX - 3, SB_IDX_MAX - 1, SB_IDX_MAX,
};
for (unsigned int n = 0; n < NUM(idx_set); n++) {
rv = sb_set(sb, idx_set[n]);
CU_ASSERT_EQUAL_FATAL(rv, 0);
}
// Clear and reset a bit in the middle, so that a simple binary-tree
// implementation won't store the nodes effectively as a linked-list.
// By creating nodes in accending order, a simple binary-tree implementation
// would only add nodes to the right of the lowest child. By clearing then
// reseting all the bits of a node in the middle, a simple binary-tree
// implementation will add back this node to the left of one of the
// existing nodes.
sb_clear(sb, idx_set[4]);
sb_set(sb, idx_set[4]);
idx = sb_firstset(sb);
CU_ASSERT_EQUAL(idx, idx_set[0]);
for (unsigned int n = 1; n < NUM(idx_set); n++) {
idx = sb_nextset(sb, idx_set[n]);
if ((n + 1) < NUM(idx_set)) {
CU_ASSERT_EQUAL(idx, idx_set[n + 1]);
} else {
CU_ASSERT_EQUAL(idx, 0);
}
}
// Clear the bits at index 0 and index ~0 and test again.
assert(idx_set[0] == 0);
assert(idx_set[NUM(idx_set) - 1] == SB_IDX_MAX);
sb_clear(sb, idx_set[0]);
sb_clear(sb, idx_set[NUM(idx_set) - 1]);
idx = sb_firstset(sb);
CU_ASSERT_EQUAL(idx, idx_set[1]);
for (unsigned int n = 2; n < (NUM(idx_set) - 1); n++) {
idx = sb_nextset(sb, idx_set[n]);
if ((n + 1) < (NUM(idx_set) - 1)) {
CU_ASSERT_EQUAL(idx, idx_set[n + 1]);
} else {
CU_ASSERT_EQUAL(idx, 0);
}
}
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
void test_first_next_cleared(void)
{
int rv;
sb_idx_t idx;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set significant number of bits starting at lowest index and ending
// at highest index.
sb_num_t set_num = 2000;
rv = sb_setnum(sb, 0, set_num);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_setnum(sb, SB_IDX_MAX - set_num + 1, set_num);
CU_ASSERT_EQUAL_FATAL(rv, 0);
// Clear some bits, including ones at the lowest and highest indexes.
sb_idx_t idx_cleared[] = {
0, 1, 2,
68, 316, 1024 - 1, 1024,
SB_IDX_MAX - 3, SB_IDX_MAX - 1, SB_IDX_MAX,
};
for (unsigned int n = 0; n < NUM(idx_cleared); n++) {
rv = sb_clear(sb, idx_cleared[n]);
CU_ASSERT_EQUAL_FATAL(rv, 0);
}
// Clear and reset at least a node worth of bits in the middle, so that a
// simple binary-tree implementation won't store the nodes effectively as
// a linked-list. By creating nodes in accending order, a simple
// binary-tree implementation would only add nodes to the right of the
// lowest child. By clearing then reseting all the bits of a node in the
// middle, a simple binary-tree implementation will add back this node to
// the left of one of the existing nodes.
sb_clearnum(sb, idx_cleared[4] + 1, 100);
sb_setnum(sb, idx_cleared[4] + 1, 100);
idx = sb_firstcleared(sb);
CU_ASSERT_EQUAL(idx, idx_cleared[0]);
for (unsigned int n = 1; n < NUM(idx_cleared); n++) {
idx = sb_nextcleared(sb, idx_cleared[n]);
if ((n + 1) < NUM(idx_cleared)) {
if ((idx_cleared[n] < set_num) && ((idx_cleared[n + 1] > set_num))) {
CU_ASSERT_EQUAL(idx, set_num);
} else {
CU_ASSERT_EQUAL(idx, idx_cleared[n + 1]);
}
} else {
CU_ASSERT_EQUAL(idx, 0);
}
}
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
void test_prev_set(void)
{
int rv;
sb_idx_t idx;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set some bits, including ones at the lowest and highest indexes.
sb_idx_t idx_set[] = {
0, 1, 2,
68, 512, 1024 - 1,
SB_IDX_MAX - 3, SB_IDX_MAX - 1, SB_IDX_MAX,
};
for (unsigned int n = 0; n < NUM(idx_set); n++) {
rv = sb_set(sb, idx_set[n]);
CU_ASSERT_EQUAL_FATAL(rv, 0);
}
for (unsigned int n = 0; n < NUM(idx_set); n++) {
sb_idx_t expected_rv = (idx_set[n] == 0) ? 0 : idx_set[n - 1];
sb_idx_t actual_rv = sb_prevset(sb, idx_set[n]);
if (actual_rv != expected_rv) {
fprintf(stderr, "Unexpected sb_prevset rv,\n"
" n: %u idx_set[n]: %#" SB_PRI_IDX "\n"
" actual_rv: %#" SB_PRI_IDX " expected_rv: %#" SB_PRI_IDX "\n",
n, idx_set[n], actual_rv, expected_rv);
CU_ASSERT_EQUAL(actual_rv, expected_rv);
}
}
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
void test_prev_cleared(void)
{
int rv;
sb_idx_t idx;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set significant number of bits starting at lowest index and ending
// at highest index.
sb_num_t set_num = 3000;
rv = sb_setnum(sb, 0, set_num);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_setnum(sb, SB_IDX_MAX - set_num + 1, set_num);
CU_ASSERT_EQUAL_FATAL(rv, 0);
// Clear some bits, including ones at the lowest and highest indexes.
sb_idx_t idx_cleared[] = {
0, 1, 2,
196, 444, 2048 - 1, 2048,
SB_IDX_MAX - 3, SB_IDX_MAX - 1, SB_IDX_MAX,
};
for (unsigned int n = 0; n < NUM(idx_cleared); n++) {
rv = sb_clear(sb, idx_cleared[n]);
CU_ASSERT_EQUAL_FATAL(rv, 0);
}
for (unsigned int n = 0; n < NUM(idx_cleared); n++) {
sb_idx_t expected_rv = (n > 0) ? idx_cleared[n - 1] : 0;
if ((n >= 1)
&& (idx_cleared[n - 1] < (SB_IDX_MAX - set_num + 1))
&& (idx_cleared[n] >= (SB_IDX_MAX - set_num + 1)) ) {
expected_rv = SB_IDX_MAX - set_num;
}
sb_idx_t actual_rv = sb_prevcleared(sb, idx_cleared[n]);
if (actual_rv != expected_rv) {
fprintf(stderr, "Unexpected sb_prevcleared rv,\n"
" n: %u idx_cleared[n]: %#" SB_PRI_IDX "\n"
" actual_rv: %#" SB_PRI_IDX " expected_rv: %#" SB_PRI_IDX "\n",
n, idx_cleared[n], actual_rv, expected_rv);
CU_ASSERT_EQUAL(actual_rv, expected_rv);
}
}
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
void test_nthset(void)
{
int rv;
sb_idx_t idx;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set some bits, including ones at the lowest and highest indexes.
sb_idx_t idx_set[] = {
0, 2, 5, 6,
63, 64, 65,
0x103f,
SB_IDX_MAX - 3, SB_IDX_MAX - 1, SB_IDX_MAX,
};
for (unsigned int n = 0; n < NUM(idx_set); n++) {
rv = sb_set(sb, idx_set[n]);
CU_ASSERT_EQUAL_FATAL(rv, 0);
}
// For number of set bits, plus 3 more. The 3 more, are to validate
// behavior when asking for the index of the Nth bit, beyond the number
// of set bits.
for (unsigned int n = 0; n < NUM(idx_set) + 3; n++) {
sb_idx_t expected_rv = (n < NUM(idx_set)) ? idx_set[n] : 0;
// Set errno to a magic value dependent on the current value of n.
// On success, errno value should be unchanged. On failure, it should
// get set to ESRCH.
error_t errno_magic = 0x7a2c ^ n;
error_t expected_errno = (n < NUM(idx_set)) ? errno_magic : ESRCH;
// Perform sb_nthset operations.
errno = errno_magic;
sb_idx_t actual_rv = sb_nthset(sb, n);
error_t actual_errno = errno;
if (actual_rv != expected_rv) {
fprintf(stderr, "Unexpected sb_nthset rv,\n"
" n: %u\n"
" actual_rv: %#" SB_PRI_IDX " expected_rv: %#" SB_PRI_IDX "\n",
n, actual_rv, expected_rv);
CU_ASSERT_EQUAL(actual_rv, expected_rv);
}
if (actual_errno != expected_errno) {
fprintf(stderr, "Unexpected sb_nthset errno,\n"
" n: %u\n"
" actual_errno: %#x expected_errno: %#x\n",
n, actual_errno, expected_errno);
CU_ASSERT_EQUAL(actual_errno, expected_errno);
}
}
sb_delete(sb);
}
void test_nthset_with_noneset(void)
{
int rv;
sb_idx_t idx;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
for (unsigned int n = 0; n < 5; n++) {
// With no bits set, should always get a return index of 0,
// with errno set to ESRCH.
sb_idx_t expected_rv = 0;
error_t expected_errno = ESRCH;
// Perform the operation
errno = 0;
sb_idx_t actual_rv = sb_nthset(sb, n);
error_t actual_errno = errno;
if (actual_rv != expected_rv) {
fprintf(stderr, "Unexpected sb_nthset rv,\n"
" n: %u\n"
" actual_rv: %#" SB_PRI_IDX " expected_rv: %#" SB_PRI_IDX "\n",
n, actual_rv, expected_rv);
CU_ASSERT_EQUAL(actual_rv, expected_rv);
}
if (actual_errno != expected_errno) {
fprintf(stderr, "Unexpected sb_nthset errno,\n"
" n: %u\n"
" actual_errno: %#x expected_errno: %#x\n",
n, actual_errno, expected_errno);
CU_ASSERT_EQUAL(actual_errno, expected_errno);
}
}
sb_delete(sb);
}
void test_nthset_with_allset(void)
{
int rv;
sb_idx_t idx;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set all bits.
rv = sb_set(sb, 0);
CU_ASSERT_EQUAL_FATAL(rv, 0);
rv = sb_setnum(sb, 1, ((sb_num_t) 0) - 1);
CU_ASSERT_EQUAL_FATAL(rv, 0);
bool first_pass = true;
for (sb_num_t nth_idx = 0; (nth_idx != 0) || first_pass; nth_idx++) {
// Once a few bits at the beginning have been tested, skip to an
// index near the end, so the test will complete in a reasonable
// amount of time.
if (nth_idx == 5) {
nth_idx = SB_IDX_MAX - 5;
}
// With all bits set, return index should be equal to the requested
// Nth index and errno value should be unchanged.
sb_idx_t expected_rv = nth_idx;
error_t errno_magic = 0x38ac ^ (nth_idx % 200);
if (errno_magic == 0) { errno_magic = 0x732a; }
error_t expected_errno = errno_magic;
// Perform the operation
errno = errno_magic;
sb_idx_t actual_rv = sb_nthset(sb, nth_idx);
error_t actual_errno = errno;
if (actual_rv != expected_rv) {
fprintf(stderr, "Unexpected sb_nthset rv,\n"
" nth_idx: %#" SB_PRI_IDX "\n"
" actual_rv: %#" SB_PRI_IDX " expected_rv: %#" SB_PRI_IDX "\n",
nth_idx, actual_rv, expected_rv);
CU_ASSERT_EQUAL(actual_rv, expected_rv);
}
if (actual_errno != expected_errno) {
fprintf(stderr, "Unexpected sb_nthset errno,\n"
" nth_idx: %#" SB_PRI_IDX "\n"
" actual_errno: %#x expected_errno: %#x\n",
nth_idx, actual_errno, expected_errno);
CU_ASSERT_EQUAL(actual_errno, expected_errno);
}
first_pass = false;
}
sb_delete(sb);
}
// Sets then clears 6 bits in all possible orders/permutations. The bits
// indexes are sufficiently seperated such that the state of each bit
// will be maintained by its own node. The primary purpose of this test
// is to validate that the binary-tree used to maintain the nodes is valid
// no matter which order the nodes are added then deleted.
// There is a trade-off between how many nodes are added then deleted and
// how long the test takes to execute. A complete binary tree has 1 node
// at the root (level-0), 2 at level-1, and 4 at level-2. For a total of
// 7 nodes in the first 3 levels. Ideally would validate all permutations
// for the first 3 levels, but that tends to take several minutes to
// execute. This test performs all permutations of just 6 nodes, which
// tends to execute in significantly less than a minute and provides
// nearly the same level of validations. Nearly the same level of validation
// in that the third level of a complete binary-tree will have 3 of the 4
// nodes present, with 2 of them attached to the left and right of the next
// higher level and the 3rd attached to either the left or right of the
// other node in the next higher level.
void test_permutations6(void)
{
unsigned int idx_set[6];
unsigned int idx_clear[6];
sb_idx_t idx_base = 0x2350000;
sb_idx_t idx_stride = 0x100; // At least twice the number of bits
// in a nodes mask, so each of the set
// bits are maintained in a distinct node.
// For each permutation of the Set indexes.
MEMCLEAR(idx_set, sizeof(idx_set));
do {
// Increment Add Indexes
unsigned int n;
for (n = 0; n < NUM(idx_set); n++) {
idx_set[n]++;
if (idx_set[n] < NUM(idx_set)) {
break;
}
idx_set[n] = 0;
}
if (n == NUM(idx_set)) break;
// Skip if any duplicate set indexes.
bool skip = false;
for (unsigned int n1 = 0; n1 < NUM(idx_set) - 1; n1++) {
for (unsigned int n2 = n1 + 1; n2 < NUM(idx_set); n2++) {
if (idx_set[n1] == idx_set[n2]) {
skip = true;
break;
}
}
if (skip) {
break;
}
}
if (skip) continue;
// For each permutation of the clear indexes.
MEMCLEAR(idx_clear, sizeof(idx_clear));
do {
// Increment Clear Indexes
unsigned int n;
for (n = 0; n < NUM(idx_clear); n++) {
idx_clear[n]++;
if (idx_clear[n] < NUM(idx_clear)) {
break;
}
idx_clear[n] = 0;
}
if (n == NUM(idx_clear)) break;
// Skip if any duplicate clear indexes.
bool skip = false;
for (unsigned int n1 = 0; n1 < NUM(idx_clear) - 1; n1++) {
for (unsigned int n2 = n1 + 1; n2 < NUM(idx_clear); n2++) {
if (idx_clear[n1] == idx_clear[n2]) {
skip = true;
break;
}
}
if (skip) {
break;
}
}
if (skip) continue;
sb_t *sb = sb_create();
// Perform the set operations, in the order given by idx_set[].
for (unsigned int n = 0; n < NUM(idx_set); n++) {
sb_set(sb, (idx_set[n] * idx_stride) + idx_base);
}
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
// Perform the clear operations, in the order given by idx_clear[].
for (unsigned int n = 0; n < NUM(idx_clear); n++) {
sb_clear(sb, (idx_clear[n] * idx_stride) + idx_base);
err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
}
err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
} while (true);
} while (true);
}
void test_set_after_single(void)
{
int rv;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set a few bits before a mask boundary
// and then a single bit at the mask boundary.
sb_idx_t boundary = 0x1000;
int offsets[] = {-5, -2, -1, 0};
for (unsigned int n = 0; n < NUM(offsets); n++) {
rv = sb_set(sb, boundary + offsets[n]);
CU_ASSERT_EQUAL_FATAL(rv, 0);
}
sb_num_t num = sb_nodes_num(sb);
CU_ASSERT_EQUAL(num, 1);
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
void test_set_after_clear_single(void)
{
int rv;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set a few bits before a mask boundary and then a few
// contiguous bits starting at the mask boundary.
sb_idx_t boundary = 0x2000;
int offsets[] = {-5, -3, -2, 0, 1, 2, 3, 4};
int offset_clear = 2;
for (unsigned int n = 0; n < NUM(offsets); n++) {
rv = sb_set(sb, boundary + offsets[n]);
CU_ASSERT_EQUAL_FATAL(rv, 0);
}
rv = sb_clear(sb, boundary + offset_clear);
CU_ASSERT_EQUAL_FATAL(rv, 0);
sb_num_t num = sb_nodes_num(sb);
CU_ASSERT_EQUAL(num, 2);
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
void test_set_after_then_clear_mask(void)
{
int rv;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
// Set a single bit before a mask boundary
// and then a few contiguous bits starting at the mask boundary.
// The bits starting at the mask boundary will get described by
// the nodes set_after value.
sb_idx_t boundary = 0x2000;
int offsets[] = {-4, 0, 1, 2};
int offset_clear = -4;
for (unsigned int n = 0; n < NUM(offsets); n++) {
rv = sb_set(sb, boundary + offsets[n]);
CU_ASSERT_EQUAL_FATAL(rv, 0);
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
}
rv = sb_clear(sb, boundary + offset_clear);
CU_ASSERT_EQUAL_FATAL(rv, 0);
sb_num_t num = sb_nodes_num(sb);
CU_ASSERT_EQUAL(num, 1);
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
sb_delete(sb);
}
// Performs a sb_clearnum(), within a set of acjacent nodes, such
// that the sb_clearnum() is performed where:
// + Start of sb_clearnum() range is in gap just before node with
// mask that will be cleared.
// + End of mask to be cleared is beyond highest set bit within the
// mask, but also still within that mask (e.g. before set_after
// bits of the node).
// + At least one bit described by the set_after value of the node
// whoses mask will be cleared.
void test_adjacent_clear_across_mask(void)
{
int rv;
sb_pdynstr_t err_string;
sb_num_t expected_nodes_num, actual_nodes_num;
size_t groups_num = 8;
sb_idx_t groups_idx_start = 0x1a75000;
sb_num_t groups_idx_stride = sb_mask_bits_min();
// Index of where to perform sb_clear(), within the chain of
// adjacent nodes. Plus offset, from where sb_clear() was performed,
// and length for a sb_clearnum() operations.
size_t idx_clear = groups_idx_start + 3 * groups_idx_stride;
ssize_t clearnum_offset = -1;
sb_num_t clearnum_length = 0x42;
sb_t *sb = sb_create();
CU_ASSERT_PTR_NOT_EQUAL_FATAL(sb, NULL);
for (unsigned int n = 0; n < groups_num; n++) {
sb_idx_t idx = groups_idx_start + n * groups_idx_stride;
rv = sb_set(sb, idx);
CU_ASSERT_EQUAL_FATAL(rv, 0);
err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed001: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
}
expected_nodes_num = groups_num / 2 + (groups_num % 2);
actual_nodes_num = sb_nodes_num(sb);
if (actual_nodes_num != expected_nodes_num) {
fprintf(stderr, "Unexpected number of nodes001:\n"
" actual: %#" SB_PRI_IDX " expected: %#" SB_PRI_IDX "\n",
actual_nodes_num, expected_nodes_num);
fputs(sb_dump(sb), stderr);
CU_FAIL("Unexpected number of nodes001");
}
rv = sb_clear(sb, idx_clear);
CU_ASSERT_EQUAL_FATAL(rv, 0);
err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed003: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
// Mask bit cleared within node that also has a set_after bit, so
// number of nodes should not change.
expected_nodes_num += 0;
actual_nodes_num = sb_nodes_num(sb);
if (actual_nodes_num != expected_nodes_num) {
fprintf(stderr, "Unexpected number of nodes002:\n"
" actual: %#" SB_PRI_IDX " expected: %#" SB_PRI_IDX "\n",
actual_nodes_num, expected_nodes_num);
fputs(sb_dump(sb), stderr);
CU_FAIL("Unexpected number of nodes002");
}
rv = sb_clearnum(sb, idx_clear + clearnum_offset, clearnum_length);
CU_ASSERT_EQUAL_FATAL(rv, 0);
err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed002: %s\n", err_string);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
// The sb_clearnum() was done from a gap before a node's mask bits, to
// a bit beyond the bits set within the node's mask, yet still in that
// mask. The node where the mask bits are cleared, also has set_after
// bits, which are not cleared, so number of nodes should not change.
expected_nodes_num += 0;
actual_nodes_num = sb_nodes_num(sb);
if (actual_nodes_num != expected_nodes_num) {
fprintf(stderr, "Unexpected number of nodes003:\n"
" actual: %#" SB_PRI_IDX " expected: %#" SB_PRI_IDX "\n",
actual_nodes_num, expected_nodes_num);
fputs(sb_dump(sb), stderr);
CU_FAIL("Unexpected number of nodes003");
}
sb_delete(sb);
}
void test_combinations4(void)
{
struct range {
sb_idx_t idx;
sb_num_t num;
};
struct range ranges[] = {
{0x1000, 1},
{0x1001, 1},
{0x1002, 60},
{0x103e, 1},
{0x103f, 1},
{0x1040, 1},
{0x1041, 1},
{0x1042, 60},
{0x107e, 1},
{0x107f, 1},
{0x1080, 1},
{0x1081, 1},
{0x1082, 60},
{0x10be, 1},
{0x10bf, 1},
};
sb_idx_t range_min, range_max;
for (unsigned int n = 0; n < NUM(ranges); n++) {
if ((n == 0) || (ranges[n].idx < range_min)) {
range_min = ranges[n].idx;
}
if ((n == 0) || ((ranges[n].idx + ranges[n].num - 1) > range_max)) {
range_max = ranges[n].idx + ranges[n].num - 1;
}
}
bool *expected = malloc(sizeof(bool) * ((range_max - range_min) + 1));
struct op {
bool do_set;
unsigned int range_idx;
} operations[4];
MEMCLEAR(operations, sizeof(operations));
do {
MEMCLEAR(expected, sizeof(bool) * ((range_max - range_min) + 1));
sb_t *sb = sb_create();
// Perform Operations
for (unsigned int n1 = 0; n1 < NUM(operations); n1++) {
struct range *prange = &ranges[operations[n1].range_idx];
if (operations[n1].do_set) {
sb_setnum(sb, prange->idx, prange->num);
for (unsigned int n2 = 0; n2 < prange->num; n2++) {
expected[prange->idx - range_min + n2] = true;
}
} else {
sb_clearnum(sb, prange->idx, prange->num);
for (unsigned int n2 = 0; n2 < prange->num; n2++) {
expected[prange->idx - range_min + n2] = false;
}
}
sb_pdynstr_t err_string = sb_validate(sb);
if (err_string) {
fprintf(stderr, "Sparsebit Validate Failed: %s\n", err_string);
fputs("Operations:\n", stderr);
for (unsigned int op_idx = 0; op_idx < NUM(operations); op_idx++) {
fprintf(stderr, " %u %s idx: %#" SB_PRI_IDX
" num: %#" SB_PRI_NUM "\n",
op_idx, operations[op_idx].do_set ? "SET_NUM" : "CLEAR_NUM",
ranges[operations[op_idx].range_idx].idx,
ranges[operations[op_idx].range_idx].num);
}
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Sparsebit - Inconsistent Internal State");
sb_dynstr_free(err_string);
}
}
// Validate setting of each bit, along with nextset, nextcleared,
// prevset, and prevcleared for each bit in the ranges.
for (unsigned int n1 = 0; n1 < (range_max - range_min + 1); n1++) {
sb_idx_t idx = range_min + n1;
bool expected_isset = expected[n1];
sb_idx_t expected_nextset = 0;
int n2;
for (n2 = (idx - range_min) + 1; n2 < (range_max - range_min + 1); n2++) {
if (expected[n2]) {
expected_nextset = range_min + n2;
break;
}
}
sb_idx_t expected_nextcleared = 0;
for (n2 = (idx - range_min) + 1; n2 < (range_max - range_min + 1); n2++) {
if (!expected[n2]) {
expected_nextcleared = range_min + n2;
break;
}
}
if (n2 == (range_max - range_min + 1)) {
expected_nextcleared = range_max + 1;
}
sb_idx_t expected_prevset = 0;
for (n2 = (idx - range_min) - 1; n2 >= 0; n2--) {
if (expected[n2]) {
expected_prevset = range_min + n2;
break;
}
}
sb_idx_t expected_prevcleared = (range_min == 0) ? 0 : range_min - 1;
for (n2 = (idx - range_min) - 1; n2 >= 0; n2--) {
if (!expected[n2]) {
expected_prevcleared = range_min + n2;
break;
}
}
bool actual_isset = sb_isset(sb, idx);
if (actual_isset != expected_isset) {
fputs("Error - Unexpected bit setting\n", stderr);
fputs("Operations:\n", stderr);
for (unsigned int op_idx = 0; op_idx < NUM(operations); op_idx++) {
fprintf(stderr, " %u %s idx: %#" SB_PRI_IDX
" num: %#" SB_PRI_NUM "\n",
op_idx, operations[op_idx].do_set ? "SET_NUM" : "CLEAR_NUM",
ranges[operations[op_idx].range_idx].idx,
ranges[operations[op_idx].range_idx].num);
}
fprintf(stderr, "idx: %#" SB_PRI_IDX
" actual_isset: %u expected_isset: %u\n",
idx, actual_isset, expected_isset);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Unexpected Bit Setting");
}
sb_idx_t actual_nextset = sb_nextset(sb, idx);
if (actual_nextset != expected_nextset) {
fputs("Error - Unexpected next set\n", stderr);
fputs("Operations:\n", stderr);
for (unsigned int op_idx = 0; op_idx < NUM(operations); op_idx++) {
fprintf(stderr, " %u %s idx: %#" SB_PRI_IDX
" num: %#" SB_PRI_NUM "\n",
op_idx, operations[op_idx].do_set ? "SET_NUM" : "CLEAR_NUM",
ranges[operations[op_idx].range_idx].idx,
ranges[operations[op_idx].range_idx].num);
}
fprintf(stderr,
"idx: %#" SB_PRI_IDX " actual_nextset: %#" SB_PRI_IDX
" expected_nextset: %#" SB_PRI_IDX "\n",
idx, actual_nextset, expected_nextset);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Unexpected Next Set Index");
}
sb_idx_t actual_nextcleared = sb_nextcleared(sb, idx);
if (actual_nextcleared != expected_nextcleared) {
fputs("Error - Unexpected next cleared\n", stderr);
fputs("Operations:\n", stderr);
for (unsigned int op_idx = 0; op_idx < NUM(operations); op_idx++) {
fprintf(stderr, " %u %s idx: %#" SB_PRI_IDX
" num: %#" SB_PRI_NUM "\n",
op_idx, operations[op_idx].do_set ? "SET_NUM" : "CLEAR_NUM",
ranges[operations[op_idx].range_idx].idx,
ranges[operations[op_idx].range_idx].num);
}
fprintf(stderr,
"idx: %#" SB_PRI_IDX " actual_nextcleared: %#" SB_PRI_IDX
" expected_nextcleared: %#" SB_PRI_IDX "\n",
idx, actual_nextcleared, expected_nextcleared);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Unexpected Next Cleared Index");
}
sb_idx_t actual_prevset = sb_prevset(sb, idx);
if (actual_prevset != expected_prevset) {
fputs("Error - Unexpected previous set\n", stderr);
fputs("Operations:\n", stderr);
for (unsigned int op_idx = 0; op_idx < NUM(operations); op_idx++) {
fprintf(stderr, " %u %s idx: %#" SB_PRI_IDX
" num: %#" SB_PRI_NUM "\n",
op_idx, operations[op_idx].do_set ? "SET_NUM" : "CLEAR_NUM",
ranges[operations[op_idx].range_idx].idx,
ranges[operations[op_idx].range_idx].num);
}
fprintf(stderr,
"idx: %#" SB_PRI_IDX " actual_prevset: %#" SB_PRI_IDX
" expected_prevset: %#" SB_PRI_IDX "\n",
idx, actual_prevset, expected_prevset);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Unexpected Previous Set Index");
}
sb_idx_t actual_prevcleared = sb_prevcleared(sb, idx);
if (actual_prevcleared != expected_prevcleared) {
fputs("Error - Unexpected previous cleared\n", stderr);
fputs("Operations:\n", stderr);
for (unsigned int op_idx = 0; op_idx < NUM(operations); op_idx++) {
fprintf(stderr, " %u %s idx: %#" SB_PRI_IDX
" num: %#" SB_PRI_NUM "\n",
op_idx, operations[op_idx].do_set ? "SET_NUM" : "CLEAR_NUM",
ranges[operations[op_idx].range_idx].idx,
ranges[operations[op_idx].range_idx].num);
}
fprintf(stderr,
"idx: %#" SB_PRI_IDX " actual_prevcleared: %#" SB_PRI_IDX
" expected_prevcleared: %#" SB_PRI_IDX "\n",
idx, actual_prevcleared, expected_prevcleared);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Unexpected Previous Cleared Index");
}
}
// Validate value returned from sb_numset().
sb_num_t expected_numset = 0;
for (bool *p = expected; p < (expected + (range_max - range_min) + 1);
p++) {
if (*p) { expected_numset++; }
}
sb_num_t actual_numset = sb_numset(sb);
if (actual_numset != expected_numset) {
fputs("Error - Unexpected num set\n", stderr);
fputs("Operations:\n", stderr);
for (unsigned int op_idx = 0; op_idx < NUM(operations); op_idx++) {
fprintf(stderr, " %u %s idx: %#" SB_PRI_IDX
" num: %#" SB_PRI_NUM "\n",
op_idx, operations[op_idx].do_set ? "SET_NUM" : "CLEAR_NUM",
ranges[operations[op_idx].range_idx].idx,
ranges[operations[op_idx].range_idx].num);
}
fprintf(stderr,
" actual_numset: %#" SB_PRI_NUM
" expected_numset: %#" SB_PRI_NUM "\n",
actual_numset, expected_numset);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Unexpected Num Set");
}
// Validate index returned for each sb_nthset().
for (sb_num_t nth_idx = 0; nth_idx < expected_numset; nth_idx++) {
sb_num_t num_set = 0;
sb_idx_t expected_rv;
for (expected_rv = range_min; expected_rv <= range_max;
expected_rv++) {
if (expected[expected_rv - range_min]) {
num_set++;
}
if ((nth_idx + 1) == num_set) { break; }
}
sb_idx_t actual_rv = sb_nthset(sb, nth_idx);
if (actual_rv != expected_rv) {
fputs("Error - Unexpected Nth set return value\n", stderr);
fputs("Operations:\n", stderr);
for (unsigned int op_idx = 0; op_idx < NUM(operations); op_idx++) {
fprintf(stderr, " %u %s idx: %#" SB_PRI_IDX
" num: %#" SB_PRI_NUM "\n",
op_idx, operations[op_idx].do_set ? "SET_NUM" : "CLEAR_NUM",
ranges[operations[op_idx].range_idx].idx,
ranges[operations[op_idx].range_idx].num);
}
fprintf(stderr,
" nth_idx: %#" SB_PRI_NUM
" actual_rv: %#" SB_PRI_NUM
" expected_rv: %#" SB_PRI_NUM "\n",
nth_idx, actual_rv, expected_rv);
fputs(sb_dump(sb), stderr);
CU_FAIL_FATAL("Unexpected Nth Set Return Value");
}
}
sb_delete(sb);
// Increment to next combination of operations.
unsigned int n;
for (n = 0; n < NUM(operations); n++) {
operations[n].range_idx++;
if (operations[n].range_idx >= NUM(ranges)) {
operations[n].range_idx = 0;
if (operations[n].do_set == false) {
operations[n].do_set = true;
} else {
operations[n].do_set = false;
break;
}
} else {
break;
}
}
if (n == NUM(operations)) {
break;
}
} while (true);
}
int main(void)
{
bool any_failed;
CU_ErrorCode cu_error_code;
CU_pSuite pSuite = NULL;
/* Initialize CUnit Test Registry */
if (CUE_SUCCESS != CU_initialize_registry()) {
return CU_get_error();
}
/* Add Test Suite */
pSuite = CU_add_suite("Suite_1", NULL, NULL);
if (pSuite == NULL) {
CU_cleanup_registry();
return CU_get_error();
}
/* Add Tests */
// TODO: Optionally use positional command-line arguments, that are
// regular expressions, to specify which tests are to be added.
if ((CU_add_test(pSuite, "create_delete", test_create_delete) == NULL)
|| (CU_add_test(pSuite, "set", test_set) == NULL)
|| (CU_add_test(pSuite, "clear", test_clear) == NULL)
|| (CU_add_test(pSuite, "multinode", test_multinode) == NULL)
|| (CU_add_test(pSuite, "clear_two_nodes", test_clear_two_nodes) == NULL)
|| (CU_add_test(pSuite, "first_next_set", test_first_next_set) == NULL)
|| (CU_add_test(pSuite, "first_next_cleared", test_first_next_cleared)
== NULL)
|| (CU_add_test(pSuite, "prev_set", test_prev_set) == NULL)
|| (CU_add_test(pSuite, "prev_cleared", test_prev_cleared) == NULL)
|| (CU_add_test(pSuite, "nthset", test_nthset) == NULL)
|| (CU_add_test(pSuite, "nthset_with_noneset", test_nthset_with_noneset)
== NULL)
|| (CU_add_test(pSuite, "nthset_with_allset", test_nthset_with_allset)
== NULL)
|| (CU_add_test(pSuite, "permutations6", test_permutations6) == NULL)
|| (CU_add_test(pSuite, "set_after_single", test_set_after_single) == NULL)
|| (CU_add_test(pSuite, "set_after_clear_single",
test_set_after_clear_single) == NULL)
|| (CU_add_test(pSuite, "set_after_then_clear_mask",
test_set_after_then_clear_mask) == NULL)
|| (CU_add_test(pSuite, "adjacent_clear_across_mask",
test_adjacent_clear_across_mask) == NULL)
|| (CU_add_test(pSuite, "combinations4", test_combinations4) == NULL)
) {
CU_cleanup_registry();
return CU_get_error();
}
/* Run tests - Basic Mode */
CU_basic_set_mode(CU_BRM_VERBOSE);
CU_basic_run_tests();
any_failed = (CU_get_number_of_tests_failed()) ? true : false;
CU_cleanup_registry();
cu_error_code = CU_get_error();
if (cu_error_code) {
return cu_error_code;
}
return (any_failed) ? 1 : 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment