Return to zend_qsort.c CVS log

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

5.4.17

    1: /*
    2:    +----------------------------------------------------------------------+
    3:    | Zend Engine                                                          |
    4:    +----------------------------------------------------------------------+
    5:    | Copyright (c) 1998-2013 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.1.1.3 2013/07/22 01:32:16 misho 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: {
   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:  */