1                 : /*
       2                 :    +----------------------------------------------------------------------+
       3                 :    | Zend Engine                                                          |
       4                 :    +----------------------------------------------------------------------+
       5                 :    | Copyright (c) 1998-2007 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,v 1.8.2.1.2.1 2007/01/01 09:35:47 sebastian Exp $ */
      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             490 : {
      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             490 :         tmp_a_int = (int *) a;
      38             490 :         tmp_b_int = (int *) b;
      39                 : 
      40            1219 :         for (i = sizeof(int); i <= siz; i += sizeof(int)) {
      41             729 :                 t_i = *tmp_a_int;
      42             729 :                 *tmp_a_int++ = *tmp_b_int;
      43             729 :                 *tmp_b_int++ = t_i;
      44                 :         }
      45                 : 
      46             490 :         tmp_a_char = (char *) tmp_a_int;
      47             490 :         tmp_b_char = (char *) tmp_b_int;
      48                 : 
      49             490 :         for (i = i - sizeof(int) + 1; i <= siz; ++i) {
      50               0 :                 t_c = *tmp_a_char;
      51               0 :                 *tmp_a_char++ = *tmp_b_char;
      52               0 :                 *tmp_b_char++ = t_c;
      53                 :         }
      54             490 : }
      55                 : 
      56                 : ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC)
      57               8 : {
      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               8 :         begin_stack[0] = (char *) base;
      69               8 :         end_stack[0]   = (char *) base + ((nmemb - 1) * siz);
      70                 : 
      71             112 :         for (loop = 0; loop >= 0; --loop) {
      72             104 :                 begin = begin_stack[loop];
      73             104 :                 end   = end_stack[loop];
      74                 : 
      75             356 :                 while (begin < end) {
      76             148 :                         offset = (end - begin) >> 1;
      77             148 :                         _zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);
      78                 : 
      79             148 :                         seg1 = begin + siz;
      80             148 :                         seg2 = end;
      81                 : 
      82                 :                         while (1) {
      83            1352 :                                 for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;
      84             668 :                                      seg1 += siz);
      85                 : 
      86            1058 :                                 for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;
      87             374 :                                      seg2 -= siz);
      88                 :                                 
      89             342 :                                 if (seg1 >= seg2)
      90             148 :                                         break;
      91                 :                                 
      92             194 :                                 _zend_qsort_swap(seg1, seg2, siz);
      93                 : 
      94             194 :                                 seg1 += siz;
      95             194 :                                 seg2 -= siz;
      96             194 :                         }
      97                 : 
      98             148 :                         _zend_qsort_swap(begin, seg2, siz);
      99                 : 
     100             148 :                         seg2p = seg2;
     101                 :                         
     102             148 :                         if ((seg2p - begin) <= (end - seg2p)) {
     103              86 :                                 if ((seg2p + siz) < end) {
     104              52 :                                         begin_stack[loop] = seg2p + siz;
     105              52 :                                         end_stack[loop++] = end;
     106                 :                                 }
     107              86 :                                 end = seg2p - siz;
     108                 :                         }
     109                 :                         else {
     110              62 :                                 if ((seg2p - siz) > begin) {
     111              44 :                                         begin_stack[loop] = begin;
     112              44 :                                         end_stack[loop++] = seg2p - siz;
     113                 :                                 }
     114              62 :                                 begin = seg2p + siz;
     115                 :                         }
     116                 :                 }
     117                 :         }
     118               8 : }
     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                 :  */