toys

commit 9769f561b8ca0bb35106780d0e2430a0edec7a3a
Author: Mikołaj Lenczewski <mblenczewski@gmail.com>
Date:   Sat, 12 Apr 2025 11:59:24 +0000

Initial commit

Diffstat:
A
.editorconfig
 | 
17
+++++++++++++++++
A
.gitignore
 | 
3
+++
A
LICENSE
 | 
18
++++++++++++++++++
A
README
 | 
9
+++++++++
A
arena.c
 | 
88
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
arena.h
 | 
68
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
build.sh
 | 
11
+++++++++++
A
clean.sh
 | 
5
+++++
A
list.c
 | 
66
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
list.h
 | 
150
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

10 files changed, 435 insertions(+), 0 deletions(-)
diff --git a/.editorconfig b/.editorconfig
@@ -0,0 +1,17 @@
+root = true
+
+[*]
+end_of_line = lf
+insert_final_newline = true
+trim_trailing_whitespace = true
+charset = utf-8
+
+guidelines = 80, 120, 160
+
+[*.{c,h}]
+indent_style = tab
+indent_size = 8
+
+[*.{md,txt}]
+indent_style = space
+indent_size = 2
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,3 @@
+bin/
+
+**/.*.swp
diff --git a/LICENSE b/LICENSE
@@ -0,0 +1,18 @@
+The MIT-Zero License
+
+Copyright (c) 2025 Mikołaj Lenczewski <mikolaj@lenczewski.org>
+
+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.
+
+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/README b/README
@@ -0,0 +1,9 @@
+toys
+==============================================================================
+A small collection of C data structures, algorithms, and macros that I have
+used in the past. Written in (reasonably) portable C99. Includes basic test
+programs. Includes some commentary for each toy.
+
+toys: Building
+------------------------------------------------------------------------------
+To build, simply run `build.sh`. Similarly, to clean, simply run `clean.sh`.
diff --git a/arena.c b/arena.c
@@ -0,0 +1,88 @@
+#define HEADER_IMPL
+#include "arena.h"
+
+#include <stdio.h>
+
+struct mystruct {
+	int a, b, c;
+};
+
+struct alignas(64) mystruct2 {
+	char buf[17];
+};
+
+int
+main(void)
+{
+	printf("IS_POW2(1): %d, IS_POW2(2): %d, IS_POW2(3): %d\n",
+			IS_POW2(1), IS_POW2(2), IS_POW2(3));
+
+	printf("IS_ALIGNED(2, 2): %d, IS_ALIGNED(1, 2): %d\n",
+			IS_ALIGNED(2, 2), IS_ALIGNED(1, 2));
+
+	printf("ALIGN_PREV(2, 2): %d, ALIGN_PREV(1, 2): %d\n",
+			ALIGN_PREV(2, 2), ALIGN_PREV(1, 2));
+
+	printf("ALIGN_NEXT(2, 2): %d, ALIGN_NEXT(1, 2): %d\n",
+			ALIGN_NEXT(2, 2), ALIGN_NEXT(1, 2));
+
+	char buf[1024];
+	struct arena arena = { .ptr = buf, .cap = sizeof buf, .len = 0, };
+
+	printf("arena: buf: %p, cap: %zu, len: %zu\n",
+			arena.ptr, arena.cap, arena.len);
+
+	struct mystruct *foo = arena_alloc(&arena, sizeof *foo, alignof(struct mystruct));
+	assert(foo);
+
+	printf("foo: %p, sizeof foo: %zu, alignof foo: %zu\n",
+			foo, sizeof *foo, alignof(struct mystruct));
+
+	foo->a = foo->b = foo->c = 42;
+
+	struct mystruct *bar = ARENA_ALLOC_SIZED(&arena, struct mystruct);
+	assert(bar);
+
+	printf("bar: %p, sizeof bar: %zu, alignof bar: %zu\n",
+			bar, sizeof *bar, alignof(struct mystruct));
+
+	bar->a = bar->b = bar->c = 69;
+
+	assert(foo != bar);
+
+	printf("arena_reset() ...\n");
+
+	printf("\tbefore reset: foo->a = %d\n", foo->a);
+	arena_reset(&arena);
+	printf("\tafter reset: foo->a = %d\n", foo->a);
+
+	struct mystruct *baz = ARENA_ALLOC_SIZED(&arena, struct mystruct);
+	assert(baz);
+	assert(foo == baz);
+
+	printf("\tafter reset: baz: %p, baz->a = %d, baz == foo: %d\n",
+			baz, baz->a, baz == foo);
+
+	// struct mystruct2 *fee = ARENA_ALLOC_ARRAY(&arena, struct mystruct2, 2);
+	struct mystruct2 *fee = arena_alloc(&arena, sizeof *fee * 2, alignof(struct mystruct2));
+	assert(fee);
+
+	printf("fee: %p, sizeof fee: %zu, alignof fee: %zu\n",
+			fee, sizeof *fee, alignof(struct mystruct2));
+
+	printf("fee[0]: %p, fee[0] is aligned: %d, fee[1]: %p, fee[1] is aligned: %d\n",
+			&fee[0], IS_ALIGNED((uintptr_t) &fee[0], alignof(struct mystruct2)),
+			&fee[1], IS_ALIGNED((uintptr_t) &fee[1], alignof(struct mystruct2)));
+
+	assert(IS_ALIGNED((uintptr_t) &fee[0], 64));
+	assert(IS_ALIGNED((uintptr_t) &fee[1], 64));
+
+	char *mybuf = arena_alloc(&arena, 128, 256);
+	assert(mybuf);
+
+	printf("mybuf: %p, sizeof mybuf: 128, alignof mybuf: 256\n", mybuf);
+
+	assert(IS_ALIGNED((uintptr_t) mybuf, 256));
+
+	return 0;
+}
diff --git a/arena.h b/arena.h
@@ -0,0 +1,68 @@
+#ifndef ARENA_H
+#define ARENA_H
+
+#include <assert.h>
+#include <stdalign.h>
+#include <stddef.h>
+#include <stdint.h>
+
+/* helper macros to allow us to use bitwise tricks to quickly and efficiently
+ * calculate aligned addresses and sizes.
+ */
+#define IS_POW2(v) (((v) & ((v) - 1)) == 0)
+#define IS_ALIGNED(v, align) (((v) & ((align) - 1)) == 0)
+#define ALIGN_PREV(v, align) ((v) & ~((align) - 1))
+#define ALIGN_NEXT(v, align) ALIGN_PREV(((v) + ((align) - 1)), (align))
+
+struct arena {
+	void *ptr;
+	uint64_t cap, len;
+};
+
+/* arenas dont support freeing individual elements, instead allowing only to
+ * free all elements at once.
+ */
+inline void
+arena_reset(struct arena *arena)
+{
+	arena->len = 0;
+}
+
+/* we might want to allocate arbitrary buffers out of an arena, with any given
+ * alignment (as long as it is a power of two).
+ */
+inline void *
+arena_alloc(struct arena *arena, size_t size, size_t align)
+{
+	assert(size);
+	assert(align);
+	assert(IS_POW2(align));
+
+	uintptr_t aligned_ptr = ALIGN_NEXT((uintptr_t) arena->ptr + arena->len, align);
+	if (aligned_ptr + size > (uintptr_t) arena->ptr + arena->cap)
+		return NULL;
+
+	arena->len = (aligned_ptr - (uintptr_t) arena->ptr) + size;
+
+	return (void *) aligned_ptr;
+}
+
+/* helper macros to make allocation more concise.
+ */
+#define ARENA_ALLOC_ARRAY(arena, T, n) \
+	((T *) arena_alloc((arena), sizeof(T) * (n), alignof(T)))
+
+#define ARENA_ALLOC_SIZED(arena, T) \
+	ARENA_ALLOC_ARRAY((arena), T, 1)
+
+#endif /* ARENA_H */
+
+#ifdef HEADER_IMPL
+
+extern inline void
+arena_reset(struct arena *arena);
+
+extern inline void *
+arena_alloc(struct arena *arena, size_t size, size_t align);
+
+#endif /* HEADER_IMPL */
diff --git a/build.sh b/build.sh
@@ -0,0 +1,11 @@
+#!/bin/sh
+
+FLAGS="-Wall -Wextra -Wpedantic -Wno-format-pedantic -std=c99 -Og -g"
+
+set -ex
+
+mkdir -p bin
+
+for src in *.c; do
+	cc -o bin/$(basename -s .c $src) $src $FLAGS
+done
diff --git a/clean.sh b/clean.sh
@@ -0,0 +1,5 @@
+#!/bin/sh
+
+set -ex
+
+rm -rf bin
diff --git a/list.c b/list.c
@@ -0,0 +1,66 @@
+#define HEADER_IMPL
+#include "list.h"
+
+struct mystruct {
+	int a;
+	struct list_node list_node;
+};
+
+int
+main(void)
+{
+	struct list_node list = LIST_INIT(list);
+	list_print(&list, 0);
+
+	struct mystruct a = {1,{0,0}}, b = {2,{0,0}}, c = {3,{0,0}};
+	fprintf(stderr, "a: %p\n", (void *) &a.list_node);
+	fprintf(stderr, "b: %p\n", (void *) &b.list_node);
+	fprintf(stderr, "c: %p\n", (void *) &c.list_node);
+
+	/* list_iter() */
+	fprintf(stderr, "list_iter()...\n");
+	list_push_head(&list, &a.list_node);
+	list_push_head(&list, &b.list_node);
+	list_push_head(&list, &c.list_node);
+	list_print(&list, 0);
+
+	/* list_entry_iter() */
+	{
+		fprintf(stderr, "list_entry_iter()...\n");
+		fprintf(stderr, "mystruct list: %p, head: %p, tail: %p\n",
+				(void *) &list, (void *) LIST_HEAD(&list), (void *) LIST_TAIL(&list));
+
+		size_t i = 0;
+		struct mystruct *it;
+		LIST_ENTRY_ITER(&list, it, list_node) {
+			fprintf(stderr, "\t%zu = { %d, { %p, prev: %p, next: %p } }\n",
+					i++, it->a,
+					(void *) &it->list_node,
+					(void *) it->list_node.prev,
+					(void *) it->list_node.next);
+		}
+	}
+
+	/* list_riter() */
+	fprintf(stderr, "list_riter()...\n");
+	list_print(&list, 1);
+
+	/* list_entry_riter() */
+	{
+		fprintf(stderr, "list_entry_riter()...\n");
+		fprintf(stderr, "list: %p, head: %p, tail: %p\n",
+				(void *) &list, (void *) LIST_HEAD(&list), (void *) LIST_TAIL(&list));
+
+		size_t i = 0;
+		struct mystruct *it;
+		LIST_ENTRY_RITER(&list, it, list_node) {
+			fprintf(stderr, "\t%zu = { %d, { %p, prev: %p, next: %p } }\n",
+					i++, it->a,
+					(void *) &it->list_node,
+					(void *) it->list_node.prev,
+					(void *) it->list_node.next);
+		}
+	}
+
+	return 0;
+}
diff --git a/list.h b/list.h
@@ -0,0 +1,150 @@
+#ifndef LIST_H
+#define LIST_H
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+/* we define an "intrusive" list, meaning that out data struct contains a
+ * list_node member. this allows a type-generic list implementation, but
+ * necessitates need a way to get from a pointer to this list_node, to a
+ * pointer to the parent struct
+ */
+#define TO_PARENT(ptr, T, member) \
+	((T *) ((uintptr_t) (ptr) - offsetof(T, member)))
+
+/* we choose to implement a doubly-linked list for simplicity and flexible
+ * use in situations that require either singly-linked or doubly-linked lists
+ */
+struct list_node {
+	struct list_node *prev, *next;
+};
+
+/* shorthands for getting the head and tail members of a list
+ */
+#define LIST_HEAD(list) ((list)->next)
+#define LIST_TAIL(list) ((list)->prev)
+
+/* instead of having NULL signify an empty list, we have the list itself be the
+ * "sentinel value". this approach simplifys some of the code (as we always
+ * point to a valid instance in our next and prev fields). this makes checking
+ * whether a list is empty slightly convoluted unfortunately.
+ */
+#define LIST_INIT(list) { .prev = &(list), .next = &(list), }
+#define LIST_EMTPY(list) (LIST_HEAD(list) == (list) && LIST_TAIL(list) == (list))
+
+
+inline void
+list_node_link(struct list_node *node, struct list_node *prev, struct list_node *next)
+{
+	node->prev = prev;
+	prev->next = node;
+	node->next = next;
+	next->prev = node;
+}
+
+inline struct list_node *
+list_node_unlink(struct list_node *node)
+{
+	node->prev->next = node->next;
+	node->next->prev = node->prev;
+	return node;
+}
+
+/* some helpers to push and pop a node to and from an existing list
+ */
+inline void
+list_push_head(struct list_node *restrict list, struct list_node *restrict node)
+{
+	list_node_link(node, list, LIST_HEAD(list));
+}
+
+inline void
+list_push_tail(struct list_node *restrict list, struct list_node *restrict node)
+{
+	list_node_link(node, LIST_TAIL(list), list);
+}
+
+inline struct list_node *
+list_pop_head(struct list_node *list)
+{
+	struct list_node *node = list_node_unlink(LIST_HEAD(list));
+	return node;
+}
+
+inline struct list_node *
+list_pop_tail(struct list_node *list)
+{
+	struct list_node *node = list_node_unlink(LIST_TAIL(list));
+	return node;
+}
+
+/* helper macros to allow simple iteration over the list_node instances, or
+ * over the parent types that comprise the list.
+ */
+#define LIST_ITER(list, it) \
+	for ((it) = LIST_HEAD(list); (it) != (list); (it) = (it)->next)
+
+#define LIST_RITER(list, it) \
+	for ((it) = LIST_TAIL(list); (it) != (list); (it) = (it)->prev)
+
+#define LIST_NODE_ENTRY(ptr, T, member) TO_PARENT(ptr, T, member)
+
+#define LIST_ENTRY_ITER(list, it, member) \
+	for ((it) = LIST_NODE_ENTRY(LIST_HEAD(list), __typeof__ (*(it)), member); \
+	     &(it)->member != (list); \
+	     (it) = LIST_NODE_ENTRY((it)->member.next, __typeof__ (*(it)), member))
+
+#define LIST_ENTRY_RITER(list, it, member) \
+	for ((it) = LIST_NODE_ENTRY(LIST_TAIL(list), __typeof__ (*(it)), member); \
+	     &(it)->member != (list); \
+	     (it) = LIST_NODE_ENTRY((it)->member.prev, __typeof__ (*(it)), member))
+
+inline void
+list_print(struct list_node const *list, int reversed)
+{
+	fprintf(stderr, "list: %p, head: %p, tail: %p\n",
+			(void *) list, (void *) LIST_HEAD(list), (void *) LIST_TAIL(list));
+
+	struct list_node *it;
+	if (reversed) {
+		LIST_ITER(list, it) {
+			fprintf(stderr, "\t{ %p, prev: %p, next: %p }\n",
+					(void *) it, (void *) it->prev, (void *) it->next);
+		}
+	} else {
+		LIST_RITER(list, it) {
+			fprintf(stderr, "\t{ %p, prev: %p, next: %p }\n",
+					(void *) it, (void *) it->prev, (void *) it->next);
+		}
+	}
+}
+
+#endif /* LIST_H */
+
+#ifdef HEADER_IMPL
+
+extern inline void
+list_node_link(struct list_node *restrict node,
+	       struct list_node *restrict prev, struct list_node *restrict next);
+
+extern inline struct list_node *
+list_node_unlink(struct list_node *node);
+
+extern inline void
+list_push_head(struct list_node *restrict list, struct list_node *restrict node);
+
+extern inline void
+list_push_tail(struct list_node *restrict list, struct list_node *restrict node);
+
+extern inline struct list_node *
+list_pop_head(struct list_node *list);
+
+extern inline struct list_node *
+list_pop_tail(struct list_node *list);
+
+extern inline void
+list_print(struct list_node const *list, int reversed);
+
+#endif /* HEADER_IMPL */