Ignore:
Timestamp:
2018-07-05T21:41:25Z (6 years ago)
Author:
Dzejrou <dzejrou@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
3ae7827
Parents:
65ee021
git-author:
Dzejrou <dzejrou@…> (2018-07-03 18:04:10)
git-committer:
Dzejrou <dzejrou@…> (2018-07-05 21:41:25)
Message:

cpp: fixed unordered_map tests on ppc32 and sparc64, added additional checks to make sure the programs don't fail

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/cpp/include/__bits/adt/hash_table_policies.hpp

    r65ee021 r07eaeea  
    4747        {
    4848            auto idx = table.get_bucket_idx_(key);
    49             return make_tuple(
    50                 &table.table_[idx],
    51                 table.table_[idx].head,
    52                 idx
    53             );
    54         }
    55 
    56         template<class Table, class Key>
    57         static typename Table::size_type erase(Table& table, const Key& key)
    58         {
    59             auto idx = table.get_bucket_idx_(key);
    6049            auto head = table.table_[idx].head;
    61             auto current = head;
    62 
    63             if (!current)
    64                 return 0;
    65 
    66             do
    67             {
    68                 if (table.keys_equal(key, current->value))
    69                 {
    70                     --table.size_;
    71 
    72                     if (current == head)
    73                     {
    74                         if (current->next != head)
    75                             table.table_[idx].head = current->next;
    76                         else
    77                             table.table_[idx].head = nullptr;
    78                     }
    79 
    80                     current->unlink();
    81                     delete current;
    82 
    83                     return 1;
    84                 }
    85                 else
    86                     current = current->next;
    87             }
    88             while (current != head);
    89 
    90             return 0;
    91         }
    92 
    93         template<class Table, class Key>
    94         static pair<
    95             typename Table::iterator,
    96             typename Table::iterator
    97         > equal_range(Table& table, const Key& key)
    98         {
    99             auto it = table.find(key);
    100             return make_pair(it, ++it);
    101         }
    102 
    103         template<class Table, class Key>
    104         static pair<
    105             typename Table::const_iterator,
    106             typename Table::const_iterator
    107         > equal_range_const(const Table& table, const Key& key)
    108         { // Note: We cannot overload by return type, so we use a different name.
    109             auto it = table.find(key);
    110             return make_pair(it, ++it);
    111         }
    112 
    113         /**
    114          * Note: We have to duplicate code for emplace, insert(const&)
    115          *       and insert(&&) here, because the node (which makes distinction
    116          *       between the arguments) is only created if the value isn't
    117          *       in the table already.
    118          */
    119 
    120         template<class Table, class... Args>
    121         static pair<
    122             typename Table::iterator, bool
    123         > emplace(Table& table, Args&&... args)
    124         {
    125             using value_type = typename Table::value_type;
    126             using node_type  = typename Table::node_type;
    127             using iterator   = typename Table::iterator;
    128 
    129             table.increment_size();
    130 
    131             auto val = value_type{forward<Args>(args)...};
    132             const auto& key = table.get_key(val);
    133             auto [bucket, target, idx] = table.find_insertion_spot(key);
    134 
    135             if (!bucket)
    136                 return make_pair(table.end(), false);
    137 
    138             if (target && table.keys_equal(key, target->value))
    139             {
    140                 table.decrement_size();
    141 
    142                 return make_pair(
    143                     iterator{
    144                         table.table(), idx, table.bucket_count(),
    145                         target
    146                     },
    147                     false
    148                 );
    149             }
    150             else
    151             {
    152                 auto node = new node_type{move(val)};
    153                 bucket->prepend(node);
    154 
    155                 return make_pair(iterator{
    156                     table.table(), idx,
    157                     table.bucket_count(),
    158                     node
    159                 }, true);
    160             }
    161         }
    162 
    163         template<class Table, class Value>
    164         static pair<
    165             typename Table::iterator, bool
    166         > insert(Table& table, const Value& val)
    167         {
    168             using node_type  = typename Table::node_type;
    169             using iterator   = typename Table::iterator;
    170 
    171             table.increment_size();
    172 
    173             const auto& key = table.get_key(val);
    174             auto [bucket, target, idx] = table.find_insertion_spot(key);
    175 
    176             if (!bucket)
    177                 return make_pair(table.end(), false);
    178 
    179             if (target && table.keys_equal(key, target->value))
    180             {
    181                 table.decrement_size();
    182 
    183                 return make_pair(
    184                     iterator{
    185                         table.table(), idx, table.bucket_count(),
    186                         target
    187                     },
    188                     false
    189                 );
    190             }
    191             else
    192             {
    193                 auto node = new node_type{val};
    194                 bucket->prepend(node);
    195 
    196                 return make_pair(iterator{
    197                     table.table(), idx,
    198                     table.bucket_count(),
    199                     node
    200                 }, true);
    201             }
    202         }
    203 
    204         template<class Table, class Value>
    205         static pair<
    206             typename Table::iterator, bool
    207         > insert(Table& table, Value&& val)
    208         {
    209             using value_type = typename Table::value_type;
    210             using node_type  = typename Table::node_type;
    211             using iterator   = typename Table::iterator;
    212 
    213             table.increment_size();
    214 
    215             const auto& key = table.get_key(val);
    216             auto [bucket, target, idx] = table.find_insertion_spot(key);
    217 
    218             if (!bucket)
    219                 return make_pair(table.end(), false);
    220 
    221             if (target && table.keys_equal(key, target->value))
    222             {
    223                 table.decrement_size();
    224 
    225                 return make_pair(
    226                     iterator{
    227                         table.table(), idx, table.bucket_count(),
    228                         target
    229                     },
    230                     false
    231                 );
    232             }
    233             else
    234             {
    235                 auto node = new node_type{forward<value_type>(val)};
    236                 bucket->prepend(node);
    237 
    238                 return make_pair(iterator{
    239                     table.table(), idx,
    240                     table.bucket_count(),
    241                     node
    242                 }, true);
    243             }
    244         }
    245     };
    246 
    247     struct hash_multi_policy
    248     {
    249         template<class Table, class Key>
    250         static typename Table::size_type count(const Table& table, const Key& key)
    251         {
    252             auto head = table.table_[table.get_bucket_idx_(key)].head;
    253             if (!head)
    254                 return 0;
    255 
    256             auto current = head;
    257             typename Table::size_type res = 0;
    258             do
    259             {
    260                 if (table.keys_equal(key, current->value))
    261                     ++res;
    262 
    263                 current = current->next;
    264             }
    265             while (current != head);
    266 
    267             return res;
    268         }
    269 
    270         template<class Table, class Key>
    271         static typename Table::place_type find_insertion_spot(const Table& table, const Key& key)
    272         {
    273             auto idx = table.get_bucket_idx_(key);
    274             auto head = table.table_[idx].head;
    27550
    27651            if (head)
    277             {
     52            { // Check if the key is present.
    27853                auto current = head;
    27954                do
    … …  
    28964
    29065                    current = current->next;
    291                 } while (current != head);
     66                } while (current && current != head);
    29267            }
    29368
    … …  
    30580            auto head = table.table_[idx].head;
    30681            auto current = head;
     82
     83            if (!current)
     84                return 0;
     85
     86            do
     87            {
     88                if (table.keys_equal(key, current->value))
     89                {
     90                    --table.size_;
     91
     92                    if (current == head)
     93                    {
     94                        if (current->next != head)
     95                            table.table_[idx].head = current->next;
     96                        else
     97                            table.table_[idx].head = nullptr;
     98                    }
     99
     100                    current->unlink();
     101                    delete current;
     102
     103                    return 1;
     104                }
     105                else
     106                    current = current->next;
     107            }
     108            while (current && current != head);
     109
     110            return 0;
     111        }
     112
     113        template<class Table, class Key>
     114        static pair<
     115            typename Table::iterator,
     116            typename Table::iterator
     117        > equal_range(Table& table, const Key& key)
     118        {
     119            auto it = table.find(key);
     120            return make_pair(it, ++it);
     121        }
     122
     123        template<class Table, class Key>
     124        static pair<
     125            typename Table::const_iterator,
     126            typename Table::const_iterator
     127        > equal_range_const(const Table& table, const Key& key)
     128        { // Note: We cannot overload by return type, so we use a different name.
     129            auto it = table.find(key);
     130            return make_pair(it, ++it);
     131        }
     132
     133        /**
     134         * Note: We have to duplicate code for emplace, insert(const&)
     135         *       and insert(&&) here, because the node (which makes distinction
     136         *       between the arguments) is only created if the value isn't
     137         *       in the table already.
     138         */
     139
     140        template<class Table, class... Args>
     141        static pair<
     142            typename Table::iterator, bool
     143        > emplace(Table& table, Args&&... args)
     144        {
     145            using value_type = typename Table::value_type;
     146            using node_type  = typename Table::node_type;
     147            using iterator   = typename Table::iterator;
     148
     149            table.increment_size();
     150
     151            auto val = value_type{forward<Args>(args)...};
     152            const auto& key = table.get_key(val);
     153            auto [bucket, target, idx] = table.find_insertion_spot(key);
     154
     155            if (!bucket)
     156                return make_pair(table.end(), false);
     157
     158            if (target && table.keys_equal(key, target->value))
     159            {
     160                table.decrement_size();
     161
     162                return make_pair(
     163                    iterator{
     164                        table.table(), idx, table.bucket_count(),
     165                        target
     166                    },
     167                    false
     168                );
     169            }
     170            else
     171            {
     172                auto node = new node_type{move(val)};
     173                bucket->prepend(node);
     174
     175                return make_pair(iterator{
     176                    table.table(), idx,
     177                    table.bucket_count(),
     178                    node
     179                }, true);
     180            }
     181        }
     182
     183        template<class Table, class Value>
     184        static pair<
     185            typename Table::iterator, bool
     186        > insert(Table& table, const Value& val)
     187        {
     188            using node_type  = typename Table::node_type;
     189            using iterator   = typename Table::iterator;
     190
     191            table.increment_size();
     192
     193            const auto& key = table.get_key(val);
     194            auto [bucket, target, idx] = table.find_insertion_spot(key);
     195
     196            if (!bucket)
     197                return make_pair(table.end(), false);
     198
     199            if (target && table.keys_equal(key, target->value))
     200            {
     201                table.decrement_size();
     202
     203                return make_pair(
     204                    iterator{
     205                        table.table(), idx, table.bucket_count(),
     206                        target
     207                    },
     208                    false
     209                );
     210            }
     211            else
     212            {
     213                auto node = new node_type{val};
     214                bucket->prepend(node);
     215
     216                return make_pair(iterator{
     217                    table.table(), idx,
     218                    table.bucket_count(),
     219                    node
     220                }, true);
     221            }
     222        }
     223
     224        template<class Table, class Value>
     225        static pair<
     226            typename Table::iterator, bool
     227        > insert(Table& table, Value&& val)
     228        {
     229            using value_type = typename Table::value_type;
     230            using node_type  = typename Table::node_type;
     231            using iterator   = typename Table::iterator;
     232
     233            table.increment_size();
     234
     235            const auto& key = table.get_key(val);
     236            auto [bucket, target, idx] = table.find_insertion_spot(key);
     237
     238            if (!bucket)
     239                return make_pair(table.end(), false);
     240
     241            if (target && table.keys_equal(key, target->value))
     242            {
     243                table.decrement_size();
     244
     245                return make_pair(
     246                    iterator{
     247                        table.table(), idx, table.bucket_count(),
     248                        target
     249                    },
     250                    false
     251                );
     252            }
     253            else
     254            {
     255                auto node = new node_type{forward<value_type>(val)};
     256                bucket->prepend(node);
     257
     258                return make_pair(iterator{
     259                    table.table(), idx,
     260                    table.bucket_count(),
     261                    node
     262                }, true);
     263            }
     264        }
     265    };
     266
     267    struct hash_multi_policy
     268    {
     269        template<class Table, class Key>
     270        static typename Table::size_type count(const Table& table, const Key& key)
     271        {
     272            auto head = table.table_[table.get_bucket_idx_(key)].head;
     273            if (!head)
     274                return 0;
     275
     276            auto current = head;
     277            typename Table::size_type res = 0;
     278            do
     279            {
     280                if (table.keys_equal(key, current->value))
     281                    ++res;
     282
     283                current = current->next;
     284            }
     285            while (current && current != head);
     286
     287            return res;
     288        }
     289
     290        template<class Table, class Key>
     291        static typename Table::place_type find_insertion_spot(const Table& table, const Key& key)
     292        {
     293            auto idx = table.get_bucket_idx_(key);
     294            auto head = table.table_[idx].head;
     295
     296            if (head)
     297            {
     298                auto current = head;
     299                do
     300                {
     301                    if (table.keys_equal(key, current->value))
     302                    {
     303                        return make_tuple(
     304                            &table.table_[idx],
     305                            current,
     306                            idx
     307                        );
     308                    }
     309
     310                    current = current->next;
     311                } while (current && current != head);
     312            }
     313
     314            return make_tuple(
     315                &table.table_[idx],
     316                table.table_[idx].head,
     317                idx
     318            );
     319        }
     320
     321        template<class Table, class Key>
     322        static typename Table::size_type erase(Table& table, const Key& key)
     323        {
     324            auto idx = table.get_bucket_idx_(key);
     325            auto head = table.table_[idx].head;
     326            auto current = head;
    307327            table.table_[idx].head = nullptr;
     328            decltype(head) last = nullptr;
    308329
    309330            if (!current)
    … …  
    321342                auto tmp = current;
    322343                current = current->next;
    323 
     344                tmp->unlink();
     345
     346                --table.size_;
    324347                if (!table.keys_equal(key, tmp->value))
    325                     table.table_[idx].append(tmp);
     348                {
     349                    if (!last)
     350                        table.table_[idx].head = tmp;
     351                    else
     352                        last->append(tmp);
     353                    last = tmp;
     354                }
    326355                else
    327356                {
    328357                    ++res;
    329                     --table.size_;
    330358
    331359                    delete tmp;
    332360                }
    333361            }
    334             while (current != head);
     362            while (current && current != head);
    335363
    336364            return res;
    … …  
    351379            {
    352380                ++last;
    353             } while (table.keys_equal(key, *last));
     381            } while (last != table.end() && table.keys_equal(key, *last));
    354382
    355383            return make_pair(first, last);
    … …  
    370398            {
    371399                ++last;
    372             } while (table.keys_equal(key, *last));
     400            } while (last != table.end() && table.keys_equal(key, *last));
    373401
    374402            return make_pair(first, last);
    … …  
    417445
    418446            if (!bucket)
    419                 table.end();
     447                return table.end();
    420448
    421449            if (target && table.keys_equal(key, target->value))
Note: See TracChangeset for help on using the changeset viewer.