libsmartcols/src/grouping.c

   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 allows 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 */
  18 void scols_ref_group(struct libscols_group *gr)
  19 {
  20         if (gr)
  21                 gr->refcount++;
  22 }
  23
  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
  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 */
  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
  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
 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 memeber 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
 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 static int group_state_for_line(struct libscols_group *gr, struct libscols_line *ln)
 183 {
 184         if (gr->state == SCOLS_GSTATE_NONE &&
 185             (ln->group != gr || !is_first_group_member(ln)))
 186                 /*
 187                  * NONE is possible to translate to FIRST_MEMBER only, and only if
 188                  * line group matches with the current group.
 189                  */
 190                 return SCOLS_GSTATE_NONE;
 191
 192         if (ln->group != gr && ln->parent_group != gr) {
 193                 /* Not our line, continue */
 194                 if (gr->state == SCOLS_GSTATE_FIRST_MEMBER ||
 195                     gr->state == SCOLS_GSTATE_MIDDLE_MEMBER ||
 196                     gr->state == SCOLS_GSTATE_CONT_MEMBERS)
 197                         return SCOLS_GSTATE_CONT_MEMBERS;
 198
 199                 if (gr->state == SCOLS_GSTATE_LAST_MEMBER ||
 200                     gr->state == SCOLS_GSTATE_MIDDLE_CHILD ||
 201                     gr->state == SCOLS_GSTATE_CONT_CHILDREN)
 202                         return SCOLS_GSTATE_CONT_CHILDREN;
 203
 204         } else if (ln->group == gr && is_first_group_member(ln)) {
 205                 return SCOLS_GSTATE_FIRST_MEMBER;
 206
 207         } else if (ln->group == gr && is_last_group_member(ln)) {
 208                 return SCOLS_GSTATE_LAST_MEMBER;
 209
 210         } else if (ln->group == gr && is_group_member(ln)) {
 211                 return SCOLS_GSTATE_MIDDLE_MEMBER;
 212
 213         } else if (ln->parent_group == gr && is_last_group_child(ln)) {
 214                 return SCOLS_GSTATE_LAST_CHILD;
 215
 216         } else if (ln->parent_group == gr && is_group_child(ln)) {
 217                 return SCOLS_GSTATE_MIDDLE_CHILD;
 218         }
 219
 220         return SCOLS_GSTATE_NONE;
 221 }
 222
 223 /* For now we assume that each active group is just 3 columns width. Later we can make it dynamic...
 224  */
 225 static void grpset_apply_group_state(struct libscols_group **xx, int state, struct libscols_group *gr)
 226 {
 227         DBG(GROUP, ul_debugobj(gr, "   appling state to grpset"));
 228
 229         /* gr->state holds the old state, @state is the new state
 230          */
 231         if (state == SCOLS_GSTATE_NONE)
 232                 xx[0] = xx[1] = xx[2] = NULL;
 233         else
 234                 xx[0] = xx[1] = xx[2] = gr;
 235         gr->state = state;
 236 }
 237
 238 static struct libscols_group **grpset_locate_freespace(struct libscols_table *tb, size_t wanted, int prepend)
 239 {
 240         size_t i, avail = 0;
 241         struct libscols_group **tmp, **first = NULL;
 242
 243         if (!tb->grpset_size)
 244                 prepend = 0;
 245
 246         if (prepend) {
 247                 for (i = tb->grpset_size - 1; ; i--) {
 248                         if (tb->grpset[i] == NULL) {
 249                                 first = &tb->grpset[i];
 250                                 avail++;
 251                         } else
 252                                 avail = 0;
 253                         if (avail == wanted)
 254                                 goto done;
 255                         if (i == 0)
 256                                 break;
 257                 }
 258         } else {
 259                 for (i = 0; i < tb->grpset_size; i++) {
 260                         if (tb->grpset[i] == NULL) {
 261                                 if (avail == 0)
 262                                         first = &tb->grpset[i];
 263                                 avail++;
 264                         } else
 265                                 avail = 0;
 266                         if (avail == wanted)
 267                                 goto done;
 268                 }
 269         }
 270
 271         DBG(TAB, ul_debugobj(tb, "   realocate grpset [sz: old=%zu, new=%zu]",
 272                                 tb->grpset_size, tb->grpset_size + wanted));
 273
 274         tmp = realloc(tb->grpset, (tb->grpset_size + wanted) * sizeof(struct libscols_group *));
 275         if (!tmp)
 276                 return NULL;
 277
 278         tb->grpset = tmp;
 279
 280         if (prepend) {
 281                 DBG(TAB, ul_debugobj(tb, "   prepending free space"));
 282                 char *dest = (char *) tb->grpset;
 283
 284                 memmove(        dest + (wanted * sizeof(struct libscols_group *)),
 285                                 tb->grpset,
 286                                 tb->grpset_size * sizeof(struct libscols_group *));
 287                 first = tb->grpset;
 288         } else {
 289                 first = tb->grpset + tb->grpset_size;
 290         }
 291
 292         memset(first, 0, wanted * sizeof(struct libscols_group *));
 293         tb->grpset_size += wanted;
 294
 295         grpset_debug(tb, NULL);
 296 done:
 297         return first;
 298 }
 299
 300 static struct libscols_group **grpset_locate_group(struct libscols_table *tb, struct libscols_group *gr)
 301 {
 302         size_t i;
 303
 304         for (i = 0; i < tb->grpset_size; i++) {
 305                 if (gr == tb->grpset[i])
 306                         return &tb->grpset[i];
 307         }
 308
 309         return NULL;
 310 }
 311
 312
 313
 314 #define SCOLS_GRPSET_MINSZ      3
 315
 316 static int grpset_update(struct libscols_table *tb, struct libscols_line *ln, struct libscols_group *gr)
 317 {
 318         struct libscols_group **xx;
 319         int state;
 320
 321         DBG(LINE, ul_debugobj(ln, "   group [%p] grpset update", gr));
 322
 323         /* new state, note that gr->state still holds the original state */
 324         state = group_state_for_line(gr, ln);
 325         DBG(LINE, ul_debugobj(ln, "    state old='%s', new='%s'",
 326                         group_state_to_string(gr->state),
 327                         group_state_to_string(state)));
 328
 329         if (state == SCOLS_GSTATE_FIRST_MEMBER && gr->state != SCOLS_GSTATE_NONE) {
 330                 DBG(LINE, ul_debugobj(ln, "wrong group initialization"));
 331                 abort();
 332         }
 333         if (state != SCOLS_GSTATE_NONE && gr->state == SCOLS_GSTATE_LAST_CHILD) {
 334                 DBG(LINE, ul_debugobj(ln, "wrong group termination"));
 335                 abort();
 336         }
 337         if (gr->state == SCOLS_GSTATE_LAST_MEMBER &&
 338             !(state == SCOLS_GSTATE_LAST_CHILD ||
 339               state == SCOLS_GSTATE_CONT_CHILDREN ||
 340               state == SCOLS_GSTATE_MIDDLE_CHILD ||
 341               state == SCOLS_GSTATE_NONE)) {
 342                 DBG(LINE, ul_debugobj(ln, "wrong group member->child order"));
 343                 abort();
 344         }
 345
 346         /* should not happen; probably wrong line... */
 347         if (gr->state == SCOLS_GSTATE_NONE && state == SCOLS_GSTATE_NONE)
 348                 return 0;
 349
 350         /* locate place in grpset where we draw the group */
 351         if (!tb->grpset || gr->state == SCOLS_GSTATE_NONE)
 352                 xx = grpset_locate_freespace(tb, SCOLS_GRPSET_MINSZ, 1);
 353         else
 354                 xx = grpset_locate_group(tb, gr);
 355         if (!xx) {
 356                 DBG(LINE, ul_debugobj(ln, "failed to locate group or reallocate grpset"));
 357                 return -ENOMEM;
 358         }
 359
 360         grpset_apply_group_state(xx, state, gr);
 361         ON_DBG(LINE, grpset_debug(tb, ln));
 362         return 0;
 363 }
 364
 365 static int grpset_update_active_groups(struct libscols_table *tb, struct libscols_line *ln)
 366 {
 367         int rc = 0;
 368         size_t i;
 369         struct libscols_group *last = NULL;
 370
 371         DBG(LINE, ul_debugobj(ln, "   update for active groups"));
 372
 373         for (i = 0; i < tb->grpset_size; i++) {
 374                 struct libscols_group *gr = tb->grpset[i];
 375
 376                 if (!gr || last == gr)
 377                         continue;
 378                 last = gr;
 379                 rc = grpset_update(tb, ln, gr);
 380                 if (rc)
 381                         break;
 382         }
 383
 384         DBG(LINE, ul_debugobj(ln, "   <- active groups updated [rc=%d]", rc));
 385         return rc;
 386 }
 387
 388 int scols_groups_update_grpset(struct libscols_table *tb, struct libscols_line *ln)
 389 {
 390         int rc = 0;
 391
 392         DBG(LINE, ul_debugobj(ln, "  grpset update [line: group=%p, parent_group=%p",
 393                                 ln->group, ln->parent_group));
 394
 395         rc = grpset_update_active_groups(tb, ln);
 396         if (!rc && ln->group && ln->group->state == SCOLS_GSTATE_NONE) {
 397                 DBG(LINE, ul_debugobj(ln, " introduce a new group"));
 398                 rc = grpset_update(tb, ln, ln->group);
 399         }
 400         return rc;
 401 }
 402
 403 static int groups_calculate_grpset(struct libscols_table *tb, struct libscols_line *ln)
 404 {
 405         struct libscols_iter itr;
 406         struct libscols_line *child;
 407         int rc = 0;
 408
 409         DBG(LINE, ul_debugobj(ln, " grpset calculate"));
 410
 411         /* current line */
 412         rc = scols_groups_update_grpset(tb, ln);
 413         if (rc)
 414                 goto done;
 415
 416         /* line's children */
 417         if (has_children(ln)) {
 418                 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
 419                 while (scols_line_next_child(ln, &itr, &child) == 0) {
 420                         rc = groups_calculate_grpset(tb, child);
 421                         if (rc)
 422                                 goto done;
 423                 }
 424         }
 425
 426         /* group's children */
 427         if (is_last_group_member(ln) && has_group_children(ln)) {
 428                 scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
 429                 while (scols_line_next_group_child(ln, &itr, &child) == 0) {
 430                         rc = groups_calculate_grpset(tb, child);
 431                         if (rc)
 432                                 goto done;
 433                 }
 434         }
 435 done:
 436         return rc;
 437 }
 438
 439
 440 int scols_groups_calculate_grpset(struct libscols_table *tb)
 441 {
 442         struct libscols_iter itr;
 443         struct libscols_line *ln;
 444         int rc = 0;
 445
 446         DBG(TAB, ul_debugobj(tb, "grpset calculate [top-level]"));
 447
 448         scols_groups_reset_state(tb);
 449
 450         scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
 451         while (scols_table_next_line(tb, &itr, &ln) == 0) {
 452                 if (ln->parent || ln->parent_group)
 453                         continue;
 454                 rc = groups_calculate_grpset(tb, ln);
 455                 if (rc)
 456                         break;
 457         }
 458
 459         scols_groups_reset_state(tb);
 460         return rc;
 461 }
 462
 463 void scols_groups_reset_state(struct libscols_table *tb)
 464 {
 465         struct libscols_iter itr;
 466         struct libscols_group *gr;
 467
 468         DBG(TAB, ul_debugobj(tb, "reset groups states"));
 469
 470         scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
 471         while (scols_table_next_group(tb, &itr, &gr) == 0)
 472                 gr->state = SCOLS_GSTATE_NONE;
 473
 474         if (tb->grpset)
 475                 memset(tb->grpset, 0, tb->grpset_size);
 476 }
 477
 478 static void add_member(struct libscols_group *gr, struct libscols_line *ln)
 479 {
 480         DBG(GROUP, ul_debugobj(gr, "add member"));
 481
 482         ln->group = gr;
 483         gr->nmembers++;
 484         scols_ref_group(gr);
 485
 486         INIT_LIST_HEAD(&ln->ln_groups);
 487         list_add_tail(&ln->ln_groups, &gr->gr_members);
 488         scols_ref_line(ln);
 489 }
 490
 491 /**
 492  * scols_table_group_lines:
 493  * @tb: a pointer to a struct libscols_table instance
 494  * @ln: new group member
 495  * @member: group member
 496  * @id: group identifier (unused, not implemented yet), use zero.
 497  *
 498  * This function add line @ln to group of lines represented by @member.  If the
 499  * group is not yet defined (@member is not member of any group) than a new one
 500  * is allocated.
 501  *
 502  * The @ln maybe a NULL -- in this case only a new group is allocated if not
 503  * defined yet.
 504  *
 505  * Note that the same line cannot be member of more groups (not implemented
 506  * yet). The child of any group can be member of another group.
 507  *
 508  * The @id is not used for now, use 0. The plan is to use it to support
 509  * multi-group membership in future.
 510  *
 511  * Returns: 0, a negative value in case of an error.
 512  *
 513  * Since: 2.34
 514  */
 515 int scols_table_group_lines(    struct libscols_table *tb,
 516                                 struct libscols_line *ln,
 517                                 struct libscols_line *member,
 518                                 __attribute__((__unused__)) int id)
 519 {
 520         struct libscols_group *gr = NULL;
 521
 522         if (!tb || (!ln && !member))
 523                 return -EINVAL;
 524         if (ln && member)  {
 525                 if (ln->group && !member->group)
 526                         return -EINVAL;
 527                 if (ln->group && member->group && ln->group != member->group)
 528                         return -EINVAL;
 529         }
 530
 531         gr = member->group;
 532
 533         /* create a new group */
 534         if (!gr) {
 535                 gr = calloc(1, sizeof(*gr));
 536                 if (!gr)
 537                         return -ENOMEM;
 538                 DBG(GROUP, ul_debugobj(gr, "alloc"));
 539                 gr->refcount = 1;
 540                 INIT_LIST_HEAD(&gr->gr_members);
 541                 INIT_LIST_HEAD(&gr->gr_children);
 542                 INIT_LIST_HEAD(&gr->gr_groups);
 543
 544                 /* add group to the table */
 545                 list_add_tail(&gr->gr_groups, &tb->tb_groups);
 546
 547                 /* add the first member */
 548                 add_member(gr, member);
 549         }
 550
 551         /* add to group */
 552         if (ln && !ln->group)
 553                 add_member(gr, ln);
 554
 555         return 0;
 556 }
 557
 558 /**
 559  * scols_line_link_groups:
 560  * @ln: line instance
 561  * @member: group member
 562  * @id: group identifier (unused, not implemented yet))
 563  *
 564  * Define @ln as child of group represented by group @member. The line @ln
 565  * cannot be child of any other line. It's possible to create group->child or
 566  * parent->child relationship, but no both for the same line (child).
 567  *
 568  * The @id is not used for now, use 0. The plan is to use it to support
 569  * multi-group membership in future.
 570  *
 571  * Returns: 0, a negative value in case of an error.
 572  *
 573  * Since: 2.34
 574  */
 575 int scols_line_link_group(struct libscols_line *ln, struct libscols_line *member,
 576                  __attribute__((__unused__)) int id)
 577 {
 578         if (!ln || !member || !member->group || ln->parent)
 579                 return -EINVAL;
 580
 581         if (!list_empty(&ln->ln_children))
 582                 return -EINVAL;
 583
 584         DBG(GROUP, ul_debugobj(member->group, "add child"));
 585
 586         list_add_tail(&ln->ln_children, &member->group->gr_children);
 587         scols_ref_line(ln);
 588
 589         ln->parent_group = member->group;
 590         scols_ref_group(member->group);
 591
 592         return 0;
 593 }