Revision 58696bfcaacc50323e596112124b41242fde23de authored by Junio C Hamano on 08 July 2024, 22:52:11 UTC, committed by Junio C Hamano on 08 July 2024, 23:23:05 UTC
Under ci/ hierarchy, we run scripts under either "sh" (any Bourne compatible POSIX shell would work) or specifically "bash" (as they require features from bash, e.g., ${parameter/pattern/string} expansion). As we have the CI environment under our control, we can expect that /bin/sh will always be fine to run the scripts that only require a Bourne shell, but we may not know where "bash" is installed depending on the distro used. So let's make sure we start these scripts with either one of these: #!/bin/sh #!/usr/bin/env bash Yes, the latter has to assume that everybody installs "env" at that path and not as /bin/env or /usr/local/bin/env, but this currently is the best we could do. Signed-off-by: Junio C Hamano <gitster@pobox.com>
1 parent 337b4d4
mergesort.h
#ifndef MERGESORT_H
#define MERGESORT_H
/* Combine two sorted lists. Take from `list` on equality. */
#define DEFINE_LIST_MERGE_INTERNAL(name, type) \
static type *name##__merge(type *list, type *other, \
int (*compare_fn)(const type *, const type *))\
{ \
type *result = list, *tail; \
int prefer_list = compare_fn(list, other) <= 0; \
\
if (!prefer_list) { \
result = other; \
SWAP(list, other); \
} \
for (;;) { \
do { \
tail = list; \
list = name##__get_next(list); \
if (!list) { \
name##__set_next(tail, other); \
return result; \
} \
} while (compare_fn(list, other) < prefer_list); \
name##__set_next(tail, other); \
prefer_list ^= 1; \
SWAP(list, other); \
} \
}
/*
* Perform an iterative mergesort using an array of sublists.
*
* n is the number of items.
* ranks[i] is undefined if n & 2^i == 0, and assumed empty.
* ranks[i] contains a sublist of length 2^i otherwise.
*
* The number of bits in a void pointer limits the number of objects
* that can be created, and thus the number of array elements necessary
* to be able to sort any valid list.
*
* Adding an item to this array is like incrementing a binary number;
* positional values for set bits correspond to sublist lengths.
*/
#define DEFINE_LIST_SORT_INTERNAL(scope, name, type) \
scope void name(type **listp, \
int (*compare_fn)(const type *, const type *)) \
{ \
type *list = *listp; \
type *ranks[bitsizeof(type *)]; \
size_t n = 0; \
\
if (!list) \
return; \
\
for (;;) { \
int i; \
size_t m; \
type *next = name##__get_next(list); \
if (next) \
name##__set_next(list, NULL); \
for (i = 0, m = n;; i++, m >>= 1) { \
if (m & 1) { \
list = name##__merge(ranks[i], list, \
compare_fn); \
} else if (next) { \
break; \
} else if (!m) { \
*listp = list; \
return; \
} \
} \
n++; \
ranks[i] = list; \
list = next; \
} \
}
#define DECLARE_LIST_SORT(scope, name, type) \
scope void name(type **listp, \
int (*compare_fn)(const type *, const type *))
#define DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, \
on_get_next, on_set_next) \
\
static inline type *name##__get_next(const type *elem) \
{ \
on_get_next; \
return elem->next_member; \
} \
\
static inline void name##__set_next(type *elem, type *next) \
{ \
on_set_next; \
elem->next_member = next; \
} \
\
DEFINE_LIST_MERGE_INTERNAL(name, type) \
DEFINE_LIST_SORT_INTERNAL(scope, name, type) \
DECLARE_LIST_SORT(scope, name, type)
#define DEFINE_LIST_SORT(scope, name, type, next_member) \
DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0)
#endif
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...