https://git.reactos.org/?p=reactos.git;a=commitdiff;h=2dfe5e3f463ca4d7eb920…
commit 2dfe5e3f463ca4d7eb920d25c2a33b29a70f3e27
Author: Pierre Schweitzer <pierre(a)reactos.org>
AuthorDate: Sat Jun 2 13:52:09 2018 +0200
Commit: Pierre Schweitzer <pierre(a)reactos.org>
CommitDate: Sat Jun 2 13:56:42 2018 +0200
[CRT] Reimplement qsort() using FreeBSD implementation.
Our implementation had a bug that could be triggered while
building our USBD library on ReactOS: the compare function
could be called with a NULL pointer instead of a valid value.
With this bug fixed (and the cmd hack in CORE-14648), ReactOS
can totally selfhost :-)! I was able to build LiveCD and BootCD
without any trouble, crash, deadlock or whatever.
(Next step: having a buildbot slave hosted on ReactOS ;-)).
Enjoy: https://twitter.com/HeisSpiter/status/1002880397103988737
CORE-14680
---
sdk/lib/crt/stdlib/qsort.c | 353 ++++++++++++++++++---------------------------
1 file changed, 138 insertions(+), 215 deletions(-)
diff --git a/sdk/lib/crt/stdlib/qsort.c b/sdk/lib/crt/stdlib/qsort.c
index 62f365177d..d6bca5f06c 100644
--- a/sdk/lib/crt/stdlib/qsort.c
+++ b/sdk/lib/crt/stdlib/qsort.c
@@ -1,170 +1,81 @@
-/* Copyright (C) 1994 DJ Delorie, see COPYING.DJ for details */
-
-#include <stdlib.h>
-#include <search.h>
-
/*-
- * Copyright (c) 1980, 1983 The Regents of the University of California.
- * All rights reserved.
+ * Copyright (c) 1992, 1993
+ * The Regents of the University of California. All rights reserved.
*
- * Redistribution and use in source and binary forms are permitted
- * provided that: (1) source distributions retain this entire copyright
- * notice and comment, and (2) distributions including binaries display
- * the following acknowledgement: ``This product includes software
- * developed by the University of California, Berkeley and its contributors''
- * in the documentation or other materials provided with the distribution
- * and in all advertising materials mentioning features or use of this
- * software. Neither the name of the University nor the names of its
- * contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 4. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
*/
-/*
- * qsort.c:
- * Our own version of the system qsort routine which is faster by an average
- * of 25%, with lows and highs of 10% and 50%.
- * The THRESHold below is the insertion sort threshold, and has been adjusted
- * for records of size 48 bytes.
- * The MTHREShold is where we stop finding a better median.
- */
+#include <stdlib.h>
+#include <search.h>
-#define THRESH 4 /* threshold for insertion */
-#define MTHRESH 6 /* threshold for median */
+#define min(a, b) (a) < (b) ? (a) : (b)
/*
- * qst:
- * Do a quicksort
- * First, find the median element, and put that one in the first place as the
- * discriminator. (This "median" is just the median of the first, last and
- * middle elements). (Using this median instead of the first element is a big
- * win). Then, the usual partitioning/swapping, followed by moving the
- * discriminator into the right place. Then, figure out the sizes of the two
- * partions, do the smaller one recursively and the larger one via a repeat of
- * this code. Stopping when there are less than THRESH elements in a partition
- * and cleaning up with an insertion sort (in our caller) is a huge win.
- * All data swaps are done in-line, which is space-losing but time-saving.
- * (And there are only three places where this is done).
+ * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
*/
+#define swapcode(TYPE, parmi, parmj, n) { \
+ long i = (n) / sizeof (TYPE); \
+ register TYPE *pi = (TYPE *) (parmi); \
+ register TYPE *pj = (TYPE *) (parmj); \
+ do { \
+ register TYPE t = *pi; \
+ *pi++ = *pj; \
+ *pj++ = t; \
+ } while (--i > 0); \
+}
-static void __cdecl
-qst(size_t size, int (__cdecl *compar)(const void*, const void*), char *base, char *max)
+#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
+ es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
+
+static __inline void
+swapfunc(char *a, char *b, int n, int swaptype)
{
- char c, *i, *j, *jj;
- size_t ii;
- char *mid, *tmp;
- size_t lo, hi;
- size_t thresh;
- size_t mthresh;
+ if(swaptype <= 1)
+ swapcode(long, a, b, n)
+ else
+ swapcode(char, a, b, n)
+}
- thresh = size * THRESH;
- mthresh = size * MTHRESH;
+#define swap(a, b) \
+ if (swaptype == 0) { \
+ long t = *(long *)(a); \
+ *(long *)(a) = *(long *)(b); \
+ *(long *)(b) = t; \
+ } else \
+ swapfunc(a, b, es, swaptype)
- /*
- * At the top here, lo is the number of characters of elements in the
- * current partition. (Which should be max - base).
- * Find the median of the first, last, and middle element and make
- * that the middle element. Set j to largest of first and middle.
- * If max is larger than that guy, then it's that guy, else compare
- * max with loser of first and take larger. Things are set up to
- * prefer the middle, then the first in case of ties.
- */
- lo = max - base; /* number of elements as chars */
- do {
- mid = i = base + size * ((lo / size) >> 1);
- if (lo >= mthresh)
- {
- j = (compar((jj = base), i) > 0 ? jj : i);
- if (compar(j, (tmp = max - size)) > 0)
- {
- /* switch to first loser */
- j = (j == jj ? i : jj);
- if (compar(j, tmp) < 0)
- j = tmp;
- }
- if (j != i)
- {
- ii = size;
- do {
- c = *i;
- *i++ = *j;
- *j++ = c;
- } while (--ii);
- }
- }
- /*
- * Semi-standard quicksort partitioning/swapping
- */
- for (i = base, j = max - size; ; )
- {
- while (i < mid && compar(i, mid) <= 0)
- i += size;
- while (j > mid)
- {
- if (compar(mid, j) <= 0)
- {
- j -= size;
- continue;
- }
- tmp = i + size; /* value of i after swap */
- if (i == mid)
- {
- /* j <-> mid, new mid is j */
- mid = jj = j;
- }
- else
- {
- /* i <-> j */
- jj = j;
- j -= size;
- }
- goto swap;
- }
- if (i == mid)
- {
- break;
- }
- else
- {
- /* i <-> mid, new mid is i */
- jj = mid;
- tmp = mid = i; /* value of i after swap */
- j -= size;
- }
- swap:
- ii = size;
- do {
- c = *i;
- *i++ = *jj;
- *jj++ = c;
- } while (--ii);
- i = tmp;
- }
- /*
- * Look at sizes of the two partitions, do the smaller
- * one first by recursion, then do the larger one by
- * making sure lo is its size, base and max are update
- * correctly, and branching back. But only repeat
- * (recursively or by branching) if the partition is
- * of at least size THRESH.
- */
- i = (j = mid) + size;
- if ((lo = j - base) <= (hi = max - i))
- {
- if (lo >= thresh)
- qst(size, compar, base, j);
- base = i;
- lo = hi;
- }
- else
- {
- if (hi >= thresh)
- qst(size, compar, i, max);
- max = j;
- }
- } while (lo >= thresh);
+#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
+
+#define CMP(x, y) (cmp((x), (y)))
+
+static __inline char *
+med3(char *a, char *b, char *c, int (__cdecl *cmp)(const void*, const void*))
+{
+ return CMP(a, b) < 0 ?
+ (CMP(b, c) < 0 ? b : (CMP(a, c) < 0 ? c : a ))
+ :(CMP(b, c) > 0 ? b : (CMP(a, c) < 0 ? a : c ));
}
/*
@@ -177,67 +88,79 @@ qst(size_t size, int (__cdecl *compar)(const void*, const void*), char *base, ch
*/
void
__cdecl
-qsort(void *base0, size_t n, size_t size, int (__cdecl *compar)(const void*, const void*))
+qsort(void *a, size_t n, size_t es, int (__cdecl *cmp)(const void*, const void*))
{
- char *base = (char *)base0;
- char c, *i, *j, *lo, *hi;
- char *min, *max;
- size_t thresh;
+ char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
+ int d, r, swaptype, swap_cnt;
- if (n <= 1)
- return;
+loop: SWAPINIT(a, es);
+ swap_cnt = 0;
+ if (n < 7) {
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm; pl > (char *)a && CMP(pl - es, pl) > 0;
+ pl -= es)
+ swap(pl, pl - es);
+ return;
+ }
+ pm = (char *)a + (n / 2) * es;
+ if (n > 7) {
+ pl = a;
+ pn = (char *)a + (n - 1) * es;
+ if (n > 40) {
+ d = (n / 8) * es;
+ pl = med3(pl, pl + d, pl + 2 * d, cmp);
+ pm = med3(pm - d, pm, pm + d, cmp);
+ pn = med3(pn - 2 * d, pn - d, pn, cmp);
+ }
+ pm = med3(pl, pm, pn, cmp);
+ }
+ swap(a, pm);
+ pa = pb = (char *)a + es;
+
+ pc = pd = (char *)a + (n - 1) * es;
+ for (;;) {
+ while (pb <= pc && (r = CMP(pb, a)) <= 0) {
+ if (r == 0) {
+ swap_cnt = 1;
+ swap(pa, pb);
+ pa += es;
+ }
+ pb += es;
+ }
+ while (pb <= pc && (r = CMP(pc, a)) >= 0) {
+ if (r == 0) {
+ swap_cnt = 1;
+ swap(pc, pd);
+ pd -= es;
+ }
+ pc -= es;
+ }
+ if (pb > pc)
+ break;
+ swap(pb, pc);
+ swap_cnt = 1;
+ pb += es;
+ pc -= es;
+ }
+ if (swap_cnt == 0) { /* Switch to insertion sort */
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm; pl > (char *)a && CMP(pl - es, pl) > 0;
+ pl -= es)
+ swap(pl, pl - es);
+ return;
+ }
- if (size == 0)
- return;
- thresh = size * THRESH;
- max = base + n * size;
- if (n >= THRESH)
- {
- qst(size, compar, base, max);
- hi = base + thresh;
- }
- else
- {
- hi = max;
- }
- /*
- * First put smallest element, which must be in the first THRESH, in
- * the first position as a sentinel. This is done just by searching
- * the first THRESH elements (or the first n if n < THRESH), finding
- * the min, and swapping it into the first position.
- */
- for (j = lo = base; (lo += size) < hi; )
- if (compar(j, lo) > 0)
- j = lo;
- if (j != base)
- {
- /* swap j into place */
- for (i = base, hi = base + size; i < hi; )
- {
- c = *j;
- *j++ = *i;
- *i++ = c;
- }
- }
- /*
- * With our sentinel in place, we now run the following hyper-fast
- * insertion sort. For each remaining element, min, from [1] to [n-1],
- * set hi to the index of the element AFTER which this one goes.
- * Then, do the standard insertion sort shift on a character at a time
- * basis for each element in the frob.
- */
- for (min = base; (hi = min += size) < max; )
- {
- while (compar(hi -= size, min) > 0)
- /* void */;
- if ((hi += size) != min) {
- for (lo = min + size; --lo >= min; )
- {
- c = *lo;
- for (i = j = lo; (j -= size) >= hi; i = j)
- *i = *j;
- *i = c;
- }
- }
- }
+ pn = (char *)a + n * es;
+ r = min(pa - (char *)a, pb - pa);
+ vecswap(a, pb - r, r);
+ r = min(pd - pc, pn - pd - es);
+ vecswap(pb, pn - r, r);
+ if ((r = pb - pa) > es)
+ qsort(a, r / es, es, cmp);
+ if ((r = pd - pc) > es) {
+ /* Iterate rather than recurse to save stack space */
+ a = pn - r;
+ n = r / es;
+ goto loop;
+ }
}
https://git.reactos.org/?p=reactos.git;a=commitdiff;h=ce5d4fd3e14047402955e…
commit ce5d4fd3e14047402955e14fe002f4cc37c64e12
Author: Dheeraj Bhaskar <dheerajthe1(a)gmail.com>
AuthorDate: Fri Jun 1 02:56:33 2018 +0530
Commit: David Quintana <gigaherz(a)gmail.com>
CommitDate: Thu May 31 23:26:33 2018 +0200
Create a Code of conduct to complete the Github community checklist (#431)
---
CODE_OF_CONDUCT.md | 3 +++
1 file changed, 3 insertions(+)
diff --git a/CODE_OF_CONDUCT.md b/CODE_OF_CONDUCT.md
new file mode 100644
index 0000000000..8109c09b77
--- /dev/null
+++ b/CODE_OF_CONDUCT.md
@@ -0,0 +1,3 @@
+# Code of Conduct
+
+Be respectful toward other members of the community. Don't initiate or engage in discussions that are designed to insult, inflame, attack, or incite hate/discrimination/bullying against others. Don't feed the trolls. If we detect any kind of behaviour we consider unacceptable, we reserve the right to ban, block, or remove the involved members from any or all of our communities.