]> git.ipfire.org Git - location/libloc.git/commit
Implement search through the network tree
authorMichael Tremer <michael.tremer@ipfire.org>
Thu, 3 Oct 2019 15:13:03 +0000 (15:13 +0000)
committerMichael Tremer <michael.tremer@ipfire.org>
Thu, 3 Oct 2019 15:13:03 +0000 (15:13 +0000)
commite3f696c13851bef313183e59ef7dbc77f67359fd
treeb36e877f8f17a535f01b0ed30e3a06f5fce0ebc9
parent35bb3a32f117d43e45a13e452ab1148ca2aa023f
Implement search through the network tree

This could not be implemented as a usual DFS since we cannot simply
have a recursive solution here and need to be able to break the
search at any time.

However, it needs to be tracked where in the graph we are when we
are walking through it to extract the informaton encoded into the
edges.

This is now solved by using a stack that keeps that information
as we walk through the graph.

This solution uses O(1) in memory since the stack can not be larger
than 256 nodes (the maximum path length should be 128).

Signed-off-by: Michael Tremer <michael.tremer@ipfire.org>
src/database.c
src/libloc.sym
src/loc/database.h
src/loc/network.h
src/network.c