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          177 : size_t multi_list::move_node(size_t const s, size_t dst)
      22              : {
      23          350 :     while ((s < items()[dst]) && (items()[dst] < _n))
      24              :     {
      25          173 :         dst = items()[dst];
      26              :     }
      27          177 :     auto const src            = backlinks()[s];
      28          177 :     items()[src]              = items()[s];
      29          177 :     items()[s]                = items()[dst];
      30          177 :     items()[dst]              = static_cast<idx_type>(s);
      31          177 :     backlinks()[items()[src]] = src;
      32          177 :     backlinks()[items()[s]]   = static_cast<idx_type>(s);
      33          177 :     backlinks()[items()[dst]] = static_cast<idx_type>(dst);
      34          177 :     return dst;
      35              : }
      36              : 
      37           34 : multi_list* multi_list::make(size_t const n, size_t const buckets, ::etl::span<uint8_t>& mem)
      38              : {
      39           34 :     if (!is_size_valid(n, buckets))
      40              :     {
      41            0 :         return nullptr;
      42              :     }
      43           34 :     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           34 :     if (!::etl::is_aligned<multi_list>(mem.data()))
      49              :     {
      50            1 :         return nullptr;
      51              :     }
      52           33 :     auto* const self = new (mem.data()) multi_list(n, buckets);
      53           33 :     mem.advance(memory_for(n, buckets));
      54           33 :     return self;
      55              : }
      56              : 
      57           33 : multi_list::multi_list(size_t const n, size_t const buckets)
      58              : {
      59           33 :     _n         = static_cast<idx_type>(n);
      60           33 :     _buckets   = static_cast<idx_type>(buckets);
      61           33 :     items()[0] = static_cast<idx_type>(n);
      62        65752 :     for (size_t i = 0; i < n; ++i)
      63              :     {
      64        65719 :         items()[i + 1] = static_cast<idx_type>(i);
      65              :     }
      66          151 :     for (size_t i = n + 1; i < n + buckets; ++i)
      67              :     {
      68          118 :         items()[i] = static_cast<idx_type>(i);
      69              :     }
      70        65903 :     for (size_t i = 0; i < n + buckets; ++i)
      71              :     {
      72        65870 :         backlinks()[items()[i]] = static_cast<idx_type>(i);
      73              :     }
      74           33 : }
      75              : 
      76           12 : void multi_list::NotInBuckets::iter(::etl::delegate<bool(size_t)> const f) const
      77              : {
      78           12 :     size_t const n              = self->_n;
      79           12 :     idx_type const* const items = self->items();
      80           12 :     size_t pos[2]               = {items[n + buckets[0]], items[n + buckets[1]]};
      81              : 
      82          112 :     for (size_t i = n; i > 0;)
      83              :     {
      84          100 :         --i;
      85          100 :         bool excluded = false;
      86          300 :         for (auto& bucket_pos : pos)
      87              :         {
      88          200 :             if (i == bucket_pos)
      89              :             {
      90           67 :                 bucket_pos = items[bucket_pos];
      91           67 :                 excluded   = true;
      92              :             }
      93              :         }
      94          100 :         if (!excluded && !f(i))
      95              :         {
      96            0 :             break;
      97              :         }
      98              :     }
      99           12 : }
     100              : } // namespace internal
     101              : } // namespace shed