matrixfurry.com
The open source OpenXR runtime
1// Copyright 2020, Collabora, Ltd.
2// SPDX-License-Identifier: BSL-1.0
3/*!
4 * @file
5 * @brief Code to generate permutation of indices.
6 * @author Jakob Bornecrantz <jakob@collabora.com>
7 * @ingroup aux_math
8 */
9
10
11#include "util/u_misc.h"
12#include "util/u_logging.h"
13
14#include "m_permutation.h"
15
16
17/*
18 *
19 * Helper functions
20 *
21 */
22
23static void
24swap(uint32_t *array, uint32_t a, uint32_t b)
25{
26 int tmp = array[a];
27 array[a] = array[b];
28 array[b] = tmp;
29}
30
31static void
32copy(struct m_permutator *mp, uint32_t *out_elements)
33{
34 for (uint32_t i = 0; i < mp->n; i++) {
35 out_elements[i] = mp->elements[i];
36 }
37}
38
39static void
40setup(struct m_permutator *mp, uint32_t num_elements)
41{
42 mp->i = 0;
43 mp->n = num_elements;
44 mp->indices = U_TYPED_ARRAY_CALLOC(uint32_t, num_elements);
45 mp->elements = U_TYPED_ARRAY_CALLOC(uint32_t, num_elements);
46 for (uint32_t i = 0; i < mp->n; i++) {
47 mp->indices[i] = 0;
48 mp->elements[i] = i;
49 }
50}
51
52static bool
53step(struct m_permutator *mp)
54{
55 while (mp->i < mp->n) {
56 if (mp->indices[mp->i] < mp->i) {
57 uint32_t a = mp->i % 2 == 0 ? 0 : mp->indices[mp->i];
58 uint32_t b = mp->i;
59 swap(mp->elements, a, b);
60 mp->indices[mp->i]++;
61 mp->i = 0;
62 return true;
63 }
64 mp->indices[mp->i] = 0;
65 mp->i++;
66 }
67
68 return false;
69}
70
71
72/*
73 *
74 * 'Exported' functions.
75 *
76 */
77
78bool
79m_permutator_step(struct m_permutator *mp, uint32_t *out_elements, uint32_t num_elements)
80{
81 if (mp->indices == NULL || mp->n != num_elements) {
82 setup(mp, num_elements);
83 copy(mp, out_elements);
84 return true;
85 }
86 if (step(mp)) {
87
88 copy(mp, out_elements);
89 return true;
90 } else {
91 return false;
92 }
93}
94
95void
96m_permutator_reset(struct m_permutator *mp)
97{
98 if (mp->indices != NULL) {
99 free(mp->indices);
100 mp->indices = NULL;
101 }
102 if (mp->elements != NULL) {
103 free(mp->elements);
104 mp->elements = NULL;
105 }
106
107 U_ZERO(mp);
108}
109
110
111/*
112 *
113 * Debug functions.
114 *
115 */
116
117#if 1
118
119#include <stdio.h>
120
121static void
122printArray(const uint32_t *array, uint32_t num)
123{
124 static int count = 0;
125 fprintf(stderr, "GLARG #%i: ", count++);
126 for (uint32_t i = 0; i < num; i++) {
127 fprintf(stderr, "%i, ", array[i]);
128 }
129 fprintf(stderr, "\n");
130}
131
132void
133m_do_the_thing(void)
134{
135 struct m_permutator mp = {0};
136 uint32_t elements[7];
137 uint32_t size = ARRAY_SIZE(elements);
138 while (m_permutator_step(&mp, elements, size)) {
139 printArray(elements, size);
140 }
141
142 m_permutator_reset(&mp);
143
144 U_LOG_D("BLARG!");
145}
146
147#endif