/*
* 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 allows 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 (addresesd 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 || (!ln && !member)) {
DBG(GROUP, ul_debugobj(gr, "failed group lines (no table, line or member)"));
return -EINVAL;
}
if (ln && member) {
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_groups:
* @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;
}