Coverage Report

Created: 2024-09-08 06:24

/src/git/mergesort.h
Line
Count
Source (jump to first uncovered line)
1
#ifndef MERGESORT_H
2
#define MERGESORT_H
3
4
/* Combine two sorted lists.  Take from `list` on equality. */
5
#define DEFINE_LIST_MERGE_INTERNAL(name, type)        \
6
static type *name##__merge(type *list, type *other,     \
7
0
         int (*compare_fn)(const type *, const type *))\
8
0
{                 \
9
0
  type *result = list, *tail;         \
10
0
  int prefer_list = compare_fn(list, other) <= 0;     \
11
0
                  \
12
0
  if (!prefer_list) {           \
13
0
    result = other;           \
14
0
    SWAP(list, other);          \
15
0
  }               \
16
0
  for (;;) {             \
17
0
    do {             \
18
0
      tail = list;          \
19
0
      list = name##__get_next(list);      \
20
0
      if (!list) {         \
21
0
        name##__set_next(tail, other);    \
22
0
        return result;        \
23
0
      }            \
24
0
    } while (compare_fn(list, other) < prefer_list);  \
25
0
    name##__set_next(tail, other);        \
26
0
    prefer_list ^= 1;         \
27
0
    SWAP(list, other);          \
28
0
  }               \
29
0
}
Unexecuted instantiation: blame.c:sort_blame_entries__merge
Unexecuted instantiation: commit.c:commit_list_sort__merge
Unexecuted instantiation: fetch-pack.c:sort_ref_list__merge
Unexecuted instantiation: packfile.c:sort_packs__merge
30
31
/*
32
 * Perform an iterative mergesort using an array of sublists.
33
 *
34
 * n is the number of items.
35
 * ranks[i] is undefined if n & 2^i == 0, and assumed empty.
36
 * ranks[i] contains a sublist of length 2^i otherwise.
37
 *
38
 * The number of bits in a void pointer limits the number of objects
39
 * that can be created, and thus the number of array elements necessary
40
 * to be able to sort any valid list.
41
 *
42
 * Adding an item to this array is like incrementing a binary number;
43
 * positional values for set bits correspond to sublist lengths.
44
 */
45
#define DEFINE_LIST_SORT_INTERNAL(scope, name, type)      \
46
scope void name(type **listp,           \
47
1.46k
    int (*compare_fn)(const type *, const type *))    \
48
1.46k
{                 \
49
1.46k
  type *list = *listp;            \
50
1.46k
  type *ranks[bitsizeof(type *)];         \
51
1.46k
  size_t n = 0;             \
52
1.46k
                  \
53
1.46k
  if (!list)             \
54
1.46k
    return;             \
55
1.46k
                  \
56
1.46k
  for (;;) {             \
57
0
    int i;              \
58
0
    size_t m;           \
59
0
    type *next = name##__get_next(list);      \
60
0
    if (next)           \
61
0
      name##__set_next(list, NULL);     \
62
0
    for (i = 0, m = n;; i++, m >>= 1) {     \
63
0
      if (m & 1) {         \
64
0
        list = name##__merge(ranks[i], list,  \
65
0
                compare_fn);  \
66
0
      } else if (next) {       \
67
0
        break;          \
68
0
      } else if (!m) {       \
69
0
        *listp = list;        \
70
0
        return;         \
71
0
      }            \
72
0
    }             \
73
0
    n++;              \
74
0
    ranks[i] = list;          \
75
0
    list = next;            \
76
0
  }                \
77
0
}
Unexecuted instantiation: blame.c:sort_blame_entries
Unexecuted instantiation: commit.c:commit_list_sort
Unexecuted instantiation: fetch-pack.c:sort_ref_list
packfile.c:sort_packs
Line
Count
Source
47
1.46k
    int (*compare_fn)(const type *, const type *))    \
48
1.46k
{                 \
49
1.46k
  type *list = *listp;            \
50
1.46k
  type *ranks[bitsizeof(type *)];         \
51
1.46k
  size_t n = 0;             \
52
1.46k
                  \
53
1.46k
  if (!list)             \
54
1.46k
    return;             \
55
1.46k
                  \
56
1.46k
  for (;;) {             \
57
0
    int i;              \
58
0
    size_t m;           \
59
0
    type *next = name##__get_next(list);      \
60
0
    if (next)           \
61
0
      name##__set_next(list, NULL);     \
62
0
    for (i = 0, m = n;; i++, m >>= 1) {     \
63
0
      if (m & 1) {         \
64
0
        list = name##__merge(ranks[i], list,  \
65
0
                compare_fn);  \
66
0
      } else if (next) {       \
67
0
        break;          \
68
0
      } else if (!m) {       \
69
0
        *listp = list;        \
70
0
        return;         \
71
0
      }            \
72
0
    }             \
73
0
    n++;              \
74
0
    ranks[i] = list;          \
75
0
    list = next;            \
76
0
  }                \
77
0
}
78
79
#define DECLARE_LIST_SORT(scope, name, type)      \
80
scope void name(type **listp,         \
81
    int (*compare_fn)(const type *, const type *))
82
83
#define DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member,  \
84
             on_get_next, on_set_next)  \
85
                \
86
0
static inline type *name##__get_next(const type *elem)    \
87
0
{               \
88
0
  on_get_next;            \
89
0
  return elem->next_member;       \
90
0
}                \
Unexecuted instantiation: blame.c:sort_blame_entries__get_next
Unexecuted instantiation: commit.c:commit_list_sort__get_next
Unexecuted instantiation: fetch-pack.c:sort_ref_list__get_next
Unexecuted instantiation: packfile.c:sort_packs__get_next
91
                \
92
0
static inline void name##__set_next(type *elem, type *next) \
93
0
{               \
94
0
  on_set_next;            \
95
0
  elem->next_member = next;       \
96
0
}                \
Unexecuted instantiation: blame.c:sort_blame_entries__set_next
Unexecuted instantiation: commit.c:commit_list_sort__set_next
Unexecuted instantiation: fetch-pack.c:sort_ref_list__set_next
Unexecuted instantiation: packfile.c:sort_packs__set_next
97
                \
98
DEFINE_LIST_MERGE_INTERNAL(name, type)        \
99
DEFINE_LIST_SORT_INTERNAL(scope, name, type)      \
100
DECLARE_LIST_SORT(scope, name, type)
101
102
#define DEFINE_LIST_SORT(scope, name, type, next_member) \
103
DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0)
104
105
#endif