| 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 |