X-Git-Url: https://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fpermutation%2Fpermutation.h;fp=ccan%2Fpermutation%2Fpermutation.h;h=c4d647ac3dd9574da5361cc34b3b84e2ea896ec2;hp=0000000000000000000000000000000000000000;hb=c3e9a05832ec5362bf108a7f1487aa4dcff96f99;hpb=e8d1e7304feb9318a841ad4a7d5a8773271ab814

diff --git a/ccan/permutation/permutation.h b/ccan/permutation/permutation.h
new file mode 100644
index 00000000..c4d647ac
--- /dev/null
+++ b/ccan/permutation/permutation.h
@@ -0,0 +1,181 @@
+/* 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 */