include/boost/json /detail /charconv /detail /integer_search_trees.hpp
0.00% Lines (0/40) 0.00% Functions (0/1)
[ ] prev/next file n p prev/next uncovered line
TLA Baseline Branch
Line Hits Code Line Hits Code
1   // Copyright 2023 Matt Borland 1   // Copyright 2023 Matt Borland
2   // Distributed under the Boost Software License, Version 1.0. 2   // Distributed under the Boost Software License, Version 1.0.
3   // https://www.boost.org/LICENSE_1_0.txt 3   // https://www.boost.org/LICENSE_1_0.txt
4   4  
5   #ifndef BOOST_JSON_DETAIL_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP 5   #ifndef BOOST_JSON_DETAIL_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP
6   #define BOOST_JSON_DETAIL_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP 6   #define BOOST_JSON_DETAIL_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP
7   7  
8   // https://stackoverflow.com/questions/1489830/efficient-way-to-determine-number-of-digits-in-an-integer?page=1&tab=scoredesc#tab-top 8   // https://stackoverflow.com/questions/1489830/efficient-way-to-determine-number-of-digits-in-an-integer?page=1&tab=scoredesc#tab-top
9   // https://graphics.stanford.edu/~seander/bithacks.html 9   // https://graphics.stanford.edu/~seander/bithacks.html
10   10  
11   #include <boost/json/detail/charconv/detail/config.hpp> 11   #include <boost/json/detail/charconv/detail/config.hpp>
12   #include <limits> 12   #include <limits>
13   #include <array> 13   #include <array>
14   #include <cstdint> 14   #include <cstdint>
15   15  
16   namespace boost { namespace json { namespace detail { namespace charconv { namespace detail { 16   namespace boost { namespace json { namespace detail { namespace charconv { namespace detail {
17   17  
18   // Generic solution 18   // Generic solution
19   template <typename T> 19   template <typename T>
20   BOOST_JSON_CXX14_CONSTEXPR int num_digits(T x) noexcept 20   BOOST_JSON_CXX14_CONSTEXPR int num_digits(T x) noexcept
21   { 21   {
22   int digits = 0; 22   int digits = 0;
23   23  
24   while (x) 24   while (x)
25   { 25   {
26   x /= 10; 26   x /= 10;
27   ++digits; 27   ++digits;
28   } 28   }
29   29  
30   return digits; 30   return digits;
31   } 31   }
32   32  
33   template <> 33   template <>
34   BOOST_JSON_CXX14_CONSTEXPR int num_digits(std::uint32_t x) noexcept 34   BOOST_JSON_CXX14_CONSTEXPR int num_digits(std::uint32_t x) noexcept
35   { 35   {
36   if (x >= UINT32_C(10000)) 36   if (x >= UINT32_C(10000))
37   { 37   {
38   if (x >= UINT32_C(10000000)) 38   if (x >= UINT32_C(10000000))
39   { 39   {
40   if (x >= UINT32_C(100000000)) 40   if (x >= UINT32_C(100000000))
41   { 41   {
42   if (x >= UINT32_C(1000000000)) 42   if (x >= UINT32_C(1000000000))
43   { 43   {
44   return 10; 44   return 10;
45   } 45   }
46   return 9; 46   return 9;
47   } 47   }
48   return 8; 48   return 8;
49   } 49   }
50   50  
51   else if (x >= UINT32_C(100000)) 51   else if (x >= UINT32_C(100000))
52   { 52   {
53   if (x >= UINT32_C(1000000)) 53   if (x >= UINT32_C(1000000))
54   { 54   {
55   return 7; 55   return 7;
56   } 56   }
57   return 6; 57   return 6;
58   } 58   }
59   return 5; 59   return 5;
60   } 60   }
61   else if (x >= UINT32_C(100)) 61   else if (x >= UINT32_C(100))
62   { 62   {
63   if (x >= UINT32_C(1000)) 63   if (x >= UINT32_C(1000))
64   { 64   {
65   return 4; 65   return 4;
66   } 66   }
67   return 3; 67   return 3;
68   } 68   }
69   else if (x >= UINT32_C(10)) 69   else if (x >= UINT32_C(10))
70   { 70   {
71   return 2; 71   return 2;
72   } 72   }
73   73  
74   return 1; 74   return 1;
75   } 75   }
76   76  
77   template <> 77   template <>
MISUBC 78   ✗ BOOST_JSON_CXX14_CONSTEXPR int num_digits(std::uint64_t x) noexcept 78   ✗ BOOST_JSON_CXX14_CONSTEXPR int num_digits(std::uint64_t x) noexcept
79   { 79   {
MISUBC 80   ✗ if (x >= UINT64_C(10000000000)) 80   ✗ if (x >= UINT64_C(10000000000))
81   { 81   {
MISUBC 82   ✗ if (x >= UINT64_C(100000000000000)) 82   ✗ if (x >= UINT64_C(100000000000000))
83   { 83   {
MISUBC 84   ✗ if (x >= UINT64_C(10000000000000000)) 84   ✗ if (x >= UINT64_C(10000000000000000))
85   { 85   {
MISUBC 86   ✗ if (x >= UINT64_C(100000000000000000)) 86   ✗ if (x >= UINT64_C(100000000000000000))
87   { 87   {
MISUBC 88   ✗ if (x >= UINT64_C(1000000000000000000)) 88   ✗ if (x >= UINT64_C(1000000000000000000))
89   { 89   {
MISUBC 90   ✗ if (x >= UINT64_C(10000000000000000000)) 90   ✗ if (x >= UINT64_C(10000000000000000000))
91   { 91   {
MISUBC 92   ✗ return 20; 92   ✗ return 20;
93   } 93   }
MISUBC 94   ✗ return 19; 94   ✗ return 19;
95   } 95   }
MISUBC 96   ✗ return 18; 96   ✗ return 18;
97   } 97   }
MISUBC 98   ✗ return 17; 98   ✗ return 17;
99   } 99   }
MISUBC 100   ✗ else if (x >= UINT64_C(1000000000000000)) 100   ✗ else if (x >= UINT64_C(1000000000000000))
101   { 101   {
MISUBC 102   ✗ return 16; 102   ✗ return 16;
103   } 103   }
MISUBC 104   ✗ return 15; 104   ✗ return 15;
105   } 105   }
MISUBC 106   ✗ if (x >= UINT64_C(1000000000000)) 106   ✗ if (x >= UINT64_C(1000000000000))
107   { 107   {
MISUBC 108   ✗ if (x >= UINT64_C(10000000000000)) 108   ✗ if (x >= UINT64_C(10000000000000))
109   { 109   {
MISUBC 110   ✗ return 14; 110   ✗ return 14;
111   } 111   }
MISUBC 112   ✗ return 13; 112   ✗ return 13;
113   } 113   }
MISUBC 114   ✗ if (x >= UINT64_C(100000000000)) 114   ✗ if (x >= UINT64_C(100000000000))
115   { 115   {
MISUBC 116   ✗ return 12; 116   ✗ return 12;
117   } 117   }
MISUBC 118   ✗ return 11; 118   ✗ return 11;
119   } 119   }
MISUBC 120   ✗ else if (x >= UINT64_C(100000)) 120   ✗ else if (x >= UINT64_C(100000))
121   { 121   {
MISUBC 122   ✗ if (x >= UINT64_C(10000000)) 122   ✗ if (x >= UINT64_C(10000000))
123   { 123   {
MISUBC 124   ✗ if (x >= UINT64_C(100000000)) 124   ✗ if (x >= UINT64_C(100000000))
125   { 125   {
MISUBC 126   ✗ if (x >= UINT64_C(1000000000)) 126   ✗ if (x >= UINT64_C(1000000000))
127   { 127   {
MISUBC 128   ✗ return 10; 128   ✗ return 10;
129   } 129   }
MISUBC 130   ✗ return 9; 130   ✗ return 9;
131   } 131   }
MISUBC 132   ✗ return 8; 132   ✗ return 8;
133   } 133   }
MISUBC 134   ✗ if (x >= UINT64_C(1000000)) 134   ✗ if (x >= UINT64_C(1000000))
135   { 135   {
MISUBC 136   ✗ return 7; 136   ✗ return 7;
137   } 137   }
MISUBC 138   ✗ return 6; 138   ✗ return 6;
139   } 139   }
MISUBC 140   ✗ if (x >= UINT64_C(100)) 140   ✗ if (x >= UINT64_C(100))
141   { 141   {
MISUBC 142   ✗ if (x >= UINT64_C(1000)) 142   ✗ if (x >= UINT64_C(1000))
143   { 143   {
MISUBC 144   ✗ if (x >= UINT64_C(10000)) 144   ✗ if (x >= UINT64_C(10000))
145   { 145   {
MISUBC 146   ✗ return 5; 146   ✗ return 5;
147   } 147   }
MISUBC 148   ✗ return 4; 148   ✗ return 4;
149   } 149   }
MISUBC 150   ✗ return 3; 150   ✗ return 3;
151   } 151   }
MISUBC 152   ✗ if (x >= UINT64_C(10)) 152   ✗ if (x >= UINT64_C(10))
153   { 153   {
MISUBC 154   ✗ return 2; 154   ✗ return 2;
155   } 155   }
MISUBC 156   ✗ return 1; 156   ✗ return 1;
157   } 157   }
158   158  
159   #ifdef BOOST_HAS_INT128 159   #ifdef BOOST_HAS_INT128
160   static constexpr std::array<std::uint64_t, 20> powers_of_10 = 160   static constexpr std::array<std::uint64_t, 20> powers_of_10 =
161   {{ 161   {{
162   UINT64_C(1), UINT64_C(10), UINT64_C(100), UINT64_C(1000), UINT64_C(10000), UINT64_C(100000), UINT64_C(1000000), 162   UINT64_C(1), UINT64_C(10), UINT64_C(100), UINT64_C(1000), UINT64_C(10000), UINT64_C(100000), UINT64_C(1000000),
163   UINT64_C(10000000), UINT64_C(100000000), UINT64_C(1000000000), UINT64_C(10000000000), UINT64_C(100000000000), 163   UINT64_C(10000000), UINT64_C(100000000), UINT64_C(1000000000), UINT64_C(10000000000), UINT64_C(100000000000),
164   UINT64_C(1000000000000), UINT64_C(10000000000000), UINT64_C(100000000000000), UINT64_C(1000000000000000), 164   UINT64_C(1000000000000), UINT64_C(10000000000000), UINT64_C(100000000000000), UINT64_C(1000000000000000),
165   UINT64_C(10000000000000000), UINT64_C(100000000000000000), UINT64_C(1000000000000000000), UINT64_C(10000000000000000000) 165   UINT64_C(10000000000000000), UINT64_C(100000000000000000), UINT64_C(1000000000000000000), UINT64_C(10000000000000000000)
166   }}; 166   }};
167   167  
168   // Assume that if someone is using 128 bit ints they are favoring the top end of the range 168   // Assume that if someone is using 128 bit ints they are favoring the top end of the range
169   // Max value is 340,282,366,920,938,463,463,374,607,431,768,211,455 (39 digits) 169   // Max value is 340,282,366,920,938,463,463,374,607,431,768,211,455 (39 digits)
170   BOOST_JSON_CXX14_CONSTEXPR int num_digits(boost::uint128_type x) noexcept 170   BOOST_JSON_CXX14_CONSTEXPR int num_digits(boost::uint128_type x) noexcept
171   { 171   {
172   // There is not literal for boost::uint128_type so we need to calculate them using the max value of the 172   // There is not literal for boost::uint128_type so we need to calculate them using the max value of the
173   // std::uint64_t powers of 10 173   // std::uint64_t powers of 10
174   constexpr boost::uint128_type digits_39 = static_cast<boost::uint128_type>(UINT64_C(10000000000000000000)) * 174   constexpr boost::uint128_type digits_39 = static_cast<boost::uint128_type>(UINT64_C(10000000000000000000)) *
175   static_cast<boost::uint128_type>(UINT64_C(10000000000000000000)); 175   static_cast<boost::uint128_type>(UINT64_C(10000000000000000000));
176   176  
177   constexpr boost::uint128_type digits_38 = digits_39 / 10; 177   constexpr boost::uint128_type digits_38 = digits_39 / 10;
178   constexpr boost::uint128_type digits_37 = digits_38 / 10; 178   constexpr boost::uint128_type digits_37 = digits_38 / 10;
179   constexpr boost::uint128_type digits_36 = digits_37 / 10; 179   constexpr boost::uint128_type digits_36 = digits_37 / 10;
180   constexpr boost::uint128_type digits_35 = digits_36 / 10; 180   constexpr boost::uint128_type digits_35 = digits_36 / 10;
181   constexpr boost::uint128_type digits_34 = digits_35 / 10; 181   constexpr boost::uint128_type digits_34 = digits_35 / 10;
182   constexpr boost::uint128_type digits_33 = digits_34 / 10; 182   constexpr boost::uint128_type digits_33 = digits_34 / 10;
183   constexpr boost::uint128_type digits_32 = digits_33 / 10; 183   constexpr boost::uint128_type digits_32 = digits_33 / 10;
184   constexpr boost::uint128_type digits_31 = digits_32 / 10; 184   constexpr boost::uint128_type digits_31 = digits_32 / 10;
185   constexpr boost::uint128_type digits_30 = digits_31 / 10; 185   constexpr boost::uint128_type digits_30 = digits_31 / 10;
186   constexpr boost::uint128_type digits_29 = digits_30 / 10; 186   constexpr boost::uint128_type digits_29 = digits_30 / 10;
187   constexpr boost::uint128_type digits_28 = digits_29 / 10; 187   constexpr boost::uint128_type digits_28 = digits_29 / 10;
188   constexpr boost::uint128_type digits_27 = digits_28 / 10; 188   constexpr boost::uint128_type digits_27 = digits_28 / 10;
189   constexpr boost::uint128_type digits_26 = digits_27 / 10; 189   constexpr boost::uint128_type digits_26 = digits_27 / 10;
190   constexpr boost::uint128_type digits_25 = digits_26 / 10; 190   constexpr boost::uint128_type digits_25 = digits_26 / 10;
191   constexpr boost::uint128_type digits_24 = digits_25 / 10; 191   constexpr boost::uint128_type digits_24 = digits_25 / 10;
192   constexpr boost::uint128_type digits_23 = digits_24 / 10; 192   constexpr boost::uint128_type digits_23 = digits_24 / 10;
193   constexpr boost::uint128_type digits_22 = digits_23 / 10; 193   constexpr boost::uint128_type digits_22 = digits_23 / 10;
194   constexpr boost::uint128_type digits_21 = digits_22 / 10; 194   constexpr boost::uint128_type digits_21 = digits_22 / 10;
195   195  
196   return (x >= digits_39) ? 39 : 196   return (x >= digits_39) ? 39 :
197   (x >= digits_38) ? 38 : 197   (x >= digits_38) ? 38 :
198   (x >= digits_37) ? 37 : 198   (x >= digits_37) ? 37 :
199   (x >= digits_36) ? 36 : 199   (x >= digits_36) ? 36 :
200   (x >= digits_35) ? 35 : 200   (x >= digits_35) ? 35 :
201   (x >= digits_34) ? 34 : 201   (x >= digits_34) ? 34 :
202   (x >= digits_33) ? 33 : 202   (x >= digits_33) ? 33 :
203   (x >= digits_32) ? 32 : 203   (x >= digits_32) ? 32 :
204   (x >= digits_31) ? 31 : 204   (x >= digits_31) ? 31 :
205   (x >= digits_30) ? 30 : 205   (x >= digits_30) ? 30 :
206   (x >= digits_29) ? 29 : 206   (x >= digits_29) ? 29 :
207   (x >= digits_28) ? 28 : 207   (x >= digits_28) ? 28 :
208   (x >= digits_27) ? 27 : 208   (x >= digits_27) ? 27 :
209   (x >= digits_26) ? 26 : 209   (x >= digits_26) ? 26 :
210   (x >= digits_25) ? 25 : 210   (x >= digits_25) ? 25 :
211   (x >= digits_24) ? 24 : 211   (x >= digits_24) ? 24 :
212   (x >= digits_23) ? 23 : 212   (x >= digits_23) ? 23 :
213   (x >= digits_22) ? 22 : 213   (x >= digits_22) ? 22 :
214   (x >= digits_21) ? 21 : 214   (x >= digits_21) ? 21 :
215   (x >= powers_of_10[19]) ? 20 : 215   (x >= powers_of_10[19]) ? 20 :
216   (x >= powers_of_10[18]) ? 19 : 216   (x >= powers_of_10[18]) ? 19 :
217   (x >= powers_of_10[17]) ? 18 : 217   (x >= powers_of_10[17]) ? 18 :
218   (x >= powers_of_10[16]) ? 17 : 218   (x >= powers_of_10[16]) ? 17 :
219   (x >= powers_of_10[15]) ? 16 : 219   (x >= powers_of_10[15]) ? 16 :
220   (x >= powers_of_10[14]) ? 15 : 220   (x >= powers_of_10[14]) ? 15 :
221   (x >= powers_of_10[13]) ? 14 : 221   (x >= powers_of_10[13]) ? 14 :
222   (x >= powers_of_10[12]) ? 13 : 222   (x >= powers_of_10[12]) ? 13 :
223   (x >= powers_of_10[11]) ? 12 : 223   (x >= powers_of_10[11]) ? 12 :
224   (x >= powers_of_10[10]) ? 11 : 224   (x >= powers_of_10[10]) ? 11 :
225   (x >= powers_of_10[9]) ? 10 : 225   (x >= powers_of_10[9]) ? 10 :
226   (x >= powers_of_10[8]) ? 9 : 226   (x >= powers_of_10[8]) ? 9 :
227   (x >= powers_of_10[7]) ? 8 : 227   (x >= powers_of_10[7]) ? 8 :
228   (x >= powers_of_10[6]) ? 7 : 228   (x >= powers_of_10[6]) ? 7 :
229   (x >= powers_of_10[5]) ? 6 : 229   (x >= powers_of_10[5]) ? 6 :
230   (x >= powers_of_10[4]) ? 5 : 230   (x >= powers_of_10[4]) ? 5 :
231   (x >= powers_of_10[3]) ? 4 : 231   (x >= powers_of_10[3]) ? 4 :
232   (x >= powers_of_10[2]) ? 3 : 232   (x >= powers_of_10[2]) ? 3 :
233   (x >= powers_of_10[1]) ? 2 : 233   (x >= powers_of_10[1]) ? 2 :
234   (x >= powers_of_10[0]) ? 1 : 0; 234   (x >= powers_of_10[0]) ? 1 : 0;
235   } 235   }
236   #endif 236   #endif
237   237  
238   }}}}} // Namespace boost::json::detail::charconv::detail 238   }}}}} // Namespace boost::json::detail::charconv::detail
239   239  
240   #endif // BOOST_JSON_DETAIL_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP 240   #endif // BOOST_JSON_DETAIL_CHARCONV_DETAIL_INTEGER_SEARCH_TREES_HPP