[Qemacs-commit] qemacs dired.c extras.c qe.h util.c

[Charlie Gordon]

CVSROOT:        /sources/qemacs
Module name:    qemacs
Changes by:     Charlie Gordon <chqrlie>        16/12/25 05:51:14

Modified files:
        .              : dired.c extras.c qe.h util.c 

Log message:
        basic: use our own version of qsort_r
        - add `qe_qsort_r()` because some platforms do not provide `qsort_r()`
          it uses a median of 3 pivot selection and falls back to insert sort
          for small chunks.
        - use `qe_qsort_r()` in dired, remove `state` field in `DirEntry`
        - use `qe_qsort_r()` in sort-buffer commands
        - make buffer sorting algorithm stable

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/qemacs/dired.c?cvsroot=qemacs&r1=1.70&r2=1.71
http://cvs.savannah.gnu.org/viewcvs/qemacs/extras.c?cvsroot=qemacs&r1=1.47&r2=1.48
http://cvs.savannah.gnu.org/viewcvs/qemacs/qe.h?cvsroot=qemacs&r1=1.228&r2=1.229
http://cvs.savannah.gnu.org/viewcvs/qemacs/util.c?cvsroot=qemacs&r1=1.74&r2=1.75

Patches:
Index: dired.c
===================================================================
RCS file: /sources/qemacs/qemacs/dired.c,v
retrieving revision 1.70
retrieving revision 1.71
diff -u -b -r1.70 -r1.71
--- dired.c     23 Dec 2016 13:00:55 -0000      1.70
+++ dired.c     25 Dec 2016 10:51:14 -0000      1.71
@@ -87,7 +87,6 @@
 
 /* opaque structure for sorting DiredState.items StringArray */
 struct DiredItem {
-    DiredState *state;
     mode_t  mode;   /* inode protection mode */
     nlink_t nlink;  /* number of hard links to the file */
     uid_t   uid;    /* user-id of owner */
@@ -201,13 +200,14 @@
 }
 
 /* sort alphabetically with directories first */
-static int dired_sort_func(const void *p1, const void *p2)
+static int dired_sort_func(void *opaque, const void *p1, const void *p2)
 {
     const StringItem *item1 = *(const StringItem **)p1;
     const StringItem *item2 = *(const StringItem **)p2;
     const DiredItem *dip1 = item1->opaque;
     const DiredItem *dip2 = item2->opaque;
-    int sort_mode = dip1->state->sort_mode, res;
+    DiredState *ds = opaque;
+    int sort_mode = ds->sort_mode, res;
     int is_dir1, is_dir2;
 
     if (sort_mode & DIRED_SORT_GROUP) {
@@ -630,8 +630,8 @@
     if (flags & DIRED_UPDATE_SORT) {
         flags |= DIRED_UPDATE_REBUILD;
         ds->sort_mode = dired_sort_mode;
-        qsort(ds->items.items, ds->items.nb_items,
-              sizeof(StringItem *), dired_sort_func);
+        qe_qsort_r(ds->items.items, ds->items.nb_items,
+                   sizeof(StringItem *), ds, dired_sort_func);
     }
 
     if (ds->show_dot_files != dired_show_dot_files
@@ -984,7 +984,6 @@
             int plen = strlen(p);
 
             dip = qe_malloc_hack(DiredItem, plen);
-            dip->state = ds;
             dip->mode = st.st_mode;
             dip->nlink = st.st_nlink;
             dip->uid = st.st_uid;

Index: extras.c
===================================================================
RCS file: /sources/qemacs/qemacs/extras.c,v
retrieving revision 1.47
retrieving revision 1.48
diff -u -b -r1.47 -r1.48
--- extras.c    23 Dec 2016 20:12:05 -0000      1.47
+++ extras.c    25 Dec 2016 10:51:14 -0000      1.48
@@ -1354,8 +1354,10 @@
         if (c1 > c2)
             return +cp->dir;
         if (c1 == 0)
-            return 0;
+            break;
     }
+    /* make sort stable by comparing offsets of equal elements */
+    return (p1->start > p2->start) - (p1->start < p2->start);
 }
 
 static void do_sort_span(EditState *s, int p1, int p2, int flags) {
@@ -1388,7 +1390,7 @@
         chunk_array[i].end = offset = eb_goto_eol(s->b, offset);
         offset = eb_next(s->b, offset);
     }
-    qsort_r(chunk_array, lines, sizeof(*chunk_array), &ctx, chunk_cmp);
+    qe_qsort_r(chunk_array, lines, sizeof(*chunk_array), &ctx, chunk_cmp);
         
     b = eb_new("*sorted*", BF_SYSTEM);
     eb_set_charset(b, s->b->charset, s->b->eol_type);

Index: qe.h
===================================================================
RCS file: /sources/qemacs/qemacs/qe.h,v
retrieving revision 1.228
retrieving revision 1.229
diff -u -b -r1.228 -r1.229
--- qe.h        23 Dec 2016 20:28:56 -0000      1.228
+++ qe.h        25 Dec 2016 10:51:14 -0000      1.229
@@ -464,6 +464,10 @@
 int buf_printf(buf_t *bp, const char *fmt, ...) qe__attr_printf(2,3);
 int buf_putc_utf8(buf_t *bp, int c);
 
+/* our own implementation of qsort_r() */
+void qe_qsort_r(void *base, size_t nmemb, size_t size, void *thunk,
+                int (*compar)(void *, const void *, const void *));
+
 /* command line option */
 #define CMD_OPT_ARG      0x0001 /* argument */
 #define CMD_OPT_STRING   0x0002 /* string */

Index: util.c
===================================================================
RCS file: /sources/qemacs/qemacs/util.c,v
retrieving revision 1.74
retrieving revision 1.75
diff -u -b -r1.74 -r1.75
--- util.c      23 Dec 2016 09:47:11 -0000      1.74
+++ util.c      25 Dec 2016 10:51:14 -0000      1.75
@@ -1668,3 +1668,170 @@
         *(void **)pp = p;
     return p;
 }
+
+/*---------------- qe_qsort_r ----------------*/
+
+/* Our own implementation of qsort_r() since it is not available
+ * on some targets, such as OpenBSD.
+ */
+
+typedef void (*exchange_f)(void *a, void *b, size_t size);
+
+static void exchange_bytes(void *a, void *b, size_t size) {
+    unsigned char t;
+    unsigned char *ac = (unsigned char *)a;
+    unsigned char *bc = (unsigned char *)b;
+
+    while (size-- > 0) {
+        t = *ac;
+        *ac++ = *bc;
+        *bc++ = t;
+    }
+}
+
+static void exchange_ints(void *a, void *b, size_t size) {
+    int *ai = (int *)a;
+    int *bi = (int *)b;
+
+    for (size /= sizeof(int); size-- != 0;) {
+        int t = *ai;
+        *ai++ = *bi;
+        *bi++ = t;
+    }
+}
+
+static void exchange_one_int(void *a, void *b, size_t size) {
+    int *ai = (int *)a;
+    int *bi = (int *)b;
+    int t = *ai;
+    *ai = *bi;
+    *bi = t;
+}
+
+#if LONG_MAX != INT_MAX
+static void exchange_longs(void *a, void *b, size_t size) {
+    long *ai = (long *)a;
+    long *bi = (long *)b;
+
+    for (size /= sizeof(long); size-- != 0;) {
+        long t = *ai;
+        *ai++ = *bi;
+        *bi++ = t;
+    }
+}
+
+static void exchange_one_long(void *a, void *b, size_t size) {
+    long *ai = (long *)a;
+    long *bi = (long *)b;
+    long t = *ai;
+    *ai = *bi;
+    *bi = t;
+}
+#endif
+
+static inline exchange_f exchange_func(void *base, size_t size) {
+    exchange_f exchange = exchange_bytes;
+#if LONG_MAX != INT_MAX
+    if ((((uintptr_t)base | (uintptr_t)size) & (sizeof(long) - 1)) == 0) {
+        exchange = exchange_longs;
+        if (size == sizeof(long))
+            exchange = exchange_one_long;
+    } else
+#endif
+    if ((((uintptr_t)base | (uintptr_t)size) & (sizeof(int) - 1)) == 0) {
+        exchange = exchange_ints;
+        if (size == sizeof(int))
+            exchange = exchange_one_int;
+    }
+    return exchange;
+}
+
+static inline void *med3_r(void *a, void *b, void *c, void *thunk,
+                           int (*compare)(void *, const void *, const void *))
+{
+    return compare(thunk, a, b) < 0 ?
+        (compare(thunk, b, c) < 0 ? b : (compare(thunk, a, c) < 0 ? c : a )) :
+        (compare(thunk, b, c) > 0 ? b : (compare(thunk, a, c) < 0 ? a : c ));
+}
+
+#define MAXSTACK 64
+
+void qe_qsort_r(void *base, size_t nmemb, size_t size, void *thunk,
+                int (*compare)(void *, const void *, const void *))
+{
+    struct {
+        unsigned char *base;
+        size_t count;
+    } stack[MAXSTACK], *sp;
+    size_t m0, n;
+    unsigned char *lb, *m, *i, *j;
+    exchange_f exchange = exchange_func(base, size);
+
+    if (nmemb < 2 || size <= 0)
+        return;
+
+    sp = stack;
+    sp->base = base;
+    sp->count = nmemb;
+    sp++;
+    while (sp-- > stack) {
+        lb = sp->base;
+        n = sp->count;
+
+        while (n >= 7) {
+            /* partition into two segments */
+            i = lb + size;
+            j = lb + (n - 1) * size;
+            /* select pivot and exchange with 1st element */
+            m0 = (n >> 2) * size;
+            /* should use median of 3 or 9 */
+            m = med3_r(lb + m0, lb + 2 * m0, lb + 3 * m0, thunk, compare);
+
+            exchange(lb, m, size);
+
+            m0 = n - 1;  /* m is the offset of j */
+            for (;;) {
+                while (i < j && compare(thunk, lb, i) > 0) {
+                    i += size;
+                }
+                while (j >= i && compare(thunk, j, lb) > 0) {
+                    j -= size;
+                    m0--;
+                }
+                if (i >= j)
+                    break;
+                exchange(i, j, size);
+                i += size;
+                j -= size;
+                m0--;
+            }
+
+            /* pivot belongs in A[j] */
+            exchange(lb, j, size);
+
+            /* keep processing smallest segment,
+            * and stack largest */
+            n = n - m0 - 1;
+            if (m0 < n) {
+                if (n > 1) {
+                    sp->base = j + size;
+                    sp->count = n;
+                    sp++;
+                }
+                n = m0;
+            } else {
+                if (m0 > 1) {
+                    sp->base = lb;
+                    sp->count = m0;
+                    sp++;
+                }
+                lb = j + size;
+            }
+        }
+        /* Use insertion sort for small fragments */
+        for (i = lb + size, j = lb + n * size; i < j; i += size) {
+                       for (m = i; m > lb && compare(thunk, m - size, m) > 0; 
m -= size)
+                exchange(m, m - size, size);
+        }
+    }
+}