Skip to content

Instantly share code, notes, and snippets.

View RobertDurfee's full-sized avatar

Robert Durfee RobertDurfee

10 followers · 0 following
View GitHub Profile
@RobertDurfee
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
RobertDurfee / sorting_networks.c
Created December 16, 2021 19:51
Optimal serial software sorting networks for arrays with at most 16 elements.
#define CE(A, B) \
if ((A) > (B)) { \
int tmp = (A); \
(A) = (B); \
(B) = tmp; \
}
void network2(int *start) {
CE(start[0], start[1]);
}
@RobertDurfee
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
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
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
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
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
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
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
RobertDurfee / queue.c
Last active September 16, 2020 14:27
A simple queue implementation in C.
#include <stdlib.h>
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Header
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define IN /* IN */
#define OUT /* OUT */
#define INOUT /* INOUT */