summaryrefslogtreecommitdiffstats
path: root/libsmartcols/src/grouping.c
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 14:30:35 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-04-07 14:30:35 +0000
commit378c18e5f024ac5a8aef4cb40d7c9aa9633d144c (patch)
tree44dfb6ca500d32cabd450649b322a42e70a30683 /libsmartcols/src/grouping.c
parentInitial commit. (diff)
downloadutil-linux-378c18e5f024ac5a8aef4cb40d7c9aa9633d144c.tar.xz
util-linux-378c18e5f024ac5a8aef4cb40d7c9aa9633d144c.zip
Adding upstream version 2.38.1.upstream/2.38.1upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'libsmartcols/src/grouping.c')
-rw-r--r--libsmartcols/src/grouping.c575
1 files changed, 575 insertions, 0 deletions
diff --git a/libsmartcols/src/grouping.c b/libsmartcols/src/grouping.c
new file mode 100644
index 0000000..0b27cb2
--- /dev/null
+++ b/libsmartcols/src/grouping.c
@@ -0,0 +1,575 @@
+/*
+ * Copyright (C) 2018 Karel Zak <kzak@redhat.com>
+ */
+#include "smartcolsP.h"
+
+/**
+ * SECTION: grouping
+ * @title: Grouping
+ * @short_description: lines grouing
+ *
+ * Lines groups manipulation API. The grouping API can be used to create M:N
+ * relations between lines and on tree-like output it prints extra chart to
+ * visualize these relations. The group has unlimited number of members and
+ * group childs. See libsmartcols/sample/grouping* for more details.
+ */
+
+/* Private API */
+void scols_ref_group(struct libscols_group *gr)
+{
+ if (gr)
+ gr->refcount++;
+}
+
+void scols_group_remove_children(struct libscols_group *gr)
+{
+ if (!gr)
+ return;
+
+ while (!list_empty(&gr->gr_children)) {
+ struct libscols_line *ln = list_entry(gr->gr_children.next,
+ struct libscols_line, ln_children);
+
+ DBG(GROUP, ul_debugobj(gr, "remove child"));
+ list_del_init(&ln->ln_children);
+ scols_ref_group(ln->parent_group);
+ ln->parent_group = NULL;
+ scols_unref_line(ln);
+ }
+}
+
+void scols_group_remove_members(struct libscols_group *gr)
+{
+ if (!gr)
+ return;
+
+ while (!list_empty(&gr->gr_members)) {
+ struct libscols_line *ln = list_entry(gr->gr_members.next,
+ struct libscols_line, ln_groups);
+
+ DBG(GROUP, ul_debugobj(gr, "remove member [%p]", ln));
+ list_del_init(&ln->ln_groups);
+
+ scols_unref_group(ln->group);
+ ln->group->nmembers++;
+ ln->group = NULL;
+
+ scols_unref_line(ln);
+ }
+}
+
+/* note group has to be already without members to deallocate */
+void scols_unref_group(struct libscols_group *gr)
+{
+ if (gr && --gr->refcount <= 0) {
+ DBG(GROUP, ul_debugobj(gr, "dealloc"));
+ scols_group_remove_children(gr);
+ list_del(&gr->gr_groups);
+ free(gr);
+ return;
+ }
+}
+
+
+static void groups_fix_members_order(struct libscols_line *ln)
+{
+ struct libscols_iter itr;
+ struct libscols_line *child;
+
+ if (ln->group) {
+ INIT_LIST_HEAD(&ln->ln_groups);
+ list_add_tail(&ln->ln_groups, &ln->group->gr_members);
+ DBG(GROUP, ul_debugobj(ln->group, "fixing member line=%p [%zu/%zu]",
+ ln, ln->group->nmembers,
+ list_count_entries(&ln->group->gr_members)));
+ }
+
+ scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+ while (scols_line_next_child(ln, &itr, &child) == 0)
+ groups_fix_members_order(child);
+
+ /*
+ * We modify gr_members list, so is_last_group_member() does not have
+ * to provide reliable answer, we need to verify by list_count_entries().
+ */
+ if (ln->group
+ && is_last_group_member(ln)
+ && ln->group->nmembers == list_count_entries(&ln->group->gr_members)) {
+
+ DBG(GROUP, ul_debugobj(ln->group, "fixing childs"));
+ scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+ while (scols_line_next_group_child(ln, &itr, &child) == 0)
+ groups_fix_members_order(child);
+ }
+}
+
+void scols_groups_fix_members_order(struct libscols_table *tb)
+{
+ struct libscols_iter itr;
+ struct libscols_line *ln;
+ struct libscols_group *gr;
+
+ /* remove all from groups lists */
+ scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+ while (scols_table_next_group(tb, &itr, &gr) == 0) {
+ while (!list_empty(&gr->gr_members)) {
+ struct libscols_line *line = list_entry(gr->gr_members.next,
+ struct libscols_line, ln_groups);
+ list_del_init(&line->ln_groups);
+ }
+ }
+
+ /* add again to the groups list in order we walk in tree */
+ scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+ while (scols_table_next_line(tb, &itr, &ln) == 0) {
+ if (ln->parent || ln->parent_group)
+ continue;
+ groups_fix_members_order(ln);
+ }
+
+ /* If group child is member of another group *
+ scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+ while (scols_table_next_group(tb, &itr, &gr) == 0) {
+ struct libscols_iter xitr;
+ struct libscols_line *child;
+
+ scols_reset_iter(&xitr, SCOLS_ITER_FORWARD);
+ while (scols_line_next_group_child(ln, &xitr, &child) == 0)
+ groups_fix_members_order(child);
+ }
+ */
+}
+
+static inline const char *group_state_to_string(int state)
+{
+ static const char *grpstates[] = {
+ [SCOLS_GSTATE_NONE] = "none",
+ [SCOLS_GSTATE_FIRST_MEMBER] = "1st-member",
+ [SCOLS_GSTATE_MIDDLE_MEMBER] = "middle-member",
+ [SCOLS_GSTATE_LAST_MEMBER] = "last-member",
+ [SCOLS_GSTATE_MIDDLE_CHILD] = "middle-child",
+ [SCOLS_GSTATE_LAST_CHILD] = "last-child",
+ [SCOLS_GSTATE_CONT_MEMBERS] = "continue-members",
+ [SCOLS_GSTATE_CONT_CHILDREN] = "continue-children"
+ };
+
+ assert(state >= 0);
+ assert((size_t) state < ARRAY_SIZE(grpstates));
+
+ return grpstates[state];
+}
+/*
+static void grpset_debug(struct libscols_table *tb, struct libscols_line *ln)
+{
+ size_t i;
+
+ for (i = 0; i < tb->grpset_size; i++) {
+ if (tb->grpset[i]) {
+ struct libscols_group *gr = tb->grpset[i];
+
+ if (ln)
+ DBG(LINE, ul_debugobj(ln, "grpset[%zu]: %p %s", i,
+ gr, group_state_to_string(gr->state)));
+ else
+ DBG(LINE, ul_debug("grpset[%zu]: %p %s", i,
+ gr, group_state_to_string(gr->state)));
+ } else if (ln) {
+ DBG(LINE, ul_debugobj(ln, "grpset[%zu]: free", i));
+ } else
+ DBG(LINE, ul_debug("grpset[%zu]: free", i));
+ }
+}
+*/
+static int group_state_for_line(struct libscols_group *gr, struct libscols_line *ln)
+{
+ if (gr->state == SCOLS_GSTATE_NONE &&
+ (ln->group != gr || !is_first_group_member(ln)))
+ /*
+ * NONE is possible to translate to FIRST_MEMBER only, and only if
+ * line group matches with the current group.
+ */
+ return SCOLS_GSTATE_NONE;
+
+ if (ln->group != gr && ln->parent_group != gr) {
+ /* Not our line, continue */
+ if (gr->state == SCOLS_GSTATE_FIRST_MEMBER ||
+ gr->state == SCOLS_GSTATE_MIDDLE_MEMBER ||
+ gr->state == SCOLS_GSTATE_CONT_MEMBERS)
+ return SCOLS_GSTATE_CONT_MEMBERS;
+
+ if (gr->state == SCOLS_GSTATE_LAST_MEMBER ||
+ gr->state == SCOLS_GSTATE_MIDDLE_CHILD ||
+ gr->state == SCOLS_GSTATE_CONT_CHILDREN)
+ return SCOLS_GSTATE_CONT_CHILDREN;
+
+ } else if (ln->group == gr && is_first_group_member(ln)) {
+ return SCOLS_GSTATE_FIRST_MEMBER;
+
+ } else if (ln->group == gr && is_last_group_member(ln)) {
+ return SCOLS_GSTATE_LAST_MEMBER;
+
+ } else if (ln->group == gr && is_group_member(ln)) {
+ return SCOLS_GSTATE_MIDDLE_MEMBER;
+
+ } else if (ln->parent_group == gr && is_last_group_child(ln)) {
+ return SCOLS_GSTATE_LAST_CHILD;
+
+ } else if (ln->parent_group == gr && is_group_child(ln)) {
+ return SCOLS_GSTATE_MIDDLE_CHILD;
+ }
+
+ return SCOLS_GSTATE_NONE;
+}
+
+/*
+ * apply new @state to the chunk (addressed by @xx) of grpset used for the group (@gr)
+ */
+static void grpset_apply_group_state(struct libscols_group **xx, int state, struct libscols_group *gr)
+{
+ size_t i;
+
+ DBG(GROUP, ul_debugobj(gr, " applying state to grpset"));
+
+ /* gr->state holds the old state, @state is the new state
+ */
+ for (i = 0; i < SCOLS_GRPSET_CHUNKSIZ; i++)
+ xx[i] = state == SCOLS_GSTATE_NONE ? NULL : gr;
+
+ gr->state = state;
+}
+
+static struct libscols_group **grpset_locate_freespace(struct libscols_table *tb, int chunks, int prepend)
+{
+ size_t i, avail = 0;
+ struct libscols_group **tmp, **first = NULL;
+ const size_t wanted = chunks * SCOLS_GRPSET_CHUNKSIZ;
+
+ if (!tb->grpset_size)
+ prepend = 0;
+ /*
+ DBG(TAB, ul_debugobj(tb, "orig grpset:"));
+ grpset_debug(tb, NULL);
+ */
+ if (prepend) {
+ for (i = tb->grpset_size - 1; ; i--) {
+ if (tb->grpset[i] == NULL) {
+ first = &tb->grpset[i];
+ avail++;
+ } else
+ avail = 0;
+ if (avail == wanted)
+ goto done;
+ if (i == 0)
+ break;
+ }
+ } else {
+ for (i = 0; i < tb->grpset_size; i++) {
+ if (tb->grpset[i] == NULL) {
+ if (avail == 0)
+ first = &tb->grpset[i];
+ avail++;
+ } else
+ avail = 0;
+ if (avail == wanted)
+ goto done;
+ }
+ }
+
+ DBG(TAB, ul_debugobj(tb, " realocate grpset [sz: old=%zu, new=%zu, new_chunks=%d]",
+ tb->grpset_size, tb->grpset_size + wanted, chunks));
+
+ tmp = realloc(tb->grpset, (tb->grpset_size + wanted) * sizeof(struct libscols_group *));
+ if (!tmp)
+ return NULL;
+
+ tb->grpset = tmp;
+
+ if (prepend) {
+ DBG(TAB, ul_debugobj(tb, " prepending free space"));
+ char *dest = (char *) tb->grpset;
+
+ memmove( dest + (wanted * sizeof(struct libscols_group *)),
+ tb->grpset,
+ tb->grpset_size * sizeof(struct libscols_group *));
+ first = tb->grpset;
+ } else {
+ first = tb->grpset + tb->grpset_size;
+ }
+
+ memset(first, 0, wanted * sizeof(struct libscols_group *));
+ tb->grpset_size += wanted;
+
+done:
+ /*
+ DBG(TAB, ul_debugobj(tb, "new grpset:"));
+ grpset_debug(tb, NULL);
+ */
+ return first;
+}
+
+static struct libscols_group **grpset_locate_group(struct libscols_table *tb, struct libscols_group *gr)
+{
+ size_t i;
+
+ for (i = 0; i < tb->grpset_size; i++) {
+ if (gr == tb->grpset[i])
+ return &tb->grpset[i];
+ }
+
+ return NULL;
+}
+
+
+static int grpset_update(struct libscols_table *tb, struct libscols_line *ln, struct libscols_group *gr)
+{
+ struct libscols_group **xx;
+ int state;
+
+ DBG(LINE, ul_debugobj(ln, " group [%p] grpset update [grpset size=%zu]", gr, tb->grpset_size));
+
+ /* new state, note that gr->state still holds the original state */
+ state = group_state_for_line(gr, ln);
+ DBG(LINE, ul_debugobj(ln, " state %s --> %s",
+ group_state_to_string(gr->state),
+ group_state_to_string(state)));
+
+ if (state == SCOLS_GSTATE_FIRST_MEMBER && gr->state != SCOLS_GSTATE_NONE) {
+ DBG(LINE, ul_debugobj(ln, "wrong group initialization (%s)", group_state_to_string(gr->state)));
+ abort();
+ }
+ if (state != SCOLS_GSTATE_NONE && gr->state == SCOLS_GSTATE_LAST_CHILD) {
+ DBG(LINE, ul_debugobj(ln, "wrong group termination (%s)", group_state_to_string(gr->state)));
+ abort();
+ }
+ if (gr->state == SCOLS_GSTATE_LAST_MEMBER &&
+ !(state == SCOLS_GSTATE_LAST_CHILD ||
+ state == SCOLS_GSTATE_CONT_CHILDREN ||
+ state == SCOLS_GSTATE_MIDDLE_CHILD ||
+ state == SCOLS_GSTATE_NONE)) {
+ DBG(LINE, ul_debugobj(ln, "wrong group member->child order"));
+ abort();
+ }
+
+ /* should not happen; probably wrong line... */
+ if (gr->state == SCOLS_GSTATE_NONE && state == SCOLS_GSTATE_NONE)
+ return 0;
+
+ /* locate place in grpset where we draw the group */
+ if (!tb->grpset || gr->state == SCOLS_GSTATE_NONE)
+ xx = grpset_locate_freespace(tb, 1, 1);
+ else
+ xx = grpset_locate_group(tb, gr);
+ if (!xx) {
+ DBG(LINE, ul_debugobj(ln, "failed to locate group or reallocate grpset"));
+ return -ENOMEM;
+ }
+
+ grpset_apply_group_state(xx, state, gr);
+ /*ON_DBG(LINE, grpset_debug(tb, ln));*/
+ return 0;
+}
+
+static int grpset_update_active_groups(struct libscols_table *tb, struct libscols_line *ln)
+{
+ int rc = 0;
+ size_t i;
+ struct libscols_group *last = NULL;
+
+ DBG(LINE, ul_debugobj(ln, " update for active groups"));
+
+ for (i = 0; i < tb->grpset_size; i++) {
+ struct libscols_group *gr = tb->grpset[i];
+
+ if (!gr || last == gr)
+ continue;
+ last = gr;
+ rc = grpset_update(tb, ln, gr);
+ if (rc)
+ break;
+ }
+
+ DBG(LINE, ul_debugobj(ln, " <- active groups updated [rc=%d]", rc));
+ return rc;
+}
+
+int scols_groups_update_grpset(struct libscols_table *tb, struct libscols_line *ln)
+{
+ int rc = 0;
+
+ DBG(LINE, ul_debugobj(ln, " grpset update [line: group=%p, parent_group=%p",
+ ln->group, ln->parent_group));
+
+ rc = grpset_update_active_groups(tb, ln);
+ if (!rc && ln->group && ln->group->state == SCOLS_GSTATE_NONE) {
+ DBG(LINE, ul_debugobj(ln, " introduce a new group"));
+ rc = grpset_update(tb, ln, ln->group);
+ }
+ return rc;
+}
+
+void scols_groups_reset_state(struct libscols_table *tb)
+{
+ struct libscols_iter itr;
+ struct libscols_group *gr;
+
+ DBG(TAB, ul_debugobj(tb, "reset groups states"));
+
+ scols_reset_iter(&itr, SCOLS_ITER_FORWARD);
+ while (scols_table_next_group(tb, &itr, &gr) == 0) {
+ DBG(GROUP, ul_debugobj(gr, " reset to NONE"));
+ gr->state = SCOLS_GSTATE_NONE;
+ }
+
+ if (tb->grpset) {
+ DBG(TAB, ul_debugobj(tb, " zeroize grpset"));
+ memset(tb->grpset, 0, tb->grpset_size * sizeof(struct libscols_group *));
+ }
+ tb->ngrpchlds_pending = 0;
+}
+
+static void add_member(struct libscols_group *gr, struct libscols_line *ln)
+{
+ DBG(GROUP, ul_debugobj(gr, "add member %p", ln));
+
+ ln->group = gr;
+ gr->nmembers++;
+ scols_ref_group(gr);
+
+ INIT_LIST_HEAD(&ln->ln_groups);
+ list_add_tail(&ln->ln_groups, &gr->gr_members);
+ scols_ref_line(ln);
+}
+
+/*
+ * Returns first group which is ready to print group children.
+ *
+ * This function scans grpset[] in backward order and returns first group
+ * with SCOLS_GSTATE_CONT_CHILDREN or SCOLS_GSTATE_LAST_MEMBER state.
+ */
+struct libscols_group *scols_grpset_get_printable_children(struct libscols_table *tb)
+{
+ size_t i;
+
+ for (i = tb->grpset_size; i > 0; i -= SCOLS_GRPSET_CHUNKSIZ) {
+ struct libscols_group *gr = tb->grpset[i-1];
+
+ if (gr == NULL)
+ continue;
+ if (gr->state == SCOLS_GSTATE_CONT_CHILDREN ||
+ gr->state == SCOLS_GSTATE_LAST_MEMBER)
+ return gr;
+ }
+
+ return NULL;
+}
+
+
+/**
+ * scols_table_group_lines:
+ * @tb: a pointer to a struct libscols_table instance
+ * @ln: new group member
+ * @member: group member
+ * @id: group identifier (unused, not implemented yet), use zero.
+ *
+ * This function add line @ln to group of lines represented by @member. If the
+ * group is not yet defined (@member is not member of any group) than a new one
+ * is allocated.
+ *
+ * The @ln maybe a NULL -- in this case only a new group is allocated if not
+ * defined yet.
+ *
+ * Note that the same line cannot be member of more groups (not implemented
+ * yet). The child of any group can be member of another group.
+ *
+ * The @id is not used for now, use 0. The plan is to use it to support
+ * multi-group membership in future.
+ *
+ * Returns: 0, a negative value in case of an error.
+ *
+ * Since: 2.34
+ */
+int scols_table_group_lines( struct libscols_table *tb,
+ struct libscols_line *ln,
+ struct libscols_line *member,
+ __attribute__((__unused__)) int id)
+{
+ struct libscols_group *gr = NULL;
+
+ if (!tb || !member) {
+ DBG(GROUP, ul_debugobj(gr, "failed group lines (no table or member)"));
+ return -EINVAL;
+ }
+ if (ln) {
+ if (ln->group && !member->group) {
+ DBG(GROUP, ul_debugobj(gr, "failed group lines (new group, line member of another)"));
+ return -EINVAL;
+ }
+ if (ln->group && member->group && ln->group != member->group) {
+ DBG(GROUP, ul_debugobj(gr, "failed group lines (groups mismatch bwteen member and line"));
+ return -EINVAL;
+ }
+ }
+
+ gr = member->group;
+
+ /* create a new group */
+ if (!gr) {
+ gr = calloc(1, sizeof(*gr));
+ if (!gr)
+ return -ENOMEM;
+ DBG(GROUP, ul_debugobj(gr, "alloc"));
+ gr->refcount = 1;
+ INIT_LIST_HEAD(&gr->gr_members);
+ INIT_LIST_HEAD(&gr->gr_children);
+ INIT_LIST_HEAD(&gr->gr_groups);
+
+ /* add group to the table */
+ list_add_tail(&gr->gr_groups, &tb->tb_groups);
+
+ /* add the first member */
+ add_member(gr, member);
+ }
+
+ /* add to group */
+ if (ln && !ln->group)
+ add_member(gr, ln);
+
+ return 0;
+}
+
+/**
+ * scols_line_link_group:
+ * @ln: line instance
+ * @member: group member
+ * @id: group identifier (unused, not implemented yet))
+ *
+ * Define @ln as child of group represented by group @member. The line @ln
+ * cannot be child of any other line. It's possible to create group->child or
+ * parent->child relationship, but no both for the same line (child).
+ *
+ * The @id is not used for now, use 0. The plan is to use it to support
+ * multi-group membership in future.
+ *
+ * Returns: 0, a negative value in case of an error.
+ *
+ * Since: 2.34
+ */
+int scols_line_link_group(struct libscols_line *ln, struct libscols_line *member,
+ __attribute__((__unused__)) int id)
+{
+ if (!ln || !member || !member->group || ln->parent)
+ return -EINVAL;
+
+ if (!list_empty(&ln->ln_children))
+ return -EINVAL;
+
+ DBG(GROUP, ul_debugobj(member->group, "add child"));
+
+ list_add_tail(&ln->ln_children, &member->group->gr_children);
+ scols_ref_line(ln);
+
+ ln->parent_group = member->group;
+ scols_ref_group(member->group);
+
+ return 0;
+}