xref: /openbmc/bmcweb/include/human_sort.hpp (revision 8ece0e45)
1 #pragma once
2 
3 #include <charconv>
4 #include <iterator>
5 #include <string_view>
6 
7 namespace details
8 {
9 
10 // This implementation avoids the complexity of using std::isdigit, which pulls
11 // in all of <locale>, and likely has other consequences.
simpleIsDigit(const char c)12 inline bool simpleIsDigit(const char c)
13 {
14     return c >= '0' && c <= '9';
15 }
16 
17 enum class ModeType
18 {
19     STRING,
20     NUMBER
21 };
22 
23 } // namespace details
24 
alphanumComp(std::string_view left,std::string_view right)25 inline int alphanumComp(std::string_view left, std::string_view right)
26 {
27     std::string_view::const_iterator l = left.cbegin();
28     std::string_view::const_iterator r = right.cbegin();
29 
30     details::ModeType mode = details::ModeType::STRING;
31 
32     while (l != left.end() && r != right.end())
33     {
34         if (mode == details::ModeType::STRING)
35         {
36             // check if this are digit characters
37             const bool lDigit = details::simpleIsDigit(*l);
38             const bool rDigit = details::simpleIsDigit(*r);
39             // if both characters are digits, we continue in NUMBER mode
40             if (lDigit && rDigit)
41             {
42                 mode = details::ModeType::NUMBER;
43                 continue;
44             }
45             // if only the left character is a digit, we have a result
46             if (lDigit)
47             {
48                 return -1;
49             } // if only the right character is a digit, we have a result
50             if (rDigit)
51             {
52                 return +1;
53             }
54             // compute the difference of both characters
55             const int diff = *l - *r;
56             // if they differ we have a result
57             if (diff != 0)
58             {
59                 return diff;
60             }
61             // otherwise process the next characters
62             std::advance(l, 1);
63             std::advance(r, 1);
64         }
65         else // mode==NUMBER
66         {
67             // get the left number
68             int lInt = 0;
69             auto fc = std::from_chars(&(*l), &(*left.end()), lInt);
70             std::advance(l, std::distance(l, fc.ptr));
71 
72             // get the right number
73             int rInt = 0;
74             fc = std::from_chars(&(*r), &(*right.end()), rInt);
75             std::advance(r, std::distance(r, fc.ptr));
76 
77             // if the difference is not equal to zero, we have a comparison
78             // result
79             const int diff = lInt - rInt;
80             if (diff != 0)
81             {
82                 return diff;
83             }
84 
85             // otherwise we process the next substring in STRING mode
86             mode = details::ModeType::STRING;
87         }
88     }
89     if (r == right.end() && l == left.end())
90     {
91         return 0;
92     }
93     if (r == right.end())
94     {
95         return 1;
96     }
97     return -1;
98 }
99 
100 // A generic template type compatible with std::less that can be used on generic
101 // containers (set, map, etc)
102 template <class Type>
103 struct AlphanumLess
104 {
operator ()AlphanumLess105     bool operator()(const Type& left, const Type& right) const
106     {
107         return alphanumComp(left, right) < 0;
108     }
109 };
110