/*

 * Copyright © 2008 Chris Wilson

 *

 * This library is free software; you can redistribute it and/or

 * modify it either under the terms of the GNU Lesser General Public

 * License version 2.1 as published by the Free Software Foundation

 * (the "LGPL") or, at your option, under the terms of the Mozilla

 * Public License Version 1.1 (the "MPL"). If you do not alter this

 * notice, a recipient may use your version of this file under either

 * the MPL or the LGPL.

 *

 * You should have received a copy of the LGPL along with this library

 * in the file COPYING-LGPL-2.1; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA

 * You should have received a copy of the MPL along with this library

 * in the file COPYING-MPL-1.1

 *

 * The contents of this file are subject to the Mozilla Public License

 * Version 1.1 (the "License"); you may not use this file except in

 * compliance with the License. You may obtain a copy of the License at

 * http://www.mozilla.org/MPL/

 *

 * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY

 * OF ANY KIND, either express or implied. See the LGPL or the MPL for

 * the specific language governing rights and limitations.

 *

 * The Original Code is the cairo graphics library.

 *

 * The Initial Developer of the Original Code is Chris Wilson

 *

 * Contributor(s):

 *  Chris Wilson <chris@chris-wilson.co.uk>

 */

/* This fragment implements a comb sort (specifically combsort11) */

#ifndef _HAVE_CAIRO_COMBSORT_NEWGAP

#define _HAVE_CAIRO_COMBSORT_NEWGAP

static inline unsigned int

_cairo_combsort_newgap (unsigned int gap)

{

  gap = 10 * gap / 13;

  if (gap == 9 || gap == 10)

    gap = 11;

  if (gap < 1)

    gap = 1;

  return gap;

}

Unexecuted instantiation: cairo-recording-surface.c:_cairo_combsort_newgap

cairo-bentley-ottmann-rectangular.c:_cairo_combsort_newgap

Line

Count

Source

40

3.77k

{

41

3.77k

  gap = 10 * gap / 13;

42

3.77k

  if (gap == 9 || gap == 10)

43

199

    gap = 11;

44

3.77k

  if (gap < 1)

45

605

    gap = 1;

46

3.77k

  return gap;

47

3.77k

}

cairo-bentley-ottmann-rectilinear.c:_cairo_combsort_newgap

Line

Count

Source

40

2.89k

{

41

2.89k

  gap = 10 * gap / 13;

42

2.89k

  if (gap == 9 || gap == 10)

43

6

    gap = 11;

44

2.89k

  if (gap < 1)

45

347

    gap = 1;

46

2.89k

  return gap;

47

2.89k

}

Unexecuted instantiation: cairo-bentley-ottmann.c:_cairo_combsort_newgap

Unexecuted instantiation: cairo-boxes-intersect.c:_cairo_combsort_newgap

Unexecuted instantiation: cairo-contour.c:_cairo_combsort_newgap

cairo-polygon-intersect.c:_cairo_combsort_newgap

Line

Count

Source

40

21.2k

{

41

21.2k

  gap = 10 * gap / 13;

42

21.2k

  if (gap == 9 || gap == 10)

43

180

    gap = 11;

44

21.2k

  if (gap < 1)

45

2.63k

    gap = 1;

46

21.2k

  return gap;

47

21.2k

}

cairo-polygon-reduce.c:_cairo_combsort_newgap

Line

Count

Source

40

1.92k

{

41

1.92k

  gap = 10 * gap / 13;

42

1.92k

  if (gap == 9 || gap == 10)

43

56

    gap = 11;

44

1.92k

  if (gap < 1)

45

177

    gap = 1;

46

1.92k

  return gap;

47

1.92k

}

cairo-rectangular-scan-converter.c:_cairo_combsort_newgap

Line

Count

Source

40

886

{

41

886

  gap = 10 * gap / 13;

42

886

  if (gap == 9 || gap == 10)

43

0

    gap = 11;

44

886

  if (gap < 1)

45

126

    gap = 1;

46

886

  return gap;

47

886

}

#endif

#define CAIRO_COMBSORT_DECLARE(NAME, TYPE, CMP) \

static void \

NAME (TYPE *base, unsigned int nmemb) \

{ \

  unsigned int gap = nmemb; \

  unsigned int i, j; \

  int swapped; \

  do { \

      gap = _cairo_combsort_newgap (gap); \

      swapped = gap > 1; \

      for (i = 0; i < nmemb-gap ; i++) { \

    j = i + gap; \

    if (CMP (base[i], base[j]) > 0 ) { \

        TYPE tmp; \

        tmp = base[i]; \

        base[i] = base[j]; \

        base[j] = tmp; \

        swapped = 1; \

    } \

      } \

  } while (swapped); \

}

Unexecuted instantiation: cairo-recording-surface.c:sort_indices

cairo-bentley-ottmann-rectangular.c:_rectangle_sort

Line

Count

Source

52

729

NAME (TYPE *base, unsigned int nmemb) \

53

729

{ \

54

729

  unsigned int gap = nmemb; \

55

729

  unsigned int i, j; \

56

729

  int swapped; \

57

3.77k

  do { \

58

3.77k

      gap = _cairo_combsort_newgap (gap); \

59

3.77k

      swapped = gap > 1; \

60

78.1k

      for (i = 0; i < nmemb-gap ; i++) { \

61

74.3k

    j = i + gap; \

62

74.3k

    if (CMP (base[i], base[j]) > 0 ) { \

63

7.96k

        TYPE tmp; \

64

7.96k

        tmp = base[i]; \

65

7.96k

        base[i] = base[j]; \

66

7.96k

        base[j] = tmp; \

67

7.96k

        swapped = 1; \

68

7.96k

    } \

69

74.3k

      } \

70

3.77k

  } while (swapped); \

71

729

}

cairo-bentley-ottmann-rectilinear.c:_cairo_bo_event_queue_sort

Line

Count

Source

52

347

NAME (TYPE *base, unsigned int nmemb) \

53

347

{ \

54

347

  unsigned int gap = nmemb; \

55

347

  unsigned int i, j; \

56

347

  int swapped; \

57

2.89k

  do { \

58

2.89k

      gap = _cairo_combsort_newgap (gap); \

59

2.89k

      swapped = gap > 1; \

60

64.9k

      for (i = 0; i < nmemb-gap ; i++) { \

61

62.0k

    j = i + gap; \

62

62.0k

    if (CMP (base[i], base[j]) > 0 ) { \

63

13.3k

        TYPE tmp; \

64

13.3k

        tmp = base[i]; \

65

13.3k

        base[i] = base[j]; \

66

13.3k

        base[j] = tmp; \

67

13.3k

        swapped = 1; \

68

13.3k

    } \

69

62.0k

      } \

70

2.89k

  } while (swapped); \

71

347

}

Unexecuted instantiation: cairo-bentley-ottmann.c:_cairo_bo_event_queue_sort

Unexecuted instantiation: cairo-boxes-intersect.c:_rectangle_sort

cairo-polygon-intersect.c:_cairo_bo_event_queue_sort

Line

Count

Source

52

2.75k

NAME (TYPE *base, unsigned int nmemb) \

53

2.75k

{ \

54

2.75k

  unsigned int gap = nmemb; \

55

2.75k

  unsigned int i, j; \

56

2.75k

  int swapped; \

57

21.2k

  do { \

58

21.2k

      gap = _cairo_combsort_newgap (gap); \

59

21.2k

      swapped = gap > 1; \

60

26.7M

      for (i = 0; i < nmemb-gap ; i++) { \

61

26.7M

    j = i + gap; \

62

26.7M

    if (CMP (base[i], base[j]) > 0 ) { \

63

1.80M

        TYPE tmp; \

64

1.80M

        tmp = base[i]; \

65

1.80M

        base[i] = base[j]; \

66

1.80M

        base[j] = tmp; \

67

1.80M

        swapped = 1; \

68

1.80M

    } \

69

26.7M

      } \

70

21.2k

  } while (swapped); \

71

2.75k

}

cairo-polygon-reduce.c:_cairo_bo_event_queue_sort

Line

Count

Source

52

144

NAME (TYPE *base, unsigned int nmemb) \

53

144

{ \

54

144

  unsigned int gap = nmemb; \

55

144

  unsigned int i, j; \

56

144

  int swapped; \

57

1.92k

  do { \

58

1.92k

      gap = _cairo_combsort_newgap (gap); \

59

1.92k

      swapped = gap > 1; \

60

11.3M

      for (i = 0; i < nmemb-gap ; i++) { \

61

11.3M

    j = i + gap; \

62

11.3M

    if (CMP (base[i], base[j]) > 0 ) { \

63

965k

        TYPE tmp; \

64

965k

        tmp = base[i]; \

65

965k

        base[i] = base[j]; \

66

965k

        base[j] = tmp; \

67

965k

        swapped = 1; \

68

965k

    } \

69

11.3M

      } \

70

1.92k

  } while (swapped); \

71

144

}

cairo-rectangular-scan-converter.c:rectangle_sort

Line

Count

Source

52

332

NAME (TYPE *base, unsigned int nmemb) \

53

332

{ \

54

332

  unsigned int gap = nmemb; \

55

332

  unsigned int i, j; \

56

332

  int swapped; \

57

886

  do { \

58

886

      gap = _cairo_combsort_newgap (gap); \

59

886

      swapped = gap > 1; \

60

567k

      for (i = 0; i < nmemb-gap ; i++) { \

61

566k

    j = i + gap; \

62

566k

    if (CMP (base[i], base[j]) > 0 ) { \

63

59.8k

        TYPE tmp; \

64

59.8k

        tmp = base[i]; \

65

59.8k

        base[i] = base[j]; \

66

59.8k

        base[j] = tmp; \

67

59.8k

        swapped = 1; \

68

59.8k

    } \

69

566k

      } \

70

886

  } while (swapped); \

71

332

}

#define CAIRO_COMBSORT_DECLARE_WITH_DATA(NAME, TYPE, CMP) \

static void \

NAME (TYPE *base, unsigned int nmemb, void *data) \

{ \

  unsigned int gap = nmemb; \

  unsigned int i, j; \

  int swapped; \

  do { \

      gap = _cairo_combsort_newgap (gap); \

      swapped = gap > 1; \

      for (i = 0; i < nmemb-gap ; i++) { \

    j = i + gap; \

    if (CMP (base[i], base[j], data) > 0 ) { \

        TYPE tmp; \

        tmp = base[i]; \

        base[i] = base[j]; \

        base[j] = tmp; \

        swapped = 1; \

    } \

      } \

  } while (swapped); \

}