text: // Copyright (c) 2019-2020, The KomputerKult Project
  //
  // All rights reserved.
  //
  // Redistribution and use in source and binary forms, with or without modification, are
  // permitted provided that the following conditions are met:
  //
  // 1. Redistributions of source code must retain the above copyright notice, this list of
  //    conditions and the following disclaimer.
  //
  // 2. Redistributions in binary form must reproduce the above copyright notice, this list
  //    of conditions and the following disclaimer in the documentation and/or other
  //    materials provided with the distribution.
  //
  // 3. Neither the name of the copyright holder nor the names of its contributors may be
  //    used to endorse or promote products derived from this software without specific
  //    prior written permission.
  //
  // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
  // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  // MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
  // THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  // STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
  // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  
  #include "dandelionpp.h"
  
  #include <boost/container/small_vector.hpp>
  #include <boost/uuid/nil_generator.hpp>
  #include <chrono>
  
  #include "common/expect.h"
  #include "cryptonote_config.h"
  #include "crypto/crypto.h"
  
  namespace net
  {
  namespace dandelionpp
  {
      namespace
      {
          constexpr const std::size_t expected_max_channels = CRYPTONOTE_NOISE_CHANNELS;
  
          // could be in util somewhere
          struct key_less
          {
              template<typename K, typename V>
              bool operator()(const std::pair<K, V>& left, const K& right) const
              {
                  return left.first < right;
              }
  
              template<typename K, typename V>
              bool operator()(const K& left, const std::pair<K, V>& right) const
              {
                  return left < right.first;
              }
          };
  
          std::size_t select_stem(epee::span<const std::size_t> usage, epee::span<const boost::uuids::uuid> out_map)
          {
              assert(usage.size() < std::numeric_limits<std::size_t>::max()); // prevented in constructor
              if (usage.size() < out_map.size())
                  return std::numeric_limits<std::size_t>::max();
  
              // small_vector uses stack space if `expected_max_channels < capacity()`
              std::size_t lowest = std::numeric_limits<std::size_t>::max();
              boost::container::small_vector<std::size_t, expected_max_channels> choices;
              static_assert(sizeof(choices) < 256, "choices is too large based on current configuration");
  
              for (const boost::uuids::uuid& out : out_map)
              {
                  if (!out.is_nil())
                  {
                      const std::size_t location = std::addressof(out) - out_map.begin();
                      if (usage[location] < lowest)
                      {
                          lowest = usage[location];
                          choices = {location};
                      }
                      else if (usage[location] == lowest)
                          choices.push_back(location);
                  }
              }
  
              switch (choices.size())
              {
              case 0:
                  return std::numeric_limits<std::size_t>::max();
              case 1:
                  return choices[0];
              default:
                  break;
              }
  
              return choices[crypto::rand_idx(choices.size())];
          }
      } // anonymous
  
      connection_map::connection_map(std::vector<boost::uuids::uuid> out_connections, const std::size_t stems)
        : out_mapping_(std::move(out_connections)),
          in_mapping_(),
          usage_count_()
      {
          // max value is used by `select_stem` as error case
          if (stems == std::numeric_limits<std::size_t>::max())
              MONERO_THROW(common_error::kInvalidArgument, "stems value cannot be max size_t");
  
          usage_count_.resize(stems);
          if (stems < out_mapping_.size())
          {
              for (unsigned i = 0; i < stems; ++i)
                  std::swap(out_mapping_[i], out_mapping_.at(i + crypto::rand_idx(out_mapping_.size() - i)));
  
              out_mapping_.resize(stems);
          }
          else
          {
              std::shuffle(out_mapping_.begin(), out_mapping_.end(), crypto::random_device{});
          }
      }
  
      connection_map::~connection_map() noexcept
      {}
  
      connection_map connection_map::clone() const
      {
          return {*this};
      }
  
      bool connection_map::update(std::vector<boost::uuids::uuid> current)
      {
          std::sort(current.begin(), current.end());
  
          bool replace = false;
          for (auto& existing_out : out_mapping_)
          {
              const auto elem = std::lower_bound(current.begin(), current.end(), existing_out);
              if (elem == current.end() || *elem != existing_out)
              {
                  existing_out = boost::uuids::nil_uuid();
                  replace = true;
              }
              else // already using connection, remove it from candidate list
                  current.erase(elem);
          }
  
          if (!replace && out_mapping_.size() == usage_count_.size())
              return false;
  
          const std::size_t existing_outs = out_mapping_.size();
          for (std::size_t i = 0; i < usage_count_.size() && !current.empty(); ++i)
          {
              const bool increase_stems = out_mapping_.size() <= i;
              if (increase_stems || out_mapping_[i].is_nil())
              {
                  std::swap(current.back(), current.at(crypto::rand_idx(current.size())));
                  if (increase_stems)
                      out_mapping_.push_back(current.back());
                  else
                      out_mapping_[i] = current.back();
                  current.pop_back();
              }
          }
  
          return replace || existing_outs < out_mapping_.size();
      }
  
      std::size_t connection_map::size() const noexcept
      {
          std::size_t count = 0;
          for (const boost::uuids::uuid& connection : out_mapping_)
          {
              if (!connection.is_nil())
                  ++count;
          }
          return count;
      }
  
      boost::uuids::uuid connection_map::get_stem(const boost::uuids::uuid& source)
      {
          auto elem = std::lower_bound(in_mapping_.begin(), in_mapping_.end(), source, key_less{});
          if (elem == in_mapping_.end() || elem->first != source)
          {
              const std::size_t index = select_stem(epee::to_span(usage_count_), epee::to_span(out_mapping_));
              if (out_mapping_.size() < index)
                  return boost::uuids::nil_uuid();
  
              elem = in_mapping_.emplace(elem, source, index);
              usage_count_[index]++;
          }
          else if (out_mapping_.at(elem->second).is_nil()) // stem connection disconnected after mapping
          {
              usage_count_.at(elem->second)--;
              const std::size_t index = select_stem(epee::to_span(usage_count_), epee::to_span(out_mapping_));
              if (out_mapping_.size() < index)
              {
                  in_mapping_.erase(elem);
                  return boost::uuids::nil_uuid();
              }
  
              elem->second = index;
              usage_count_[index]++;
          }
  
          return out_mapping_[elem->second];
      }
  } // dandelionpp
  } // net
  