OpenCoverage

mpsort.c

Absolute File Name:

/home/opencoverage/opencoverage/guest-scripts/coreutils/src/gnulib/lib/mpsort.c

Source code

Switch to Preprocessed file

Line Source Count

1 /* Sort a vector of pointers to data. -

2 -

4 -

5 This program is free software: you can redistribute it and/or modify -

6 it under the terms of the GNU General Public License as published by -

7 the Free Software Foundation; either version 3 of the License, or -

8 (at your option) any later version. -

9 -

10 This program is distributed in the hope that it will be useful, -

11 but WITHOUT ANY WARRANTY; without even the implied warranty of -

12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -

13 GNU General Public License for more details. -

14 -

15 You should have received a copy of the GNU General Public License -

16 along with this program. If not, see <https://www.gnu.org/licenses/>. */ -

17 -

18 /* Written by Paul Eggert. */ -

19 -

20 #include <config.h> -

21 -

22 #include "mpsort.h" -

23 -

24 #include <string.h> -

25 -

26 /* The type of qsort-style comparison functions. */ -

27 -

28 typedef int (*comparison_function) (void const *, void const *); -

29 -

30 static void mpsort_with_tmp (void const **restrict, size_t, -

31 void const **restrict, comparison_function); -

32 -

33 /* Sort a vector BASE containing N pointers, placing the sorted array -

34 into TMP. Compare pointers with CMP. N must be at least 2. */ -

35 -

36 static void -

37 mpsort_into_tmp (void const **restrict base, size_t n, -

38 void const **restrict tmp, -

39 comparison_function cmp) -

40 { -

41 size_t n1 = n / 2; -

42 size_t n2 = n - n1; -

43 size_t a = 0; -

44 size_t alim = n1; -

45 size_t b = n1; -

46 size_t blim = n; -

47 void const *ba; -

48 void const *bb; -

49 -

50 mpsort_with_tmp (base + n1, n2, tmp, cmp); -

51 mpsort_with_tmp (base, n1, tmp, cmp); -

52 -

53 ba = base[a]; -

54 bb = base[b]; -

55 -

56 for (;;) -

if (cmp (ba, bb) <= 0)

cmp (ba, bb) <= 0	Description
TRUE	evaluated 29 times by 3 tests Evaluated by: dir ls vdir
FALSE	evaluated 11 times by 3 tests Evaluated by: dir ls vdir

11-29

58 { -

59 *tmp++ = ba; -

60 a++; -

if (a == alim)

a == alim	Description
TRUE	evaluated 15 times by 3 tests Evaluated by: dir ls vdir
FALSE	evaluated 14 times by 3 tests Evaluated by: dir ls vdir

14-15

62 { -

63 a = b; -

64 alim = blim; -

break;

executed 15 times by 3 tests: break;

Executed by:

dir
ls
vdir

66 } -

67 ba = base[a]; -

}

executed 14 times by 3 tests: end of block

Executed by:

dir
ls
vdir

69 else -

70 { -

71 *tmp++ = bb; -

72 b++; -

if (b == blim)

b == blim	Description
TRUE	evaluated 5 times by 3 tests Evaluated by: dir ls vdir
FALSE	evaluated 6 times by 3 tests Evaluated by: dir ls vdir

5-6

break;

executed 5 times by 3 tests: break;

Executed by:

dir
ls
vdir

75 bb = base[b]; -

}

executed 6 times by 3 tests: end of block

Executed by:

dir
ls
vdir

77 -

78 memcpy (tmp, base + a, (alim - a) * sizeof *base); -

}

executed 20 times by 3 tests: end of block

Executed by:

dir
ls
vdir

80 -

81 /* Sort a vector BASE containing N pointers, in place. Use TMP -

82 (containing N / 2 pointers) for temporary storage. Compare -

83 pointers with CMP. */ -

84 -

85 static void -

86 mpsort_with_tmp (void const **restrict base, size_t n, -

87 void const **restrict tmp, -

88 comparison_function cmp) -

89 { -

if (n <= 2)

n <= 2	Description
TRUE	evaluated 1124 times by 3 tests Evaluated by: dir ls vdir
FALSE	evaluated 36 times by 3 tests Evaluated by: dir ls vdir

36-1124

91 { -

if (n == 2)

n == 2	Description
TRUE	evaluated 33 times by 3 tests Evaluated by: dir ls vdir
FALSE	evaluated 1091 times by 3 tests Evaluated by: dir ls vdir

33-1091

93 { -

94 void const *p0 = base[0]; -

95 void const *p1 = base[1]; -

if (! (cmp (p0, p1) <= 0))

! (cmp (p0, p1) <= 0)	Description
TRUE	evaluated 8 times by 3 tests Evaluated by: dir ls vdir
FALSE	evaluated 25 times by 3 tests Evaluated by: dir ls vdir

8-25

97 { -

98 base[0] = p1; -

99 base[1] = p0; -

100

}

executed 8 times by 3 tests: end of block

Executed by:

dir
ls
vdir

101

}

executed 33 times by 3 tests: end of block

Executed by:

dir
ls
vdir

102

}

executed 1124 times by 3 tests: end of block

Executed by:

dir
ls
vdir

1124

103 else -

104 { -

105 size_t n1 = n / 2; -

106 size_t n2 = n - n1; -

107 size_t i; -

108 size_t t = 0; -

109 size_t tlim = n1; -

110 size_t b = n1; -

111 size_t blim = n; -

112 void const *bb; -

113 void const *tt; -

114 -

115 mpsort_with_tmp (base + n1, n2, tmp, cmp); -

116 -

117

if (n1 < 2)

n1 < 2	Description
TRUE	evaluated 16 times by 3 tests Evaluated by: dir ls vdir
FALSE	evaluated 20 times by 3 tests Evaluated by: dir ls vdir

16-20

118

tmp[0] = base[0];

executed 16 times by 3 tests: tmp[0] = base[0];

Executed by:

dir
ls
vdir

119 else -

120

mpsort_into_tmp (base, n1, tmp, cmp);

executed 20 times by 3 tests: mpsort_into_tmp (base, n1, tmp, cmp);

Executed by:

dir
ls
vdir

121 -

122 tt = tmp[t]; -

123 bb = base[b]; -

124 -

125 for (i = 0; ; ) -

126

if (cmp (tt, bb) <= 0)

cmp (tt, bb) <= 0	Description
TRUE	evaluated 75 times by 3 tests Evaluated by: dir ls vdir
FALSE	evaluated 36 times by 3 tests Evaluated by: dir ls vdir

36-75

127 { -

128 base[i++] = tt; -

129 t++; -

130

if (t == tlim)

t == tlim	Description
TRUE	evaluated 27 times by 3 tests Evaluated by: dir ls vdir
FALSE	evaluated 48 times by 3 tests Evaluated by: dir ls vdir

27-48

131

break;

executed 27 times by 3 tests: break;

Executed by:

dir
ls
vdir

132 tt = tmp[t]; -

133

}

executed 48 times by 3 tests: end of block

Executed by:

dir
ls
vdir

134 else -

135 { -

136 base[i++] = bb; -

137 b++; -

138

if (b == blim)

b == blim	Description
TRUE	evaluated 9 times by 3 tests Evaluated by: dir ls vdir
FALSE	evaluated 27 times by 3 tests Evaluated by: dir ls vdir

9-27

139 { -

140 memcpy (base + i, tmp + t, (tlim - t) * sizeof *base); -

141

break;

executed 9 times by 3 tests: break;

Executed by:

dir
ls
vdir

142 } -

143 bb = base[b]; -

144

}

executed 27 times by 3 tests: end of block

Executed by:

dir
ls
vdir

145

}

executed 36 times by 3 tests: end of block

Executed by:

dir
ls
vdir

146 } -

147 -

148 /* Sort a vector BASE containing N pointers, in place. BASE must -

149 contain enough storage to hold N + N / 2 vectors; the trailing -

150 vectors are used for temporaries. Compare pointers with CMP. */ -

151 -

152 void -

153 mpsort (void const **base, size_t n, comparison_function cmp) -

154 { -

155 mpsort_with_tmp (base, n, base + n, cmp); -

156

}

executed 1084 times by 3 tests: end of block

Executed by:

dir
ls
vdir

1084

Source code

Switch to Preprocessed file

Generated by Squish Coco 4.1.2