permute c function for ruby, separated out for history and learning

permute.c

/*
 * Compute permutations of +r+ elements of the set <code>[0..n-1]</code>.
 *
 * When we have a complete permutation of array indices, copy the values
 * at those indices into a new array and yield that array.
 *
 * n: the size of the set
 * r: the number of elements in each permutation
 * p: the array (of size r) that we're filling in
 * used: an array of booleans: whether a given index is already used
 * values: the Ruby array that holds the actual values to permute
 */
static void
permute0(const long n, const long r, long *const p, char *const used, const VALUE values)
{
    long i = 0, index = 0;

    for (;;) {
	const char *const unused = memchr(&used[i], 0, n-i);
	if (!unused) {
	    if (!index) break;
	    i = p[--index];                /* pop index */
	    used[i++] = 0;                 /* index unused */
	}
	else {
	    i = unused - used;
	    p[index] = i;
	    used[i] = 1;                   /* mark index used */
	    ++index;
	    if (index < r-1) {             /* if not done yet */
		p[index] = i = 0;
		continue;
	    }
	    for (i = 0; i < n; ++i) {
		if (used[i]) continue;
		p[index] = i;
		if (!yield_indexed_values(values, r, p)) {
		    rb_raise(rb_eRuntimeError, "permute reentered");
		}
	    }
	    i = p[--index];                /* pop index */
	    used[i] = 0;                   /* index unused */
	    p[index] = ++i;
	}
    }
}