Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/isl_sort.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * The code of this file was taken from http://jeffreystedfast.blogspot.be,
3
 * where it was posted in 2011 by Jeffrey Stedfast under the MIT license.
4
 * The MIT license text is as follows:
5
 *
6
 * Permission is hereby granted, free of charge, to any person obtaining a copy
7
 * of this software and associated documentation files (the "Software"), to
8
 * deal in the Software without restriction, including without limitation the
9
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10
 * sell copies of the Software, and to permit persons to whom the Software is
11
 * furnished to do so, subject to the following conditions:
12
 *
13
 * The above copyright notice and this permission notice shall be included in
14
 * all copies or substantial portions of the Software.
15
 *
16
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22
 * IN THE SOFTWARE.
23
 */
24
25
#include <errno.h>
26
#include <string.h>
27
#include <stdlib.h>
28
#include <isl_sort.h>
29
30
1.15M
#define MID(lo, hi) (lo + ((hi - lo) >> 1))
31
32
/* The code here is an optimized merge sort. Starting from a generic merge sort
33
 * the following optimizations were applied:
34
 *
35
 * o Batching of memcpy() calls: Instead of calling memcpy() to copy each and
36
 *   every element into a temporary buffer, blocks of elements are copied
37
 *   at a time.
38
 *
39
 * o To reduce the number of memcpy() calls further, copying leading
40
 *   and trailing elements into our temporary buffer is avoided, in case it is
41
 *   not necessary to merge them.
42
 *
43
 * A further optimization could be to specialize memcpy calls based on the
44
 * size of the types we compare. For now, this code does not include the
45
 * relevant optimization, as clang e.g. inlines a very efficient memcpy()
46
 * implementation. It is not clear, that the specialized version as provided in
47
 * the blog post, is really superior to the one that will be inlined by
48
 * default. So we decided to keep the code simple until this optimization was
49
 * proven to be beneficial.
50
 */
51
52
static void
53
msort (void *array, void *buf, size_t low, size_t high, size_t size,
54
       int (* compare) (const void *, const void *, void *), void *arg)
55
1.15M
{
56
1.15M
    char *a1, *al, *am, *ah, *ls, *hs, *lo, *hi, *b;
57
1.15M
    size_t copied = 0;
58
1.15M
    size_t mid;
59
1.15M
60
1.15M
    mid = MID (low, high);
61
1.15M
62
1.15M
    if (mid + 1 < high)
63
368k
        msort (array, buf, mid + 1, high, size, compare, arg);
64
1.15M
65
1.15M
    if (mid > low)
66
570k
        msort (array, buf, low, mid, size, compare, arg);
67
1.15M
68
1.15M
    ah = ((char *) array) + ((high + 1) * size);
69
1.15M
    am = ((char *) array) + ((mid + 1) * size);
70
1.15M
    a1 = al = ((char *) array) + (low * size);
71
1.15M
72
1.15M
    b = (char *) buf;
73
1.15M
    lo = al;
74
1.15M
    hi = am;
75
1.15M
76
1.29M
    do {
77
1.29M
        ls = lo;
78
1.29M
        hs = hi;
79
1.29M
80
1.29M
        if (
lo > al || 1.29M
hi > am1.18M
) {
81
140k
            /* our last loop already compared lo & hi and found lo <= hi */
82
140k
            lo += size;
83
140k
        }
84
1.29M
85
3.31M
        while (
lo < am && 3.31M
compare (lo, hi, arg) <= 02.39M
)
86
2.01M
            lo += size;
87
1.29M
88
1.29M
        if (
lo < am1.29M
) {
89
377k
            if (
copied == 0377k
) {
90
289k
                /* avoid copying the leading items */
91
289k
                a1 = lo;
92
289k
                ls = lo;
93
289k
            }
94
377k
95
377k
            /* our last compare tells us hi < lo */
96
377k
            hi += size;
97
377k
98
644k
            while (
hi < ah && 644k
compare (hi, lo, arg) < 0407k
)
99
267k
                hi += size;
100
377k
101
377k
            if (
lo > ls377k
) {
102
87.3k
                memcpy (b, ls, lo - ls);
103
87.3k
                copied += (lo - ls);
104
87.3k
                b += (lo - ls);
105
87.3k
            }
106
377k
107
377k
            memcpy (b, hs, hi - hs);
108
377k
            copied += (hi - hs);
109
377k
            b += (hi - hs);
110
1.29M
        } else 
if (917k
copied917k
) {
111
52.8k
            memcpy (b, ls, lo - ls);
112
52.8k
            copied += (lo - ls);
113
52.8k
            b += (lo - ls);
114
52.8k
115
52.8k
            /* copy everything we needed to re-order back into array */
116
52.8k
            memcpy (a1, buf, copied);
117
52.8k
            return;
118
0
        } else {
119
864k
            /* everything already in order */
120
864k
            return;
121
864k
        }
122
377k
    } while (hi < ah);
123
1.15M
124
237k
    
if (237k
lo < am237k
) {
125
237k
        memcpy (b, lo, am - lo);
126
237k
        copied += (am - lo);
127
237k
    }
128
1.15M
129
1.15M
    memcpy (a1, buf, copied);
130
1.15M
}
131
132
static int
133
MergeSort (void *base, size_t nmemb, size_t size,
134
           int (* compare) (const void *, const void *, void *), void *arg)
135
254k
{
136
254k
    void *tmp;
137
254k
138
254k
    if (nmemb < 2)
139
38.4k
        return 0;
140
215k
141
215k
    
if (215k
!(tmp = malloc (nmemb * size))215k
) {
142
0
        errno = ENOMEM;
143
0
        return -1;
144
0
    }
145
215k
146
215k
    msort (base, tmp, 0, nmemb - 1, size, compare, arg);
147
215k
148
215k
    free (tmp);
149
215k
150
215k
    return 0;
151
215k
}
152
153
int isl_sort(void *const pbase, size_t total_elems, size_t size,
154
  int (*cmp)(const void *, const void *, void *arg), void *arg)
155
254k
{
156
254k
    return MergeSort (pbase, total_elems, size, cmp, arg);
157
254k
}