1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
2 #ifndef CCAN_PERMUTATION_H
3 #define CCAN_PERMUTATION_H
12 #include <ccan/build_assert/build_assert.h>
13 #include <ccan/mem/mem.h>
16 * We limit the number of elements to 64, to keep our data structures
17 * neat. That seems low, but even 64! permutations is far too many to
18 * really generate in practice.
20 #define PERMUTATION_MAX_SHIFT 6
21 #define PERMUTATION_MAX_ITEMS (1 << PERMUTATION_MAX_SHIFT)
24 * struct permutation - represents a permutation
26 * The fields here are user visible, but it's allocated internally
27 * with extra state information appended.
29 * @n: Number of elements in the permutation
30 * @v: values 0..(n-1) arranged in current permutation
35 /* Private state data follows */
40 * permutation_count - determine number of permutations
41 * @n: Number of elements
43 * Returns the number of permutations of @n elements.
45 unsigned long long permutation_count(int n);
48 * permutation_swap_t - represents a swap of two items
50 * Encodes a swap of two elements in an array. Should be treated as
51 * opaque, except that 0 always represents "swap nothing".
53 typedef unsigned permutation_swap_t;
57 * permutation_swap_a - first item to swap
58 * permutation_swap_b - second item to swap
60 static inline int permutation_swap_a(permutation_swap_t swap)
62 return swap % PERMUTATION_MAX_ITEMS;
65 static inline int permutation_swap_b(permutation_swap_t swap)
67 return swap / PERMUTATION_MAX_ITEMS;
71 * permutation_swap - swap two elements in an array
72 * @base: address of array
73 * @size: size of each array element
74 * @swap: which elements to swap
76 * Swaps the elements at index permutation_swap_a(@swap) and
77 * permutation_swap_b(@swap) in the array at @base of items of size
80 static inline void permutation_swap_mem(void *base, size_t size,
81 permutation_swap_t swap)
83 char *ap = (char *)base + (permutation_swap_a(swap) * size);
84 char *bp = (char *)base + (permutation_swap_b(swap) * size);
86 BUILD_ASSERT(sizeof(permutation_swap_t) * 8
87 >= PERMUTATION_MAX_SHIFT * 2);
92 memswap(ap, bp, size);
96 * PERMUTATION_SWAP - swap two elements in an array
98 * @swap_: which elements to swap
100 * As permutation_swap(), but must act on a C array declared at the
103 #define PERMUTATION_SWAP(a_, swap_) \
105 permutation_swap((a_), sizeof((a_)[0]), (swap_)); \
110 * permutation_new - allocates a new identity permutation
111 * @n: Number of elements
113 * Allocates and initializes a new permutation of @n elements.
114 * Initially it represents the identity permutation.
116 struct permutation *permutation_new(int n);
119 * PERMUTATION_NEW - allocates a new identity permutation of an array
120 * @array_: Array to permute
122 * As permutation_new() but take the number of elements from the
123 * declaration of @array_.
125 #define PERMUTATION_NEW(array_) (permutation_new(ARRAY_SIZE(array_)))
128 * permutation_change - Advance to a new permutation
129 * @pi: Current permutation
131 * Advances @pi to the next permutation by the plain changes method
132 * (Steinhaus-Johnson-Trotter algorithm).
134 * Returns the elements which were swapped in @pi, or 0 if there are
135 * no more permutations.
137 permutation_swap_t permutation_change(struct permutation *pi);
140 * permutation_change_array - Advance an array to a new permutation
141 * @pi: Current permutation
142 * @base: Address of array
143 * @size: Size of array elements
145 * Assuming the array at @base is currently in permutation @pi,
146 * advances @pi to the next permutation (as permutation_change()) and
147 * keeps the array in sync.
149 * Returns true if the permutation was advanced, false if there are no
152 static inline bool permutation_change_array(struct permutation *pi,
153 void *base, size_t size)
155 permutation_swap_t swap = permutation_change(pi);
157 permutation_swap_mem(base, size, swap);
161 static inline bool permutation_change_array_check_(struct permutation *pi,
162 void *base, size_t size,
166 return permutation_change_array(pi, base, size);
170 * PERMUTATION_CHANGE_ARRAY - Advance an array to a new permutation
171 * @pi_: Current permutation
174 * As permutation_change_array(), but operate on array @a_, which must
175 * be a C array declared with the same number of elements as @pi_.
177 #define PERMUTATION_CHANGE_ARRAY(pi_, a_) \
178 (permutation_change_array_check_((pi_), (a_), \
179 sizeof((a_)[0]), ARRAY_SIZE(a_)))
181 #endif /* CCAN_PERMUTATION_H */