OLD | NEW |
1 /* | 1 /* |
2 * taken from https://github.com/swenson/sort | 2 * taken from https://github.com/swenson/sort |
3 * Kept as is for the moment to be able to apply upstream patches for that | 3 * Kept as is for the moment to be able to apply upstream patches for that |
4 * code, currently used only to speed up XPath node sorting, see xpath.c | 4 * code, currently used only to speed up XPath node sorting, see xpath.c |
5 */ | 5 */ |
6 | 6 |
7 /* | 7 /* |
8 * All code in this header, unless otherwise specified, is hereby licensed under
the MIT Public License: | 8 * All code in this header, unless otherwise specified, is hereby licensed under
the MIT Public License: |
9 | 9 |
10 Copyright (c) 2010 Christopher Swenson | 10 Copyright (c) 2010 Christopher Swenson |
11 | 11 |
12 Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in th
e Software without restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the
Software, and to permit persons to whom the Software is furnished to do so, subj
ect to the following conditions: | 12 Permission is hereby granted, free of charge, to any person obtaining a copy of
this software and associated documentation files (the "Software"), to deal in th
e Software without restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the
Software, and to permit persons to whom the Software is furnished to do so, subj
ect to the following conditions: |
13 | 13 |
14 The above copyright notice and this permission notice shall be included in all c
opies or substantial portions of the Software. | 14 The above copyright notice and this permission notice shall be included in all c
opies or substantial portions of the Software. |
15 | 15 |
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLI
ED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR
A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYR
IGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WIT
H THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | 16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLI
ED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR
A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYR
IGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WIT
H THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
17 */ | 17 */ |
18 | 18 |
19 #include <stdlib.h> | 19 #include <stdlib.h> |
20 #include <stdio.h> | 20 #include <stdio.h> |
21 #include <string.h> | 21 #include <string.h> |
22 #ifdef HAVE_STDINT_H | 22 #ifdef HAVE_STDINT_H |
23 #include <stdint.h> | 23 #include <stdint.h> |
24 #else | 24 #else |
25 #ifdef HAVE_INTTYPES_H | 25 #ifdef HAVE_INTTYPES_H |
26 #include <inttypes.h> | 26 #include <inttypes.h> |
27 #elif defined(WIN32) | 27 #elif defined(WIN32) |
28 typedef __int64 int64_t; | 28 typedef __int64 int64_t; |
29 typedef unsigned __int64 uint64_t; | 29 typedef unsigned __int64 uint64_t; |
| 30 #if !defined(PRIuS) |
| 31 #define PRIuS "Iu" |
| 32 #endif |
30 #endif | 33 #endif |
31 #endif | 34 #endif |
32 | 35 |
33 #ifndef MK_UINT64 | 36 #ifndef MK_UINT64 |
34 #if defined(WIN32) && defined(_MSC_VER) && _MSC_VER < 1300 | 37 #if defined(WIN32) && defined(_MSC_VER) && _MSC_VER < 1300 |
35 #define MK_UINT64(x) ((uint64_t)(x)) | 38 #define MK_UINT64(x) ((uint64_t)(x)) |
36 #else | 39 #else |
37 #define MK_UINT64(x) x##ULL | 40 #define MK_UINT64(x) x##ULL |
38 #endif | 41 #endif |
39 #endif | 42 #endif |
(...skipping 276 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
316 } TEMP_STORAGE_T; | 319 } TEMP_STORAGE_T; |
317 | 320 |
318 | 321 |
319 static void TIM_SORT_RESIZE(TEMP_STORAGE_T *store, const size_t new_size) | 322 static void TIM_SORT_RESIZE(TEMP_STORAGE_T *store, const size_t new_size) |
320 { | 323 { |
321 if (store->alloc < new_size) | 324 if (store->alloc < new_size) |
322 { | 325 { |
323 SORT_TYPE *tempstore = (SORT_TYPE *)realloc(store->storage, new_size * sizeo
f(SORT_TYPE)); | 326 SORT_TYPE *tempstore = (SORT_TYPE *)realloc(store->storage, new_size * sizeo
f(SORT_TYPE)); |
324 if (tempstore == NULL) | 327 if (tempstore == NULL) |
325 { | 328 { |
326 fprintf(stderr, "Error allocating temporary storage for tim sort: need %lu
bytes", sizeof(SORT_TYPE) * new_size); | 329 fprintf(stderr, "Error allocating temporary storage for tim sort: need %"
PRIuS " bytes", sizeof(SORT_TYPE) * new_size); |
327 exit(1); | 330 exit(1); |
328 } | 331 } |
329 store->storage = tempstore; | 332 store->storage = tempstore; |
330 store->alloc = new_size; | 333 store->alloc = new_size; |
331 } | 334 } |
332 } | 335 } |
333 | 336 |
334 static void TIM_SORT_MERGE(SORT_TYPE *dst, const TIM_SORT_RUN_T *stack, const in
t stack_curr, TEMP_STORAGE_T *store) | 337 static void TIM_SORT_MERGE(SORT_TYPE *dst, const TIM_SORT_RUN_T *stack, const in
t stack_curr, TEMP_STORAGE_T *store) |
335 { | 338 { |
336 const int64_t A = stack[stack_curr - 2].length; | 339 const int64_t A = stack[stack_curr - 2].length; |
(...skipping 168 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
505 #undef BINARY_INSERTION_FIND | 508 #undef BINARY_INSERTION_FIND |
506 #undef BINARY_INSERTION_SORT_START | 509 #undef BINARY_INSERTION_SORT_START |
507 #undef BINARY_INSERTION_SORT | 510 #undef BINARY_INSERTION_SORT |
508 #undef REVERSE_ELEMENTS | 511 #undef REVERSE_ELEMENTS |
509 #undef COUNT_RUN | 512 #undef COUNT_RUN |
510 #undef TIM_SORT | 513 #undef TIM_SORT |
511 #undef TIM_SORT_RESIZE | 514 #undef TIM_SORT_RESIZE |
512 #undef TIM_SORT_COLLAPSE | 515 #undef TIM_SORT_COLLAPSE |
513 #undef TIM_SORT_RUN_T | 516 #undef TIM_SORT_RUN_T |
514 #undef TEMP_STORAGE_T | 517 #undef TEMP_STORAGE_T |
OLD | NEW |