git.ozlabs.org Git - ccan/blob - ccan/permutation/permutation.h

   1 /* Licensed under LGPLv2.1+ - see LICENSE file for details */
   2 #ifndef CCAN_PERMUTATION_H
   3 #define CCAN_PERMUTATION_H
   4
   5 #include <config.h>
   6
   7 #include <stdlib.h>
   8 #include <stdbool.h>
   9 #include <stdint.h>
  10 #include <assert.h>
  11
  12 #include <ccan/build_assert/build_assert.h>
  13 #include <ccan/mem/mem.h>
  14
  15 /*
  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.
  19  */
  20 #define PERMUTATION_MAX_SHIFT   6
  21 #define PERMUTATION_MAX_ITEMS   (1 << PERMUTATION_MAX_SHIFT)
  22
  23 /**
  24  * struct permutation - represents a permutation
  25  *
  26  * The fields here are user visible, but it's allocated internally
  27  * with extra state information appended.
  28  *
  29  * @n: Number of elements in the permutation
  30  * @v: values 0..(n-1) arranged in current permutation
  31  */
  32 struct permutation {
  33         int n;
  34         uint8_t v[];
  35         /* Private state data follows */
  36 };
  37
  38
  39 /**
  40  * permutation_count - determine number of permutations
  41  * @n: Number of elements
  42  *
  43  * Returns the number of permutations of @n elements.
  44  */
  45 unsigned long long permutation_count(int n);
  46
  47 /**
  48  * permutation_swap_t - represents a swap of two items
  49  *
  50  * Encodes a swap of two elements in an array.  Should be treated as
  51  * opaque, except that 0 always represents "swap nothing".
  52  */
  53 typedef unsigned permutation_swap_t;
  54
  55
  56 /**
  57  * permutation_swap_a - first item to swap
  58  * permutation_swap_b - second item to swap
  59  */
  60 static inline int permutation_swap_a(permutation_swap_t swap)
  61 {
  62         return swap % PERMUTATION_MAX_ITEMS;
  63 }
  64
  65 static inline int permutation_swap_b(permutation_swap_t swap)
  66 {
  67         return swap / PERMUTATION_MAX_ITEMS;
  68 }
  69
  70 /**
  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
  75  *
  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
  78  * @size.
  79  */
  80 static inline void permutation_swap_mem(void *base, size_t size,
  81                                         permutation_swap_t swap)
  82 {
  83         char *ap = (char *)base + (permutation_swap_a(swap) * size);
  84         char *bp = (char *)base + (permutation_swap_b(swap) * size);
  85
  86         BUILD_ASSERT(sizeof(permutation_swap_t) * 8
  87                      >= PERMUTATION_MAX_SHIFT * 2);
  88
  89         if (!swap)
  90                 return;
  91
  92         memswap(ap, bp, size);
  93 }
  94
  95 /**
  96  * PERMUTATION_SWAP - swap two elements in an array
  97  * @a_: array
  98  * @swap_: which elements to swap
  99  *
 100  * As permutation_swap(), but must act on a C array declared at the
 101  * right size.
 102  */
 103 #define PERMUTATION_SWAP(a_, swap_)                                     \
 104         do {                                                            \
 105                 permutation_swap((a_), sizeof((a_)[0]), (swap_));       \
 106         } while (0)
 107
 108
 109 /**
 110  * permutation_new - allocates a new identity permutation
 111  * @n: Number of elements
 112  *
 113  * Allocates and initializes a new permutation of @n elements.
 114  * Initially it represents the identity permutation.
 115  */
 116 struct permutation *permutation_new(int n);
 117
 118 /**
 119  * PERMUTATION_NEW - allocates a new identity permutation of an array
 120  * @array_: Array to permute
 121  *
 122  * As permutation_new() but take the number of elements from the
 123  * declaration of @array_.
 124  */
 125 #define PERMUTATION_NEW(array_) (permutation_new(ARRAY_SIZE(array_)))
 126
 127 /**
 128  * permutation_change - Advance to a new permutation
 129  * @pi: Current permutation
 130  *
 131  * Advances @pi to the next permutation by the plain changes method
 132  * (Steinhaus-Johnson-Trotter algorithm).
 133  *
 134  * Returns the elements which were swapped in @pi, or 0 if there are
 135  * no more permutations.
 136  */
 137 permutation_swap_t permutation_change(struct permutation *pi);
 138
 139 /**
 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
 144  *
 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.
 148  *
 149  * Returns true if the permutation was advanced, false if there are no
 150  * more permutations.
 151  */
 152 static inline bool permutation_change_array(struct permutation *pi,
 153                                             void *base, size_t size)
 154 {
 155         permutation_swap_t swap = permutation_change(pi);
 156
 157         permutation_swap_mem(base, size, swap);
 158         return (swap != 0);
 159 }
 160
 161 static inline bool permutation_change_array_check_(struct permutation *pi,
 162                                                    void *base, size_t size,
 163                                                    int n)
 164 {
 165         assert(n == pi->n);
 166         return permutation_change_array(pi, base, size);
 167 }
 168
 169 /**
 170  * PERMUTATION_CHANGE_ARRAY - Advance an array to a new permutation
 171  * @pi_: Current permutation
 172  * @a_: Array
 173  *
 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_.
 176  */
 177 #define PERMUTATION_CHANGE_ARRAY(pi_, a_)                               \
 178         (permutation_change_array_check_((pi_), (a_),                   \
 179                                          sizeof((a_)[0]), ARRAY_SIZE(a_)))
 180
 181 #endif /* CCAN_PERMUTATION_H */