New module.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
ogg_to_pcm \
opt \
order \
+ permutation \
pr_log \
ptrint \
ptr_valid \
--- /dev/null
+../../licenses/LGPL-2.1
\ No newline at end of file
--- /dev/null
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+/**
+ * permutation - Generate permutations
+ *
+ * This module allows you to generate all permutations of a given
+ * number of elements. It can also modify a user-supplied array in
+ * place through all those permutations.
+ *
+ * It uses the "plain changes" method, aka the
+ * Steinhaus-Johnson-Trotter algorithm to generate the permtations.
+ * This has some advantages over a naive recursive algorithm:
+ *
+ * - Each permutation is generated from the last by a single swap of
+ * adjacent elements
+ *
+ * - Constructing each permutation in place from the last takes
+ * amortized O(1) time.
+ *
+ * License: LGPL (v2.1 or any later version)
+ * Example:
+ * // Given "1 2 3" outputs 1 2 3 1 3 2 3 1 2 3 2 1 2 3 1 2 1 3
+ * #include <stdio.h>
+ * #include <ccan/permutation/permutation.h>
+ *
+ * int main(int argc, char *argv[])
+ * {
+ * int i;
+ * struct permutation *pi = permutation_new(argc - 1);
+ *
+ * do {
+ * for (i = 1; i < argc; i++)
+ * printf("%s ", argv[i]);
+ * printf("\n");
+ * } while (permutation_change_array(pi,
+ * &argv[1], sizeof(argv[1])));
+ * exit(0);
+ * }
+ */
+int main(int argc, char *argv[])
+{
+ /* Expect exactly one argument */
+ if (argc != 2)
+ return 1;
+
+ if (strcmp(argv[1], "depends") == 0) {
+ printf("ccan/build_assert\n");
+ printf("ccan/mem\n");
+ return 0;
+ }
+
+ if (strcmp(argv[1], "testdepends") == 0) {
+ printf("ccan/array_size\n");
+ return 0;
+ }
+
+ return 1;
+}
--- /dev/null
+/* GNU LGPL version 2 (or later) - see LICENSE file for details */
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/build_assert/build_assert.h>
+#include <ccan/mem/mem.h>
+#include <ccan/permutation/permutation.h>
+
+unsigned long long permutation_count(int n)
+{
+ unsigned long long count = 1;
+ int i;
+
+ for (i = 1; i <=n; i++)
+ count *= i;
+
+ return count;
+}
+
+struct plain_change_state {
+ int8_t dir : 2;
+ uint8_t pos : PERMUTATION_MAX_SHIFT;
+};
+
+static inline struct plain_change_state *get_state(struct permutation *pi)
+{
+ BUILD_ASSERT(sizeof(struct plain_change_state) == 1);
+
+ return (struct plain_change_state *)(pi + 1) + pi->n;
+}
+
+struct permutation *permutation_new(int n)
+{
+ struct permutation *pi;
+ int i;
+ struct plain_change_state *xs;
+
+ assert(n <= PERMUTATION_MAX_ITEMS);
+
+ pi = malloc(sizeof(*pi) + 2 * n);
+ if (!pi)
+ return NULL;
+
+ pi->n = n;
+
+ xs = get_state(pi);
+
+ for (i = 0; i < pi->n; i++) {
+ pi->v[i] = i;
+ xs[i].pos = i;
+ xs[i].dir = (i == 0) ? 0 : -1;
+ }
+
+ return pi;
+}
+
+permutation_swap_t permutation_change(struct permutation *pi)
+{
+ int v, w, i;
+ int a, b, vdir;
+ struct plain_change_state *xs = get_state(pi);
+
+ if (!pi->n)
+ return 0;
+
+ for (v = pi->n - 1; v > 0; v--) {
+ if (xs[v].dir)
+ break;
+ }
+
+ a = xs[v].pos;
+ vdir = xs[v].dir;
+ if (!vdir)
+ return 0;
+
+ b = a + vdir;
+ w = pi->v[b];
+
+ pi->v[a] = w;
+ pi->v[b] = v;
+ xs[v].pos = b;
+ xs[w].pos = a;
+
+ /* If we reach the end, or the next item is larger, set
+ * direction to 0 */
+ if ((b == 0) || (b == (pi->n-1))
+ || (pi->v[b + vdir] > v))
+ xs[v].dir = 0;
+
+ /* Reset direction on all elements greater than the chosen one */
+ for (i = v + 1; i < pi->n; i++) {
+ if (xs[i].pos < b)
+ xs[i].dir = 1;
+ else
+ xs[i].dir = -1;
+ }
+
+ return (b * PERMUTATION_MAX_ITEMS) + a;
+}
--- /dev/null
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+#ifndef CCAN_PERMUTATION_H
+#define CCAN_PERMUTATION_H
+
+#include <config.h>
+
+#include <stdlib.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <assert.h>
+
+#include <ccan/build_assert/build_assert.h>
+#include <ccan/mem/mem.h>
+
+/*
+ * We limit the number of elements to 64, to keep our data structures
+ * neat. That seems low, but even 64! permutations is far too many to
+ * really generate in practice.
+ */
+#define PERMUTATION_MAX_SHIFT 6
+#define PERMUTATION_MAX_ITEMS (1 << PERMUTATION_MAX_SHIFT)
+
+/**
+ * struct permutation - represents a permutation
+ *
+ * The fields here are user visible, but it's allocated internally
+ * with extra state information appended.
+ *
+ * @n: Number of elements in the permutation
+ * @v: values 0..(n-1) arranged in current permutation
+ */
+struct permutation {
+ int n;
+ uint8_t v[];
+ /* Private state data follows */
+};
+
+
+/**
+ * permutation_count - determine number of permutations
+ * @n: Number of elements
+ *
+ * Returns the number of permutations of @n elements.
+ */
+unsigned long long permutation_count(int n);
+
+/**
+ * permutation_swap_t - represents a swap of two items
+ *
+ * Encodes a swap of two elements in an array. Should be treated as
+ * opaque, except that 0 always represents "swap nothing".
+ */
+typedef unsigned permutation_swap_t;
+
+
+/**
+ * permutation_swap_a - first item to swap
+ * permutation_swap_b - second item to swap
+ */
+static inline int permutation_swap_a(permutation_swap_t swap)
+{
+ return swap % PERMUTATION_MAX_ITEMS;
+}
+
+static inline int permutation_swap_b(permutation_swap_t swap)
+{
+ return swap / PERMUTATION_MAX_ITEMS;
+}
+
+/**
+ * permutation_swap - swap two elements in an array
+ * @base: address of array
+ * @size: size of each array element
+ * @swap: which elements to swap
+ *
+ * Swaps the elements at index permutation_swap_a(@swap) and
+ * permutation_swap_b(@swap) in the array at @base of items of size
+ * @size.
+ */
+static inline void permutation_swap_mem(void *base, size_t size,
+ permutation_swap_t swap)
+{
+ char *ap = (char *)base + (permutation_swap_a(swap) * size);
+ char *bp = (char *)base + (permutation_swap_b(swap) * size);
+
+ BUILD_ASSERT(sizeof(permutation_swap_t) * 8
+ >= PERMUTATION_MAX_SHIFT * 2);
+
+ if (!swap)
+ return;
+
+ memswap(ap, bp, size);
+}
+
+/**
+ * PERMUTATION_SWAP - swap two elements in an array
+ * @a_: array
+ * @swap_: which elements to swap
+ *
+ * As permutation_swap(), but must act on a C array declared at the
+ * right size.
+ */
+#define PERMUTATION_SWAP(a_, swap_) \
+ do { \
+ permutation_swap((a_), sizeof((a_)[0]), (swap_)); \
+ } while (0)
+
+
+/**
+ * permutation_new - allocates a new identity permutation
+ * @n: Number of elements
+ *
+ * Allocates and initializes a new permutation of @n elements.
+ * Initially it represents the identity permutation.
+ */
+struct permutation *permutation_new(int n);
+
+/**
+ * PERMUTATION_NEW - allocates a new identity permutation of an array
+ * @array_: Array to permute
+ *
+ * As permutation_new() but take the number of elements from the
+ * declaration of @array_.
+ */
+#define PERMUTATION_NEW(array_) (permutation_new(ARRAY_SIZE(array_)))
+
+/**
+ * permutation_change - Advance to a new permutation
+ * @pi: Current permutation
+ *
+ * Advances @pi to the next permutation by the plain changes method
+ * (Steinhaus-Johnson-Trotter algorithm).
+ *
+ * Returns the elements which were swapped in @pi, or 0 if there are
+ * no more permutations.
+ */
+permutation_swap_t permutation_change(struct permutation *pi);
+
+/**
+ * permutation_change_array - Advance an array to a new permutation
+ * @pi: Current permutation
+ * @base: Address of array
+ * @size: Size of array elements
+ *
+ * Assuming the array at @base is currently in permutation @pi,
+ * advances @pi to the next permutation (as permutation_change()) and
+ * keeps the array in sync.
+ *
+ * Returns true if the permutation was advanced, false if there are no
+ * more permutations.
+ */
+static inline bool permutation_change_array(struct permutation *pi,
+ void *base, size_t size)
+{
+ permutation_swap_t swap = permutation_change(pi);
+
+ permutation_swap_mem(base, size, swap);
+ return (swap != 0);
+}
+
+static inline bool permutation_change_array_check_(struct permutation *pi,
+ void *base, size_t size,
+ int n)
+{
+ assert(n == pi->n);
+ return permutation_change_array(pi, base, size);
+}
+
+/**
+ * PERMUTATION_CHANGE_ARRAY - Advance an array to a new permutation
+ * @pi_: Current permutation
+ * @a_: Array
+ *
+ * As permutation_change_array(), but operate on array @a_, which must
+ * be a C array declared with the same number of elements as @pi_.
+ */
+#define PERMUTATION_CHANGE_ARRAY(pi_, a_) \
+ (permutation_change_array_check_((pi_), (a_), \
+ sizeof((a_)[0]), ARRAY_SIZE(a_)))
+
+#endif /* CCAN_PERMUTATION_H */
--- /dev/null
+#include "config.h"
+
+#include <assert.h>
+#include <string.h>
+#include <stdint.h>
+#include <inttypes.h>
+
+#include <ccan/array_size/array_size.h>
+#include <ccan/permutation/permutation.h>
+#include <ccan/tap/tap.h>
+
+#define MAX_ITEMS 10
+
+#define PERMUTE(pi, arr) \
+ do { \
+ ok1(PERMUTATION_CHANGE_ARRAY((pi), (arr))); \
+ } while (0)
+
+#define CHECK_ORDER(a, t, ...) \
+ do { \
+ t cmp[] = { __VA_ARGS__ }; \
+ ok1(memcmp((a), cmp, sizeof(cmp)) == 0); \
+ } while (0)
+
+#define WORDLEN 6
+typedef char word[WORDLEN];
+
+int main(void)
+{
+ struct permutation *pi;
+ int single = 12345;
+ char pair[] = { 'P', 'Q' };
+ uint16_t triple[] = {7, 9, 1000};
+ word four[] = {"ZERO", "ONE", "TWO", "THREE"};
+ int i;
+
+ plan_tests(2 * permutation_count(1) + 1
+ + 2 * permutation_count(2) + 1
+ + 2 * permutation_count(3) + 1
+ + 2 * permutation_count(4) + 1
+ + MAX_ITEMS + 1);
+
+ /* One */
+ pi = permutation_new(1);
+ CHECK_ORDER(&single, int, 12345);
+ ok1(!permutation_change_array(pi, &single, sizeof(single)));
+ CHECK_ORDER(&single, int, 12345);
+ free(pi);
+
+ /* Pair */
+ pi = PERMUTATION_NEW(pair);
+ CHECK_ORDER(pair, char, 'P', 'Q');
+ PERMUTE(pi, pair);
+ CHECK_ORDER(pair, char, 'Q', 'P');
+ ok1(!PERMUTATION_CHANGE_ARRAY(pi, pair));
+ CHECK_ORDER(pair, char, 'Q', 'P');
+ free(pi);
+
+ /* Triple */
+ pi = PERMUTATION_NEW(triple);
+ CHECK_ORDER(triple, uint16_t, 7, 9, 1000);
+ PERMUTE(pi, triple);
+ CHECK_ORDER(triple, uint16_t, 7, 1000, 9);
+ PERMUTE(pi, triple);
+ CHECK_ORDER(triple, uint16_t, 1000, 7, 9);
+ PERMUTE(pi, triple);
+ CHECK_ORDER(triple, uint16_t, 1000, 9, 7);
+ PERMUTE(pi, triple);
+ CHECK_ORDER(triple, uint16_t, 9, 1000, 7);
+ PERMUTE(pi, triple);
+ CHECK_ORDER(triple, uint16_t, 9, 7, 1000);
+ ok1(!PERMUTATION_CHANGE_ARRAY(pi, triple));
+ CHECK_ORDER(triple, uint16_t, 9, 7, 1000);
+ free(pi);
+
+ /* Four */
+ pi = PERMUTATION_NEW(four);
+ CHECK_ORDER(four, word, "ZERO", "ONE", "TWO", "THREE");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "ZERO", "ONE", "THREE", "TWO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "ZERO", "THREE", "ONE", "TWO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "THREE", "ZERO", "ONE", "TWO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "THREE", "ZERO", "TWO", "ONE");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "ZERO", "THREE", "TWO", "ONE");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "ZERO", "TWO", "THREE", "ONE");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "ZERO", "TWO", "ONE", "THREE");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "TWO", "ZERO", "ONE", "THREE");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "TWO", "ZERO", "THREE", "ONE");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "TWO", "THREE", "ZERO", "ONE");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "THREE", "TWO", "ZERO", "ONE");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "THREE", "TWO", "ONE", "ZERO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "TWO", "THREE", "ONE", "ZERO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "TWO", "ONE", "THREE", "ZERO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "TWO", "ONE", "ZERO", "THREE");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "ONE", "TWO", "ZERO", "THREE");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "ONE", "TWO", "THREE", "ZERO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "ONE", "THREE", "TWO", "ZERO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "THREE", "ONE", "TWO", "ZERO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "THREE", "ONE", "ZERO", "TWO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "ONE", "THREE", "ZERO", "TWO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "ONE", "ZERO", "THREE", "TWO");
+ PERMUTE(pi, four);
+ CHECK_ORDER(four, word, "ONE", "ZERO", "TWO", "THREE");
+ ok1(!PERMUTATION_CHANGE_ARRAY(pi, four));
+ CHECK_ORDER(four, word, "ONE", "ZERO", "TWO", "THREE");
+ free(pi);
+
+ for (i = 0; i <= MAX_ITEMS; i++) {
+ uint64_t nperms = 1;
+
+ diag("Counting permutations of %d\n", i);
+
+ pi = permutation_new(i);
+ while (permutation_change(pi))
+ nperms++;
+
+ ok(nperms == permutation_count(i),
+ "%"PRId64" permutations of %d (%d! == %lld)",
+ nperms, i, i, permutation_count(i));
+ free(pi);
+ }
+
+ /* This exits depending on whether all tests passed */
+
+ return exit_status();
+}
projects / ccan / commitdiff