summaryrefslogtreecommitdiffstats
path: root/lib/graph.c (follow)
Commit message (Collapse)AuthorAgeFilesLines
* lib: fix spelling nits in more lib filesewlumpkin2021-10-051-1/+1
| | | | Signed-off-by: ewlumpkin <ewlumpkin@gmail.com>
* *: require semicolon after DEFINE_MTYPE & coDavid Lamparter2021-03-171-2/+2
| | | | | | | | | | | | | | | | | Back when I put this together in 2015, ISO C11 was still reasonably new and we couldn't require it just yet. Without ISO C11, there is no "good" way (only bad hacks) to require a semicolon after a macro that ends with a function definition. And if you added one anyway, you'd get "spurious semicolon" warnings on some compilers... With C11, `_Static_assert()` at the end of a macro will make it so that the semicolon is properly required, consumed, and not warned about. Consistently requiring semicolons after "file-level" macros matches Linux kernel coding style and helps some editors against mis-syntax'ing these macros. Signed-off-by: David Lamparter <equinox@diac24.net>
* Treewide: use ANSI function definitionsRuben Kerkhof2019-01-241-1/+1
| | | | Signed-off-by: Ruben Kerkhof <ruben@rubenkerkhof.com>
* lib: add vector_remove() to vector.[ch]Quentin Young2018-06-061-4/+4
| | | | | | | | | | | An optimized version of this has already been implemented within graph.c that assumes some specialized constraints for that code. It's generally useful so this change implements a general purpose version of it. This fixes cmd_make_strvec() that was broken by some code shuffling in previous commits. Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* lib: add DFS + DOT dumping to graph datastructureQuentin Young2018-04-191-0/+71
| | | | | | | | * Add general-purpose DFS traversal code * Add ability to dump any graph to DOT language * Add tests for graph datastructure Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* lib: add graph_find_nodeQuentin Young2018-04-061-6/+27
| | | | | | Allows finding a graph node by its data pointer. Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* *: reindentreindent-master-afterwhitespace / reindent2017-07-171-95/+86
| | | | | | indent.py `git ls-files | pcregrep '\.[ch]$' | pcregrep -v '^(ldpd|babeld|nhrpd)/'` Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* *: make consistent & update GPLv2 file headersDavid Lamparter2017-05-151-4/+3
| | | | | | | | | | | The FSF's address changed, and we had a mixture of comment styles for the GPL file header. (The style with * at the beginning won out with 580 to 141 in existing files.) Note: I've intentionally left intact other "variations" of the copyright header, e.g. whether it says "Zebra", "Quagga", "FRR", or nothing. Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* lib: graph: fix vector_remove()David Lamparter2017-01-261-4/+9
| | | | | | | | | | | | | | | | | | | | | | | | vector_remove would corrupt the data in the following sequence: 1. assume vector v = [a, b], active = 2 2. vector_unset(v, 0) => v = [NULL, b], active = 2 3. vector_remove(v, 1) vector_remove calls vector_unset(v, 1), vector_unset notices index #0 is also NULL and thus sets active to 0. The equality test in vector_remove() now fails, leading it to decrement v->active *again*, leading to an underflow that will likely crash the daemon (and might even be exploitable). This call sequence does not happen in existing code since vector_unset() is not used on graph from/to lists. Nonetheless this is a buried land mine in the code at best. Rewrite the function - while we're at it, there's no reason to move the entire array around, just fill the hole with the last element. Signed-off-by: David Lamparter <equinox@opensourcerouting.org> Cc: Quentin Young <qlyoung@cumulusnetworks.com>
* lib: graph: speed up node deletionDavid Lamparter2017-01-261-12/+17
| | | | | | | | | | | | We don't need to copy the from/to arrays, we can just iterate backwards. NB: this makes graph_remove_edge delete only one edge (which is more consistent with graph_add_edge allowing parallel edges). Iterating graph->nodes backwards also makes graph_delete_graph faster since that also iterates backwards. Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
* lib: graph: fix deletionsDavid Lamparter2017-01-261-3/+3
| | | | | | | | | | | | | | Iterating over an array while deleting items needs to consider interactions between the iteration position and deletion. The previous code completely ignored that problem, leading to memleaks (graph_delete skipping half of the nodes) and dangling pointers (if parallel edges exist in graph_remove_edge). Iterating backwards is safe and reduces "move to fill hole" overhead in deletion. Signed-off-by: David Lamparter <equinox@opensourcerouting.org> Cc: Quentin Young <qlyoung@cumulusnetworks.com>
* Merge remote-tracking branch 'origin/cmaster-next' into vtysh-grammarDonald Sharp2016-09-211-0/+2
|
* lib: Add edge removal to graph data structureQuentin Young2016-09-181-15/+36
| | | | | | | Ability to remove directed edge between two nodes. Also ensures that adjacency vectors have no null entries. Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* lib: Add nullcheck before graph node deletionQuentin Young2016-09-091-0/+2
| | | | Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* lib: Remove automatic node deletionQuentin Young2016-09-081-13/+1
| | | | Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* lib: Continue matching system refactorQuentin Young2016-09-071-15/+23
| | | | | | | Most things back to working, all CLI units refactored to use improved graph implementation. Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* lib: Refactor command_parse.y for graph dsQuentin Young2016-09-021-4/+8
| | | | Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
* lib: Generalize graph to work for any data typeQuentin Young2016-09-011-0/+113
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-06 03:51:31 +0100