Home | History | Annotate | Line # | Download | only in Zend 
      1 /*
      2    +----------------------------------------------------------------------+
      3    | Zend Engine                                                          |
      4    +----------------------------------------------------------------------+
      5    | Copyright (c) 1998-2012 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 (at) zend.com so we can mail you a copy immediately.              |
     14    +----------------------------------------------------------------------+
     15    | Authors: Sterling Hughes <sterling (at) php.net>                          |
     16    +----------------------------------------------------------------------+
     17 */
     18 
     19 /* $Id: zend_qsort.c 321634 2012-01-01 13:15:04Z felipe $ */
     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  */
    128