1/*
2 * Copyright (c) 2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16#ifndef ECMASCRIPT_BASE_SORT_HELPER_H
17#define ECMASCRIPT_BASE_SORT_HELPER_H
18
19#include "ecmascript/js_tagged_value.h"
20#include "ecmascript/js_handle.h"
21#include "ecmascript/object_factory.h"
22#include "ecmascript/global_env.h"
23
24namespace panda::ecmascript::base {
25struct run {
26    int base;
27    int len;
28    run(int b, int l) : base(b), len(l) {
29    }
30};
31
32class TimSort {
33    TimSort(JSThread *thread, const JSHandle<TaggedArray> &elements, const JSHandle<JSTaggedValue> &fn)
34        : thread_(thread), elements_(elements), fn_(fn),
35          minGallop_(MIN_GALLOP) {}
36    ~TimSort() {}
37
38    JSThread *thread_ {nullptr};
39    JSHandle<TaggedArray> elements_;
40    JSHandle<JSTaggedValue> fn_;
41
42    static const int MIN_MERGE = 32;
43    static const int MIN_GALLOP = 7;
44    static const int tempSize = 32;
45    int minGallop_; // default to MIN_GALLOP
46    JSHandle<TaggedArray> tmp_ {}; // temp storage for merges
47    std::vector<run> pending_;
48
49    static void BinarySort(JSThread *thread, JSHandle<TaggedArray> &array,
50                           int lo, int hi, int start, JSHandle<JSTaggedValue> fn);
51    static int CountRunAndMakeAscending(JSThread *thread, JSHandle<TaggedArray> &array, int lo, int h,
52                                        const JSHandle<JSTaggedValue> &fn);
53    static void ReverseRange(JSThread *thread, JSHandle<TaggedArray> &array, int from, int to);
54    void MergeCollapse();
55    void MergeForceCollapse();
56    void MergeAt(int i);
57    int GallopLeft(JSHandle<TaggedArray> &array, JSHandle<JSTaggedValue> key, int base, int len, int hint);
58    int GallopRight(JSHandle<TaggedArray> &array, JSHandle<JSTaggedValue> key, int base, int len, int hint);
59    void MergeLo(int base1, int len1, int base2, int len2);
60    void MergeHi(int base1, int len1, int base2, int len2);
61    void CopyArray(JSHandle<TaggedArray> &src, int srcPos,
62                   JSHandle<TaggedArray> &dst, int dstPos, int length);
63
64    JSHandle<TaggedArray> GetTempArray(int requestedSize)
65    {
66        int minSize = std::max(requestedSize, 32);
67        if (!tmp_.IsEmpty()) {
68            int currentSize = static_cast<int>(tmp_->GetLength());
69            if (currentSize >= minSize) {
70                return tmp_;
71            }
72        }
73        tmp_ = thread_->GetEcmaVM()->GetFactory()->NewTaggedArray(minSize);
74        return tmp_;
75    }
76
77    void PushRun(const int runBase, const int runLen)
78    {
79        pending_.push_back(run(runBase, runLen));
80    }
81
82    static int ComputeMinRunLength(int n)
83    {
84        int r = 0;
85        while (n >= 2 * MIN_MERGE) { // 2 * MIN_MERGE : 64
86            r |= (n & 1);
87            n >>= 1;
88        }
89        return n + r;
90    }
91
92public:
93    static void Sort(JSThread *thread, JSHandle<TaggedArray> &elements, const JSHandle<JSTaggedValue> &fn);
94};
95}
96#endif