RobertDurfee’s gists

RobertDurfee / tree_barrier.c

Created February 21, 2022 14:23

	// John M. Mellor-Crummey and Michael L. Scott. 1991. Algorithms for scalable
	// synchronization on shared-memory multiprocessors. ACM Trans. Comput. Syst. 9,
	// 1 (Feb. 1991), 21–65. DOI:https://doi.org/10.1145/103727.103729

	#include <stdlib.h>
	#include <assert.h>
	#include <errno.h>

	typedef int tree_barrierattr_t;

RobertDurfee / sorting_networks.c

Created December 16, 2021 19:51

Optimal serial software sorting networks for arrays with at most 16 elements.

RobertDurfee / msd_radix.c

Last active March 9, 2021 22:43

Power-of-two base MSD radix sort for small arrays of unsigned 64-bit integers.

	#include <stddef.h>
	#include <stdint.h>
	#include <stdlib.h>
	#include <stdio.h>
	#include <assert.h>
	#include <string.h>

	#define CEIL_DIV(n, d) (((n) / (d)) + (((n) % (d)) != 0))

	#define N_DIGITS(lg_base, elem) CEIL_DIV(64 - __builtin_clzll(elem), lg_base)

RobertDurfee / lsd_radix.c

Last active March 9, 2021 22:43

Power-of-two base LSD radix sort for small arrays of unsigned 64-bit integers.

	#include <stddef.h>
	#include <stdint.h>
	#include <stdlib.h>
	#include <stdio.h>
	#include <assert.h>
	#include <string.h>

	#define CEIL_DIV(n, d) (((n) / (d)) + (((n) % (d)) != 0))

	#define N_DIGITS(lg_base, elem) CEIL_DIV(64 - __builtin_clzll(elem), lg_base)

RobertDurfee / jodhpur.c

Created October 18, 2020 14:18

A five-color, in-place partitioning algorithm in O(n)-time (based on the Dutch flag algorithm).

	enum Color {
	ORANGE,
	WHITE,
	RED,
	YELLOW,
	GREEN,
	};

	void swap(enum Color a, enum Color b) {
	enum Color temp;

RobertDurfee / hashset.h

Last active October 15, 2020 12:43

A simple, generic, dynamic hashset implementation with linear probing in C.

	#ifndef SET_H
	#define SET_H

	#include <stdint.h> // uint8_t, uint32_t
	#include <stdlib.h> // size_t, calloc, free
	#include <stdbool.h> // bool
	#include <assert.h> // assert
	#include <stdio.h> // printf

	#define TOKENPASTE(X, Y) X ## Y

RobertDurfee / hashmap.h

Last active October 15, 2020 12:43

A simple, generic, dynamic hashmap implementation with linear probing in C.

	#ifndef MAP_H
	#define MAP_H

	#include <stdint.h> // uint8_t, uint32_t
	#include <stdlib.h> // size_t, calloc, free
	#include <stdbool.h> // bool
	#include <assert.h> // assert
	#include <stdio.h> // printf

	#define TOKENPASTE(X, Y) X ## Y

RobertDurfee / uniq_rand.c

Last active September 16, 2020 15:09

A simple O(M)-space and O(N+M)-time algorithm for generating M unique pseudorandom numbers in the range [0, N) in C.

	#include <stdint.h>
	#include <stdlib.h>

	uint64_t *uniq_rand(uint64_t m, uint64_t n) {
	uint64_t *vs, im, in, rm, rn, rim, tmp;

	vs = malloc(m * sizeof(uint64_t));

	// Knuth algorithm
	for (im = 0, in = 0; im < m && in < n; in++) {

RobertDurfee / list.h

Last active October 5, 2020 21:31

A simple, generic implementation of an array with amortized O(1) append in C.

	#ifndef LIST_H
	#define LIST_H

	#include <stdlib.h> // size_t, malloc, realloc, free
	#include <stdint.h> // uint32_t
	#include <stdio.h> // printf
	#include <stdbool.h> // bool

	#define TOKENPASTE(X, Y) X ## Y
	#define INDENT(DEPTH) printf("%c", DEPTH 2, ' ')

RobertDurfee / queue.c

Last active September 16, 2020 14:27

A simple queue implementation in C.

Robert Durfee RobertDurfee