Ignore:
Timestamp:
2018-07-05T21:41:21Z (6 years ago)
Author:
Dzejrou <dzejrou@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
2d46556
Parents:
e037873d
git-author:
Dzejrou <dzejrou@…> (2018-04-26 15:12:10)
git-committer:
Dzejrou <dzejrou@…> (2018-07-05 21:41:21)
Message:

cpp: moved more logic to the policies, since a lot of the code added to unordered_map was the same as in unordered_set

File:
1 edited

Legend:

Unmodified
Added
Removed

  • uspace/lib/cpp/include/impl/unordered_map.hpp

    re037873d r492377a  
    245245            pair<iterator, bool> emplace(Args&&... args)
    246246            {
    247                 /**
    248                  * Note: Some of these modifier functions start off
    249                  *       by incrementing the table's element count and
    250                  *       decrement it when insertion does not take place.
    251                  *       This is because we need to cause rehashing if
    252                  *       there are too many elements, but rehashing itself
    253                  *       would invalidate all pointers we get from
    254                  *       find_insertion_spot, which would require us to
    255                  *       do another find. But this way we avoid two searches
    256                  *       with the possibility of a rehash that is not necessary
    257                  *       (but hardly a bad thing as the table needs just one
    258                  *       element more to rehash).
    259                  *
    260                  *       Also, there are 3 functions with similar bodies,
    261                  *       but the duplicit code cannot be moved to a common
    262                  *       sub-function because all three require different
    263                  *       handling of the value (move, forward and copy).
    264                  */
    265                 table_.increment_size();
    266 
    267                 auto val = value_type{forward<Args>(args)...};
    268                 auto key = table_.get_key(val);
    269                 auto spot = table_.find_insertion_spot(key);
    270                 auto bucket = get<0>(spot);
    271                 auto idx = get<2>(spot);
    272 
    273                 if (!bucket)
    274                     return make_pair(end(), false);
    275 
    276                 auto target = table_.find_node_or_return_head(key, *bucket);
    277                 if (target && table_.keys_equal(key, target->value))
    278                 {
    279                     table_.decrement_size();
    280                     return make_pair(
    281                         iterator{
    282                             table_.table(), idx, table_.bucket_count(),
    283                             target
    284                         },
    285                         false
    286                     );
    287                 }
    288                 else
    289                 {
    290                     auto node = new node_type{move(val)};
    291                     bucket->append(node);
    292 
    293                     return make_pair(iterator{
    294                         table_.table(), idx,
    295                         table_.bucket_count(),
    296                         node
    297                     }, true);
    298                 }
     247                return table_.emplace(forward<Args>(args)...);
    299248            }
    300249
    … …  
    307256            pair<iterator, bool> insert(const value_type& val)
    308257            {
    309                 table_.increment_size();
    310 
    311                 auto key = table_.get_key(val);
    312                 auto spot = table_.find_insertion_spot(key);
    313                 auto bucket = get<0>(spot);
    314                 auto idx = get<2>(spot);
    315 
    316                 if (!bucket)
    317                     return make_pair(end(), false);
    318 
    319                 auto target = table_.find_node_or_return_head(key, *bucket);
    320                 if (target && table_.keys_equal(key, target->value))
    321                 {
    322                     table_.decrement_size();
    323                     return make_pair(
    324                         iterator{
    325                             table_.table(), idx, table_.bucket_count(),
    326                             target
    327                         },
    328                         false
    329                     );
    330                 }
    331                 else
    332                 {
    333                     auto node = new node_type{val};
    334                     bucket->append(node);
    335 
    336                     return make_pair(iterator{
    337                         table_.table(), idx,
    338                         table_.bucket_count(),
    339                         node
    340                     }, true);
    341                 }
     258                return table_.insert(val);
    342259            }
    343260
    344261            pair<iterator, bool> insert(value_type&& val)
    345262            {
    346                 table_.increment_size();
    347 
    348                 auto key = table_.get_key(val);
    349                 auto spot = table_.find_insertion_spot(key);
    350                 auto bucket = get<0>(spot);
    351                 auto idx = get<2>(spot);
    352 
    353                 if (!bucket)
    354                     return make_pair(end(), false);
    355 
    356                 auto target = table_.find_node_or_return_head(key, *bucket);
    357                 if (target && table_.keys_equal(key, target->value))
    358                 {
    359                     table_.decrement_size();
    360                     return make_pair(
    361                         iterator{
    362                             table_.table(), idx, table_.bucket_count(),
    363                             target
    364                         },
    365                         false
    366                     );
    367                 }
    368                 else
    369                 {
    370                     auto node = new node_type{forward<value_type>(val)};
    371                     bucket->append(node);
    372 
    373                     return make_pair(iterator{
    374                         table_.table(), idx,
    375                         table_.bucket_count(),
    376                         node
    377                     }, true);
    378                 }
     263                return table_.insert(forward<value_type>(val));
    379264            }
    380265
    … …  
    431316                table_.increment_size();
    432317
    433                 auto spot = table_.find_insertion_spot(key);
    434                 auto bucket = get<0>(spot);
    435                 auto idx = get<2>(spot);
     318                auto [bucket, target, idx] = table_.find_insertion_spot(key);
    436319
    437320                if (!bucket)
    438321                    return make_pair(end(), false);
    439322
    440                 auto target = table_.find_node_or_return_head(key, *bucket);
    441323                if (target && table_.keys_equal(key, target->value))
    442324                {
    … …  
    469351                table_.increment_size();
    470352
    471                 auto spot = table_.find_insertion_spot(key);
    472                 auto bucket = get<0>(spot);
    473                 auto idx = get<2>(spot);
     353                auto [bucket, target, idx] = table_.find_insertion_spot(key);
    474354
    475355                if (!bucket)
    476356                    return make_pair(end(), false);
    477357
    478                 auto target = table_.find_node_or_return_head(key, *bucket);
    479358                if (target && table_.keys_equal(key, target->value))
    480359                {
    … …  
    519398                table_.increment_size();
    520399
    521                 auto spot = table_.find_insertion_spot(key);
    522                 auto bucket = get<0>(spot);
    523                 auto idx = get<2>(spot);
     400                auto [bucket, target, idx] = table_.find_insertion_spot(key);
    524401
    525402                if (!bucket)
    526403                    return make_pair(end(), false);
    527404
    528                 auto target = table_.find_node_or_return_head(key, *bucket);
    529405                if (target && table_.keys_equal(key, target->value))
    530406                {
    … …  
    558434                table_.increment_size();
    559435
    560                 auto spot = table_.find_insertion_spot(key);
    561                 auto bucket = get<0>(spot);
    562                 auto idx = get<2>(spot);
     436                auto [bucket, target, idx] = table_.find_insertion_spot(key);
    563437
    564438                if (!bucket)
    565439                    return make_pair(end(), false);
    566440
    567                 auto target = table_.find_node_or_return_head(key, *bucket);
    568441                if (target && table_.keys_equal(key, target->value))
    569442                {
    … …  
    1046919            pair<iterator, bool> emplace(Args&&... args)
    1047920            {
    1048                 table_.increment_size();
    1049 
    1050                 auto val = value_type{forward<Args>(args)...};
    1051                 auto key = table_.get_key(val);
    1052                 auto spot = table_.find_insertion_spot(key);
    1053                 auto bucket = get<0>(spot);
    1054                 auto idx = get<2>(spot);
    1055 
    1056                 if (!bucket)
    1057                     return make_pair(end(), false);
    1058 
    1059                 auto target = table_.find_node_or_return_head(key, *bucket);
    1060                 auto node = new node_type{move(val)};
    1061                 if (target && table_.keys_equal(key, target->value))
    1062                     target->append(node);
    1063                 else
    1064                     bucket->prepend(node);
    1065 
    1066                 return make_pair(iterator{
    1067                     table_.table(), idx,
    1068                     table_.bucket_count(),
    1069                     node
    1070                 }, true);
     921                return table_.emplace(forward<Args>(args)...);
    1071922            }
    1072923
    … …  
    1079930            pair<iterator, bool> insert(const value_type& val)
    1080931            {
    1081                 table_.increment_size();
    1082 
    1083                 auto key = table_.get_key(val);
    1084                 auto spot = table_.find_insertion_spot(key);
    1085                 auto bucket = get<0>(spot);
    1086                 auto idx = get<2>(spot);
    1087 
    1088                 if (!bucket)
    1089                     return make_pair(end(), false);
    1090 
    1091                 auto target = table_.find_node_or_return_head(key, *bucket);
    1092                 auto node = new node_type{val};
    1093                 if (target && table_.keys_equal(key, target->value))
    1094                     target->append(node);
    1095                 else
    1096                     bucket->prepend(node);
    1097 
    1098                 return make_pair(iterator{
    1099                     table_.table(), idx,
    1100                     table_.bucket_count(),
    1101                     node
    1102                 }, true);
     932                return table_.insert(val);
    1103933            }
    1104934
    1105935            pair<iterator, bool> insert(value_type&& val)
    1106936            {
    1107                 table_.increment_size();
    1108 
    1109                 auto key = table_.get_key(val);
    1110                 auto spot = table_.find_insertion_spot(key);
    1111                 auto bucket = get<0>(spot);
    1112                 auto idx = get<2>(spot);
    1113 
    1114                 if (!bucket)
    1115                     return make_pair(end(), false);
    1116 
    1117                 auto target = table_.find_node_or_return_head(key, *bucket);
    1118                 auto node = new node_type{forward<value_type>(val)};
    1119                 if (target && table_.keys_equal(key, target->value))
    1120                     target->append(node);
    1121                 else
    1122                     bucket->prepend(node);
    1123 
    1124                 return make_pair(iterator{
    1125                     table_.table(), idx,
    1126                     table_.bucket_count(),
    1127                     node
    1128                 }, true);
     937                return table_.insert(forward<value_type>(val));
    1129938            }
    1130939
Note: See TracChangeset for help on using the changeset viewer.