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;
+}