Return to zend_qsort.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / Zend

Annotation of embedaddon/php/Zend/zend_qsort.c, revision 1.1.1.3

1.1       misho       1: /*
                      2:    +----------------------------------------------------------------------+
                      3:    | Zend Engine                                                          |
                      4:    +----------------------------------------------------------------------+
1.1.1.3 ! misho       5:    | Copyright (c) 1998-2013 Zend Technologies Ltd. (http://www.zend.com) |
1.1       misho       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: Sterling Hughes <sterling@php.net>                          |
                     16:    +----------------------------------------------------------------------+
                     17: */
                     18: 
1.1.1.2   misho      19: /* $Id$ */
1.1       misho      20: 
                     21: #include "zend.h"
                     22: 
                     23: #include <limits.h>
                     24: 
                     25: #define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT)
                     26: 
                     27: static void _zend_qsort_swap(void *a, void *b, size_t siz)
                     28: {
                     29:        register char  *tmp_a_char;
                     30:        register char  *tmp_b_char;
                     31:        register int   *tmp_a_int;
                     32:        register int   *tmp_b_int;
                     33:        register size_t i;
                     34:        int             t_i;
                     35:        char            t_c;
                     36: 
                     37:        tmp_a_int = (int *) a;
                     38:        tmp_b_int = (int *) b;
                     39: 
                     40:        for (i = sizeof(int); i <= siz; i += sizeof(int)) {
                     41:                t_i = *tmp_a_int;
                     42:                *tmp_a_int++ = *tmp_b_int;
                     43:                *tmp_b_int++ = t_i;
                     44:        }
                     45: 
                     46:        tmp_a_char = (char *) tmp_a_int;
                     47:        tmp_b_char = (char *) tmp_b_int;
                     48: 
                     49:        for (i = i - sizeof(int) + 1; i <= siz; ++i) {
                     50:                t_c = *tmp_a_char;
                     51:                *tmp_a_char++ = *tmp_b_char;
                     52:                *tmp_b_char++ = t_c;
                     53:        }
                     54: }
                     55: 
                     56: ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC)
                     57: {
                     58:        void           *begin_stack[QSORT_STACK_SIZE];
                     59:        void           *end_stack[QSORT_STACK_SIZE];
                     60:        register char  *begin;
                     61:        register char  *end;
                     62:        register char  *seg1;
                     63:        register char  *seg2;
                     64:        register char  *seg2p;
                     65:        register int    loop;
                     66:        uint            offset;
                     67: 
                     68:        begin_stack[0] = (char *) base;
                     69:        end_stack[0]   = (char *) base + ((nmemb - 1) * siz);
                     70: 
                     71:        for (loop = 0; loop >= 0; --loop) {
                     72:                begin = begin_stack[loop];
                     73:                end   = end_stack[loop];
                     74: 
                     75:                while (begin < end) {
                     76:                        offset = (end - begin) >> 1;
                     77:                        _zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);
                     78: 
                     79:                        seg1 = begin + siz;
                     80:                        seg2 = end;
                     81: 
                     82:                        while (1) {
                     83:                                for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;
                     84:                                     seg1 += siz);
                     85: 
                     86:                                for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;
                     87:                                     seg2 -= siz);
                     88:                                
                     89:                                if (seg1 >= seg2)
                     90:                                        break;
                     91:                                
                     92:                                _zend_qsort_swap(seg1, seg2, siz);
                     93: 
                     94:                                seg1 += siz;
                     95:                                seg2 -= siz;
                     96:                        }
                     97: 
                     98:                        _zend_qsort_swap(begin, seg2, siz);
                     99: 
                    100:                        seg2p = seg2;
                    101:                        
                    102:                        if ((seg2p - begin) <= (end - seg2p)) {
                    103:                                if ((seg2p + siz) < end) {
                    104:                                        begin_stack[loop] = seg2p + siz;
                    105:                                        end_stack[loop++] = end;
                    106:                                }
                    107:                                end = seg2p - siz;
                    108:                        }
                    109:                        else {
                    110:                                if ((seg2p - siz) > begin) {
                    111:                                        begin_stack[loop] = begin;
                    112:                                        end_stack[loop++] = seg2p - siz;
                    113:                                }
                    114:                                begin = seg2p + siz;
                    115:                        }
                    116:                }
                    117:        }
                    118: }
                    119: 
                    120: /* 
                    121:  * Local Variables:
                    122:  * c-basic-offset: 4 
                    123:  * tab-width: 4
                    124:  * End:
                    125:  * vim600: fdm=marker
                    126:  * vim: noet sw=4 ts=4
                    127:  */