From 378c18e5f024ac5a8aef4cb40d7c9aa9633d144c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 16:30:35 +0200 Subject: Adding upstream version 2.38.1. Signed-off-by: Daniel Baumann --- libsmartcols/src/grouping.c | 575 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 575 insertions(+) create mode 100644 libsmartcols/src/grouping.c (limited to 'libsmartcols/src/grouping.c') 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 + */ +#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; +} -- cgit v1.2.3