* chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [#600]
Closes#600
The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues.
Signed-off-by: Andrii Korotkov <andrii.korotkov@verkada.com>
* improvements to graph building
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
* use old name
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
* chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [#600]
Closes#600
The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues.
Signed-off-by: Andrii Korotkov <andrii.korotkov@verkada.com>
* finish merge
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
* chore: More optimal IterateHierarchyV2 and iterateChildrenV2 [#600]
Closes#600
The existing (effectively v1) implementations are suboptimal since they don't construct a graph before the iteration. They search for children by looking at all namespace resources and checking `isParentOf`, which can give `O(tree_size * namespace_resources_count)` time complexity. The v2 algorithms construct the graph and have `O(namespace_resources_count)` time complexity. See more details in the linked issues.
Signed-off-by: Andrii Korotkov <andrii.korotkov@verkada.com>
* discard unneeded copies of child resources as we go
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
* remove unnecessary comment
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
* make childrenByUID sparse
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
* eliminate duplicate map
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
* fix comment
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
* add useful comment back
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
* use nsNodes instead of dupe map
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
* remove unused struct
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
* skip invalid APIVersion
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
---------
Signed-off-by: Andrii Korotkov <andrii.korotkov@verkada.com>
Signed-off-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
Co-authored-by: Michael Crenshaw <350466+crenshaw-dev@users.noreply.github.com>
Andrii Korotkov