| Age | Commit message (Collapse) | Author |
|---|
|
Done with a combination of regex'ing and banging my head against a wall.
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
Signed-off-by: ewlumpkin <ewlumpkin@gmail.com>
|
|
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>
|
|
Signed-off-by: Ruben Kerkhof <ruben@rubenkerkhof.com>
|
|
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>
|
|
* 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>
|
|
Allows finding a graph node by its data pointer.
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
|
|
indent.py `git ls-files | pcregrep '\.[ch]$' | pcregrep -v '^(ldpd|babeld|nhrpd)/'`
Signed-off-by: David Lamparter <equinox@opensourcerouting.org>
|
|
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>
|
|
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>
|
|
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>
|
|
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>
|
|
|
|
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>
|
|
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
|
|
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
|
|
Most things back to working, all CLI units refactored
to use improved graph implementation.
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
|
|
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
|
|
Signed-off-by: Quentin Young <qlyoung@cumulusnetworks.com>
|
