src/borast/borast-combsort-private.h

   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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 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_BORAST_COMBSORT_NEWGAP
  37 #define _HAVE_BORAST_COMBSORT_NEWGAP
  38 static inline unsigned int
  39 _borast_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 BORAST_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 = _borast_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 }