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 24 namespace panda::ecmascript::base { 25 struct run { 26 int base; 27 int len; runrun28 run(int b, int l) : base(b), len(l) { 29 } 30 }; 31 32 class TimSort { TimSort(JSThread * thread,const JSHandle<TaggedArray> & elements,const JSHandle<JSTaggedValue> & fn)33 TimSort(JSThread *thread, const JSHandle<TaggedArray> &elements, const JSHandle<JSTaggedValue> &fn) 34 : thread_(thread), elements_(elements), fn_(fn), 35 minGallop_(MIN_GALLOP) {} ~TimSort()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 GetTempArray(int requestedSize)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 PushRun(const int runBase,const int runLen)77 void PushRun(const int runBase, const int runLen) 78 { 79 pending_.push_back(run(runBase, runLen)); 80 } 81 ComputeMinRunLength(int n)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 92 public: 93 static void Sort(JSThread *thread, JSHandle<TaggedArray> &elements, const JSHandle<JSTaggedValue> &fn); 94 }; 95 } 96 #endif