Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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. _cairo_combsort_newgap (unsigned int gap)
  40. {
  41.   gap = 10 * gap / 13;
  42.   if (gap == 9 || gap == 10)
  43.     gap = 11;
  44.   if (gap < 1)
  45.     gap = 1;
  46.   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. }
  72.  
  73. #define CAIRO_COMBSORT_DECLARE_WITH_DATA(NAME, TYPE, CMP) \
  74. static void \
  75. NAME (TYPE *base, unsigned int nmemb, void *data) \
  76. { \
  77.   unsigned int gap = nmemb; \
  78.   unsigned int i, j; \
  79.   int swapped; \
  80.   do { \
  81.       gap = _cairo_combsort_newgap (gap); \
  82.       swapped = gap > 1; \
  83.       for (i = 0; i < nmemb-gap ; i++) { \
  84.           j = i + gap; \
  85.           if (CMP (base[i], base[j], data) > 0 ) { \
  86.               TYPE tmp; \
  87.               tmp = base[i]; \
  88.               base[i] = base[j]; \
  89.               base[j] = tmp; \
  90.               swapped = 1; \
  91.           } \
  92.       } \
  93.   } while (swapped); \
  94. }
  95.