// SPDX-License-Identifier: GPL-2.0-or-later // SPDX-FileCopyrightText: 2007-2010 Jan Engelhardt /* * graph-lchain.c - Longest-chain tree nodes */ #include #include #include #include #include #include #include #include struct node { char *name; struct node *parent; bool mark; }; static struct HXmap *nodename_map; static inline bool lchain_contains(const struct node *start, const struct node *needle) { const struct node *w; for (w = start; w != NULL; w = w->parent) if (w == needle) return true; return false; } static void lchain_relink(struct node *source, struct node *new_parent) { unsigned int old_path_length, new_path_length; struct node *common_ancestor, *w; /* * Check whether adding to the tree would generate a * circle/loop a1-->a2-->...-->a1. If so, CONTINUE. * * This ensures the tree remains a tree. Once you have loops * the graph would quickly get cramped. */ /* Make sure it will be loop-free */ if (lchain_contains(new_parent, source)) return; /* * [ Now we know that is a potential candidate to replace * and that the tree is indeed loop-free. ] */ /* * Find longest path towards common ancestor. */ /* Walk down old path and mark */ for (w = source->parent; w != NULL; w = w->parent) { if (w->mark) { fprintf(stderr, "Impossible loop detected at %s\n", w->name); abort(); } w->mark = true; } /* Walk down new path and check for mark=1 */ new_path_length = 0; for (w = new_parent; w != NULL; w = w->parent) { ++new_path_length; if (w->mark) break; } /* * Let c be a common ancestor of an existing path, e.g. * a1-->a3-->...-->c, and the "proposed" new path * a1-->a2-->...-->c. If no such common ancestor exists, CONTINUE. */ common_ancestor = w; if (common_ancestor == NULL) { /* No common ancestor. Clear flags. Bail out. */ for (w = source->parent; w != NULL; w = w->parent) w->mark = false; return; } /* Walk down old path again and reset mark for further traversals. */ old_path_length = 0; for (w = source; w != common_ancestor; w = w->parent) { ++old_path_length; w->mark = false; } for (; w != NULL; w = w->parent) w->mark = false; /* * If the path a1-->a2-->...->c is longer (has more edges) than * a1-->a3->...-->c, delete from the tree and add * instead. * * This I call longest-chaining. * * One can see that this results in a tree with only ever one * tuple to match . * This ensures that no two edges ever overlap which "helps" * decramping the graph. */ source->parent = new_parent; } static void lchain_link(const char *source_name, const char *target_name) { struct node *source_ptr, *target_ptr; int ret; target_ptr = HXmap_get(nodename_map, target_name); if (target_ptr == NULL) { struct node local_node = {.name = HX_strdup(target_name)}; if (local_node.name == NULL) { perror("strdup"); abort(); } target_ptr = HX_memdup(&local_node, sizeof(local_node)); if (target_ptr == NULL) { perror("HX_memdup"); abort(); } ret = HXmap_add(nodename_map, local_node.name, target_ptr); if (ret <= 0) { fprintf(stderr, "HXmap_add: %s\n", strerror(-ret)); abort(); } } source_ptr = HXmap_get(nodename_map, source_name); if (source_ptr == NULL) { struct node local_node = { .name = HX_strdup(source_name), .parent = target_ptr, }; if (local_node.name == NULL) { perror("strdup"); abort(); } source_ptr = HX_memdup(&local_node, sizeof(local_node)); if (source_ptr == NULL) { perror("HX_memdup"); abort(); } ret = HXmap_add(nodename_map, local_node.name, source_ptr); if (ret <= 0) { fprintf(stderr, "HXmap_add: %s\n", strerror(-ret)); abort(); } /* New parent */ return; } /* * If there is no edge in the (directed) tree, add edge to * tree, restart loop with next tuple ("CONTINUE"/RETURN). */ if (source_ptr->parent == NULL) { if (lchain_contains(target_ptr, source_ptr)) return; /* New parent */ source_ptr->parent = target_ptr; return; } /* [ Now we know there must be a edge in the tree. ] */ /* If the edge is already in the tree, CONTINUE. */ if (strcmp(source_ptr->parent->name, target_name) == 0) /* Parent did not change */ return; /* [ Now there is in the tree, with a2 != a3 ] */ lchain_relink(source_ptr, target_ptr); } static void lchain_process(FILE *fp) { hxmc_t *source_name = NULL, *target_name = NULL; while (HX_getl(&source_name, fp) != NULL) { if (HX_getl(&target_name, fp) == NULL) break; HX_chomp(source_name); HX_chomp(target_name); lchain_link(source_name, target_name); } HXmc_free(source_name); HXmc_free(target_name); } static void lchain_dump_tree(const struct HXmap *tree) { const struct HXmap_node *tree_node; const struct node *source; struct HXmap_trav *trav; trav = HXmap_travinit(tree, 0); while ((tree_node = HXmap_traverse(trav)) != NULL) { source = tree_node->data; if (source->parent != NULL) printf("%s\n%s\n", source->name, source->parent->name); } HXmap_travfree(trav); } static void lchain_free_tree(struct HXmap *tree) { const struct HXmap_node *tree_node; struct node *source; struct HXmap_trav *trav; trav = HXmap_travinit(tree, 0); while ((tree_node = HXmap_traverse(trav)) != NULL) { source = tree_node->data; free(source->name); free(source); } HXmap_travfree(trav); HXmap_free(tree); } static int main2(int argc, const char **argv) { const char **file; FILE *fp; setvbuf(stdout, NULL, _IOLBF, 0); nodename_map = HXmap_init(HXMAPT_DEFAULT, HXMAP_SKEY); if (nodename_map == NULL) { perror("HXmap_init"); abort(); } if (argc == 1) { lchain_process(stdin); } else { for (file = &argv[1]; *file != NULL; ++file) { fp = fopen(*file, "r"); if (fp == NULL) { fprintf(stderr, "%s: Could not open %s: %s\n", *argv, *file, strerror(errno)); continue; } lchain_process(fp); fclose(fp); } } lchain_dump_tree(nodename_map); lchain_free_tree(nodename_map); return EXIT_SUCCESS; } int main(int argc, const char **argv) { int ret; if ((ret = HX_init()) <= 0) { fprintf(stderr, "HX_init: %s\n", strerror(-ret)); abort(); } ret = main2(argc, argv); HX_exit(); return ret; } #if 0 static void lchain_loopcheck(const struct HXmap *tree) { const struct HXmap_node *tree_node; const struct node *source; struct node *w; struct HXmap_trav *trav; trav = HXmap_travinit(tree, 0); while ((tree_node = HXmap_traverse(trav)) != NULL) { source = tree_node->data; for (w = source->parent; w != NULL; w = w->parent) { if (w->mark) fprintf(stderr, "Loop detected at %s\n", w->name); w->mark = true; } for (w = source->parent; w != NULL; w = w->parent) w->mark = false; } HXmap_travfree(trav); } #endif