From cb1a40859029f33184355475e51fec95afb79a73 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Yaroslav=20de=20la=20Pe=C3=B1a=20Smirnov?= Date: Sat, 22 Jul 2023 03:03:09 +0300 Subject: init Just some C wares; hmap, list, optional, unit tests. --- .clang-format | 187 +++++++++++++++++ .gitignore | 6 + README.md | 28 +++ hmap/Makefile | 9 + hmap/README.md | 8 + hmap/hash.h | 61 ++++++ hmap/hmap-test.c | 291 +++++++++++++++++++++++++++ hmap/hmap.c | 297 +++++++++++++++++++++++++++ hmap/hmap.h | 238 ++++++++++++++++++++++ licenses/LGPL-2.1 | 511 +++++++++++++++++++++++++++++++++++++++++++++++ licenses/MIT | 18 ++ list/list.h | 205 +++++++++++++++++++ optional/Makefile | 5 + optional/README.md | 12 ++ optional/optional-test.c | 55 +++++ optional/optional.h | 92 +++++++++ utest/Makefile | 5 + utest/utest-test.c | 34 ++++ utest/utest.h | 221 ++++++++++++++++++++ utils.h | 35 ++++ 20 files changed, 2318 insertions(+) create mode 100644 .clang-format create mode 100644 .gitignore create mode 100644 README.md create mode 100644 hmap/Makefile create mode 100644 hmap/README.md create mode 100644 hmap/hash.h create mode 100644 hmap/hmap-test.c create mode 100644 hmap/hmap.c create mode 100644 hmap/hmap.h create mode 100644 licenses/LGPL-2.1 create mode 100644 licenses/MIT create mode 100644 list/list.h create mode 100644 optional/Makefile create mode 100644 optional/README.md create mode 100644 optional/optional-test.c create mode 100644 optional/optional.h create mode 100644 utest/Makefile create mode 100644 utest/utest-test.c create mode 100644 utest/utest.h create mode 100644 utils.h diff --git a/.clang-format b/.clang-format new file mode 100644 index 0000000..008800f --- /dev/null +++ b/.clang-format @@ -0,0 +1,187 @@ +# SPDX-License-Identifier: GPL-2.0 +# +# clang-format configuration file. Intended for clang-format >= 11. +# +# For more information, see: +# +# Documentation/process/clang-format.rst +# https://clang.llvm.org/docs/ClangFormat.html +# https://clang.llvm.org/docs/ClangFormatStyleOptions.html +# +# Taken from Linux v6.0 with some adjustments +--- +AccessModifierOffset: -4 +AlignAfterOpenBracket: Align +AlignArrayOfStructures: Left +AlignConsecutiveAssignments: Consecutive +AlignConsecutiveDeclarations: Consecutive +AlignConsecutiveMacros: Consecutive +AlignConsecutiveBitFields: Consecutive +AlignEscapedNewlines: Left +AlignOperands: AlignAfterOperator +AlignTrailingComments: true +AllowAllParametersOfDeclarationOnNextLine: false +AllowShortBlocksOnASingleLine: false +AllowShortCaseLabelsOnASingleLine: false +AllowShortFunctionsOnASingleLine: None +AllowShortIfStatementsOnASingleLine: false +AllowShortLoopsOnASingleLine: false +AlwaysBreakAfterDefinitionReturnType: None +AlwaysBreakAfterReturnType: None +AlwaysBreakBeforeMultilineStrings: false +AlwaysBreakTemplateDeclarations: false +# Taken from RAIDIX Generic +AttributeMacros: + - '__init' + - '__exit' + - '__packed' + - '__aligned' + - '__rcu' + - '__must_hold' + - '__read_mostly' + +BinPackArguments: true +BinPackParameters: true +BraceWrapping: + AfterClass: false + AfterControlStatement: false + AfterEnum: false + AfterFunction: true + AfterNamespace: true + AfterObjCDeclaration: false + AfterStruct: false + AfterUnion: false + AfterExternBlock: false + BeforeCatch: false + BeforeElse: false + IndentBraces: false + SplitEmptyFunction: true + SplitEmptyRecord: true + SplitEmptyNamespace: true +BreakBeforeBinaryOperators: NonAssignment +BreakBeforeBraces: Custom +BreakBeforeInheritanceComma: false +BreakBeforeTernaryOperators: true +BreakConstructorInitializersBeforeComma: false +BreakConstructorInitializers: BeforeComma +BreakAfterJavaFieldAnnotations: false +BreakStringLiterals: false +ColumnLimit: 80 +CommentPragmas: '^ IWYU pragma:' +CompactNamespaces: false +ConstructorInitializerAllOnOneLineOrOnePerLine: false +ConstructorInitializerIndentWidth: 8 +ContinuationIndentWidth: 8 +Cpp11BracedListStyle: false +DerivePointerAlignment: false +DisableFormat: false +ExperimentalAutoDetectBinPacking: false +FixNamespaceComments: false + +# Taken from: +# git grep -h '^#define [^[:space:]]*for_each[^[:space:]]*(' include/ tools/ \ +# | sed "s,^#define \([^[:space:]]*for_each[^[:space:]]*\)(.*$, - '\1'," \ +# | LC_ALL=C sort -u +ForEachMacros: + - 'hlist_bl_for_each_entry' + - 'hlist_bl_for_each_entry_rcu' + - 'hlist_bl_for_each_entry_safe' + - 'hlist_for_each' + - 'hlist_for_each_entry' + - 'hlist_for_each_entry_continue' + - 'hlist_for_each_entry_continue_rcu' + - 'hlist_for_each_entry_continue_rcu_bh' + - 'hlist_for_each_entry_from' + - 'hlist_for_each_entry_from_rcu' + - 'hlist_for_each_entry_rcu' + - 'hlist_for_each_entry_rcu_bh' + - 'hlist_for_each_entry_rcu_notrace' + - 'hlist_for_each_entry_safe' + - 'hlist_for_each_entry_srcu' + - 'hlist_for_each_safe' + - 'hlist_nulls_for_each_entry' + - 'hlist_nulls_for_each_entry_from' + - 'hlist_nulls_for_each_entry_rcu' + - 'hlist_nulls_for_each_entry_safe' + - 'hmap_iter_foreach' + - 'list_for_each' + - 'list_for_each_codec' + - 'list_for_each_codec_safe' + - 'list_for_each_continue' + - 'list_for_each_entry' + - 'list_for_each_entry_continue' + - 'list_for_each_entry_continue_rcu' + - 'list_for_each_entry_continue_reverse' + - 'list_for_each_entry_from' + - 'list_for_each_entry_from_rcu' + - 'list_for_each_entry_from_reverse' + - 'list_for_each_entry_lockless' + - 'list_for_each_entry_rcu' + - 'list_for_each_entry_reverse' + - 'list_for_each_entry_safe' + - 'list_for_each_entry_safe_continue' + - 'list_for_each_entry_safe_from' + - 'list_for_each_entry_safe_reverse' + - 'list_for_each_entry_srcu' + - 'list_for_each_from' + - 'list_for_each_prev' + - 'list_for_each_prev_safe' + - 'list_for_each_safe' + - 'llist_for_each' + - 'llist_for_each_entry' + - 'llist_for_each_entry_safe' + - 'llist_for_each_safe' + +IncludeBlocks: Preserve +IncludeCategories: + - Regex: '.*' + Priority: 1 +IncludeIsMainRegex: '(Test)?$' +IndentCaseLabels: false +IndentGotoLabels: false +IndentPPDirectives: None +IndentWidth: 4 +IndentWrappedFunctionNames: false +JavaScriptQuotes: Leave +JavaScriptWrapImports: true +KeepEmptyLinesAtTheStartOfBlocks: true +MacroBlockBegin: '' +MacroBlockEnd: '' +MaxEmptyLinesToKeep: 1 +NamespaceIndentation: None +ObjCBinPackProtocolList: Auto +ObjCBlockIndentWidth: 4 +ObjCSpaceAfterProperty: true +ObjCSpaceBeforeProtocolList: true + +# Taken from git's rules +PenaltyBreakAssignment: 30 +PenaltyBreakBeforeFirstCallParameter: 10 +PenaltyBreakComment: 10 +PenaltyBreakFirstLessLess: 0 +PenaltyBreakString: 10 +PenaltyExcessCharacter: 100 +PenaltyReturnTypeOnItsOwnLine: 60 + +PointerAlignment: Right +ReflowComments: false +SortIncludes: false +SortUsingDeclarations: false +SpaceAfterCStyleCast: false +SpaceAfterTemplateKeyword: true +SpaceBeforeAssignmentOperators: true +SpaceBeforeCtorInitializerColon: true +SpaceBeforeInheritanceColon: true +SpaceBeforeParens: ControlStatementsExceptForEachMacros +SpaceBeforeRangeBasedForLoopColon: true +SpaceInEmptyParentheses: false +SpacesBeforeTrailingComments: 1 +SpacesInAngles: false +SpacesInContainerLiterals: false +SpacesInCStyleCastParentheses: false +SpacesInParentheses: false +SpacesInSquareBrackets: false +Standard: Auto +TabWidth: 4 +UseTab: Always +... diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..af407b2 --- /dev/null +++ b/.gitignore @@ -0,0 +1,6 @@ +.cache/ +compile_commands.json +build/ +.gdb_history + +*/*-test diff --git a/README.md b/README.md new file mode 100644 index 0000000..37d4f4d --- /dev/null +++ b/README.md @@ -0,0 +1,28 @@ +# C Wares + +This repo is intended as a collection of different data structures, and other +small utilities in C, that I've collected over time. Some of the stuff here is +written by me, some other stuff I've extracted from open source projects for my +own personal use. + +This repo is not intended as a library or framework, but rather just a +collection of useful simple stuff that is hard to come by when writing programs +in C. + +## Wares + +Currently this repo contains the following: + +* hmap - simple generic hashmap with no macro vodoo-magic. +* list - double-link listed as seen on the Linux Kernel™; extracted from Git. +* optional - header-only poor man's optional "type templates" for C. +* utest - micro header-only unit test "framework" +* utils.h - various useful macros, needed by some of the "libs" in this repo, + but that can also be useful on their own. + +hmap, optional and utest have unit test of their own that serve as examples of +their respective APIs. list.h doesn't have its own unit tests since it wasn't +written by me. + +To run any of the tests just cd into the respective dir, run `make` and then +`./*-test`. diff --git a/hmap/Makefile b/hmap/Makefile new file mode 100644 index 0000000..dc52ab3 --- /dev/null +++ b/hmap/Makefile @@ -0,0 +1,9 @@ +CC?=gcc +CFLAGS+=-Wall -Werror -std=gnu11 -Og -g + +ifdef DEBUG +CFLAGS+=-DHMAP_DEBUG +endif + +all: + $(CC) $(CFLAGS) -o hmap-test hmap-test.c hmap.c diff --git a/hmap/README.md b/hmap/README.md new file mode 100644 index 0000000..a39d14a --- /dev/null +++ b/hmap/README.md @@ -0,0 +1,8 @@ +# Hmap + +Simple generic hash map with no macro vodoo magic. Inspired by other data +structures in the Linux Kernel. + +## Example usage + +If you want to see an example on how to use hmap, take a look at `hmap-test.c`. diff --git a/hmap/hash.h b/hmap/hash.h new file mode 100644 index 0000000..9d4d8dd --- /dev/null +++ b/hmap/hash.h @@ -0,0 +1,61 @@ +/* SPDX-License-Identifier: MIT */ +/** + * hash.h - implementations of the FNV1a hashing algorithm. + * + * Copyright (c) 2022-2023 - Yaroslav de la Peña Smirnov + */ +#ifndef HMAP_HASH_H +#define HMAP_HASH_H + +#include +#include + +#if SIZE_MAX == 0xFFFFFFFF +/* size_t is 32bit */ +static const size_t fnv_prime = 16777619u; +static const size_t fnv_offsetb = 2166136261u; +#elif SIZE_MAX == 0xFFFFFFFFFFFFFFFF +/* size_t is 64bit */ +static const size_t fnv_prime = 1099511628211u; +static const size_t fnv_offsetb = 14695981039346656037u; +#endif + +/** + * fnv1a_bytes_hash() - generic fnv1a hash function. + * @data: pointer to data to hash. + * @len: size of @data in bytes. + * + * Return: hash value. + */ +static inline size_t fnv1a_bytes_hash(const void *data, size_t len) +{ + const char *bytes = (const char *)data; + size_t hash = fnv_offsetb; + + for (size_t i = 0; i < len; i++) { + hash ^= bytes[i]; + hash *= fnv_prime; + } + + return hash; +} + +/** + * fnv1a_str_hash() - fnv1a hash function for nul-terminated strings. + * @str: nul-terminated string of characters to hash. + * + * Return: hash value. + */ +static inline size_t fnv1a_str_hash(const char *str) +{ + size_t hash = fnv_offsetb; + + for (size_t i = 0; str[i]; i++) { + hash ^= str[i]; + hash *= fnv_prime; + } + + return hash; +} + +#endif /* HMAP_HASH_H */ diff --git a/hmap/hmap-test.c b/hmap/hmap-test.c new file mode 100644 index 0000000..bf3ebe2 --- /dev/null +++ b/hmap/hmap-test.c @@ -0,0 +1,291 @@ +#include "hash.h" +#include "hmap.h" +#include "../utest/utest.h" + +#include + +struct hmap_test_s { + const char *key; + uint64_t data; + struct hmap_entry entry; +}; + +#define entry_to_test_s(ent) hmap_item(ent, struct hmap_test_s, entry) + +bool hmap_test_cmp(const struct hmap_entry *ent, const struct hmap_entry *key) +{ + struct hmap_test_s *a = entry_to_test_s(ent); + struct hmap_test_s *b = entry_to_test_s(key); + + return !strcmp(a->key, b->key); +} + +void hmap_test_hash(struct hmap_entry *ent) +{ + struct hmap_test_s *e = entry_to_test_s(ent); + ent->hash = fnv1a_str_hash(e->key); +} + +struct hmap *map; + +/* clang-format off */ +struct hmap_test_s inputs[] = { + { .key = "alpha", .data = 10, }, + { .key = "bravo", .data = 24, }, + { .key = "charlie", .data = 30, }, + { .key = "delta", .data = 42, }, + { .key = "echo", .data = 50, }, + { .key = "foxtrot", .data = 69, }, + { .key = "golf", .data = 70, }, + { .key = "hotel", .data = 80, }, + { .key = "india", .data = 99, }, +}; + +struct hmap_test_s inputs2[] = { + { .key = "aa" }, + { .key = "ab" }, + { .key = "ac" }, + { .key = "ad" }, + { .key = "ae" }, + { .key = "af" }, + { .key = "ag" }, + { .key = "ah" }, + { .key = "ai" }, + { .key = "aj" }, + { .key = "ak" }, + { .key = "al" }, + { .key = "am" }, + { .key = "an" }, + { .key = "ao" }, + { .key = "ap" }, + { .key = "aq" }, + { .key = "ar" }, + { .key = "as" }, + { .key = "at" }, + { .key = "au" }, + { .key = "av" }, + { .key = "aw" }, + { .key = "ax" }, + { .key = "ay" }, + { .key = "az" }, + { .key = "ba" }, + { .key = "bb" }, + { .key = "bc" }, + { .key = "bd" }, + { .key = "be" }, + { .key = "bf" }, + { .key = "bg" }, + { .key = "bh" }, + { .key = "bi" }, + { .key = "bj" }, + { .key = "bk" }, + { .key = "bl" }, + { .key = "bm" }, + { .key = "bn" }, + { .key = "bo" }, + { .key = "bp" }, + { .key = "bq" }, + { .key = "br" }, + { .key = "bs" }, + { .key = "bt" }, + { .key = "bu" }, + { .key = "bv" }, + { .key = "bw" }, + { .key = "bx" }, + { .key = "by" }, +}; +/* clang-format on */ + +struct hmap_test_s duplicate = { .key = "foxtrot", .data = 420 }; + +#ifndef HMAP_DEBUG + +TEST_BEGIN(test_hmap_add) +{ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + size_t cnt = hmap_entry_cnt(map); + expect(cnt == ARRAY_SIZE(inputs), + "number of entries in hashmap (%lu) != number of entries added " + "(%lu)", + cnt, ARRAY_SIZE(inputs)); + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_get) +{ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + struct hmap_test_s key = { .key = inputs[i].key }; + struct hmap_test_s *expect = inputs + i; + struct hmap_entry *ent = hmap_get(map, &key.entry); + + assertneq(ent, NULL); + + struct hmap_test_s *got = entry_to_test_s(ent); + asserteq(expect, got); + } + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_get_next_dup) +{ + hmap_add(map, &duplicate.entry); + struct hmap_test_s key = { .key = duplicate.key }; + struct hmap_entry *ent = hmap_get(map, &key.entry); + + assertneq(ent, NULL); + + struct hmap_test_s *got = entry_to_test_s(ent); + + struct hmap_entry *next = hmap_get_next_dup(map, ent); + + assertneq(next, NULL); + + struct hmap_test_s *got_dup = entry_to_test_s(next); + if (got->data != duplicate.data) { + asserteq(got_dup->data, duplicate.data); + } else { + assertneq(got_dup->data, duplicate.data); + } + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_remove) +{ + struct hmap_entry *removed; + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + struct hmap_test_s key = { .key = inputs[i].key }; + removed = hmap_remove(map, &key.entry); + + assertneq(removed, NULL); + } + + expect(hmap_entry_cnt(map) == 1, "expected only duplicate entry left"); + removed = hmap_remove(map, &duplicate.entry); + asserteq(removed, &duplicate.entry); + + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_realloc) +{ + /* This test case assumes default hmap settings */ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + expect(hmap_cur_cap(map) <= 64, "hashmap shouldn't grow so fast"); + + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_add(map, &inputs2[i].entry); + } + asserteq(hmap_entry_cnt(map), ARRAY_SIZE(inputs) + ARRAY_SIZE(inputs2)); + expect(hmap_cur_cap(map) > 64, "expected hashmap to grow"); + + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_remove(map, &inputs2[i].entry); + } + expect(hmap_cur_cap(map) <= 64, "expected hashmap to shrink"); + + TEST_OUT + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_remove(map, &inputs[i].entry); + } +} +TEST_END + +TEST_BEGIN(test_hmap_iter) +{ + struct hmap_iter iter; + struct hmap_entry *ent, *prev = NULL; + size_t cnt = 0; + + hmap_iter_init(&iter, map); + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + + hmap_iter_foreach(&iter, ent) { + cnt++; + expect(ent != prev, "hmap_iter shouldn't return same entry on next"); + } + asserteq(cnt, ARRAY_SIZE(inputs)); + + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_iter_remove) +{ + struct hmap_iter iter; + struct hmap_entry *ent; + + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_add(map, &inputs2[i].entry); + } + + hmap_dynamic_set(map, false); + expect(!hmap_dynamic_get(map), "expected dynamic setting to be off"); + + hmap_iter_init(&iter, map); + hmap_iter_foreach(&iter, ent) { + expect(hmap_remove(map, ent), "expected entry to be removed"); + } + asserteq(hmap_entry_cnt(map), 0); + + hmap_dynamic_set(map, true); + expect(hmap_dynamic_get(map), "expected dynamic setting to be on"); + + TEST_OUT +} +TEST_END + +#else + +TEST_BEGIN(test_hmap_collisions) +{ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_add(map, &inputs2[i].entry); + } + asserteq(hmap_entry_cnt(map), ARRAY_SIZE(inputs) + ARRAY_SIZE(inputs2)); + TEST_OUT +} +TEST_END + +#endif /* HMAP_DEBUG */ + +void hmap_test_init(void) +{ +#ifdef HMAP_DEBUG +#ifndef HMAP_DEBUG_CAP +#define HMAP_DEBUG_CAP 128 +#endif /* HMAP_DEBUG_CAP */ + map = hmap_new_with(hmap_test_cmp, hmap_test_hash, HMAP_DEBUG_CAP, false); +#else + map = hmap_new(hmap_test_cmp, hmap_test_hash); +#endif /* HMAP_DEBUG */ +} + +void hmap_test_destroy(void) +{ + hmap_free(map); +} + +#ifdef HMAP_DEBUG + +RUN_TEST_SUITE(hmap_test_init, hmap_test_destroy, test_hmap_collisions); + +#else + +RUN_TEST_SUITE(hmap_test_init, hmap_test_destroy, test_hmap_add, test_hmap_get, + test_hmap_get_next_dup, test_hmap_remove, test_hmap_realloc, + test_hmap_iter, test_hmap_iter_remove) + +#endif /* HMAP_DEBUG */ diff --git a/hmap/hmap.c b/hmap/hmap.c new file mode 100644 index 0000000..8bc5760 --- /dev/null +++ b/hmap/hmap.c @@ -0,0 +1,297 @@ +/* SPDX-License-Identifier: MIT */ +#include "hmap.h" + +#include +#include +#include +#ifdef HMAP_DEBUG +#include +#endif + +#ifndef HMAP_LOAD_FACTOR +#define HMAP_LOAD_FACTOR 80 +#endif +#ifndef HMAP_GROWTH_RATE +#define HMAP_GROWTH_RATE 2 +#endif + +/** + * Structures + * ========== + */ + +/** + * struct hmap - generic hash map. + * @buckets: table where we store our buckets. + * @cap: current capacity. + * @cnt: how many entries we currently hold. + * @grow_at: load factor at which we grow. > 100 if hmap is not dynamic. + * @shrink_at: load factor at which we shrink. + * @cmp: key compare function. + */ +struct hmap { + struct hmap_entry **buckets; + + size_t cap; + size_t cnt; + + size_t grow_at; + size_t shrink_at; + + hmap_cmp_fn cmp; + hmap_hash_fn hash_key; + + uint8_t dynamic : 1; +}; + +/** + * Internal methods + * ================ + */ + +/** + * find_hmap_bucket() - find the bucket for @key. + * @map: hashmap. + * @key: key with hash. + * + * Return: pointer to bucket in buckets table. + */ +static inline struct hmap_entry **find_hmap_bucket(struct hmap *map, + struct hmap_entry *key) +{ + size_t i = key->hash % map->cap; + + return map->buckets + i; +} + +/** + * find_hmap_entry() - find entry that has @key. + * @map: hashmap. + * @key: key with hash. + * + * Return: pointer where the entry is stored. + */ +static struct hmap_entry **find_hmap_entry(struct hmap *map, + struct hmap_entry *key) +{ + map->hash_key(key); + + struct hmap_entry **ptr = find_hmap_bucket(map, key); + while (*ptr) { + if (map->cmp(*ptr, key)) { + return ptr; + } + ptr = &(*ptr)->next; + } + + return ptr; +} + +/** + * __hmap_add() -- low level add function. + * @map: hashmap. + * @ent: entry to add. + */ +static void __hmap_add(struct hmap *map, struct hmap_entry *ent) +{ + struct hmap_entry **bucket = find_hmap_bucket(map, ent); + if (*bucket) { + struct hmap_entry *coll = *bucket; + struct hmap_entry *next = coll->next; +#ifdef HMAP_DEBUG + fprintf(stderr, "\nCOLLISION!\n"); +#endif + while (next) { +#ifdef HMAP_DEBUG + fprintf(stderr, "\nCOLLISION!\n"); +#endif + coll = next; + next = coll->next; + } + coll->next = ent; + } else { + *bucket = ent; + } +} + +/** + * set_thresholds() - set growth and shrink thresholds. + * @map: hashmap. + */ +static inline void set_thresholds(struct hmap *map) +{ + map->grow_at = map->cap * HMAP_LOAD_FACTOR / 100; + if (map->cap <= HMAP_INIT_CAP) { + map->shrink_at = 0; + } else { + map->shrink_at = map->grow_at / HMAP_GROWTH_RATE - 2; + } +} + +/** + * alloc_buckets() - allocate buckets table. + * @map: hashmap. + */ +static inline void alloc_buckets(struct hmap *map) +{ + map->buckets = calloc(map->cap, sizeof(struct hmap_entry *)); +} + +/** + * maybe_realloc() - grow/shrink buckets table if needed. + * @map: hashmap. + */ +static void maybe_realloc(struct hmap *map) +{ + if (!map->dynamic) { + return; + } + + size_t oldcap = map->cap; + + if (map->cnt >= map->grow_at) { + map->cap = map->cap * HMAP_GROWTH_RATE; + } else if (map->cnt < map->shrink_at) { + map->cap = map->cap / HMAP_GROWTH_RATE; + } else { + return; + } + + struct hmap_entry **oldbucks = map->buckets; + + alloc_buckets(map); + set_thresholds(map); + + for (size_t i = 0; i < oldcap; i++) { + struct hmap_entry *next = oldbucks[i], *cur; + while (next) { + cur = next; + next = cur->next; + cur->next = NULL; + __hmap_add(map, cur); + } + } + + free(oldbucks); +} + +/** + * Public methods + * ============== + */ + +struct hmap *hmap_new_with(hmap_cmp_fn cmp_fn, hmap_hash_fn hash_fn, size_t cap, + bool dynamic) +{ + struct hmap *map = malloc(sizeof(*map)); + + map->cap = cap; + map->cnt = 0; + map->cmp = cmp_fn; + map->hash_key = hash_fn; + map->dynamic = dynamic; + alloc_buckets(map); + if (dynamic) { + set_thresholds(map); + } + + return map; +} + +void hmap_add(struct hmap *map, struct hmap_entry *ent) +{ + ent->next = NULL; + map->hash_key(ent); + + map->cnt++; + maybe_realloc(map); + + __hmap_add(map, ent); +} + +struct hmap_entry *hmap_get(struct hmap *map, struct hmap_entry *key) +{ + return *find_hmap_entry(map, key); +} + +struct hmap_entry *hmap_get_next_dup(struct hmap *map, struct hmap_entry *ent) +{ + struct hmap_entry *next = ent->next; + while (next) { + if (map->cmp(next, ent)) { + return next; + } + } + + return next; +} + +struct hmap_entry *hmap_remove(struct hmap *map, struct hmap_entry *key) +{ + struct hmap_entry **ptr = find_hmap_entry(map, key), *old; + + if (*ptr) { + if (map->cmp(*ptr, key)) { + old = *ptr; + *ptr = old->next; + + map->cnt--; + maybe_realloc(map); + + return old; + } + } + + return NULL; +} + +size_t hmap_entry_cnt(struct hmap *map) +{ + return map->cnt; +} + +size_t hmap_cur_cap(struct hmap *map) +{ + return map->cap; +} + +void hmap_dynamic_set(struct hmap *map, bool on) +{ + map->dynamic = on; +} + +bool hmap_dynamic_get(struct hmap *map) +{ + return map->dynamic; +} + +void hmap_free(struct hmap *map) +{ + free(map->buckets); + free(map); +} + +void hmap_iter_init(struct hmap_iter *iter, struct hmap *map) +{ + iter->map = map; + iter->cursor = 0; + iter->next = NULL; +} + +struct hmap_entry *hmap_iter_next(struct hmap_iter *iter) +{ + struct hmap_entry *cur = iter->next; + + for (;;) { + if (cur) { + iter->next = cur->next; + return cur; + } + + if (iter->cursor >= iter->map->cap) { + return NULL; + } + + cur = iter->map->buckets[iter->cursor++]; + } +} diff --git a/hmap/hmap.h b/hmap/hmap.h new file mode 100644 index 0000000..bbd95f3 --- /dev/null +++ b/hmap/hmap.h @@ -0,0 +1,238 @@ +/* SPDX-License-Identifier: LGPL-2.1 */ +/** + * hmap.h - a simple generic hashmap. v2.0.0 + * + * Copyright (c) 2022-2023 - Yaroslav de la Peña Smirnov + * + * Documentation + * ============= + * + * In order to use this hashmap, you need to incapsulate struct hmap_entry + * inside your own structure. For example:: + * + * struct my_struct { + * char *key; + * uint64_t data; + * struct hmap_entry entry; + * }; + * + * Then you can insert any instance of such struct into the hashmap by calling + * the corresponding method and passing it the pointer to @entry. + * + * For search and removal operations you just need to fill your structure with + * your key. The hmap_cmp_fn and hmap_hash_fn functions you provided will be + * called by hmap in order to perform the needed operations. + * + * When you get a hmap_entry pointer from hmap's API, you can get your + * containing structure with the help of the hmap_item macro, for example:: + * + * struct hmap_entry *e = hmap_get(map, key); + * struct my_struct *my = hmap_item(e, struct my_struct, entry); + * + */ +#ifndef HMAP_H +#define HMAP_H +#include "../utils.h" + +#include +#include +#include + +#ifndef HMAP_INIT_CAP +#define HMAP_INIT_CAP 64 +#endif + +/** + * Structures + * ========== + */ + +/** + * struct hmap - opaque structure for generic hashmap. + */ +struct hmap; + +/** + * struct hmap_entry - the base class for a hashmap entry. + * @next: linked list in case of collisions. + * @hash: the hash value of the entry key. + * + * This structure should only be manipulated using the methods below. The @hash + * member should be filled by the hmap_hash_fn function provided to hmap_new(). + */ +struct hmap_entry { + struct hmap_entry *next; + size_t hash; +}; + +/** + * struct hmap_iter - iterator over hmap entries. + * @map: hashmap. + * @next: next item to be returned. + * @cursor: current position in buckets table. + * + * If you want to remove entries while iterating, be sure to change the dynamic + * resizing setting to on = false with hmap_dynamic_get(). + */ +struct hmap_iter { + struct hmap *map; + struct hmap_entry *next; + size_t cursor; +}; + +/** + * Typedefs + * ======== + */ + +typedef bool (*hmap_cmp_fn)(const struct hmap_entry *ent, + const struct hmap_entry *key); +typedef void (*hmap_hash_fn)(struct hmap_entry *ent); + +/** + * Methods + * ======= + */ + +/** + * hmap_new_with() - allocate new hashmap with given parameters. + * @cmp_fn: key comparison function. + * @hash_fn: key hashing function. + * @cap: initial hashmap capacity. + * @dynamic: whether the hashmap should dynamically grow/shrink based on load + * factor. + * + * Return: pointer to hmap object. + */ +struct hmap *hmap_new_with(hmap_cmp_fn cmp_fn, hmap_hash_fn hash_fn, size_t cap, + bool dynamic); + +/** + * hmap_new - allocate new hashmap with default parameters. + * @cmp_fn: key comparison function. + * @hash_fn: key hashing function. + * + * Return: pointer to hmap object. + */ +#define hmap_new(cmp_fn, hash_fn) \ + hmap_new_with(cmp_fn, hash_fn, HMAP_INIT_CAP, true) + +/** + * hmap_free() - free all resources used by @map. + * @map: hashmap. + * + * This function does not release or free any resources associated with any + * entries stored in the hashmap. It is the responsibility of the caller to free + * any such resources. + */ +void hmap_free(struct hmap *map); + +/** + * hmap_item - get the pointer to the containing structure for this entry. + * @entry: struct hmap_entry pointer. + * @type: containing struct. + * @member: the member in the struct that holds hmap_entry. + */ +#define hmap_item(entry, type, member) container_of(entry, type, member) + +/** + * hmap_add() - add entry to @map. + * @map: hashmap. + * @ent: entry to add. + * + * If there's already an entry with the same key, it wil still add it and hold + * both. + */ +void hmap_add(struct hmap *map, struct hmap_entry *ent); + +/** + * hmap_get() - get entry with @key from @map. + * @map: hashmap. + * @key: hmap_entry object that holds the key. + * + * In order to pass the key, you just need to fill what is needed by your + * hashing and comparison functions; you could even use a separate structure + * that just holds the key, if you use the appropriate logic in your functions. + * + * If there are entries with duplicate keys, it will get the first it finds. If + * your want to get the next duplicate-key entry use hmap_get_next_dup(). + * + * Return: pointer to entry; NULL if no entry with such key. + */ +struct hmap_entry *hmap_get(struct hmap *map, struct hmap_entry *key); + +/** + * hmap_get_next_dup() - get the next entry with the same key as @ent. + * @map: hashmap. + * @ent: entry with duplicate key. + * + * Return: pointer to entry; NULL if no more entries with same key. + */ +struct hmap_entry *hmap_get_next_dup(struct hmap *map, struct hmap_entry *ent); + +/** + * hmap_remove() - remove entry with @key from @map. + * @map: hashmap. + * @key: hmap_entry object that holds the key. + * + * If there are entries with duplicates keys, it will remove the first it finds. + * + * Return: pointer to removed entry; NULL if no entry with such key. + */ +struct hmap_entry *hmap_remove(struct hmap *map, struct hmap_entry *key); + +/** + * hmap_entry_cnt() - get the current number of entries in @map. + * @map: hashmap. + * + * Return: number of entries held by @map. + */ +size_t hmap_entry_cnt(struct hmap *map); + +/** + * hmap_dynamic_set() - enable/disable hashmap resizing. + * @map: hashmap. + * @on: whether to turn on/off. + */ +void hmap_dynamic_set(struct hmap *map, bool on); + +/** + * hmap_dynamic_get() - get current hashmap resizing setting. + * @map: hashmap. + * + * Return: current dynamic resizing setting. + */ +bool hmap_dynamic_get(struct hmap *map); + +/** + * hmap_cur_cap() - get the current capacity of @map. + * @map: hashmap. + * + * Return: current @map capacity. + */ +size_t hmap_cur_cap(struct hmap *map); + +/** + * hmap_iter_init() - initialize and reset hmap iterator. + * @iter: pointer to hmap_iter object. + * @map: hashmap to iterate over. + */ +void hmap_iter_init(struct hmap_iter *iter, struct hmap *map); + +/** + * hmap_iter_next() - get the next entry. + * @iter: iterator. + * + * Return: pointer to entry; NULL if no more entries are left. + */ +struct hmap_entry *hmap_iter_next(struct hmap_iter *iter); + +/** + * hmap_iter_foreach - loop to iterate over every entry. + * @iter: pointer to iterator. + * @entry: hmap_entry pointer to hold the next entry. + */ +#define hmap_iter_foreach(iter, entry) \ + for (entry = hmap_iter_next((iter)); entry; entry = hmap_iter_next((iter))) + +#endif /* HMAP_H */ diff --git a/licenses/LGPL-2.1 b/licenses/LGPL-2.1 new file mode 100644 index 0000000..d38b1b9 --- /dev/null +++ b/licenses/LGPL-2.1 @@ -0,0 +1,511 @@ + + While most of this project is under the GPL (see COPYING), the xdiff/ + library and some libc code from compat/ are licensed under the + GNU LGPL, version 2.1 or (at your option) any later version and some + other files are under other licenses. Check the individual files to + be sure. + +---------------------------------------- + + GNU LESSER GENERAL PUBLIC LICENSE + Version 2.1, February 1999 + + Copyright (C) 1991, 1999 Free Software Foundation, Inc. + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + +[This is the first released version of the Lesser GPL. It also counts + as the successor of the GNU Library Public License, version 2, hence + the version number 2.1.] + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +Licenses are intended to guarantee your freedom to share and change +free software--to make sure the software is free for all its users. + + This license, the Lesser General Public License, applies to some +specially designated software packages--typically libraries--of the +Free Software Foundation and other authors who decide to use it. You +can use it too, but we suggest you first think carefully about whether +this license or the ordinary General Public License is the better +strategy to use in any particular case, based on the explanations below. + + When we speak of free software, we are referring to freedom of use, +not price. Our General Public Licenses are designed to make sure that +you have the freedom to distribute copies of free software (and charge +for this service if you wish); that you receive source code or can get +it if you want it; that you can change the software and use pieces of +it in new free programs; and that you are informed that you can do +these things. + + To protect your rights, we need to make restrictions that forbid +distributors to deny you these rights or to ask you to surrender these +rights. These restrictions translate to certain responsibilities for +you if you distribute copies of the library or if you modify it. + + For example, if you distribute copies of the library, whether gratis +or for a fee, you must give the recipients all the rights that we gave +you. You must make sure that they, too, receive or can get the source +code. If you link other code with the library, you must provide +complete object files to the recipients, so that they can relink them +with the library after making changes to the library and recompiling +it. And you must show them these terms so they know their rights. + + We protect your rights with a two-step method: (1) we copyright the +library, and (2) we offer you this license, which gives you legal +permission to copy, distribute and/or modify the library. + + To protect each distributor, we want to make it very clear that +there is no warranty for the free library. Also, if the library is +modified by someone else and passed on, the recipients should know +that what they have is not the original version, so that the original +author's reputation will not be affected by problems that might be +introduced by others. + + Finally, software patents pose a constant threat to the existence of +any free program. We wish to make sure that a company cannot +effectively restrict the users of a free program by obtaining a +restrictive license from a patent holder. Therefore, we insist that +any patent license obtained for a version of the library must be +consistent with the full freedom of use specified in this license. + + Most GNU software, including some libraries, is covered by the +ordinary GNU General Public License. This license, the GNU Lesser +General Public License, applies to certain designated libraries, and +is quite different from the ordinary General Public License. We use +this license for certain libraries in order to permit linking those +libraries into non-free programs. + + When a program is linked with a library, whether statically or using +a shared library, the combination of the two is legally speaking a +combined work, a derivative of the original library. The ordinary +General Public License therefore permits such linking only if the +entire combination fits its criteria of freedom. The Lesser General +Public License permits more lax criteria for linking other code with +the library. + + We call this license the "Lesser" General Public License because it +does Less to protect the user's freedom than the ordinary General +Public License. It also provides other free software developers Less +of an advantage over competing non-free programs. These disadvantages +are the reason we use the ordinary General Public License for many +libraries. However, the Lesser license provides advantages in certain +special circumstances. + + For example, on rare occasions, there may be a special need to +encourage the widest possible use of a certain library, so that it becomes +a de-facto standard. To achieve this, non-free programs must be +allowed to use the library. A more frequent case is that a free +library does the same job as widely used non-free libraries. In this +case, there is little to gain by limiting the free library to free +software only, so we use the Lesser General Public License. + + In other cases, permission to use a particular library in non-free +programs enables a greater number of people to use a large body of +free software. For example, permission to use the GNU C Library in +non-free programs enables many more people to use the whole GNU +operating system, as well as its variant, the GNU/Linux operating +system. + + Although the Lesser General Public License is Less protective of the +users' freedom, it does ensure that the user of a program that is +linked with the Library has the freedom and the wherewithal to run +that program using a modified version of the Library. + + The precise terms and conditions for copying, distribution and +modification follow. Pay close attention to the difference between a +"work based on the library" and a "work that uses the library". The +former contains code derived from the library, whereas the latter must +be combined with the library in order to run. + + GNU LESSER GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License Agreement applies to any software library or other +program which contains a notice placed by the copyright holder or +other authorized party saying it may be distributed under the terms of +this Lesser General Public License (also called "this License"). +Each licensee is addressed as "you". + + A "library" means a collection of software functions and/or data +prepared so as to be conveniently linked with application programs +(which use some of those functions and data) to form executables. + + The "Library", below, refers to any such software library or work +which has been distributed under these terms. A "work based on the +Library" means either the Library or any derivative work under +copyright law: that is to say, a work containing the Library or a +portion of it, either verbatim or with modifications and/or translated +straightforwardly into another language. (Hereinafter, translation is +included without limitation in the term "modification".) + + "Source code" for a work means the preferred form of the work for +making modifications to it. For a library, complete source code means +all the source code for all modules it contains, plus any associated +interface definition files, plus the scripts used to control compilation +and installation of the library. + + Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running a program using the Library is not restricted, and output from +such a program is covered only if its contents constitute a work based +on the Library (independent of the use of the Library in a tool for +writing it). Whether that is true depends on what the Library does +and what the program that uses the Library does. + + 1. You may copy and distribute verbatim copies of the Library's +complete source code as you receive it, in any medium, provided that +you conspicuously and appropriately publish on each copy an +appropriate copyright notice and disclaimer of warranty; keep intact +all the notices that refer to this License and to the absence of any +warranty; and distribute a copy of this License along with the +Library. + + You may charge a fee for the physical act of transferring a copy, +and you may at your option offer warranty protection in exchange for a +fee. + + 2. You may modify your copy or copies of the Library or any portion +of it, thus forming a work based on the Library, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) The modified work must itself be a software library. + + b) You must cause the files modified to carry prominent notices + stating that you changed the files and the date of any change. + + c) You must cause the whole of the work to be licensed at no + charge to all third parties under the terms of this License. + + d) If a facility in the modified Library refers to a function or a + table of data to be supplied by an application program that uses + the facility, other than as an argument passed when the facility + is invoked, then you must make a good faith effort to ensure that, + in the event an application does not supply such function or + table, the facility still operates, and performs whatever part of + its purpose remains meaningful. + + (For example, a function in a library to compute square roots has + a purpose that is entirely well-defined independent of the + application. Therefore, Subsection 2d requires that any + application-supplied function or table used by this function must + be optional: if the application does not supply it, the square + root function must still compute square roots.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Library, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Library, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote +it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Library. + +In addition, mere aggregation of another work not based on the Library +with the Library (or with a work based on the Library) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may opt to apply the terms of the ordinary GNU General Public +License instead of this License to a given copy of the Library. To do +this, you must alter all the notices that refer to this License, so +that they refer to the ordinary GNU General Public License, version 2, +instead of to this License. (If a newer version than version 2 of the +ordinary GNU General Public License has appeared, then you can specify +that version instead if you wish.) Do not make any other change in +these notices. + + Once this change is made in a given copy, it is irreversible for +that copy, so the ordinary GNU General Public License applies to all +subsequent copies and derivative works made from that copy. + + This option is useful when you wish to copy part of the code of +the Library into a program that is not a library. + + 4. You may copy and distribute the Library (or a portion or +derivative of it, under Section 2) in object code or executable form +under the terms of Sections 1 and 2 above provided that you accompany +it with the complete corresponding machine-readable source code, which +must be distributed under the terms of Sections 1 and 2 above on a +medium customarily used for software interchange. + + If distribution of object code is made by offering access to copy +from a designated place, then offering equivalent access to copy the +source code from the same place satisfies the requirement to +distribute the source code, even though third parties are not +compelled to copy the source along with the object code. + + 5. A program that contains no derivative of any portion of the +Library, but is designed to work with the Library by being compiled or +linked with it, is called a "work that uses the Library". Such a +work, in isolation, is not a derivative work of the Library, and +therefore falls outside the scope of this License. + + However, linking a "work that uses the Library" with the Library +creates an executable that is a derivative of the Library (because it +contains portions of the Library), rather than a "work that uses the +library". The executable is therefore covered by this License. +Section 6 states terms for distribution of such executables. + + When a "work that uses the Library" uses material from a header file +that is part of the Library, the object code for the work may be a +derivative work of the Library even though the source code is not. +Whether this is true is especially significant if the work can be +linked without the Library, or if the work is itself a library. The +threshold for this to be true is not precisely defined by law. + + If such an object file uses only numerical parameters, data +structure layouts and accessors, and small macros and small inline +functions (ten lines or less in length), then the use of the object +file is unrestricted, regardless of whether it is legally a derivative +work. (Executables containing this object code plus portions of the +Library will still fall under Section 6.) + + Otherwise, if the work is a derivative of the Library, you may +distribute the object code for the work under the terms of Section 6. +Any executables containing that work also fall under Section 6, +whether or not they are linked directly with the Library itself. + + 6. As an exception to the Sections above, you may also combine or +link a "work that uses the Library" with the Library to produce a +work containing portions of the Library, and distribute that work +under terms of your choice, provided that the terms permit +modification of the work for the customer's own use and reverse +engineering for debugging such modifications. + + You must give prominent notice with each copy of the work that the +Library is used in it and that the Library and its use are covered by +this License. You must supply a copy of this License. If the work +during execution displays copyright notices, you must include the +copyright notice for the Library among them, as well as a reference +directing the user to the copy of this License. Also, you must do one +of these things: + + a) Accompany the work with the complete corresponding + machine-readable source code for the Library including whatever + changes were used in the work (which must be distributed under + Sections 1 and 2 above); and, if the work is an executable linked + with the Library, with the complete machine-readable "work that + uses the Library", as object code and/or source code, so that the + user can modify the Library and then relink to produce a modified + executable containing the modified Library. (It is understood + that the user who changes the contents of definitions files in the + Library will not necessarily be able to recompile the application + to use the modified definitions.) + + b) Use a suitable shared library mechanism for linking with the + Library. A suitable mechanism is one that (1) uses at run time a + copy of the library already present on the user's computer system, + rather than copying library functions into the executable, and (2) + will operate properly with a modified version of the library, if + the user installs one, as long as the modified version is + interface-compatible with the version that the work was made with. + + c) Accompany the work with a written offer, valid for at + least three years, to give the same user the materials + specified in Subsection 6a, above, for a charge no more + than the cost of performing this distribution. + + d) If distribution of the work is made by offering access to copy + from a designated place, offer equivalent access to copy the above + specified materials from the same place. + + e) Verify that the user has already received a copy of these + materials or that you have already sent this user a copy. + + For an executable, the required form of the "work that uses the +Library" must include any data and utility programs needed for +reproducing the executable from it. However, as a special exception, +the materials to be distributed need not include anything that is +normally distributed (in either source or binary form) with the major +components (compiler, kernel, and so on) of the operating system on +which the executable runs, unless that component itself accompanies +the executable. + + It may happen that this requirement contradicts the license +restrictions of other proprietary libraries that do not normally +accompany the operating system. Such a contradiction means you cannot +use both them and the Library together in an executable that you +distribute. + + 7. You may place library facilities that are a work based on the +Library side-by-side in a single library together with other library +facilities not covered by this License, and distribute such a combined +library, provided that the separate distribution of the work based on +the Library and of the other library facilities is otherwise +permitted, and provided that you do these two things: + + a) Accompany the combined library with a copy of the same work + based on the Library, uncombined with any other library + facilities. This must be distributed under the terms of the + Sections above. + + b) Give prominent notice with the combined library of the fact + that part of it is a work based on the Library, and explaining + where to find the accompanying uncombined form of the same work. + + 8. You may not copy, modify, sublicense, link with, or distribute +the Library except as expressly provided under this License. Any +attempt otherwise to copy, modify, sublicense, link with, or +distribute the Library is void, and will automatically terminate your +rights under this License. However, parties who have received copies, +or rights, from you under this License will not have their licenses +terminated so long as such parties remain in full compliance. + + 9. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Library or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Library (or any work based on the +Library), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Library or works based on it. + + 10. Each time you redistribute the Library (or any work based on the +Library), the recipient automatically receives a license from the +original licensor to copy, distribute, link with or modify the Library +subject to these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties with +this License. + + 11. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Library at all. For example, if a patent +license would not permit royalty-free redistribution of the Library by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Library. + +If any portion of this section is held invalid or unenforceable under any +particular circumstance, the balance of the section is intended to apply, +and the section as a whole is intended to apply in other circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 12. If the distribution and/or use of the Library is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Library under this License may add +an explicit geographical distribution limitation excluding those countries, +so that distribution is permitted only in or among countries not thus +excluded. In such case, this License incorporates the limitation as if +written in the body of this License. + + 13. The Free Software Foundation may publish revised and/or new +versions of the Lesser General Public License from time to time. +Such new versions will be similar in spirit to the present version, +but may differ in detail to address new problems or concerns. + +Each version is given a distinguishing version number. If the Library +specifies a version number of this License which applies to it and +"any later version", you have the option of following the terms and +conditions either of that version or of any later version published by +the Free Software Foundation. If the Library does not specify a +license version number, you may choose any version ever published by +the Free Software Foundation. + + 14. If you wish to incorporate parts of the Library into other free +programs whose distribution conditions are incompatible with these, +write to the author to ask for permission. For software which is +copyrighted by the Free Software Foundation, write to the Free +Software Foundation; we sometimes make exceptions for this. Our +decision will be guided by the two goals of preserving the free status +of all derivatives of our free software and of promoting the sharing +and reuse of software generally. + + NO WARRANTY + + 15. BECAUSE THE LIBRARY IS LICENSED FREE OF CHARGE, THERE IS NO +WARRANTY FOR THE LIBRARY, TO THE EXTENT PERMITTED BY APPLICABLE LAW. +EXCEPT WHEN OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR +OTHER PARTIES PROVIDE THE LIBRARY "AS IS" WITHOUT WARRANTY OF ANY +KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +PURPOSE. THE ENTIRE RISK AS TO THE QUALITY AND PERFORMANCE OF THE +LIBRARY IS WITH YOU. SHOULD THE LIBRARY PROVE DEFECTIVE, YOU ASSUME +THE COST OF ALL NECESSARY SERVICING, REPAIR OR CORRECTION. + + 16. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN +WRITING WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY +AND/OR REDISTRIBUTE THE LIBRARY AS PERMITTED ABOVE, BE LIABLE TO YOU +FOR DAMAGES, INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR +CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THE +LIBRARY (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING +RENDERED INACCURATE OR LOSSES SUSTAINED BY YOU OR THIRD PARTIES OR A +FAILURE OF THE LIBRARY TO OPERATE WITH ANY OTHER SOFTWARE), EVEN IF +SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH +DAMAGES. + + END OF TERMS AND CONDITIONS + + How to Apply These Terms to Your New Libraries + + If you develop a new library, and you want it to be of the greatest +possible use to the public, we recommend making it free software that +everyone can redistribute and change. You can do so by permitting +redistribution under these terms (or, alternatively, under the terms of the +ordinary General Public License). + + To apply these terms, attach the following notices to the library. It is +safest to attach them to the start of each source file to most effectively +convey the exclusion of warranty; and each file should have at least the +"copyright" line and a pointer to where the full notice is found. + + + Copyright (C) + + This library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with this library; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + +Also add information on how to contact you by electronic and paper mail. + +You should also get your employer (if you work as a programmer) or your +school, if any, to sign a "copyright disclaimer" for the library, if +necessary. Here is a sample; alter the names: + + Yoyodyne, Inc., hereby disclaims all copyright interest in the + library `Frob' (a library for tweaking knobs) written by James Random Hacker. + + , 1 April 1990 + Ty Coon, President of Vice + +That's all there is to it! diff --git a/licenses/MIT b/licenses/MIT new file mode 100644 index 0000000..b8f727e --- /dev/null +++ b/licenses/MIT @@ -0,0 +1,18 @@ +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. diff --git a/list/list.h b/list/list.h new file mode 100644 index 0000000..e944a0a --- /dev/null +++ b/list/list.h @@ -0,0 +1,205 @@ +/* + * Copyright (C) 2002 Free Software Foundation, Inc. + * (originally part of the GNU C Library and Userspace RCU; extracted from Git) + * Contributed by Ulrich Drepper , 2002. + * + * Copyright (C) 2009 Pierre-Marc Fournier + * Conversion to RCU list. + * Copyright (C) 2010 Mathieu Desnoyers + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, see + * . + */ + +#ifndef LIST_H +#define LIST_H 1 + +#include + +/* + * The definitions of this file are adopted from those which can be + * found in the Linux kernel headers to enable people familiar with the + * latter find their way in these sources as well. + */ + +/* Basic type for the double-link list. */ +struct list_head { + struct list_head *next, *prev; +}; + +/* avoid conflicts with BSD-only sys/queue.h */ +#undef LIST_HEAD +/* Define a variable with the head and tail of the list. */ +#define LIST_HEAD(name) struct list_head name = { &(name), &(name) } + +/* Initialize a new list head. */ +#define INIT_LIST_HEAD(ptr) (ptr)->next = (ptr)->prev = (ptr) + +#define LIST_HEAD_INIT(name) \ + { \ + .next = &(name), .prev = &(name), \ + } + +/* Add new element at the head of the list. */ +static inline void list_add(struct list_head *newp, struct list_head *head) +{ + head->next->prev = newp; + newp->next = head->next; + newp->prev = head; + head->next = newp; +} + +/* Add new element at the tail of the list. */ +static inline void list_add_tail(struct list_head *newp, struct list_head *head) +{ + head->prev->next = newp; + newp->next = head; + newp->prev = head->prev; + head->prev = newp; +} + +/* Remove element from list. */ +static inline void __list_del(struct list_head *prev, struct list_head *next) +{ + next->prev = prev; + prev->next = next; +} + +/* Remove element from list. */ +static inline void list_del(struct list_head *elem) +{ + __list_del(elem->prev, elem->next); +} + +/* Remove element from list, initializing the element's list pointers. */ +static inline void list_del_init(struct list_head *elem) +{ + list_del(elem); + INIT_LIST_HEAD(elem); +} + +/* Delete from list, add to another list as head. */ +static inline void list_move(struct list_head *elem, struct list_head *head) +{ + __list_del(elem->prev, elem->next); + list_add(elem, head); +} + +/* Replace an old entry. */ +static inline void list_replace(struct list_head *old, struct list_head *newp) +{ + newp->next = old->next; + newp->prev = old->prev; + newp->prev->next = newp; + newp->next->prev = newp; +} + +/* Join two lists. */ +static inline void list_splice(struct list_head *add, struct list_head *head) +{ + /* Do nothing if the list which gets added is empty. */ + if (add != add->next) { + add->next->prev = head; + add->prev->next = head->next; + head->next->prev = add->prev; + head->next = add->next; + } +} + +/* Get typed element from list at a given position. */ +#define list_entry(ptr, type, member) \ + ((type *)((char *)(ptr)-offsetof(type, member))) + +/* Get first entry from a list. */ +#define list_first_entry(ptr, type, member) \ + list_entry((ptr)->next, type, member) + +/* Iterate forward over the elements of the list. */ +#define list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); pos = pos->next) + +/* + * Iterate forward over the elements list. The list elements can be + * removed from the list while doing this. + */ +#define list_for_each_safe(pos, p, head) \ + for (pos = (head)->next, p = pos->next; pos != (head); \ + pos = p, p = pos->next) + +/* Iterate backward over the elements of the list. */ +#define list_for_each_prev(pos, head) \ + for (pos = (head)->prev; pos != (head); pos = pos->prev) + +/* + * Iterate backwards over the elements list. The list elements can be + * removed from the list while doing this. + */ +#define list_for_each_prev_safe(pos, p, head) \ + for (pos = (head)->prev, p = pos->prev; pos != (head); \ + pos = p, p = pos->prev) + +static inline int list_empty(struct list_head *head) +{ + return head == head->next; +} + +static inline void list_replace_init(struct list_head *old, + struct list_head *newp) +{ + struct list_head *head = old->next; + + list_del(old); + list_add_tail(newp, head); + INIT_LIST_HEAD(old); +} + +/* + * This is exactly the same as a normal list_head, except that it can be + * declared volatile (e.g., if you have a list that may be accessed from signal + * handlers). + */ +struct volatile_list_head { + volatile struct volatile_list_head *next, *prev; +}; + +#define VOLATILE_LIST_HEAD(name) \ + volatile struct volatile_list_head name = { &(name), &(name) } + +static inline void __volatile_list_del(volatile struct volatile_list_head *prev, + volatile struct volatile_list_head *next) +{ + next->prev = prev; + prev->next = next; +} + +static inline void volatile_list_del(volatile struct volatile_list_head *elem) +{ + __volatile_list_del(elem->prev, elem->next); +} + +static inline int volatile_list_empty(volatile struct volatile_list_head *head) +{ + return head == head->next; +} + +static inline void volatile_list_add(volatile struct volatile_list_head *newp, + volatile struct volatile_list_head *head) +{ + head->next->prev = newp; + newp->next = head->next; + newp->prev = head; + head->next = newp; +} + +#endif /* LIST_H */ diff --git a/optional/Makefile b/optional/Makefile new file mode 100644 index 0000000..32e87b2 --- /dev/null +++ b/optional/Makefile @@ -0,0 +1,5 @@ +CC?=gcc +CFLAGS+=-Wall -Werror -Wno-unused -std=gnu11 -Og -g + +all: + $(CC) $(CFLAGS) -o optional-test optional-test.c diff --git a/optional/README.md b/optional/README.md new file mode 100644 index 0000000..c039b85 --- /dev/null +++ b/optional/README.md @@ -0,0 +1,12 @@ +# Optional + +Poor man's optional "type templates" for C. Just for fun. + +In its current form it's intended to be used with "single token" types. Might +or might not "make it compatible" with structs, enums, unions, etc. in the +future, if the need arises. + +## Example usage + +If you want to see an example on how to use optional, take a look at +`optional-test.c`. diff --git a/optional/optional-test.c b/optional/optional-test.c new file mode 100644 index 0000000..88577d3 --- /dev/null +++ b/optional/optional-test.c @@ -0,0 +1,55 @@ +#include "optional.h" +#include "../utest/utest.h" + +#include + +OPTIONALDEC(int); +OPTIONALDEC(char); + +struct my_struct { + OPTIONAL(int) a; + OPTIONAL(int) b; +}; + +void optput(OPTIONAL(char) * dst, char src) +{ + opt_set_some(*dst, src); +} + +TEST_BEGIN(test_optional_example) +{ + int a, b; + + struct my_struct my = { + .a = OPTSOME(69), + .b = OPTNONE, + }; + + OPTIONAL(char) y = OPTNONE; + OPTIONAL(char) z = OPTSOME('z'); + float xy, xz; + + expect(opt_has(my.a), "expected to contain something"); + expect(opt_unwrap(my.a, a), "expected to contain something"); + asserteq(a, 69); + + expect(!opt_unwrap(my.b, b), "expected to contain nothing"); + + optput(&y, 'y'); + opt_set_none(z); + + expect(opt_unwrap(y, xy), "expected to contain something"); + asserteq(xy, 'y'); + + expect(!opt_unwrap(z, xz), "expected to contain nothing"); + + xy = opt_default(y, 'd'), xz = opt_default(z, 'd'); + + asserteq(xy, 'y'); + asserteq(xz, 'd'); + + TEST_OUT +} +TEST_END + +RUN_TESTS(test_optional_example) diff --git a/optional/optional.h b/optional/optional.h new file mode 100644 index 0000000..6dcc3e2 --- /dev/null +++ b/optional/optional.h @@ -0,0 +1,92 @@ +/* SPDX-License-Identifier: MIT */ +/** + * optional.h - Macros for optional types. v0.1.0 + * + * Copyright (C) 2023 Yaroslav de la Peña Smirnov + * + * Documentation + * ============= + * + * Poor man's optional "type templates" for C. + * + * An object of optional type is an object that may or may not hold an object of + * a certain type inside itself at any time. Before declaring a variable of a + * certain OPTIONAL type, said OPTIONAL type should be declared with the + * OPTIONALDEC macro. + * + * Currently only supports types that are composed of one token, i.e. no + * structs, enums, unions, etc. Might expand it in the future to support them. + */ + +#ifndef OPTIONAL_H +#define OPTIONAL_H + +#include + +/** + * OPTIONALDEC - declare OPTIONAL type that holds data of type @T + * @T: the type of data to hold. + */ +#define OPTIONALDEC(T) struct __OPTIONAL_##T { bool has; T data; } + +/** + * OPTIONAL - declare an object that optionally holds type @T + * @T: the type of data to hold. + */ +#define OPTIONAL(T) struct __OPTIONAL_##T + +/** + * OPTNONE - initialize an OPTIONAL object to hold nothing. + */ +#define OPTNONE { .has = false } + +/** + * OPTSOME - initialize an OPTIONAL object to hold something. + * @d: data to hold. + */ +#define OPTSOME(d) { .has = true, .data = d } + +/** + * opt_set_none - set an OPTIONAL object to hold nothing. + * @opt: OPTIONAL object. + */ +#define opt_set_none(opt) opt.has = false + +/** + * opt_set_some - set an OPTIONAL object to hold something. + * @opt: OPTIONAL object. + * @d: data to hold. + */ +#define opt_set_some(opt, d) \ + ((opt).has = true, (opt).data = d) + +/** + * opt_has - true if an OPTIONAL object has something. + * @opt: OPTIONAL object. + */ +#define opt_has(opt) ((opt).has) + +/** + * opt_hasnt - true if an OPTIONAL object has nothing. + * @opt: OPTIONAL object. + */ +#define opt_hasnt(opt) (!(opt).has) + +/** + * opt_unwrap - if there's something in @src, copy it to @dst. + * @src: OPTIONAL object to copy data of type T from. + * @dst: variable of type T to copy to. + * + * Returns true if there was something, false if there wasn't. + */ +#define opt_unwrap(src, dst) \ + (opt_has(src) ? (dst = (src).data, true) : (false)) + +/** + * opt_default - get something from @src or default to @def. + * @src: OPTIONAL object to get data from. + * @def: default value if there's nothing. + */ +#define opt_default(src, def) opt_has(src) ? (src).data : def + +#endif diff --git a/utest/Makefile b/utest/Makefile new file mode 100644 index 0000000..0ecb1c5 --- /dev/null +++ b/utest/Makefile @@ -0,0 +1,5 @@ +CC?=gcc +CFLAGS+=-Wall -Werror -Wno-unused -std=gnu11 -Og -g + +all: + $(CC) $(CFLAGS) -o utest-test utest-test.c diff --git a/utest/utest-test.c b/utest/utest-test.c new file mode 100644 index 0000000..591ee32 --- /dev/null +++ b/utest/utest-test.c @@ -0,0 +1,34 @@ +#include "utest.h" + +static int a, b; + +/* This should pass */ +TEST_BEGIN(test_pass) +{ + asserteq(a, 0); + assertneq(a, b); + expect(b > a, "expected b > a"); + TEST_OUT +} +TEST_END + +/* This should fail */ +TEST_BEGIN(test_fail) +{ + expect(0, "oopsie!"); + TEST_OUT +} +TEST_END + +void test_init(void) +{ + a = 0, b = 1; + printf("hello, world!\n\n"); +} + +void test_destroy(void) +{ + printf("\ngood bye!\n"); +} + +RUN_TEST_SUITE(test_init, test_destroy, test_pass, test_fail); diff --git a/utest/utest.h b/utest/utest.h new file mode 100644 index 0000000..218b2b7 --- /dev/null +++ b/utest/utest.h @@ -0,0 +1,221 @@ +/* SPDX-License-Identifier: LGPL-2.1 */ +/** + * utest.h - header-only unit testing micro "framework". v1.0.0 + * + * Copyright (c) 2021-2023 Yaroslav de la Peña Smirnov + */ +#ifndef UTEST_H +#define UTEST_H +#include +#include +#include +#include + +/* + * TODO?: test runners that run in different processes in order to not crash the + * whole test unit when a single test crashes. + */ + +/** + * Constants + * ========= + */ + +/** + * Terminal escape codes + * --------------------- + * + * TBLD: bold text. + * TRED: red text. + * TGRN: green text. + * TBLU: blue text. + * TRST: reset colors. + * TDEL: delete current line. + */ +#ifndef NOCOLOR +#define TBLD "\033[1m" +#define TRED "\033[31m" +#define TGRN "\033[32m" +#define TBLU "\033[34m" +#define TRST "\033[0m" +#else +#define TBLD "" +#define TRED "" +#define TGRN "" +#define TBLU "" +#define TRST "" +#endif +#define TDEL "\33[2K\r" + +/** + * Typedefs + * ======== + */ + +typedef bool (*test_fn)(void); +typedef void (*setup_fn)(void); + +/** + * Internal variables + * ================== + */ + +static setup_fn tests_init = NULL; +static setup_fn tests_destroy = NULL; + +/** + * Functions and function-like macros + * ================================== + */ + +/** + * FAIL_TEST - fail the test and print the @reason. + * @reason: a variable list of arguments, where the first argument is the format + * text. + */ +#define FAIL_TEST(reason...) \ + printf(TDEL " [" TBLD TRED "×" TRST "]\t%s: " TBLD TRED "FAILED!\n" TRST, \ + __this_name); \ + printf("\t﹂%s:%d: ", __FILE__, __LINE__); \ + printf(reason); \ + printf("\n"); \ + __ret = false; \ + goto test_out + +/** + * asserteq - assert @a and @b's equality; fail test if not equal. + * @a: argument to compare to b. + * @b: argument to compare to a. + */ +#define asserteq(a, b) \ + ({ \ + if ((a) != (b)) { \ + FAIL_TEST("assertion " TBLD TBLU #a " == " #b TRST " failed"); \ + } \ + }) + +/** + * assertneq - assert @a and @b's inequality; fail test if equal. + * @a: argument to compare to b. + * @b: argument to compare to a. + */ +#define assertneq(a, b) \ + ({ \ + if ((a) == (b)) { \ + FAIL_TEST("assertion " TBLD TBLU #a " != " #b TRST " failed"); \ + } \ + }) + +/** + * expect - fail the test on !@cond and print the reason. + * @cond: condition to test. + * @reason: a variable list of arguments, where the first argument is the format + * text. + */ +#define expect(cond, reason...) \ + ({ \ + if (!(cond)) { \ + FAIL_TEST(reason); \ + } \ + }) + +/** + * TEST_BEGIN - declare test function @name. + * @name: name of test function to declare. + * + * Should be followed by TEST_OUT and TEST_END. + */ +#define TEST_BEGIN(name) \ + int name(void) \ + { \ + const char *__this_name = #name; \ + bool __ret = true; \ + printf(" [⏳]\t%s: " TBLU "running..." TRST, __this_name); \ + fflush(stdout); + +/** + * TEST_OUT - code that should be executed on test exit goes after this. + * This declares a goto label, so that on test failure anything that needs to be + * cleaned up is cleaned up. You need to use this even if there's nothing to be + * cleaned up. + */ +#define TEST_OUT \ +test_out:; + +/** + * TEST_END - close the test scope. + */ +#define TEST_END \ + if (__ret) { \ + printf(TDEL " [" TBLD TGRN "✓" TRST "]\t%s: " TBLD TGRN \ + "PASSED!\n" TRST, \ + __this_name); \ + } \ + return __ret; \ + } + +/** + * __run_tests() - runs tests; for internal use. + */ +static inline int __run_tests(const char *const unit_name, ...) +{ + va_list args; + test_fn test; + size_t passed = 0, total = 0, failed = 0; + + if (tests_init) { + tests_init(); + } + + printf("[***]\t" TBLD "running:" TRST TBLU " %s " TRST "tests\n", + unit_name); + + va_start(args, unit_name); + test = va_arg(args, test_fn); + while (test) { + test() ? passed++ : 0; + total++; + test = va_arg(args, test_fn); + } + va_end(args); + + failed = total - passed; + + printf("[***]\t" TBLD "finished:" TRST TBLU " %s: " TRST "tests: " TBLU + "%lu" TRST ", passed: " TGRN "%lu" TRST ", failed: " TRED "%lu" TRST + "\n", + unit_name, total, passed, failed); + + if (tests_destroy) { + tests_destroy(); + } + + return failed; +} + +/** + * RUN_TEST_SUITE - runs the @tests given as arguments. + * @init_fn: initialization function. + * @destroy_fn: cleanup function. + * @tests...: tests to run. + * + * @init_fn and @destroy_fn are used to initialize and cleanup test-related data + * respectively. + */ +#define RUN_TEST_SUITE(init_fn, destroy_fn, tests...) \ + int main(void) \ + { \ + tests_init = init_fn; \ + tests_destroy = destroy_fn; \ + return __run_tests(__FILE__, tests, NULL); \ + } + +/** + * RUN_TESTS - runs the @tests given as arguments. + * @tests...: tests to run. + * + * Same as RUN_TEST_SUITE, but without initialization and cleanup functions + */ +#define RUN_TESTS(tests...) RUN_TEST_SUITE(NULL, NULL, tests) + +#endif /* UTEST_H */ diff --git a/utils.h b/utils.h new file mode 100644 index 0000000..cb7d795 --- /dev/null +++ b/utils.h @@ -0,0 +1,35 @@ +/* SPDX-License-Identifier: MIT */ +/** + * utils.h - useful macros for compile-time magic + * + * Inspired by similar macros in the Linux Kernel. + * + * Copyright (c) 2023 - Yaroslav de la Peña Smirnov + */ +#ifndef CWARE_UTILS_H +#define CWARE_UTILS_H + +#include + +#ifndef static_assert +#define static_assert(exp, msg) _Static_assert(exp, msg) +#endif + +#define same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) + +#define container_of(ptr, T, member) \ + ({ \ + static_assert(same_type(*(ptr), ((T *)0)->member) \ + || same_type(*(ptr), void), \ + "type mismatch in container_of()"); \ + (T *)((void *)(ptr)-offsetof(T, member)); \ + }) + +#define ARRAY_SIZE(arr) \ + ({ \ + static_assert(!same_type((arr), &(arr)[0]), \ + "variable is not an array"); \ + sizeof(arr) / sizeof(*arr); \ + }) + +#endif -- cgit v1.2.3