Compare commits
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
|
|
@ -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,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
15
.idea/customTargets.xml
Normal 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
25
.idea/makefile.xml
Normal 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>
|
||||
|
|
@ -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>
|
||||
|
|
@ -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
106
Makefile
Normal 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
|
||||
113
README.md
113
README.md
|
|
@ -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
|
||||
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
|
||||
|
||||
|
|
|
|||
|
|
@ -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()
|
||||
|
|
@ -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);
|
||||
|
|
@ -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;
|
||||
}
|
||||
|
|
@ -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;
|
||||
|
|
@ -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);
|
||||
|
|
@ -1,5 +1,5 @@
|
|||
|
||||
#include <sparsemap.h>
|
||||
#include "../include/sparsemap.h"
|
||||
|
||||
#pragma GCC diagnostic push
|
||||
#pragma GCC diagnostic ignored "-Wvariadic-macros"
|
||||
|
|
@ -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.
|
||||
*
|
||||
|
|
@ -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?
|
||||
}
|
||||
}
|
||||
3389
sparsemap.c
3389
sparsemap.c
File diff suppressed because it is too large
Load diff
1882
src/sparsemap.c
Normal file
1882
src/sparsemap.c
Normal file
File diff suppressed because it is too large
Load diff
831
test/qc.c
831
test/qc.c
|
|
@ -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
284
test/qc.h
|
|
@ -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
|
||||
|
|
@ -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;
|
||||
|
|
@ -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);
|
||||
}
|
||||
|
||||
Loading…
Reference in a new issue