/*

   +----------------------------------------------------------------------+

   | Zend Engine                                                          |

   +----------------------------------------------------------------------+

   | Copyright (c) Zend Technologies Ltd. (http://www.zend.com)           |

   +----------------------------------------------------------------------+

   | This source file is subject to version 2.00 of the Zend license,     |

   | that is bundled with this package in the file LICENSE, and is        |

   | available through the world-wide-web at the following url:           |

   | http://www.zend.com/license/2_00.txt.                                |

   | If you did not receive a copy of the Zend license and are unable to  |

   | obtain it through the world-wide-web, please send a note to          |

   | license@zend.com so we can mail you a copy immediately.              |

   +----------------------------------------------------------------------+

   | Authors: Xinchen Hui <laruence@php.net>                              |

   |          Sterling Hughes <sterling@php.net>                          |

   +----------------------------------------------------------------------+

*/

#include "zend.h"

#include "zend_sort.h"

#include <limits.h>

static inline void zend_sort_2(void *a, void *b, compare_func_t cmp, swap_func_t swp) /* {{{ */ {

  if (cmp(a, b) > 0) {

    swp(a, b);

  }

}

/* }}} */

static inline void zend_sort_3(void *a, void *b, void *c, compare_func_t cmp, swap_func_t swp) /* {{{ */ {

  if (!(cmp(a, b) > 0)) {

    if (!(cmp(b, c) > 0)) {

      return;

    }

    swp(b, c);

    if (cmp(a, b) > 0) {

      swp(a, b);

    }

    return;

  }

  if (!(cmp(c, b) > 0)) {

    swp(a, c);

    return;

  }

  swp(a, b);

  if (cmp(b, c) > 0) {

    swp(b, c);

  }

}

/* }}} */

static void zend_sort_4(void *a, void *b, void *c, void *d, compare_func_t cmp, swap_func_t swp) /* {{{ */ {

  zend_sort_3(a, b, c, cmp, swp);

  if (cmp(c, d) > 0) {

    swp(c, d);

    if (cmp(b, c) > 0) {

      swp(b, c);

      if (cmp(a, b) > 0) {

        swp(a, b);

      }

    }

  }

}

/* }}} */

static void zend_sort_5(void *a, void *b, void *c, void *d, void *e, compare_func_t cmp, swap_func_t swp) /* {{{ */ {

  zend_sort_4(a, b, c, d, cmp, swp);

  if (cmp(d, e) > 0) {

    swp(d, e);

    if (cmp(c, d) > 0) {

      swp(c, d);

      if (cmp(b, c) > 0) {

        swp(b, c);

        if (cmp(a, b) > 0) {

          swp(a, b);

        }

      }

    }

  }

}

/* }}} */

ZEND_API void zend_insert_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) /* {{{ */{

  switch (nmemb) {

    case 0:

    case 1:

      break;

    case 2:

      zend_sort_2(base, (char *)base + siz, cmp, swp);

      break;

    case 3:

      zend_sort_3(base, (char *)base + siz, (char *)base + siz + siz, cmp, swp);

      break;

    case 4:

      {

        size_t siz2 = siz + siz;

        zend_sort_4(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, cmp, swp);

      }

      break;

    case 5:

      {

        size_t siz2 = siz + siz;

        zend_sort_5(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, (char *)base + siz2 + siz2, cmp, swp);

      }

      break;

    default:

      {

        char *i, *j, *k;

        char *start = (char *)base;

        char *end = start + (nmemb * siz);

        size_t siz2= siz + siz;

        char *sentry = start + (6 * siz);

        for (i = start + siz; i < sentry; i += siz) {

          j = i - siz;

          if (!(cmp(j, i) > 0)) {

            continue;

          }

          while (j != start) {

            j -= siz;

            if (!(cmp(j, i) > 0)) {

              j += siz;

              break;

            }

          }

          for (k = i; k > j; k -= siz) {

            swp(k, k - siz);

          }

        }

        for (i = sentry; i < end; i += siz) {

          j = i - siz;

          if (!(cmp(j, i) > 0)) {

            continue;

          }

          do {

            j -= siz2;

            if (!(cmp(j, i) > 0)) {

              j += siz;

              if (!(cmp(j, i) > 0)) {

                j += siz;

              }

              break;

            }

            if (j == start) {

              break;

            }

            if (j == start + siz) {

              j -= siz;

              if (cmp(i, j) > 0) {

                j += siz;

              }

              break;

            }

          } while (1);

          for (k = i; k > j; k -= siz) {

            swp(k, k - siz);

          }

        }

      }

      break;

  }

}

/* }}} */

/* {{{ ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp)

 *

 * Derived from LLVM's libc++ implementation of std::sort.

 *

 * ===========================================================================

 * libc++ License

 * ===========================================================================

 *

 * The libc++ library is dual licensed under both the University of Illinois

 * "BSD-Like" license and the MIT license. As a user of this code you may

 * choose to use it under either license. As a contributor, you agree to allow

 * your code to be used under both.

 *

 * Full text of the relevant licenses is included below.

 *

 * ===========================================================================

 *

 * University of Illinois/NCSA

 * Open Source License

 *

 * Copyright (c) 2009-2012 by the contributors listed at

 * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT

 *

 * All rights reserved.

 *

 * Developed by:

 *

 *     LLVM Team

 *

 *     University of Illinois at Urbana-Champaign

 *

 *     http://llvm.org

 *

 * Permission is hereby granted, free of charge, to any person obtaining a copy

 * of this software and associated documentation files (the "Software"), to

 * deal with the Software without restriction, including without limitation the

 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or

 * sell copies of the Software, and to permit persons to whom the Software is

 * furnished to do so, subject to the following conditions:

 *

 *     * Redistributions of source code must retain the above copyright notice,

 *       this list of conditions and the following disclaimers.

 *

 *     * Redistributions in binary form must reproduce the above copyright

 *       notice, this list of conditions and the following disclaimers in the

 *       documentation and/or other materials provided with the distribution.

 *

 *     * Neither the names of the LLVM Team, University of Illinois at

 *       Urbana-Champaign, nor the names of its contributors may be used to

 *       endorse or promote products derived from this Software without

 *       specific prior written permission.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

 * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS

 * WITH THE SOFTWARE.

 *

 * ===========================================================================

 *

 * Copyright (c) 2009-2012 by the contributors listed at

 * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT

 *

 * Permission is hereby granted, free of charge, to any person obtaining a copy

 * of this software and associated documentation files (the "Software"), to

 * deal in the Software without restriction, including without limitation the

 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or

 * sell copies of the Software, and to permit persons to whom the Software is

 * furnished to do so, subject to the following conditions:

 *

 * The above copyright notice and this permission notice shall be included in

 * all copies or substantial portions of the Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS

 * IN THE SOFTWARE.

 */

ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp)

{

  while (1) {

    if (nmemb <= 16) {

      zend_insert_sort(base, nmemb, siz, cmp, swp);

      return;

    } else {

      char *i, *j;

      char *start = (char *)base;

      char *end = start + (nmemb * siz);

      size_t offset = (nmemb >> Z_L(1));

      char *pivot = start + (offset * siz);

      if ((nmemb >> Z_L(10))) {

        size_t delta = (offset >> Z_L(1)) * siz;

        zend_sort_5(start, start + delta, pivot, pivot + delta, end - siz, cmp, swp);

      } else {

        zend_sort_3(start, pivot, end - siz, cmp, swp);

      }

      swp(start + siz, pivot);

      pivot = start + siz;

      i = pivot + siz;

      j = end - siz;

      while (1) {

        while (cmp(pivot, i) > 0) {

          i += siz;

          if (UNEXPECTED(i == j)) {

            goto done;

          }

        }

        j -= siz;

        if (UNEXPECTED(j == i)) {

          goto done;

        }

        while (cmp(j, pivot) > 0) {

          j -= siz;

          if (UNEXPECTED(j == i)) {

            goto done;

          }

        }

        swp(i, j);

        i += siz;

        if (UNEXPECTED(i == j)) {

          goto done;

        }

      }

done:

      swp(pivot, i - siz);

      if ((i - siz) - start < end - i) {

        zend_sort(start, (i - start)/siz - 1, siz, cmp, swp);

        base = i;

        nmemb = (end - i)/siz;

      } else {

        zend_sort(i, (end - i)/siz, siz, cmp, swp);

        nmemb = (i - start)/siz - 1;

      }

    }

  }

}

/* }}} */