Merge branch 'rs/qsort-s'

A few codepaths had to rely on a global variable when sorting
elements of an array because sort(3) API does not allow extra data
to be passed to the comparison function.  Use qsort_s() when
natively available, and a fallback implementation of it when not,
to eliminate the need, which is a prerequisite for making the
codepath reentrant.

* rs/qsort-s:
ref-filter: use QSORT_S in ref_array_sort()
string-list: use QSORT_S in string_list_sort()
perf: add basic sort performance test
add QSORT_S
compat: add qsort_s()

diff --combined Makefile
index 27afd0f378619c1960861d72df74a4b7cba7514f,8c549cecf09275070b9887800b59178ff6b159ab..53ecc84e28a183344b30aa2a82755cc6e6cd41f8
--- 1/Makefile
--- 2/Makefile
+++ b/Makefile
@@@ -279,6 -279,9 +279,9 @@@ all:
  # is a simplified version of the merge sort used in glibc. This is
  # recommended if Git triggers O(n^2) behavior in your platform's qsort().
  #
+ # Define HAVE_ISO_QSORT_S if your platform provides a qsort_s() that's
+ # compatible with the one described in C11 Annex K.
+ #
  # Define UNRELIABLE_FSTAT if your system's fstat does not return the same
  # information on a not yet closed file that lstat would return for the same
  # file after it was closed.
@@@ -338,6 -341,11 +341,6 @@@
  #
  # Define NATIVE_CRLF if your platform uses CRLF for line endings.
  #
 -# Define XDL_FAST_HASH to use an alternative line-hashing method in
 -# the diff algorithm.  It gives a nice speedup if your processor has
 -# fast unaligned word loads.  Does NOT work on big-endian systems!
 -# Enabled by default on x86_64.
 -#
  # Define GIT_USER_AGENT if you want to change how git identifies itself during
  # network interactions.  The default is "git/$(GIT_VERSION)".
  #
@@@ -1418,6 -1426,11 +1421,11 @@@ ifdef INTERNAL_QSOR
        COMPAT_CFLAGS += -DINTERNAL_QSORT
        COMPAT_OBJS += compat/qsort.o
  endif
+ ifdef HAVE_ISO_QSORT_S
+       COMPAT_CFLAGS += -DHAVE_ISO_QSORT_S
+ else
+       COMPAT_OBJS += compat/qsort_s.o
+ endif
  ifdef RUNTIME_PREFIX
        COMPAT_CFLAGS += -DRUNTIME_PREFIX
  endif
@@@ -1480,6 -1493,10 +1488,6 @@@ ifndef NO_MSGFMT_EXTENDED_OPTION
        MSGFMT += --check --statistics
  endif
  
 -ifneq (,$(XDL_FAST_HASH))
 -      BASIC_CFLAGS += -DXDL_FAST_HASH
 -endif
 -
  ifdef GMTIME_UNRELIABLE_ERRORS
        COMPAT_OBJS += compat/gmtime.o
        BASIC_CFLAGS += -DGMTIME_UNRELIABLE_ERRORS
@@@ -1816,7 -1833,7 +1824,7 @@@ $(SCRIPT_LIB) : % : %.sh GIT-SCRIPT-DEF
  git.res: git.rc GIT-VERSION-FILE
        $(QUIET_RC)$(RC) \
          $(join -DMAJOR= -DMINOR=, $(wordlist 1,2,$(subst -, ,$(subst ., ,$(GIT_VERSION))))) \
 -        -DGIT_VERSION="\\\"$(GIT_VERSION)\\\"" $< -o $@
 +        -DGIT_VERSION="\\\"$(GIT_VERSION)\\\"" -i $< -o $@
  
  # This makes sure we depend on the NO_PERL setting itself.
  $(SCRIPT_PERL_GEN): GIT-BUILD-OPTIONS
@@@ -2046,7 -2063,7 +2054,7 @@@ git-%$X: %.o GIT-LDFLAGS $(GITLIBS
  
  git-imap-send$X: imap-send.o $(IMAP_SEND_BUILDDEPS) GIT-LDFLAGS $(GITLIBS)
        $(QUIET_LINK)$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) \
 -              $(LIBS) $(IMAP_SEND_LDFLAGS)
 +              $(IMAP_SEND_LDFLAGS) $(LIBS)
  
  git-http-fetch$X: http.o http-walker.o http-fetch.o GIT-LDFLAGS $(GITLIBS)
        $(QUIET_LINK)$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) \
@@@ -2105,8 -2122,7 +2113,8 @@@ XGETTEXT_FLAGS_C = $(XGETTEXT_FLAGS) --
        --keyword=_ --keyword=N_ --keyword="Q_:1,2"
  XGETTEXT_FLAGS_SH = $(XGETTEXT_FLAGS) --language=Shell \
        --keyword=gettextln --keyword=eval_gettextln
 -XGETTEXT_FLAGS_PERL = $(XGETTEXT_FLAGS) --keyword=__ --language=Perl
 +XGETTEXT_FLAGS_PERL = $(XGETTEXT_FLAGS) --language=Perl \
 +      --keyword=__ --keyword=N__ --keyword="__n:1,2"
  LOCALIZED_C = $(C_OBJ:o=c) $(LIB_H) $(GENERATED_H)
  LOCALIZED_SH = $(SCRIPT_SH)
  LOCALIZED_SH += git-parse-remote.sh
@@@ -2141,22 -2157,9 +2149,22 @@@ endi
  po/build/locale/%/LC_MESSAGES/git.mo: po/%.po
        $(QUIET_MSGFMT)mkdir -p $(dir $@) && $(MSGFMT) -o $@ $<
  
 -FIND_SOURCE_FILES = ( git ls-files '*.[hcS]' 2>/dev/null || \
 -                      $(FIND) . \( -name .git -type d -prune \) \
 -                              -o \( -name '*.[hcS]' -type f -print \) )
 +FIND_SOURCE_FILES = ( \
 +      git ls-files \
 +              '*.[hcS]' \
 +              '*.sh' \
 +              ':!*[tp][0-9][0-9][0-9][0-9]*' \
 +              ':!contrib' \
 +              2>/dev/null || \
 +      $(FIND) . \
 +              \( -name .git -type d -prune \) \
 +              -o \( -name '[tp][0-9][0-9][0-9][0-9]*' -prune \) \
 +              -o \( -name contrib -type d -prune \) \
 +              -o \( -name build -type d -prune \) \
 +              -o \( -name 'trash*' -type d -prune \) \
 +              -o \( -name '*.[hcS]' -type f -print \) \
 +              -o \( -name '*.sh' -type f -print \) \
 +      )
  
  $(ETAGS_TARGET): FORCE
        $(RM) $(ETAGS_TARGET)

diff --combined ref-filter.c
index 5f4b08792bd82d5a70097af18d9c7869c32bceab,f39e6617aaaa473d7f94d3951bab10b0399fcda3..3820b21cc75f5e7fd4b1b1851be0aaa9e3268d7d
--- 1/ref-filter.c
--- 2/ref-filter.c
+++ b/ref-filter.c
@@@ -13,7 -13,6 +13,7 @@@
  #include "utf8.h"
  #include "git-compat-util.h"
  #include "version.h"
 +#include "trailer.h"
  
  typedef enum { FIELD_STR, FIELD_ULONG, FIELD_TIME } cmp_type;
  
@@@ -41,7 -40,7 +41,7 @@@ static struct used_atom 
                enum { RR_NORMAL, RR_SHORTEN, RR_TRACK, RR_TRACKSHORT }
                        remote_ref;
                struct {
 -                      enum { C_BARE, C_BODY, C_BODY_DEP, C_LINES, C_SIG, C_SUB } option;
 +                      enum { C_BARE, C_BODY, C_BODY_DEP, C_LINES, C_SIG, C_SUB, C_TRAILERS } option;
                        unsigned int nlines;
                } contents;
                enum { O_FULL, O_SHORT } objectname;
@@@ -86,13 -85,6 +86,13 @@@ static void subject_atom_parser(struct 
        atom->u.contents.option = C_SUB;
  }
  
 +static void trailers_atom_parser(struct used_atom *atom, const char *arg)
 +{
 +      if (arg)
 +              die(_("%%(trailers) does not take arguments"));
 +      atom->u.contents.option = C_TRAILERS;
 +}
 +
  static void contents_atom_parser(struct used_atom *atom, const char *arg)
  {
        if (!arg)
@@@ -103,8 -95,6 +103,8 @@@
                atom->u.contents.option = C_SIG;
        else if (!strcmp(arg, "subject"))
                atom->u.contents.option = C_SUB;
 +      else if (!strcmp(arg, "trailers"))
 +              atom->u.contents.option = C_TRAILERS;
        else if (skip_prefix(arg, "lines=", &arg)) {
                atom->u.contents.option = C_LINES;
                if (strtoul_ui(arg, 10, &atom->u.contents.nlines))
@@@ -204,7 -194,6 +204,7 @@@ static struct 
        { "creatordate", FIELD_TIME },
        { "subject", FIELD_STR, subject_atom_parser },
        { "body", FIELD_STR, body_atom_parser },
 +      { "trailers", FIELD_STR, trailers_atom_parser },
        { "contents", FIELD_STR, contents_atom_parser },
        { "upstream", FIELD_STR, remote_ref_atom_parser },
        { "push", FIELD_STR, remote_ref_atom_parser },
@@@ -796,7 -785,6 +796,7 @@@ static void grab_sub_body_contents(stru
                        name++;
                if (strcmp(name, "subject") &&
                    strcmp(name, "body") &&
 +                  strcmp(name, "trailers") &&
                    !starts_with(name, "contents"))
                        continue;
                if (!subpos)
@@@ -820,14 -808,6 +820,14 @@@
                        /*  Size is the length of the message after removing the signature */
                        append_lines(&s, subpos, contents_end - subpos, atom->u.contents.nlines);
                        v->s = strbuf_detach(&s, NULL);
 +              } else if (atom->u.contents.option == C_TRAILERS) {
 +                      struct trailer_info info;
 +
 +                      /* Search for trailer info */
 +                      trailer_info_get(&info, subpos);
 +                      v->s = xmemdupz(info.trailer_start,
 +                                      info.trailer_end - info.trailer_start);
 +                      trailer_info_release(&info);
                } else if (atom->u.contents.option == C_BARE)
                        v->s = xstrdup(subpos);
        }
@@@ -1251,14 -1231,8 +1251,14 @@@ static int commit_contains(struct ref_f
   * matches a pattern "refs/heads/mas") or a wildcard (e.g. the same ref
   * matches "refs/heads/mas*", too).
   */
 -static int match_pattern(const char **patterns, const char *refname)
 +static int match_pattern(const struct ref_filter *filter, const char *refname)
  {
 +      const char **patterns = filter->name_patterns;
 +      unsigned flags = 0;
 +
 +      if (filter->ignore_case)
 +              flags |= WM_CASEFOLD;
 +
        /*
         * When no '--format' option is given we need to skip the prefix
         * for matching refs of tags and branches.
@@@ -1269,7 -1243,7 +1269,7 @@@
               skip_prefix(refname, "refs/", &refname));
  
        for (; *patterns; patterns++) {
 -              if (!wildmatch(*patterns, refname, 0, NULL))
 +              if (!wildmatch(*patterns, refname, flags, NULL))
                        return 1;
        }
        return 0;
@@@ -1281,15 -1255,9 +1281,15 @@@
   * matches a pattern "refs/heads/" but not "refs/heads/m") or a
   * wildcard (e.g. the same ref matches "refs/heads/m*", too).
   */
 -static int match_name_as_path(const char **pattern, const char *refname)
 +static int match_name_as_path(const struct ref_filter *filter, const char *refname)
  {
 +      const char **pattern = filter->name_patterns;
        int namelen = strlen(refname);
 +      unsigned flags = WM_PATHNAME;
 +
 +      if (filter->ignore_case)
 +              flags |= WM_CASEFOLD;
 +
        for (; *pattern; pattern++) {
                const char *p = *pattern;
                int plen = strlen(p);
@@@ -1312,8 -1280,8 +1312,8 @@@ static int filter_pattern_match(struct 
        if (!*filter->name_patterns)
                return 1; /* No pattern always matches */
        if (filter->match_as_path)
 -              return match_name_as_path(filter->name_patterns, refname);
 -      return match_pattern(filter->name_patterns, refname);
 +              return match_name_as_path(filter, refname);
 +      return match_pattern(filter, refname);
  }
  
  /*
@@@ -1361,7 -1329,7 +1361,7 @@@ static struct ref_array_item *new_ref_a
        return ref;
  }
  
 -static int filter_ref_kind(struct ref_filter *filter, const char *refname)
 +static int ref_kind_from_refname(const char *refname)
  {
        unsigned int i;
  
@@@ -1374,7 -1342,11 +1374,7 @@@
                { "refs/tags/", FILTER_REFS_TAGS}
        };
  
 -      if (filter->kind == FILTER_REFS_BRANCHES ||
 -          filter->kind == FILTER_REFS_REMOTES ||
 -          filter->kind == FILTER_REFS_TAGS)
 -              return filter->kind;
 -      else if (!strcmp(refname, "HEAD"))
 +      if (!strcmp(refname, "HEAD"))
                return FILTER_REFS_DETACHED_HEAD;
  
        for (i = 0; i < ARRAY_SIZE(ref_kind); i++) {
@@@ -1385,15 -1357,6 +1385,15 @@@
        return FILTER_REFS_OTHERS;
  }
  
 +static int filter_ref_kind(struct ref_filter *filter, const char *refname)
 +{
 +      if (filter->kind == FILTER_REFS_BRANCHES ||
 +          filter->kind == FILTER_REFS_REMOTES ||
 +          filter->kind == FILTER_REFS_TAGS)
 +              return filter->kind;
 +      return ref_kind_from_refname(refname);
 +}
 +
  /*
   * A call-back given to for_each_ref().  Filter refs and keep them for
   * later object processing.
@@@ -1573,20 -1536,18 +1573,20 @@@ static int cmp_ref_sorting(struct ref_s
        struct atom_value *va, *vb;
        int cmp;
        cmp_type cmp_type = used_atom[s->atom].type;
 +      int (*cmp_fn)(const char *, const char *);
  
        get_ref_atom_value(a, s->atom, &va);
        get_ref_atom_value(b, s->atom, &vb);
 +      cmp_fn = s->ignore_case ? strcasecmp : strcmp;
        if (s->version)
                cmp = versioncmp(va->s, vb->s);
        else if (cmp_type == FIELD_STR)
 -              cmp = strcmp(va->s, vb->s);
 +              cmp = cmp_fn(va->s, vb->s);
        else {
                if (va->ul < vb->ul)
                        cmp = -1;
                else if (va->ul == vb->ul)
 -                      cmp = strcmp(a->refname, b->refname);
 +                      cmp = cmp_fn(a->refname, b->refname);
                else
                        cmp = 1;
        }
@@@ -1594,8 -1555,7 +1594,7 @@@
        return (s->reverse) ? -cmp : cmp;
  }
  
- static struct ref_sorting *ref_sorting;
- static int compare_refs(const void *a_, const void *b_)
+ static int compare_refs(const void *a_, const void *b_, void *ref_sorting)
  {
        struct ref_array_item *a = *((struct ref_array_item **)a_);
        struct ref_array_item *b = *((struct ref_array_item **)b_);
@@@ -1611,8 -1571,7 +1610,7 @@@
  
  void ref_array_sort(struct ref_sorting *sorting, struct ref_array *array)
  {
-       ref_sorting = sorting;
-       QSORT(array->items, array->nr, compare_refs);
+       QSORT_S(array->items, array->nr, compare_refs, sorting);
  }
  
  static void append_literal(const char *cp, const char *ep, struct ref_formatting_state *state)
@@@ -1676,16 -1635,6 +1674,16 @@@ void show_ref_array_item(struct ref_arr
        putchar('\n');
  }
  
 +void pretty_print_ref(const char *name, const unsigned char *sha1,
 +              const char *format)
 +{
 +      struct ref_array_item *ref_item;
 +      ref_item = new_ref_array_item(name, sha1, 0);
 +      ref_item->kind = ref_kind_from_refname(name);
 +      show_ref_array_item(ref_item, format, 0);
 +      free_array_item(ref_item);
 +}
 +
  /*  If no sorting option is given, use refname to sort as default */
  struct ref_sorting *ref_default_sorting(void)
  {