147 static int init_groups(struct isl_factor_groups *g, __isl_keep isl_mat *H)  in init_groups()  argument
154 	g->pos = isl_alloc_array(H->ctx, int, H->n_col);  in init_groups()
155 	g->group = isl_alloc_array(H->ctx, int, H->n_col);  in init_groups()
156 	g->cnt = isl_alloc_array(H->ctx, int, H->n_col);  in init_groups()
157 	g->rowgroup = isl_alloc_array(H->ctx, int, H->n_row);  in init_groups()
159 	if (!g->pos || !g->group || !g->cnt || !g->rowgroup)  in init_groups()
163 		g->rowgroup[i] = -1;  in init_groups()
168 		g->pos[i] = j;  in init_groups()
171 		g->group[i] = i;  in init_groups()
172 		g->cnt[i] = 1;  in init_groups()
184 static void update_group(struct isl_factor_groups *g, int k)  in update_group()  argument
186 	int p = g->group[k];  in update_group()
187 	while (g->cnt[p] == 0)  in update_group()
188 		p = g->group[p];  in update_group()
189 	g->group[k] = p;  in update_group()
197 static int update_group_i_with_row_j(struct isl_factor_groups *g, int i, int j,  in update_group_i_with_row_j()  argument
202 	g->rowgroup[j] = g->group[i];  in update_group_i_with_row_j()
203 	for (k = i + 1; k < H->n_col && j >= g->pos[k]; ++k) {  in update_group_i_with_row_j()
204 		update_group(g, k);  in update_group_i_with_row_j()
205 		update_group(g, i);  in update_group_i_with_row_j()
206 		if (g->group[k] != g->group[i] &&  in update_group_i_with_row_j()
208 			isl_assert(H->ctx, g->cnt[g->group[k]] != 0, return -1);  in update_group_i_with_row_j()
209 			isl_assert(H->ctx, g->cnt[g->group[i]] != 0, return -1);  in update_group_i_with_row_j()
210 			if (g->group[i] < g->group[k]) {  in update_group_i_with_row_j()
211 				g->cnt[g->group[i]] += g->cnt[g->group[k]];  in update_group_i_with_row_j()
212 				g->cnt[g->group[k]] = 0;  in update_group_i_with_row_j()
213 				g->group[g->group[k]] = g->group[i];  in update_group_i_with_row_j()
215 				g->cnt[g->group[k]] += g->cnt[g->group[i]];  in update_group_i_with_row_j()
216 				g->cnt[g->group[i]] = 0;  in update_group_i_with_row_j()
217 				g->group[g->group[i]] = g->group[k];  in update_group_i_with_row_j()
227 static int update_groups(struct isl_factor_groups *g, __isl_keep isl_mat *H)  in update_groups()  argument
231 	for (i = 0; i < H->n_col && g->cnt[0] < H->n_col; ++i) {  in update_groups()
232 		if (g->pos[i] == H->n_row)  in update_groups()
234 		if (g->rowgroup[g->pos[i]] == -1)  in update_groups()
235 			g->rowgroup[g->pos[i]] = i;  in update_groups()
236 		for (j = g->pos[i] + 1; j < H->n_row; ++j) {  in update_groups()
239 			if (g->rowgroup[j] != -1)  in update_groups()
241 			if (update_group_i_with_row_j(g, i, j, H) < 0)  in update_groups()
246 		update_group(g, i);  in update_groups()
251 static void clear_groups(struct isl_factor_groups *g)  in clear_groups()  argument
253 	if (!g)  in clear_groups()
255 	free(g->pos);  in clear_groups()
256 	free(g->group);  in clear_groups()
257 	free(g->cnt);  in clear_groups()
258 	free(g->rowgroup);  in clear_groups()
275 	struct isl_factor_groups g = { 0 };  in isl_basic_set_factorizer()  local
294 	if (init_groups(&g, H) < 0)  in isl_basic_set_factorizer()
296 	if (update_groups(&g, H) < 0)  in isl_basic_set_factorizer()
299 	if (g.cnt[0] == nvar) {  in isl_basic_set_factorizer()
303 		clear_groups(&g);  in isl_basic_set_factorizer()
311 		int group = g.group[done];  in isl_basic_set_factorizer()
312 		for (i = 1; i < g.cnt[group]; ++i) {  in isl_basic_set_factorizer()
313 			if (g.group[done + i] == group)  in isl_basic_set_factorizer()
315 			for (j = done + g.cnt[group]; j < nvar; ++j)  in isl_basic_set_factorizer()
316 				if (g.group[j] == group)  in isl_basic_set_factorizer()
321 			g.group[j] = g.group[done + i];  in isl_basic_set_factorizer()
325 		done += g.cnt[group];  in isl_basic_set_factorizer()
326 		g.pos[n++] = g.cnt[group];  in isl_basic_set_factorizer()
329 	f = isl_factorizer_groups(bset, Q, U, n, g.pos);  in isl_basic_set_factorizer()
332 	clear_groups(&g);  in isl_basic_set_factorizer()
339 	clear_groups(&g);  in isl_basic_set_factorizer()