aboutsummaryrefslogtreecommitdiff
path: root/libstdc++-v3/include/bits
diff options
context:
space:
mode:
Diffstat (limited to 'libstdc++-v3/include/bits')
-rw-r--r--libstdc++-v3/include/bits/hashtable.h146
-rw-r--r--libstdc++-v3/include/bits/ios_base.h8
-rw-r--r--libstdc++-v3/include/bits/parse_numbers.h339
-rw-r--r--libstdc++-v3/include/bits/regex.tcc2
-rw-r--r--libstdc++-v3/include/bits/regex_automaton.tcc4
-rw-r--r--libstdc++-v3/include/bits/regex_compiler.h43
-rw-r--r--libstdc++-v3/include/bits/regex_compiler.tcc36
-rw-r--r--libstdc++-v3/include/bits/regex_executor.h99
-rw-r--r--libstdc++-v3/include/bits/regex_executor.tcc168
-rw-r--r--libstdc++-v3/include/bits/regex_scanner.tcc11
-rw-r--r--libstdc++-v3/include/bits/uses_allocator.h31
11 files changed, 437 insertions, 450 deletions
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 22e17d29d7b..9b6394c4e49 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -316,14 +316,49 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
size_type _M_element_count;
_RehashPolicy _M_rehash_policy;
+ // A single bucket used when only need for 1 bucket. Especially
+ // interesting in move semantic to leave hashtable with only 1 buckets
+ // which is not allocated so that we can have those operations noexcept
+ // qualified.
+ // Note that we can't leave hashtable with 0 bucket without adding
+ // numerous checks in the code to avoid 0 modulus.
+ __bucket_type _M_single_bucket;
+
+ bool
+ _M_uses_single_bucket(__bucket_type* __bkts) const
+ { return __builtin_expect(_M_buckets == &_M_single_bucket, false); }
+
+ bool
+ _M_uses_single_bucket() const
+ { return _M_uses_single_bucket(_M_buckets); }
+
__hashtable_alloc&
_M_base_alloc() { return *this; }
- using __hashtable_alloc::_M_deallocate_buckets;
+ __bucket_type*
+ _M_allocate_buckets(size_type __n)
+ {
+ if (__builtin_expect(__n == 1, false))
+ {
+ _M_single_bucket = nullptr;
+ return &_M_single_bucket;
+ }
+
+ return __hashtable_alloc::_M_allocate_buckets(__n);
+ }
+
+ void
+ _M_deallocate_buckets(__bucket_type* __bkts, size_type __n)
+ {
+ if (_M_uses_single_bucket(__bkts))
+ return;
+
+ __hashtable_alloc::_M_deallocate_buckets(__bkts, __n);
+ }
void
_M_deallocate_buckets()
- { this->_M_deallocate_buckets(_M_buckets, _M_bucket_count); }
+ { _M_deallocate_buckets(_M_buckets, _M_bucket_count); }
// Gets bucket begin, deals with the fact that non-empty buckets contain
// their before begin node.
@@ -703,11 +738,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
size_type
erase(const key_type& __k)
- {
- if (__builtin_expect(_M_bucket_count == 0, false))
- return 0;
- return _M_erase(__unique_keys(), __k);
- }
+ { return _M_erase(__unique_keys(), __k); }
iterator
erase(const_iterator, const_iterator);
@@ -768,7 +799,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_rehash_policy()
{
_M_bucket_count = _M_rehash_policy._M_next_bkt(__bucket_hint);
- _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
}
template<typename _Key, typename _Value,
@@ -796,7 +827,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::max(_M_rehash_policy._M_bkt_for_elements(__nb_elems),
__bucket_hint));
- _M_buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
for (; __f != __l; ++__f)
@@ -833,9 +864,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
// Replacement allocator cannot free existing storage.
this->_M_deallocate_nodes(_M_begin());
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
- _M_reset();
+ _M_before_begin._M_nxt = nullptr;
+ _M_deallocate_buckets();
+ _M_buckets = nullptr;
std::__alloc_on_copy(__this_alloc, __that_alloc);
__hashtable_base::operator=(__ht);
_M_bucket_count = __ht._M_bucket_count;
@@ -867,7 +898,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (_M_bucket_count != __ht._M_bucket_count)
{
__former_buckets = _M_buckets;
- _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
+ _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
_M_bucket_count = __ht._M_bucket_count;
}
else
@@ -885,8 +916,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
[&__roan](const __node_type* __n)
{ return __roan(__n->_M_v()); });
if (__former_buckets)
- this->_M_deallocate_buckets(__former_buckets,
- __former_bucket_count);
+ _M_deallocate_buckets(__former_buckets, __former_bucket_count);
}
__catch(...)
{
@@ -917,7 +947,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__bucket_type* __buckets = nullptr;
if (!_M_buckets)
- _M_buckets = __buckets = this->_M_allocate_buckets(_M_bucket_count);
+ _M_buckets = __buckets = _M_allocate_buckets(_M_bucket_count);
__try
{
@@ -964,8 +994,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_reset() noexcept
{
_M_rehash_policy._M_reset();
- _M_bucket_count = 0;
- _M_buckets = nullptr;
+ _M_bucket_count = 1;
+ _M_single_bucket = nullptr;
+ _M_buckets = &_M_single_bucket;
_M_before_begin._M_nxt = nullptr;
_M_element_count = 0;
}
@@ -980,12 +1011,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_move_assign(_Hashtable&& __ht, std::true_type)
{
this->_M_deallocate_nodes(_M_begin());
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
-
+ _M_deallocate_buckets();
__hashtable_base::operator=(std::move(__ht));
_M_rehash_policy = __ht._M_rehash_policy;
- _M_buckets = __ht._M_buckets;
+ if (!__ht._M_uses_single_bucket())
+ _M_buckets = __ht._M_buckets;
+ else
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
_M_bucket_count = __ht._M_bucket_count;
_M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
_M_element_count = __ht._M_element_count;
@@ -1019,7 +1054,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (_M_bucket_count != __ht._M_bucket_count)
{
__former_buckets = _M_buckets;
- _M_buckets = this->_M_allocate_buckets(__ht._M_bucket_count);
+ _M_buckets = _M_allocate_buckets(__ht._M_bucket_count);
_M_bucket_count = __ht._M_bucket_count;
}
else
@@ -1093,10 +1128,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_element_count(__ht._M_element_count),
_M_rehash_policy(__ht._M_rehash_policy)
{
+ // Update, if necessary, buckets if __ht is using its single bucket.
+ if (__ht._M_uses_single_bucket())
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
+
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
__ht._M_reset();
}
@@ -1139,7 +1182,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
if (__ht._M_node_allocator() == this->_M_node_allocator())
{
- _M_buckets = __ht._M_buckets;
+ if (__ht._M_uses_single_bucket())
+ {
+ _M_buckets = &_M_single_bucket;
+ _M_single_bucket = __ht._M_single_bucket;
+ }
+ else
+ _M_buckets = __ht._M_buckets;
+
_M_before_begin._M_nxt = __ht._M_before_begin._M_nxt;
// Update, if necessary, bucket pointing to before begin that hasn't
// moved.
@@ -1189,15 +1239,34 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::__alloc_on_swap(this->_M_node_allocator(), __x._M_node_allocator());
std::swap(_M_rehash_policy, __x._M_rehash_policy);
- std::swap(_M_buckets, __x._M_buckets);
+
+ // Deal properly with potentially moved instances.
+ if (this->_M_uses_single_bucket())
+ {
+ if (!__x._M_uses_single_bucket())
+ {
+ _M_buckets = __x._M_buckets;
+ __x._M_buckets = &__x._M_single_bucket;
+ }
+ }
+ else if (__x._M_uses_single_bucket())
+ {
+ __x._M_buckets = _M_buckets;
+ _M_buckets = &_M_single_bucket;
+ }
+ else
+ std::swap(_M_buckets, __x._M_buckets);
+
std::swap(_M_bucket_count, __x._M_bucket_count);
std::swap(_M_before_begin._M_nxt, __x._M_before_begin._M_nxt);
std::swap(_M_element_count, __x._M_element_count);
+ std::swap(_M_single_bucket, __x._M_single_bucket);
// Fix buckets containing the _M_before_begin pointers that can't be
// swapped.
if (_M_begin())
_M_buckets[_M_bucket_index(_M_begin())] = &_M_before_begin;
+
if (__x._M_begin())
__x._M_buckets[__x._M_bucket_index(__x._M_begin())]
= &__x._M_before_begin;
@@ -1230,9 +1299,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
find(const key_type& __k)
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return end();
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1250,9 +1316,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
find(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return end();
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1270,9 +1333,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
count(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return 0;
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_bucket_begin(__n);
@@ -1287,7 +1347,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else if (__result)
// All equivalent values are next to each other, if we
// found a non-equivalent value after an equivalent one it
- // means that we won't find any more equivalent values.
+ // means that we won't find any new equivalent value.
break;
if (!__p->_M_nxt || _M_bucket_index(__p->_M_next()) != __n)
break;
@@ -1311,9 +1371,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
equal_range(const key_type& __k)
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return std::make_pair(end(), end());
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1347,9 +1404,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
equal_range(const key_type& __k) const
{
- if (__builtin_expect(_M_bucket_count == 0, false))
- return std::make_pair(end(), end());
-
__hash_code __code = this->_M_hash_code(__k);
std::size_t __n = _M_bucket_index(__k, __code);
__node_type* __p = _M_find_node(__n, __k, __code);
@@ -1944,7 +1998,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_rehash_aux(size_type __n, std::true_type)
{
- __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
+ __bucket_type* __new_buckets = _M_allocate_buckets(__n);
__node_type* __p = _M_begin();
_M_before_begin._M_nxt = nullptr;
std::size_t __bbegin_bkt = 0;
@@ -1969,8 +2023,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__p = __next;
}
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
+ _M_deallocate_buckets();
_M_bucket_count = __n;
_M_buckets = __new_buckets;
}
@@ -1986,7 +2039,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_H1, _H2, _Hash, _RehashPolicy, _Traits>::
_M_rehash_aux(size_type __n, std::false_type)
{
- __bucket_type* __new_buckets = this->_M_allocate_buckets(__n);
+ __bucket_type* __new_buckets = _M_allocate_buckets(__n);
__node_type* __p = _M_begin();
_M_before_begin._M_nxt = nullptr;
@@ -2060,8 +2113,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__new_buckets[__next_bkt] = __prev_p;
}
- if (__builtin_expect(_M_bucket_count != 0, true))
- _M_deallocate_buckets();
+ _M_deallocate_buckets();
_M_bucket_count = __n;
_M_buckets = __new_buckets;
}
diff --git a/libstdc++-v3/include/bits/ios_base.h b/libstdc++-v3/include/bits/ios_base.h
index ae856de7b45..59c506696f5 100644
--- a/libstdc++-v3/include/bits/ios_base.h
+++ b/libstdc++-v3/include/bits/ios_base.h
@@ -780,6 +780,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
protected:
ios_base() throw ();
+#if __cplusplus < 201103L
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 50. Copy constructor and assignment operator of ios_base
private:
@@ -787,6 +788,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
ios_base&
operator=(const ios_base&);
+#else
+ public:
+ ios_base(const ios_base&) = delete;
+
+ ios_base&
+ operator=(const ios_base&) = delete;
+#endif
};
// [27.4.5.1] fmtflags manipulators
diff --git a/libstdc++-v3/include/bits/parse_numbers.h b/libstdc++-v3/include/bits/parse_numbers.h
index 91a127c4ebe..a29d1272255 100644
--- a/libstdc++-v3/include/bits/parse_numbers.h
+++ b/libstdc++-v3/include/bits/parse_numbers.h
@@ -27,8 +27,8 @@
* Do not attempt to use it directly. @headername{chrono}
*/
-#ifndef _PARSE_NUMBERS_H
-#define _PARSE_NUMBERS_H 1
+#ifndef _GLIBCXX_PARSE_NUMBERS_H
+#define _GLIBCXX_PARSE_NUMBERS_H 1
#pragma GCC system_header
@@ -36,289 +36,182 @@
#if __cplusplus > 201103L
+#include <limits>
+
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
-namespace __parse_int {
-
+namespace __parse_int
+{
template<unsigned _Base, char _Dig>
struct _Digit;
template<unsigned _Base>
- struct _Digit<_Base, '0'>
+ struct _Digit<_Base, '0'> : integral_constant<unsigned, 0>
{
- static constexpr bool valid{true};
- static constexpr unsigned value{0};
+ using __valid = true_type;
};
template<unsigned _Base>
- struct _Digit<_Base, '1'>
+ struct _Digit<_Base, '1'> : integral_constant<unsigned, 1>
{
- static constexpr bool valid{true};
- static constexpr unsigned value{1};
+ using __valid = true_type;
};
- template<unsigned _Base>
- struct _Digit<_Base, '2'>
+ template<unsigned _Base, unsigned _Val>
+ struct _Digit_impl : integral_constant<unsigned, _Val>
{
- static_assert(_Base > 2, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{2};
+ static_assert(_Base > _Val, "invalid digit");
+ using __valid = true_type;
};
template<unsigned _Base>
- struct _Digit<_Base, '3'>
- {
- static_assert(_Base > 3, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{3};
- };
+ struct _Digit<_Base, '2'> : _Digit_impl<_Base, 2>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, '4'>
- {
- static_assert(_Base > 4, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{4};
- };
+ struct _Digit<_Base, '3'> : _Digit_impl<_Base, 3>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, '5'>
- {
- static_assert(_Base > 5, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{5};
- };
+ struct _Digit<_Base, '4'> : _Digit_impl<_Base, 4>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, '6'>
- {
- static_assert(_Base > 6, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{6};
- };
+ struct _Digit<_Base, '5'> : _Digit_impl<_Base, 5>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, '7'>
- {
- static_assert(_Base > 7, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{7};
- };
+ struct _Digit<_Base, '6'> : _Digit_impl<_Base, 6>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, '8'>
- {
- static_assert(_Base > 8, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{8};
- };
+ struct _Digit<_Base, '7'> : _Digit_impl<_Base, 7>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, '9'>
- {
- static_assert(_Base > 9, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{9};
- };
+ struct _Digit<_Base, '8'> : _Digit_impl<_Base, 8>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'a'>
- {
- static_assert(_Base > 0xa, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xa};
- };
+ struct _Digit<_Base, '9'> : _Digit_impl<_Base, 9>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'A'>
- {
- static_assert(_Base > 0xa, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xa};
- };
+ struct _Digit<_Base, 'a'> : _Digit_impl<_Base, 0xa>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'b'>
- {
- static_assert(_Base > 0xb, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xb};
- };
+ struct _Digit<_Base, 'A'> : _Digit_impl<_Base, 0xa>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'B'>
- {
- static_assert(_Base > 0xb, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xb};
- };
+ struct _Digit<_Base, 'b'> : _Digit_impl<_Base, 0xb>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'c'>
- {
- static_assert(_Base > 0xc, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xc};
- };
+ struct _Digit<_Base, 'B'> : _Digit_impl<_Base, 0xb>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'C'>
- {
- static_assert(_Base > 0xc, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xc};
- };
+ struct _Digit<_Base, 'c'> : _Digit_impl<_Base, 0xc>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'd'>
- {
- static_assert(_Base > 0xd, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xd};
- };
+ struct _Digit<_Base, 'C'> : _Digit_impl<_Base, 0xc>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'D'>
- {
- static_assert(_Base > 0xd, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xd};
- };
+ struct _Digit<_Base, 'd'> : _Digit_impl<_Base, 0xd>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'e'>
- {
- static_assert(_Base > 0xe, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xe};
- };
+ struct _Digit<_Base, 'D'> : _Digit_impl<_Base, 0xd>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'E'>
- {
- static_assert(_Base > 0xe, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xe};
- };
+ struct _Digit<_Base, 'e'> : _Digit_impl<_Base, 0xe>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'f'>
- {
- static_assert(_Base > 0xf, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xf};
- };
+ struct _Digit<_Base, 'E'> : _Digit_impl<_Base, 0xe>
+ { };
template<unsigned _Base>
- struct _Digit<_Base, 'F'>
- {
- static_assert(_Base > 0xf, "invalid digit");
- static constexpr bool valid{true};
- static constexpr unsigned value{0xf};
- };
+ struct _Digit<_Base, 'f'> : _Digit_impl<_Base, 0xf>
+ { };
- // Digit separator
template<unsigned _Base>
- struct _Digit<_Base, '\''>
- {
- static constexpr bool valid{false};
- static constexpr unsigned value{0};
- };
-
-
-//------------------------------------------------------------------------------
-
- template<unsigned _Base, char _Dig, char... _Digs>
- struct _Digits_help
- {
- static constexpr unsigned
- value{_Digit<_Base, _Dig>::valid ?
- 1U + _Digits_help<_Base, _Digs...>::value :
- _Digits_help<_Base, _Digs...>::value};
- };
-
- template<unsigned _Base, char _Dig>
- struct _Digits_help<_Base, _Dig>
- {
- static constexpr unsigned value{_Digit<_Base, _Dig>::valid ? 1U : 0U};
- };
-
- template<unsigned _Base, char... _Digs>
- struct _Digits
- {
- static constexpr unsigned value{_Digits_help<_Base, _Digs...>::value};
- };
+ struct _Digit<_Base, 'F'> : _Digit_impl<_Base, 0xf>
+ { };
+ // Digit separator
template<unsigned _Base>
- struct _Digits<_Base>
+ struct _Digit<_Base, '\''> : integral_constant<unsigned, 0>
{
- static constexpr unsigned value{0U};
+ using __valid = false_type;
};
//------------------------------------------------------------------------------
+ template<unsigned long long _Val>
+ using __ull_constant = integral_constant<unsigned long long, _Val>;
+
template<unsigned _Base, char _Dig, char... _Digs>
struct _Power_help
{
- static constexpr unsigned
- value{_Digit<_Base, _Dig>::valid ?
- _Base * _Power_help<_Base, _Digs...>::value :
- _Power_help<_Base, _Digs...>::value};
+ using __next = typename _Power_help<_Base, _Digs...>::type;
+ using __valid_digit = typename _Digit<_Base, _Dig>::__valid;
+ using type
+ = __ull_constant<__next::value * (__valid_digit{} ? _Base : 1ULL)>;
};
template<unsigned _Base, char _Dig>
struct _Power_help<_Base, _Dig>
{
- static constexpr unsigned value{_Digit<_Base, _Dig>::valid ? 1U : 0U};
+ using __valid_digit = typename _Digit<_Base, _Dig>::__valid;
+ using type = __ull_constant<__valid_digit::value>;
};
template<unsigned _Base, char... _Digs>
- struct _Power
- {
- static constexpr unsigned value{_Power_help<_Base, _Digs...>::value};
- };
+ struct _Power : _Power_help<_Base, _Digs...>::type
+ { };
template<unsigned _Base>
- struct _Power<_Base>
- {
- static constexpr unsigned value{0U};
- };
+ struct _Power<_Base> : __ull_constant<0>
+ { };
//------------------------------------------------------------------------------
- template<unsigned _Base, unsigned _Pow, char _Dig, char... _Digs>
+ template<unsigned _Base, unsigned long long _Pow, char _Dig, char... _Digs>
struct _Number_help
{
- static constexpr unsigned
- value{_Digit<_Base, _Dig>::valid ?
- _Pow * _Digit<_Base, _Dig>::value
- + _Number_help<_Base, _Pow / _Base, _Digs...>::value :
- _Number_help<_Base, _Pow, _Digs...>::value};
+ using __digit = _Digit<_Base, _Dig>;
+ using __valid_digit = typename __digit::__valid;
+ using __next = _Number_help<_Base,
+ _Pow / (_Base * __valid_digit::value),
+ _Digs...>;
+ using type = __ull_constant<_Pow * __digit::value + __next::type::value>;
+ static_assert((type::value / _Pow) == __digit::value, "overflow");
};
- template<unsigned _Base, unsigned _Pow, char _Dig>
+ template<unsigned _Base, unsigned long long _Pow, char _Dig>
struct _Number_help<_Base, _Pow, _Dig>
{
//static_assert(_Pow == 1U, "power should be one");
- static constexpr unsigned
- value{_Digit<_Base, _Dig>::valid ? _Digit<_Base, _Dig>::value : 0U};
+ using type = __ull_constant<_Digit<_Base, _Dig>::value>;
};
template<unsigned _Base, char... _Digs>
struct _Number
- {
- static constexpr unsigned
- value{_Number_help<_Base, _Power<_Base, _Digs...>::value,
- _Digs...>::value};
- };
+ : _Number_help<_Base, _Power<_Base, _Digs...>::value, _Digs...>::type
+ { };
template<unsigned _Base>
struct _Number<_Base>
- {
- static constexpr unsigned value{0U};
- };
+ : __ull_constant<0>
+ { };
//------------------------------------------------------------------------------
// This _Parse_int is the same 'level' as the old _Base_dispatch.
@@ -328,84 +221,62 @@ namespace __parse_int {
template<char... _Digs>
struct _Parse_int<'0', 'b', _Digs...>
- {
- static constexpr unsigned long long
- value{_Number<2U, _Digs...>::value};
- };
+ : _Number<2U, _Digs...>::type
+ { };
template<char... _Digs>
struct _Parse_int<'0', 'B', _Digs...>
- {
- static constexpr unsigned long long
- value{_Number<2U, _Digs...>::value};
- };
+ : _Number<2U, _Digs...>::type
+ { };
template<char... _Digs>
struct _Parse_int<'0', 'x', _Digs...>
- {
- static constexpr unsigned long long
- value{_Number<16U, _Digs...>::value};
- };
+ : _Number<16U, _Digs...>::type
+ { };
template<char... _Digs>
struct _Parse_int<'0', 'X', _Digs...>
- {
- static constexpr unsigned long long
- value{_Number<16U, _Digs...>::value};
- };
+ : _Number<16U, _Digs...>::type
+ { };
template<char... _Digs>
struct _Parse_int<'0', _Digs...>
- {
- static constexpr unsigned long long
- value{_Number<8U, _Digs...>::value};
- };
+ : _Number<8U, _Digs...>::type
+ { };
template<char... _Digs>
struct _Parse_int
- {
- static constexpr unsigned long long
- value{_Number<10U, _Digs...>::value};
- };
+ : _Number<10U, _Digs...>::type
+ { };
} // namespace __parse_int
-namespace __select_int {
-
+namespace __select_int
+{
template<unsigned long long _Val, typename... _Ints>
struct _Select_int_base;
template<unsigned long long _Val, typename _IntType, typename... _Ints>
struct _Select_int_base<_Val, _IntType, _Ints...>
- : integral_constant
- <
- typename conditional
- <
- _Val <= static_cast<unsigned long long>
- (std::numeric_limits<_IntType>::max()),
- _IntType,
- typename _Select_int_base<_Val, _Ints...>::value_type
- >::type,
- _Val
- >
+ : conditional_t<(_Val <= std::numeric_limits<_IntType>::max()),
+ integral_constant<_IntType, _Val>,
+ _Select_int_base<_Val, _Ints...>>
{ };
template<unsigned long long _Val>
- struct _Select_int_base<_Val> : integral_constant<unsigned long long, _Val>
+ struct _Select_int_base<_Val>
{ };
template<char... _Digs>
- struct _Select_int
- : _Select_int_base<
+ using _Select_int = typename _Select_int_base<
__parse_int::_Parse_int<_Digs...>::value,
unsigned char,
unsigned short,
unsigned int,
unsigned long,
unsigned long long
- >
- { };
+ >::type;
} // namespace __select_int
@@ -414,4 +285,4 @@ _GLIBCXX_END_NAMESPACE_VERSION
#endif // __cplusplus > 201103L
-#endif // _PARSE_NUMBERS_H
+#endif // _GLIBCXX_PARSE_NUMBERS_H
diff --git a/libstdc++-v3/include/bits/regex.tcc b/libstdc++-v3/include/bits/regex.tcc
index 0d737a0b74b..a81f51750dc 100644
--- a/libstdc++-v3/include/bits/regex.tcc
+++ b/libstdc++-v3/include/bits/regex.tcc
@@ -32,7 +32,7 @@
// If _GLIBCXX_REGEX_USE_THOMPSON_NFA is defined, the thompson NFA
// algorithm will be used. This algorithm is not enabled by default,
// and cannot be used if the regex contains back-references, but has better
-// (polynomial instead of exponential) worst case performace.
+// (polynomial instead of exponential) worst case performance.
// See __regex_algo_impl below.
namespace std _GLIBCXX_VISIBILITY(default)
diff --git a/libstdc++-v3/include/bits/regex_automaton.tcc b/libstdc++-v3/include/bits/regex_automaton.tcc
index e0ac3f94ceb..1c6cfdd1b9f 100644
--- a/libstdc++-v3/include/bits/regex_automaton.tcc
+++ b/libstdc++-v3/include/bits/regex_automaton.tcc
@@ -35,7 +35,7 @@ namespace __detail
_GLIBCXX_BEGIN_NAMESPACE_VERSION
#ifdef _GLIBCXX_DEBUG
- std::ostream&
+ inline std::ostream&
_State_base::_M_print(std::ostream& ostr) const
{
switch (_M_opcode)
@@ -67,7 +67,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
// Prints graphviz dot commands for state.
- std::ostream&
+ inline std::ostream&
_State_base::_M_dot(std::ostream& __ostr, _StateIdT __id) const
{
switch (_M_opcode)
diff --git a/libstdc++-v3/include/bits/regex_compiler.h b/libstdc++-v3/include/bits/regex_compiler.h
index d7e21624e37..ca116de53af 100644
--- a/libstdc++-v3/include/bits/regex_compiler.h
+++ b/libstdc++-v3/include/bits/regex_compiler.h
@@ -43,7 +43,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
struct _BracketMatcher;
/**
- * @brief Builds an NFA from an input iterator interval.
+ * @brief Builds an NFA from an input iterator range.
*
* The %_TraitsT type should fulfill requirements [28.3].
*/
@@ -329,7 +329,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
operator()(_CharT __ch) const
{
_GLIBCXX_DEBUG_ASSERT(_M_is_ready);
- return _M_apply(__ch, _IsChar());
+ return _M_apply(__ch, _UseCache());
}
void
@@ -369,15 +369,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
#endif
}
+ // __neg should be true for \D, \S and \W only.
void
- _M_add_character_class(const _StringT& __s)
+ _M_add_character_class(const _StringT& __s, bool __neg)
{
auto __mask = _M_traits.lookup_classname(__s.data(),
__s.data() + __s.size(),
__icase);
if (__mask == 0)
__throw_regex_error(regex_constants::error_ctype);
- _M_class_set |= __mask;
+ if (!__neg)
+ _M_class_set |= __mask;
+ else
+ _M_neg_class_set.push_back(__mask);
#ifdef _GLIBCXX_DEBUG
_M_is_ready = false;
#endif
@@ -387,7 +391,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_make_range(_CharT __l, _CharT __r)
{
_M_range_set.push_back(make_pair(_M_translator._M_transform(__l),
- _M_translator._M_transform(__r)));
+ _M_translator._M_transform(__r)));
#ifdef _GLIBCXX_DEBUG
_M_is_ready = false;
#endif
@@ -396,21 +400,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_M_ready()
{
- _M_make_cache(_IsChar());
+ std::sort(_M_char_set.begin(), _M_char_set.end());
+ auto __end = std::unique(_M_char_set.begin(), _M_char_set.end());
+ _M_char_set.erase(__end, _M_char_set.end());
+ _M_make_cache(_UseCache());
#ifdef _GLIBCXX_DEBUG
_M_is_ready = true;
#endif
}
private:
- typedef typename is_same<_CharT, char>::type _IsChar;
+ // Currently we only use the cache for char
+ typedef typename std::is_same<_CharT, char>::type _UseCache;
+
+ static constexpr size_t
+ _S_cache_size() { return 1ul << (sizeof(_CharT) * __CHAR_BIT__); }
+
struct _Dummy { };
- typedef typename conditional<_IsChar::value,
- std::bitset<1 << (8 * sizeof(_CharT))>,
- _Dummy>::type _CacheT;
- typedef typename make_unsigned<_CharT>::type _UnsignedCharT;
+ typedef typename std::conditional<_UseCache::value,
+ std::bitset<_S_cache_size()>,
+ _Dummy>::type _CacheT;
+ typedef typename std::make_unsigned<_CharT>::type _UnsignedCharT;
- private:
bool
_M_apply(_CharT __ch, false_type) const;
@@ -421,9 +432,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
void
_M_make_cache(true_type)
{
- for (size_t __i = 0; __i < _M_cache.size(); __i++)
- _M_cache[static_cast<_UnsignedCharT>(__i)] =
- _M_apply(__i, false_type());
+ for (unsigned __i = 0; __i < _M_cache.size(); __i++)
+ _M_cache[__i] = _M_apply(static_cast<_CharT>(__i), false_type());
}
void
@@ -431,14 +441,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{ }
private:
- _CacheT _M_cache;
std::vector<_CharT> _M_char_set;
std::vector<_StringT> _M_equiv_set;
std::vector<pair<_StrTransT, _StrTransT>> _M_range_set;
+ std::vector<_CharClassT> _M_neg_class_set;
_CharClassT _M_class_set;
_TransT _M_translator;
const _TraitsT& _M_traits;
bool _M_is_non_matching;
+ _CacheT _M_cache;
#ifdef _GLIBCXX_DEBUG
bool _M_is_ready;
#endif
diff --git a/libstdc++-v3/include/bits/regex_compiler.tcc b/libstdc++-v3/include/bits/regex_compiler.tcc
index 3cf9e457ccd..0df10cc1a8b 100644
--- a/libstdc++-v3/include/bits/regex_compiler.tcc
+++ b/libstdc++-v3/include/bits/regex_compiler.tcc
@@ -37,9 +37,9 @@
// When compiling, states are *chained* instead of tree- or graph-constructed.
// It's more like structured programs: there's if statement and loop statement.
//
-// For alternative structure(say "a|b"), aka "if statement", two branchs should
-// be constructed. However, these two shall merge to an "end_tag" at the end of
-// this operator:
+// For alternative structure (say "a|b"), aka "if statement", two branches
+// should be constructed. However, these two shall merge to an "end_tag" at
+// the end of this operator:
//
// branch1
// / \
@@ -151,7 +151,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else if (_M_match_token(_ScannerT::_S_token_line_end))
_M_stack.push(_StateSeqT(_M_nfa, _M_nfa._M_insert_line_end()));
else if (_M_match_token(_ScannerT::_S_token_word_bound))
- // _M_value[0] == 'n' means it's negtive, say "not word boundary".
+ // _M_value[0] == 'n' means it's negative, say "not word boundary".
_M_stack.push(_StateSeqT(_M_nfa, _M_nfa.
_M_insert_word_bound(_M_value[0] == 'n')));
else if (_M_match_token(_ScannerT::_S_token_subexpr_lookahead_begin))
@@ -256,7 +256,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto __end = _M_nfa._M_insert_dummy();
// _M_alt is the "match more" branch, and _M_next is the
// "match less" one. Switch _M_alt and _M_next of all created
- // nodes. This is a hacking but IMO works well.
+ // nodes. This is a hack but IMO works well.
std::stack<_StateIdT> __stack;
for (long __i = 0; __i < __n; ++__i)
{
@@ -397,7 +397,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_GLIBCXX_DEBUG_ASSERT(_M_value.size() == 1);
_BracketMatcher<_TraitsT, __icase, __collate> __matcher
(_M_ctype.is(_CtypeT::upper, _M_value[0]), _M_traits);
- __matcher._M_add_character_class(_M_value);
+ __matcher._M_add_character_class(_M_value, false);
__matcher._M_ready();
_M_stack.push(_StateSeqT(_M_nfa,
_M_nfa._M_insert_matcher(std::move(__matcher))));
@@ -428,7 +428,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else if (_M_match_token(_ScannerT::_S_token_equiv_class_name))
__matcher._M_add_equivalence_class(_M_value);
else if (_M_match_token(_ScannerT::_S_token_char_class_name))
- __matcher._M_add_character_class(_M_value);
+ __matcher._M_add_character_class(_M_value, false);
else if (_M_try_char()) // [a
{
auto __ch = _M_value[0];
@@ -451,6 +451,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
__matcher._M_add_char(__ch);
}
+ else if (_M_match_token(_ScannerT::_S_token_quoted_class))
+ __matcher._M_add_character_class(_M_value,
+ _M_ctype.is(_CtypeT::upper,
+ _M_value[0]));
else
__throw_regex_error(regex_constants::error_brack);
}
@@ -507,12 +511,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_BracketMatcher<_TraitsT, __icase, __collate>::
_M_apply(_CharT __ch, false_type) const
{
- bool __ret = false;
- if (std::find(_M_char_set.begin(), _M_char_set.end(),
- _M_translator._M_translate(__ch))
- != _M_char_set.end())
- __ret = true;
- else
+ bool __ret = std::binary_search(_M_char_set.begin(), _M_char_set.end(),
+ _M_translator._M_translate(__ch));
+ if (!__ret)
{
auto __s = _M_translator._M_transform(__ch);
for (auto& __it : _M_range_set)
@@ -527,6 +528,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_traits.transform_primary(&__ch, &__ch+1))
!= _M_equiv_set.end())
__ret = true;
+ else
+ {
+ for (auto& __it : _M_neg_class_set)
+ if (!_M_traits.isctype(__ch, __it))
+ {
+ __ret = true;
+ break;
+ }
+ }
}
if (_M_is_non_matching)
return !__ret;
diff --git a/libstdc++-v3/include/bits/regex_executor.h b/libstdc++-v3/include/bits/regex_executor.h
index c110b88a3f4..1991c0007a1 100644
--- a/libstdc++-v3/include/bits/regex_executor.h
+++ b/libstdc++-v3/include/bits/regex_executor.h
@@ -42,8 +42,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
*/
/**
- * @brief Takes a regex and an input string in and
- * do the matching.
+ * @brief Takes a regex and an input string and does the matching.
*
* The %_Executor class has two modes: DFS mode and BFS mode, controlled
* by the template parameter %__dfs_mode.
@@ -52,6 +51,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool __dfs_mode>
class _Executor
{
+ using __search_mode = integral_constant<bool, __dfs_mode>;
+ using __dfs = true_type;
+ using __bfs = false_type;
+
+ enum class _Match_mode : unsigned char { _Exact, _Prefix };
+
public:
typedef typename iterator_traits<_BiIter>::value_type _CharT;
typedef basic_regex<_CharT, _TraitsT> _RegexT;
@@ -71,24 +76,21 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_re(__re),
_M_nfa(*__re._M_automaton),
_M_results(__results),
- _M_match_queue(__dfs_mode ? nullptr
- : new vector<pair<_StateIdT, _ResultsVec>>()),
_M_rep_count(_M_nfa.size()),
- _M_visited(__dfs_mode ? nullptr : new vector<bool>(_M_nfa.size())),
+ _M_states(_M_nfa._M_start(), _M_nfa.size()),
_M_flags((__flags & regex_constants::match_prev_avail)
? (__flags
& ~regex_constants::match_not_bol
& ~regex_constants::match_not_bow)
- : __flags),
- _M_start_state(_M_nfa._M_start())
+ : __flags)
{ }
- // Set matched when string exactly match the pattern.
+ // Set matched when string exactly matches the pattern.
bool
_M_match()
{
_M_current = _M_begin;
- return _M_main<true>();
+ return _M_main(_Match_mode::_Exact);
}
// Set matched when some prefix of the string matches the pattern.
@@ -96,24 +98,28 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_search_from_first()
{
_M_current = _M_begin;
- return _M_main<false>();
+ return _M_main(_Match_mode::_Prefix);
}
bool
_M_search();
private:
- template<bool __match_mode>
- void
- _M_rep_once_more(_StateIdT);
+ void
+ _M_rep_once_more(_Match_mode __match_mode, _StateIdT);
- template<bool __match_mode>
- void
- _M_dfs(_StateIdT __start);
+ void
+ _M_dfs(_Match_mode __match_mode, _StateIdT __start);
- template<bool __match_mode>
- bool
- _M_main();
+ bool
+ _M_main(_Match_mode __match_mode)
+ { return _M_main_dispatch(__match_mode, __search_mode{}); }
+
+ bool
+ _M_main_dispatch(_Match_mode __match_mode, __dfs);
+
+ bool
+ _M_main_dispatch(_Match_mode __match_mode, __bfs);
bool
_M_is_word(_CharT __ch) const
@@ -144,6 +150,53 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool
_M_lookahead(_State<_TraitsT> __state);
+ // Holds additional information used in BFS-mode.
+ template<typename _SearchMode, typename _ResultsVec>
+ struct _State_info;
+
+ template<typename _ResultsVec>
+ struct _State_info<__bfs, _ResultsVec>
+ {
+ explicit
+ _State_info(_StateIdT __start, size_t __n)
+ : _M_start(__start), _M_visited_states(new bool[__n]())
+ { }
+
+ bool _M_visited(_StateIdT __i)
+ {
+ if (_M_visited_states[__i])
+ return true;
+ _M_visited_states[__i] = true;
+ return false;
+ }
+
+ void _M_queue(_StateIdT __i, const _ResultsVec& __res)
+ { _M_match_queue.emplace_back(__i, __res); }
+
+ // Saves states that need to be considered for the next character.
+ vector<pair<_StateIdT, _ResultsVec>> _M_match_queue;
+ // Indicates which states are already visited.
+ unique_ptr<bool[]> _M_visited_states;
+ // To record current solution.
+ _StateIdT _M_start;
+ };
+
+ template<typename _ResultsVec>
+ struct _State_info<__dfs, _ResultsVec>
+ {
+ explicit
+ _State_info(_StateIdT __start, size_t) : _M_start(__start)
+ { }
+
+ // Dummy implementations for DFS mode.
+ bool _M_visited(_StateIdT) const { return false; }
+ void _M_queue(_StateIdT, const _ResultsVec&) { }
+
+ // To record current solution.
+ _StateIdT _M_start;
+ };
+
+
public:
_ResultsVec _M_cur_results;
_BiIter _M_current;
@@ -152,15 +205,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const _RegexT& _M_re;
const _NFAT& _M_nfa;
_ResultsVec& _M_results;
- // Used in BFS, saving states that need to be considered for the next
- // character.
- unique_ptr<vector<pair<_StateIdT, _ResultsVec>>> _M_match_queue;
- // Used in BFS, indicating that which state is already visited.
vector<pair<_BiIter, int>> _M_rep_count;
- unique_ptr<vector<bool>> _M_visited;
+ _State_info<__search_mode, _ResultsVec> _M_states;
_FlagT _M_flags;
- // To record current solution.
- _StateIdT _M_start_state;
// Do we have a solution so far?
bool _M_has_sol;
};
diff --git a/libstdc++-v3/include/bits/regex_executor.tcc b/libstdc++-v3/include/bits/regex_executor.tcc
index 7f8993382c8..aefa8f47137 100644
--- a/libstdc++-v3/include/bits/regex_executor.tcc
+++ b/libstdc++-v3/include/bits/regex_executor.tcc
@@ -35,7 +35,7 @@ namespace __detail
_GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _BiIter, typename _Alloc, typename _TraitsT,
- bool __dfs_mode>
+ bool __dfs_mode>
bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
_M_search()
{
@@ -45,7 +45,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
do
{
_M_current = __cur;
- if (_M_main<false>())
+ if (_M_main(_Match_mode::_Prefix))
return true;
}
// Continue when __cur == _M_end
@@ -53,8 +53,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return false;
}
- // This function operates in different modes, DFS mode or BFS mode, indicated
- // by template parameter __dfs_mode. See _M_main for details.
+ // The _M_main function operates in different modes, DFS mode or BFS mode,
+ // indicated by template parameter __dfs_mode, and dispatches to one of the
+ // _M_main_dispatch overloads.
//
// ------------------------------------------------------------
//
@@ -62,12 +63,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
//
// It applies a Depth-First-Search (aka backtracking) on given NFA and input
// string.
- // At the very beginning the executor stands in the start state, then it tries
- // every possible state transition in current state recursively. Some state
- // transitions consume input string, say, a single-char-matcher or a
+ // At the very beginning the executor stands in the start state, then it
+ // tries every possible state transition in current state recursively. Some
+ // state transitions consume input string, say, a single-char-matcher or a
// back-reference matcher; some don't, like assertion or other anchor nodes.
- // When the input is exhausted and/or the current state is an accepting state,
- // the whole executor returns true.
+ // When the input is exhausted and/or the current state is an accepting
+ // state, the whole executor returns true.
//
// TODO: This approach is exponentially slow for certain input.
// Try to compile the NFA to a DFA.
@@ -75,6 +76,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Time complexity: \Omega(match_length), O(2^(_M_nfa.size()))
// Space complexity: \theta(match_results.size() + match_length)
//
+ template<typename _BiIter, typename _Alloc, typename _TraitsT,
+ bool __dfs_mode>
+ bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
+ _M_main_dispatch(_Match_mode __match_mode, __dfs)
+ {
+ _M_has_sol = false;
+ _M_cur_results = _M_results;
+ _M_dfs(__match_mode, _M_states._M_start);
+ return _M_has_sol;
+ }
+
// ------------------------------------------------------------
//
// BFS mode:
@@ -84,11 +96,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
//
// It first computes epsilon closure (states that can be achieved without
// consuming characters) for every state that's still matching,
- // using the same DFS algorithm, but doesn't re-enter states (find a true in
- // _M_visited), nor follows _S_opcode_match.
+ // using the same DFS algorithm, but doesn't re-enter states (using
+ // _M_states._M_visited to check), nor follow _S_opcode_match.
//
- // Then apply DFS using every _S_opcode_match (in _M_match_queue) as the start
- // state.
+ // Then apply DFS using every _S_opcode_match (in _M_states._M_match_queue)
+ // as the start state.
//
// It significantly reduces potential duplicate states, so has a better
// upper bound; but it requires more overhead.
@@ -98,60 +110,45 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Space complexity: \Omega(_M_nfa.size() + match_results.size())
// O(_M_nfa.size() * match_results.size())
template<typename _BiIter, typename _Alloc, typename _TraitsT,
- bool __dfs_mode>
- template<bool __match_mode>
+ bool __dfs_mode>
bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
- _M_main()
+ _M_main_dispatch(_Match_mode __match_mode, __bfs)
{
- if (__dfs_mode)
+ _M_states._M_queue(_M_states._M_start, _M_results);
+ bool __ret = false;
+ while (1)
{
_M_has_sol = false;
- _M_cur_results = _M_results;
- _M_dfs<__match_mode>(_M_start_state);
- return _M_has_sol;
- }
- else
- {
- _M_match_queue->push_back(make_pair(_M_start_state, _M_results));
- bool __ret = false;
- while (1)
+ if (_M_states._M_match_queue.empty())
+ break;
+ std::fill_n(_M_states._M_visited_states.get(), _M_nfa.size(), false);
+ auto __old_queue = std::move(_M_states._M_match_queue);
+ for (auto& __task : __old_queue)
{
- _M_has_sol = false;
- if (_M_match_queue->empty())
- break;
- _M_visited->assign(_M_visited->size(), false);
- auto _M_old_queue = std::move(*_M_match_queue);
- for (auto __task : _M_old_queue)
- {
- _M_cur_results = __task.second;
- _M_dfs<__match_mode>(__task.first);
- }
- if (!__match_mode)
- __ret |= _M_has_sol;
- if (_M_current == _M_end)
- break;
- ++_M_current;
+ _M_cur_results = std::move(__task.second);
+ _M_dfs(__match_mode, __task.first);
}
- if (__match_mode)
- __ret = _M_has_sol;
- return __ret;
+ if (__match_mode == _Match_mode::_Prefix)
+ __ret |= _M_has_sol;
+ if (_M_current == _M_end)
+ break;
+ ++_M_current;
}
+ if (__match_mode == _Match_mode::_Exact)
+ __ret = _M_has_sol;
+ return __ret;
}
// Return whether now match the given sub-NFA.
template<typename _BiIter, typename _Alloc, typename _TraitsT,
- bool __dfs_mode>
+ bool __dfs_mode>
bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
_M_lookahead(_State<_TraitsT> __state)
{
_ResultsVec __what(_M_cur_results.size());
- auto __sub = std::unique_ptr<_Executor>(new _Executor(_M_current,
- _M_end,
- __what,
- _M_re,
- _M_flags));
- __sub->_M_start_state = __state._M_alt;
- if (__sub->_M_search_from_first())
+ _Executor __sub(_M_current, _M_end, __what, _M_re, _M_flags);
+ __sub._M_states._M_start = __state._M_alt;
+ if (__sub._M_search_from_first())
{
for (size_t __i = 0; __i < __what.size(); __i++)
if (__what[__i].matched)
@@ -169,9 +166,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// we need to spare one more time for potential group capture.
template<typename _BiIter, typename _Alloc, typename _TraitsT,
bool __dfs_mode>
- template<bool __match_mode>
void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
- _M_rep_once_more(_StateIdT __i)
+ _M_rep_once_more(_Match_mode __match_mode, _StateIdT __i)
{
const auto& __state = _M_nfa[__i];
auto& __rep_count = _M_rep_count[__i];
@@ -180,7 +176,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto __back = __rep_count;
__rep_count.first = _M_current;
__rep_count.second = 1;
- _M_dfs<__match_mode>(__state._M_alt);
+ _M_dfs(__match_mode, __state._M_alt);
__rep_count = __back;
}
else
@@ -188,24 +184,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__rep_count.second < 2)
{
__rep_count.second++;
- _M_dfs<__match_mode>(__state._M_alt);
+ _M_dfs(__match_mode, __state._M_alt);
__rep_count.second--;
}
}
};
template<typename _BiIter, typename _Alloc, typename _TraitsT,
- bool __dfs_mode>
- template<bool __match_mode>
+ bool __dfs_mode>
void _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
- _M_dfs(_StateIdT __i)
+ _M_dfs(_Match_mode __match_mode, _StateIdT __i)
{
- if (!__dfs_mode)
- {
- if ((*_M_visited)[__i])
- return;
- (*_M_visited)[__i] = true;
- }
+ if (_M_states._M_visited(__i))
+ return;
const auto& __state = _M_nfa[__i];
// Every change on _M_cur_results and _M_current will be rolled back after
@@ -221,33 +212,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Greedy.
if (!__state._M_neg)
{
- _M_rep_once_more<__match_mode>(__i);
+ _M_rep_once_more(__match_mode, __i);
// If it's DFS executor and already accepted, we're done.
if (!__dfs_mode || !_M_has_sol)
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
}
else // Non-greedy mode
{
if (__dfs_mode)
{
// vice-versa.
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
if (!_M_has_sol)
- _M_rep_once_more<__match_mode>(__i);
+ _M_rep_once_more(__match_mode, __i);
}
else
{
// DON'T attempt anything, because there's already another
- // state with higher priority accepted. This state cannot be
- // better by attempting its next node.
+ // state with higher priority accepted. This state cannot
+ // be better by attempting its next node.
if (!_M_has_sol)
{
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
// DON'T attempt anything if it's already accepted. An
// accepted state *must* be better than a solution that
// matches a non-greedy quantifier one more time.
if (!_M_has_sol)
- _M_rep_once_more<__match_mode>(__i);
+ _M_rep_once_more(__match_mode, __i);
}
}
}
@@ -258,7 +249,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto& __res = _M_cur_results[__state._M_subexpr];
auto __back = __res.first;
__res.first = _M_current;
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
__res.first = __back;
}
break;
@@ -268,27 +259,27 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
auto __back = __res;
__res.second = _M_current;
__res.matched = true;
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
__res = __back;
}
break;
case _S_opcode_line_begin_assertion:
if (_M_at_begin())
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
break;
case _S_opcode_line_end_assertion:
if (_M_at_end())
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
break;
case _S_opcode_word_boundary:
if (_M_word_boundary(__state) == !__state._M_neg)
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
break;
// Here __state._M_alt offers a single start node for a sub-NFA.
// We recursively invoke our algorithm to match the sub-NFA.
case _S_opcode_subexpr_lookahead:
if (_M_lookahead(__state) == !__state._M_neg)
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
break;
case _S_opcode_match:
if (__dfs_mode)
@@ -296,14 +287,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (_M_current != _M_end && __state._M_matches(*_M_current))
{
++_M_current;
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
--_M_current;
}
}
else
if (__state._M_matches(*_M_current))
- _M_match_queue->push_back(make_pair(__state._M_next,
- _M_cur_results));
+ _M_states._M_queue(__state._M_next, _M_cur_results);
break;
// First fetch the matched result from _M_cur_results as __submatch;
// then compare it with
@@ -328,11 +318,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
auto __backup = _M_current;
_M_current = __last;
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
_M_current = __backup;
}
else
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
}
}
break;
@@ -340,7 +330,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__dfs_mode)
{
_GLIBCXX_DEBUG_ASSERT(!_M_has_sol);
- if (__match_mode)
+ if (__match_mode == _Match_mode::_Exact)
_M_has_sol = _M_current == _M_end;
else
_M_has_sol = true;
@@ -355,7 +345,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (_M_current == _M_begin
&& (_M_flags & regex_constants::match_not_null))
break;
- if (!__match_mode || _M_current == _M_end)
+ if (__match_mode == _Match_mode::_Prefix || _M_current == _M_end)
if (!_M_has_sol)
{
_M_has_sol = true;
@@ -364,9 +354,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
break;
case _S_opcode_alternative:
- _M_dfs<__match_mode>(__state._M_alt);
+ _M_dfs(__match_mode, __state._M_alt);
if (!__dfs_mode || !_M_has_sol)
- _M_dfs<__match_mode>(__state._M_next);
+ _M_dfs(__match_mode, __state._M_next);
break;
default:
_GLIBCXX_DEBUG_ASSERT(false);
@@ -375,7 +365,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Return whether now is at some word boundary.
template<typename _BiIter, typename _Alloc, typename _TraitsT,
- bool __dfs_mode>
+ bool __dfs_mode>
bool _Executor<_BiIter, _Alloc, _TraitsT, __dfs_mode>::
_M_word_boundary(_State<_TraitsT> __state) const
{
diff --git a/libstdc++-v3/include/bits/regex_scanner.tcc b/libstdc++-v3/include/bits/regex_scanner.tcc
index f501ff6c2cb..818e47b5670 100644
--- a/libstdc++-v3/include/bits/regex_scanner.tcc
+++ b/libstdc++-v3/include/bits/regex_scanner.tcc
@@ -227,14 +227,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
}
// In POSIX, when encountering "[]" or "[^]", the ']' is interpreted
- // literally. So "[]]" or "[^]]" is valid regex. See the testcases
+ // literally. So "[]]" and "[^]]" are valid regexes. See the testcases
// `*/empty_range.cc`.
else if (__c == ']' && (_M_is_ecma() || !_M_at_bracket_start))
{
_M_token = _S_token_bracket_end;
_M_state = _S_state_normal;
}
- // ECMAScirpt and awk permmits escaping in bracket.
+ // ECMAScript and awk permits escaping in bracket.
else if (__c == '\\' && (_M_is_ecma() || _M_is_awk()))
(this->*_M_eat_escape)();
else
@@ -344,7 +344,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
_M_token = _S_token_hex_num;
}
- // ECMAScript recongnizes multi-digit back-references.
+ // ECMAScript recognizes multi-digit back-references.
else if (_M_ctype.is(_CtypeT::digit, __c))
{
_M_value.assign(1, __c);
@@ -392,6 +392,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else
{
#ifdef __STRICT_ANSI__
+ // POSIX says it is undefined to escape ordinary characters
__throw_regex_error(regex_constants::error_escape);
#else
_M_token = _S_token_ord_char;
@@ -435,8 +436,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__throw_regex_error(regex_constants::error_escape);
}
- // Eats a character class or throwns an exception.
- // __ch cound be ':', '.' or '=', _M_current is the char after ']' when
+ // Eats a character class or throws an exception.
+ // __ch could be ':', '.' or '=', _M_current is the char after ']' when
// returning.
template<typename _CharT>
void
diff --git a/libstdc++-v3/include/bits/uses_allocator.h b/libstdc++-v3/include/bits/uses_allocator.h
index 10131c0a967..7281508fc06 100644
--- a/libstdc++-v3/include/bits/uses_allocator.h
+++ b/libstdc++-v3/include/bits/uses_allocator.h
@@ -45,35 +45,33 @@ _GLIBCXX_HAS_NESTED_TYPE(allocator_type)
template<typename _Tp, typename _Alloc,
bool = __has_allocator_type<_Tp>::value>
struct __uses_allocator_helper
- : public false_type { };
+ : false_type { };
template<typename _Tp, typename _Alloc>
struct __uses_allocator_helper<_Tp, _Alloc, true>
- : public integral_constant<bool, is_convertible<_Alloc,
- typename _Tp::allocator_type>::value>
+ : is_convertible<_Alloc, typename _Tp::allocator_type>::type
{ };
/// [allocator.uses.trait]
template<typename _Tp, typename _Alloc>
struct uses_allocator
- : public integral_constant<bool,
- __uses_allocator_helper<_Tp, _Alloc>::value>
+ : __uses_allocator_helper<_Tp, _Alloc>::type
{ };
- template<typename _Tp, typename _Alloc, typename... _Args>
- struct __uses_allocator_arg
- : is_constructible<_Tp, _Alloc, _Args...>
- { static_assert( uses_allocator<_Tp, _Alloc>::value, "uses allocator" ); };
-
struct __uses_alloc_base { };
+
struct __uses_alloc0 : __uses_alloc_base
- { struct _Anything { _Anything(...) { } } _M_a; };
+ {
+ struct _Sink { void operator=(const void*) { } } _M_a;
+ };
+
template<typename _Alloc>
struct __uses_alloc1 : __uses_alloc_base { const _Alloc* _M_a; };
+
template<typename _Alloc>
struct __uses_alloc2 : __uses_alloc_base { const _Alloc* _M_a; };
- template<bool, typename _Alloc, typename... _Args>
+ template<bool, typename _Tp, typename _Alloc, typename... _Args>
struct __uses_alloc;
template<typename _Tp, typename _Alloc, typename... _Args>
@@ -89,15 +87,14 @@ _GLIBCXX_HAS_NESTED_TYPE(allocator_type)
: __uses_alloc0 { };
template<typename _Tp, typename _Alloc, typename... _Args>
- struct __uses_alloc_impl
- : __uses_alloc<uses_allocator<_Tp, _Alloc>::value, _Tp, _Alloc, _Args...>
- { };
+ using __uses_alloc_t =
+ __uses_alloc<uses_allocator<_Tp, _Alloc>::value, _Tp, _Alloc, _Args...>;
template<typename _Tp, typename _Alloc, typename... _Args>
- __uses_alloc_impl<_Tp, _Alloc, _Args...>
+ inline __uses_alloc_t<_Tp, _Alloc, _Args...>
__use_alloc(const _Alloc& __a)
{
- __uses_alloc_impl<_Tp, _Alloc, _Args...> __ret;
+ __uses_alloc_t<_Tp, _Alloc, _Args...> __ret;
__ret._M_a = &__a;
return __ret;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-26 09:58:14 +0000