1 /* Copyright JS Foundation and other contributors, http://js.foundation
2 *
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 #include "ecma-builtin-helpers.h"
17 #include "ecma-globals.h"
18 #include "ecma-try-catch-macro.h"
19
20 /**
21 * Function used to reconstruct the ordered binary tree.
22 * Shifts 'index' down in the tree until it is in the correct position.
23 *
24 * @return ecma value
25 * Returned value must be freed with ecma_free_value.
26 */
27 static ecma_value_t
ecma_builtin_helper_array_to_heap(ecma_value_t * array_p,uint32_t index,uint32_t right,ecma_value_t compare_func,const ecma_builtin_helper_sort_compare_fn_t sort_cb)28 ecma_builtin_helper_array_to_heap (ecma_value_t *array_p, /**< heap data array */
29 uint32_t index, /**< current item index */
30 uint32_t right, /**< right index is a maximum index */
31 ecma_value_t compare_func, /**< compare function */
32 const ecma_builtin_helper_sort_compare_fn_t sort_cb) /**< sorting cb */
33 {
34 ecma_value_t ret_value = ECMA_VALUE_EMPTY;
35
36 /* Left child of the current index. */
37 uint32_t child = index * 2 + 1;
38 ecma_value_t swap = array_p[index];
39 bool should_break = false;
40
41 while (child <= right && ecma_is_value_empty (ret_value) && !should_break)
42 {
43 if (child < right)
44 {
45 /* Compare the two child nodes. */
46 ECMA_TRY_CATCH (child_compare_value, sort_cb (array_p[child], array_p[child + 1], compare_func),
47 ret_value);
48
49 JERRY_ASSERT (ecma_is_value_number (child_compare_value));
50
51 /* Use the child that is greater. */
52 if (ecma_get_number_from_value (child_compare_value) < ECMA_NUMBER_ZERO)
53 {
54 child++;
55 }
56
57 ECMA_FINALIZE (child_compare_value);
58 }
59
60 if (ecma_is_value_empty (ret_value))
61 {
62 JERRY_ASSERT (child <= right);
63
64 /* Compare current child node with the swap (tree top). */
65 ECMA_TRY_CATCH (swap_compare_value, sort_cb (array_p[child], swap, compare_func), ret_value);
66 JERRY_ASSERT (ecma_is_value_number (swap_compare_value));
67
68 if (ecma_get_number_from_value (swap_compare_value) <= ECMA_NUMBER_ZERO)
69 {
70 /* Break from loop if current child is less than swap (tree top) */
71 should_break = true;
72 }
73 else
74 {
75 /* We have to move 'swap' lower in the tree, so shift current child up in the hierarchy. */
76 uint32_t parent = (child - 1) / 2;
77 JERRY_ASSERT (parent <= right);
78 array_p[parent] = array_p[child];
79
80 /* Update child to be the left child of the current node. */
81 child = child * 2 + 1;
82 }
83
84 ECMA_FINALIZE (swap_compare_value);
85 }
86 }
87
88 /*
89 * Loop ended, either current child does not exist, or is less than swap.
90 * This means that 'swap' should be placed in the parent node.
91 */
92 uint32_t parent = (child - 1) / 2;
93 JERRY_ASSERT (parent <= right);
94 array_p[parent] = swap;
95
96 if (ecma_is_value_empty (ret_value))
97 {
98 ret_value = ECMA_VALUE_UNDEFINED;
99 }
100
101 return ret_value;
102 } /* ecma_builtin_helper_array_to_heap */
103
104 /**
105 * Heapsort function
106 *
107 * @return ecma value
108 * Returned value must be freed with ecma_free_value.
109 */
110 ecma_value_t
ecma_builtin_helper_array_heap_sort_helper(ecma_value_t * array_p,uint32_t right,ecma_value_t compare_func,const ecma_builtin_helper_sort_compare_fn_t sort_cb)111 ecma_builtin_helper_array_heap_sort_helper (ecma_value_t *array_p, /**< array to sort */
112 uint32_t right, /**< right index */
113 ecma_value_t compare_func, /**< compare function */
114 const ecma_builtin_helper_sort_compare_fn_t sort_cb) /**< sorting cb */
115 {
116 ecma_value_t ret_value = ECMA_VALUE_EMPTY;
117
118 /* First, construct the ordered binary tree from the array. */
119 for (uint32_t i = (right / 2) + 1; i > 0 && ecma_is_value_empty (ret_value); i--)
120 {
121 ECMA_TRY_CATCH (value,
122 ecma_builtin_helper_array_to_heap (array_p, i - 1, right, compare_func, sort_cb),
123 ret_value);
124 ECMA_FINALIZE (value);
125 }
126
127 /* Sorting elements. */
128 for (uint32_t i = right; i > 0 && ecma_is_value_empty (ret_value); i--)
129 {
130 /*
131 * The top element will always contain the largest value.
132 * Move top to the end, and remove it from the tree.
133 */
134 ecma_value_t swap = array_p[0];
135 array_p[0] = array_p[i];
136 array_p[i] = swap;
137
138 /* Rebuild binary tree from the remaining elements. */
139 ECMA_TRY_CATCH (value,
140 ecma_builtin_helper_array_to_heap (array_p, 0, i - 1, compare_func, sort_cb),
141 ret_value);
142 ECMA_FINALIZE (value);
143 }
144
145 return ret_value;
146 } /* ecma_builtin_helper_array_heap_sort_helper */
147