git.sesse.net Git - bcachefs-tools-debian/blob - c_src/raid/combo.h

   1 /*
   2  * Copyright (C) 2013 Andrea Mazzoleni
   3  *
   4  * This program is free software: you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation, either version 2 of the License, or
   7  * (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  */
  14
  15 #ifndef __RAID_COMBO_H
  16 #define __RAID_COMBO_H
  17
  18 #include <assert.h>
  19
  20 /**
  21  * Get the first permutation with repetition of r of n elements.
  22  *
  23  * Typical use is with permutation_next() in the form :
  24  *
  25  * int i[R];
  26  * permutation_first(R, N, i);
  27  * do {
  28  *    code using i[0], i[1], ..., i[R-1]
  29  * } while (permutation_next(R, N, i));
  30  *
  31  * It's equivalent at the code :
  32  *
  33  * for(i[0]=0;i[0]<N;++i[0])
  34  *     for(i[1]=0;i[1]<N;++i[1])
  35  *        ...
  36  *            for(i[R-2]=0;i[R-2]<N;++i[R-2])
  37  *                for(i[R-1]=0;i[R-1]<N;++i[R-1])
  38  *                    code using i[0], i[1], ..., i[R-1]
  39  */
  40 static __always_inline void permutation_first(int r, int n, int *c)
  41 {
  42         int i;
  43
  44         (void)n; /* unused, but kept for clarity */
  45         assert(0 < r && r <= n);
  46
  47         for (i = 0; i < r; ++i)
  48                 c[i] = 0;
  49 }
  50
  51 /**
  52  * Get the next permutation with repetition of r of n elements.
  53  * Return ==0 when finished.
  54  */
  55 static __always_inline int permutation_next(int r, int n, int *c)
  56 {
  57         int i = r - 1; /* present position */
  58
  59 recurse:
  60         /* next element at position i */
  61         ++c[i];
  62
  63         /* if the position has reached the max */
  64         if (c[i] >= n) {
  65
  66                 /* if we are at the first level, we have finished */
  67                 if (i == 0)
  68                         return 0;
  69
  70                 /* increase the previous position */
  71                 --i;
  72                 goto recurse;
  73         }
  74
  75         ++i;
  76
  77         /* initialize all the next positions, if any */
  78         while (i < r) {
  79                 c[i] = 0;
  80                 ++i;
  81         }
  82
  83         return 1;
  84 }
  85
  86 /**
  87  * Get the first combination without repetition of r of n elements.
  88  *
  89  * Typical use is with combination_next() in the form :
  90  *
  91  * int i[R];
  92  * combination_first(R, N, i);
  93  * do {
  94  *    code using i[0], i[1], ..., i[R-1]
  95  * } while (combination_next(R, N, i));
  96  *
  97  * It's equivalent at the code :
  98  *
  99  * for(i[0]=0;i[0]<N-(R-1);++i[0])
 100  *     for(i[1]=i[0]+1;i[1]<N-(R-2);++i[1])
 101  *        ...
 102  *            for(i[R-2]=i[R-3]+1;i[R-2]<N-1;++i[R-2])
 103  *                for(i[R-1]=i[R-2]+1;i[R-1]<N;++i[R-1])
 104  *                    code using i[0], i[1], ..., i[R-1]
 105  */
 106 static __always_inline void combination_first(int r, int n, int *c)
 107 {
 108         int i;
 109
 110         (void)n; /* unused, but kept for clarity */
 111         assert(0 < r && r <= n);
 112
 113         for (i = 0; i < r; ++i)
 114                 c[i] = i;
 115 }
 116
 117 /**
 118  * Get the next combination without repetition of r of n elements.
 119  * Return ==0 when finished.
 120  */
 121 static __always_inline int combination_next(int r, int n, int *c)
 122 {
 123         int i = r - 1; /* present position */
 124         int h = n; /* high limit for this position */
 125
 126 recurse:
 127         /* next element at position i */
 128         ++c[i];
 129
 130         /* if the position has reached the max */
 131         if (c[i] >= h) {
 132
 133                 /* if we are at the first level, we have finished */
 134                 if (i == 0)
 135                         return 0;
 136
 137                 /* increase the previous position */
 138                 --i;
 139                 --h;
 140                 goto recurse;
 141         }
 142
 143         ++i;
 144
 145         /* initialize all the next positions, if any */
 146         while (i < r) {
 147                 /* each position start at the next value of the previous one */
 148                 c[i] = c[i - 1] + 1;
 149                 ++i;
 150         }
 151
 152         return 1;
 153 }
 154 #endif
 155