path: root/std.h

/* See copyright information at the end of the file */

/*! @file std.h
 * @brief Mario Forzanini's "standard" library
 */

#ifndef __STD_H__
#define __STD_H__

#ifndef STD_MALLOC
#include <stdlib.h>
/*! malloc(3) compatible function to use to allocate memory. */
#define STD_MALLOC(size) (malloc(size))
#endif /* STD_MALLOC */

#ifndef STD_CALLOC
#include <stdlib.h>
/*! calloc(3) compatible function to use to allocate memory. */
#define STD_CALLOC(count, size) (calloc(count, size))
#endif /* STD_CALLOC */

#ifndef STD_ERROR
#include <stdio.h>
#include <stdlib.h>
/*! Function to use to report errors, by default will call exit(3). */
#define STD_ERROR(...)                                                       \
	do {                                                                 \
		fprintf(stderr, __VA_ARGS__);                                \
		exit(EXIT_FAILURE);                                          \
	} while (0)
#endif /* STD_ERROR */

#ifndef STD_ASSERT
#include <assert.h>
/*! assert(3) compatible function. */
#define STD_ASSERT(...) assert(__VA_ARGS__)
#endif /* STD_ASSERT */

#define MB (1024 * 1024)
#define LEN(x) (sizeof(x) / sizeof(x[0]))
#define UNUSED(x) ((void)x)

#if defined(__SSE__) || defined(__SSE2__) || defined(__SSE3__)               \
	|| defined(STD_THREAD)
#include <immintrin.h>
#endif /* __SSE__ */

/*! Fail with a TODO message. */
#define STD_TODO(str) STD_ASSERT(0 && "TODO: " str)

typedef struct Region Region;
typedef struct String String;

/*! Arena allocator */
struct Region {
	size_t bcap, bsize; /*!< capacity and occupied size, in bytes */
	Region *next;	    /*!< Singly-linked list of regions */
	uintptr_t words[];  /*!< The buffer in which allocations are stored */
};

/*! Immutable slice into a string */
struct String {
	size_t count;	 /*!< Length of the slice */
	const char *str; /*!< Pointer to the beginning of the string */
};

#ifdef STD_THREAD
#ifndef STD_JOB_CAP
/*! Maximum number of jobs in queue at the same time */
#define STD_JOB_CAP 512
#endif /* STD_JOB_CAP */

#ifndef STD_POOL_SIZE
/*! Number of concurrent workers */
#define STD_POOL_SIZE 7
#endif /* STD_POOL_SIZE */

typedef struct ThreadPool ThreadPool;
typedef struct ThreadPoolItem ThreadPoolItem;
typedef struct WorkArg WorkArg;

struct WorkArg {
	void *arg;
	int idx;
};

typedef void *(*TpoolFn)(WorkArg *);

struct ThreadPoolItem {
	TpoolFn fn;
	void *arg;
};

/*! Worker pool */
struct ThreadPool {
	pthread_mutex_t rwmutex;
	pthread_t workers[STD_POOL_SIZE];
	ThreadPoolItem items[STD_JOB_CAP];
	volatile size_t head, tail; /*!< Circular queue */
	atomic_int item_count;
	atomic_bool working;
	pthread_cond_t cv;
};
#endif /* STD_THREAD */

/*! Use this in format strings to print Strings */
#define String_Fmt "%.*s"
/*! Use this in format arguments to print String_Fmt.
 * e.g.
 * @code
 * String to_print = STRING_STATIC("blabla");
 * printf(String_Fmt, String_Arg(to_print));
 * @endcode
 */
#define String_Arg(s) (int)(s).count, (s).str

/*! Like calloc(3), but exits on error. */
void *ecalloc(size_t, size_t);
/*! Like malloc(3), but exits on error. */
void *emalloc(size_t);

/*! Define a statically allocated string */
#define STRING_STATIC(str)                                                   \
	{                                                                    \
		sizeof(str) / sizeof(char) - 1, str                          \
	}
/*! Make a String out of a char* literal */
#define STRING_LITERAL(str)                                                  \
	(String)                                                             \
	{                                                                    \
		sizeof(str) / sizeof(char) - 1, str                          \
	}
/*! Copy a file.
 *
 * @param src Name of the file to copy.
 * @param dst File to copy to.
 * @return errno(3)
 */
int cp(const char src[static restrict 1], const char dst[static restrict 1]);
bool string_is_null(String);
String make_string(size_t, const char *);
/*! Acts like strcmp(3) on s1 and s2. */
int string_cmp(String s1, String s2);
/*! Checks whether str ends with end. */
bool string_ends_with(String end, String str);
/*! Return next line in String.
 *
 * Cannot be used to count the number of lines in a file as it will
 * skip empty lines.
 *
 * @see string_next_tok
 * @param str String to tokenize.
 * @todo handle CRLF
 */
String string_next_line(String str[static 1]);
/*! Tokenize str based on delim, and return the next token.
 *
 * Multiple delimiters are skipped and produce only two tokens, e.g.:
 *
 * @code
 * String str = STRING_STATIC("a  b    c");
 * String tok1 = string_next_tok(&str, ' ');
 * String tok2 = string_next_tok(&str, ' ');
 * String tok3 = string_next_tok(&str, ' ');
 * @endcode
 *
 * tok1 == (String){.count = 1, .str = "a"};
 * tok2 == (String){.count = 1, .str = "b"};
 * tok3 == (String){.count = 1, .str = "c"};
 *
 * @param str The string to modify.
 * @param delim The delimiter to look for when tokenizing.
 * @return The next token found until delim, or a string where .str = NULL.
 * Note that after the execution str will point to the character after the
 * delimiter.
 */
String string_next_tok(String str[static 1], char delim);
/*! Read the whole contents of a stream into a string.
 *
 * @param r Region on which to allocate the string.
 * @param stream File stream to read from.
 * @param contents pointer to the string to fill.
 * @return false on error, setting errno(3).
 *
 * @warning This does not work for non seekable files.
 */
bool string_read(Region *r, FILE stream[static 1], String contents[static 1]);
/*! Read the whole file into a string.
 *
 * @see string_read
 */
bool string_read_file(
	Region *r, const char filename[static 1], String contents[static 1]);
/*! Check whether str starts with start. */
bool string_starts_with(String start, String str);
/*! Strip the first n characters off of a String.
 *
 * @param str pointer to String to modify.
 * @param n Number of characters to consume.
 * @return The first n characters of str, or less if str is not long
 * enough.
 */
String string_take(String str[static 1], size_t n);
/*! Remove whitespace from String.
 *
 * @param str Input String to be modified.
 */
void string_trim(String str[static 1]);
/*! Behaves like strcat(3) for Strings.
 *
 * @param r Region in which to allocate the result
 * @param x First string to concatenate.
 * @param y Second string to concatenate.
 * @return Concatenation of x and y, allocated on r.
 */
String string_strcat(Region *r, String x, String y);
/*! Convert String to int.
 *
 * @warning First converts to long, it may truncate the result.
 * @param[in] str String to convert.
 * @param[out] i Pointer to the result.
 * @return true if no error occurred, false otherwise (check errno(3)).
 */
bool string_strtoi(String str, int i[static 1]);
/*! Convert String to unsigned long.
 *
 * @param[in] str String to convert.
 * @param[out] ul Pointer to the result.
 * @return true if no error occurred, false otherwise (check errno(3)).
 */
bool string_strtoul(String str, unsigned long ul[static 1]);
/*! Convert String to long.
 *
 * @param[in] str String to convert.
 * @param[out] l Pointer to the result.
 * @return true if no error occurred, false otherwise (check errno(3)).
 */
bool string_strtol(String str, long l[static 1]);
/*! Convert String to double.
 *
 * @param[in] str String to convert.
 * @param[out] d Pointer to the result.
 * @return true if no error occurred, false otherwise (check errno(3)).
 */
bool string_strtod(String str, double d[static 1]);

/*! Allocate linear allocator in a heap buffer.
 * @param bcap Capacity in bytes.
 * @return Heap allocated, zero-initialized, empty Region.
 */
Region *region_alloc(size_t bcap);
/*! Allocate memory in region r.
 *
 * Note that if the requested size is bigger that the region's
 * capacity, a new node in the linked list of regions is allocated
 * using region_alloc.
 * @see region_alloc
 * @see Region
 *
 * @warning Allocates memory aligned to sizeof(void *).
 * @param r Region to allocate on.
 * @param bsize Size of needed space in bytes.
 * @return Pointer to the allocated buffer.
 */
void *region_malloc(Region *r, size_t bsize);
/*! Reset a region to it's initial state.
 *
 * @warning Does not zero the memory, in this sense the region will
 * not be exactly in its initial state.
 * @param r Region to reset.
 */
void region_reset(Region *r);
/*! Free heap allocated region.
 * @see region_alloc
 */
void region_free(Region *r);

#ifdef STD_THREAD
bool tpool_init(ThreadPool[static 1]);
void tpool_add_work(ThreadPool[static 1], TpoolFn, void *);
void tpool_wait_all(ThreadPool[static 1]);
bool tpool_destroy(ThreadPool[static 1]);
#endif /* STD_THREAD */

#ifdef STD_IMPLEMENTATION
int
cp(const char src[static restrict 1], const char dst[static restrict 1])
{
	char c[4096];
	FILE *fsrc = NULL, *fdst = NULL;
	int errnum = 0;

	if (!(fsrc = fopen(src, "r"))) {
		errnum = errno;
		goto err;
	}

	if (!(fdst = fopen(dst, "w"))) {
		errnum = errno;
		goto err;
	}

	while (!feof(fsrc)) {
		size_t bytes = fread(c, 1, sizeof(c), fsrc);
		if (bytes) {
			fwrite(c, 1, bytes, fdst);
		}
	}

	fclose(fsrc);
	fclose(fdst);
	return errnum;
err:
	if (fsrc)
		fclose(fsrc);
	if (fdst)
		fclose(fdst);
	return errno;
}

void *
ecalloc(size_t count, size_t size)
{
	void *p;
	if (!(p = STD_CALLOC(count, size)))
		STD_ERROR("Cannot allocate memory.");

	return p;
}

void *
emalloc(size_t size)
{
	void *p;
	if (!(p = STD_MALLOC(size)))
		STD_ERROR("Cannot allocate memory.");

	return p;
}

bool
string_is_null(String s)
{
	return !s.str;
}

String
make_string(size_t count, const char *str)
{
	return (String) {
		.count = count,
		.str = str,
	};
}

int
string_cmp(String s1, String s2)
{
	unsigned long less = s1.count < s2.count;
	unsigned long min_length = s1.count * less + s2.count * (1 - less);
	return memcmp(s1.str, s2.str, min_length);
}

String
string_next_tok(String str[static 1], char delim)
{
	size_t idx = 0;
	String result = { 0 };

	if (str->count == 0)
		return result;

#if defined(__SSE__) || defined(__SSE2__) || defined(__SSE3__)
	__m128i _toks = _mm_set1_epi8(delim);
	if (str->count >= 16) {
		for (idx = 0; idx + 16 < str->count; idx += 16) {
			__m128i _chars, _mask;

			_chars = _mm_loadu_si128((__m128i *)&str->str[idx]);
			_mask = _mm_cmpeq_epi8(_chars, _toks);
#if defined(__SSE4_1__)
			int32_t found = _mm_testz_si128(_mask, _mask);
			if (found == 0)
				break;
#else
			int32_t found;
			found = _mm_movemask_epi8(_mask);
			if (found)
				break;
#endif /* defined(__SSE4_1__) */
		}
	}
#endif /* defined(__SSE__) || defined(__SSE2__) || defined(__SSE3__) */

	for (; idx < str->count; idx++) {
		if (str->str[idx] == delim) {
			while (idx < str->count && str->str[idx] == delim)
				idx++;
			idx--;
			break;
		}
	}
	if (idx >= str->count) {
		result.count = str->count;
		result.str = str->str;
		str->count = 0;
		str->str = NULL;
	} else {
		result.count = idx;
		result.str = str->str;
		str->count -= idx + 1;
		str->str += idx + 1;
	}

	return result;
}

bool
string_ends_with(String end, String str)
{
	if (end.count > str.count)
		return false;

	return strncmp(&str.str[str.count - end.count], end.str, end.count)
		== 0;
}

String
string_next_line(String str[static 1])
{
	return string_next_tok(str, '\n');
}

void
string_trim(String str[static 1])
{
	int i, j;
	for (i = 0; i < str->count; i++) {
		if (!isspace(str->str[i]))
			break;
	}

	for (j = (int)str->count - 1; j >= 0; j--) {
		if (!isspace(str->str[j]))
			break;
	}
	j = (int)str->count - 1 - j;

	str->str += i;
	str->count -= (size_t)i + (size_t)j;
}

bool
string_starts_with(String start, String str)
{
	if (start.count > str.count)
		return false;

	return strncmp(str.str, start.str, start.count) == 0;
}

String
string_strcat(Region *r, String x, String y)
{
	char *cat;

	cat = region_malloc(r, (x.count + y.count) * sizeof(char));

	memcpy(cat, x.str, x.count);
	memcpy(&cat[x.count + 1], y.str, y.count);

	return (String) { .count = x.count + y.count, .str = cat };
}

bool
string_strtoi(String str, int i[static 1])
{
	char *endptr = NULL;
	int result;

	result = (int)strtol(str.str, &endptr, 10);
	if ((result == 0 && endptr == str.str) || errno == ERANGE) {
		return false;
	} else {
		*i = result;
		return true;
	}
}

bool
string_strtoul(String str, unsigned long ul[static 1])
{
	char *endptr = NULL;
	unsigned long result;

	result = strtoul(str.str, &endptr, 10);
	if ((result == 0 && endptr == str.str) || errno == ERANGE) {
		return false;
	} else {
		*ul = result;
		return true;
	}
}

bool
string_strtol(String str, long l[static 1])
{
	char *endptr = NULL;
	long result;

	result = strtol(str.str, &endptr, 10);
	if ((result == 0 && endptr == str.str) || errno == ERANGE) {
		return false;
	} else {
		*l = result;
		return true;
	}
}

bool
string_strtod(String str, double d[static 1])
{
	char *endptr = NULL;
	double result;

	result = strtod(str.str, &endptr);
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wfloat-equal"
	if ((result == 0 && endptr == str.str) || errno == ERANGE) {
		return false;
	} else {
		*d = result;
		return true;
	}
#pragma GCC diagnostic pop
}

String
string_take(String str[static 1], size_t n)
{
	String result = { 0 };

	if (str->count >= n) {
		result.count = n;
		result.str = str->str;
		str->count -= n;
		str->str = &str->str[n];
	} else {
		result.count = str->count;
		result.str = str->str;
		str->count = 0;
		str->str = &str->str[str->count - 1];
	}
	return result;
}

bool
string_read(Region *r, FILE stream[static 1], String contents[static 1])
{
	long end, start;

	/* This is not guaranteed to return the number of characters in
	 * stream, it would be better to read the file in chunks or write a
	 * simple buffered input interface
	 */
	start = ftell(stream);
	fseek(stream, 0, SEEK_END);
	end = ftell(stream);

	fseek(stream, 0, SEEK_SET);
	contents->count = (size_t)(end - start);
	contents->str = region_malloc(r, contents->count);
	if (fread((void *)contents->str, sizeof(char), contents->count,
		    stream)
		< contents->count) {
		return false;
	}

	return true;
}

bool
string_read_file(
	Region *r, const char filename[static 1], String contents[static 1])
{
	FILE *f;

	if (!(f = fopen(filename, "rb")))
		return false;
	if (!string_read(r, f, contents))
		return false;
	fclose(f);
	return contents;
}

Region *
region_alloc(size_t bcap)
{
	Region *region;

	region = ecalloc(1, sizeof(Region) + bcap);
	region->bcap = bcap;
	return region;
}

static inline bool
is_power_of_two(uintptr_t x)
{
	return (x & (x - 1)) == 0;
}

/* https://www.gingerbill.org/article/2019/02/08/memory-allocation-strategies-002/
 */
static uintptr_t
align_forward(uintptr_t ptr, size_t align)
{
	uintptr_t p, a, modulo;
	STD_ASSERT(is_power_of_two(align));

	p = ptr;
	a = (uintptr_t)align;
	modulo = p & (a - 1);

	if (modulo != 0) {
		p += a - modulo;
	}
	return p;
}

static void *
region_malloc_align(Region *r, size_t bsize, size_t alignment)
{
	void *ptr;
	uintptr_t boffset = align_forward(
		(uintptr_t)r->words + (uintptr_t)r->bsize, alignment);
	boffset -= (uintptr_t)r->words;

	if (bsize + boffset > r->bcap) {
		if (!r->next) {
			if (bsize > r->bcap) {
				r->next = region_alloc(bsize);
			} else {
				r->next = region_alloc(r->bcap);
			}
		}
		return region_malloc_align(r->next, bsize, alignment);
	}

	ptr = (void *)((uintptr_t)r->words + (uintptr_t)boffset);
	r->bsize = bsize + boffset;
	return ptr;
}

void *
region_malloc(Region *r, size_t bsize)
{
	return region_malloc_align(r, bsize, sizeof(void *));
}

void
region_reset(Region *r)
{
	Region *tmp, *next;
	for (tmp = r; tmp; tmp = next) {
		next = tmp->next;
		tmp->bsize = 0;
	}
}

void
region_free(Region *r)
{
	Region *tmp, *next;
	for (tmp = r; tmp; tmp = next) {
		next = tmp->next;
		free(tmp);
	}
}

#ifdef STD_THREAD
void
tpool_add_work(ThreadPool tpool[static 1], TpoolFn fn, void *arg)
{
	STD_ASSERT(atomic_load(&tpool->item_count) < STD_JOB_CAP
		&& "Job queue full.");
	size_t tail = tpool->tail;
	tpool->tail = (tail + 1) % STD_JOB_CAP;
	tpool->items[tail] = (ThreadPoolItem) { .fn = fn, .arg = arg };

	atomic_fetch_add(&tpool->item_count, 1);
	pthread_cond_signal(&tpool->cv);
}

static inline bool
tpool_work_to_do(ThreadPool tpool[static 1])
{
	int item_count;

	pthread_mutex_lock(&tpool->rwmutex);
	while ((item_count = atomic_load(&tpool->item_count)) == 0) {
		pthread_cond_wait(&tpool->cv, &tpool->rwmutex);
	}
	pthread_mutex_unlock(&tpool->rwmutex);

	return item_count > 0;
}

void
tpool_do_work(ThreadPool tpool[static 1], int idx)
{
	TpoolFn fn;
	void *arg;
	size_t head;
	int item_count;

	pthread_mutex_lock(&tpool->rwmutex);

	item_count = atomic_load(&tpool->item_count);
	STD_ASSERT(item_count < STD_JOB_CAP && "Job queue full.");
	head = tpool->head;
	fn = tpool->items[head].fn;
	arg = tpool->items[head].arg;

	if (item_count <= 0) {
		pthread_mutex_unlock(&tpool->rwmutex);
		return;
	}

	tpool->head = (head + 1) % STD_JOB_CAP;
	pthread_mutex_unlock(&tpool->rwmutex);
	atomic_fetch_sub(&tpool->item_count, 1);

	fn(&(WorkArg) { .idx = idx, .arg = arg });
}

static atomic_int current_idx = 0;

void *
worker_fn(void *pool)
{
	ThreadPool *tpool = pool;
	int idx = atomic_fetch_add(&current_idx, 1);

	while (atomic_load(&tpool->working) && tpool_work_to_do(tpool)) {
		tpool_do_work(tpool, idx);
	}
	return NULL;
}

bool
tpool_init(ThreadPool tpool[static 1])
{
	bool error_occurred = false;

	tpool->head = 0;
	tpool->tail = 0;
	atomic_store(&tpool->working, true);
	atomic_store(&tpool->item_count, 0);

	if (pthread_mutex_init(&tpool->rwmutex, NULL) != 0) {
		return false;
	}

	if (pthread_cond_init(&tpool->cv, NULL) != 0) {
		return false;
	}

	for (int i = 0; i < STD_POOL_SIZE; i++) {
		if (pthread_create(&tpool->workers[i], NULL, worker_fn, tpool)
			!= 0) {
			error_occurred = true;
		}
	}

	return !error_occurred;
}

void
tpool_wait_all(ThreadPool tpool[static 1])
{
	while (atomic_load(&tpool->item_count) > 0)
		;
}

bool
tpool_destroy(ThreadPool tpool[static 1])
{
	bool error_occurred = false;

	tpool_wait_all(tpool);

	atomic_store(&tpool->working, false);
	pthread_cond_broadcast(&tpool->cv);

	for (int i = 0; i < STD_POOL_SIZE; i++) {
		void *result;
		if (pthread_join(tpool->workers[i], &result) != 0) {
			error_occurred = true;
		}
		UNUSED(result);
	}

	pthread_mutex_destroy(&tpool->rwmutex);

	return !error_occurred;
}

#endif /* STD_THREAD */
#endif /* STD_IMPLEMENTATION */
#endif /* __STD_H__ */

/*
 * Copyright ©️ 2023 Mario Forzanini <mf@marioforzanini.com>
 *
 * This file is part of my bachelor thesis.
 *
 * This file is free software: you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation, either version 3 of the License, or (at your
 * option) any later version.
 *
 * This file 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
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this file. If not, see <https://www.gnu.org/licenses/>.
 *
 */