From dce7dbecb0135501eb8641c8f5ec8e98bddc808c Mon Sep 17 00:00:00 2001 From: Marc Mutz Date: Thu, 2 May 2019 19:56:29 +0200 Subject: qlalr: replace QLinkedList with std::list This is in preparation of deprecating QLinkedList. Most is straight-forward, except where operator+ was used on linked-list iterators. In one case, replaced this with std::next, in the other, with prefix increments, since the advancement was always equal to the loop control variable. Since advancing a linked-list iterator is a linear operation, this removes a source of quadratic complexity. Another obstacle was the overloaded op< set, which was in the Qt namespace while the iterator is from std and the payload, as before, was global. This breaks ADL, so move these operators to namespace std. This violates the standard, but the functions are tagged with our distinct types, so it shouldn't cause any trouble. Change-Id: Ifec0a927bfdabb002838cdf86fb8d23b32a38ff7 Reviewed-by: Giuseppe D'Angelo --- src/tools/bootstrap/bootstrap.pro | 1 - src/tools/qlalr/cppgenerator.cpp | 17 +++++++++-------- src/tools/qlalr/lalr.cpp | 10 ++++++---- src/tools/qlalr/lalr.h | 34 +++++++++++----------------------- src/tools/qlalr/main.cpp | 2 +- 5 files changed, 27 insertions(+), 37 deletions(-) (limited to 'src') diff --git a/src/tools/bootstrap/bootstrap.pro b/src/tools/bootstrap/bootstrap.pro index 8598fc2721..757460393e 100644 --- a/src/tools/bootstrap/bootstrap.pro +++ b/src/tools/bootstrap/bootstrap.pro @@ -84,7 +84,6 @@ SOURCES += \ ../../corelib/tools/qcryptographichash.cpp \ ../../corelib/tools/qhash.cpp \ ../../corelib/tools/qlist.cpp \ - ../../corelib/tools/qlinkedlist.cpp \ ../../corelib/tools/qlocale.cpp \ ../../corelib/tools/qlocale_tools.cpp \ ../../corelib/tools/qmap.cpp \ diff --git a/src/tools/qlalr/cppgenerator.cpp b/src/tools/qlalr/cppgenerator.cpp index ee17be041e..95f70dc988 100644 --- a/src/tools/qlalr/cppgenerator.cpp +++ b/src/tools/qlalr/cppgenerator.cpp @@ -36,6 +36,8 @@ #include #include +#include + namespace { void generateSeparator(int i, QTextStream &out) @@ -126,7 +128,7 @@ QString CppGenerator::endIncludeGuard(const QString &fileName) void CppGenerator::operator () () { // action table... - state_count = aut.states.size (); + state_count = static_cast(aut.states.size()); terminal_count = static_cast(grammar.terminals.size()); non_terminal_count = static_cast(grammar.non_terminals.size()); @@ -156,7 +158,7 @@ void CppGenerator::operator () () if (grammar.isNonTerminal (a.key ())) { - Q_ASSERT (symbol >= terminal_count && symbol < grammar.names.size ()); + Q_ASSERT(symbol >= terminal_count && symbol < static_cast(grammar.names.size())); GOTO (q, symbol - terminal_count) = r; } @@ -245,7 +247,7 @@ void CppGenerator::operator () () << Qt::endl; } - QBitArray used_rules (grammar.rules.count ()); + QBitArray used_rules{static_cast(grammar.rules.size())}; int q = 0; for (StatePointer state = aut.states.begin (); state != aut.states.end (); ++state, ++q) @@ -259,12 +261,11 @@ void CppGenerator::operator () () } } - for (int i = 0; i < used_rules.count (); ++i) + auto rule = grammar.rules.begin(); + for (int i = 0; i < used_rules.count (); ++i, ++rule) { if (! used_rules.testBit (i)) { - RulePointer rule = grammar.rules.begin () + i; - if (rule != grammar.goal) qerr() << "*** Warning: Rule ``" << *rule << "'' is useless!" << Qt::endl; } @@ -280,7 +281,7 @@ void CppGenerator::operator () () if (u >= 0) continue; - RulePointer rule = grammar.rules.begin () + (- u - 1); + RulePointer rule = std::next(grammar.rules.begin(), - u - 1); if (state->defaultReduce == rule) u = 0; @@ -619,7 +620,7 @@ void CppGenerator::generateImpl (QTextStream &out) out << "const int " << grammar.table_name << "::rule_index [] = {"; idx = 0; - int offset = 0; + size_t offset = 0; for (RulePointer rule = grammar.rules.begin (); rule != grammar.rules.end (); ++rule, ++idx) { generateSeparator(idx, out); diff --git a/src/tools/qlalr/lalr.cpp b/src/tools/qlalr/lalr.cpp index 8af3b3c0db..b9a9cf264f 100644 --- a/src/tools/qlalr/lalr.cpp +++ b/src/tools/qlalr/lalr.cpp @@ -51,7 +51,9 @@ QTextStream &qout() static QTextStream result(stdout, QIODevice::WriteOnly); return result; } +QT_END_NAMESPACE +namespace std { bool operator < (Name a, Name b) { return *a < *b; @@ -66,7 +68,7 @@ bool operator < (StatePointer a, StatePointer b) { return &*a < &*b; } -QT_END_NAMESPACE +} bool Read::operator < (const Read &other) const { @@ -329,7 +331,7 @@ QPair Automaton::internState (const State &state) struct _Bucket { - QLinkedList items; + std::list items; void insert (ItemPointer item) { items.push_back (item); } @@ -338,8 +340,8 @@ struct _Bucket { State st (aut->_M_grammar); - for (QLinkedList::iterator item = items.begin (); item != items.end (); ++item) - st.insert ((*item)->next ()); + for (auto &item : items) + st.insert(item->next()); return st; } diff --git a/src/tools/qlalr/lalr.h b/src/tools/qlalr/lalr.h index 55b65a640d..473ea89769 100644 --- a/src/tools/qlalr/lalr.h +++ b/src/tools/qlalr/lalr.h @@ -51,34 +51,22 @@ class Automaton; // names -typedef QLinkedList::iterator Name; -QT_BEGIN_NAMESPACE -Q_DECLARE_TYPEINFO(QLinkedList::iterator, Q_PRIMITIVE_TYPE); -QT_END_NAMESPACE -typedef QLinkedList NameList; +typedef std::list::iterator Name; +typedef std::list NameList; typedef std::set NameSet; // items -typedef QLinkedList ItemList; +typedef std::list ItemList; typedef ItemList::iterator ItemPointer; -QT_BEGIN_NAMESPACE -Q_DECLARE_TYPEINFO(ItemList::iterator, Q_PRIMITIVE_TYPE); -QT_END_NAMESPACE // rules -typedef QLinkedList debug_infot; +typedef std::list debug_infot; typedef debug_infot::iterator RulePointer; -QT_BEGIN_NAMESPACE -Q_DECLARE_TYPEINFO(debug_infot::iterator, Q_PRIMITIVE_TYPE); -QT_END_NAMESPACE typedef QMultiMap RuleMap; // states -typedef QLinkedList StateList; +typedef std::list StateList; typedef StateList::iterator StatePointer; -QT_BEGIN_NAMESPACE -Q_DECLARE_TYPEINFO(StateList::iterator, Q_PRIMITIVE_TYPE); -QT_END_NAMESPACE // arrows typedef QMap Bundle; @@ -175,7 +163,7 @@ class Node public: typedef std::set > Repository; typedef typename Repository::iterator iterator; - typedef typename QLinkedList::iterator edge_iterator; + typedef typename std::list::iterator edge_iterator; public: static iterator get (_Tp data); @@ -213,7 +201,7 @@ public: // attributes mutable bool root; mutable int dfn; mutable _Tp data; - mutable QLinkedList outs; + mutable std::list outs; protected: inline Node () {} @@ -235,7 +223,7 @@ typename Node<_Tp>::iterator Node<_Tp>::get (_Tp data) } template -QPair::iterator>::iterator, bool> Node<_Tp>::insertEdge (typename Node<_Tp>::iterator other) const +QPair::iterator>::iterator, bool> Node<_Tp>::insertEdge(typename Node<_Tp>::iterator other) const { edge_iterator it = std::find (outs.begin (), outs.end (), other); @@ -272,7 +260,7 @@ public: QString decl_file_name; QString impl_file_name; QString token_prefix; - QLinkedList names; + std::list names; Name start; NameSet terminals; NameSet non_terminals; @@ -401,11 +389,11 @@ private: int _M_includes_dfn; }; -QT_BEGIN_NAMESPACE +namespace std { bool operator < (Name a, Name b); bool operator < (StatePointer a, StatePointer b); bool operator < (ItemPointer a, ItemPointer b); -QT_END_NAMESPACE +} QTextStream &operator << (QTextStream &out, const Name &n); QTextStream &operator << (QTextStream &out, const Rule &r); diff --git a/src/tools/qlalr/main.cpp b/src/tools/qlalr/main.cpp index a920b13c85..6a57c7aa7a 100644 --- a/src/tools/qlalr/main.cpp +++ b/src/tools/qlalr/main.cpp @@ -106,7 +106,7 @@ int main (int argc, char *argv[]) if (! p.parse (file_name)) exit (EXIT_FAILURE); - if (grammar.rules.isEmpty ()) + if (grammar.rules.empty()) { qerr() << "*** Fatal. No rules!" << Qt::endl; exit (EXIT_FAILURE); -- cgit v1.2.3