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