Back to index

php5  5.3.10
zend_qsort.c
Go to the documentation of this file.
00001 /*
00002    +----------------------------------------------------------------------+
00003    | Zend Engine                                                          |
00004    +----------------------------------------------------------------------+
00005    | Copyright (c) 1998-2012 Zend Technologies Ltd. (http://www.zend.com) |
00006    +----------------------------------------------------------------------+
00007    | This source file is subject to version 2.00 of the Zend license,     |
00008    | that is bundled with this package in the file LICENSE, and is        | 
00009    | available through the world-wide-web at the following url:           |
00010    | http://www.zend.com/license/2_00.txt.                                |
00011    | If you did not receive a copy of the Zend license and are unable to  |
00012    | obtain it through the world-wide-web, please send a note to          |
00013    | license@zend.com so we can mail you a copy immediately.              |
00014    +----------------------------------------------------------------------+
00015    | Authors: Sterling Hughes <sterling@php.net>                          |
00016    +----------------------------------------------------------------------+
00017 */
00018 
00019 /* $Id: zend_qsort.c 321634 2012-01-01 13:15:04Z felipe $ */
00020 
00021 #include "zend.h"
00022 
00023 #include <limits.h>
00024 
00025 #define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT)
00026 
00027 static void _zend_qsort_swap(void *a, void *b, size_t siz)
00028 {
00029        register char  *tmp_a_char;
00030        register char  *tmp_b_char;
00031        register int   *tmp_a_int;
00032        register int   *tmp_b_int;
00033        register size_t i;
00034        int             t_i;
00035        char            t_c;
00036 
00037        tmp_a_int = (int *) a;
00038        tmp_b_int = (int *) b;
00039 
00040        for (i = sizeof(int); i <= siz; i += sizeof(int)) {
00041               t_i = *tmp_a_int;
00042               *tmp_a_int++ = *tmp_b_int;
00043               *tmp_b_int++ = t_i;
00044        }
00045 
00046        tmp_a_char = (char *) tmp_a_int;
00047        tmp_b_char = (char *) tmp_b_int;
00048 
00049        for (i = i - sizeof(int) + 1; i <= siz; ++i) {
00050               t_c = *tmp_a_char;
00051               *tmp_a_char++ = *tmp_b_char;
00052               *tmp_b_char++ = t_c;
00053        }
00054 }
00055 
00056 ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC)
00057 {
00058        void           *begin_stack[QSORT_STACK_SIZE];
00059        void           *end_stack[QSORT_STACK_SIZE];
00060        register char  *begin;
00061        register char  *end;
00062        register char  *seg1;
00063        register char  *seg2;
00064        register char  *seg2p;
00065        register int    loop;
00066        uint            offset;
00067 
00068        begin_stack[0] = (char *) base;
00069        end_stack[0]   = (char *) base + ((nmemb - 1) * siz);
00070 
00071        for (loop = 0; loop >= 0; --loop) {
00072               begin = begin_stack[loop];
00073               end   = end_stack[loop];
00074 
00075               while (begin < end) {
00076                      offset = (end - begin) >> 1;
00077                      _zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);
00078 
00079                      seg1 = begin + siz;
00080                      seg2 = end;
00081 
00082                      while (1) {
00083                             for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;
00084                                  seg1 += siz);
00085 
00086                             for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;
00087                                  seg2 -= siz);
00088                             
00089                             if (seg1 >= seg2)
00090                                    break;
00091                             
00092                             _zend_qsort_swap(seg1, seg2, siz);
00093 
00094                             seg1 += siz;
00095                             seg2 -= siz;
00096                      }
00097 
00098                      _zend_qsort_swap(begin, seg2, siz);
00099 
00100                      seg2p = seg2;
00101                      
00102                      if ((seg2p - begin) <= (end - seg2p)) {
00103                             if ((seg2p + siz) < end) {
00104                                    begin_stack[loop] = seg2p + siz;
00105                                    end_stack[loop++] = end;
00106                             }
00107                             end = seg2p - siz;
00108                      }
00109                      else {
00110                             if ((seg2p - siz) > begin) {
00111                                    begin_stack[loop] = begin;
00112                                    end_stack[loop++] = seg2p - siz;
00113                             }
00114                             begin = seg2p + siz;
00115                      }
00116               }
00117        }
00118 }
00119 
00120 /* 
00121  * Local Variables:
00122  * c-basic-offset: 4 
00123  * tab-width: 4
00124  * End:
00125  * vim600: fdm=marker
00126  * vim: noet sw=4 ts=4
00127  */