Merge qargs stable sort

Use stable sort for qargs

3 files changed, 50 insertions, 154 deletions

diff --git a/library/cpp/uri/common.h b/library/cpp/uri/common.h
index 27c559a55b..14e54f8bda 100644
--- a/library/cpp/uri/common.h
+++ b/library/cpp/uri/common.h
@@ -475,7 +475,6 @@ namespace NUri {
             ProcessedDirty = 1,
 
             ProcessedMalformed = 2,
-            ProcessedTooMany = 3,
         };
     };
 
diff --git a/library/cpp/uri/qargs.cpp b/library/cpp/uri/qargs.cpp
index 23058f8102..56572fe88d 100644
--- a/library/cpp/uri/qargs.cpp
+++ b/library/cpp/uri/qargs.cpp
@@ -1,21 +1,15 @@
 #include "qargs.h"
 #include <string>
+#include <vector>
 
 namespace NUri {
     namespace NOnStackArgsList {
         struct TQArgNode {
-            TQArgNode* Prev;
-            TQArgNode* Next;
-
             TStringBuf Name;
             TStringBuf Value;
             TStringBuf All;
         };
 
-        TQArgNode MakeArg(TQArgNode* prev) {
-            return {prev, 0, {}, {}, {}};
-        }
-
         const char* SkipDelimiter(const char* str, const char* end) {
             while (str != end)
                 if (*str == '&')
@@ -26,125 +20,38 @@ namespace NUri {
         }
 
         /// return next pos or 0 if error
-        const char* ExtractArgData(const char* pos, const char* end, TQArgNode* arg) {
+        const char* ExtractArgData(const char* pos, const char* end, TQArgNode& arg) {
             const char* nameStart = pos;
             const char* nextArg = strchr(pos, '&');
             const char* valueStart = strchr(pos, '=');
             if (valueStart && nextArg && valueStart < nextArg) // a=1& or a=&
             {
-                arg->Name = TStringBuf(nameStart, valueStart - nameStart);
-                arg->Value = TStringBuf(valueStart + 1, nextArg - valueStart - 1);
-                arg->All = TStringBuf(nameStart, nextArg - nameStart);
+                arg.Name = TStringBuf(nameStart, valueStart - nameStart);
+                arg.Value = TStringBuf(valueStart + 1, nextArg - valueStart - 1);
+                arg.All = TStringBuf(nameStart, nextArg - nameStart);
                 return nextArg;
             } else if (valueStart && nextArg && valueStart > nextArg) // a&b=2
             {
-                arg->Name = TStringBuf(nameStart, nextArg - nameStart);
-                arg->All = arg->Name;
+                arg.Name = TStringBuf(nameStart, nextArg - nameStart);
+                arg.All = arg.Name;
                 return nextArg;
             } else if (valueStart && !nextArg) // a=1 or a=
             {
-                arg->Name = TStringBuf(nameStart, valueStart - nameStart);
-                arg->Value = TStringBuf(valueStart + 1, end - valueStart - 1);
-                arg->All = TStringBuf(nameStart, end - nameStart);
+                arg.Name = TStringBuf(nameStart, valueStart - nameStart);
+                arg.Value = TStringBuf(valueStart + 1, end - valueStart - 1);
+                arg.All = TStringBuf(nameStart, end - nameStart);
                 return end;
             } else if (!valueStart && nextArg) // a&b
             {
-                arg->Name = TStringBuf(nameStart, nextArg - nameStart);
-                arg->All = arg->Name;
+                arg.Name = TStringBuf(nameStart, nextArg - nameStart);
+                arg.All = arg.Name;
                 return nextArg;
             } else { // a
-                arg->Name = TStringBuf(nameStart, end - nameStart);
-                arg->All = arg->Name;
+                arg.Name = TStringBuf(nameStart, end - nameStart);
+                arg.All = arg.Name;
                 return end;
             }
         }
-
-        // arg can be null
-        TQArgNode* GetHead(TQArgNode* arg) {
-            TQArgNode* prev = arg;
-            while (prev) {
-                arg = prev;
-                prev = prev->Prev;
-            }
-            return arg;
-        }
-
-        // arg can be null
-        TQArgNode* GetLast(TQArgNode* arg) {
-            TQArgNode* next = arg;
-            while (next) {
-                arg = next;
-                next = arg->Next;
-            }
-            return arg;
-        }
-
-        int CompareName(const TQArgNode* l, const TQArgNode* r) {
-            return l->Name.compare(r->Name);
-        }
-
-        TQArgNode* Move(TQArgNode* before, TQArgNode* node) {
-            TQArgNode* tn = node->Next;
-            TQArgNode* tp = node->Prev;
-
-            node->Prev = before->Prev;
-            if (node->Prev)
-                node->Prev->Next = node;
-
-            node->Next = before;
-            before->Prev = node;
-
-            if (tn)
-                tn->Prev = tp;
-            if (tp)
-                tp->Next = tn;
-
-            return node;
-        }
-
-        // return new head
-        TQArgNode* QSortByName(TQArgNode* iter, TQArgNode* last) {
-            if (iter == last)
-                return iter;
-            if (iter->Next == last) {
-                int c = CompareName(iter, last);
-                return c <= 0 ? iter : Move(iter, last);
-            } else {
-                TQArgNode* pivot = iter;
-                iter = iter->Next;
-                TQArgNode* head = 0;
-                TQArgNode* tail = 0;
-                TQArgNode* tailPartitionStart = pivot;
-                while (true) {
-                    TQArgNode* next = iter->Next;
-                    int c = CompareName(iter, pivot);
-                    int sign = (0 < c) - (c < 0);
-                    switch (sign) {
-                        case -1:
-                            head = head ? Move(head, iter) : Move(pivot, iter);
-                            break;
-
-                        case 0:
-                            pivot = Move(pivot, iter);
-                            break;
-
-                        case 1:
-                            tail = iter;
-                            break;
-                    }
-
-                    if (iter == last)
-                        break;
-                    iter = next;
-                }
-
-                if (head)
-                    head = QSortByName(head, pivot->Prev);
-                if (tail)
-                    QSortByName(tailPartitionStart->Next, tail);
-                return head ? head : pivot;
-            }
-        }
     }
 
     using namespace NOnStackArgsList;
@@ -154,7 +61,6 @@ namespace NUri {
         Pipeline(TQueryArgProcessing& parent, TUri& subject)
             : Parent(parent)
             , Subject(subject)
-            , ArgsCount(0)
             , IsDirty(false)
         {
         }
@@ -165,7 +71,7 @@ namespace NUri {
                 return ProcessEmpty();
 
             const char* start = query.data();
-            return Parse(start, start + query.length(), 0);
+            return Parse(start, start + query.length());
         }
 
         TQueryArg::EProcessed ProcessEmpty() {
@@ -175,52 +81,46 @@ namespace NUri {
             return TQueryArg::ProcessedOK;
         }
 
-        TQueryArg::EProcessed Parse(const char* str, const char* end, TQArgNode* prev) {
-            str = SkipDelimiter(str, end);
+        TQueryArg::EProcessed Parse(const char* str, const char* end) {
+            if (str != end)
+                Nodes.reserve(8);
 
-            if (str == end) {
-                TQArgNode* head = GetHead(prev);
-                TQArgNode* last = GetLast(prev);
-                return FinalizeParsing(head, last);
-            } else {
-                TQArgNode current = MakeArg(prev);
-                const char* next = ExtractArgData(str, end, &current);
-                if (!next)
-                    return TQueryArg::ProcessedMalformed;
+            while (str != end) {
+                str = SkipDelimiter(str, end);
 
-                TQArgNode* tail = ApplyFilter(prev, &current);
+                TQArgNode current;
+                str = ExtractArgData(str, end, current);
 
-                if (++ArgsCount > MaxCount)
-                    return TQueryArg::ProcessedTooMany;
-
-                return Parse(next, end, tail);
-            }
-        }
+                if (!str)
+                    return TQueryArg::ProcessedMalformed;
 
-        TQArgNode* ApplyFilter(TQArgNode* prev, TQArgNode* current) {
-            if (Parent.Flags & TQueryArg::FeatureFilter) {
-                TQueryArg arg = {current->Name, current->Value};
-                if (!Parent.Filter(arg, Parent.FilterData)) {
-                    IsDirty = true;
-                    return prev;
+                if (Parent.Flags & TQueryArg::FeatureFilter) {
+                    TQueryArg arg = {current.Name, current.Value};
+                    if (!Parent.Filter(arg, Parent.FilterData)) {
+                        IsDirty = true;
+                        continue;
+                    }
                 }
-            }
 
-            if (prev)
-                prev->Next = current;
-            return current;
-        }
+                Nodes.push_back(current);
+            }
 
-        TQueryArg::EProcessed FinalizeParsing(TQArgNode* head, TQArgNode* last) {
             if (Parent.Flags & TQueryArg::FeatureSortByName) {
-                head = QSortByName(head, last);
+                std::stable_sort(Nodes.begin(), Nodes.end(), [](auto l, auto r) {
+                    return l.Name < r.Name;
+                });
+                
                 IsDirty = true;
             }
 
+            return FinalizeParsing();
+        }
+
+        TQueryArg::EProcessed FinalizeParsing() {
             if (!IsDirty)
                 return TQueryArg::ProcessedOK;
 
-            bool dirty = Render(head);
+            bool dirty = Render();
 
             bool rewrite = Parent.Flags & TQueryArg::FeatureRewriteDirty;
             if (dirty && rewrite)
@@ -228,19 +128,18 @@ namespace NUri {
             return (!dirty || rewrite) ? TQueryArg::ProcessedOK : TQueryArg::ProcessedDirty;
         }
 
-        bool Render(TQArgNode* head) {
+        bool Render() {
             std::string& result = Parent.Buffer;
             result.clear();
             result.reserve(Subject.GetField(NUri::TField::FieldQuery).length());
+
             bool first = true;
-            while (head) {
-                if (first)
-                    first = false;
-                else
+            for (const auto& node: Nodes)
+            {
+                if (!first)
                     result.append("&");
-
-                result.append(head->All);
-                head = head->Next;
+                result.append(node.All);
+                first = false;
             }
 
             if (result.empty())
@@ -259,10 +158,8 @@ namespace NUri {
         TQueryArgProcessing& Parent;
         TUri& Subject;
 
-        unsigned ArgsCount;
+        std::vector<TQArgNode> Nodes;
         bool IsDirty;
-
-        static const unsigned MaxCount = 100;
     };
 
     TQueryArgProcessing::TQueryArgProcessing(ui32 flags, TQueryArgFilter filter, void* filterData)
diff --git a/library/cpp/uri/uri_ut.cpp b/library/cpp/uri/uri_ut.cpp
index 2ebd83fc93..b54653854d 100644
--- a/library/cpp/uri/uri_ut.cpp
+++ b/library/cpp/uri/uri_ut.cpp
@@ -960,7 +960,7 @@ namespace NUri {
             UNIT_ASSERT_STRINGS_EQUAL(SortQargs("http://ya.ru/?"), "http://ya.ru/?");
             UNIT_ASSERT_STRINGS_EQUAL(SortQargs("http://ya.ru/?some=value"), "http://ya.ru/?some=value");
             UNIT_ASSERT_STRINGS_EQUAL(SortQargs("http://ya.ru/?b=1&a=2"), "http://ya.ru/?a=2&b=1");
-            UNIT_ASSERT_STRINGS_EQUAL(SortQargs("http://ya.ru/?b=1&a=2&a=3"), "http://ya.ru/?a=3&a=2&b=1");
+            UNIT_ASSERT_STRINGS_EQUAL(SortQargs("http://ya.ru/?b=1&a=2&a=3"), "http://ya.ru/?a=2&a=3&b=1");
 
             UNIT_ASSERT_STRINGS_EQUAL(SortQargs("http://ya.ru/?aaa=3&b=b&a=1&aa=2"), "http://ya.ru/?a=1&aa=2&aaa=3&b=b");