|
1 | 1 | #pragma once |
2 | 2 |
|
3 | | -#include <string.h> |
4 | 3 | #if !defined(OS_DARWIN) && !defined(OS_FREEBSD) |
5 | 4 | #include <malloc.h> |
6 | 5 | #endif |
|
16 | 15 | #include <base/extended_types.h> |
17 | 16 | #include <base/sort.h> |
18 | 17 |
|
| 18 | +#include <Common/AllocatorWithMemoryTracking.h> |
19 | 19 | #include <Common/TargetSpecific.h> |
20 | 20 |
|
21 | 21 | /** Radix sort, has the following functionality: |
|
33 | 33 | */ |
34 | 34 |
|
35 | 35 |
|
36 | | -/** Used as a template parameter. See below. |
37 | | - */ |
38 | | -struct RadixSortAllocator |
39 | | -{ |
40 | | - static void * allocate(size_t size) |
41 | | - { |
42 | | - return ::operator new(size); |
43 | | - } |
44 | | - |
45 | | - static void deallocate(void * ptr, size_t size) |
46 | | - { |
47 | | - ::operator delete(ptr, size); |
48 | | - } |
49 | | -}; |
50 | | - |
51 | | - |
52 | 36 | /** A transformation that transforms the bit representation of a key into an unsigned integer number, |
53 | 37 | * that the order relation over the keys will match the order relation over the obtained unsigned numbers. |
54 | 38 | * For floats this conversion does the following: |
@@ -97,11 +81,6 @@ struct RadixSortFloatTraits |
97 | 81 | /// Converting a key into KeyBits is such that the order relation over the key corresponds to the order relation over KeyBits. |
98 | 82 | using Transform = RadixSortFloatTransform<KeyBits>; |
99 | 83 |
|
100 | | - /// An object with the functions allocate and deallocate. |
101 | | - /// Can be used, for example, to allocate memory for a temporary array on the stack. |
102 | | - /// To do this, the allocator itself is created on the stack. |
103 | | - using Allocator = RadixSortAllocator; |
104 | | - |
105 | 84 | /// The function to get the key from an array element. |
106 | 85 | static Key & extractKey(Element & elem) { return elem; } |
107 | 86 |
|
@@ -144,7 +123,6 @@ struct RadixSortUIntTraits |
144 | 123 | static constexpr size_t PART_SIZE_BITS = 8; |
145 | 124 |
|
146 | 125 | using Transform = RadixSortIdentityTransform<KeyBits>; |
147 | | - using Allocator = RadixSortAllocator; |
148 | 126 |
|
149 | 127 | static Key & extractKey(Element & elem) { return elem; } |
150 | 128 | static Result & extractResult(Element & elem) { return elem; } |
@@ -183,7 +161,6 @@ struct RadixSortIntTraits |
183 | 161 | static constexpr size_t PART_SIZE_BITS = 8; |
184 | 162 |
|
185 | 163 | using Transform = RadixSortSignedTransform<KeyBits>; |
186 | | - using Allocator = RadixSortAllocator; |
187 | 164 |
|
188 | 165 | static Key & extractKey(Element & elem) { return elem; } |
189 | 166 | static Result & extractResult(Element & elem) { return elem; } |
@@ -289,10 +266,10 @@ struct RadixSort |
289 | 266 | /// For each of the NUM_PASSES bit ranges of the key, consider how many times each value of this bit range met. |
290 | 267 | std::unique_ptr<CountType[]> histograms{new CountType[HISTOGRAM_SIZE * NUM_PASSES]{}}; |
291 | 268 |
|
292 | | - typename Traits::Allocator allocator; |
| 269 | + AllocatorWithMemoryTracking<typename Traits::Element> allocator; |
293 | 270 |
|
294 | 271 | /// We will do several passes through the array. On each pass, the data is transferred to another array. Let's allocate this temporary array. |
295 | | - Element * swap_buffer = reinterpret_cast<Element *>(allocator.allocate(size * sizeof(Element))); |
| 272 | + Element * swap_buffer = allocator.allocate(size); |
296 | 273 |
|
297 | 274 | /// Transform the array and calculate the histogram. |
298 | 275 | /// NOTE This is slightly suboptimal. Look at https://github.com/powturbo/TurboHist |
@@ -436,7 +413,7 @@ struct RadixSort |
436 | 413 | std::reverse(arr, arr + size); |
437 | 414 | } |
438 | 415 |
|
439 | | - allocator.deallocate(swap_buffer, size * sizeof(Element)); |
| 416 | + allocator.deallocate(swap_buffer, size); |
440 | 417 | } |
441 | 418 |
|
442 | 419 |
|
|
0 commit comments