Line data    Source code

       1             : /*
       2             :  * Copyright © 2008 Chris Wilson
       3             :  *
       4             :  * This library is free software; you can redistribute it and/or
       5             :  * modify it either under the terms of the GNU Lesser General Public
       6             :  * License version 2.1 as published by the Free Software Foundation
       7             :  * (the "LGPL") or, at your option, under the terms of the Mozilla
       8             :  * Public License Version 1.1 (the "MPL"). If you do not alter this
       9             :  * notice, a recipient may use your version of this file under either
      10             :  * the MPL or the LGPL.
      11             :  *
      12             :  * You should have received a copy of the LGPL along with this library
      13             :  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
      14             :  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA
      15             :  * You should have received a copy of the MPL along with this library
      16             :  * in the file COPYING-MPL-1.1
      17             :  *
      18             :  * The contents of this file are subject to the Mozilla Public License
      19             :  * Version 1.1 (the "License"); you may not use this file except in
      20             :  * compliance with the License. You may obtain a copy of the License at
      21             :  * http://www.mozilla.org/MPL/
      22             :  *
      23             :  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
      24             :  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
      25             :  * the specific language governing rights and limitations.
      26             :  *
      27             :  * The Original Code is the cairo graphics library.
      28             :  *
      29             :  * The Initial Developer of the Original Code is Chris Wilson
      30             :  *
      31             :  * Contributor(s):
      32             :  *      Chris Wilson <chris@chris-wilson.co.uk>
      33             :  */
      34             : 
      35             : /* This fragment implements a comb sort (specifically combsort11) */
      36             : #ifndef _HAVE_CAIRO_COMBSORT_NEWGAP
      37             : #define _HAVE_CAIRO_COMBSORT_NEWGAP
      38             : static inline unsigned int
      39           0 : _cairo_combsort_newgap (unsigned int gap)
      40             : {
      41           0 :   gap = 10 * gap / 13;
      42           0 :   if (gap == 9 || gap == 10)
      43           0 :     gap = 11;
      44           0 :   if (gap < 1)
      45           0 :     gap = 1;
      46           0 :   return gap;
      47             : }
      48             : #endif
      49             : 
      50             : #define CAIRO_COMBSORT_DECLARE(NAME, TYPE, CMP) \
      51             : static void \
      52             : NAME (TYPE *base, unsigned int nmemb) \
      53             : { \
      54             :   unsigned int gap = nmemb; \
      55             :   unsigned int i, j; \
      56             :   int swapped; \
      57             :   do { \
      58             :       gap = _cairo_combsort_newgap (gap); \
      59             :       swapped = gap > 1; \
      60             :       for (i = 0; i < nmemb-gap ; i++) { \
      61             :           j = i + gap; \
      62             :           if (CMP (base[i], base[j]) > 0 ) { \
      63             :               TYPE tmp; \
      64             :               tmp = base[i]; \
      65             :               base[i] = base[j]; \
      66             :               base[j] = tmp; \
      67             :               swapped = 1; \
      68             :           } \
      69             :       } \
      70             :   } while (swapped); \
      71             : }