Skip to content

Instantly share code, notes, and snippets.

View lxr's full-sized avatar

Dead account lxr

View GitHub Profile
@lxr
lxr / pthread_chan.c
Created November 8, 2016 20:56
libthread-style channels in pthreads
/*
* pthread_chan implements Plan 9 libthread-style channels using
* pure pthreads. Compared to other C channel libraries I've seen,
* this one has the distinction of supporting blocking select and
* deferred cancellation, albeit at a cost: all select operations are
* serialized using a single process-wide lock. This lock contention
* percolates even to ordinary sends and receives, which are implemented
* using pthread_chan_select. This is unfortunate, but it's still the
* cheapest way to implement blocking select in pthreads, as one can
* only wait on a single condition variable-mutex pair at a time; the
@lxr
lxr / ssort.c
Last active November 26, 2015 01:00
stable in-place mergesort
/*
* ssort.c implements a stable in-place merge sort as described on [1].
* The crux of the algorithm is that, when merging two adjacent
* sub-arrays, one needs to find the longest suffix of the first
* subarray where every element is larger than any element in a prefix
* of similar length in the second subarray. Swapping this prefix for
* the suffix causes every element in the second subarray to be larger
* than every element in the first subarray, which is half the battle.
* The rest can be merged by recursing the merge procedure into both
* subarrays. The unfortunate consequence of this is that the merge
@lxr
lxr / poll
Created November 13, 2015 21:38
execute a command repeatedly
#!/bin/sh -e
delimiter='\
'
interval=1
while getopts d:i: opt; do
case $opt in
d) delimiter=$OPTARG;;
i) interval=$OPTARG;;
\?) exit 1;;
esac
@lxr
lxr / rename
Last active November 13, 2015 21:09
rename files
#!/bin/sh -e
mvopts=-i
debug=false
unset command
while getopts fne: opt; do
case $opt in
f) mvopts=-f;;
n) debug=true;;
@lxr
lxr / hirschberg.c
Last active January 13, 2023 00:53
Hirschberg's algorithm for global string alignment
/*
* hirschberg.c implements Hirschberg's algorithm for global string
* alignment in C. To test it, compile it with
* `c99 -o hirschberg hirschberg.c` and then run
* `./hirschberg <string1> <string2>`. (hirschberg.c uses
* variable-length arrays, so the 99 standard is necessary.)
*
* Copyright (c) 2015 Lari Rasku. This code is released to the public
* domain, or under CC0 if not applicable.
*/
@lxr
lxr / tree
Last active November 13, 2015 21:37
print tree structures
#!/usr/bin/awk -f
{
parent = $1
child = $2
if (!(parent in isroot))
isroot[parent] = 1
if (child != parent)
isroot[child] = 0
n = ++childcount[parent]