Uploaded image for project: 'Core Server'
  1. Core Server
  2. SERVER-66764

Polyfill C++20 constexpr isSorted

    • Type: Icon: Bug Bug
    • Resolution: Done
    • Priority: Icon: Major - P3 Major - P3
    • None
    • Affects Version/s: None
    • Component/s: None
    • None
    • ALL
    • Service Arch 2022-06-27, Service Arch 2022-07-11, Service Arch 2022-07-25

      One can make the case a flat data structure should be declared with all elements already sorted so run-time checks for elements being contained within the list can be optimized. C++20 has isSorted as a constexpr which therefore can be used with static_asserts possibly failing compilation. This is a betterment to writing a comment above the data structure and hoping for the best as non-sorted lists with silently degrade performance or require extra run-time checks or complicated constructs. Here is a proposal for a possible polyfill:

      template <typename It>
      constexpr bool constexprIsSorted(It b, It e) {
      #if __cpp_lib_constexpr_algorithms >= 201806L
          return std::is_sorted(b, e);
      #else
          if (b == e)
              return true;
          auto p = b++;
          while (b != e) {
              if (!(*p < *b))
                  return false;
              p = b++;
          }
          return true;
      #endif
      } 

      And here's an example on how to use it:

       // Keep this sorted.
      constexpr std::array roCmds{
          "collStats"_sd,
          "count"_sd,
          "dataSize"_sd,
          "dbStats"_sd,
          "distinct"_sd,
          "filemd5"_sd,
          "find"_sd,
          "listCollections"_sd,
          "listIndexes"_sd,
          "planCacheListFilters"_sd,
      };
      
      static_assert(constexprIsSorted(roCmds.begin(), roCmds.end()));
      
      bool isReadOnlyCommand(StringData cmd) {
          return std::binary_search(roCmds.begin(), roCmds.end(), cmd);
      }  

            Assignee:
            alex.li@mongodb.com Alex Li
            Reporter:
            daniel.morilha@mongodb.com Daniel Morilha (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

              Created:
              Updated:
              Resolved: