greg/sparsemap
1
0
Fork 0
Code Issues Pull requests 1 Projects Releases Packages Wiki Activity

Compare commits

base: greg:gburd/add-rle-1s
Branches Tags
greg:main
greg:gburd/add-rle-1s
greg:gburd/thread-safe
greg:gburd/resize-when-necessary
greg:gburd/tests
greg:gburd/find-span
..
compare: greg:main
Branches Tags
greg:gburd/add-rle-1s
greg:main
greg:gburd/thread-safe
greg:gburd/resize-when-necessary
greg:gburd/tests
greg:gburd/find-span

No commits in common. "gburd/add-rle-1s" and "main" have entirely different histories.
gburd/add- ... main

31 changed files with 2246 additions and 5053 deletions
Show stats Expand all files Collapse all files

32
.editorconfig
View file

@ -1,32 +0,0 @@
# Editor configuration, see http://editorconfig.org
root = true
[*]
end_of_line = lf
insert_final_newline = true
trim_trailing_whitespace = true
charset = utf-8
indent_style = space
indent_size = 2
# Ignore diffs/patches
[*.{diff,patch}]
end_of_line = unset
insert_final_newline = unset
trim_trailing_whitespace = unset
indent_size = unset
[{.*,secrets}/**]
end_of_line = unset
insert_final_newline = unset
trim_trailing_whitespace = unset
charset = unset
indent_style = unset
indent_size = unset
[*.py]
indent_size = 4
[*.md]
max_line_length = off
trim_trailing_whitespace = false

3
.idea/codeStyles/Project.xml
View file

@ -3,8 +3,5 @@
<clangFormatSettings>
<option name="ENABLED" value="true" />
</clangFormatSettings>
<editorconfig>
<option name="ENABLED" value="false" />
</editorconfig>
</code_scheme>
</component>

15
.idea/customTargets.xml Normal file
View file

@ -0,0 +1,15 @@
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
<component name="CLionExternalBuildManager">
<target id="db0ccaeb-4851-470b-83d0-afa663f6ceb9" name="tests/soak" defaultType="MAKE">
<configuration id="98973a90-a9d0-431b-9071-9ce6960b0b01" name="tests/soak">
<build type="MAKE">
<make targetName="tests/soak" />
</build>
<clean type="MAKE">
<make targetName="clean" />
</clean>
</configuration>
</target>
</component>
</project>

25
.idea/makefile.xml Normal file
View file

@ -0,0 +1,25 @@
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
<component name="MakefileBuildTargetsManager">
<user-build-targets>
<build-target name="tests/soak">
<build-configurations>
<build-configuration>
<make-targets>
<make-target>tests/soak</make-target>
</make-targets>
</build-configuration>
</build-configurations>
</build-target>
<build-target name="clean">
<build-configurations>
<build-configuration>
<make-targets>
<make-target>clean</make-target>
</make-targets>
</build-configuration>
</build-configurations>
</build-target>
</user-build-targets>
</component>
</project>

26
.idea/misc.xml
View file

@ -4,8 +4,28 @@
<option name="executionMode" value="BINARY" />
<option name="pathToExecutable" value="$USER_HOME$/.nix-profile/bin/black" />
</component>
<component name="CMakePythonSetting">
<option name="pythonIntegrationState" value="YES" />
<component name="CidrRootsConfiguration">
<sourceRoots>
<file path="$PROJECT_DIR$/examples" />
<file path="$PROJECT_DIR$/include" />
<file path="$PROJECT_DIR$/lib" />
<file path="$PROJECT_DIR$/src" />
<file path="$PROJECT_DIR$/tests" />
</sourceRoots>
</component>
<component name="CMakeWorkspace" PROJECT_DIR="$PROJECT_DIR$" />
<component name="ExternalStorageConfigurationManager" enabled="true" />
<component name="MakefileSettings">
<option name="linkedExternalProjectsSettings">
<MakefileProjectSettings>
<option name="externalProjectPath" value="$PROJECT_DIR$" />
<option name="modules">
<set>
<option value="$PROJECT_DIR$" />
</set>
</option>
<option name="version" value="2" />
</MakefileProjectSettings>
</option>
</component>
<component name="MakefileWorkspace" PROJECT_DIR="$PROJECT_DIR$" />
</project>

26
CMakeLists.txt
View file

@ -11,12 +11,13 @@ set(CMAKE_C_STANDARD_REQUIRED ON)
set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
set(CMAKE_C_OUTPUT_EXTENSION .o)
set(SOURCE_DIR .)
set(HEADER_DIR . test)
# Set source and header file locations
set(SOURCE_DIR src)
set(HEADER_DIR include)
set(COMMON_CMAKE_C_FLAGS "-std=c11 -Wall -Wextra -Wpedantic")
set(CMAKE_C_FLAGS_DEBUG "-DSPARSEMAP_DIAGNOSTIC -DSPARSEMAP_TESTING -DDEBUG -g -O0")
set(CMAKE_C_FLAGS_PROFILE "-DSPARSEMAP_DIAGNOSTIC -DSPARSEMAP_TESTING -DDEBUG -g -Og -fsanitize=address,leak,object-size,pointer-compare,pointer-subtract,null,return,bounds,pointer-overflow,undefined -fsanitize-address-use-after-scope")
set(COMMON_CMAKE_C_FLAGS "-Wall -Wextra -Wpedantic")
set(CMAKE_C_FLAGS_DEBUG "-DSPARSEMAP_DIAGNOSTIC -DDEBUG -g -O0")
set(CMAKE_C_FLAGS_PROFILE "-DSPARSEMAP_DIAGNOSTIC -DDEBUG -g -Og -fsanitize=address,leak,object-size,pointer-compare,pointer-subtract,null,return,bounds,pointer-overflow,undefined -fsanitize-address-use-after-scope")
set(CMAKE_C_FLAGS_RELEASE "-Ofast")
# Include all header files from the header directory
@ -49,45 +50,44 @@ set_target_properties(sparsemap PROPERTIES
target_include_directories(sparsemap PRIVATE ${HEADER_DIR})
# Add ex_1 program
add_executable(ex_1 test/ex_1.c test/munit.c test/qc.c test/common.c)
add_executable(ex_1 examples/ex_1.c tests/munit.c lib/common.c)
target_link_libraries(ex_1 PRIVATE sparsemap)
target_include_directories(ex_1 PRIVATE ${HEADER_DIR})
add_custom_target(run_ex_1 COMMAND ex_1 WORKING_DIRECTORY ${CMAKE_BINARY_DIR})
# Add ex_2 program
add_executable(ex_2 test/ex_2.c test/munit.c test/qc.c test/common.c)
add_executable(ex_2 examples/ex_2.c tests/munit.c lib/common.c)
target_link_libraries(ex_2 PRIVATE sparsemap)
target_include_directories(ex_2 PRIVATE ${HEADER_DIR})
add_custom_target(run_ex_2 COMMAND ex_2 WORKING_DIRECTORY ${CMAKE_BINARY_DIR})
# Add ex_3 program
add_executable(ex_3 test/ex_3.c test/munit.c test/qc.c test/common.c)
add_executable(ex_3 examples/ex_3.c tests/munit.c lib/common.c)
target_link_libraries(ex_3 PRIVATE sparsemap)
target_include_directories(ex_3 PRIVATE ${HEADER_DIR})
add_custom_target(run_ex_3 COMMAND ex_3 WORKING_DIRECTORY ${CMAKE_BINARY_DIR})
# Add ex_4 program
add_executable(ex_4 test/ex_4.c test/munit.c test/qc.c test/common.c)
add_executable(ex_4 examples/ex_4.c tests/munit.c lib/common.c)
target_link_libraries(ex_4 PRIVATE sparsemap)
target_include_directories(ex_4 PRIVATE ${HEADER_DIR})
add_custom_target(run_ex_4 COMMAND ex_4 WORKING_DIRECTORY ${CMAKE_BINARY_DIR})
# Add test program
add_executable(test test/test.c test/munit.c test/qc.c test/common.c)
add_executable(test tests/test.c tests/munit.c lib/common.c)
target_link_libraries(test PRIVATE sparsemap)
target_include_directories(test PRIVATE ${HEADER_DIR})
set_source_files_properties(test/test.c PROPERTIES COMPILE_FLAGS "-DDEBUG -DSPARSEMAP_DIAGNOSTIC -DSPARSEMAP_TESTING" )
add_custom_target(run_test COMMAND test WORKING_DIRECTORY ${CMAKE_BINARY_DIR})
# Add soak program
add_executable(soak test/soak.c test/common.c test/tdigest.c test/qc.c test/roaring.c)
add_executable(soak tests/soak.c lib/common.c lib/tdigest.c lib/roaring.c)
target_link_libraries(soak PRIVATE sparsemap)
target_include_directories(soak PRIVATE ${HEADER_DIR} lib)
target_link_libraries(soak PUBLIC m)
add_custom_target(run_soak COMMAND soak WORKING_DIRECTORY ${CMAKE_BINARY_DIR})
# Add fuzzer program
# add_executable(fuzzer EXCLUDE_FROM_ALL tests/fuzzer.c)
# add_executable(fuzzer tests/fuzzer.c)
# target_link_libraries(fuzzer PRIVATE sparsemap)
# target_include_directories(fuzzer PRIVATE ${HEADER_DIR} lib)
# target_link_libraries(fuzzer PUBLIC m)

106
Makefile Normal file
View file

@ -0,0 +1,106 @@
OBJS = sparsemap.o
STATIC_LIB = libsparsemap.a
SHARED_LIB = libsparsemap.so
LIBS = -lm
#CFLAGS = -Wall -Wextra -Wpedantic -Of -std=c11 -Iinclude/ -fPIC
#CFLAGS = -Wall -Wextra -Wpedantic -Og -g -std=c11 -Iinclude/ -fPIC
#CFLAGS = -DSPARSEMAP_DIAGNOSTIC -DDEBUG -Wall -Wextra -Wpedantic -O0 -g -std=c11 -Iinclude/ -fPIC
CFLAGS = -DSPARSEMAP_DIAGNOSTIC -DDEBUG -Wall -Wextra -Ofast -g -std=c11 -Iinclude/ -fPIC
#CFLAGS = -Wall -Wextra -Wpedantic -Og -g -std=c11 -Iinclude/ -fPIC
#CFLAGS = -Wall -Wextra -Wpedantic -Ofast -g -std=c11 -Iinclude/ -fPIC
#CFLAGS = -DSPARSEMAP_DIAGNOSTIC -DDEBUG -Wall -Wextra -Wpedantic -Og -g -fsanitize=address,leak,object-size,pointer-compare,pointer-subtract,null,return,bounds,pointer-overflow,undefined -fsanitize-address-use-after-scope -std=c11 -Iinclude/ -fPIC
#CFLAGS = -Wall -Wextra -Wpedantic -Og -g -fsanitize=all -fhardened -std=c11 -Iinclude/ -fPIC
#TEST_FLAGS = -DDEBUG -Wall -Wextra -Wpedantic -O0 -g -std=c11 -Iinclude/ -Itests/ -fPIC
TEST_FLAGS = -Wall -Wextra -Wpedantic -Ofast -g -std=c11 -Iinclude/ -Itests/ -fPIC
#TEST_FLAGS = -Wall -Wextra -Wpedantic -Og -g -std=c11 -Iinclude/ -Itests/ -fPIC
#TEST_FLAGS = -DDEBUG -Wall -Wextra -Wpedantic -Og -g -fsanitize=address,leak,object-size,pointer-compare,pointer-subtract,null,return,bounds,pointer-overflow,undefined -fsanitize-address-use-after-scope -std=c11 -Iinclude/ -fPIC
TESTS = tests/test tests/soak
TEST_OBJS = tests/test.o lib/munit.o lib/tdigest.o lib/common.o
LIB_OBJS = lib/munit.o lib/tdigest.o lib/common.o lib/roaring.o
EXAMPLES = examples/ex_1 examples/ex_2 examples/ex_3 examples/ex_4
.PHONY: all shared static clean test examples mls
all: static shared
static: $(STATIC_LIB)
shared: $(SHARED_LIB)
$(STATIC_LIB): $(OBJS)
ar rcs $(STATIC_LIB) $?
$(SHARED_LIB): $(OBJS)
$(CC) $(CFLAGS) -o $@ $? -shared
examples: $(STATIC_LIB) $(EXAMPLES) $(TEST_OBJS)
mls: examples/mls
tests: $(TESTS)
test: tests
env ASAN_OPTIONS=detect_leaks=1 LSAN_OPTIONS=verbosity=1:log_threads=1 ./tests/test
soak: tests
env ASAN_OPTIONS=detect_leaks=1 LSAN_OPTIONS=verbosity=1:log_threads=1 ./tests/soak
fuzzer: tests
env ASAN_OPTIONS=detect_leaks=1 LSAN_OPTIONS=verbosity=1:log_threads=1 ./tests/fuzzer ./crash.case
tests/test: $(TEST_OBJS) $(LIB_OBJS) $(STATIC_LIB)
$(CC) $^ $(LIBS) -o $@ $(TEST_FLAGS)
clean:
rm -f $(OBJS)
rm -f examples/main.c
rm -f $(STATIC_LIB) $(SHARED_LIB)
rm -f $(TESTS) tests/*.o
rm -f $(EXAMPLES) examples/*.o
format:
clang-format -i src/sparsemap.c include/sparsemap.h examples/ex_*.c tests/soak.c tests/test.c tests/midl.c lib/common.c include/common.h
# clang-format -i include/*.h src/*.c tests/*.c tests/*.h examples/*.c
%.o: src/%.c
$(CC) $(CFLAGS) -c -o $@ $^
lib/%.o: tests/%.c
$(CC) $(CFLAGS) -c -o $@ $^
tests/%.o: tests/%.c
$(CC) $(CFLAGS) -c -o $@ $^
examples/%.o: examples/%.c
$(CC) $(CFLAGS) -c -o $@ $^
examples/ex_1: $(LIB_OBJS) examples/ex_1.o $(STATIC_LIB)
$(CC) $^ $(LIBS) -o $@ $(TEST_FLAGS)
examples/ex_2: $(LIB_OBJS) examples/ex_2.o $(STATIC_LIB)
$(CC) $^ $(LIBS) -o $@ $(TEST_FLAGS)
examples/ex_3: $(LIB_OBJS) examples/ex_3.o $(STATIC_LIB)
$(CC) $^ $(LIBS) -o $@ $(TEST_FLAGS)
examples/ex_4: $(LIB_OBJS) examples/ex_4.o $(STATIC_LIB)
$(CC) $^ $(LIBS) -o $@ $(TEST_FLAGS)
tests/soak: $(LIB_OBJS) tests/soak.o $(STATIC_LIB)
$(CC) $^ $(LIBS) -o $@ $(TEST_FLAGS)
tests/fuzzer: $(LIB_OBJS) tests/fuzzer.o $(STATIC_LIB)
$(CC) $^ $(LIBS) -o $@ $(TEST_FLAGS) -DFUZZ_DEBUG
todo:
rg -i 'todo|gsb|abort'
# cp src/sparsemap.c /tmp && clang-tidy src/sparsemap.c -fix -fix-errors -checks="readability-braces-around-statements" -- -DDEBUG -DSPARSEMAP_DIAGNOSTIC -DSPARSEMAP_ASSERT -Wall -Wextra -Wpedantic -Og -g -std=c11 -Iinclude/ -fPIC
# clear; make clean examples test && env ASAN_OPTIONS=detect_leaks=1 LSAN_OPTIONS=verbosity=1:log_threads=1 ./tests/test
# clear; make clean examples test && env ASAN_OPTIONS=detect_leaks=1 LSAN_OPTIONS=verbosity=1:log_threads=1 ./examples/soak

111
README.md
View file

@ -5,106 +5,47 @@ Unfortunately, they can use too much memory. To compensate, we often use
compressed bitmaps.
`sparsemap` is a sparse, compressed bitmap. In the best case, it can store 2048
bits in just 8 bytes. In the worst case, it stores the 2048 bits uncompressed
and requires an additional 8 bytes of overhead.
bits in just 8 bytes. In the worst case, it stores the 2048 bits uncompressed and
requires an additional 8 bytes of overhead.
The "best" case happens when large consecutive sequences of the bits are
either set ("1") or not set ("0"). If your numbers are consecutive 64 bit
either set ("1") or not set ("0"). If your numbers are consecutive 64bit
integers then sparsemap can compress up to 16kb in just 8 bytes.
## How does it work? TODO... refine...
## How does it work?
On the lowest level a bitmap contains a number of chunks. Each chunk has a
starting offset (`uint32_t`), a descriptor (the first `sm_bitvec_t`), and may
require a variable amount of additional space for encoding some bit patterns.
On the lowest level stores bits in sm_bitvec_t's (a uint32_t or uint64_t).
So, if the user sets bit 0 and bit 10000, and the chunk capacity is 2048,
the sparsemap creates two vectors; the first starts at offset 0, the second
starts at offset 8192. Offsets must align with the capacity of a vector.
Each sm_bitvec_t has an additional descriptor (2 bits). A single word prepended
to each sm_bitvec_t describes its condition. The descriptor word and the
sm_bitvec_t's have the same size. The descriptor of a sm_bitvec_t
specifies whether the sm_bitvec_t consists only of set bits ("1"), unset
bits ("0") or has a mixed payload. In the first and second cases, the
sm_bitvec_t is not stored.
Every 2 bit pair within the descriptor (the first vector size portion of the
chunk after the 4 bytes for the offset) indicates the encoded bit pattern at
that location's relative offset. This can be only set bits ("1"), only unset
bits ("0"), a mixed payload, or a run-length encoded extent of set bits
("1s"). A mixed vector consumes an additional `sm_bitvec_t`'s worth of space in
the buffer used to encode the bit pattern within that range.
Our examples below ignore the 4 byte overhead for the starting offset of these
chunks because they focus on the compressed encoding. Also, for brevity, we use
16 bit wide vectors (`sm_bitvec_t`), rather than 64 bits.
The first example, shows a sequence of 4 x 16 bits:
An example shows a sequence of 4 x 16 bits (here, each sm_bitvec_t and the
Descriptor word has 16 bits):
Descriptor:
00 00 00 00 11 00 11 10
^^ ^^ ^^ ^^-- sm_bitvec_t [0..3] are "0000000000000000"
^^-- sm_bitvec_t 4 is "1111111111111111"
^^-- sm_bitvec_t 5 is "0000000000000000"
^^-- sm_bitvec_t 6 is "1111111111111111"
^^-- sm_bitvec_t 7 is "0110010101111001"
^^ ^^ ^^ ^^-- sm_bitvec_t #0 - #3 are "0000000000000000"
^^-- sm_bitvec_t #4 is "1111111111111111"
^^-- sm_bitvec_t #5 is "0000000000000000"
^^-- sm_bitvec_t #6 is "1111111111111111"
^^-- sm_bitvec_t #7 is "0110010101111001"
Since the first 7 (0 through 6) `sm_bitvec_t`'s are either all "1" or "0" and
their encoding reqiures no additional storage in the buffer, so the actual
memory sequence for this chunk within the buffer looks like this:
Since the first 7 sm_bitvec_t's are either all "1" or "0" they are not stored.
The actual memory sequence looks like this:
0000000011001110 0110010101111001
Instead of storing 16 bytes, we only store 2 bytes: one for the descriptor, and
one for the last `sm_bitvec_t` #7.
Instead of storing 8 Words (16 bytes), we only store 2 Words (2 bytes): one
for the descriptor, and one for the last sm_bitvec_t #7.
A 2nd example shows a chunk with reduced capacity.
Descriptor:
00 00 00 00 11 01 01 01
^^ ^^ ^^ ^^-- sm_bitvec_t [0..3] are "0000000000000000"
^^-- sm_bitvec_t 4 is "1111111111111111"
^^ ^^ ^^-- sm_bitvec_t [5..8] represent nothing
The memory sequence for this second, truncated chunk, looks like this:
0000000011010101
The bit pattern "01" can exist at the end of a chunk to indicate a reduced chunk
capacity. In this case the chunk's last 3 descriptors indicate that it can
encode up to 5 * 16 or 80 bit positions rather than the normal 128 (when using
16 bit wide vectors, `sm_bitvec_t`). When a chunk's capacity is entirely
truncated, it is empty and removed from the sparsemap entirely.
A 3rd example shows a single vector representing a long run of adjacent 1s
greater than the vector width (16 bits). Let's examine the representation:
Descriptor:
01 00 00 00 10 01 00 00
^^-- sm_bitvec_t #0 is '01' indicating a run-length encoding of 1s
^^ ^^ ^^ ^^ ^^ ^^ ^^-- the lenght of the run, 144
When (if, and only if) the first 2 bits of the descriptor are '01' they indicate
that this is an run-length encoded (RLE) vector. The number of 1s is the
remaining portion of the descriptor -- in this case 14 of the 16 bits -- encode
the run length. Simply mask the first two bits and interpret the remaining as an
`size_t`.
With that in mind, the memory sequence for this third example looks like this:
01 00 00 00 10 00 01 00
Which decodes to a run of 144 adjacent 1s:
1111 ... <then another 139 1s followed by the final> ... 1
The run must always be modulo the width of the descriptor (144 % 16 = 0). The
next chunk would encode any additional 1s adjacent to this set of 144 unless
there were 16 more, then this chunk would change to:
Descriptor:
01 00 00 00 10 10 00 00
^^-- sm_bitvec_t #0 is '01' meaning RLE a set of adjacent 1s
^^ ^^ ^^ ^^ ^^ ^^ ^^-- the new length of the run is 160
Using this method of RLE for adjacent 1s we can compress (again, in this case
where bitvec_t is 16 bits wide) 2^14 or 16348 adjacent 1s to the width of a
single descriptor, 2 bytes in this case, rather than the approximately 4096
bytes without RLE.
The sparsemap stores a list of chunk maps, and for each chunk map, it stores the
absolute address (i.e. if the user sets bit 0 and bit 10000, and the chunk map
capacity is 2048, the sparsemap creates two chunk maps; the first starts at
offset 0, the second starts at offset 8192).
## Usage instructions

65
bin/gen_chunk_vector_size_table.py
View file

@ -1,65 +0,0 @@
#!/usr/bin/env python
# Gererate a C function that contains a pre-calculated static table where each
# 8bit offset into that table encodes the required additional space for what is
# described.
# The 2 bit patters are:
# 00 -> 0 additional sm_bitvec_t (ZEROS)
# 11 -> 0 additional sm_bitvec_t (ONES)
# 10 -> 1 additional sm_bitvec_t (MIXED)
# 01 -> 0 additional sm_bitvec_t (NONE)
# The goal is to output this:
# /**
# * Calculates the number of sm_bitvec_ts required by a single byte with flags
# * (in m_data[0]).
# */
# static size_t
# __sm_chunk_calc_vector_size(uint8_t b)
# {
# // clang-format off
# static int lookup[] = {
# 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0,
# 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0,
# 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 3, 2, 1, 1, 2, 1,
# 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0,
# 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0,
# 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0,
# 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 3, 2, 1, 1, 2, 1,
# 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0,
# 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 3, 2, 1, 1, 2, 1,
# 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 3, 2, 1, 1, 2, 1,
# 2, 2, 3, 2, 2, 2, 3, 2, 3, 3, 4, 3, 2, 2, 3, 2,
# 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 3, 2, 1, 1, 2, 1,
# 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0,
# 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0,
# 1, 1, 2, 1, 1, 1, 2, 1, 2, 2, 3, 2, 1, 1, 2, 1,
# 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0
# };
# // clang-format on
# return (size_t)lookup[b];
# }
def create_lookup_table_c_format():
"""Creates a lookup table in C-style format."""
lookup_table = []
for byte in range(256):
count = 0
for i in range(3):
if (byte >> (i * 2)) & 3 == 2:
count += 1
lookup_table.append(count)
# Format the output as a C array
output = "static int lookup[] = {\n"
for i in range(0, 256, 16):
line = " " + ", ".join(str(x) for x in lookup_table[i:i+16]) + ",\n"
output += line
output += "};"
print(output)
if __name__ == "__main__":
create_lookup_table_c_format()

0
bin/cmake-it.sh → cmake-it.sh
View file

32
test/ex_1.c → examples/ex_1.c
View file

@ -4,7 +4,7 @@
#include <stdint.h>
#include <stdio.h>
#include <sparsemap.h>
#include "../include/sparsemap.h"
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wvariadic-macros"
@ -35,16 +35,16 @@ main()
uint8_t buffer2[1024];
sparsemap_init(map, buffer, sizeof(buffer));
assert(sparsemap_get_size(map) == size);
sparsemap_set(map, 0);
sparsemap_set(map, 0, true);
assert(sparsemap_get_size(map) == size + 4 + 8 + 8);
assert(sparsemap_is_set(map, 0) == true);
assert(sparsemap_get_size(map) == size + 4 + 8 + 8);
assert(sparsemap_is_set(map, 1) == false);
sparsemap_unset(map, 0);
sparsemap_set(map, 0, false);
assert(sparsemap_get_size(map) == size);
sparsemap_clear(map);
sparsemap_set(map, 64);
sparsemap_set(map, 64, true);
assert(sparsemap_is_set(map, 64) == true);
assert(sparsemap_get_size(map) == size + 4 + 8 + 8);
@ -54,7 +54,7 @@ main()
// set [0..100000]
for (int i = 0; i < 100000; i++) {
assert(sparsemap_is_set(map, i) == false);
sparsemap_set(map, i);
sparsemap_set(map, i, true);
if (i > 5) {
for (int j = i - 5; j <= i; j++) {
assert(sparsemap_is_set(map, j) == true);
@ -73,7 +73,7 @@ main()
// unset [0..10000]
for (int i = 0; i < 10000; i++) {
assert(sparsemap_is_set(map, i) == true);
sparsemap_unset(map, i);
sparsemap_set(map, i, false);
assert(sparsemap_is_set(map, i) == false);
}
@ -87,7 +87,7 @@ main()
// set [10000..0]
for (int i = 10000; i >= 0; i--) {
assert(sparsemap_is_set(map, i) == false);
sparsemap_set(map, i);
sparsemap_set(map, i, true);
assert(sparsemap_is_set(map, i) == true);
}
@ -106,7 +106,7 @@ main()
// unset [10000..0]
for (int i = 10000; i >= 0; i--) {
assert(sparsemap_is_set(map, i) == true);
sparsemap_unset(map, i);
sparsemap_set(map, i, false);
assert(sparsemap_is_set(map, i) == false);
}
@ -117,13 +117,13 @@ main()
fprintf(stderr, ".");
sparsemap_clear(map);
sparsemap_set(map, 0);
sparsemap_set(map, 2048 * 2 + 1);
sparsemap_set(map, 0, true);
sparsemap_set(map, 2048 * 2 + 1, true);
assert(sparsemap_is_set(map, 0) == true);
assert(sparsemap_is_set(map, 2048 * 2 + 0) == false);
assert(sparsemap_is_set(map, 2048 * 2 + 1) == true);
assert(sparsemap_is_set(map, 2048 * 2 + 2) == false);
sparsemap_set(map, 2048);
sparsemap_set(map, 2048, true);
assert(sparsemap_is_set(map, 0) == true);
assert(sparsemap_is_set(map, 2047) == false);
assert(sparsemap_is_set(map, 2048) == true);
@ -137,7 +137,7 @@ main()
fprintf(stderr, ".");
for (int i = 0; i < 100000; i++) {
sparsemap_set(map, i);
sparsemap_set(map, i, true);
}
for (int i = 0; i < 100000; i++) {
assert(sparsemap_select(map, i, true) == (unsigned)i);
@ -147,7 +147,7 @@ main()
fprintf(stderr, ".");
for (int i = 1; i < 513; i++) {
sparsemap_set(map, i);
sparsemap_set(map, i, true);
}
for (int i = 1; i < 513; i++) {
assert(sparsemap_select(map, i - 1, true) == (unsigned)i);
@ -157,7 +157,7 @@ main()
fprintf(stderr, ".");
for (size_t i = 0; i < 8; i++) {
sparsemap_set(map, i * 10);
sparsemap_set(map, i * 10, true);
}
for (size_t i = 0; i < 8; i++) {
assert(sparsemap_select(map, i, true) == (sparsemap_idx_t)i * 10);
@ -168,7 +168,7 @@ main()
sparsemap_init(sm2, buffer2, sizeof(buffer2));
sparsemap_clear(sm2);
for (int i = 0; i < 2048 * 2; i++) {
sparsemap_set(map, i);
sparsemap_set(map, i, true);
}
sparsemap_split(map, 2048, sm2);
for (int i = 0; i < 2048; i++) {
@ -185,7 +185,7 @@ main()
sparsemap_init(sm2, buffer2, sizeof(buffer2));
sparsemap_clear(map);
for (int i = 0; i < 2048 * 3; i++) {
sparsemap_set(map, i);
sparsemap_set(map, i, true);
assert(sparsemap_is_set(map, i) == true);
}
sparsemap_split(map, 64, sm2);

6
test/ex_2.c → examples/ex_2.c
View file

@ -3,7 +3,7 @@
#include <stdio.h>
#include <stdlib.h>
#include <sparsemap.h>
#include "../include/sparsemap.h"
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wvariadic-macros"
@ -33,13 +33,13 @@ main(void)
// when the map is full.
for (i = 0; i < 7744; i++) {
if (!i % 2) {
sparsemap_set(map, i);
sparsemap_set(map, i, true);
assert(sparsemap_is_set(map, i) == true);
}
}
// On 1024 KiB of buffer with every other bit set the map holds 7744 bits
// and then runs out of space. This next _set() call will fail.
sparsemap_set(map, ++i);
sparsemap_set(map, ++i, true);
assert(sparsemap_is_set(map, i) == true);
return 0;
}

4
test/ex_3.c → examples/ex_3.c
View file

@ -62,11 +62,11 @@ main(void)
// set all the bits on in a random order
for (i = 0; i < 1024; i++) {
__diag("set %d\n", array[i]);
sparsemap_set(map, array[i]);
sparsemap_set(map, array[i], true);
assert(sparsemap_is_set(map, array[i]) == true);
}
sparsemap_set(map, 1025);
sparsemap_set(map, 1025, true);
assert(sparsemap_is_set(map, 1025) == true);
return 0;

4
test/ex_4.c → examples/ex_4.c
View file

@ -35,7 +35,7 @@ main(void)
// set all the bits on in a random order
for (i = 0; i < TEST_ARRAY_SIZE; i++) {
sparsemap_set(map, array[i]);
sparsemap_set(map, array[i], true);
assert(sparsemap_is_set(map, array[i]) == true);
}
@ -55,7 +55,7 @@ main(void)
shuffle(array, TEST_ARRAY_SIZE);
print_spans(array, TEST_ARRAY_SIZE);
for (i = 0; i < TEST_ARRAY_SIZE; i++) {
sparsemap_set(map, array[i]);
sparsemap_set(map, array[i], true);
assert(sparsemap_is_set(map, array[i]) == true);
}
has_span(map, array, TEST_ARRAY_SIZE, (int)len);

2
test/common.h → include/common.h
View file

@ -1,5 +1,5 @@
#include <sparsemap.h>
#include "../include/sparsemap.h"
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wvariadic-macros"

0
popcount.h → include/popcount.h
View file

0
test/roaring.h → include/roaring.h
View file

90
sparsemap.h → include/sparsemap.h
View file

@ -29,31 +29,31 @@
*
* The implementation is separated into tiers.
*
* Tier 0 (lowest): bits are stored in a __sm_bitvec_t (uint64_t).
* Tier 0 (lowest): bits are stored in a sm_bitvec_t (uint64_t).
*
* Tier 1 (middle): multiple __sm_bitvec_t are managed in a chunk map. The chunk
* map only stores those __sm_bitvec_t that have a mixed payload of bits (i.e.
* some bits are 1, some are 0). As soon as ALL bits in a __sm_bitvec_t are
* identical, this __sm_bitvec_t is no longer stored, it is compressed.
* Tier 1 (middle): multiple sm_bitvec_t are managed in a chunk map. The chunk
* map only stores those sm_bitvec_t that have a mixed payload of bits (i.e.
* some bits are 1, some are 0). As soon as ALL bits in a sm_bitvec_t are
* identical, this sm_bitvec_t is no longer stored, it is compressed.
*
* The chunk maps store additional flags (2 bit) for each __sm_bitvec_t in an
* additional word (same size as the __sm_bitvec_t itself).
* The chunk maps store additional flags (2 bit) for each sm_bitvec_t in an
* additional word (same size as the sm_bitvec_t itself).
*
* 00 11 22 33
* ^-- descriptor for __sm_bitvec_t 1
* ^-- descriptor for __sm_bitvec_t 2
* ^-- descriptor for __sm_bitvec_t 3
* ^-- descriptor for __sm_bitvec_t 4
* ^-- descriptor for sm_bitvec_t 1
* ^-- descriptor for sm_bitvec_t 2
* ^-- descriptor for sm_bitvec_t 3
* ^-- descriptor for sm_bitvec_t 4
*
* Those flags (*) can have one of the following values:
*
* 00 The __sm_bitvec_t is all zero -> __sm_bitvec_t is not stored
* 11 The __sm_bitvec_t is all one -> __sm_bitvec_t is not stored
* 10 The __sm_bitvec_t contains a bitmap -> __sm_bitvec_t is stored
* 01 The __sm_bitvec_t is not used (**)
* 00 The sm_bitvec_t is all zero -> sm_bitvec_t is not stored
* 11 The sm_bitvec_t is all one -> sm_bitvec_t is not stored
* 10 The sm_bitvec_t contains a bitmap -> sm_bitvec_t is stored
* 01 The sm_bitvec_t is not used (**)
*
* The serialized size of a chunk map in memory therefore is at least
* one __sm_bitvec_t for the flags, and (optionally) additional __sm_bitvec_ts
* one sm_bitvec_t for the flags, and (optionally) additional sm_bitvec_ts
* if they are required.
*
* (*) The code comments often use the Erlang format for binary
@ -82,7 +82,7 @@ extern "C" {
* The public interface for a sparse bit-mapped index, a "sparse map".
*
* |sm_idx_t| is the user's numerical data type which is mapped to a single bit
* in the bitmap. Usually this is uint32_t or uint64_t. |__sm_bitvec_t| is the
* in the bitmap. Usually this is uint32_t or uint64_t. |sm_bitvec_t| is the
* storage type for a bit vector used by the __sm_chunk_t internal maps.
* Usually this is an uint64_t.
*/
@ -92,6 +92,8 @@ typedef size_t sparsemap_idx_t;
#define SPARSEMAP_IDX_MAX SIZE_MAX
#define SPARSEMAP_FOUND(x) ((x) != SPARSEMAP_IDX_MAX)
#define SPARSEMAP_NOT_FOUND(x) ((x) == SPARSEMAP_IDX_MAX)
typedef uint32_t sm_idx_t;
typedef uint64_t sm_bitvec_t;
/** @brief Allocate a new, empty sparsemap_t with a buffer of \b size on the
* heap to use for storage of bitmap data.
@ -227,7 +229,7 @@ size_t sparsemap_get_capacity(sparsemap_t *map);
*/
bool sparsemap_is_set(sparsemap_t *map, sparsemap_idx_t idx);
/** @brief Assigns the bit at 0-based index \b idx to \b value.
/** @brief Sets the bit at index \b idx to \b value.
*
* A sparsemap has a fixed size buffer with a capacity that can be exhausted by
* when calling this function. In such cases the return value is not equal to
@ -237,41 +239,10 @@ bool sparsemap_is_set(sparsemap_t *map, sparsemap_idx_t idx);
*
* @param[in] map The sparsemap reference.
* @param[in] idx The 0-based offset into the bitmap index to modify.
* @param[in] value When true idx set to 1, otherwise idx set to 0.
* @returns the \b idx supplied on success or SPARSEMAP_IDX_MAX on error
* with \b errno set to ENOSPC when the map is full.
*/
sparsemap_idx_t sparsemap_assign(sparsemap_t *map, sparsemap_idx_t idx, bool value);
/** @brief Sets the bit at 0-based index \b idx to 1.
*
* A sparsemap has a fixed size buffer with a capacity that can be exhausted by
* when calling this function. In such cases the return value is not equal to
* the provided \b idx and errno is set to ENOSPC. In such situations it is
* possible to grow the data size and retry the set() operation under certain
* circumstances (see #sparsemap() and #sparsemap_set_data_size()).
*
* @param[in] map The sparsemap reference.
* @param[in] idx The 0-based offset into the bitmap index to set to 1;
* @returns the \b idx supplied on success or SPARSEMAP_IDX_MAX on error
* with \b errno set to ENOSPC when the map is full.
*/
sparsemap_idx_t sparsemap_set(sparsemap_t *map, sparsemap_idx_t idx);
/** @brief Unsets the bit at 0-based index \b idx (sets it to 0).
*
* A sparsemap has a fixed size buffer with a capacity that can be exhausted by
* when calling this function. In such cases the return value is not equal to
* the provided \b idx and errno is set to ENOSPC. In such situations it is
* possible to grow the data size and retry the set() operation under certain
* circumstances (see #sparsemap() and #sparsemap_set_data_size()).
*
* @param[in] map The sparsemap reference.
* @param[in] idx The 0-based offset into the bitmap index to unset.
* @returns the \b idx supplied on success or SPARSEMAP_IDX_MAX on error
* with \b errno set to ENOSPC when the map is full.
*/
sparsemap_idx_t sparsemap_unset(sparsemap_t *map, sparsemap_idx_t idx);
sparsemap_idx_t sparsemap_set(sparsemap_t *map, sparsemap_idx_t idx, bool value);
/** @brief Returns the byte size of the data buffer that has been used thus far.
*
@ -294,9 +265,9 @@ void *sparsemap_get_data(sparsemap_t *map);
*/
size_t sparsemap_count(sparsemap_t *map);
/** @brief Returns the position of the first bit set in the map.
/** @brief Returns the offset of the first bit set in the map.
*
* This is the same as the offset of the first set bit in the
* This is the same as the value of the first set bit in the
* map.
*
* @param[in] map The sparsemap reference.
@ -331,7 +302,7 @@ double sparsemap_fill_factor(sparsemap_t *map);
* @param[in] skip Start the scan after \b skip position in the map.
* @param[in] aux Auxiliary information passed to the scanner.
*/
void sparsemap_scan(sparsemap_t *map, void (*scanner)(uint32_t vec[], size_t n, void *aux), size_t skip, void *aux);
void sparsemap_scan(sparsemap_t *map, void (*scanner)(sm_idx_t vec[], size_t n, void *aux), size_t skip, void *aux);
/** @brief Merges the values from \b source into \b destination, \b source is unchanged.
*
@ -341,24 +312,21 @@ void sparsemap_scan(sparsemap_t *map, void (*scanner)(uint32_t vec[], size_t n,
* @param[in] source The bitmap to merge into \b destination.
* @returns 0 on success, or sets errno to ENOSPC and returns the amount of
* additional space required to successfully merge the maps.
* @todo change return to SPARSEMAP_IDX_MAX on ENOSPC to match other functions
*/
int sparsemap_merge(sparsemap_t *destination, sparsemap_t *source);
/** @brief Splits the bitmap by assigning all bits starting at \b idx to the
/** @brief Splits the bitmap by assigning all bits starting at \b offset to the
* \b other bitmap while removing them from \b map.
*
* Splits into [start, idx), and [idx, end]. The \b other bitmap is
* expected to be empty.
* The \b other bitmap is expected to be empty.
*
* @param[in] map The sparsemap reference.
* @param[in] idx The 0-based idx into the bitmap at which to split, if
* @param[in] offset The 0-based offset into the bitmap at which to split, if
* set to SPARSEMAP_IDX_MAX then the bits will be evenly split.
* @param[in] other The bitmap into which we place the split.
* @returns the idx at which the map was split, or sets errno to ENOSPC and
* returns SPARSEMAP_IDX_MAX.
* @returns the offset at which the map was split
*/
sparsemap_idx_t sparsemap_split(sparsemap_t *map, sparsemap_idx_t idx, sparsemap_t *other);
sparsemap_idx_t sparsemap_split(sparsemap_t *map, sparsemap_idx_t offset, sparsemap_t *other);
/** @brief Finds the index of the \b n'th bit set to \b value.
*

0
test/tdigest.h → include/tdigest.h
View file

18
test/common.c → lib/common.c
View file

@ -18,8 +18,8 @@
#endif
#endif
#include <common.h>
#include <sparsemap.h>
#include "../include/common.h"
#include "../include/sparsemap.h"
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wvariadic-macros"
@ -51,12 +51,6 @@ tsc(void)
return 0;
}
// TODO remove me, this is only used for debugging.
#ifdef SPARSEMAP_TESTING
char *QCC_showSparsemap(void *value, int len);
char *QCC_showChunk(void *value, int len);
#endif
// get microsecond timestamp
uint64_t
msts()
@ -128,7 +122,7 @@ shuffle(int *array, size_t n)
}
}
static int
int
compare_ints(const void *a, const void *b)
{
return *(const int *)a - *(const int *)b;
@ -353,7 +347,7 @@ bitmap_from_uint32(sparsemap_t *map, uint32_t number)
{
for (int i = 0; i < 32; i++) {
bool bit = number & (1 << i);
sparsemap_assign(map, i, bit);
sparsemap_set(map, i, bit);
}
}
@ -404,7 +398,7 @@ sm_bitmap_from_uint64(sparsemap_t *map, int offset, uint64_t number)
{
for (int i = offset; i < 64; i++) {
bool bit = number & ((uint64_t)1 << i);
sparsemap_assign(map, i, bit);
sparsemap_set(map, i, bit);
}
}
@ -422,7 +416,7 @@ sm_add_span(sparsemap_t *map, int map_size, int span_length)
}
} while (attempts);
for (sparsemap_idx_t i = placed_at; i < placed_at + span_length; i++) {
if (sparsemap_set(map, i) != i) {
if (sparsemap_set(map, i, true) != i) {
return placed_at; // TODO error?
}
}

0
test/roaring.c → lib/roaring.c
View file

0
test/tdigest.c → lib/tdigest.c
View file

3389
sparsemap.c
View file

File diff suppressed because it is too large Load diff

1882
src/sparsemap.c Normal file
View file

File diff suppressed because it is too large Load diff

831
test/qc.c
View file

@ -1,831 +0,0 @@
/********************************************************************
* Copyright (c) 2014, Andrea Zito
* All rights reserved.
*
* License: BSD3
********************************************************************/
#include <stddef.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "qc.h"
// TODO: fix these...
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wimplicit-function-declaration"
#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wint-conversion"
#pragma GCC diagnostic ignored "-Wpedantic"
typedef void (*QCC_genRaw)(void *ptr);
typedef void (*QCC_genRawR)(void *ptr, void *from, void *to);
struct QCC_Stamp {
char *label;
int n;
struct QCC_Stamp *next;
};
typedef struct QCC_Result {
QCC_TestStatus status;
QCC_Stamp *stamps;
QCC_GenValue **arguments;
int argumentsN;
} QCC_Result;
enum QCC_deref_type { NONE, LONG, INT, FLOAT, DOUBLE, BYTE, CHAR };
void
QCC_init(int seed)
{
if (seed) {
srandom(seed);
} else {
srandom(time(NULL));
}
}
/***********************************************************************
* Generators helper functions
***********************************************************************/
static char *
QCC_showSimpleValue(void *value, enum QCC_deref_type dt, int maxsize, const char *format)
{
char *vc = malloc(sizeof(char) * (maxsize + 1));
switch (dt) {
case LONG:
snprintf(vc, maxsize + 1, format, *(long *)value);
break;
case INT:
snprintf(vc, maxsize + 1, format, *(int *)value);
break;
case FLOAT:
snprintf(vc, maxsize + 1, format, *(float *)value);
break;
case DOUBLE:
snprintf(vc, maxsize + 1, format, *(double *)value);
break;
case CHAR:
snprintf(vc, maxsize + 1, format, *(char *)value);
break;
case BYTE:
snprintf(vc, maxsize + 1, format, *(uint8_t *)value);
break;
default:
snprintf(vc, maxsize + 1, format, *(int *)value);
break;
}
vc[maxsize] = 0;
return vc;
}
static void
QCC_freeSimpleValue(void *value)
{
free(value);
}
QCC_GenValue *
QCC_initGenValue(void *value, int n, QCC_showValue show, QCC_freeValue free)
{
QCC_GenValue *gv = malloc(sizeof(QCC_GenValue));
*gv = (QCC_GenValue) { .value = value, .n = n, .show = show, .free = free };
return gv;
}
/***********************************************************************
* Generators implementations
***********************************************************************/
static char *
QCC_showLong(void *value, int len)
{
return QCC_showSimpleValue(value, LONG, 21, "%ld");
}
void
QCC_genLongAtR(long *l, long *from, long *to)
{
long _from = *from;
long _to = *to;
unsigned long n = _to - _from;
if (n > RAND_MAX) {
_from = _from + n / 2 - RAND_MAX / 2;
_to = _from + n / 2 + RAND_MAX / 2;
n = _to - _from;
}
*l = (random() % n) + _from;
}
void
QCC_genLongAt(long *l)
{
long from = QCC_LONG_FROM;
long to = QCC_LONG_TO;
QCC_genLongAtR(l, &from, &to);
}
QCC_GenValue *
QCC_genLongR(long from, long to)
{
long *v = malloc(sizeof(long));
QCC_genLongAtR(v, &from, &to);
return QCC_initGenValue(v, 1, QCC_showLong, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genLong()
{
return QCC_genLongR(QCC_LONG_FROM, QCC_LONG_TO);
}
static char *
QCC_showInt(void *value, int len)
{
return QCC_showSimpleValue(value, INT, 11, "%d");
}
void
QCC_genIntAtR(int *i, int *from, int *to)
{
int n = *to - *from;
*i = (random() % n) + *from;
}
void
QCC_genIntAt(int *i)
{
int from = QCC_INT_FROM;
int to = QCC_INT_TO;
QCC_genIntAtR(i, &from, &to);
}
QCC_GenValue *
QCC_genIntR(int from, int to)
{
int *v = malloc(sizeof(int));
QCC_genIntAtR(v, &from, &to);
return QCC_initGenValue(v, 1, QCC_showInt, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genInt()
{
return QCC_genIntR(QCC_INT_FROM, QCC_INT_TO);
}
static char *
QCC_showDouble(void *value, int len)
{
return QCC_showSimpleValue(value, DOUBLE, 50, "%.12e");
}
void
QCC_genDoubleAtR(double *d, double *from, double *to)
{
double r = (double)random() / (double)RAND_MAX;
*d = *from + (*to - *from) * r;
}
void
QCC_genDoubleAt(double *d)
{
double from = QCC_DOUBLE_FROM;
double to = QCC_DOUBLE_TO;
QCC_genDoubleAtR(d, &from, &to);
}
QCC_GenValue *
QCC_genDoubleR(double from, double to)
{
double *v = malloc(sizeof(double));
QCC_genDoubleAtR(v, &from, &to);
return QCC_initGenValue(v, 1, QCC_showDouble, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genDouble()
{
return QCC_genDoubleR(QCC_DOUBLE_FROM, QCC_DOUBLE_TO);
}
static char *
QCC_showFloat(void *value, int len)
{
return QCC_showSimpleValue(value, FLOAT, 50, "%.12e");
}
void
QCC_genFloatAtR(float *f, float *from, float *to)
{
float r = (float)random() / (float)RAND_MAX;
*f = *from + (*to - *from) * r;
}
void
QCC_genFloatAt(float *f)
{
float from = QCC_FLOAT_FROM;
float to = QCC_FLOAT_TO;
QCC_genFloatAtR(f, &from, &to);
}
QCC_GenValue *
QCC_genFloatR(float from, float to)
{
float *v = malloc(sizeof(float));
QCC_genFloatAtR(v, &from, &to);
return QCC_initGenValue(v, 1, QCC_showFloat, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genFloat()
{
return QCC_genFloatR(QCC_FLOAT_FROM, QCC_FLOAT_TO);
}
static char *
QCC_showBoolean(void *value, int len)
{
QCC_Boolean *b = (QCC_Boolean *)value;
if (*b) {
return strdup("TRUE");
} else {
return strdup("FALSE");
}
}
void
QCC_genBooleanAt(QCC_Boolean *b)
{
double r = (double)random() / (double)RAND_MAX;
*b = r > 0.5 ? QCC_TRUE : QCC_FALSE;
}
QCC_GenValue *
QCC_genBoolean()
{
QCC_Boolean *v = malloc(sizeof(QCC_Boolean));
QCC_genBooleanAt(v);
return QCC_initGenValue(v, 1, QCC_showBoolean, QCC_freeSimpleValue);
}
static char *
QCC_showChar(void *value, int len)
{
return QCC_showSimpleValue(value, CHAR, 3, "'%c'");
}
void
QCC_genCharAt(char *c)
{
*c = (char)(random() % 93) + 33;
}
QCC_GenValue *
QCC_genChar()
{
char *v = malloc(sizeof(char));
QCC_genCharAt(v);
return QCC_initGenValue(v, 1, QCC_showChar, QCC_freeSimpleValue);
}
/***********************************************************************
* Array generators implementations
***********************************************************************/
QCC_GenValue *
QCC_genArrayOf(int len, QCC_genRaw elemGen, size_t elemSize, QCC_showValue show, QCC_freeValue free)
{
int n = random() % len;
uint8_t *arr = malloc(n * elemSize);
int p, i;
for (i = 0, p = 0; i < n; i++, p += elemSize)
elemGen(arr + p);
return QCC_initGenValue(arr, n, show, free);
}
QCC_GenValue *
QCC_genArrayOfR(int len, QCC_genRawR elemGen, void *from, void *to, size_t elemSize, QCC_showValue show, QCC_freeValue free)
{
int n = random() % len;
uint8_t *arr = malloc(n * elemSize);
int p, i;
for (i = 0, p = 0; i < n; i++, p += elemSize)
elemGen(arr + p, from, to);
return QCC_initGenValue(arr, n, show, free);
}
static char *
QCC_showString(void *value, int len)
{
return QCC_showSimpleValue(value, NONE, len, "%s");
}
QCC_GenValue *
QCC_genStringL(int len)
{
QCC_GenValue *s = QCC_genArrayOf(len, (QCC_genRaw)QCC_genCharAt, sizeof(char), QCC_showString, QCC_freeSimpleValue);
((char *)s->value)[s->n - 1] = '\0';
return s;
}
QCC_GenValue *
QCC_genString()
{
return QCC_genStringL(50);
}
static char *
QCC_showSimpleArray(void *value, size_t elemSize, QCC_showValue showValue, int len)
{
char **valStr = malloc(sizeof(char *) * len);
int valStrLen = 0;
int i;
for (i = 0; i < len; i++) {
valStr[i] = showValue(((uint8_t *)value) + (i * elemSize), 1);
valStrLen += strlen(valStr[i]);
}
int totStrLen = valStrLen + 2 + 2 * len + 1;
char *str = malloc(sizeof(char) * totStrLen);
sprintf(str, "[");
int currLen = 1;
for (i = 0; i < len; i++) {
if (i == 0) {
sprintf(str + currLen, "%s", valStr[i]);
} else {
sprintf(str + currLen, ", %s", valStr[i]);
currLen += 2;
}
currLen += strlen(valStr[i]);
free(valStr[i]);
}
sprintf(str + currLen, "]");
free(valStr);
return str;
}
static char *
QCC_showByte(void *value, int len)
{
return QCC_showSimpleValue(value, BYTE, 3, "'%x'");
}
static char *
QCC_showArrayByte(void *value, int n)
{
return QCC_showSimpleArray(value, sizeof(long), QCC_showByte, n);
}
void
QCC_genByteAtR(uint8_t *b, uint8_t *from, uint8_t *to)
{
uint8_t r = (uint8_t)random() / (uint8_t)RAND_MAX;
*b = *from + (*to - *from) * r;
}
void
QCC_genByteAt(uint8_t *b)
{
*b = ((uint8_t)random() / (uint8_t)RAND_MAX) % UINT8_MAX;
}
QCC_GenValue *
QCC_genArrayByteLR(int len, long from, long to)
{
return QCC_genArrayOfR(len, (QCC_genRawR)QCC_genByteAtR, &from, &to, sizeof(long), QCC_showArrayByte, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayByteL(int len)
{
return QCC_genArrayOf(len, (QCC_genRaw)QCC_genByteAt, sizeof(long), QCC_showArrayByte, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayByte()
{
return QCC_genArrayOf(50, (QCC_genRaw)QCC_genByteAt, sizeof(long), QCC_showArrayByte, QCC_freeSimpleValue);
}
static char *
QCC_showArrayLong(void *value, int n)
{
return QCC_showSimpleArray(value, sizeof(long), QCC_showLong, n);
}
QCC_GenValue *
QCC_genArrayLongLR(int len, long from, long to)
{
return QCC_genArrayOfR(len, (QCC_genRawR)QCC_genLongAtR, &from, &to, sizeof(long), QCC_showArrayLong, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayLongL(int len)
{
return QCC_genArrayOf(len, (QCC_genRaw)QCC_genLongAt, sizeof(long), QCC_showArrayLong, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayLong()
{
return QCC_genArrayOf(50, (QCC_genRaw)QCC_genLongAt, sizeof(long), QCC_showArrayLong, QCC_freeSimpleValue);
}
static char *
QCC_showArrayInt(void *value, int n)
{
return QCC_showSimpleArray(value, sizeof(int), QCC_showInt, n);
}
QCC_GenValue *
QCC_genArrayIntLR(int len, int from, int to)
{
return QCC_genArrayOfR(len, (QCC_genRawR)QCC_genIntAtR, &from, &to, sizeof(int), QCC_showArrayInt, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayIntL(int len)
{
return QCC_genArrayOf(len, (QCC_genRaw)QCC_genIntAt, sizeof(int), QCC_showArrayInt, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayInt()
{
return QCC_genArrayOf(50, (QCC_genRaw)QCC_genIntAt, sizeof(int), QCC_showArrayInt, QCC_freeSimpleValue);
}
static char *
QCC_showArrayDouble(void *value, int n)
{
return QCC_showSimpleArray(value, sizeof(double), QCC_showDouble, n);
}
QCC_GenValue *
QCC_genArrayDoubleLR(int len, double from, double to)
{
return QCC_genArrayOfR(len, (QCC_genRawR)QCC_genDoubleAtR, &from, &to, sizeof(double), QCC_showArrayDouble, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayDoubleL(int len)
{
return QCC_genArrayOf(len, (QCC_genRaw)QCC_genDoubleAt, sizeof(double), QCC_showArrayDouble, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayDouble()
{
return QCC_genArrayOf(50, (QCC_genRaw)QCC_genDoubleAt, sizeof(double), QCC_showArrayDouble, QCC_freeSimpleValue);
}
static char *
QCC_showArrayFloat(void *value, int n)
{
return QCC_showSimpleArray(value, sizeof(float), QCC_showFloat, n);
}
QCC_GenValue *
QCC_genArrayFloatLR(int len, float from, float to)
{
return QCC_genArrayOfR(len, (QCC_genRawR)QCC_genFloatAtR, &from, &to, sizeof(float), QCC_showArrayFloat, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayFloatL(int len)
{
return QCC_genArrayOf(len, (QCC_genRaw)QCC_genFloatAt, sizeof(float), QCC_showArrayFloat, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayFloat()
{
return QCC_genArrayOf(50, (QCC_genRaw)QCC_genFloatAt, sizeof(float), QCC_showArrayFloat, QCC_freeSimpleValue);
}
static char *
QCC_showArrayBoolean(void *value, int n)
{
return QCC_showSimpleArray(value, sizeof(QCC_Boolean), QCC_showBoolean, n);
}
QCC_GenValue *
QCC_genArrayBooleanL(int len)
{
return QCC_genArrayOf(len, (QCC_genRaw)QCC_genBooleanAt, sizeof(QCC_Boolean), QCC_showArrayBoolean, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayBoolean()
{
return QCC_genArrayOf(50, (QCC_genRaw)QCC_genBooleanAt, sizeof(QCC_Boolean), QCC_showArrayBoolean, QCC_freeSimpleValue);
}
static char *
QCC_showArrayChar(void *value, int n)
{
return QCC_showSimpleArray(value, sizeof(char), QCC_showChar, n);
}
QCC_GenValue *
QCC_genArrayCharL(int len)
{
return QCC_genArrayOf(len, (QCC_genRaw)QCC_genCharAt, sizeof(char), QCC_showArrayChar, QCC_freeSimpleValue);
}
QCC_GenValue *
QCC_genArrayChar()
{
return QCC_genArrayOf(50, (QCC_genRaw)QCC_genCharAt, sizeof(char), QCC_showArrayChar, QCC_freeSimpleValue);
}
/***********************************************************************
* Convenience functions
***********************************************************************/
QCC_TestStatus
QCC_not(QCC_TestStatus propStatus)
{
switch (propStatus) {
case QCC_OK:
return QCC_FAIL;
case QCC_FAIL:
return QCC_OK;
case QCC_NOTHING:
return QCC_NOTHING;
default:
return QCC_FAIL;
}
}
QCC_TestStatus
QCC_and(QCC_TestStatus prop1Status, QCC_TestStatus prop2Status)
{
switch (prop1Status) {
case QCC_OK:
return prop2Status;
case QCC_FAIL:
return QCC_FAIL;
case QCC_NOTHING:
return QCC_NOTHING;
default:
return QCC_FAIL;
}
}
QCC_TestStatus
QCC_or(QCC_TestStatus prop1Status, QCC_TestStatus prop2Status)
{
switch (prop1Status) {
case QCC_OK:
return QCC_OK;
case QCC_FAIL:
case QCC_NOTHING:
return prop2Status;
default:
return QCC_FAIL;
}
}
QCC_TestStatus
QCC_xor(QCC_TestStatus prop1Status, QCC_TestStatus prop2Status)
{
switch (prop1Status) {
case QCC_OK:
return QCC_not(prop2Status);
case QCC_FAIL:
return prop2Status;
case QCC_NOTHING:
return QCC_NOTHING;
default:
return QCC_FAIL;
}
}
/***********************************************************************
* Categorization function
***********************************************************************/
void
QCC_freeStamp(QCC_Stamp *stamps)
{
QCC_Stamp *tstamps;
QCC_Stamp *curr;
for (tstamps = stamps; tstamps != NULL;) {
curr = tstamps;
tstamps = tstamps->next;
free(curr->label);
free(curr);
}
}
static void
QCC_insertOrdStamp(QCC_Stamp **stamps, QCC_Stamp *s)
{
QCC_Stamp *new = malloc(sizeof(QCC_Stamp));
*new = (QCC_Stamp) { .label = strdup(s->label), .n = s->n, .next = NULL };
QCC_Stamp *tstamp = *stamps;
QCC_Stamp **pre = stamps;
while (tstamp) {
if (tstamp->n < new->n) {
break;
} else {
pre = &tstamp->next;
tstamp = tstamp->next;
}
}
*pre = new;
new->next = tstamp;
}
static QCC_Stamp *
QCC_sortStamp(QCC_Stamp *stamps)
{
QCC_Stamp *sortedStamps = NULL;
QCC_Stamp *tstamp;
for (tstamp = stamps; tstamp != NULL; tstamp = tstamp->next) {
QCC_insertOrdStamp(&sortedStamps, tstamp);
}
return sortedStamps;
}
static void
QCC_labelN(QCC_Stamp **stamps, char *label, int n)
{
QCC_Stamp *ptr = *stamps;
QCC_Stamp *pre = NULL;
QCC_Stamp *new;
while (ptr) {
if (strcmp(ptr->label, label) == 0) {
(ptr->n)++;
return;
}
pre = ptr;
ptr = ptr->next;
}
new = malloc(sizeof(QCC_Stamp));
*new = (QCC_Stamp) { .label = strdup(label), .n = 1, .next = NULL };
if (pre) {
pre->next = new;
} else {
*stamps = new;
}
}
void
QCC_label(QCC_Stamp **stamps, char *label)
{
return QCC_labelN(stamps, label, 1);
}
static void
QCC_mergeLabels(QCC_Stamp **dst, QCC_Stamp *src)
{
for (; src != NULL; src = src->next)
QCC_labelN(dst, src->label, src->n);
}
/***********************************************************************
* Testing functions
***********************************************************************/
void
QCC_freeGenValues(QCC_GenValue **arguments, int argumentsN)
{
int i;
for (i = 0; i < argumentsN; i++) {
arguments[i]->free(arguments[i]->value);
free(arguments[i]);
}
if (arguments)
free(arguments);
}
void
QCC_freeResult(QCC_Result *res)
{
QCC_freeStamp(res->stamps);
QCC_freeGenValues(res->arguments, res->argumentsN);
}
QCC_Result
QCC_vforAll(QCC_property prop, int genNum, va_list genP)
{ // QCC_gen *genLst,
QCC_GenValue **vals = NULL;
if (genNum) {
int i;
vals = malloc(sizeof(QCC_GenValue *) * genNum);
for (i = 0; i < genNum; i++) {
QCC_gen gen = va_arg(genP, QCC_gen);
vals[i] = gen();
}
}
QCC_Stamp *stamps = NULL;
QCC_TestStatus status = prop(vals, genNum, &stamps);
return (QCC_Result) { .status = status, .stamps = stamps, .arguments = vals, .argumentsN = genNum };
}
QCC_Result
QCC_forAll(QCC_property prop, int genNum, ...)
{ // QCC_gen *genLst,
va_list genP;
QCC_Result res;
va_start(genP, genNum);
res = QCC_vforAll(prop, genNum, genP);
va_end(genP);
return res;
}
static void
QCC_printStamps(QCC_Stamp *stamps, int n)
{
QCC_Stamp *sortedStamps = QCC_sortStamp(stamps);
QCC_Stamp *tstamps;
for (tstamps = sortedStamps; tstamps != NULL; tstamps = tstamps->next)
printf("%.2f%%\t%s\n", (tstamps->n / (float)n) * 100, tstamps->label);
if (sortedStamps)
QCC_freeStamp(sortedStamps);
}
static void
QCC_printArguments(QCC_GenValue **arguments, int argumentsN)
{
int i;
for (i = 0; i < argumentsN; i++) {
char *s = arguments[i]->show(arguments[i]->value, arguments[i]->n);
printf("%s\n", s);
free(s);
}
}
int
QCC_testForAll(int num, int maxFail, QCC_property prop, int genNum, ...)
{
va_list genP;
int succ = 0;
int fail = 0;
QCC_Result res = { .status = QCC_OK };
QCC_Stamp *stamps = NULL;
while (succ < num && fail < maxFail) {
va_start(genP, genNum);
res = QCC_vforAll(prop, genNum, genP);
va_end(genP);
if (res.status == QCC_FAIL) {
break;
} else {
if (res.status == QCC_OK) {
succ++;
QCC_mergeLabels(&stamps, res.stamps);
} else
fail++;
QCC_freeResult(&res);
}
}
if (succ == num) {
//printf("%d test passed (%d)!\n", succ, fail);
QCC_printStamps(stamps, succ);
if (stamps)
QCC_freeStamp(stamps);
return 0;
} else if (res.status == QCC_FAIL) {
printf("\nFalsifiable after %d test\n", succ + 1);
QCC_printArguments(res.arguments, res.argumentsN);
QCC_freeResult(&res);
if (stamps)
QCC_freeStamp(stamps);
return 1;
} else if (fail >= maxFail) {
printf("\nGave up after %d tests!\n", succ);
QCC_printStamps(stamps, succ);
if (stamps)
QCC_freeStamp(stamps);
return -1;
}
return 0;
}
#pragma GCC diagnostic pop

284
test/qc.h
View file

@ -1,284 +0,0 @@
/********************************************************************
* Copyright (c) 2014, Andrea Zito
* All rights reserved.
*
* License: BSD3
********************************************************************/
#ifndef QUICKCHECK4C_C
#define QUICKCHECK4C_C
#include <stdarg.h>
#include <stdlib.h>
/* Default ranges used for type generation */
#define QCC_LONG_FROM -RAND_MAX / 2
#define QCC_LONG_TO RAND_MAX / 2
#define QCC_INT_FROM -RAND_MAX / 2
#define QCC_INT_TO RAND_MAX / 2
#define QCC_DOUBLE_FROM ((double)-(RAND_MAX / 2))
#define QCC_DOUBLE_TO ((double)(RAND_MAX / 2))
#define QCC_FLOAT_FROM ((float)-(RAND_MAX / 2))
#define QCC_FLOAT_TO ((float)(RAND_MAX / 2))
/**
* Explicit definition of a boolean type compatible with
* normal C boolean interpretation.
*/
typedef enum { QCC_TRUE = 1, QCC_FALSE = 0 } QCC_Boolean;
/**
* Enumerator defining the evaluation of a property.
* QCC_OK represent a satisfied property.
* QCC_FAIL represent a falsified property.
* QCC_NOTHING indicates a property that didn't fail
* but should NOT be considered in the successes count or
* categorization (used by QCC_IMPLY)
*/
typedef enum { QCC_OK = 1, QCC_FAIL = 0, QCC_NOTHING = -1 } QCC_TestStatus;
/**
* Convenince macro to extract generated values inside a property.
* Es: int a = *QCC_getValue(vals, 0, int*)
*
* @param vals A QCC_GenValue array
* @param idx Index of the value to extract
* @param type Type of the generated value
*/
#define QCC_getValue(vals, idx, type) ((type)vals[idx]->value)
/**
* Signature of function used to represent values in a human readable
* fashion.
* Calling this function allocates memory that must be freed by the caller.
*
* @param value Pointer to the value to show
* @param len Lenght of the data (used to keep track of array lengths)
* @return String representation of the value.
*/
typedef char *(*QCC_showValue)(void *value, int len);
/**
* Signature of function used to free generated values.
*
* @param value Pointer to the value to free
*/
typedef void (*QCC_freeValue)(void *value);
/**
* Structure defining a generated value.
* It specifies the value itself (alongside its length in case
* of arrays), a function pointer for getting a human readable
* string representation of the value and a function pointer to
* free the memory allocated for the value.
*
* @param value Pointer to the memory allocated for the value
* @param n Length of the value (1 for simple types, length for arrays)
* @param show Function to get string representation of the value
* @param free Function to free the memory of the value
*/
typedef struct QCC_GenValue {
void *value;
int n;
QCC_showValue show;
QCC_freeValue free;
} QCC_GenValue;
/**
* Opaque structure used to categorize test instances.
* See QCC_property and QCC_label.
*/
typedef struct QCC_Stamp QCC_Stamp;
/**
* Signature of functions used to generate random values
*/
typedef QCC_GenValue *(*QCC_gen)();
/**
* Signature of property functions.
*
* @param vals Array of generated random values
* @param len Number of generated values
* @param stamp Used to categorize test instances via QCC_label
*/
typedef QCC_TestStatus (*QCC_property)(QCC_GenValue **vals, int len, QCC_Stamp **stamps);
/**
* Implements logic implication.
* The implication is satisfied if both the precondition and the property are
* satisfied.
* In case the precondition is not satisfied the special QCC_NOTHING value is
* returned, indicating that the current test should not be considered as a
* success.
*
* @param precondition A boolean condition
* @param property A QCC_property to evaluate iff the precondition is satisfied
* @return QCC_TestStatus
*/
#define QCC_imply(precondition, property) precondition ? property : QCC_NOTHING
/**
* Convenience function to express property conjunction.
* The function returns:
* - QCC_OK iff prop1Status == prop2Status == QCC_OK
* - QCC_FAIL iff prop1Status == QCC_FAIL || prop2Status == QCC_FAIL
* - QCC_NOTHING iff prop1Status != QCC_FAIL && prop2Status != QCC_FAIL &&
* (prop1Status == QCC_NOTHING || prop2Status == QCC_NOTHING)
*
* @param prop1Status The evaluation status of property 1
* @param prop2Status The evaluation status of property 2
* @return The evaluation status of the conjunction of property 1 and property 2
*/
QCC_TestStatus QCC_and(QCC_TestStatus prop1Status, QCC_TestStatus prop2Status);
/**
* Convenience function to express property disjunction.
* The function returns:
* - QCC_OK iff prop1Status == QCC_OK || prop2Status == QCC_OK
* - QCC_FAIL iff prop1Status == QCC_FAIL && prop2Status == QCC_FAIL
* - QCC_NOTHING iff prop1Status != QCC_OK && prop2Status != QCC_OK &&
* (prop1Status == QCC_NOTHING || prop2Status == QCC_NOTHING)
*
* @param prop1Status The evaluation status of property 1
* @param prop2Status The evaluation status of property 2
* @return The evaluation status of the disjunction of property 1 and property 2
*/
QCC_TestStatus QCC_or(QCC_TestStatus prop1Status, QCC_TestStatus prop2Status);
/**
* Convenience function to express property exclusive disjunction.
* The function returns:
* - QCC_OK iff (prop1Status == QCC_OK && prop2Status == QCC_FAIL) ||
* (prop1Status == QCC_FAIL && prop2Status == QCC_OK)
* - QCC_FAIL iff prop1Status == prop2Status != QCC_NOTHING
* - QCC_NOTHING iff prop1Status == QCC_NOTHING || prop2Status = QCC_NOTHING
*
* @param prop1Status The evaluation status of property 1
* @param prop2Status The evaluation status of property 2
* @return The evaluation status of the exclusive disjunction of property 1 and
* property 2
*/
QCC_TestStatus QCC_xor(QCC_TestStatus prop1Status, QCC_TestStatus prop2Status);
/**
* Convenience function to express property negation.
* The function returns:
* - QCC_OK iff propStatus == QCC_FAIL
* - QCC_FAIL iff propStatus == QCC_OK
* - QCC_NOTHING iff propStatus == QCC_NOTHING
*/
QCC_TestStatus QCC_not(QCC_TestStatus propStatus);
/**
* Initialize the random generator using a specific seed.
*
* @param seed The seed to use or 0 to automatically select seed
*/
void QCC_init(int seed);
/**
* Adds a label to the test stamps.
*
* @param stamps Stamps associated to the current test
* @param label Label to add to the test stamps
*/
void QCC_label(QCC_Stamp **stamps, char *label);
/**
* Test a property for num times allowing at most maxFail unsuccesful
* argument generation.
*
* If all num test succede, the function outputs a success string and
* return 0. If argument generation fails maxFail time before a success
* string is printed reporting the number of success test cases and return -1.
*
* In both cases any label label gathered during test evaluation is printed
* alongside its distribution.
*
* If a set of arguments falsifying the property is found, the testing is
* interrupted immediately and a failure string is printed alongside the
* set of arguments which caused the failure.
*
* @parm num Number of successful test to perform
* @parm maxFail Maximum number of unsuccessful argument generation
* (i.e. unsatisfied implication precondition)
* @parm prop Property to test
* @parm genNum Number of generators specified as vararg
* @param ... genNum QCC_gen function to use as generators
* @return 0 (all num test passed),
* -1 (gave up after maxFail unsuccessful arguments generation),
* 1 (property falsified)
*/
int QCC_testForAll(int num, int maxFail, QCC_property prop, int genNum, ...);
/*************************************************************
* Helper function for generator definitions
*************************************************************/
/**
* Initialize a QCC_GenValue using the specified parameters
*
* @param value Raw generated balue
* @param n Length of the value in case of an array (1 should be used otherwise)
* @param show Pointer to a QCC_ShowValue function to use for displaying the raw
* value
* @param free Pointer to a QCC_FreeValue function to use for free the raw value
* memory
* @return Initialized QCC_GenValue
*/
QCC_GenValue *QCC_initGenValue(void *value, int n, QCC_showValue show, QCC_freeValue free);
/*************************************************************
* Simple types generators
*************************************************************/
QCC_GenValue *QCC_genLong();
QCC_GenValue *QCC_genLongR(long from, long to);
QCC_GenValue *QCC_genInt();
QCC_GenValue *QCC_genIntR(int from, int to);
QCC_GenValue *QCC_genDouble();
QCC_GenValue *QCC_genDoubleR(double from, double to);
QCC_GenValue *QCC_genFloat();
QCC_GenValue *QCC_genFloatR(float from, float to);
QCC_GenValue *QCC_genBoolean();
QCC_GenValue *QCC_genChar();
/*************************************************************
* Array types generators
*************************************************************/
QCC_GenValue *QCC_genString();
QCC_GenValue *QCC_genStringL(int len);
QCC_GenValue *QCC_genArrayByte();
QCC_GenValue *QCC_genArrayByteL(int len);
QCC_GenValue *QCC_genArrayByteLR(int len, long from, long to);
QCC_GenValue *QCC_genArrayLong();
QCC_GenValue *QCC_genArrayLongL(int len);
QCC_GenValue *QCC_genArrayLongLR(int len, long from, long to);
QCC_GenValue *QCC_genArrayInt();
QCC_GenValue *QCC_genArrayIntL(int len);
QCC_GenValue *QCC_genArrayIntLR(int len, int from, int to);
QCC_GenValue *QCC_genArrayDouble();
QCC_GenValue *QCC_genArrayDoubleL(int len);
QCC_GenValue *QCC_genArrayDoubleLR(int len, double from, double to);
QCC_GenValue *QCC_genArrayFloat();
QCC_GenValue *QCC_genArrayFloatL(int len);
QCC_GenValue *QCC_genArrayFloatLR(int len, float from, float to);
QCC_GenValue *QCC_genArrayBoolean();
QCC_GenValue *QCC_genArrayBooleanL(int len);
QCC_GenValue *QCC_genArrayChar();
QCC_GenValue *QCC_genArrayCharL(int len);
QCC_GenValue *QCC_genArrayString();
QCC_GenValue *QCC_genArrayStringL(int len, int strLen);
#endif

0
test/midl.c → tests/midl.c
View file

0
test/munit.c → tests/munit.c
View file

0
test/munit.h → tests/munit.h
View file

12
test/soak.c → tests/soak.c
View file

@ -10,10 +10,10 @@
#include <time.h>
#include <unistd.h>
#include <common.h>
#include <roaring.h>
#include <sparsemap.h>
#include <tdigest.h>
#include "../include/common.h"
#include "../include/roaring.h"
#include "../include/sparsemap.h"
#include "../include/tdigest.h"
#include "midl.c"
@ -336,7 +336,7 @@ record_release_span_mutation(FILE *out, pgno_t pg, unsigned len)
}
static void
__scan_record_offsets(uint32_t v[], size_t n, void *aux)
__scan_record_offsets(sm_idx_t v[], size_t n, void *aux)
{
FILE *out = (FILE *)aux;
for (size_t i = 0; i < n; i++) {
@ -377,7 +377,7 @@ _sparsemap_set(sparsemap_t **_map, sparsemap_idx_t idx, bool value)
{
sparsemap_t *map = *_map, *new_map = NULL;
do {
sparsemap_idx_t l = sparsemap_assign(map, idx, value);
sparsemap_idx_t l = sparsemap_set(map, idx, value);
if (l != idx) {
if (errno == ENOSPC) {
size_t capacity = sparsemap_get_capacity(map) + 64;

332
test/test.c → tests/test.c
View file

@ -1,5 +1,5 @@
/*
* sparsemap is MIT-licensed, but for this file:
* smartmap is MIT-licensed, but for this file:
*
* To the extent possible under law, the author(s) of this file have
* waived all copyright and related or neighboring rights to this
@ -10,15 +10,15 @@
#define MUNIT_NO_FORK (1)
#define MUNIT_ENABLE_ASSERT_ALIASES (1)
#include <common.h>
#include <errno.h>
#include <munit.h>
#include <qc.h>
#include <sparsemap.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "../include/sparsemap.h"
#include "common.h"
#include "munit.h"
#define munit_free free
#if defined(_MSC_VER)
@ -27,9 +27,6 @@
#define SELECT_FALSE
char *QCC_showSparsemap(void *value, int len);
char *QCC_showChunk(void *value, int len);
/* !!! Duplicated here for testing purposes. Keep in sync, or suffer. !!! */
struct sparsemap {
size_t m_capacity;
@ -43,33 +40,21 @@ struct user_data {
/* -------------------------- Supporting Functions for Testing */
size_t
populate_map_rle(sparsemap_t *map, size_t loc, size_t num, size_t amount)
{
size_t i, len = munit_rand_int_range(1, num) * amount;
for (i = 0; i < len; i++) {
sparsemap_set(map, loc + i);
}
return i;
}
size_t
void
populate_map(sparsemap_t *map, int size, int max_value)
{
int array[size];
size_t i, before;
size_t before;
setup_test_array(array, size, max_value);
shuffle(array, size);
before = sparsemap_count(map);
for (i = 0; i < size; i++) {
sparsemap_set(map, array[i]);
for (int i = 0; i < size; i++) {
sparsemap_set(map, array[i], true);
bool set = sparsemap_is_set(map, array[i]);
assert_true(set);
}
assert_true(sparsemap_count(map) == before + size);
return i;
}
static void *
@ -103,7 +88,6 @@ test_api_new(const MunitParameter params[], void *data)
assert_ptr_not_null(map);
assert_true(map->m_capacity == 1024);
assert_true(map->m_data_used == sizeof(uint32_t));
assert_true((((uint8_t)map->m_data[0]) & 0x03) == 0x00);
munit_free(map);
@ -221,7 +205,7 @@ test_api_clear(const MunitParameter params[], void *data)
assert_ptr_not_null(map);
sparsemap_set(map, 42);
sparsemap_set(map, 42, true);
assert_true(sparsemap_is_set(map, 42));
sparsemap_clear(map);
assert_false(sparsemap_is_set(map, 42));
@ -330,7 +314,7 @@ test_api_remaining_capacity(const MunitParameter params[], void *data)
int i = 0;
double cap;
do {
sparsemap_set(map, i++ * 2);
sparsemap_set(map, i++, true);
cap = sparsemap_capacity_remaining(map);
} while (cap > 1.0 && errno != ENOSPC);
errno = 0;
@ -343,7 +327,7 @@ test_api_remaining_capacity(const MunitParameter params[], void *data)
i = 0;
do {
int p = munit_rand_int_range(0, 150000);
sparsemap_set(map, p);
sparsemap_set(map, p, true);
i++;
cap = sparsemap_capacity_remaining(map);
} while (cap > 1.0 && errno != ENOSPC);
@ -362,7 +346,6 @@ test_api_get_capacity_setup(const MunitParameter params[], void *user_data)
sparsemap_init(map, buf, 1024);
populate_map(map, 1024, 3 * 1024);
populate_map_rle(map, 3 * 1024, 5, 4096);
return (void *)map;
}
@ -382,7 +365,7 @@ test_api_get_capacity(const MunitParameter params[], void *data)
assert_ptr_not_null(map);
sparsemap_set(map, 42);
sparsemap_set(map, 42, true);
assert_true(sparsemap_is_set(map, 42));
assert_true(sparsemap_get_capacity(map) == 1024);
@ -417,16 +400,9 @@ test_api_is_set(const MunitParameter params[], void *data)
assert_ptr_not_null(map);
sparsemap_set(map, 42);
sparsemap_set(map, 42, true);
assert_true(sparsemap_is_set(map, 42));
sparsemap_clear(map);
size_t n = populate_map_rle(map, 0, 10, 2718);
for (size_t i = 0; i < n; i++) {
assert_true(sparsemap_is_set(map, i));
}
return MUNIT_OK;
}
@ -459,12 +435,12 @@ test_api_set(const MunitParameter params[], void *data)
assert_false(sparsemap_is_set(map, 1));
assert_false(sparsemap_is_set(map, 8192));
sparsemap_set(map, 1);
sparsemap_set(map, 8192);
sparsemap_set(map, 1, true);
sparsemap_set(map, 8192, true);
assert_true(sparsemap_is_set(map, 1));
assert_true(sparsemap_is_set(map, 8192));
sparsemap_unset(map, 1);
sparsemap_unset(map, 8192);
sparsemap_set(map, 1, false);
sparsemap_set(map, 8192, false);
assert_false(sparsemap_is_set(map, 1));
assert_false(sparsemap_is_set(map, 8192));
@ -480,7 +456,6 @@ test_api_get_size_setup(const MunitParameter params[], void *user_data)
sparsemap_init(map, buf, 1024);
populate_map(map, 1024, 3 * 1024);
populate_map_rle(map, 3 * 1024, 5, 4096);
return (void *)map;
}
@ -537,22 +512,18 @@ test_api_count(const MunitParameter params[], void *data)
assert_true(sparsemap_count(map) == 1024);
sparsemap_clear(map);
sparsemap_set(map, 0);
sparsemap_set(map, 0, true);
assert_true(sparsemap_count(map) == 1);
sparsemap_set(map, 8675309);
sparsemap_set(map, 8675309, true);
assert_true(sparsemap_count(map) == 2);
sparsemap_clear(map);
for (int i = 0; i < 512; i++) {
sparsemap_set(map, i + 13);
sparsemap_set(map, i + 13, true);
}
assert_true(sparsemap_count(map) == 512);
sparsemap_clear(map);
size_t n = populate_map_rle(map, 3 * 1024, 7, 4001);
assert_true(sparsemap_count(map) == n);
sparsemap_clear(map);
assert_true(sparsemap_count(map) == 0);
@ -579,7 +550,7 @@ test_api_get_data(const MunitParameter params[], void *data)
}
static void *
test_api_get_start_offset_setup(const MunitParameter params[], void *user_data)
test_api_get_starting_offset_setup(const MunitParameter params[], void *user_data)
{
uint8_t *buf = munit_calloc(1024, sizeof(uint8_t));
assert_ptr_not_null(buf);
@ -590,7 +561,7 @@ test_api_get_start_offset_setup(const MunitParameter params[], void *user_data)
return (void *)map;
}
static void
test_api_get_start_offset_tear_down(void *fixture)
test_api_get_starting_offset_tear_down(void *fixture)
{
sparsemap_t *map = (sparsemap_t *)fixture;
assert_ptr_not_null(map->m_data);
@ -598,45 +569,45 @@ test_api_get_start_offset_tear_down(void *fixture)
test_api_tear_down(fixture);
}
static MunitResult
test_api_get_start_offset(const MunitParameter params[], void *data)
test_api_get_starting_offset(const MunitParameter params[], void *data)
{
sparsemap_t *map = (sparsemap_t *)data;
(void)params;
assert_ptr_not_null(map);
sparsemap_set(map, 0);
sparsemap_set(map, 0, true);
assert_true(sparsemap_get_starting_offset(map) == 0);
sparsemap_clear(map);
sparsemap_set(map, 1);
sparsemap_set(map, 1, true);
assert_true(sparsemap_get_starting_offset(map) == 1);
sparsemap_clear(map);
sparsemap_set(map, 1025);
sparsemap_set(map, 1025, true);
assert_true(sparsemap_get_starting_offset(map) == 1025);
sparsemap_clear(map);
for (int i = 0; i < 1000; i++) {
sparsemap_set(map, i);
sparsemap_set(map, i, true);
}
assert_true(sparsemap_get_starting_offset(map) == 0);
sparsemap_clear(map);
for (int i = 0; i < 1000; i++) {
sparsemap_set(map, i + 1024);
sparsemap_set(map, i + 1024, true);
}
assert_true(sparsemap_get_starting_offset(map) == 1024);
sparsemap_clear(map);
sparsemap_set(map, 13012);
sparsemap_set(map, 13012, true);
assert_true(sparsemap_get_starting_offset(map) == 13012);
return MUNIT_OK;
}
static void *
test_api_get_end_offset_setup(const MunitParameter params[], void *user_data)
test_api_get_ending_offset_setup(const MunitParameter params[], void *user_data)
{
uint8_t *buf = munit_calloc(1024, sizeof(uint8_t));
assert_ptr_not_null(buf);
@ -647,7 +618,7 @@ test_api_get_end_offset_setup(const MunitParameter params[], void *user_data)
return (void *)map;
}
static void
test_api_get_end_offset_tear_down(void *fixture)
test_api_get_ending_offset_tear_down(void *fixture)
{
sparsemap_t *map = (sparsemap_t *)fixture;
assert_ptr_not_null(map->m_data);
@ -655,44 +626,34 @@ test_api_get_end_offset_tear_down(void *fixture)
test_api_tear_down(fixture);
}
static MunitResult
test_api_get_end_offset(const MunitParameter params[], void *data)
test_api_get_ending_offset(const MunitParameter params[], void *data)
{
sparsemap_t *map = (sparsemap_t *)data;
(void)params;
assert_ptr_not_null(map);
sparsemap_set(map, 0);
sparsemap_set(map, 0, true);
assert_true(sparsemap_get_ending_offset(map) == 0);
sparsemap_clear(map);
sparsemap_set(map, 0);
sparsemap_set(map, 1);
sparsemap_set(map, 0, true);
sparsemap_set(map, 1, true);
assert_true(sparsemap_get_ending_offset(map) == 1);
sparsemap_clear(map);
sparsemap_set(map, 0);
sparsemap_set(map, 67);
sparsemap_set(map, 1002);
sparsemap_set(map, 3087);
sparsemap_set(map, 13012);
sparsemap_set(map, 0, true);
sparsemap_set(map, 67, true);
sparsemap_set(map, 1002, true);
sparsemap_set(map, 3087, true);
sparsemap_set(map, 13012, true);
assert_true(sparsemap_get_ending_offset(map) == 13012);
sparsemap_clear(map);
size_t n = populate_map_rle(map, 13012, 10, 2718);
size_t exp = n + 13012 - 1;
size_t eoff = sparsemap_get_ending_offset(map);
assert_true(sparsemap_get_ending_offset(map) == 13012 + n - 1);
// fprintf(stdout, "\n%s\n", QCC_showSparsemap(map, 0));
sparsemap_set(map, 13012 + n + 100);
// fprintf(stdout, "\n%s\n", QCC_showSparsemap(map, 0));
assert_true(sparsemap_get_ending_offset(map) == 13112 + n);
return MUNIT_OK;
}
static void *
test_api_get_start_offset_roll_setup(const MunitParameter params[], void *user_data)
test_api_get_starting_offset_rolling_setup(const MunitParameter params[], void *user_data)
{
(void)params;
(void)user_data;
@ -701,27 +662,24 @@ test_api_get_start_offset_roll_setup(const MunitParameter params[], void *user_d
return (void *)map;
}
static void
test_api_get_start_offset_roll_tear_down(void *fixture)
test_api_get_starting_offset_rolling_tear_down(void *fixture)
{
sparsemap_t *map = (sparsemap_t *)fixture;
assert_ptr_not_null(map);
munit_free(map);
}
static MunitResult
test_api_get_start_offset_roll(const MunitParameter params[], void *data)
test_api_get_starting_offset_rolling(const MunitParameter params[], void *data)
{
sparsemap_t *map = (sparsemap_t *)data;
(void)params;
for (sparsemap_idx_t i = 0; i < 10 * 2048; i++) {
sparsemap_set(map, i);
sparsemap_set(map, i, true);
if (i > 2047) {
sparsemap_unset(map, i - 2048);
// if (sparsemap_get_starting_offset(map) != i - 2047) {
// fprintf(stdout, "\n%s\n", QCC_showSparsemap(map, 0));
// fprintf(stdout, "%ld\t%ld\t%zu\n", i, i - 2047, sparsemap_get_starting_offset(map));
// }
sparsemap_set(map, i - 2048, false);
assert_true(sparsemap_get_starting_offset(map) == i - 2047);
// printf("%d\t%d\t%zu\n", i, i - 2047, sparsemap_get_starting_offset(map));
}
}
return MUNIT_OK;
@ -745,7 +703,7 @@ test_api_scan_tear_down(void *fixture)
test_api_tear_down(fixture);
}
void
scan_for_0xfeedfacebadcoffee(uint32_t v[], size_t n, void *aux)
scan_for_0xfeedfacebadcoffee(sm_idx_t v[], size_t n, void *aux)
{
size_t bit_pos[] = { 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34, 35, 38, 39, 41, 43, 44, 45, 46, 47, 48, 50, 51,
53, 54, 55, 57, 58, 59, 60, 61, 62, 63 };
@ -789,7 +747,6 @@ test_api_split_tear_down(void *fixture)
static MunitResult
test_api_split(const MunitParameter params[], void *data)
{
sparsemap_idx_t offset;
sparsemap_t *map = (sparsemap_t *)data;
uint8_t buf[1024] = { 0 };
sparsemap_t portion;
@ -799,33 +756,11 @@ test_api_split(const MunitParameter params[], void *data)
sparsemap_init(&portion, buf, 1024);
size_t amt = populate_map_rle(map, 0, 7, 8178);
for (sparsemap_idx_t i = 0; i < amt + 2049; i++) {
sparsemap_clear(&portion);
size_t rank = sparsemap_rank(map, 0, i, true);
offset = sparsemap_split(map, i + 1, &portion);
if (sparsemap_count(map) != rank) {
fprintf(stdout, "exp: %lu\tgot: %lu", rank, sparsemap_count(map));
}
assert_true(sparsemap_count(map) == rank);
if (sparsemap_count(&portion) != amt - rank) {
fprintf(stdout, "exp: %lu\tgot: %lu", amt - rank, sparsemap_count(&portion));
}
assert_true(sparsemap_count(&portion) == amt - rank);
sparsemap_merge(map, &portion);
if (*(uint32_t *)map->m_data != 1) {
fprintf(stdout, "yikes");
}
}
sparsemap_clear(map);
sparsemap_clear(&portion);
for (sparsemap_idx_t off = 0; off < 1024; off++) {
for (sparsemap_idx_t seg = 0; seg < 10 * 1024; seg += 1024) {
for (sparsemap_idx_t i = 0; i < 1024; i++) {
assert_true(sparsemap_set(map, i + seg) == i + seg);
assert_true(sparsemap_set(map, i + seg, true) == i + seg);
}
for (sparsemap_idx_t i = 0; i < 1024; i++) {
assert_true(sparsemap_is_set(map, i + seg));
@ -849,20 +784,20 @@ test_api_split(const MunitParameter params[], void *data)
}
for (sparsemap_idx_t i = 0; i < 100; i++) {
assert_true(sparsemap_set(map, i) == i);
assert_true(sparsemap_set(map, i, true) == i);
}
for (sparsemap_idx_t i = 0; i < 100; i++) {
assert_true(sparsemap_is_set(map, i));
assert_false(sparsemap_is_set(&portion, i));
}
offset = sparsemap_split(map, SPARSEMAP_IDX_MAX, &portion);
sparsemap_idx_t offset = sparsemap_split(map, SPARSEMAP_IDX_MAX, &portion);
for (sparsemap_idx_t i = 0; i < offset; i++) {
for (size_t i = 0; i < offset; i++) {
assert_true(sparsemap_is_set(map, i));
assert_false(sparsemap_is_set(&portion, i));
}
for (sparsemap_idx_t i = offset + 1; i < sparsemap_get_ending_offset(&portion); i++) {
for (int i = offset; i < 100; i++) {
assert_false(sparsemap_is_set(map, i));
assert_true(sparsemap_is_set(&portion, i));
}
@ -872,14 +807,10 @@ test_api_split(const MunitParameter params[], void *data)
sparsemap_init(&portion, buf, 1024);
for (sparsemap_idx_t i = 0; i < 13; i++) {
assert_true(sparsemap_set(map, i + 24) == i + 24);
assert_true(sparsemap_set(map, i + 24, true) == i + 24);
}
offset = sparsemap_split(map, SPARSEMAP_IDX_MAX, &portion);
assert_true(sparsemap_get_ending_offset(map) < offset);
assert_true(sparsemap_get_starting_offset(&portion) >= offset);
assert_true(sparsemap_count(map) == 6);
assert_true(sparsemap_count(&portion) == 7);
for (sparsemap_idx_t i = 0; i < offset - 24; i++) {
assert_true(sparsemap_is_set(map, i + 24));
@ -923,7 +854,7 @@ test_api_merge(const MunitParameter params[], void *data)
sparsemap_merge(map, other);
// Merge a single set bit in the first chunk into the empty map.
sparsemap_set(other, 0);
sparsemap_set(other, 0, true);
sparsemap_merge(map, other);
assert_true(sparsemap_is_set(other, 0));
assert_true(sparsemap_is_set(map, 0));
@ -931,32 +862,32 @@ test_api_merge(const MunitParameter params[], void *data)
sparsemap_clear(other);
// Merge two maps with the same single bit set.
sparsemap_set(map, 0);
sparsemap_set(other, 0);
sparsemap_set(map, 0, true);
sparsemap_set(other, 0, true);
sparsemap_merge(map, other);
assert_true(sparsemap_is_set(map, 0));
sparsemap_clear(map);
sparsemap_clear(other);
// Merge an empty map with one that has the first bit set.
sparsemap_set(map, 0);
sparsemap_set(map, 0, true);
sparsemap_merge(map, other);
assert_true(sparsemap_is_set(map, 0));
sparsemap_clear(map);
sparsemap_clear(other);
sparsemap_set(other, 2049);
sparsemap_set(other, 2049, true);
sparsemap_merge(map, other);
assert_true(sparsemap_is_set(map, 2049));
sparsemap_clear(map);
sparsemap_clear(other);
sparsemap_set(other, 1);
sparsemap_set(other, 2049);
sparsemap_set(map, 2050);
sparsemap_set(other, 4097);
sparsemap_set(map, 6113);
sparsemap_set(other, 8193);
sparsemap_set(other, 1, true);
sparsemap_set(other, 2049, true);
sparsemap_set(map, 2050, true);
sparsemap_set(other, 4097, true);
sparsemap_set(map, 6113, true);
sparsemap_set(other, 8193, true);
sparsemap_merge(map, other);
assert_true(sparsemap_is_set(map, 1));
assert_true(sparsemap_is_set(map, 2049));
@ -973,11 +904,11 @@ test_api_merge(const MunitParameter params[], void *data)
sparsemap_clear(map);
sparsemap_clear(other);
sparsemap_set(map, 0);
sparsemap_set(map, 2048);
sparsemap_set(map, 8193);
sparsemap_set(map, 0, true);
sparsemap_set(map, 2048, true);
sparsemap_set(map, 8193, true);
for (int i = 2049; i < 4096; i++) {
sparsemap_set(other, i);
sparsemap_set(other, i, true);
}
sparsemap_merge(map, other);
assert(sparsemap_is_set(map, 0));
@ -990,7 +921,7 @@ test_api_merge(const MunitParameter params[], void *data)
sparsemap_clear(other);
for (int i = 2049; i < 4096; i++) {
sparsemap_set(map, i);
sparsemap_set(map, i, true);
}
sparsemap_split(map, 2051, other);
for (int i = 2049; i < 4096; i++) {
@ -1117,9 +1048,9 @@ test_api_select_neg(const MunitParameter params[], void *data)
assert_ptr_not_null(map);
sparsemap_set(map, 42);
sparsemap_set(map, 420);
sparsemap_set(map, 4200);
sparsemap_set(map, 42, true);
sparsemap_set(map, 420, true);
sparsemap_set(map, 4200, true);
f = sparsemap_select(map, 0, false);
assert_true(f == 0);
@ -1164,7 +1095,7 @@ test_api_rank_true(const MunitParameter params[], void *data)
assert_ptr_not_null(map);
for (int i = 0; i < 10; i++) {
sparsemap_set(map, i);
sparsemap_set(map, i, true);
}
/* rank() is also 0-based, for consistency (and confusion sake); consider the
range as [start, end] of [0, 9] counts the bits set in the first 10
@ -1178,23 +1109,14 @@ test_api_rank_true(const MunitParameter params[], void *data)
sparsemap_clear(map);
for (int i = 0; i < 10000; i++) {
sparsemap_set(map, i);
sparsemap_set(map, i, true);
}
// TODO: separate test for slicing a run within the chunk size of the end of the run
// sparsemap_unset(map, 9990);
// sparsemap_set(map, 9990);
sparsemap_idx_t hole = 4999;
sparsemap_unset(map, hole);
sparsemap_set(map, hole, false);
for (size_t i = 0; i < 10000; i++) {
for (size_t j = i; j < 10000; j++) {
size_t amt = (i > j) ? 0 : j - i + 1 - ((hole >= i && j >= hole) ? 1 : 0);
size_t r = sparsemap_rank(map, i, j, true);
// if (r != amt) {
// fprintf(stdout, "\n%s\n", QCC_showSparsemap(map, 0));
// sparsemap_rank(map, i, j, true);
// }
assert_true(r == amt);
}
}
@ -1224,7 +1146,7 @@ test_api_rank_false_tear_down(void *fixture)
static MunitResult
test_api_rank_false(const MunitParameter params[], void *data)
{
size_t r;
int r;
sparsemap_t *map = (sparsemap_t *)data;
(void)params;
@ -1240,36 +1162,18 @@ test_api_rank_false(const MunitParameter params[], void *data)
// One chunk means not so empty now!
sparsemap_idx_t hole = 4999;
sparsemap_set(map, hole);
sparsemap_set(map, hole, true);
for (size_t i = 0; i < 10000; i++) {
for (size_t j = i; j < 10000; j++) {
size_t amt = (i > j) ? 0 : j - i + 1 - ((hole >= i && j >= hole) ? 1 : 0);
int amt = (i > j) ? 0 : j - i + 1 - ((hole >= i && j >= hole) ? 1 : 0);
r = sparsemap_rank(map, i, j, false);
assert_true(r == amt);
}
}
// RLE
for (size_t i = 0; i < 10000; i++) {
sparsemap_set(map, i);
}
r = sparsemap_rank(map, 9990, 10010, false);
// if (r != 10) {
// fprintf(stdout, "\n%s\n", QCC_showSparsemap(map, 0));
// sparsemap_rank(map, 9990, 10010, true);
// }
assert_true(r == 10);
r = sparsemap_rank(map, 9990, 4294967295, false);
// if (r != 4294957295) {
// fprintf(stdout, "\n%s\n", QCC_showSparsemap(map, 0));
// sparsemap_rank(map, 9990, 4294967295, true);
// }
assert_true(r == 4294957295);
sparsemap_clear(map);
sparsemap_set(map, 1);
sparsemap_set(map, 11);
sparsemap_set(map, 1, true);
sparsemap_set(map, 11, true);
r = sparsemap_rank(map, 0, 11, false);
assert_true(r == 10);
@ -1342,9 +1246,9 @@ static MunitTest api_test_suite[] = {
{ (char *)"/get_size", test_api_get_size, test_api_get_size_setup, test_api_get_size_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/count", test_api_count, test_api_count_setup, test_api_count_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/get_data", test_api_get_data, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/get_start_offset", test_api_get_start_offset, test_api_get_start_offset_setup, test_api_get_start_offset_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/get_start_offset/roll", test_api_get_start_offset_roll, test_api_get_start_offset_roll_setup, test_api_get_start_offset_roll_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/get_end_offset", test_api_get_end_offset, test_api_get_end_offset_setup, test_api_get_end_offset_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/get_starting_offset", test_api_get_starting_offset, test_api_get_starting_offset_setup, test_api_get_starting_offset_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/get_starting_offset/rolling", test_api_get_starting_offset_rolling, test_api_get_starting_offset_rolling_setup, test_api_get_starting_offset_rolling_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/get_ending_offset", test_api_get_ending_offset, test_api_get_ending_offset_setup, test_api_get_ending_offset_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/scan", test_api_scan, test_api_scan_setup, test_api_scan_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/split", test_api_split, test_api_split_setup, test_api_split_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/merge", test_api_merge, test_api_merge_setup, test_api_merge_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
@ -1362,61 +1266,6 @@ static MunitTest api_test_suite[] = {
};
// clang-format on
/* -------------------------- Quickcheck, Property Based Tests */
extern QCC_GenValue *QCC_genChunk();
extern QCC_GenValue *QCC_genSparsemap();
extern QCC_TestStatus _tst_chunk_calc_vector_size_equality(QCC_GenValue **vals, int len, QCC_Stamp **stamp);
extern QCC_TestStatus _tst_chunk_get_position(QCC_GenValue **vals, int len, QCC_Stamp **stamp);
extern QCC_TestStatus _tst_chunk_get_capacity(QCC_GenValue **vals, int len, QCC_Stamp **stamp);
extern QCC_TestStatus _tst_get_chunk_offset(QCC_GenValue **vals, int len, QCC_Stamp **stamp);
static MunitResult
qc__sm_chunk_calc_vector_size(const MunitParameter params[], void *data)
{
(void)params;
(void)data;
return QCC_testForAll(1000, 1000, _tst_chunk_calc_vector_size_equality, 1, QCC_genInt);
}
static MunitResult
qc__sm_chunk_get_position(const MunitParameter params[], void *data)
{
(void)params;
(void)data;
return QCC_testForAll(100, 1000, _tst_chunk_get_position, 1, QCC_genChunk);
}
static MunitResult
qc__sm_chunk_get_capacity(const MunitParameter params[], void *data)
{
(void)params;
(void)data;
return QCC_testForAll(100, 1000, _tst_chunk_get_capacity, 1, QCC_genChunk);
}
static MunitResult
qc__sm_get_chunk_offset(const MunitParameter params[], void *data)
{
(void)params;
(void)data;
return QCC_testForAll(100, 1000, _tst_get_chunk_offset, 2, QCC_genInt, QCC_genSparsemap);
}
// clang-format off
static MunitTest qc_test_suite[] = {
{ (char *)"/__sm_chunk_calc_vector_size", qc__sm_chunk_calc_vector_size, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/__sm_chunk_get_position", qc__sm_chunk_get_position, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/__sm_chunk_get_capacity", qc__sm_chunk_get_capacity, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/__sm_get_chunk_offset", qc__sm_get_chunk_offset, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
{ NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL }
};
// clang-format off
/* -------------------------- Scale Tests */
static void *
@ -1558,7 +1407,7 @@ test_scale_alternating(const MunitParameter params[], void *data)
for (sparsemap_idx_t i = 0; i < (1000 * 8192); i++) {
if (i % 2) {
if (sparsemap_set(map, i) != i) {
if (sparsemap_set(map, i, true) != i) {
// printf("%zu\n", i);
break;
}
@ -1614,7 +1463,7 @@ test_scale_spans_come_spans_go(const MunitParameter params[], void *data)
assert_true(sparsemap_is_set(map, j) == true);
}
for (int j = b; j < s; j++) {
sparsemap_unset(map, j);
sparsemap_set(map, j, false);
}
for (int j = b; j < s; j++) {
assert_true(sparsemap_is_set(map, j) == false);
@ -1666,7 +1515,7 @@ test_scale_best_case(const MunitParameter params[], void *data)
for (int i = 0; i < 172032; i++) {
/* ANSI esc code to clear line, carrage return, then print on the same line */
// printf("\033[2K\r%d", i);
sparsemap_set(map, i);
sparsemap_set(map, i, true);
}
return MUNIT_OK;
@ -1710,7 +1559,7 @@ test_scale_worst_case(const MunitParameter params[], void *data)
for (int i = 0; i < 7744; i += 2) {
/* ANSI esc code to clear line, carrage return, then print on the same line */
// printf("\033[2K\r%d", i);
sparsemap_set(map, i);
sparsemap_set(map, i, true);
}
return MUNIT_OK;
@ -1831,7 +1680,6 @@ static MunitTest perf_test_suite[] = {
// clang-format off
static MunitSuite other_test_suite[] = {
{ "/api", api_test_suite, NULL, 1, MUNIT_SUITE_OPTION_NONE },
{ "/qc", qc_test_suite, NULL, 1, MUNIT_SUITE_OPTION_NONE },
{ "/perf", perf_test_suite, NULL, 1, MUNIT_SUITE_OPTION_NONE },
{ "/scale", scale_test_suite, NULL, 1, MUNIT_SUITE_OPTION_NONE },
{ NULL, NULL, NULL, 0, MUNIT_SUITE_OPTION_NONE } };
@ -1843,7 +1691,7 @@ static MunitTest sparsemap_test_suite[] = {
};
// clang-format on
static const MunitSuite main_test_suite = { (char *)"", sparsemap_test_suite, other_test_suite, 1, MUNIT_SUITE_OPTION_NONE };
static const MunitSuite main_test_suite = { (char *)"/sparsemap", sparsemap_test_suite, other_test_suite, 1, MUNIT_SUITE_OPTION_NONE };
int
main(int argc, char *argv[MUNIT_ARRAY_PARAM(argc + 1)])
@ -1854,8 +1702,6 @@ main(int argc, char *argv[MUNIT_ARRAY_PARAM(argc + 1)])
setvbuf(stdout, NULL, _IONBF, 0);
setvbuf(stderr, NULL, _IONBF, 0);
QCC_init(0);
return munit_suite_main(&main_test_suite, (void *)&info, argc, argv);
}