Coverage Report

Created: 2025-06-13 06:43

/src/php-src/Zend/zend_sort.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
   +----------------------------------------------------------------------+
3
   | Zend Engine                                                          |
4
   +----------------------------------------------------------------------+
5
   | Copyright (c) Zend Technologies Ltd. (http://www.zend.com)           |
6
   +----------------------------------------------------------------------+
7
   | This source file is subject to version 2.00 of the Zend license,     |
8
   | that is bundled with this package in the file LICENSE, and is        |
9
   | available through the world-wide-web at the following url:           |
10
   | http://www.zend.com/license/2_00.txt.                                |
11
   | If you did not receive a copy of the Zend license and are unable to  |
12
   | obtain it through the world-wide-web, please send a note to          |
13
   | license@zend.com so we can mail you a copy immediately.              |
14
   +----------------------------------------------------------------------+
15
   | Authors: Xinchen Hui <laruence@php.net>                              |
16
   |          Sterling Hughes <sterling@php.net>                          |
17
   +----------------------------------------------------------------------+
18
*/
19
20
#include "zend.h"
21
#include "zend_sort.h"
22
#include <limits.h>
23
24
5.39k
static inline void zend_sort_2(void *a, void *b, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
25
5.39k
  if (cmp(a, b) > 0) {
26
3.28k
    swp(a, b);
27
3.28k
  }
28
5.39k
}
29
/* }}} */
30
31
133k
static inline void zend_sort_3(void *a, void *b, void *c, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
32
133k
  if (!(cmp(a, b) > 0)) {
33
43.5k
    if (!(cmp(b, c) > 0)) {
34
23.0k
      return;
35
23.0k
    }
36
20.5k
    swp(b, c);
37
20.5k
    if (cmp(a, b) > 0) {
38
9.09k
      swp(a, b);
39
9.09k
    }
40
20.5k
    return;
41
43.5k
  }
42
89.9k
  if (!(cmp(c, b) > 0)) {
43
9.47k
    swp(a, c);
44
9.47k
    return;
45
9.47k
  }
46
80.5k
  swp(a, b);
47
80.5k
  if (cmp(b, c) > 0) {
48
41.5k
    swp(b, c);
49
41.5k
  }
50
80.5k
}
51
/* }}} */
52
53
19.2k
static void zend_sort_4(void *a, void *b, void *c, void *d, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
54
19.2k
  zend_sort_3(a, b, c, cmp, swp);
55
19.2k
  if (cmp(c, d) > 0) {
56
12.8k
    swp(c, d);
57
12.8k
    if (cmp(b, c) > 0) {
58
4.31k
      swp(b, c);
59
4.31k
      if (cmp(a, b) > 0) {
60
2.24k
        swp(a, b);
61
2.24k
      }
62
4.31k
    }
63
12.8k
  }
64
19.2k
}
65
/* }}} */
66
67
12.6k
static void zend_sort_5(void *a, void *b, void *c, void *d, void *e, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
68
12.6k
  zend_sort_4(a, b, c, d, cmp, swp);
69
12.6k
  if (cmp(d, e) > 0) {
70
10.9k
    swp(d, e);
71
10.9k
    if (cmp(c, d) > 0) {
72
10.3k
      swp(c, d);
73
10.3k
      if (cmp(b, c) > 0) {
74
1.57k
        swp(b, c);
75
1.57k
        if (cmp(a, b) > 0) {
76
864
          swp(a, b);
77
864
        }
78
1.57k
      }
79
10.3k
    }
80
10.9k
  }
81
12.6k
}
82
/* }}} */
83
84
109k
ZEND_API void zend_insert_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) /* {{{ */{
85
109k
  switch (nmemb) {
86
0
    case 0:
87
4.34k
    case 1:
88
4.34k
      break;
89
5.39k
    case 2:
90
5.39k
      zend_sort_2(base, (char *)base + siz, cmp, swp);
91
5.39k
      break;
92
10.1k
    case 3:
93
10.1k
      zend_sort_3(base, (char *)base + siz, (char *)base + siz + siz, cmp, swp);
94
10.1k
      break;
95
6.65k
    case 4:
96
6.65k
      {
97
6.65k
        size_t siz2 = siz + siz;
98
6.65k
        zend_sort_4(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, cmp, swp);
99
6.65k
      }
100
6.65k
      break;
101
11.5k
    case 5:
102
11.5k
      {
103
11.5k
        size_t siz2 = siz + siz;
104
11.5k
        zend_sort_5(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, (char *)base + siz2 + siz2, cmp, swp);
105
11.5k
      }
106
11.5k
      break;
107
71.7k
    default:
108
71.7k
      {
109
71.7k
        char *i, *j, *k;
110
71.7k
        char *start = (char *)base;
111
71.7k
        char *end = start + (nmemb * siz);
112
71.7k
        size_t siz2= siz + siz;
113
71.7k
        char *sentry = start + (6 * siz);
114
430k
        for (i = start + siz; i < sentry; i += siz) {
115
358k
          j = i - siz;
116
358k
          if (!(cmp(j, i) > 0)) {
117
146k
            continue;
118
146k
          }
119
458k
          while (j != start) {
120
375k
            j -= siz;
121
375k
            if (!(cmp(j, i) > 0)) {
122
130k
              j += siz;
123
130k
              break;
124
130k
            }
125
375k
          }
126
670k
          for (k = i; k > j; k -= siz) {
127
458k
            swp(k, k - siz);
128
458k
          }
129
212k
        }
130
451k
        for (i = sentry; i < end; i += siz) {
131
379k
          j = i - siz;
132
379k
          if (!(cmp(j, i) > 0)) {
133
81.8k
            continue;
134
81.8k
          }
135
708k
          do {
136
708k
            j -= siz2;
137
708k
            if (!(cmp(j, i) > 0)) {
138
247k
              j += siz;
139
247k
              if (!(cmp(j, i) > 0)) {
140
155k
                j += siz;
141
155k
              }
142
247k
              break;
143
247k
            }
144
461k
            if (j == start) {
145
13.9k
              break;
146
13.9k
            }
147
447k
            if (j == start + siz) {
148
36.7k
              j -= siz;
149
36.7k
              if (cmp(i, j) > 0) {
150
19.7k
                j += siz;
151
19.7k
              }
152
36.7k
              break;
153
36.7k
            }
154
447k
          } while (1);
155
1.62M
          for (k = i; k > j; k -= siz) {
156
1.32M
            swp(k, k - siz);
157
1.32M
          }
158
297k
        }
159
71.7k
      }
160
71.7k
      break;
161
109k
  }
162
109k
}
163
/* }}} */
164
165
/* {{{ ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp)
166
 *
167
 * Derived from LLVM's libc++ implementation of std::sort.
168
 *
169
 * ===========================================================================
170
 * libc++ License
171
 * ===========================================================================
172
 *
173
 * The libc++ library is dual licensed under both the University of Illinois
174
 * "BSD-Like" license and the MIT license. As a user of this code you may
175
 * choose to use it under either license. As a contributor, you agree to allow
176
 * your code to be used under both.
177
 *
178
 * Full text of the relevant licenses is included below.
179
 *
180
 * ===========================================================================
181
 *
182
 * University of Illinois/NCSA
183
 * Open Source License
184
 *
185
 * Copyright (c) 2009-2012 by the contributors listed at
186
 * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT
187
 *
188
 * All rights reserved.
189
 *
190
 * Developed by:
191
 *
192
 *     LLVM Team
193
 *
194
 *     University of Illinois at Urbana-Champaign
195
 *
196
 *     http://llvm.org
197
 *
198
 * Permission is hereby granted, free of charge, to any person obtaining a copy
199
 * of this software and associated documentation files (the "Software"), to
200
 * deal with the Software without restriction, including without limitation the
201
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
202
 * sell copies of the Software, and to permit persons to whom the Software is
203
 * furnished to do so, subject to the following conditions:
204
 *
205
 *     * Redistributions of source code must retain the above copyright notice,
206
 *       this list of conditions and the following disclaimers.
207
 *
208
 *     * Redistributions in binary form must reproduce the above copyright
209
 *       notice, this list of conditions and the following disclaimers in the
210
 *       documentation and/or other materials provided with the distribution.
211
 *
212
 *     * Neither the names of the LLVM Team, University of Illinois at
213
 *       Urbana-Champaign, nor the names of its contributors may be used to
214
 *       endorse or promote products derived from this Software without
215
 *       specific prior written permission.
216
 *
217
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
218
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
219
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
220
 * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
221
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
222
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
223
 * WITH THE SOFTWARE.
224
 *
225
 * ===========================================================================
226
 *
227
 * Copyright (c) 2009-2012 by the contributors listed at
228
 * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT
229
 *
230
 * Permission is hereby granted, free of charge, to any person obtaining a copy
231
 * of this software and associated documentation files (the "Software"), to
232
 * deal in the Software without restriction, including without limitation the
233
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
234
 * sell copies of the Software, and to permit persons to whom the Software is
235
 * furnished to do so, subject to the following conditions:
236
 *
237
 * The above copyright notice and this permission notice shall be included in
238
 * all copies or substantial portions of the Software.
239
 *
240
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
241
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
242
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
243
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
244
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
245
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
246
 * IN THE SOFTWARE.
247
 */
248
ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp)
249
109k
{
250
215k
  while (1) {
251
215k
    if (nmemb <= 16) {
252
109k
      zend_insert_sort(base, nmemb, siz, cmp, swp);
253
109k
      return;
254
109k
    } else {
255
105k
      char *i, *j;
256
105k
      char *start = (char *)base;
257
105k
      char *end = start + (nmemb * siz);
258
105k
      size_t offset = (nmemb >> Z_L(1));
259
105k
      char *pivot = start + (offset * siz);
260
261
105k
      if ((nmemb >> Z_L(10))) {
262
1.08k
        size_t delta = (offset >> Z_L(1)) * siz;
263
1.08k
        zend_sort_5(start, start + delta, pivot, pivot + delta, end - siz, cmp, swp);
264
104k
      } else {
265
104k
        zend_sort_3(start, pivot, end - siz, cmp, swp);
266
104k
      }
267
105k
      swp(start + siz, pivot);
268
105k
      pivot = start + siz;
269
105k
      i = pivot + siz;
270
105k
      j = end - siz;
271
812k
      while (1) {
272
6.15M
        while (cmp(pivot, i) > 0) {
273
5.40M
          i += siz;
274
5.40M
          if (UNEXPECTED(i == j)) {
275
63.7k
            goto done;
276
63.7k
          }
277
5.40M
        }
278
748k
        j -= siz;
279
748k
        if (UNEXPECTED(j == i)) {
280
13.3k
          goto done;
281
13.3k
        }
282
3.64M
        while (cmp(j, pivot) > 0) {
283
2.92M
          j -= siz;
284
2.92M
          if (UNEXPECTED(j == i)) {
285
17.4k
            goto done;
286
17.4k
          }
287
2.92M
        }
288
717k
        swp(i, j);
289
717k
        i += siz;
290
717k
        if (UNEXPECTED(i == j)) {
291
10.7k
          goto done;
292
10.7k
        }
293
717k
      }
294
105k
done:
295
105k
      swp(pivot, i - siz);
296
105k
      if ((i - siz) - start < end - i) {
297
42.6k
        zend_sort(start, (i - start)/siz - 1, siz, cmp, swp);
298
42.6k
        base = i;
299
42.6k
        nmemb = (end - i)/siz;
300
62.5k
      } else {
301
62.5k
        zend_sort(i, (end - i)/siz, siz, cmp, swp);
302
62.5k
        nmemb = (i - start)/siz - 1;
303
62.5k
      }
304
105k
    }
305
215k
  }
306
109k
}
307
/* }}} */