Changeset 492377a in mainline


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

Location:
uspace/lib/cpp/include
Files:
2 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

  • uspace/lib/cpp/include/internal/hash_table.hpp

    re037873d r492377a  
    215215            return make_pair(it, ++it);
    216216        }
     217
     218        /**
     219         * Note: We have to duplicate code for emplace, insert(const&)
     220         *       and insert(&&) here, because the node (which makes distinction
     221         *       between the arguments) is only created if the value isn't
     222         *       in the table already.
     223         */
     224
     225        template<class Table, class... Args>
     226        static pair<
     227            typename Table::iterator, bool
     228        > emplace(Table& table, Args&&... args)
     229        {
     230            using value_type = typename Table::value_type;
     231            using node_type  = typename Table::node_type;
     232            using iterator   = typename Table::iterator;
     233
     234            table.increment_size();
     235
     236            auto val = value_type{forward<Args>(args)...};
     237            const auto& key = table.get_key(val);
     238            auto [bucket, target, idx] = table.find_insertion_spot(key);
     239
     240            if (!bucket)
     241                return make_pair(table.end(), false);
     242
     243            if (target && table.keys_equal(key, target->value))
     244            {
     245                table.decrement_size();
     246
     247                return make_pair(
     248                    iterator{
     249                        table.table(), idx, table.bucket_count(),
     250                        target
     251                    },
     252                    false
     253                );
     254            }
     255            else
     256            {
     257                auto node = new node_type{move(val)};
     258                bucket->prepend(node);
     259
     260                return make_pair(iterator{
     261                    table.table(), idx,
     262                    table.bucket_count(),
     263                    node
     264                }, true);
     265            }
     266        }
     267
     268        template<class Table, class Value>
     269        static pair<
     270            typename Table::iterator, bool
     271        > insert(Table& table, const Value& val)
     272        {
     273            using node_type  = typename Table::node_type;
     274            using iterator   = typename Table::iterator;
     275
     276            table.increment_size();
     277
     278            const auto& key = table.get_key(val);
     279            auto [bucket, target, idx] = table.find_insertion_spot(key);
     280
     281            if (!bucket)
     282                return make_pair(table.end(), false);
     283
     284            if (target && table.keys_equal(key, target->value))
     285            {
     286                table.decrement_size();
     287
     288                return make_pair(
     289                    iterator{
     290                        table.table(), idx, table.bucket_count(),
     291                        target
     292                    },
     293                    false
     294                );
     295            }
     296            else
     297            {
     298                auto node = new node_type{val};
     299                bucket->prepend(node);
     300
     301                return make_pair(iterator{
     302                    table.table(), idx,
     303                    table.bucket_count(),
     304                    node
     305                }, true);
     306            }
     307        }
     308
     309        template<class Table, class Value>
     310        static pair<
     311            typename Table::iterator, bool
     312        > insert(Table& table, Value&& val)
     313        {
     314            using value_type = typename Table::value_type;
     315            using node_type  = typename Table::node_type;
     316            using iterator   = typename Table::iterator;
     317
     318            table.increment_size();
     319
     320            const auto& key = table.get_key(val);
     321            auto [bucket, target, idx] = table.find_insertion_spot(key);
     322
     323            if (!bucket)
     324                return make_pair(table.end(), false);
     325
     326            if (target && table.keys_equal(key, target->value))
     327            {
     328                table.decrement_size();
     329
     330                return make_pair(
     331                    iterator{
     332                        table.table(), idx, table.bucket_count(),
     333                        target
     334                    },
     335                    false
     336                );
     337            }
     338            else
     339            {
     340                auto node = new node_type{forward<value_type>(val)};
     341                bucket->prepend(node);
     342
     343                return make_pair(iterator{
     344                    table.table(), idx,
     345                    table.bucket_count(),
     346                    node
     347                }, true);
     348            }
     349        }
    217350    };
    218351
    … …  
    340473            return make_pair(first, last);
    341474        }
     475
     476        template<class Table, class... Args>
     477        static pair<
     478            typename Table::iterator, bool
     479        > emplace(Table& table, Args&&... args)
     480        {
     481            using node_type  = typename Table::node_type;
     482
     483            auto node = new node_type{forward<Args>(args)...};
     484
     485            return insert(table, node);
     486        }
     487
     488        template<class Table, class Value>
     489        static pair<
     490            typename Table::iterator, bool
     491        > insert(Table& table, const Value& val)
     492        {
     493            using node_type  = typename Table::node_type;
     494
     495            auto node = new node_type{val};
     496
     497            return insert(table, node);
     498        }
     499
     500        template<class Table, class Value>
     501        static pair<
     502            typename Table::iterator, bool
     503        > insert(Table& table, Value&& val)
     504        {
     505            using value_type = typename Table::value_type;
     506            using node_type  = typename Table::node_type;
     507
     508            auto node = new node_type{forward<value_type>(val)};
     509
     510            return insert(table, node);
     511        }
     512
     513        template<class Table>
     514        static pair<
     515            typename Table::iterator, bool
     516        > insert(Table& table, typename Table::node_type* node)
     517        {
     518            using iterator   = typename Table::iterator;
     519
     520            table.increment_size();
     521
     522            const auto& key = table.get_key(node->value);
     523            auto [bucket, target, idx] = table.find_insertion_spot(key);
     524
     525            if (!bucket)
     526                return make_pair(table.end(), false);
     527
     528            if (target && table.keys_equal(key, target->value))
     529                target->append(node);
     530            else
     531                bucket->prepend(node);
     532
     533            return make_pair(iterator{
     534                table.table(), idx,
     535                table.bucket_count(),
     536                node
     537            }, true);
     538        }
    342539    };
    343540
    … …  
    8851082            }
    8861083
    887             template<class Allocator, class... Args>
    888             void emplace(const hint_type& where, Allocator& alloc, Args&&... args)
    889             {
    890                 if (!hint_ok_(where))
    891                     return;
    892 
    893                 auto node = new list_node<value_type>{forward<Args&&>(args)...};
    894                 if (get<1>(where) == nullptr) // Append here will create a new head.
    895                     get<0>(where)->append(node);
    896                 else // Prepending before an exact position is common in the standard.
    897                     get<1>(where)->prepend(node);
    898 
    899                 ++size_;
    900 
    901                 rehash_if_needed();
    902             }
    903 
    904             void insert(const hint_type& where, const value_type& val)
    905             {
    906                 if (!hint_ok_(where))
    907                     return;
    908 
    909                 auto node = new list_node<value_type>{val};
    910                 if (get<1>(where) == nullptr)
    911                     get<0>(where)->append(node);
    912                 else
    913                     get<1>(where)->prepend(node);
    914 
    915                 ++size_;
    916 
    917                 rehash_if_needed();
    918             }
    919 
    920             void insert(const hint_type& where, value_type&& val)
    921             {
    922                 if (!hint_ok_(where))
    923                     return;
    924 
    925                 auto node = new list_node<value_type>{forward<value_type>(val)};
    926                 if (get<1>(where) == nullptr)
    927                     get<0>(where)->append(node);
    928                 else
    929                     get<1>(where)->prepend(node);
    930 
    931                 ++size_;
    932 
    933                 rehash_if_needed();
     1084            template<class... Args>
     1085            pair<iterator, bool> emplace(Args&&... args)
     1086            {
     1087                return Policy::emplace(*this, forward<Args>(args)...);
     1088            }
     1089
     1090            pair<iterator, bool> insert(const value_type& val)
     1091            {
     1092                return Policy::insert(*this, val);
     1093            }
     1094
     1095            pair<iterator, bool> insert(value_type&& val)
     1096            {
     1097                return Policy::insert(*this, forward<value_type>(val));
    9341098            }
    9351099
    … …  
    12511415            }
    12521416
    1253             node_type* find_node_or_return_head(const key_type& key,
    1254                                                 const hash_table_bucket<value_type, size_type>& bucket)
    1255             {
    1256                 if (bucket.head)
    1257                 {
    1258                     auto head = bucket.head;
    1259                     auto current = bucket.head;
    1260 
    1261                     do
    1262                     {
    1263                         if (keys_equal(key, current->value))
    1264                             return current;
    1265                         else
    1266                             current = current->next;
    1267                     }
    1268                     while (current != head);
    1269 
    1270                     return head;
    1271                 }
    1272                 else
    1273                     return nullptr;
    1274             }
    1275 
    12761417        private:
    12771418            hash_table_bucket<value_type, size_type>* table_;
    … …  
    12901431            }
    12911432
    1292             bool hint_ok_(const hint_type& hint)
    1293             {
    1294                 // TODO: pass this to the policy, because the multi policy
    1295                 //       will need to check if a similar key is close,
    1296                 //       that is something like:
    1297                 //          return get<1>(hint)->prev->key == key || !bucket.contains(key)
    1298                 // TODO: also, make it public and make hint usage one level above?
    1299                 //       (since we already have insert with decisive hint)
    1300                 return get<0>(hint) != nullptr && get<2>(hint) < bucket_count_;
    1301             }
    1302 
    1303             // Praise C++11 for this.
    13041433            friend Policy;
    13051434    };
Note: See TracChangeset for help on using the changeset viewer.