1 /*
2 * Copyright (C) 2018 Karel Zak <kzak@redhat.com>
3 */
4 #include "smartcolsP.h"
5
6 /**
7 * SECTION: grouping
8 * @title: Grouping
9 * @short_description: lines grouing
10 *
11 * Lines groups manipulation API. The grouping API can be used to create M:N
12 * relations between lines and on tree-like output it prints extra chart to
13 * visualize these relations. The group has unlimited number of members and
14 * group childs. See libsmartcols/sample/grouping* for more details.
15 */
16
17 /* Private API */
scols_ref_group(struct libscols_group * gr)18 void scols_ref_group(struct libscols_group *gr)
19 {
20 if (gr)
21 gr->refcount++;
22 }
23
scols_group_remove_children(struct libscols_group * gr)24 void scols_group_remove_children(struct libscols_group *gr)
25 {
26 if (!gr)
27 return;
28
29 while (!list_empty(&gr->gr_children)) {
30 struct libscols_line *ln = list_entry(gr->gr_children.next,
31 struct libscols_line, ln_children);
32
33 DBG(GROUP, ul_debugobj(gr, "remove child"));
34 list_del_init(&ln->ln_children);
35 scols_ref_group(ln->parent_group);
36 ln->parent_group = NULL;
37 scols_unref_line(ln);
38 }
39 }
40
scols_group_remove_members(struct libscols_group * gr)41 void scols_group_remove_members(struct libscols_group *gr)
42 {
43 if (!gr)
44 return;
45
46 while (!list_empty(&gr->gr_members)) {
47 struct libscols_line *ln = list_entry(gr->gr_members.next,
48 struct libscols_line, ln_groups);
49
50 DBG(GROUP, ul_debugobj(gr, "remove member [%p]", ln));
51 list_del_init(&ln->ln_groups);
52
53 scols_unref_group(ln->group);
54 ln->group->nmembers++;
55 ln->group = NULL;
56
57 scols_unref_line(ln);
58 }
59 }
60
61 /* note group has to be already without members to deallocate */
scols_unref_group(struct libscols_group * gr)62 void scols_unref_group(struct libscols_group *gr)
63 {
64 if (gr && --gr->refcount <= 0) {
65 DBG(GROUP, ul_debugobj(gr, "dealloc"));
66 scols_group_remove_children(gr);
67 list_del(&gr->gr_groups);
68 free(gr);
69 return;
70 }
71 }
72
73
groups_fix_members_order(struct libscols_line * ln)74 static void groups_fix_members_order(struct libscols_line *ln)
75 {
76 struct libscols_iter itr;
77 struct libscols_line *child;
78
79 if (ln->group) {
80 INIT_LIST_HEAD(&ln->ln_groups);
81 list_add_tail(&ln->ln_groups, &ln->group->gr_members);
82 DBG(GROUP, ul_debugobj(ln->group, "fixing member line=%p [%zu/%zu]",
83 ln, ln->group->nmembers,
84 list_count_entries(&ln->group->gr_members)));
85 }
86
87 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
88 while (scols_line_next_child(ln, &itr, &child) == 0)
89 groups_fix_members_order(child);
90
91 /*
92 * We modify gr_members list, so is_last_group_member() does not have
93 * to provide reliable answer, we need to verify by list_count_entries().
94 */
95 if (ln->group
96 && is_last_group_member(ln)
97 && ln->group->nmembers == list_count_entries(&ln->group->gr_members)) {
98
99 DBG(GROUP, ul_debugobj(ln->group, "fixing childs"));
100 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
101 while (scols_line_next_group_child(ln, &itr, &child) == 0)
102 groups_fix_members_order(child);
103 }
104 }
105
scols_groups_fix_members_order(struct libscols_table * tb)106 void scols_groups_fix_members_order(struct libscols_table *tb)
107 {
108 struct libscols_iter itr;
109 struct libscols_line *ln;
110 struct libscols_group *gr;
111
112 /* remove all from groups lists */
113 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
114 while (scols_table_next_group(tb, &itr, &gr) == 0) {
115 while (!list_empty(&gr->gr_members)) {
116 struct libscols_line *line = list_entry(gr->gr_members.next,
117 struct libscols_line, ln_groups);
118 list_del_init(&line->ln_groups);
119 }
120 }
121
122 /* add again to the groups list in order we walk in tree */
123 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
124 while (scols_table_next_line(tb, &itr, &ln) == 0) {
125 if (ln->parent || ln->parent_group)
126 continue;
127 groups_fix_members_order(ln);
128 }
129
130 /* If group child is member of another group *
131 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
132 while (scols_table_next_group(tb, &itr, &gr) == 0) {
133 struct libscols_iter xitr;
134 struct libscols_line *child;
135
136 scols_reset_iter(&xitr, SCOLS_ITER_FORWARD);
137 while (scols_line_next_group_child(ln, &xitr, &child) == 0)
138 groups_fix_members_order(child);
139 }
140 */
141 }
142
group_state_to_string(int state)143 static inline const char *group_state_to_string(int state)
144 {
145 static const char *grpstates[] = {
146 [SCOLS_GSTATE_NONE] = "none",
147 [SCOLS_GSTATE_FIRST_MEMBER] = "1st-member",
148 [SCOLS_GSTATE_MIDDLE_MEMBER] = "middle-member",
149 [SCOLS_GSTATE_LAST_MEMBER] = "last-member",
150 [SCOLS_GSTATE_MIDDLE_CHILD] = "middle-child",
151 [SCOLS_GSTATE_LAST_CHILD] = "last-child",
152 [SCOLS_GSTATE_CONT_MEMBERS] = "continue-members",
153 [SCOLS_GSTATE_CONT_CHILDREN] = "continue-children"
154 };
155
156 assert(state >= 0);
157 assert((size_t) state < ARRAY_SIZE(grpstates));
158
159 return grpstates[state];
160 }
161 /*
162 static void grpset_debug(struct libscols_table *tb, struct libscols_line *ln)
163 {
164 size_t i;
165
166 for (i = 0; i < tb->grpset_size; i++) {
167 if (tb->grpset[i]) {
168 struct libscols_group *gr = tb->grpset[i];
169
170 if (ln)
171 DBG(LINE, ul_debugobj(ln, "grpset[%zu]: %p %s", i,
172 gr, group_state_to_string(gr->state)));
173 else
174 DBG(LINE, ul_debug("grpset[%zu]: %p %s", i,
175 gr, group_state_to_string(gr->state)));
176 } else if (ln) {
177 DBG(LINE, ul_debugobj(ln, "grpset[%zu]: free", i));
178 } else
179 DBG(LINE, ul_debug("grpset[%zu]: free", i));
180 }
181 }
182 */
group_state_for_line(struct libscols_group * gr,struct libscols_line * ln)183 static int group_state_for_line(struct libscols_group *gr, struct libscols_line *ln)
184 {
185 if (gr->state == SCOLS_GSTATE_NONE &&
186 (ln->group != gr || !is_first_group_member(ln)))
187 /*
188 * NONE is possible to translate to FIRST_MEMBER only, and only if
189 * line group matches with the current group.
190 */
191 return SCOLS_GSTATE_NONE;
192
193 if (ln->group != gr && ln->parent_group != gr) {
194 /* Not our line, continue */
195 if (gr->state == SCOLS_GSTATE_FIRST_MEMBER ||
196 gr->state == SCOLS_GSTATE_MIDDLE_MEMBER ||
197 gr->state == SCOLS_GSTATE_CONT_MEMBERS)
198 return SCOLS_GSTATE_CONT_MEMBERS;
199
200 if (gr->state == SCOLS_GSTATE_LAST_MEMBER ||
201 gr->state == SCOLS_GSTATE_MIDDLE_CHILD ||
202 gr->state == SCOLS_GSTATE_CONT_CHILDREN)
203 return SCOLS_GSTATE_CONT_CHILDREN;
204
205 } else if (ln->group == gr && is_first_group_member(ln)) {
206 return SCOLS_GSTATE_FIRST_MEMBER;
207
208 } else if (ln->group == gr && is_last_group_member(ln)) {
209 return SCOLS_GSTATE_LAST_MEMBER;
210
211 } else if (ln->group == gr && is_group_member(ln)) {
212 return SCOLS_GSTATE_MIDDLE_MEMBER;
213
214 } else if (ln->parent_group == gr && is_last_group_child(ln)) {
215 return SCOLS_GSTATE_LAST_CHILD;
216
217 } else if (ln->parent_group == gr && is_group_child(ln)) {
218 return SCOLS_GSTATE_MIDDLE_CHILD;
219 }
220
221 return SCOLS_GSTATE_NONE;
222 }
223
224 /*
225 * apply new @state to the chunk (addressed by @xx) of grpset used for the group (@gr)
226 */
grpset_apply_group_state(struct libscols_group ** xx,int state,struct libscols_group * gr)227 static void grpset_apply_group_state(struct libscols_group **xx, int state, struct libscols_group *gr)
228 {
229 size_t i;
230
231 DBG(GROUP, ul_debugobj(gr, " applying state to grpset"));
232
233 /* gr->state holds the old state, @state is the new state
234 */
235 for (i = 0; i < SCOLS_GRPSET_CHUNKSIZ; i++)
236 xx[i] = state == SCOLS_GSTATE_NONE ? NULL : gr;
237
238 gr->state = state;
239 }
240
grpset_locate_freespace(struct libscols_table * tb,int chunks,int prepend)241 static struct libscols_group **grpset_locate_freespace(struct libscols_table *tb, int chunks, int prepend)
242 {
243 size_t i, avail = 0;
244 struct libscols_group **tmp, **first = NULL;
245 const size_t wanted = chunks * SCOLS_GRPSET_CHUNKSIZ;
246
247 if (!tb->grpset_size)
248 prepend = 0;
249 /*
250 DBG(TAB, ul_debugobj(tb, "orig grpset:"));
251 grpset_debug(tb, NULL);
252 */
253 if (prepend) {
254 for (i = tb->grpset_size - 1; ; i--) {
255 if (tb->grpset[i] == NULL) {
256 first = &tb->grpset[i];
257 avail++;
258 } else
259 avail = 0;
260 if (avail == wanted)
261 goto done;
262 if (i == 0)
263 break;
264 }
265 } else {
266 for (i = 0; i < tb->grpset_size; i++) {
267 if (tb->grpset[i] == NULL) {
268 if (avail == 0)
269 first = &tb->grpset[i];
270 avail++;
271 } else
272 avail = 0;
273 if (avail == wanted)
274 goto done;
275 }
276 }
277
278 DBG(TAB, ul_debugobj(tb, " realocate grpset [sz: old=%zu, new=%zu, new_chunks=%d]",
279 tb->grpset_size, tb->grpset_size + wanted, chunks));
280
281 tmp = realloc(tb->grpset, (tb->grpset_size + wanted) * sizeof(struct libscols_group *));
282 if (!tmp)
283 return NULL;
284
285 tb->grpset = tmp;
286
287 if (prepend) {
288 DBG(TAB, ul_debugobj(tb, " prepending free space"));
289 char *dest = (char *) tb->grpset;
290
291 memmove( dest + (wanted * sizeof(struct libscols_group *)),
292 tb->grpset,
293 tb->grpset_size * sizeof(struct libscols_group *));
294 first = tb->grpset;
295 } else {
296 first = tb->grpset + tb->grpset_size;
297 }
298
299 memset(first, 0, wanted * sizeof(struct libscols_group *));
300 tb->grpset_size += wanted;
301
302 done:
303 /*
304 DBG(TAB, ul_debugobj(tb, "new grpset:"));
305 grpset_debug(tb, NULL);
306 */
307 return first;
308 }
309
grpset_locate_group(struct libscols_table * tb,struct libscols_group * gr)310 static struct libscols_group **grpset_locate_group(struct libscols_table *tb, struct libscols_group *gr)
311 {
312 size_t i;
313
314 for (i = 0; i < tb->grpset_size; i++) {
315 if (gr == tb->grpset[i])
316 return &tb->grpset[i];
317 }
318
319 return NULL;
320 }
321
322
grpset_update(struct libscols_table * tb,struct libscols_line * ln,struct libscols_group * gr)323 static int grpset_update(struct libscols_table *tb, struct libscols_line *ln, struct libscols_group *gr)
324 {
325 struct libscols_group **xx;
326 int state;
327
328 DBG(LINE, ul_debugobj(ln, " group [%p] grpset update [grpset size=%zu]", gr, tb->grpset_size));
329
330 /* new state, note that gr->state still holds the original state */
331 state = group_state_for_line(gr, ln);
332 DBG(LINE, ul_debugobj(ln, " state %s --> %s",
333 group_state_to_string(gr->state),
334 group_state_to_string(state)));
335
336 if (state == SCOLS_GSTATE_FIRST_MEMBER && gr->state != SCOLS_GSTATE_NONE) {
337 DBG(LINE, ul_debugobj(ln, "wrong group initialization (%s)", group_state_to_string(gr->state)));
338 abort();
339 }
340 if (state != SCOLS_GSTATE_NONE && gr->state == SCOLS_GSTATE_LAST_CHILD) {
341 DBG(LINE, ul_debugobj(ln, "wrong group termination (%s)", group_state_to_string(gr->state)));
342 abort();
343 }
344 if (gr->state == SCOLS_GSTATE_LAST_MEMBER &&
345 !(state == SCOLS_GSTATE_LAST_CHILD ||
346 state == SCOLS_GSTATE_CONT_CHILDREN ||
347 state == SCOLS_GSTATE_MIDDLE_CHILD ||
348 state == SCOLS_GSTATE_NONE)) {
349 DBG(LINE, ul_debugobj(ln, "wrong group member->child order"));
350 abort();
351 }
352
353 /* should not happen; probably wrong line... */
354 if (gr->state == SCOLS_GSTATE_NONE && state == SCOLS_GSTATE_NONE)
355 return 0;
356
357 /* locate place in grpset where we draw the group */
358 if (!tb->grpset || gr->state == SCOLS_GSTATE_NONE)
359 xx = grpset_locate_freespace(tb, 1, 1);
360 else
361 xx = grpset_locate_group(tb, gr);
362 if (!xx) {
363 DBG(LINE, ul_debugobj(ln, "failed to locate group or reallocate grpset"));
364 return -ENOMEM;
365 }
366
367 grpset_apply_group_state(xx, state, gr);
368 /*ON_DBG(LINE, grpset_debug(tb, ln));*/
369 return 0;
370 }
371
grpset_update_active_groups(struct libscols_table * tb,struct libscols_line * ln)372 static int grpset_update_active_groups(struct libscols_table *tb, struct libscols_line *ln)
373 {
374 int rc = 0;
375 size_t i;
376 struct libscols_group *last = NULL;
377
378 DBG(LINE, ul_debugobj(ln, " update for active groups"));
379
380 for (i = 0; i < tb->grpset_size; i++) {
381 struct libscols_group *gr = tb->grpset[i];
382
383 if (!gr || last == gr)
384 continue;
385 last = gr;
386 rc = grpset_update(tb, ln, gr);
387 if (rc)
388 break;
389 }
390
391 DBG(LINE, ul_debugobj(ln, " <- active groups updated [rc=%d]", rc));
392 return rc;
393 }
394
scols_groups_update_grpset(struct libscols_table * tb,struct libscols_line * ln)395 int scols_groups_update_grpset(struct libscols_table *tb, struct libscols_line *ln)
396 {
397 int rc = 0;
398
399 DBG(LINE, ul_debugobj(ln, " grpset update [line: group=%p, parent_group=%p",
400 ln->group, ln->parent_group));
401
402 rc = grpset_update_active_groups(tb, ln);
403 if (!rc && ln->group && ln->group->state == SCOLS_GSTATE_NONE) {
404 DBG(LINE, ul_debugobj(ln, " introduce a new group"));
405 rc = grpset_update(tb, ln, ln->group);
406 }
407 return rc;
408 }
409
scols_groups_reset_state(struct libscols_table * tb)410 void scols_groups_reset_state(struct libscols_table *tb)
411 {
412 struct libscols_iter itr;
413 struct libscols_group *gr;
414
415 DBG(TAB, ul_debugobj(tb, "reset groups states"));
416
417 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
418 while (scols_table_next_group(tb, &itr, &gr) == 0) {
419 DBG(GROUP, ul_debugobj(gr, " reset to NONE"));
420 gr->state = SCOLS_GSTATE_NONE;
421 }
422
423 if (tb->grpset) {
424 DBG(TAB, ul_debugobj(tb, " zeroize grpset"));
425 memset(tb->grpset, 0, tb->grpset_size * sizeof(struct libscols_group *));
426 }
427 tb->ngrpchlds_pending = 0;
428 }
429
add_member(struct libscols_group * gr,struct libscols_line * ln)430 static void add_member(struct libscols_group *gr, struct libscols_line *ln)
431 {
432 DBG(GROUP, ul_debugobj(gr, "add member %p", ln));
433
434 ln->group = gr;
435 gr->nmembers++;
436 scols_ref_group(gr);
437
438 INIT_LIST_HEAD(&ln->ln_groups);
439 list_add_tail(&ln->ln_groups, &gr->gr_members);
440 scols_ref_line(ln);
441 }
442
443 /*
444 * Returns first group which is ready to print group children.
445 *
446 * This function scans grpset[] in backward order and returns first group
447 * with SCOLS_GSTATE_CONT_CHILDREN or SCOLS_GSTATE_LAST_MEMBER state.
448 */
scols_grpset_get_printable_children(struct libscols_table * tb)449 struct libscols_group *scols_grpset_get_printable_children(struct libscols_table *tb)
450 {
451 size_t i;
452
453 for (i = tb->grpset_size; i > 0; i -= SCOLS_GRPSET_CHUNKSIZ) {
454 struct libscols_group *gr = tb->grpset[i-1];
455
456 if (gr == NULL)
457 continue;
458 if (gr->state == SCOLS_GSTATE_CONT_CHILDREN ||
459 gr->state == SCOLS_GSTATE_LAST_MEMBER)
460 return gr;
461 }
462
463 return NULL;
464 }
465
466
467 /**
468 * scols_table_group_lines:
469 * @tb: a pointer to a struct libscols_table instance
470 * @ln: new group member
471 * @member: group member
472 * @id: group identifier (unused, not implemented yet), use zero.
473 *
474 * This function add line @ln to group of lines represented by @member. If the
475 * group is not yet defined (@member is not member of any group) than a new one
476 * is allocated.
477 *
478 * The @ln maybe a NULL -- in this case only a new group is allocated if not
479 * defined yet.
480 *
481 * Note that the same line cannot be member of more groups (not implemented
482 * yet). The child of any group can be member of another group.
483 *
484 * The @id is not used for now, use 0. The plan is to use it to support
485 * multi-group membership in future.
486 *
487 * Returns: 0, a negative value in case of an error.
488 *
489 * Since: 2.34
490 */
scols_table_group_lines(struct libscols_table * tb,struct libscols_line * ln,struct libscols_line * member,int id)491 int scols_table_group_lines( struct libscols_table *tb,
492 struct libscols_line *ln,
493 struct libscols_line *member,
494 __attribute__((__unused__)) int id)
495 {
496 struct libscols_group *gr = NULL;
497
498 if (!tb || !member) {
499 DBG(GROUP, ul_debugobj(gr, "failed group lines (no table or member)"));
500 return -EINVAL;
501 }
502 if (ln) {
503 if (ln->group && !member->group) {
504 DBG(GROUP, ul_debugobj(gr, "failed group lines (new group, line member of another)"));
505 return -EINVAL;
506 }
507 if (ln->group && member->group && ln->group != member->group) {
508 DBG(GROUP, ul_debugobj(gr, "failed group lines (groups mismatch bwteen member and line"));
509 return -EINVAL;
510 }
511 }
512
513 gr = member->group;
514
515 /* create a new group */
516 if (!gr) {
517 gr = calloc(1, sizeof(*gr));
518 if (!gr)
519 return -ENOMEM;
520 DBG(GROUP, ul_debugobj(gr, "alloc"));
521 gr->refcount = 1;
522 INIT_LIST_HEAD(&gr->gr_members);
523 INIT_LIST_HEAD(&gr->gr_children);
524 INIT_LIST_HEAD(&gr->gr_groups);
525
526 /* add group to the table */
527 list_add_tail(&gr->gr_groups, &tb->tb_groups);
528
529 /* add the first member */
530 add_member(gr, member);
531 }
532
533 /* add to group */
534 if (ln && !ln->group)
535 add_member(gr, ln);
536
537 return 0;
538 }
539
540 /**
541 * scols_line_link_group:
542 * @ln: line instance
543 * @member: group member
544 * @id: group identifier (unused, not implemented yet))
545 *
546 * Define @ln as child of group represented by group @member. The line @ln
547 * cannot be child of any other line. It's possible to create group->child or
548 * parent->child relationship, but no both for the same line (child).
549 *
550 * The @id is not used for now, use 0. The plan is to use it to support
551 * multi-group membership in future.
552 *
553 * Returns: 0, a negative value in case of an error.
554 *
555 * Since: 2.34
556 */
scols_line_link_group(struct libscols_line * ln,struct libscols_line * member,int id)557 int scols_line_link_group(struct libscols_line *ln, struct libscols_line *member,
558 __attribute__((__unused__)) int id)
559 {
560 if (!ln || !member || !member->group || ln->parent)
561 return -EINVAL;
562
563 if (!list_empty(&ln->ln_children))
564 return -EINVAL;
565
566 DBG(GROUP, ul_debugobj(member->group, "add child"));
567
568 list_add_tail(&ln->ln_children, &member->group->gr_children);
569 scols_ref_line(ln);
570
571 ln->parent_group = member->group;
572 scols_ref_group(member->group);
573
574 return 0;
575 }
576