OLD | NEW |
1 // Copyright (c) 2015, the Dartino project authors. Please see the AUTHORS file | 1 // Copyright (c) 2015, the Dartino project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE.md file. | 3 // BSD-style license that can be found in the LICENSE.md file. |
4 | 4 |
5 #include "src/vm/sort.h" | 5 #include "src/vm/sort.h" |
6 | 6 |
7 #include <stddef.h> | 7 #include <stddef.h> |
8 | 8 |
9 #include "src/shared/assert.h" | 9 #include "src/shared/assert.h" |
10 #include "src/shared/random.h" | 10 #include "src/shared/random.h" |
11 | 11 |
12 namespace fletch { | 12 namespace dartino { |
13 | 13 |
14 void InsertionSort(uint8* array, size_t elements, size_t element_size, | 14 void InsertionSort(uint8* array, size_t elements, size_t element_size, |
15 VoidCompare compare) { | 15 VoidCompare compare) { |
16 uint8 temp_buffer[128]; | 16 uint8 temp_buffer[128]; |
17 ASSERT(element_size <= 128); | 17 ASSERT(element_size <= 128); |
18 uint8* end = array + elements * element_size; | 18 uint8* end = array + elements * element_size; |
19 for (uint8* p = array + element_size; p < end; p += element_size) { | 19 for (uint8* p = array + element_size; p < end; p += element_size) { |
20 if (!compare(p, p - element_size)) continue; // Already in order. | 20 if (!compare(p, p - element_size)) continue; // Already in order. |
21 | 21 |
22 // Find insertion point. | 22 // Find insertion point. |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
121 elements = partition_index; | 121 elements = partition_index; |
122 } else { | 122 } else { |
123 VoidSort(start, partition_index, element_size, compare); | 123 VoidSort(start, partition_index, element_size, compare); |
124 start = partition; | 124 start = partition; |
125 elements -= partition_index; | 125 elements -= partition_index; |
126 } | 126 } |
127 } | 127 } |
128 InsertionSort(start, elements, element_size, compare); | 128 InsertionSort(start, elements, element_size, compare); |
129 } | 129 } |
130 | 130 |
131 } // namespace fletch | 131 } // namespace dartino |
OLD | NEW |