1
/* -*- c -*- */
2

3
/*
4
 * The purpose of this module is to add faster sort functions
5
 * that are type-specific.  This is done by altering the
6
 * function table for the builtin descriptors.
7
 *
8
 * These sorting functions are copied almost directly from numarray
9
 * with a few modifications (complex comparisons compare the imaginary
10
 * part if the real parts are equal, for example), and the names
11
 * are changed.
12
 *
13
 * The original sorting code is due to Charles R. Harris who wrote
14
 * it for numarray.
15
 */
16

17
/*
18
 * Quick sort is usually the fastest, but the worst case scenario is O(N^2) so
19
 * the code switches to the O(NlogN) worst case heapsort if not enough progress
20
 * is made on the large side of the two quicksort partitions. This improves the
21
 * worst case while still retaining the speed of quicksort for the common case.
22
 * This is variant known as introsort.
23
 *
24
 *
25
 * def introsort(lower, higher, recursion_limit=log2(higher - lower + 1) * 2):
26
 *   # sort remainder with heapsort if we are not making enough progress
27
 *   # we arbitrarily choose 2 * log(n) as the cutoff point
28
 *   if recursion_limit < 0:
29
 *       heapsort(lower, higher)
30
 *       return
31
 *
32
 *   if lower < higher:
33
 *      pivot_pos = partition(lower, higher)
34
 *      # recurse into smaller first and leave larger on stack
35
 *      # this limits the required stack space
36
 *      if (pivot_pos - lower > higher - pivot_pos):
37
 *          quicksort(pivot_pos + 1, higher, recursion_limit - 1)
38
 *          quicksort(lower, pivot_pos, recursion_limit - 1)
39
 *      else:
40
 *          quicksort(lower, pivot_pos, recursion_limit - 1)
41
 *          quicksort(pivot_pos + 1, higher, recursion_limit - 1)
42
 *
43
 *
44
 * the below code implements this converted to an iteration and as an
45
 * additional minor optimization skips the recursion depth checking on the
46
 * smaller partition as it is always less than half of the remaining data and
47
 * will thus terminate fast enough
48
 */
49

50
#define NPY_NO_DEPRECATED_API NPY_API_VERSION
51

52
#include "npy_sort.h"
53
#include "npysort_common.h"
54
#include <stdlib.h>
55

56
#define NOT_USED NPY_UNUSED(unused)
57
/*
58
 * pushing largest partition has upper bound of log2(n) space
59
 * we store two pointers each time
60
 */
61
#define PYA_QS_STACK (NPY_BITSOF_INTP * 2)
62
#define SMALL_QUICKSORT 15
63
#define SMALL_MERGESORT 20
64
#define SMALL_STRING 16
65

66

67
/*
68
 *****************************************************************************
69
 **                            NUMERIC SORTS                                **
70
 *****************************************************************************
71
 */
72

73

74
/**begin repeat
75
 *
76
 * #TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
77
 *         LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE,
78
 *         CFLOAT, CDOUBLE, CLONGDOUBLE, DATETIME, TIMEDELTA#
79
 * #suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong,
80
 *         longlong, ulonglong, half, float, double, longdouble,
81
 *         cfloat, cdouble, clongdouble, datetime, timedelta#
82
 * #type = npy_bool, npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int,
83
 *         npy_uint, npy_long, npy_ulong, npy_longlong, npy_ulonglong,
84
 *         npy_ushort, npy_float, npy_double, npy_longdouble, npy_cfloat,
85
 *         npy_cdouble, npy_clongdouble, npy_datetime, npy_timedelta#
86
 */
87

88
NPY_NO_EXPORT int
89 1
quicksort_@suff@(void *start, npy_intp num, void *NOT_USED)
90
{
91
    @type@ vp;
92 1
    @type@ *pl = start;
93 1
    @type@ *pr = pl + num - 1;
94
    @type@ *stack[PYA_QS_STACK];
95 1
    @type@ **sptr = stack;
96
    @type@ *pm, *pi, *pj, *pk;
97
    int depth[PYA_QS_STACK];
98 1
    int * psdepth = depth;
99 1
    int cdepth = npy_get_msb(num) * 2;
100

101
    for (;;) {
102 1
        if (NPY_UNLIKELY(cdepth < 0)) {
103 1
            heapsort_@suff@(pl, pr - pl + 1, NULL);
104 1
            goto stack_pop;
105
        }
106 1
        while ((pr - pl) > SMALL_QUICKSORT) {
107
            /* quicksort partition */
108 1
            pm = pl + ((pr - pl) >> 1);
109 1
            if (@TYPE@_LT(*pm, *pl)) @TYPE@_SWAP(*pm, *pl);
110 1
            if (@TYPE@_LT(*pr, *pm)) @TYPE@_SWAP(*pr, *pm);
111 1
            if (@TYPE@_LT(*pm, *pl)) @TYPE@_SWAP(*pm, *pl);
112 1
            vp = *pm;
113 1
            pi = pl;
114 1
            pj = pr - 1;
115 1
            @TYPE@_SWAP(*pm, *pj);
116 1
            for (;;) {
117 1
                do ++pi; while (@TYPE@_LT(*pi, vp));
118 1
                do --pj; while (@TYPE@_LT(vp, *pj));
119 1
                if (pi >= pj) {
120
                    break;
121
                }
122 1
                @TYPE@_SWAP(*pi,*pj);
123
            }
124 1
            pk = pr - 1;
125 1
            @TYPE@_SWAP(*pi, *pk);
126
            /* push largest partition on stack */
127 1
            if (pi - pl < pr - pi) {
128 1
                *sptr++ = pi + 1;
129 1
                *sptr++ = pr;
130 1
                pr = pi - 1;
131
            }
132
            else {
133 1
                *sptr++ = pl;
134 1
                *sptr++ = pi - 1;
135 1
                pl = pi + 1;
136
            }
137 1
            *psdepth++ = --cdepth;
138
        }
139

140
        /* insertion sort */
141 1
        for (pi = pl + 1; pi <= pr; ++pi) {
142 1
            vp = *pi;
143 1
            pj = pi;
144 1
            pk = pi - 1;
145 1
            while (pj > pl && @TYPE@_LT(vp, *pk)) {
146 1
                *pj-- = *pk--;
147
            }
148 1
            *pj = vp;
149
        }
150 1
stack_pop:
151 1
        if (sptr == stack) {
152
            break;
153
        }
154 1
        pr = *(--sptr);
155 1
        pl = *(--sptr);
156 1
        cdepth = *(--psdepth);
157
    }
158

159 1
    return 0;
160
}
161

162

163
NPY_NO_EXPORT int
164 1
aquicksort_@suff@(void *vv, npy_intp* tosort, npy_intp num, void *NOT_USED)
165
{
166 1
    @type@ *v = vv;
167
    @type@ vp;
168 1
    npy_intp *pl = tosort;
169 1
    npy_intp *pr = tosort + num - 1;
170
    npy_intp *stack[PYA_QS_STACK];
171 1
    npy_intp **sptr = stack;
172
    npy_intp *pm, *pi, *pj, *pk, vi;
173
    int depth[PYA_QS_STACK];
174 1
    int * psdepth = depth;
175 1
    int cdepth = npy_get_msb(num) * 2;
176

177
    for (;;) {
178 1
        if (NPY_UNLIKELY(cdepth < 0)) {
179 1
            aheapsort_@suff@(vv, pl, pr - pl + 1, NULL);
180 1
            goto stack_pop;
181
        }
182 1
        while ((pr - pl) > SMALL_QUICKSORT) {
183
            /* quicksort partition */
184 1
            pm = pl + ((pr - pl) >> 1);
185 1
            if (@TYPE@_LT(v[*pm],v[*pl])) INTP_SWAP(*pm, *pl);
186 1
            if (@TYPE@_LT(v[*pr],v[*pm])) INTP_SWAP(*pr, *pm);
187 1
            if (@TYPE@_LT(v[*pm],v[*pl])) INTP_SWAP(*pm, *pl);
188 1
            vp = v[*pm];
189 1
            pi = pl;
190 1
            pj = pr - 1;
191 1
            INTP_SWAP(*pm, *pj);
192 1
            for (;;) {
193 1
                do ++pi; while (@TYPE@_LT(v[*pi], vp));
194 1
                do --pj; while (@TYPE@_LT(vp, v[*pj]));
195 1
                if (pi >= pj) {
196
                    break;
197
                }
198 1
                INTP_SWAP(*pi, *pj);
199
            }
200 1
            pk = pr - 1;
201 1
            INTP_SWAP(*pi,*pk);
202
            /* push largest partition on stack */
203 1
            if (pi - pl < pr - pi) {
204 1
                *sptr++ = pi + 1;
205 1
                *sptr++ = pr;
206 1
                pr = pi - 1;
207
            }
208
            else {
209 1
                *sptr++ = pl;
210 1
                *sptr++ = pi - 1;
211 1
                pl = pi + 1;
212
            }
213 1
            *psdepth++ = --cdepth;
214
        }
215

216
        /* insertion sort */
217 1
        for (pi = pl + 1; pi <= pr; ++pi) {
218 1
            vi = *pi;
219 1
            vp = v[vi];
220 1
            pj = pi;
221 1
            pk = pi - 1;
222 1
            while (pj > pl && @TYPE@_LT(vp, v[*pk])) {
223 1
                *pj-- = *pk--;
224
            }
225 1
            *pj = vi;
226
        }
227 1
stack_pop:
228 1
        if (sptr == stack) {
229
            break;
230
        }
231 1
        pr = *(--sptr);
232 1
        pl = *(--sptr);
233 1
        cdepth = *(--psdepth);
234
    }
235

236 1
    return 0;
237
}
238

239
/**end repeat**/
240

241

242
/*
243
 *****************************************************************************
244
 **                             STRING SORTS                                **
245
 *****************************************************************************
246
 */
247

248

249
/**begin repeat
250
 *
251
 * #TYPE = STRING, UNICODE#
252
 * #suff = string, unicode#
253
 * #type = npy_char, npy_ucs4#
254
 */
255

256
NPY_NO_EXPORT int
257 1
quicksort_@suff@(void *start, npy_intp num, void *varr)
258
{
259 1
    PyArrayObject *arr = varr;
260 1
    const size_t len = PyArray_ITEMSIZE(arr)/sizeof(@type@);
261
    @type@ *vp;
262 1
    @type@ *pl = start;
263 1
    @type@ *pr = pl + (num - 1)*len;
264 1
    @type@ *stack[PYA_QS_STACK], **sptr = stack, *pm, *pi, *pj, *pk;
265
    int depth[PYA_QS_STACK];
266 1
    int * psdepth = depth;
267 1
    int cdepth = npy_get_msb(num) * 2;
268

269
    /* Items that have zero size don't make sense to sort */
270 1
    if (len == 0) {
271
        return 0;
272
    }
273

274 1
    vp = malloc(PyArray_ITEMSIZE(arr));
275 1
    if (vp == NULL) {
276
        return -NPY_ENOMEM;
277
    }
278

279
    for (;;) {
280 1
        if (NPY_UNLIKELY(cdepth < 0)) {
281 0
            heapsort_@suff@(pl, (pr - pl) / len + 1, varr);
282 0
            goto stack_pop;
283
        }
284 1
        while ((size_t)(pr - pl) > SMALL_QUICKSORT*len) {
285
            /* quicksort partition */
286 1
            pm = pl + (((pr - pl)/len) >> 1)*len;
287 1
            if (@TYPE@_LT(pm, pl, len)) @TYPE@_SWAP(pm, pl, len);
288 1
            if (@TYPE@_LT(pr, pm, len)) @TYPE@_SWAP(pr, pm, len);
289 1
            if (@TYPE@_LT(pm, pl, len)) @TYPE@_SWAP(pm, pl, len);
290 1
            @TYPE@_COPY(vp, pm, len);
291 1
            pi = pl;
292 1
            pj = pr - len;
293
            @TYPE@_SWAP(pm, pj, len);
294
            for (;;) {
295 1
                do pi += len; while (@TYPE@_LT(pi, vp, len));
296 1
                do pj -= len; while (@TYPE@_LT(vp, pj, len));
297 1
                if (pi >= pj) {
298
                    break;
299
                }
300
                @TYPE@_SWAP(pi, pj, len);
301
            }
302
            pk = pr - len;
303 1
            @TYPE@_SWAP(pi, pk, len);
304
            /* push largest partition on stack */
305 1
            if (pi - pl < pr - pi) {
306 1
                *sptr++ = pi + len;
307 1
                *sptr++ = pr;
308 1
                pr = pi - len;
309
            }
310
            else {
311 1
                *sptr++ = pl;
312 1
                *sptr++ = pi - len;
313 1
                pl = pi + len;
314
            }
315 1
            *psdepth++ = --cdepth;
316
        }
317

318
        /* insertion sort */
319 1
        for (pi = pl + len; pi <= pr; pi += len) {
320 1
            @TYPE@_COPY(vp, pi, len);
321 1
            pj = pi;
322 1
            pk = pi - len;
323 1
            while (pj > pl && @TYPE@_LT(vp, pk, len)) {
324 1
                @TYPE@_COPY(pj, pk, len);
325 1
                pj -= len;
326 1
                pk -= len;
327
            }
328 1
            @TYPE@_COPY(pj, vp, len);
329
        }
330 1
stack_pop:
331 1
        if (sptr == stack) {
332
            break;
333
        }
334 1
        pr = *(--sptr);
335 1
        pl = *(--sptr);
336 1
        cdepth = *(--psdepth);
337
    }
338

339 1
    free(vp);
340 1
    return 0;
341
}
342

343

344
NPY_NO_EXPORT int
345 1
aquicksort_@suff@(void *vv, npy_intp* tosort, npy_intp num, void *varr)
346
{
347 1
    @type@ *v = vv;
348 1
    PyArrayObject *arr = varr;
349 1
    size_t len = PyArray_ITEMSIZE(arr)/sizeof(@type@);
350
    @type@ *vp;
351 1
    npy_intp *pl = tosort;
352 1
    npy_intp *pr = tosort + num - 1;
353
    npy_intp *stack[PYA_QS_STACK];
354 1
    npy_intp **sptr=stack;
355
    npy_intp *pm, *pi, *pj, *pk, vi;
356
    int depth[PYA_QS_STACK];
357 1
    int * psdepth = depth;
358 1
    int cdepth = npy_get_msb(num) * 2;
359

360
    /* Items that have zero size don't make sense to sort */
361 1
    if (len == 0) {
362
        return 0;
363
    }
364

365
    for (;;) {
366 1
        if (NPY_UNLIKELY(cdepth < 0)) {
367 0
            aheapsort_@suff@(vv, pl, pr - pl + 1, varr);
368 0
            goto stack_pop;
369
        }
370 1
        while ((pr - pl) > SMALL_QUICKSORT) {
371
            /* quicksort partition */
372 1
            pm = pl + ((pr - pl) >> 1);
373 1
            if (@TYPE@_LT(v + (*pm)*len, v + (*pl)*len, len)) INTP_SWAP(*pm, *pl);
374 1
            if (@TYPE@_LT(v + (*pr)*len, v + (*pm)*len, len)) INTP_SWAP(*pr, *pm);
375 1
            if (@TYPE@_LT(v + (*pm)*len, v + (*pl)*len, len)) INTP_SWAP(*pm, *pl);
376 1
            vp = v + (*pm)*len;
377 1
            pi = pl;
378 1
            pj = pr - 1;
379 1
            INTP_SWAP(*pm,*pj);
380 1
            for (;;) {
381 1
                do ++pi; while (@TYPE@_LT(v + (*pi)*len, vp, len));
382 1
                do --pj; while (@TYPE@_LT(vp, v + (*pj)*len, len));
383 1
                if (pi >= pj) {
384
                    break;
385
                }
386 1
                INTP_SWAP(*pi,*pj);
387
            }
388 1
            pk = pr - 1;
389 1
            INTP_SWAP(*pi,*pk);
390
            /* push largest partition on stack */
391 1
            if (pi - pl < pr - pi) {
392 1
                *sptr++ = pi + 1;
393 1
                *sptr++ = pr;
394 1
                pr = pi - 1;
395
            }
396
            else {
397 1
                *sptr++ = pl;
398 1
                *sptr++ = pi - 1;
399 1
                pl = pi + 1;
400
            }
401 1
            *psdepth++ = --cdepth;
402
        }
403

404
        /* insertion sort */
405 1
        for (pi = pl + 1; pi <= pr; ++pi) {
406 1
            vi = *pi;
407 1
            vp = v + vi*len;
408 1
            pj = pi;
409 1
            pk = pi - 1;
410 1
            while (pj > pl && @TYPE@_LT(vp, v + (*pk)*len, len)) {
411 1
                *pj-- = *pk--;
412
            }
413 1
            *pj = vi;
414
        }
415 1
stack_pop:
416 1
        if (sptr == stack) {
417
            break;
418
        }
419 1
        pr = *(--sptr);
420 1
        pl = *(--sptr);
421 1
        cdepth = *(--psdepth);
422
    }
423

424
    return 0;
425
}
426

427
/**end repeat**/
428

429

430
/*
431
 *****************************************************************************
432
 **                             GENERIC SORT                                **
433
 *****************************************************************************
434
 */
435

436

437
NPY_NO_EXPORT int
438 1
npy_quicksort(void *start, npy_intp num, void *varr)
439
{
440 1
    PyArrayObject *arr = varr;
441 1
    npy_intp elsize = PyArray_ITEMSIZE(arr);
442 1
    PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
443
    char *vp;
444 1
    char *pl = start;
445 1
    char *pr = pl + (num - 1)*elsize;
446
    char *stack[PYA_QS_STACK];
447 1
    char **sptr = stack;
448
    char *pm, *pi, *pj, *pk;
449
    int depth[PYA_QS_STACK];
450 1
    int * psdepth = depth;
451 1
    int cdepth = npy_get_msb(num) * 2;
452

453
    /* Items that have zero size don't make sense to sort */
454 1
    if (elsize == 0) {
455
        return 0;
456
    }
457

458 1
    vp = malloc(elsize);
459 1
    if (vp == NULL) {
460
        return -NPY_ENOMEM;
461
    }
462

463
    for (;;) {
464 1
        if (NPY_UNLIKELY(cdepth < 0)) {
465 1
            npy_heapsort(pl, (pr - pl) / elsize + 1, varr);
466 1
            goto stack_pop;
467
        }
468 1
        while(pr - pl > SMALL_QUICKSORT*elsize) {
469
            /* quicksort partition */
470 1
            pm = pl + (((pr - pl) / elsize) >> 1) * elsize;
471 1
            if (cmp(pm, pl, arr) < 0) {
472
                GENERIC_SWAP(pm, pl, elsize);
473
            }
474 1
            if (cmp(pr, pm, arr) < 0) {
475
                GENERIC_SWAP(pr, pm, elsize);
476
            }
477 1
            if (cmp(pm, pl, arr) < 0) {
478
                GENERIC_SWAP(pm, pl, elsize);
479
            }
480 1
            GENERIC_COPY(vp, pm, elsize);
481 1
            pi = pl;
482 1
            pj = pr - elsize;
483 1
            GENERIC_SWAP(pm, pj, elsize);
484
            /*
485
             * Generic comparisons may be buggy, so don't rely on the sentinels
486
             * to keep the pointers from going out of bounds.
487
             */
488
            for (;;) {
489
                do {
490 1
                    pi += elsize;
491 1
                } while (cmp(pi, vp, arr) < 0 && pi < pj);
492
                do {
493 1
                    pj -= elsize;
494 1
                } while (cmp(vp, pj, arr) < 0 && pi < pj);
495 1
                if (pi >= pj) {
496
                    break;
497
                }
498
                GENERIC_SWAP(pi, pj, elsize);
499
            }
500
            pk = pr - elsize;
501 1
            GENERIC_SWAP(pi, pk, elsize);
502
            /* push largest partition on stack */
503 1
            if (pi - pl < pr - pi) {
504 1
                *sptr++ = pi + elsize;
505 1
                *sptr++ = pr;
506 1
                pr = pi - elsize;
507
            }
508
            else {
509 1
                *sptr++ = pl;
510 1
                *sptr++ = pi - elsize;
511 1
                pl = pi + elsize;
512
            }
513 1
            *psdepth++ = --cdepth;
514
        }
515

516
        /* insertion sort */
517 1
        for (pi = pl + elsize; pi <= pr; pi += elsize) {
518 1
            GENERIC_COPY(vp, pi, elsize);
519 1
            pj = pi;
520 1
            pk = pi - elsize;
521 1
            while (pj > pl && cmp(vp, pk, arr) < 0) {
522 1
                GENERIC_COPY(pj, pk, elsize);
523 1
                pj -= elsize;
524 1
                pk -= elsize;
525
            }
526 1
            GENERIC_COPY(pj, vp, elsize);
527
        }
528 1
stack_pop:
529 1
        if (sptr == stack) {
530
            break;
531
        }
532 1
        pr = *(--sptr);
533 1
        pl = *(--sptr);
534 1
        cdepth = *(--psdepth);
535
    }
536

537 1
    free(vp);
538 1
    return 0;
539
}
540

541

542
NPY_NO_EXPORT int
543 1
npy_aquicksort(void *vv, npy_intp* tosort, npy_intp num, void *varr)
544
{
545 1
    char *v = vv;
546 1
    PyArrayObject *arr = varr;
547 1
    npy_intp elsize = PyArray_ITEMSIZE(arr);
548 1
    PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare;
549
    char *vp;
550 1
    npy_intp *pl = tosort;
551 1
    npy_intp *pr = tosort + num - 1;
552
    npy_intp *stack[PYA_QS_STACK];
553 1
    npy_intp **sptr = stack;
554
    npy_intp *pm, *pi, *pj, *pk, vi;
555
    int depth[PYA_QS_STACK];
556 1
    int * psdepth = depth;
557 1
    int cdepth = npy_get_msb(num) * 2;
558

559
    /* Items that have zero size don't make sense to sort */
560 1
    if (elsize == 0) {
561
        return 0;
562
    }
563

564
    for (;;) {
565 1
        if (NPY_UNLIKELY(cdepth < 0)) {
566 0
            npy_aheapsort(vv, pl, pr - pl + 1, varr);
567 0
            goto stack_pop;
568
        }
569 1
        while ((pr - pl) > SMALL_QUICKSORT) {
570
            /* quicksort partition */
571 1
            pm = pl + ((pr - pl) >> 1);
572 1
            if (cmp(v + (*pm)*elsize, v + (*pl)*elsize, arr) < 0) {
573 1
                INTP_SWAP(*pm, *pl);
574
            }
575 1
            if (cmp(v + (*pr)*elsize, v + (*pm)*elsize, arr) < 0) {
576 1
                INTP_SWAP(*pr, *pm);
577
            }
578 1
            if (cmp(v + (*pm)*elsize, v + (*pl)*elsize, arr) < 0) {
579 1
                INTP_SWAP(*pm, *pl);
580
            }
581 1
            vp = v + (*pm)*elsize;
582 1
            pi = pl;
583 1
            pj = pr - 1;
584 1
            INTP_SWAP(*pm,*pj);
585 1
            for (;;) {
586
                do {
587 1
                    ++pi;
588 1
                } while (cmp(v + (*pi)*elsize, vp, arr) < 0 && pi < pj);
589
                do {
590 1
                    --pj;
591 1
                } while (cmp(vp, v + (*pj)*elsize, arr) < 0 && pi < pj);
592 1
                if (pi >= pj) {
593
                    break;
594
                }
595 1
                INTP_SWAP(*pi,*pj);
596
            }
597 1
            pk = pr - 1;
598 1
            INTP_SWAP(*pi,*pk);
599
            /* push largest partition on stack */
600 1
            if (pi - pl < pr - pi) {
601 1
                *sptr++ = pi + 1;
602 1
                *sptr++ = pr;
603 1
                pr = pi - 1;
604
            }
605
            else {
606 1
                *sptr++ = pl;
607 1
                *sptr++ = pi - 1;
608 1
                pl = pi + 1;
609
            }
610 1
            *psdepth++ = --cdepth;
611
        }
612

613
        /* insertion sort */
614 1
        for (pi = pl + 1; pi <= pr; ++pi) {
615 1
            vi = *pi;
616 1
            vp = v + vi*elsize;
617 1
            pj = pi;
618 1
            pk = pi - 1;
619 1
            while (pj > pl && cmp(vp, v + (*pk)*elsize, arr) < 0) {
620 1
                *pj-- = *pk--;
621
            }
622 1
            *pj = vi;
623
        }
624 1
stack_pop:
625 1
        if (sptr == stack) {
626
            break;
627
        }
628 1
        pr = *(--sptr);
629 1
        pl = *(--sptr);
630 1
        cdepth = *(--psdepth);
631
    }
632

633
    return 0;
634
}

Read our documentation on viewing source code .

Loading