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

Compare commits

base: greg:gburd/lock-free
Branches Tags
greg:main
greg:gburd/splay-list
greg:gburd/lock-free
..
compare: greg:main
Branches Tags
greg:gburd/splay-list
greg:main
greg:gburd/lock-free

4 commits
gburd/lock ... main

Author SHA1 Message Date
Greg Burd
a709e68037 update flake 2024-05-03 09:42:37 -04:00
Greg Burd
3a28a0fb4d Fixes 2024-04-08 11:18:36 -04:00
Greg Burd
28db528869 move re-balancing work to branch 2024-04-08 09:28:52 -04:00
Greg Burd
0275f505fc cleanup 2024-04-08 09:24:00 -04:00
21 changed files with 296 additions and 4017 deletions
Show stats Expand all files Collapse all files

20
.gdbinit
View file

@ -1,20 +0,0 @@
cd ./build/src/json/tests
file ./iwjsreg_test1
#set args -c
set confirm off
set follow-fork-mode parent
set detach-on-fork on
set print elements 4096
define lb
set breakpoint pending on
source .breakpoints
set breakpoint pending auto
echo breakpoints loaded\n
end
define sb
save breakpoints .breakpoints
echo breakpoints saved\n
end

4
.gitignore vendored
View file

@ -2,7 +2,9 @@ libskiplist.a
libskiplist.so
**/*.o
tests/test
examples/mls*
examples/mls.c
examples/mls
examples/mls.o
/mxe
.cache
hints.txt

8
.idea/.gitignore vendored
View file

@ -1,8 +0,0 @@
# Default ignored files
/shelf/
/workspace.xml
# Editor-based HTTP Client requests
/httpRequests/
# Datasource local storage ignored files
/dataSources/
/dataSources.local.xml

7
.idea/codeStyles/Project.xml
View file

@ -1,7 +0,0 @@
<component name="ProjectCodeStyleConfiguration">
<code_scheme name="Project" version="173">
<clangFormatSettings>
<option name="ENABLED" value="true" />
</clangFormatSettings>
</code_scheme>
</component>

5
.idea/codeStyles/codeStyleConfig.xml
View file

@ -1,5 +0,0 @@
<component name="ProjectCodeStyleConfiguration">
<state>
<option name="USE_PER_PROJECT_SETTINGS" value="true" />
</state>
</component>

7
.idea/inspectionProfiles/Project_Default.xml
View file

@ -1,7 +0,0 @@
<component name="InspectionProjectProfileManager">
<profile version="1.0">
<option name="myName" value="Project Default" />
<inspection_tool class="Eslint" enabled="true" level="WARNING" enabled_by_default="true" />
<inspection_tool class="TsLint" enabled="true" level="WARNING" enabled_by_default="true" />
</profile>
</component>

29
.idea/misc.xml
View file

@ -1,29 +0,0 @@
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
<component name="CidrRootsConfiguration">
<sourceRoots>
<file path="$PROJECT_DIR$/examples" />
<file path="$PROJECT_DIR$/include" />
<file path="$PROJECT_DIR$/src" />
<file path="$PROJECT_DIR$/tests" />
</sourceRoots>
</component>
<component name="ExternalStorageConfigurationManager" enabled="true" />
<component name="MakefileSettings">
<option name="linkedExternalProjectsSettings">
<MakefileProjectSettings>
<option name="buildDirectory" value="" />
<option name="buildOptions" value="Makefile" />
<option name="buildSystemName" value="GNU Autotools" />
<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>

6
.idea/vcs.xml
View file

@ -1,6 +0,0 @@
<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
<component name="VcsDirectoryMappings">
<mapping directory="" vcs="Git" />
</component>
</project>

0
ChangeLog
View file

24
Makefile
View file

@ -1,7 +1,7 @@
OBJS = skiplist.o
STATIC_LIB = libskiplist.a
SHARED_LIB = libskiplist.so
OBJS =
STATIC_LIB =
SHARED_LIB =
# https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
#CFLAGS = -Wall -Wextra -Wpedantic -Of -std=c99 -Iinclude/ -fPIC
@ -14,7 +14,7 @@ TEST_FLAGS = -Itests/
TESTS = tests/test
TEST_OBJS = tests/test.o tests/munit.o
EXAMPLES = examples/skip examples/slm
EXAMPLES = examples/ex1.c
.PHONY: all shared static clean test examples mls
@ -45,6 +45,7 @@ clean:
rm -f $(OBJS) munit.o test.o
rm -f examples/mls.c
rm -f $(STATIC_LIB)
rm -f $(SHARED_LIB)
rm -f $(TESTS)
rm -f $(EXAMPLES)
@ -60,14 +61,19 @@ tests/%.o: tests/%.c
examples/%.o: examples/%.c
$(CC) $(CFLAGS) -c -o $@ $^
examples/mls.c: examples/slm.c
$(CC) $(CFLAGS) -C -E examples/slm.c | sed -e '1,7d' -e '/^# [0-9]* "/d' | clang-format > examples/mls.c
# $(CC) $(CFLAGS) -C -E examples/slm.c | sed -e '1,7d' -e 's/^#\( [0-9]* ".*$$\)/\/\* \1 \*\//' | clang-format > examples/mls.c
examples/mls.c: examples/ex1.c
$(CC) $(CFLAGS) -C -E examples/ex1.c | sed -e '1,7d' -e '/^# [0-9]* "/d' | clang-format > examples/mls.c
examples/mls: examples/mls.o $(STATIC_LIB)
$(CC) $^ -o $@ $(CFLAGS) $(TEST_FLAGS) -lm -pthread
#dot:
# ./examples/mls
# dot -Tpdf /tmp/slm.dot -o /tmp/slm.pdf >/dev/null 2>&1
# dot -Tpdf /tmp/ex1.dot -o /tmp/ex1.pdf >/dev/null 2>&1
#re-write CPP line information comments, but keep them
# $(CC) $(CFLAGS) -C -E examples/ex1.c | sed -e '1,7d' -e 's/^#\( [0-9]* ".*$$\)/\/\* \1 \*\//' | clang-format > examples/mls.c
# workflow:
# clear; rm examples/mls.c; make examples/mls && env ASAN_OPTIONS=detect_leaks=1 LSAN_OPTIONS=verbosity=1:log_threads=1 ./examples/mls #&& dot -Tpdf /tmp/ex1.dot -o /tmp/ex1.pdf
# cp include/sl.h /tmp/foo; clang-format -i include/sl.h

145
README.md
View file

@ -1,8 +1,141 @@
# skiplist
# Skiplist
Concurrent, lock-free Skip List in ANSI C99.
This project defines [a skiplist data structure written in
C](https://git.burd.me/greg/skiplist/src/branch/main/include/sl.h). Implemented
as using macros this code provides a way to essentially "template" (as in C++)
and emit code with types and functions specific to your use case. You can apply
these macros multiple times safely in your code, once for each application.
* Portions of this code are derived from work copyrighted by Jung-Sang Ahn
* 2017-2024 Jung-Sang Ahn <jungsang.ahn@gmail.com> and made available under the
* MIT License. (see: https://github.com/greensky00 Skiplist version: 0.2.9)
*
While there are lock-free implementations of a skiplist, this implementation is
not (yet) lock-free or designed to manage concurrent access in any way. Use a
mutex or some other method to serialize access to the API ([until I finish the
lock-free
variant](https://git.burd.me/greg/skiplist/src/branch/gburd/lock-free)).
Study the [example
code](https://git.burd.me/greg/skiplist/src/branch/main/examples/ex1.c) to see
how this works in practice.
## Overview
A skiplist is a sorted list with O(log(n)) on average for most operations. It
is a probabilistic datastructure, meaning that it does not guarantee O(log(n))
it approximates it over time. This implementation includes improves the
probability by integrating the splay list algorithm for re-balancing trading off
a bit of computational overhead and code complexity for a nearly always optimal,
or "perfect" skiplist.
Conceptually, the arrangement of a skiplist appears as follows:
```
<head> ----------> [2] --------------------------------------------------> [9] ---------->
<head> ----------> [2] ------------------------------------[7] ----------> [9] ---------->
<head> ----------> [2] ----------> [4] ------------------> [7] ----------> [9] --> [10] ->
<head> --> [1] --> [2] --> [3] --> [4] --> [5] --> [6] --> [7] --> [8] --> [9] --> [10] ->
```
Each node contains at the very least a link to the next element in the list
(corresponding to the lowest level in the above diagram), but it can randomly
contain more links which skip further down the list (the towers in the above
diagram). This allows for the algorithm to move down the list faster than
having to visit every element.
Conceptually, the skiplist can be thought of as a stack of linked lists. At
the very bottom is the full linked list with every element, and each layer
above corresponds to a linked list containing a random subset of the elements
from the layer immediately below it. The probability distribution that
determines this random subset can be customized, but typically a layer will
contain half the nodes from the layer below.
This implementation maintains a doubly-linked list at the bottom layer to
support efficient iteration in either direction. There is also a guard
node at the tail rather than simply pointing to NULL.
```
<head> <-> [1] <-> [2] <-> [3] <-> [4] <-> [5] <-> [6] <-> [7] <-> <tail>
```
## Safety:
The ordered skiplist relies on a well-behaved comparison
function. Specifically, given some ordering function f(a, b), it must satisfy
the following properties:
1) Be well-defined: f(a, b) should always return the same value
2) Be antisymmetric: f(a, b) == Greater if and only if f(b, a) == Less, and
f(a, b) == Equal == f(b, a).
3) Be transitive: If f(a, b) == Greater and f(b, c) == Greater than f(a, c)
== Greater.
Failure to satisfy these properties can result in unexpected behavior at
best, and at worst will cause a segfault, null deref, or some other bad
behavior.
## References:
Sources of information most helpful for this implementation include, but are
not limited to:
- Skip lists: a probabilistic alternative to balanced trees
```@article{10.1145/78973.78977,
author = {Pugh, William},
title = {Skip lists: a probabilistic alternative to balanced trees},
year = {1990}, issue_date = {June 1990},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {33}, number = {6}, issn = {0001-0782},
url = {https://doi.org/10.1145/78973.78977},
doi = {10.1145/78973.78977},
journal = {Commun. ACM}, month = {jun}, pages = {668-676}, numpages = {9},
keywords = {trees, searching, data structures},
download = {https://www.cl.cam.ac.uk/teaching/2005/Algorithms/skiplists.pdf}
}```
- Tutorial: The Ubiquitous Skiplist, its Variants, and Applications in Modern Big Data Systems
```@article{Vadrevu2023TutorialTU,
title={Tutorial: The Ubiquitous Skiplist, its Variants, and Applications in Modern Big Data Systems},
author={Venkata Sai Pavan Kumar Vadrevu and Lu Xing and Walid G. Aref},
journal={ArXiv},
year={2023},
volume={abs/2304.09983},
url={https://api.semanticscholar.org/CorpusID:258236678},
download={https://arxiv.org/pdf/2304.09983.pdf}
}```
- The Splay-List: A Distribution-Adaptive Concurrent Skip-List
```@misc{aksenov2020splaylist,
title={The Splay-List: A Distribution-Adaptive Concurrent Skip-List},
author={Vitaly Aksenov and Dan Alistarh and Alexandra Drozdova and Amirkeivan Mohtashami},
year={2020},
eprint={2008.01009},
archivePrefix={arXiv},
primaryClass={cs.DC},
download={https://arxiv.org/pdf/2008.01009.pdf}
}```
- JellyFish: A Fast Skip List with MVCC},
```@article{Yeon2020JellyFishAF,
title={JellyFish: A Fast Skip List with MVCC},
author={Jeseong Yeon and Leeju Kim and Youil Han and Hyeon Gyu Lee and Eunji Lee and Bryan Suk Joon Kim},
journal={Proceedings of the 21st International Middleware Conference},
year={2020},
url={https://api.semanticscholar.org/CorpusID:228086012}
}```
## Open Source
I'd like to thank others for thoughtfully licensing their work, the
community of software engineers succeeds when we work together.
Portions of this code are derived from other copyrighted works:
- _MIT License_
- https://github.com/greensky00/skiplist
- 2017-2024 Jung-Sang Ahn <jungsang.ahn@gmail.com>
- https://github.com/paulross/skiplist
- Copyright (c) 2017-2023 Paul Ross <paulross@uky.edu>
- https://github.com/JP-Ellis/rust-skiplist
- Copyright (c) 2015 Joshua Ellis <github@jpellis.me>
- _Public Domain_
- https://gist.github.com/zhpengg/2873424
- Zhipeng Li <zhpeng.is@gmail.com>
### TODO:
* The concurrent, lock-free version of this (see [gburd/lock-free](https://git.burd.me/greg/skiplist/src/branch/gburd/lock-free) branch for WIP).

49
examples/slm.c → examples/ex1.c
View file

@ -18,11 +18,13 @@
// Local demo application OPTIONS:
// ---------------------------------------------------------------------------
#define TEST_ARRAY_SIZE 1000
#define TEST_ARRAY_SIZE 10
#define VALIDATE
//define SNAPSHOTS
//define TODO_RESTORE_SNAPSHOTS
//define DOT
#define STABLE_SEED
#define DOT
#ifdef DOT
size_t gen = 0;
FILE *of = 0;
@ -38,8 +40,8 @@ FILE *of = 0;
/*
* SKIPLIST EXAMPLE:
*
* This example creates an "ex" (example in Italian) Skiplist where keys
* are integers, values are strings allocated on the heap.
* This example creates an "ex" Skiplist where keys are integers, values are
* strings containing the roman numeral for the key allocated on the heap.
*/
/*
@ -179,12 +181,38 @@ SKIPLIST_DECL_DOT(ex, api_, entries)
void
sprintf_ex_node(ex_node_t *node, char *buf)
{
// sprintf(buf, "%d:%s (hits: %lu)", node->key, node->value, node->entries.sle_levels[0].hits);
sprintf(buf, "%d:%s", node->key, node->value);
}
// Function for this demo application.
// ---------------------------------------------------------------------------
int __xorshift32_state = 0;
// Xorshift algorithm for PRNG
uint32_t
xorshift32()
{
uint32_t x = __xorshift32_state;
if (x == 0)
x = 123456789;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
__xorshift32_state = x;
return x;
}
void
xorshift32_seed()
{
// Seed the PRNG
#ifdef STABLE_SEED
__xorshift32_state = 8675309;
#else
__xorshift32_state = (unsigned int)time(NULL) ^ getpid();
#endif
}
static char *
to_lower(char *str)
{
@ -241,7 +269,7 @@ shuffle(int *array, size_t n)
if (n > 1) {
size_t i;
for (i = n - 1; i > 0; i--) {
size_t j = (unsigned int)(rand() % (i + 1)); /* NOLINT(*-msc50-cpp) */
size_t j = (unsigned int)(xorshift32() % (i + 1)); /* NOLINT(*-msc50-cpp) */
int t = array[j];
array[j] = array[i];
array[i] = t;
@ -267,10 +295,12 @@ main()
snap_info_t snaps[TEST_ARRAY_SIZE * 2 + 1];
#endif
xorshift32_seed();
#ifdef DOT
of = fopen("/tmp/slm.dot", "w");
of = fopen("/tmp/ex1.dot", "w");
if (!of) {
perror("Failed to open file /tmp/slm.dot");
perror("Failed to open file /tmp/ex1.dot");
return 1;
}
#endif
@ -280,6 +310,9 @@ main()
if (list == NULL)
return ENOMEM;
/* We set the max height here to 12, it's negative so that
the PRNG is seeded with this value as a testing trick for
predictable random sequences. */
rc = api_skip_init_ex(list, -12);
if (rc)
return rc;

154
examples/skip.c
View file

@ -1,154 +0,0 @@
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include "../include/skiplist.h"
// Define a node that contains key and value pair.
struct my_node {
// Metadata for skiplist node.
sl_node snode;
// My data here: {int, int} pair.
int key;
int value;
};
// Define a comparison function for `my_node`.
static int
my_cmp(sl_node *a, sl_node *b, void *aux)
{
// Get `my_node` from skiplist node `a` and `b`.
struct my_node *aa, *bb;
aa = sl_get_entry(a, struct my_node, snode);
bb = sl_get_entry(b, struct my_node, snode);
// aa < bb: return neg
// aa == bb: return 0
// aa > bb: return pos
if (aa->key < bb->key)
return -1;
if (aa->key > bb->key)
return 1;
return 0;
}
#define NUM_NODES 10000
int
main()
{
// seed the PRNG
srandom((unsigned)(time(NULL) | getpid()));
sl_raw slist;
// Initialize skiplist.
sl_init(&slist, my_cmp);
// << Insertion >>
// Allocate & insert NUM_NODES KV pairs: {0, 0}, {1, 10}, {2, 20}.
struct my_node *nodes[NUM_NODES];
for (int i = 0; i < NUM_NODES; ++i) {
// Allocate memory.
nodes[i] = (struct my_node *)malloc(sizeof(struct my_node));
// Initialize node.
sl_init_node(&nodes[i]->snode);
// Assign key and value.
nodes[i]->key = i;
nodes[i]->value = i * 10;
// Insert into skiplist.
sl_insert(&slist, &nodes[i]->snode);
}
// << Point lookup >>
for (int i = 0; i < NUM_NODES; ++i) {
// Define a query.
struct my_node query;
int min = 1, max = NUM_NODES - 1;
int k = min + (int)random() / (RAND_MAX / (max - min + 1) + 1);
query.key = k;
// Find a skiplist node `cursor`.
sl_node *cursor = sl_find(&slist, &query.snode);
// If `cursor` is NULL, key doesn't exist.
if (!cursor)
continue;
// Get `my_node` from `cursor`.
// Note: found->snode == *cursor
struct my_node *found = sl_get_entry(cursor, struct my_node, snode);
printf("[point lookup] key: %d, value: %d\n", found->key, found->value);
if (found->key != found->value / 10) {
printf("FAILURE: key: %d * 10 != value: %d\n", found->key, found->value);
exit(-1);
}
// Release `cursor` (== &found->snode).
// Other thread cannot free `cursor` until `cursor` is released.
sl_release_node(cursor);
}
// << Erase >>
// Erase the KV pair for key 1: {1, 10}.
{
// Define a query.
struct my_node query;
query.key = 1;
// Find a skiplist node `cursor`.
sl_node *cursor = sl_find(&slist, &query.snode);
// Get `my_node` from `cursor`.
// Note: found->snode == *cursor
struct my_node *found = sl_get_entry(cursor, struct my_node, snode);
printf("[erase] key: %d, value: %d\n", found->key, found->value);
// Detach `found` from skiplist.
sl_erase_node(&slist, &found->snode);
// Release `found`, to free its memory.
sl_release_node(&found->snode);
// Free `found` after it becomes safe.
sl_wait_for_free(&found->snode);
sl_free_node(&found->snode);
free(found);
}
// << Iteration >>
{
// Get the first cursor.
sl_node *cursor = sl_begin(&slist);
while (cursor) {
// Get `entry` from `cursor`.
// Note: entry->snode == *cursor
struct my_node *entry = sl_get_entry(cursor, struct my_node, snode);
printf("[iteration] key: %d, value: %d\n", entry->key, entry->value);
// Get next `cursor`.
cursor = sl_next(&slist, cursor);
// Release `entry`.
sl_release_node(&entry->snode);
}
}
// << Destroy >>
{
// Iterate and free all nodes.
sl_node *cursor = sl_begin(&slist);
while (cursor) {
struct my_node *entry = sl_get_entry(cursor, struct my_node, snode);
printf("[destroy] key: %d, value: %d\n", entry->key, entry->value);
// Get next `cursor`.
cursor = sl_next(&slist, cursor);
// Detach `entry` from skiplist.
sl_erase_node(&slist, &entry->snode);
// Release `entry`, to free its memory.
sl_release_node(&entry->snode);
// Free `entry` after it becomes safe.
sl_wait_for_free(&entry->snode);
sl_free_node(&entry->snode);
free(entry);
}
}
// Free skiplist.
sl_free(&slist);
return 0;
}

48
flake.lock
View file

@ -1,43 +1,25 @@
{
"nodes": {
"flake-utils": {
"inputs": {
"systems": "systems"
},
"locked": {
"lastModified": 1709126324,
"narHash": "sha256-q6EQdSeUZOG26WelxqkmR7kArjgWCdw5sfJVHPH/7j8=",
"owner": "numtide",
"repo": "flake-utils",
"rev": "d465f4819400de7c8d874d50b982301f28a84605",
"type": "github"
},
"original": {
"owner": "numtide",
"repo": "flake-utils",
"type": "github"
}
},
"nixpkgs": {
"locked": {
"lastModified": 1709780214,
"narHash": "sha256-p4iDKdveHMhfGAlpxmkCtfQO3WRzmlD11aIcThwPqhk=",
"lastModified": 1701282334,
"narHash": "sha256-MxCVrXY6v4QmfTwIysjjaX0XUhqBbxTWWB4HXtDYsdk=",
"owner": "NixOS",
"repo": "nixpkgs",
"rev": "f945939fd679284d736112d3d5410eb867f3b31c",
"rev": "057f9aecfb71c4437d2b27d3323df7f93c010b7e",
"type": "github"
},
"original": {
"owner": "NixOS",
"ref": "nixpkgs-unstable",
"ref": "23.11",
"repo": "nixpkgs",
"type": "github"
}
},
"root": {
"inputs": {
"flake-utils": "flake-utils",
"nixpkgs": "nixpkgs"
"nixpkgs": "nixpkgs",
"utils": "utils"
}
},
"systems": {
@ -54,6 +36,24 @@
"repo": "default",
"type": "github"
}
},
"utils": {
"inputs": {
"systems": "systems"
},
"locked": {
"lastModified": 1710146030,
"narHash": "sha256-SZ5L6eA7HJ/nmkzGG7/ISclqe6oZdOZTNoesiInkXPQ=",
"owner": "numtide",
"repo": "flake-utils",
"rev": "b1d9ab70662946ef0850d488da1c9019f3a9752a",
"type": "github"
},
"original": {
"owner": "numtide",
"repo": "flake-utils",
"type": "github"
}
}
},
"root": "root",

80
flake.nix
View file

@ -1,51 +1,55 @@
{
description = "A Concurrent Skip List library for key/value pairs.";
inputs.nixpkgs.url = "github:NixOS/nixpkgs/nixpkgs-unstable";
inputs.flake-utils.url = "github:numtide/flake-utils";
inputs = {
# nixpkgs.url = "github:NixOS/nixpkgs/nixpkgs-unstable";
nixpkgs.url = "github:NixOS/nixpkgs/23.11";
utils.url = "github:numtide/flake-utils";
};
outputs =
{ self
, nixpkgs
, flake-utils
, ...
}:
flake-utils.lib.eachDefaultSystem (system:
let
# pkgs = nixpkgs.legacyPackages.${system};
pkgs = import nixpkgs {
inherit system;
config = { allowUnfree = true; };
};
in
{
devShells.default = pkgs.mkShell {
outputs = { self, nixpkgs, ... }
@inputs: inputs.utils.lib.eachSystem [
"x86_64-linux" "i686-linux" "aarch64-linux" "x86_64-darwin"
] (system:
let pkgs = import nixpkgs {
inherit system;
overlays = [];
config.allowUnfree = true;
};
in {
flake-utils.inputs.systems.follows = "system";
devShell = pkgs.mkShell rec {
name = "skiplist";
packages = with pkgs; [
act
autoconf
bashInteractive
clang-tools
clang
ed
gcc
gdb
gettext
graphviz-nox
meson
python311Packages.rbtools
libtool
m4
perl
pkg-config
python3
ripgrep
valgrind
];
buildInputs = with pkgs; [
libbacktrace
glibc.out
glibc.static
];
shellHook = let
icon = "f121";
in ''
export PS1="$(echo -e '\u${icon}') {\[$(tput sgr0)\]\[\033[38;5;228m\]\w\[$(tput sgr0)\]\[\033[38;5;15m\]} (${name}) \\$ \[$(tput sgr0)\]"
'';
};
buildInputs = with pkgs; [
glibc
];
nativeBuildInputs = with pkgs.buildPackages; [
act
binutils
coreutils
gcc
gettext
libtool
m4
make
perl
pkg-config
ripgrep
];
DOCKER_BUILDKIT = 1;
});
}

132
include/skiplist.h
View file

@ -1,132 +0,0 @@
/**
* Copyright 2024-present Gregory Burd <greg@burd.me> All rights reserved.
*
* Portions of this code are derived from work copyrighted by Jung-Sang Ahn
* 2017-2024 Jung-Sang Ahn <jungsang.ahn@gmail.com> and made available under
* the MIT License. (see: https://github.com/greensky00 Skiplist version:
* 0.2.9)
*
* MIT License
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to
* deal in the Software without restriction, including without limitation the
* rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
* sell copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
* IN THE SOFTWARE.
*/
#ifndef SKIPLIST_H__
#define SKIPLIST_H__ (1)
#include <stddef.h>
#include <stdint.h>
#define SKIPLIST_MAX_LAYER (64)
#define _STL_ATOMIC (1)
#ifdef __APPLE__
#define _STL_ATOMIC (1)
#endif
typedef struct _sl_node *atm_node_ptr;
typedef uint8_t atm_bool;
typedef uint8_t atm_uint8_t;
typedef uint16_t atm_uint16_t;
typedef uint32_t atm_uint32_t;
#ifdef __cplusplus
extern "C" {
#endif
typedef struct _sl_node {
atm_node_ptr *next;
atm_bool is_fully_linked;
atm_bool being_modified;
atm_bool removed;
uint8_t top_layer; /* 0: bottom */
atm_uint16_t ref_count;
atm_uint32_t accessing_next;
} sl_node;
/*
* *a < *b : return neg
* *a == *b : return 0
* *a > *b : return pos
*/
typedef int sl_cmp_t(sl_node *a, sl_node *b, void *aux);
typedef struct {
size_t fanout;
size_t maxLayer;
void *aux;
} sl_raw_config;
typedef struct {
sl_node head;
sl_node tail;
sl_cmp_t *cmp_func;
void *aux;
atm_uint32_t num_entries;
atm_uint32_t *layer_entries;
atm_uint8_t top_layer;
uint8_t fanout;
uint8_t max_layer;
} sl_raw;
#ifndef sl_get_entry
#define sl_get_entry(ELEM, STRUCT, MEMBER) \
((STRUCT *)((uint8_t *)(ELEM)-offsetof(STRUCT, MEMBER)))
#endif
void sl_init(sl_raw *slist, sl_cmp_t *cmp_func);
void sl_free(sl_raw *slist);
void sl_init_node(sl_node *node);
void sl_free_node(sl_node *node);
size_t sl_get_size(sl_raw *slist);
sl_raw_config sl_get_default_config();
sl_raw_config sl_get_config(sl_raw *slist);
void sl_set_config(sl_raw *slist, sl_raw_config config);
int sl_insert(sl_raw *slist, sl_node *node);
int sl_insert_nodup(sl_raw *slist, sl_node *node);
sl_node *sl_find(sl_raw *slist, sl_node *query);
sl_node *sl_find_smaller_or_equal(sl_raw *slist, sl_node *query);
sl_node *sl_find_greater_or_equal(sl_raw *slist, sl_node *query);
int sl_erase_node_passive(sl_raw *slist, sl_node *node);
int sl_erase_node(sl_raw *slist, sl_node *node);
int sl_erase(sl_raw *slist, sl_node *query);
int sl_is_valid_node(sl_node *node);
int sl_is_safe_to_free(sl_node *node);
void sl_wait_for_free(sl_node *node);
void sl_grab_node(sl_node *node);
void sl_release_node(sl_node *node);
sl_node *sl_next(sl_raw *slist, sl_node *node);
sl_node *sl_prev(sl_raw *slist, sl_node *node);
sl_node *sl_begin(sl_raw *slist);
sl_node *sl_end(sl_raw *slist);
#ifdef __cplusplus
}
#endif
#endif /* SKIPLIST_H__ */

168
include/sl.h
View file

@ -53,10 +53,18 @@
#define _SKIPLIST_H_
/*
* This file defines a skiplist data structure.
* This file defines a skiplist data structure written in C. Implemented as
* using macros this code provides a way to essentially "template" (as in C++)
* and emit code with types and functions specific to your use case. You can
* apply these macros multiple times safely in your code, once for each
* application.
*
* A skiplist is a way of storing sorted elements in such a way that they can be
* accessed, inserted and removed, all in O(log(n)) on average.
* A skiplist is a sorted list with O(log(n)) on average for most operations.
* It is a probabilistic datastructure, meaning that it does not guarantee
* O(log(n)) it approximates it over time. This implementation improves the
* probability by integrating the splay list algorithm for rebalancing trading
* off a bit of computational overhead and code complexity for a nearly always
* optimal, or "perfect" skiplist.
*
* Conceptually, a skiplist is arranged as follows:
*
@ -209,7 +217,6 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
struct decl##_node *sle_prev; \
struct __skiplist_##decl##_level { \
struct decl##_node *next; \
size_t hits; \
} *sle_levels; \
}
@ -227,16 +234,10 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
#define __SKIP_IS_LAST_ENTRY_T2B() if (lvl == 0)
#define __SKIP_ALL_ENTRIES_B2T(field, elm) for (size_t lvl = 0; lvl < slist->slh_max_height; lvl++)
#define __SKIP_ENTRIES_B2T(field, elm) for (size_t lvl = 0; lvl < elm->field.sle_height; lvl++)
#define __SKIP_ENTRIES_B2T_FROM(field, elm, off) for (size_t lvl = off; lvl < elm->field.sle_height; lvl++)
#define __SKIP_ENTRIES_B2T(field, elm) for (size_t lvl = 0; lvl <= elm->field.sle_height; lvl++)
#define __SKIP_ENTRIES_B2T_FROM(field, elm, off) for (size_t lvl = off; lvl <= elm->field.sle_height; lvl++)
#define __SKIP_IS_LAST_ENTRY_B2T() if (lvl + 1 == elm->field.sle_height)
/* Iterate over the subtree to the left (v, or 'lt') and right (u) or "CHu" and "CHv". */
#define __SKIP_SUBTREE_CHv(decl, field, list, path, nth) \
for (decl##_node_t *elm = path[nth].node; elm->field.sle_levels[path[nth].in].next == path[nth].node; elm = elm->field.sle_prev)
#define __SKIP_SUBTREE_CHu(decl, field, list, path, nth) \
for (decl##_node_t *elm = path[nth].node; elm != path[nth].node->field.sle_levels[0].next; elm = elm->field.sle_levels[0].next)
/*
* Skiplist declarations and access methods.
*/
@ -255,6 +256,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
struct decl { \
size_t slh_length, slh_max_height; \
void *slh_aux; \
int slh_prng_state; \
decl##_node_t *slh_head; \
decl##_node_t *slh_tail; \
struct { \
@ -277,10 +279,21 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
\
typedef struct __skiplist_path_##decl { \
decl##_node_t *node; /* node traversed in the act of location */ \
size_t in; /* level at which the node was intersected */ \
size_t pu; /* sum of hits from intersection to level[1] */ \
} __skiplist_path_##decl##_t; \
\
/* Xorshift algorithm for PRNG */ \
static uint32_t __##decl##_xorshift32(int *state) \
{ \
uint32_t x = *state; \
if (x == 0) \
x = 123456789; \
x ^= x << 13; \
x ^= x >> 17; \
x ^= x << 5; \
*state = x; \
return x; \
} \
\
/** \
* -- __skip_compare_entries_fn_ \
* \
@ -371,12 +384,12 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
* Skiplist. For example, when `max = 6` this function returns 0 with \
* probability 0.5, 1 with 0.25, 2 with 0.125, etc. until 6 with 0.5^7. \
*/ \
static int __skip_toss_##decl(size_t max) \
static int __skip_toss_##decl(decl##_t *slist, size_t max) \
{ \
size_t level = 0; \
double probability = 0.5; \
\
double random_value = (double)rand() / RAND_MAX; /* NOLINT(*-msc50-cpp) */ \
double random_value = (double)__##decl##_xorshift32(&slist->slh_prng_state) / RAND_MAX; \
while (random_value < probability && level < max) { \
level++; \
probability *= 0.5; \
@ -448,9 +461,9 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
* seed the PRNG in a predictable way and have reproducible random numbers. \
*/ \
if (max < 0) \
srand(-max); \
slist->slh_prng_state = -max; \
else \
srand(((unsigned int)time(NULL) ^ getpid())); \
slist->slh_prng_state = ((unsigned int)time(NULL) ^ getpid()); \
fail:; \
return rc; \
} \
@ -591,110 +604,6 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
return nodes; \
} \
\
/** \
* -- __skip_adjust_hit_counts_ TODO \
* \
* On delete we check the hit counts across all nodes and next[] pointers \
* and find the smallest counter then subtract that + 1 from all hit \
* counters. \
* \
*/ \
static void __skip_adjust_hit_counts_##decl(decl##_t *slist) \
{ \
((void)slist); \
} \
\
/** \
* -- __skip_rebalance_ \
* \
* Restore balance to our list by adjusting heights and forward pointers \
* according to the algorithm put forth in "The Splay-List: A \
* Distribution-Adaptive Concurrent Skip-List". \
* \
*/ \
static void __skip_rebalance_##decl(decl##_t *slist, size_t len, __skiplist_path_##decl##_t path[]) \
{ \
size_t i, j, u_hits, hits_CHu = 0, hits_CHv = 0, delta_height, new_height, cur_hits, prev_hits; \
double k_threshold, m_total_hits, asc_cond, dsc_cond; \
\
/* return; TODO/WIP */ \
/* Total hits, `k`, accross all nodes. */ \
m_total_hits = slist->slh_head->field.sle_levels[slist->slh_head->field.sle_height].hits; \
\
/* Height of the head node, should be close to floor(log(max_height)). */ \
k_threshold = slist->slh_head->field.sle_height + 1; \
\
/* Moving backwards along the path... \
* - path[0] contains a match, if there was one \
* - path[1..len] will be the nodes traversed along the way \
* - path[len] is where the locate() terminated, just before path[0] \
* if there was a match \
*/ \
for (i = 1; i < len; i++) { \
if (path[i].node == slist->slh_head || path[i].node == slist->slh_tail) \
continue; \
\
__SKIP_SUBTREE_CHu(decl, field, slist, path, i) \
{ \
hits_CHu += elm->field.sle_levels[i].hits; \
} \
__SKIP_SUBTREE_CHv(decl, field, slist, path, i) \
{ \
hits_CHv += elm->field.sle_levels[i].hits; \
} \
u_hits = hits_CHu + hits_CHv; \
\
/* (a) Check the decent condition: \
* u_hits <= m_total_hits / (2 ^ (k_threshold - height of node)) \
* When met should induce: \
* 1) traverse the path backward, and... \
* 2) propagate path[i].level[i] hits backward along path, and... \
* 3) adjust any forward pointers along the way, then... \
* 4) lower the path[i]'s node height by 1 \
*/ \
delta_height = k_threshold - path[i].node->field.sle_height + 1; \
dsc_cond = m_total_hits / pow(2.0, delta_height); \
if (u_hits <= dsc_cond && path[i].node->field.sle_height > 0) { \
if (path[i - 1].node->field.sle_prev != slist->slh_head) { \
/* 1) go backwards along path from where we are until head */ \
j = i; \
cur_hits = path[j].node->field.sle_levels[path[j].in].hits; \
do { \
/* 2) propagate hits */ \
prev_hits = path[j - 1].node->field.sle_levels[path[j - 1].in].hits; \
path[j - 1].node->field.sle_levels[path[j - 1].in].hits += cur_hits; \
cur_hits = prev_hits; \
/* 3) adjust forward pointers */ \
if (path[j - 1].node->field.sle_levels[j].next == path[i].node) \
path[j - 1].node->field.sle_levels[j].next = path[i].node->field.sle_levels[j].next; \
} while (j-- > 1); \
/* 4) reduce height by one */ \
path[i].node->field.sle_height--; \
} \
} \
/* (b) Check the ascent condition: \
* path[i].pu + node_hits > hits total / (2 ^ (height of head - height of node - 1)) \
* When met should induce: \
* 1) check the ascent condition, then iff true ... \
* 2) add a level, and ... \
* 3) set its hits to the prev node at intersection height \
* 4) set prev node hits to 0 and forward to this new level \
*/ \
/* 1) check ascent condition */ \
asc_cond = m_total_hits / pow(2.0, delta_height == 0 ? 0 : delta_height - 1); \
if (path[i - 1].pu > asc_cond && path[i].node->field.sle_height < slist->slh_max_height - 1) { \
/* 2) increase height by one */ \
new_height = path[i].node->field.sle_height++; \
/* 3) update hit counter */ \
path[i].node->field.sle_levels[new_height].hits += path[i - 1].node->field.sle_levels[path[i - 1].in].hits; \
/* 4) reset the prev node hits to 0 */ \
path[i - 1].node->field.sle_levels[path[i - 1].in].hits = 0; \
if (path[i - 1].in != 0) \
path[i - 1].node->field.sle_levels[path[i - 1].in].next->field.sle_levels[path[i - 1].in].next = path[i].node; \
} \
} \
} \
\
/** \
* -- __skip_locate_ \
* \
@ -715,22 +624,16 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
/* Find the node that matches `node` or NULL. */ \
i = slist->slh_head->field.sle_height; \
do { \
path[i + 1].pu = 0; \
while (elm != slist->slh_tail && elm->field.sle_levels[i].next && \
__skip_compare_nodes_##decl(slist, elm->field.sle_levels[i].next, n, slist->slh_aux) < 0) { \
elm = elm->field.sle_levels[i].next; \
path[i + 1].in = i; \
path[i + 1].pu += elm->field.sle_levels[path[i + 1].in].hits; \
} \
path[i + 1].node = elm; \
path[i + 1].node->field.sle_levels[path[i + 1].in].hits++; \
len++; \
} while (i--); \
elm = elm->field.sle_levels[0].next; \
if (__skip_compare_nodes_##decl(slist, elm, n, slist->slh_aux) == 0) { \
path[0].node = elm; \
path[0].node->field.sle_levels[0].hits++; \
__skip_rebalance_##decl(slist, len, path); \
} \
return len; \
} \
@ -761,12 +664,8 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
} \
/* First element in path should be NULL, reset should start pointing at tail. */ \
path[0].node = NULL; \
path[0].in = 0; \
path[0].pu = 0; \
for (i = 1; i < slist->slh_max_height + 1; i++) { \
path[i].node = slist->slh_tail; \
path[i].in = 0; \
path[i].pu = 0; \
} \
\
/* Find a `path` to `new` in the list and a match (`path[0]`) if it exists. */ \
@ -779,7 +678,7 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
} \
/* Coin toss to determine level of this new node [0, max) */ \
cur_height = slist->slh_head->field.sle_height; \
new_height = __skip_toss_##decl(slist->slh_max_height - 1); \
new_height = __skip_toss_##decl(slist, slist->slh_max_height - 1); \
new->field.sle_height = new_height; \
/* Trim the path to at most the new height for the new node. */ \
for (i = cur_height + 1; i <= new_height; i++) { \
@ -826,8 +725,6 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
/* Increase the the list's era/age and record it. */ \
new->field.sle_era = slist->slh_snap.cur_era++; \
} \
/* Set hits for rebalencing to 1 when new born. */ \
new->field.sle_levels[new_height].hits = 1; \
/* Increase our list length (aka. size, count, etc.) by one. */ \
slist->slh_length++; \
\
@ -1191,7 +1088,6 @@ void __attribute__((format(printf, 4, 5))) __skip_diag_(const char *file, int li
slist->slh_tail->field.sle_height = i; \
\
slist->slh_length--; \
__skip_adjust_hit_counts_##decl(slist); \
} \
return 0; \
} \

196
tests/api.c
View file

@ -1,196 +0,0 @@
static void *
test_api_setup(const MunitParameter params[], void *user_data)
{
struct test_info *info = (struct test_info *)user_data;
(void)info;
(void)params;
ex_sl_t *slist = calloc(sizeof(ex_sl_t), 1);
if (slist == NULL)
return NULL;
sl_init(slist, uint32_key_cmp);
return (void *)(uintptr_t)slist;
}
static void
test_api_tear_down(void *fixture)
{
ex_sl_t *slist = (ex_sl_t *)fixture;
assert_ptr_not_null(slist);
sl_node *cursor = sl_begin(slist);
while (cursor) {
assert_ptr_not_null(cursor);
ex_node_t *entry = sl_get_entry(cursor, ex_node_t, snode);
assert_ptr_not_null(entry);
assert_uint32(entry->key, ==, entry->value);
cursor = sl_next(slist, cursor);
sl_erase_node(slist, &entry->snode);
sl_release_node(&entry->snode);
sl_wait_for_free(&entry->snode);
sl_free_node(&entry->snode);
free(entry);
}
sl_free(slist);
free(fixture);
}
static void *
test_api_insert_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_insert_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_insert(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
assert_ptr_not_null(data);
int n = munit_rand_int_range(128, 4096);
int key = munit_rand_int_range(0, (((uint32_t)0) - 1) / 10);
while (n--) {
ex_node_t *node = (ex_node_t *)calloc(sizeof(ex_node_t), 1);
sl_init_node(&node->snode);
node->key = key;
node->value = key;
sl_insert(slist, &node->snode);
}
return MUNIT_OK;
}
static void *
test_api_remove_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_remove_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_remove(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}
static void *
test_api_find_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_find_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_find(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}
static void *
test_api_update_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_update_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_update(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}
static void *
test_api_delete_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_delete_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_delete(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}
static void *
test_api_duplicates_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_duplicates_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_duplicates(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}
static void *
test_api_size_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_size_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_size(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}
static void *
test_api_iterators_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_iterators_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_iterators(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}

2255
tests/munit.c
View file

File diff suppressed because it is too large Load diff

527
tests/munit.h
View file

@ -1,527 +0,0 @@
/* µnit Testing Framework
* Copyright (c) 2013-2017 Evan Nemerson <evan@nemerson.com>
*
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use, copy,
* modify, merge, publish, distribute, sublicense, and/or sell copies
* of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
* BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
* ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
* CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
#if !defined(MUNIT_H)
#define MUNIT_H
#include <stdarg.h>
#include <stdlib.h>
#define MUNIT_VERSION(major, minor, revision) \
(((major) << 16) | ((minor) << 8) | (revision))
#define MUNIT_CURRENT_VERSION MUNIT_VERSION(0, 4, 1)
#if defined(_MSC_VER) && (_MSC_VER < 1600)
#define munit_int8_t __int8
#define munit_uint8_t unsigned __int8
#define munit_int16_t __int16
#define munit_uint16_t unsigned __int16
#define munit_int32_t __int32
#define munit_uint32_t unsigned __int32
#define munit_int64_t __int64
#define munit_uint64_t unsigned __int64
#else
#include <stdint.h>
#define munit_int8_t int8_t
#define munit_uint8_t uint8_t
#define munit_int16_t int16_t
#define munit_uint16_t uint16_t
#define munit_int32_t int32_t
#define munit_uint32_t uint32_t
#define munit_int64_t int64_t
#define munit_uint64_t uint64_t
#endif
#if defined(_MSC_VER) && (_MSC_VER < 1800)
#if !defined(PRIi8)
#define PRIi8 "i"
#endif
#if !defined(PRIi16)
#define PRIi16 "i"
#endif
#if !defined(PRIi32)
#define PRIi32 "i"
#endif
#if !defined(PRIi64)
#define PRIi64 "I64i"
#endif
#if !defined(PRId8)
#define PRId8 "d"
#endif
#if !defined(PRId16)
#define PRId16 "d"
#endif
#if !defined(PRId32)
#define PRId32 "d"
#endif
#if !defined(PRId64)
#define PRId64 "I64d"
#endif
#if !defined(PRIx8)
#define PRIx8 "x"
#endif
#if !defined(PRIx16)
#define PRIx16 "x"
#endif
#if !defined(PRIx32)
#define PRIx32 "x"
#endif
#if !defined(PRIx64)
#define PRIx64 "I64x"
#endif
#if !defined(PRIu8)
#define PRIu8 "u"
#endif
#if !defined(PRIu16)
#define PRIu16 "u"
#endif
#if !defined(PRIu32)
#define PRIu32 "u"
#endif
#if !defined(PRIu64)
#define PRIu64 "I64u"
#endif
#else
#include <inttypes.h>
#endif
#if !defined(munit_bool)
#if defined(bool)
#define munit_bool bool
#elif defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)
#define munit_bool _Bool
#else
#define munit_bool int
#endif
#endif
#if defined(__cplusplus)
extern "C" {
#endif
#if defined(__GNUC__)
#define MUNIT_LIKELY(expr) (__builtin_expect((expr), 1))
#define MUNIT_UNLIKELY(expr) (__builtin_expect((expr), 0))
#define MUNIT_UNUSED __attribute__((__unused__))
#else
#define MUNIT_LIKELY(expr) (expr)
#define MUNIT_UNLIKELY(expr) (expr)
#define MUNIT_UNUSED
#endif
#if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) && \
!defined(__PGI)
#define MUNIT_ARRAY_PARAM(name) name
#else
#define MUNIT_ARRAY_PARAM(name)
#endif
#if !defined(_WIN32)
#define MUNIT_SIZE_MODIFIER "z"
#define MUNIT_CHAR_MODIFIER "hh"
#define MUNIT_SHORT_MODIFIER "h"
#else
#if defined(_M_X64) || defined(__amd64__)
#define MUNIT_SIZE_MODIFIER "I64"
#else
#define MUNIT_SIZE_MODIFIER ""
#endif
#define MUNIT_CHAR_MODIFIER ""
#define MUNIT_SHORT_MODIFIER ""
#endif
#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L
#define MUNIT_NO_RETURN _Noreturn
#elif defined(__GNUC__)
#define MUNIT_NO_RETURN __attribute__((__noreturn__))
#elif defined(_MSC_VER)
#define MUNIT_NO_RETURN __declspec(noreturn)
#else
#define MUNIT_NO_RETURN
#endif
#if defined(_MSC_VER) && (_MSC_VER >= 1500)
#define MUNIT_PUSH_DISABLE_MSVC_C4127_ \
__pragma(warning(push)) __pragma(warning(disable : 4127))
#define MUNIT_POP_DISABLE_MSVC_C4127_ __pragma(warning(pop))
#else
#define MUNIT_PUSH_DISABLE_MSVC_C4127_
#define MUNIT_POP_DISABLE_MSVC_C4127_
#endif
typedef enum {
MUNIT_LOG_DEBUG,
MUNIT_LOG_INFO,
MUNIT_LOG_WARNING,
MUNIT_LOG_ERROR
} MunitLogLevel;
#if defined(__GNUC__) && !defined(__MINGW32__)
#define MUNIT_PRINTF(string_index, first_to_check) \
__attribute__((format(printf, string_index, first_to_check)))
#else
#define MUNIT_PRINTF(string_index, first_to_check)
#endif
MUNIT_PRINTF(4, 5)
void munit_logf_ex(MunitLogLevel level, const char *filename, int line,
const char *format, ...);
#define munit_logf(level, format, ...) \
munit_logf_ex(level, __FILE__, __LINE__, format, __VA_ARGS__)
#define munit_log(level, msg) munit_logf(level, "%s", msg)
MUNIT_NO_RETURN
MUNIT_PRINTF(3, 4)
void munit_errorf_ex(const char *filename, int line, const char *format, ...);
#define munit_errorf(format, ...) \
munit_errorf_ex(__FILE__, __LINE__, format, __VA_ARGS__)
#define munit_error(msg) munit_errorf("%s", msg)
#define munit_assert(expr) \
do { \
if (!MUNIT_LIKELY(expr)) { \
munit_error("assertion failed: " #expr); \
} \
MUNIT_PUSH_DISABLE_MSVC_C4127_ \
} while (0) MUNIT_POP_DISABLE_MSVC_C4127_
#define munit_assert_true(expr) \
do { \
if (!MUNIT_LIKELY(expr)) { \
munit_error("assertion failed: " #expr " is not true"); \
} \
MUNIT_PUSH_DISABLE_MSVC_C4127_ \
} while (0) MUNIT_POP_DISABLE_MSVC_C4127_
#define munit_assert_false(expr) \
do { \
if (!MUNIT_LIKELY(!(expr))) { \
munit_error("assertion failed: " #expr " is not false"); \
} \
MUNIT_PUSH_DISABLE_MSVC_C4127_ \
} while (0) MUNIT_POP_DISABLE_MSVC_C4127_
#define munit_assert_type_full(prefix, suffix, T, fmt, a, op, b) \
do { \
T munit_tmp_a_ = (a); \
T munit_tmp_b_ = (b); \
if (!(munit_tmp_a_ op munit_tmp_b_)) { \
munit_errorf("assertion failed: %s %s %s (" prefix "%" fmt suffix \
" %s " prefix "%" fmt suffix ")", \
#a, #op, #b, munit_tmp_a_, #op, munit_tmp_b_); \
} \
MUNIT_PUSH_DISABLE_MSVC_C4127_ \
} while (0) MUNIT_POP_DISABLE_MSVC_C4127_
#define munit_assert_type(T, fmt, a, op, b) \
munit_assert_type_full("", "", T, fmt, a, op, b)
#define munit_assert_char(a, op, b) \
munit_assert_type_full("'\\x", "'", char, "02" MUNIT_CHAR_MODIFIER "x", a, \
op, b)
#define munit_assert_uchar(a, op, b) \
munit_assert_type_full("'\\x", "'", unsigned char, \
"02" MUNIT_CHAR_MODIFIER "x", a, op, b)
#define munit_assert_short(a, op, b) \
munit_assert_type(short, MUNIT_SHORT_MODIFIER "d", a, op, b)
#define munit_assert_ushort(a, op, b) \
munit_assert_type(unsigned short, MUNIT_SHORT_MODIFIER "u", a, op, b)
#define munit_assert_int(a, op, b) munit_assert_type(int, "d", a, op, b)
#define munit_assert_uint(a, op, b) \
munit_assert_type(unsigned int, "u", a, op, b)
#define munit_assert_long(a, op, b) munit_assert_type(long int, "ld", a, op, b)
#define munit_assert_ulong(a, op, b) \
munit_assert_type(unsigned long int, "lu", a, op, b)
#define munit_assert_llong(a, op, b) \
munit_assert_type(long long int, "lld", a, op, b)
#define munit_assert_ullong(a, op, b) \
munit_assert_type(unsigned long long int, "llu", a, op, b)
#define munit_assert_size(a, op, b) \
munit_assert_type(size_t, MUNIT_SIZE_MODIFIER "u", a, op, b)
#define munit_assert_float(a, op, b) munit_assert_type(float, "f", a, op, b)
#define munit_assert_double(a, op, b) munit_assert_type(double, "g", a, op, b)
#define munit_assert_ptr(a, op, b) \
munit_assert_type(const void *, "p", a, op, b)
#define munit_assert_int8(a, op, b) \
munit_assert_type(munit_int8_t, PRIi8, a, op, b)
#define munit_assert_uint8(a, op, b) \
munit_assert_type(munit_uint8_t, PRIu8, a, op, b)
#define munit_assert_int16(a, op, b) \
munit_assert_type(munit_int16_t, PRIi16, a, op, b)
#define munit_assert_uint16(a, op, b) \
munit_assert_type(munit_uint16_t, PRIu16, a, op, b)
#define munit_assert_int32(a, op, b) \
munit_assert_type(munit_int32_t, PRIi32, a, op, b)
#define munit_assert_uint32(a, op, b) \
munit_assert_type(munit_uint32_t, PRIu32, a, op, b)
#define munit_assert_int64(a, op, b) \
munit_assert_type(munit_int64_t, PRIi64, a, op, b)
#define munit_assert_uint64(a, op, b) \
munit_assert_type(munit_uint64_t, PRIu64, a, op, b)
#define munit_assert_double_equal(a, b, precision) \
do { \
const double munit_tmp_a_ = (a); \
const double munit_tmp_b_ = (b); \
const double munit_tmp_diff_ = ((munit_tmp_a_ - munit_tmp_b_) < 0) ? \
-(munit_tmp_a_ - munit_tmp_b_) : \
(munit_tmp_a_ - munit_tmp_b_); \
if (MUNIT_UNLIKELY(munit_tmp_diff_ > 1e-##precision)) { \
munit_errorf("assertion failed: %s == %s (%0." #precision \
"g == %0." #precision "g)", \
#a, #b, munit_tmp_a_, munit_tmp_b_); \
} \
MUNIT_PUSH_DISABLE_MSVC_C4127_ \
} while (0) MUNIT_POP_DISABLE_MSVC_C4127_
#include <string.h>
#define munit_assert_string_equal(a, b) \
do { \
const char *munit_tmp_a_ = a; \
const char *munit_tmp_b_ = b; \
if (MUNIT_UNLIKELY(strcmp(munit_tmp_a_, munit_tmp_b_) != 0)) { \
munit_errorf("assertion failed: string %s == %s (\"%s\" == \"%s\")", #a, \
#b, munit_tmp_a_, munit_tmp_b_); \
} \
MUNIT_PUSH_DISABLE_MSVC_C4127_ \
} while (0) MUNIT_POP_DISABLE_MSVC_C4127_
#define munit_assert_string_not_equal(a, b) \
do { \
const char *munit_tmp_a_ = a; \
const char *munit_tmp_b_ = b; \
if (MUNIT_UNLIKELY(strcmp(munit_tmp_a_, munit_tmp_b_) == 0)) { \
munit_errorf("assertion failed: string %s != %s (\"%s\" == \"%s\")", #a, \
#b, munit_tmp_a_, munit_tmp_b_); \
} \
MUNIT_PUSH_DISABLE_MSVC_C4127_ \
} while (0) MUNIT_POP_DISABLE_MSVC_C4127_
#define munit_assert_memory_equal(size, a, b) \
do { \
const unsigned char *munit_tmp_a_ = (const unsigned char *)(a); \
const unsigned char *munit_tmp_b_ = (const unsigned char *)(b); \
const size_t munit_tmp_size_ = (size); \
if (MUNIT_UNLIKELY(memcmp(munit_tmp_a_, munit_tmp_b_, munit_tmp_size_)) != \
0) { \
size_t munit_tmp_pos_; \
for (munit_tmp_pos_ = 0; munit_tmp_pos_ < munit_tmp_size_; \
munit_tmp_pos_++) { \
if (munit_tmp_a_[munit_tmp_pos_] != munit_tmp_b_[munit_tmp_pos_]) { \
munit_errorf( \
"assertion failed: memory %s == %s, at offset %" MUNIT_SIZE_MODIFIER \
"u", \
#a, #b, munit_tmp_pos_); \
break; \
} \
} \
} \
MUNIT_PUSH_DISABLE_MSVC_C4127_ \
} while (0) MUNIT_POP_DISABLE_MSVC_C4127_
#define munit_assert_memory_not_equal(size, a, b) \
do { \
const unsigned char *munit_tmp_a_ = (const unsigned char *)(a); \
const unsigned char *munit_tmp_b_ = (const unsigned char *)(b); \
const size_t munit_tmp_size_ = (size); \
if (MUNIT_UNLIKELY(memcmp(munit_tmp_a_, munit_tmp_b_, munit_tmp_size_)) == \
0) { \
munit_errorf("assertion failed: memory %s != %s (%zu bytes)", #a, #b, \
munit_tmp_size_); \
} \
MUNIT_PUSH_DISABLE_MSVC_C4127_ \
} while (0) MUNIT_POP_DISABLE_MSVC_C4127_
#define munit_assert_ptr_equal(a, b) munit_assert_ptr(a, ==, b)
#define munit_assert_ptr_not_equal(a, b) munit_assert_ptr(a, !=, b)
#define munit_assert_null(ptr) munit_assert_ptr(ptr, ==, NULL)
#define munit_assert_not_null(ptr) munit_assert_ptr(ptr, !=, NULL)
#define munit_assert_ptr_null(ptr) munit_assert_ptr(ptr, ==, NULL)
#define munit_assert_ptr_not_null(ptr) munit_assert_ptr(ptr, !=, NULL)
/*** Memory allocation ***/
void *munit_malloc_ex(const char *filename, int line, size_t size);
#define munit_malloc(size) munit_malloc_ex(__FILE__, __LINE__, (size))
#define munit_new(type) ((type *)munit_malloc(sizeof(type)))
#define munit_calloc(nmemb, size) munit_malloc((nmemb) * (size))
#define munit_newa(type, nmemb) ((type *)munit_calloc((nmemb), sizeof(type)))
/*** Random number generation ***/
void munit_rand_seed(munit_uint32_t seed);
munit_uint32_t munit_rand_uint32(void);
int munit_rand_int_range(int min, int max);
double munit_rand_double(void);
void munit_rand_memory(size_t size,
munit_uint8_t buffer[MUNIT_ARRAY_PARAM(size)]);
/*** Tests and Suites ***/
typedef enum {
/* Test successful */
MUNIT_OK,
/* Test failed */
MUNIT_FAIL,
/* Test was skipped */
MUNIT_SKIP,
/* Test failed due to circumstances not intended to be tested
* (things like network errors, invalid parameter value, failure to
* allocate memory in the test harness, etc.). */
MUNIT_ERROR
} MunitResult;
typedef struct {
char *name;
char **values;
} MunitParameterEnum;
typedef struct {
char *name;
char *value;
} MunitParameter;
const char *munit_parameters_get(const MunitParameter params[],
const char *key);
typedef enum {
MUNIT_TEST_OPTION_NONE = 0,
MUNIT_TEST_OPTION_SINGLE_ITERATION = 1 << 0,
MUNIT_TEST_OPTION_TODO = 1 << 1
} MunitTestOptions;
typedef MunitResult (
*MunitTestFunc)(const MunitParameter params[], void *user_data_or_fixture);
typedef void *(*MunitTestSetup)(const MunitParameter params[], void *user_data);
typedef void (*MunitTestTearDown)(void *fixture);
typedef struct {
char *name;
MunitTestFunc test;
MunitTestSetup setup;
MunitTestTearDown tear_down;
MunitTestOptions options;
MunitParameterEnum *parameters;
} MunitTest;
typedef enum { MUNIT_SUITE_OPTION_NONE = 0 } MunitSuiteOptions;
typedef struct MunitSuite_ MunitSuite;
struct MunitSuite_ {
char *prefix;
MunitTest *tests;
MunitSuite *suites;
unsigned int iterations;
MunitSuiteOptions options;
};
int munit_suite_main(const MunitSuite *suite, void *user_data, int argc,
char *const argv[MUNIT_ARRAY_PARAM(argc + 1)]);
/* Note: I'm not very happy with this API; it's likely to change if I
* figure out something better. Suggestions welcome. */
typedef struct MunitArgument_ MunitArgument;
struct MunitArgument_ {
char *name;
munit_bool (*parse_argument)(const MunitSuite *suite, void *user_data,
int *arg, int argc, char *const argv[MUNIT_ARRAY_PARAM(argc + 1)]);
void (*write_help)(const MunitArgument *argument, void *user_data);
};
int munit_suite_main_custom(const MunitSuite *suite, void *user_data, int argc,
char *const argv[MUNIT_ARRAY_PARAM(argc + 1)],
const MunitArgument arguments[]);
#if defined(MUNIT_ENABLE_ASSERT_ALIASES)
#define assert_true(expr) munit_assert_true(expr)
#define assert_false(expr) munit_assert_false(expr)
#define assert_char(a, op, b) munit_assert_char(a, op, b)
#define assert_uchar(a, op, b) munit_assert_uchar(a, op, b)
#define assert_short(a, op, b) munit_assert_short(a, op, b)
#define assert_ushort(a, op, b) munit_assert_ushort(a, op, b)
#define assert_int(a, op, b) munit_assert_int(a, op, b)
#define assert_uint(a, op, b) munit_assert_uint(a, op, b)
#define assert_long(a, op, b) munit_assert_long(a, op, b)
#define assert_ulong(a, op, b) munit_assert_ulong(a, op, b)
#define assert_llong(a, op, b) munit_assert_llong(a, op, b)
#define assert_ullong(a, op, b) munit_assert_ullong(a, op, b)
#define assert_size(a, op, b) munit_assert_size(a, op, b)
#define assert_float(a, op, b) munit_assert_float(a, op, b)
#define assert_double(a, op, b) munit_assert_double(a, op, b)
#define assert_ptr(a, op, b) munit_assert_ptr(a, op, b)
#define assert_int8(a, op, b) munit_assert_int8(a, op, b)
#define assert_uint8(a, op, b) munit_assert_uint8(a, op, b)
#define assert_int16(a, op, b) munit_assert_int16(a, op, b)
#define assert_uint16(a, op, b) munit_assert_uint16(a, op, b)
#define assert_int32(a, op, b) munit_assert_int32(a, op, b)
#define assert_uint32(a, op, b) munit_assert_uint32(a, op, b)
#define assert_int64(a, op, b) munit_assert_int64(a, op, b)
#define assert_uint64(a, op, b) munit_assert_uint64(a, op, b)
#define assert_double_equal(a, b, precision) \
munit_assert_double_equal(a, b, precision)
#define assert_string_equal(a, b) munit_assert_string_equal(a, b)
#define assert_string_not_equal(a, b) munit_assert_string_not_equal(a, b)
#define assert_memory_equal(size, a, b) munit_assert_memory_equal(size, a, b)
#define assert_memory_not_equal(size, a, b) \
munit_assert_memory_not_equal(size, a, b)
#define assert_ptr_equal(a, b) munit_assert_ptr_equal(a, b)
#define assert_ptr_not_equal(a, b) munit_assert_ptr_not_equal(a, b)
#define assert_ptr_null(ptr) munit_assert_null_equal(ptr)
#define assert_ptr_not_null(ptr) munit_assert_not_null(ptr)
#define assert_null(ptr) munit_assert_null(ptr)
#define assert_not_null(ptr) munit_assert_not_null(ptr)
#endif /* defined(MUNIT_ENABLE_ASSERT_ALIASES) */
#if defined(__cplusplus)
}
#endif
#endif /* !defined(MUNIT_H) */
#if defined(MUNIT_ENABLE_ASSERT_ALIASES)
#if defined(assert)
#undef assert
#endif
#define assert(expr) munit_assert(expr)
#endif

449
tests/test.c
View file

@ -1,449 +0,0 @@
/*
* skiplist 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
* work. See <https://creativecommons.org/publicdomain/zero/1.0/> for
* details.
*/
#define MUNIT_NO_FORK (1)
#define MUNIT_ENABLE_ASSERT_ALIASES (1)
#include <stdio.h>
#include <stdlib.h>
#define __SL_DEBUG 0
#if __SL_DEBUG > 0
#include <sys/types.h>
#include <assert.h>
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#endif
#if __SL_DEBUG >= 1
#define __SLD_ASSERT(cond) assert(cond)
#define __SLD_(b) b
#elif __SL_DEBUG >= 2
#define __SLD_P(...) printf(__VA_ARGS__)
#elif __SL_DEBUG >= 3
typedef struct dbg_node {
sl_node snode;
int value;
} dbg_node_t;
inline void
__sld_rt_ins(int error_code, sl_node *node, int top_layer, int cur_layer)
{
dbg_node_t *ddd = sl_get_entry(node, dbg_node_t, snode);
printf("[INS] retry (code %d) "
"%p (top %d, cur %d) %d\n",
error_code, node, top_layer, cur_layer, ddd->value);
}
inline void
__sld_nc_ins(sl_node *node, sl_node *next_node, int top_layer, int cur_layer)
{
dbg_node_t *ddd = sl_get_entry(node, dbg_node_t, snode);
dbg_node_t *ddd_next = sl_get_entry(next_node, dbg_node_t, snode);
printf("[INS] next node changed, "
"%p %p (top %d, cur %d) %d %d\n",
node, next_node, top_layer, cur_layer, ddd->value, ddd_next->value);
}
inline void
__sld_rt_rmv(int error_code, sl_node *node, int top_layer, int cur_layer)
{
dbg_node_t *ddd = sl_get_entry(node, dbg_node_t, snode);
printf("[RMV] retry (code %d) "
"%p (top %d, cur %d) %d\n",
error_code, node, top_layer, cur_layer, ddd->value);
}
inline void
__sld_nc_rmv(sl_node *node, sl_node *next_node, int top_layer, int cur_layer)
{
dbg_node_t *ddd = sl_get_entry(node, dbg_node_t, snode);
dbg_node_t *ddd_next = sl_get_entry(next_node, dbg_node_t, snode);
printf("[RMV] next node changed, "
"%p %p (top %d, cur %d) %d %d\n",
node, next_node, top_layer, cur_layer, ddd->value, ddd_next->value);
}
inline void
__sld_bm(sl_node *node)
{
dbg_node_t *ddd = sl_get_entry(node, dbg_node_t, snode);
printf("[RMV] node is being modified %d\n", ddd->value);
}
#define __SLD_RT_INS(e, n, t, c) __sld_rt_ins(e, n, t, c)
#define __SLD_NC_INS(n, nn, t, c) __sld_nc_ins(n, nn, t, c)
#define __SLD_RT_RMV(e, n, t, c) __sld_rt_rmv(e, n, t, c)
#define __SLD_NC_RMV(n, nn, t, c) __sld_nc_rmv(n, nn, t, c)
#define __SLD_BM(n) __sld_bm(n)
#endif
#include "../include/skiplist.h"
#include "munit.h"
#if defined(_MSC_VER)
#pragma warning(disable : 4127)
#endif
struct user_data {
size_t n_ele;
};
typedef struct ex_node {
sl_node snode;
uint32_t key;
uint32_t value;
} ex_node_t;
typedef sl_raw ex_sl_t;
static int
uint32_key_cmp(sl_node *a, sl_node *b, void *aux)
{
ex_node_t *aa, *bb;
(void)aux;
aa = sl_get_entry(a, ex_node_t, snode);
bb = sl_get_entry(b, ex_node_t, snode);
if (aa->key < bb->key)
return -1;
if (aa->key > bb->key)
return 1;
return 0;
}
static size_t
__populate_slist(ex_sl_t *slist)
{
size_t inserted = 0;
uint32_t n, key;
ex_node_t *node;
n = munit_rand_int_range(1024, 4196);
while (n--) {
key = munit_rand_int_range(0, (((uint32_t)0) - 1) / 10);
node = (ex_node_t *)calloc(sizeof(ex_node_t), 1);
if (node == NULL)
return MUNIT_ERROR;
sl_init_node(&node->snode);
node->key = key;
node->value = key;
if (sl_insert_nodup(slist, &node->snode) == -1)
continue; /* a random duplicate appeared */
else
inserted++;
}
return inserted;
}
static void *
test_api_setup(const MunitParameter params[], void *user_data)
{
struct test_info *info = (struct test_info *)user_data;
(void)info;
(void)params;
ex_sl_t *slist = calloc(sizeof(ex_sl_t), 1);
if (slist == NULL)
return NULL;
sl_init(slist, uint32_key_cmp);
return (void *)(uintptr_t)slist;
}
static void
test_api_tear_down(void *fixture)
{
ex_sl_t *slist = (ex_sl_t *)fixture;
assert_ptr_not_null(slist);
sl_node *cursor = sl_begin(slist);
while (cursor) {
assert_ptr_not_null(cursor);
ex_node_t *entry = sl_get_entry(cursor, ex_node_t, snode);
assert_ptr_not_null(entry);
assert_uint32(entry->key, ==, entry->value);
cursor = sl_next(slist, cursor);
sl_erase_node(slist, &entry->snode);
sl_release_node(&entry->snode);
sl_wait_for_free(&entry->snode);
sl_free_node(&entry->snode);
free(entry);
}
sl_free(slist);
free(fixture);
}
static void *
test_api_insert_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_insert_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_insert(const MunitParameter params[], void *data)
{
int ret;
size_t inserted = 0;
uint32_t n, key;
sl_raw *slist = (sl_raw *)data;
ex_node_t *node;
(void)params;
assert_ptr_not_null(slist);
n = munit_rand_int_range(4096, 8192);
while (n--) {
key = munit_rand_int_range(0, ((uint32_t)0 - 1) / 10);
node = (ex_node_t *)calloc(sizeof(ex_node_t), 1);
if (node == NULL)
return MUNIT_ERROR;
sl_init_node(&node->snode);
node->key = key;
node->value = key;
if ((ret = sl_insert_nodup(slist, &node->snode)) == -1)
continue; /* a random duplicate appeared */
else {
assert_int(ret, ==, 0);
inserted++;
}
}
assert_size(inserted, ==, sl_get_size(slist));
return MUNIT_OK;
}
static void *
test_api_remove_setup(const MunitParameter params[], void *user_data)
{
sl_raw *slist = (sl_raw *)test_api_setup(params, user_data);
__populate_slist(slist);
return (void *)slist;
}
static void
test_api_remove_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_remove(const MunitParameter params[], void *data)
{
uint32_t key;
sl_raw *slist = (sl_raw *)data;
ex_node_t *node;
(void)params;
assert_ptr_not_null(slist);
key = munit_rand_int_range((((uint32_t)0 - 1) / 10) + 1, ((uint32_t)0 - 1));
node = (ex_node_t *)calloc(sizeof(ex_node_t), 1);
if (node == NULL)
return MUNIT_ERROR;
sl_init_node(&node->snode);
node->key = key;
node->value = key;
if (sl_insert_nodup(slist, &node->snode) == -1)
return MUNIT_ERROR;
else {
ex_node_t query;
query.key = key;
sl_node *cursor = sl_find(slist, &query.snode);
assert_ptr_not_null(cursor);
ex_node_t *entry = sl_get_entry(cursor, ex_node_t, snode);
sl_erase_node(slist, &entry->snode);
sl_release_node(&entry->snode);
sl_wait_for_free(&entry->snode);
sl_free_node(&entry->snode);
free(entry);
}
return MUNIT_OK;
}
static void *
test_api_find_setup(const MunitParameter params[], void *user_data)
{
sl_raw *slist = (sl_raw *)test_api_setup(params, user_data);
ex_node_t *node;
for (int i = 1; i <= 100; ++i) {
node = calloc(sizeof(ex_node_t), 1);
if (node == NULL)
return NULL;
node = (ex_node_t *)calloc(sizeof(ex_node_t), 1);
sl_init_node(&node->snode);
node->key = i;
node->value = i;
sl_insert(slist, &node->snode);
}
return (void *)slist;
}
static void
test_api_find_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_find(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
/* find equal every value */
assert_ptr_not_null(data);
for (int i = 1; i <= 100; i++) {
ex_node_t query;
query.key = i;
sl_node *cursor = sl_find(slist, &query.snode);
assert_ptr_not_null(cursor);
ex_node_t *entry = sl_get_entry(cursor, ex_node_t, snode);
assert_uint32(entry->key, ==, i);
}
/* */
return MUNIT_OK;
}
static void *
test_api_update_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_update_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_update(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}
static void *
test_api_delete_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_delete_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_delete(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}
static void *
test_api_duplicates_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_duplicates_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_duplicates(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}
static void *
test_api_size_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_size_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_size(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}
static void *
test_api_iterators_setup(const MunitParameter params[], void *user_data)
{
return test_api_setup(params, user_data);
}
static void
test_api_iterators_tear_down(void *fixture)
{
test_api_tear_down(fixture);
}
static MunitResult
test_api_iterators(const MunitParameter params[], void *data)
{
sl_raw *slist = (sl_raw *)data;
(void)params;
(void)slist;
return MUNIT_OK;
}
static MunitTest api_test_suite[] = {
{ (char *)"/api/insert", test_api_insert, test_api_insert_setup,
test_api_insert_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/api/remove", test_api_remove, test_api_remove_setup,
test_api_remove_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/api/find", test_api_find, test_api_find_setup,
test_api_find_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/api/update", test_api_update, test_api_update_setup,
test_api_update_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/api/delete", test_api_delete, test_api_delete_setup,
test_api_delete_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/api/duplicates", test_api_duplicates, test_api_duplicates_setup,
test_api_duplicates_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/api/size", test_api_size, test_api_size_setup,
test_api_size_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ (char *)"/api/iterators", test_api_iterators, test_api_iterators_setup,
test_api_iterators_tear_down, MUNIT_TEST_OPTION_NONE, NULL },
{ NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL }
};
static MunitTest mt_tests[] = { { NULL, NULL, NULL, NULL,
MUNIT_TEST_OPTION_NONE, NULL } };
static MunitTest scale_tests[] = { { NULL, NULL, NULL, NULL,
MUNIT_TEST_OPTION_NONE, NULL } };
static MunitSuite other_test_suite[] = { { "/mt", mt_tests, NULL, 1,
MUNIT_SUITE_OPTION_NONE },
{ "/scale", scale_tests, NULL, 1, MUNIT_SUITE_OPTION_NONE },
{ NULL, NULL, NULL, 0, MUNIT_SUITE_OPTION_NONE } };
static const MunitSuite main_test_suite = { (char *)"/api", api_test_suite,
other_test_suite, 1, MUNIT_SUITE_OPTION_NONE };
int
main(int argc, char *argv[MUNIT_ARRAY_PARAM(argc + 1)])
{
struct user_data info;
return munit_suite_main(&main_test_suite, (void *)&info, argc, argv);
}
/* ARGS: --no-fork --seed 8675309 */