hphp/runtime/base/zend-qsort.cpp

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    | Copyright (c) 1998-2010 Zend Technologies Ltd. (http://www.zend.com) |
   7    +----------------------------------------------------------------------+
   8    | This source file is subject to version 2.00 of the Zend license,     |
   9    | that is bundled with this package in the file LICENSE, and is        |
  10    | available through the world-wide-web at the following url:           |
  11    | http://www.zend.com/license/2_00.txt.                                |
  12    | If you did not receive a copy of the Zend license and are unable to  |
  13    | obtain it through the world-wide-web, please send a note to          |
  14    | license@zend.com so we can mail you a copy immediately.              |
  15    +----------------------------------------------------------------------+
  16 */
  17
  18 #include "hphp/runtime/base/zend-qsort.h"
  19
  20 namespace HPHP {
  21 ///////////////////////////////////////////////////////////////////////////////
  22
  23 #define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT)
  24
  25 void _zend_qsort_swap(void *a, void *b, size_t siz) {
  26   register char  *tmp_a_char;
  27   register char  *tmp_b_char;
  28   register int   *tmp_a_int;
  29   register int   *tmp_b_int;
  30   register size_t i;
  31   int             t_i;
  32   char            t_c;
  33
  34   tmp_a_int = (int *) a;
  35   tmp_b_int = (int *) b;
  36
  37   for (i = sizeof(int); i <= siz; i += sizeof(int)) {
  38     t_i = *tmp_a_int;
  39     *tmp_a_int++ = *tmp_b_int;
  40     *tmp_b_int++ = t_i;
  41   }
  42
  43   tmp_a_char = (char *) tmp_a_int;
  44   tmp_b_char = (char *) tmp_b_int;
  45
  46   for (i = i - sizeof(int) + 1; i <= siz; ++i) {
  47     t_c = *tmp_a_char;
  48     *tmp_a_char++ = *tmp_b_char;
  49     *tmp_b_char++ = t_c;
  50   }
  51 }
  52
  53 void zend_qsort(void *base, size_t nmemb, size_t siz,
  54                 compare_func_t compare, void *opaque) {
  55   void           *begin_stack[QSORT_STACK_SIZE];
  56   void           *end_stack[QSORT_STACK_SIZE];
  57   register char  *begin;
  58   register char  *end;
  59   register char  *seg1;
  60   register char  *seg2;
  61   register char  *seg2p;
  62   register int    loop;
  63   unsigned int    offset;
  64
  65   begin_stack[0] = (char *) base;
  66   end_stack[0]   = (char *) base + ((nmemb - 1) * siz);
  67
  68   for (loop = 0; loop >= 0; --loop) {
  69     begin = (char*)begin_stack[loop];
  70     end   = (char*)end_stack[loop];
  71
  72     while (begin < end) {
  73       offset = (end - begin) >> 1;
  74       _zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);
  75
  76       seg1 = begin + siz;
  77       seg2 = end;
  78
  79       while (1) {
  80         for (; seg1 < seg2 && compare(begin, seg1, opaque) > 0;
  81              seg1 += siz);
  82
  83         for (; seg2 >= seg1 && compare(seg2, begin, opaque) > 0;
  84              seg2 -= siz);
  85
  86         if (seg1 >= seg2)
  87           break;
  88
  89         _zend_qsort_swap(seg1, seg2, siz);
  90
  91         seg1 += siz;
  92         seg2 -= siz;
  93       }
  94
  95       _zend_qsort_swap(begin, seg2, siz);
  96
  97       seg2p = seg2;
  98
  99       if ((seg2p - begin) <= (end - seg2p)) {
 100         if ((seg2p + siz) < end) {
 101           begin_stack[loop] = seg2p + siz;
 102           end_stack[loop++] = end;
 103         }
 104         end = seg2p - siz;
 105       }
 106       else {
 107         if ((seg2p - siz) > begin) {
 108           begin_stack[loop] = begin;
 109           end_stack[loop++] = seg2p - siz;
 110         }
 111         begin = seg2p + siz;
 112       }
 113     }
 114   }
 115 }
 116
 117 ///////////////////////////////////////////////////////////////////////////////
 118 }