- Avoid going via a temporary IdealNodesList.

- Use ConstArrayRef to hide implementation.
- Store all 3 node categories in a single vector.
- Use a small_vector that can handle redundancy up to 5 without requiring extra memory allocation.
- Build a hash_map if redundancy/groups > 32 for constant lookup time.

7 files changed, 45 insertions, 231 deletions

diff --git a/vdslib/src/tests/distribution/CMakeLists.txt b/vdslib/src/tests/distribution/CMakeLists.txt
index c4ae8b0291c..3f3be1e1cad 100644
--- a/vdslib/src/tests/distribution/CMakeLists.txt
+++ b/vdslib/src/tests/distribution/CMakeLists.txt
@@ -3,7 +3,6 @@ vespa_add_library(vdslib_testdistribution
     SOURCES
     distributiontest.cpp
     grouptest.cpp
-    idealnodecalculatorimpltest.cpp
     DEPENDS
     vdslib
     GTest::GTest
diff --git a/vdslib/src/tests/distribution/distributiontest.cpp b/vdslib/src/tests/distribution/distributiontest.cpp
index ec7c05fa7a2..ce07711a069 100644
--- a/vdslib/src/tests/distribution/distributiontest.cpp
+++ b/vdslib/src/tests/distribution/distributiontest.cpp
@@ -5,7 +5,6 @@
 #include <vespa/config/subscription/configuri.h>
 #include <vespa/fastos/file.h>
 #include <vespa/vdslib/distribution/distribution.h>
-#include <vespa/vdslib/distribution/idealnodecalculator.h>
 #include <vespa/vdslib/state/clusterstate.h>
 #include <vespa/vdslib/state/random.h>
 #include <vespa/vespalib/data/slime/slime.h>
@@ -84,6 +83,51 @@ TEST(DistributionTest, test_verify_java_distributions)
 
 namespace {
 
+/**
+* A list of ideal nodes, sorted in preferred order. Wraps a vector to hide
+* unneeded details, and make it easily printable.
+*/
+class IdealNodeList : public document::Printable {
+public:
+    IdealNodeList() noexcept;
+    ~IdealNodeList();
+
+    void push_back(const Node& node) {
+        _idealNodes.push_back(node);
+    }
+
+    const Node& operator[](uint32_t i) const noexcept { return _idealNodes[i]; }
+    uint32_t size() const noexcept { return _idealNodes.size(); }
+    bool contains(const Node& n) const noexcept {
+        return indexOf(n) != 0xffff;
+    }
+    uint16_t indexOf(const Node& n) const noexcept {
+        for (uint16_t i=0; i<_idealNodes.size(); ++i) {
+            if (n == _idealNodes[i]) return i;
+        }
+        return 0xffff;
+    }
+
+    void print(std::ostream& out, bool, const std::string &) const override;
+private:
+    std::vector<Node> _idealNodes;
+};
+
+IdealNodeList::IdealNodeList() noexcept = default;
+IdealNodeList::~IdealNodeList() = default;
+
+void
+IdealNodeList::print(std::ostream& out, bool , const std::string &) const
+{
+    out << "[";
+    for (uint32_t i=0; i<_idealNodes.size(); ++i) {
+        if (i != 0) out << ", ";
+        out << _idealNodes[i];
+    }
+    out << "]";
+}
+
+
 struct ExpectedResult {
     ExpectedResult() { }
     ExpectedResult(const ExpectedResult &) = default;
diff --git a/vdslib/src/tests/distribution/idealnodecalculatorimpltest.cpp b/vdslib/src/tests/distribution/idealnodecalculatorimpltest.cpp
deleted file mode 100644
index 4159491097c..00000000000
--- a/vdslib/src/tests/distribution/idealnodecalculatorimpltest.cpp
+++ /dev/null
@@ -1,35 +0,0 @@
-// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
-
-#include <vespa/config-stor-distribution.h>
-#include <vespa/vdslib/distribution/idealnodecalculatorimpl.h>
-#include <vespa/vdslib/distribution/distribution.h>
-#include <vespa/vdslib/state/clusterstate.h>
-#include <vespa/vespalib/gtest/gtest.h>
-
-namespace storage::lib {
-
-/**
- * Class is just a wrapper for distribution, so little needs to be tested. Just
- * that:
- *
- *   - get ideal nodes calls gets propagated correctly.
- *   - Changes in distribution/cluster state is picked up.
- */
-
-TEST(IdealNodeCalculatorImplTest, test_normal_usage)
-{
-    ClusterState state("storage:10");
-    Distribution distr(Distribution::getDefaultDistributionConfig(3, 10));
-    IdealNodeCalculatorImpl impl;
-    IdealNodeCalculatorConfigurable& configurable(impl);
-    IdealNodeCalculator& calc(impl);
-    configurable.setDistribution(distr);
-    configurable.setClusterState(state);
-
-    std::string expected("[storage.8, storage.9, storage.6]");
-    EXPECT_EQ(
-            expected,
-            calc.getIdealStorageNodes(document::BucketId(16, 5)).toString());
-}
-
-}
diff --git a/vdslib/src/vespa/vdslib/distribution/CMakeLists.txt b/vdslib/src/vespa/vdslib/distribution/CMakeLists.txt
index 0d9342291e8..58ec94eec9c 100644
--- a/vdslib/src/vespa/vdslib/distribution/CMakeLists.txt
+++ b/vdslib/src/vespa/vdslib/distribution/CMakeLists.txt
@@ -4,7 +4,6 @@ vespa_add_library(vdslib_distribution OBJECT
     distribution.cpp
     distribution_config_util.cpp
     group.cpp
-    idealnodecalculatorimpl.cpp
     redundancygroupdistribution.cpp
     DEPENDS
 )
diff --git a/vdslib/src/vespa/vdslib/distribution/idealnodecalculator.h b/vdslib/src/vespa/vdslib/distribution/idealnodecalculator.h
deleted file mode 100644
index 4eb8f7e04ae..00000000000
--- a/vdslib/src/vespa/vdslib/distribution/idealnodecalculator.h
+++ /dev/null
@@ -1,89 +0,0 @@
-// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
-/**
- * An interface to implement for a calculator calcuting ideal state. It should
- * be easy to wrap this calculator in a cache. Thus options that seldom change,
- * are taken in as set parameters, such that existing cache can be invalidated.
- */
-#pragma once
-
-#include <vespa/document/bucket/bucketid.h>
-#include <vespa/document/util/printable.h>
-#include <vespa/vdslib/state/node.h>
-#include <vector>
-#include <memory>
-
-namespace storage::lib {
-
-class Distribution;
-class ClusterState;
-
-/**
- * A list of ideal nodes, sorted in preferred order. Wraps a vector to hide
- * unneeded details, and make it easily printable.
- */
-class IdealNodeList : public document::Printable {
-public:
-    IdealNodeList() noexcept;
-    ~IdealNodeList();
-
-    void push_back(const Node& node) {
-        _idealNodes.push_back(node);
-    }
-
-    const Node& operator[](uint32_t i) const noexcept { return _idealNodes[i]; }
-    uint32_t size() const noexcept { return _idealNodes.size(); }
-    bool contains(const Node& n) const noexcept {
-        return indexOf(n) != 0xffff;
-    }
-    uint16_t indexOf(const Node& n) const noexcept {
-        for (uint16_t i=0; i<_idealNodes.size(); ++i) {
-            if (n == _idealNodes[i]) return i;
-        }
-        return 0xffff;
-    }
-
-    void print(std::ostream& out, bool, const std::string &) const override;
-private:
-    std::vector<Node> _idealNodes;
-};
-
-/**
- * Simple interface to use for those who needs to calculate ideal nodes.
- */
-class IdealNodeCalculator {
-public:
-    using SP = std::shared_ptr<IdealNodeCalculator>;
-    enum UpStates {
-        UpInit,
-        UpInitMaintenance,
-        UP_STATE_COUNT
-    };
-
-    virtual ~IdealNodeCalculator() = default;
-
-    virtual IdealNodeList getIdealNodes(const NodeType&, const document::BucketId&, UpStates upStates = UpInit) const = 0;
-
-    // Wrapper functions to make prettier call if nodetype is given.
-    IdealNodeList getIdealDistributorNodes(const document::BucketId& bucket, UpStates upStates = UpInit) const {
-        return getIdealNodes(NodeType::DISTRIBUTOR, bucket, upStates);
-    }
-    IdealNodeList getIdealStorageNodes(const document::BucketId& bucket, UpStates upStates = UpInit) const {
-        return getIdealNodes(NodeType::STORAGE, bucket, upStates);
-    }
-};
-
-
-/**
- * More complex interface that provides a way to alter needed settings not
- * provided in the function call itself.
- */
-class IdealNodeCalculatorConfigurable : public IdealNodeCalculator
-{
-public:
-    using SP = std::shared_ptr<IdealNodeCalculatorConfigurable>;
-
-    virtual void setDistribution(const Distribution&) = 0;
-    virtual void setClusterState(const ClusterState&) = 0;
-};
-
-}
diff --git a/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.cpp b/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.cpp
deleted file mode 100644
index 86123f47d6f..00000000000
--- a/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.cpp
+++ /dev/null
@@ -1,73 +0,0 @@
-// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
-
-#include "idealnodecalculatorimpl.h"
-#include "distribution.h"
-#include <vespa/vespalib/util/exceptions.h>
-#include <ostream>
-#include <cassert>
-
-namespace storage::lib {
-
-IdealNodeList::IdealNodeList() noexcept = default;
-IdealNodeList::~IdealNodeList() = default;
-
-void
-IdealNodeList::print(std::ostream& out, bool , const std::string &) const
-{
-    out << "[";
-    for (uint32_t i=0; i<_idealNodes.size(); ++i) {
-        if (i != 0) out << ", ";
-        out << _idealNodes[i];
-    }
-    out << "]";
-}
-
-IdealNodeCalculatorImpl::IdealNodeCalculatorImpl()
-    : _distribution(0),
-      _clusterState(0)
-{
-    initUpStateMapping();
-}
-
-IdealNodeCalculatorImpl::~IdealNodeCalculatorImpl() = default;
-
-void
-IdealNodeCalculatorImpl::setDistribution(const Distribution& d) {
-    _distribution = &d;
-}
-void
-IdealNodeCalculatorImpl::setClusterState(const ClusterState& cs) {
-    _clusterState = &cs;
-}
-
-IdealNodeList
-IdealNodeCalculatorImpl::getIdealNodes(const NodeType& nodeType,
-                                       const document::BucketId& bucket,
-                                       UpStates upStates) const
-{
-    assert(_clusterState != 0);
-    assert(_distribution != 0);
-    std::vector<uint16_t> nodes;
-    _distribution->getIdealNodes(nodeType, *_clusterState, bucket, nodes, _upStates[upStates]);
-    IdealNodeList list;
-    for (uint32_t i=0; i<nodes.size(); ++i) {
-        list.push_back(Node(nodeType, nodes[i]));
-    }
-    return list;
-}
-
-void
-IdealNodeCalculatorImpl::initUpStateMapping() {
-    _upStates.clear();
-    _upStates.resize(UP_STATE_COUNT);
-    _upStates[UpInit] = "ui";
-    _upStates[UpInitMaintenance] = "uim";
-    for (uint32_t i=0; i<_upStates.size(); ++i) {
-        if (_upStates[i] == 0) {
-            throw vespalib::IllegalStateException("Failed to initialize up state. Code likely not updated "
-                                                  "after another upstate was added.", VESPA_STRLOC);
-        }
-    }
-}
-
-}
diff --git a/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.h b/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.h
deleted file mode 100644
index 9b36f1094fd..00000000000
--- a/vdslib/src/vespa/vdslib/distribution/idealnodecalculatorimpl.h
+++ /dev/null
@@ -1,31 +0,0 @@
-// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
-/**
- * A cache for an ideal nodes implementation. Making it cheap for localized
- * access, regardless of real implementation.
- */
-#pragma once
-
-#include "idealnodecalculator.h"
-
-namespace storage::lib {
-
-class IdealNodeCalculatorImpl : public IdealNodeCalculatorConfigurable {
-    std::vector<const char*> _upStates;
-    const Distribution* _distribution;
-    const ClusterState* _clusterState;
-
-public:
-    IdealNodeCalculatorImpl();
-    ~IdealNodeCalculatorImpl();
-
-    void setDistribution(const Distribution& d) override;
-    void setClusterState(const ClusterState& cs) override;
-
-    IdealNodeList getIdealNodes(const NodeType& nodeType,
-                                const document::BucketId& bucket,
-                                UpStates upStates) const override;
-private:
-    void initUpStateMapping();
-};
-
-}