Line data    Source code

       1              : /********************************************************************************
       2              :  * Copyright (c) 2024 Accenture
       3              :  *
       4              :  * This program and the accompanying materials are made available under the
       5              :  * terms of the Apache License Version 2.0 which is available at
       6              :  * https://www.apache.org/licenses/LICENSE-2.0
       7              :  *
       8              :  * SPDX-License-Identifier: Apache-2.0
       9              :  ********************************************************************************/
      10              : 
      11              : #include "shed/multi_list.h"
      12              : 
      13              : #include <etl/alignment.h>
      14              : 
      15              : #include <cstdint>
      16              : 
      17              : namespace shed
      18              : {
      19              : namespace internal
      20              : {
      21          172 : size_t multi_list::move_node(size_t const s, size_t dst)
      22              : {
      23          349 :     while ((s < items()[dst]) && (items()[dst] < _n))
      24              :     {
      25          177 :         dst = items()[dst];
      26              :     }
      27          172 :     auto const src            = backlinks()[s];
      28          172 :     items()[src]              = items()[s];
      29          172 :     items()[s]                = items()[dst];
      30          172 :     items()[dst]              = static_cast<idx_type>(s);
      31          172 :     backlinks()[items()[src]] = src;
      32          172 :     backlinks()[items()[s]]   = static_cast<idx_type>(s);
      33          172 :     backlinks()[items()[dst]] = static_cast<idx_type>(dst);
      34          172 :     return dst;
      35              : }
      36              : 
      37           33 : multi_list* multi_list::make(size_t const n, size_t const buckets, ::etl::span<uint8_t>& mem)
      38              : {
      39           33 :     if (!is_size_valid(n, buckets))
      40              :     {
      41            0 :         return nullptr;
      42              :     }
      43           33 :     if (mem.size() < memory_for(n, buckets))
      44              :     {
      45            0 :         return nullptr;
      46              :     }
      47              :     // If the provided memory isn't aligned to the requirements of multi_list, don't continue
      48           33 :     if (!::etl::is_aligned<multi_list>(mem.data()))
      49              :     {
      50            1 :         return nullptr;
      51              :     }
      52           32 :     auto* const self = new (mem.data()) multi_list(n, buckets);
      53           32 :     mem.advance(memory_for(n, buckets));
      54           32 :     return self;
      55              : }
      56              : 
      57           32 : multi_list::multi_list(size_t const n, size_t const buckets)
      58              : {
      59           32 :     _n         = static_cast<idx_type>(n);
      60           32 :     _buckets   = static_cast<idx_type>(buckets);
      61           32 :     items()[0] = static_cast<idx_type>(n);
      62          213 :     for (size_t i = 0; i < n; ++i)
      63              :     {
      64          181 :         items()[i + 1] = static_cast<idx_type>(i);
      65              :     }
      66          152 :     for (size_t i = n + 1; i < n + buckets; ++i)
      67              :     {
      68          120 :         items()[i] = static_cast<idx_type>(i);
      69              :     }
      70          365 :     for (size_t i = 0; i < n + buckets; ++i)
      71              :     {
      72          333 :         backlinks()[items()[i]] = static_cast<idx_type>(i);
      73              :     }
      74           32 : }
      75              : 
      76           10 : void multi_list::NotInBuckets::iter(::etl::delegate<bool(size_t)> const f) const
      77              : {
      78           10 :     size_t const n              = self->_n;
      79           10 :     idx_type const* const items = self->items();
      80           10 :     size_t pos[2]               = {items[n + buckets[0]], items[n + buckets[1]]};
      81           10 :     size_t i                    = 0;
      82              : 
      83              :     do
      84              :     {
      85           46 :         ++i;
      86           90 :         while (((n - i) == pos[0]) || ((n - i) == pos[1]))
      87              :         {
      88           44 :             ++i;
      89           44 :             auto const j = ((pos[0] < pos[1]) && (pos[1] < n)) ? 1U : 0U;
      90           44 :             pos[j]       = items[pos[j]];
      91              :         }
      92           46 :     } while ((i < n + 1) && f(n - i));
      93           10 : }
      94              : } // namespace internal
      95              : } // namespace shed