Mercurial > hg > xemacs-beta
annotate lib-src/qsort.c @ 5882:bbe4146603db
Reduce regexp usage, now CL-oriented non-regexp code available, core Lisp
lisp/ChangeLog addition:
2015-04-01 Aidan Kehoe <kehoea@parhasard.net>
When calling #'string-match with a REGEXP without regular
expression special characters, call #'search, #'mismatch, #'find,
etc. instead, making our code less likely to side-effect other
functions' match data and a little faster.
* apropos.el (apropos-command):
* apropos.el (apropos):
Call (position ?\n ...) rather than (string-match "\n" ...) here.
* buff-menu.el:
* buff-menu.el (buffers-menu-omit-invisible-buffers):
Don't fire up the regexp engine just to check if a string starts
with a space.
* buff-menu.el (select-buffers-tab-buffers-by-mode):
Don't fire up the regexp engine just to compare mode basenames.
* buff-menu.el (format-buffers-tab-line):
* buff-menu.el (build-buffers-tab-internal): Moved to being a
label within the following.
* buff-menu.el (buffers-tab-items): Use the label.
* bytecomp.el (byte-compile-log-1):
Don't fire up the regexp engine just to look for a newline.
* cus-edit.el (get):
Ditto.
* cus-edit.el (custom-variable-value-create):
Ditto, but for a colon.
* descr-text.el (describe-text-sexp):
Ditto.
* descr-text.el (describe-char-unicode-data):
Use #'split-string-by-char given that we're just looking for a
semicolon.
* descr-text.el (describe-char):
Don't fire up the regexp engine just to look for a newline.
* disass.el (disassemble-internal):
Ditto.
* files.el (file-name-sans-extension):
Implement this using #'position.
* files.el (file-name-extension):
Correct this function's docstring, implement it in terms of
#'position.
* files.el (insert-directory):
Don't fire up the regexp engine to split a string by space; don't
reverse the list of switches, this is actually a longstand bug as
far as I can see.
* gnuserv.el (gnuserv-process-filter):
Use #'position here, instead of consing inside #'split-string
needlessly.
* gtk-file-dialog.el (gtk-file-dialog-update-dropdown):
Use #'split-string-by-char here, don't fire up #'split-string for
directory-sep-char.
* gtk-font-menu.el (hack-font-truename):
Implement this more cheaply in terms of #'find,
#'split-string-by-char, #'equal, rather than #'string-match,
#'split-string, #'string-equal.
* hyper-apropos.el (hyper-apropos-grok-functions):
* hyper-apropos.el (hyper-apropos-grok-variables):
Look for a newline using #'position rather than #'string-match in
these functions.
* info.el (Info-insert-dir):
* info.el (Info-insert-file-contents):
* info.el (Info-follow-reference):
* info.el (Info-extract-menu-node-name):
* info.el (Info-menu):
Look for fixed strings using #'position or #'search as appropriate
in this file.
* ldap.el (ldap-decode-string):
* ldap.el (ldap-encode-string):
#'encode-coding-string, #'decode-coding-string are always
available, don't check if they're fboundp.
* ldap.el (ldap-decode-address):
* ldap.el (ldap-encode-address):
Use #'split-string-by-char in these functions.
* lisp-mnt.el (lm-creation-date):
* lisp-mnt.el (lm-last-modified-date):
Don't fire up the regexp engine just to look for spaces in this file.
* menubar-items.el (default-menubar):
Use (not (mismatch ...)) rather than #'string-match here, for
simple regexp.
Use (search "beta" ...) rather than (string-match "beta" ...)
* menubar-items.el (sort-buffers-menu-alphabetically):
* menubar-items.el (sort-buffers-menu-by-mode-then-alphabetically):
* menubar-items.el (group-buffers-menu-by-mode-then-alphabetically):
Don't fire up the regexp engine to check if a string starts with
a space or an asterisk.
Use the more fine-grained results of #'compare-strings; compare
case-insensitively for the buffer menu.
* menubar-items.el (list-all-buffers):
* menubar-items.el (tutorials-menu-filter):
Use #'equal rather than #'string-equal, which, in this context,
has the drawback of not having a bytecode, and no redeeming
features.
* minibuf.el:
* minibuf.el (un-substitute-in-file-name):
Use #'count, rather than counting the occurences of $ using the
regexp engine.
* minibuf.el (read-file-name-internal-1):
Don't fire up the regexp engine to search for ?=.
* mouse.el (mouse-eval-sexp):
Check for newline with #'find.
* msw-font-menu.el (mswindows-reset-device-font-menus):
Split a string by newline with #'split-string-by-char.
* mule/japanese.el:
* mule/japanese.el ("Japanese"):
Use #'search rather than #'string-match; canoncase before
comparing; fix a bug I had introduced where I had been making case
insensitive comparisons where the case mattered.
* mule/korea-util.el (default-korean-keyboard):
Look for ?3 using #'find, not #'string-march.
* mule/korea-util.el (quail-hangul-switch-hanja):
Search for a fixed string using #'search.
* mule/mule-cmds.el (set-locale-for-language-environment):
#'position, #'substitute rather than #'string-match,
#'replace-in-string.
* newcomment.el (comment-make-extra-lines):
Use #'search rather than #'string-match for a simple string.
* package-get.el (package-get-remote-filename):
Use #'position when looking for ?@
* process.el (setenv):
* process.el (read-envvar-name):
Use #'position when looking for ?=.
* replace.el (map-query-replace-regexp):
Use #'split-string-by-char instead of using an inline
implementation of it.
* select.el (select-convert-from-cf-text):
* select.el (select-convert-from-cf-unicodetext):
Use #'position rather than #'string-match in these functions.
* setup-paths.el (paths-emacs-data-root-p):
Use #'search when looking for simple string.
* sound.el (load-sound-file):
Use #'split-string-by-char rather than an inline reimplementation
of same.
* startup.el (splash-screen-window-body):
* startup.el (splash-screen-tty-body):
Search for simple strings using #'search.
* version.el (emacs-version):
Ditto.
* x-font-menu.el (hack-font-truename):
Implement this more cheaply in terms of #'find,
#'split-string-by-char, #'equal, rather than #'string-match,
#'split-string, #'string-equal.
* x-font-menu.el (x-reset-device-font-menus-core):
Use #'split-string-by-char here.
* x-init.el (x-initialize-keyboard):
Search for a simple string using #'search.
| author | Aidan Kehoe <kehoea@parhasard.net> |
|---|---|
| date | Wed, 01 Apr 2015 14:28:20 +0100 |
| parents | 061f4f90f874 |
| children |
| rev | line source |
|---|---|
| 0 | 1 /* Plug-compatible replacement for UNIX qsort. |
| 2 Copyright (C) 1989 Free Software Foundation, Inc. | |
| 3 Written by Douglas C. Schmidt (schmidt@ics.uci.edu) | |
| 4 | |
| 5 This file is part of GNU CC. | |
| 6 | |
|
5406
061f4f90f874
Convert lib-src/ to GPLv3.
Mike Sperber <sperber@deinprogramm.de>
parents:
444
diff
changeset
|
7 GNU QSORT is free software: you can redistribute it and/or modify it |
|
061f4f90f874
Convert lib-src/ to GPLv3.
Mike Sperber <sperber@deinprogramm.de>
parents:
444
diff
changeset
|
8 under the terms of the GNU General Public License as published by the |
|
061f4f90f874
Convert lib-src/ to GPLv3.
Mike Sperber <sperber@deinprogramm.de>
parents:
444
diff
changeset
|
9 Free Software Foundation, either version 3 of the License, or (at your |
|
061f4f90f874
Convert lib-src/ to GPLv3.
Mike Sperber <sperber@deinprogramm.de>
parents:
444
diff
changeset
|
10 option) any later version. |
| 0 | 11 |
|
5406
061f4f90f874
Convert lib-src/ to GPLv3.
Mike Sperber <sperber@deinprogramm.de>
parents:
444
diff
changeset
|
12 GNU QSORT is distributed in the hope that it will be useful, but WITHOUT |
|
061f4f90f874
Convert lib-src/ to GPLv3.
Mike Sperber <sperber@deinprogramm.de>
parents:
444
diff
changeset
|
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
061f4f90f874
Convert lib-src/ to GPLv3.
Mike Sperber <sperber@deinprogramm.de>
parents:
444
diff
changeset
|
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
061f4f90f874
Convert lib-src/ to GPLv3.
Mike Sperber <sperber@deinprogramm.de>
parents:
444
diff
changeset
|
15 for more details. |
| 0 | 16 |
| 17 You should have received a copy of the GNU General Public License | |
|
5406
061f4f90f874
Convert lib-src/ to GPLv3.
Mike Sperber <sperber@deinprogramm.de>
parents:
444
diff
changeset
|
18 along with GNU QSORT. If not, see <http://www.gnu.org/licenses/>. */ |
| 0 | 19 |
| 20 /* Synched up with: FSF 19.28. */ | |
| 21 | |
| 22 #ifdef sparc | |
| 23 #include <alloca.h> | |
| 24 #endif | |
| 25 | |
| 26 /* Invoke the comparison function, returns either 0, < 0, or > 0. */ | |
| 27 #define CMP(A,B) ((*cmp)((A),(B))) | |
| 28 | |
| 29 /* Byte-wise swap two items of size SIZE. */ | |
| 30 #define SWAP(A,B,SIZE) do {int sz = (SIZE); char *a = (A); char *b = (B); \ | |
| 31 do { char _temp = *a;*a++ = *b;*b++ = _temp;} while (--sz);} while (0) | |
| 32 | |
| 33 /* Copy SIZE bytes from item B to item A. */ | |
| 34 #define COPY(A,B,SIZE) {int sz = (SIZE); do { *(A)++ = *(B)++; } while (--sz); } | |
| 35 | |
| 36 /* This should be replaced by a standard ANSI macro. */ | |
| 37 #define BYTES_PER_WORD 8 | |
| 38 | |
| 39 /* The next 4 #defines implement a very fast in-line stack abstraction. */ | |
| 40 #define STACK_SIZE (BYTES_PER_WORD * sizeof (long)) | |
| 41 #define PUSH(LOW,HIGH) do {top->lo = LOW;top++->hi = HIGH;} while (0) | |
| 42 #define POP(LOW,HIGH) do {LOW = (--top)->lo;HIGH = top->hi;} while (0) | |
| 43 #define STACK_NOT_EMPTY (stack < top) | |
| 44 | |
| 45 /* Discontinue quicksort algorithm when partition gets below this size. | |
| 46 This particular magic number was chosen to work best on a Sun 4/260. */ | |
| 47 #define MAX_THRESH 4 | |
| 48 | |
| 49 /* Stack node declarations used to store unfulfilled partition obligations. */ | |
| 50 typedef struct | |
| 51 { | |
| 52 char *lo; | |
| 53 char *hi; | |
| 54 } stack_node; | |
| 55 | |
| 56 /* Order size using quicksort. This implementation incorporates | |
| 57 four optimizations discussed in Sedgewick: | |
| 58 | |
| 59 1. Non-recursive, using an explicit stack of pointer that store the | |
| 60 next array partition to sort. To save time, this maximum amount | |
| 61 of space required to store an array of MAX_INT is allocated on the | |
| 62 stack. Assuming a 32-bit integer, this needs only 32 * | |
| 63 sizeof (stack_node) == 136 bits. Pretty cheap, actually. | |
| 64 | |
| 444 | 65 2. Choose the pivot element using a median-of-three decision tree. |
| 0 | 66 This reduces the probability of selecting a bad pivot value and |
| 67 eliminates certain extraneous comparisons. | |
| 68 | |
| 69 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving | |
| 70 insertion sort to order the MAX_THRESH items within each partition. | |
| 71 This is a big win, since insertion sort is faster for small, mostly | |
| 72 sorted array segments. | |
| 73 | |
| 74 4. The larger of the two sub-partitions is always pushed onto the | |
| 75 stack first, with the algorithm then concentrating on the | |
| 76 smaller partition. This *guarantees* no more than log (n) | |
| 77 stack size is needed (actually O(1) in this case)! */ | |
| 78 | |
| 79 int | |
| 80 qsort (base_ptr, total_elems, size, cmp) | |
| 81 char *base_ptr; | |
| 82 int total_elems; | |
| 83 int size; | |
| 84 int (*cmp)(); | |
| 85 { | |
| 86 /* Allocating SIZE bytes for a pivot buffer facilitates a better | |
| 87 algorithm below since we can do comparisons directly on the pivot. */ | |
| 88 char *pivot_buffer = (char *) alloca (size); | |
| 89 int max_thresh = MAX_THRESH * size; | |
| 90 | |
| 91 if (total_elems > MAX_THRESH) | |
| 92 { | |
| 93 char *lo = base_ptr; | |
| 94 char *hi = lo + size * (total_elems - 1); | |
| 95 stack_node stack[STACK_SIZE]; /* Largest size needed for 32-bit int!!! */ | |
| 96 stack_node *top = stack + 1; | |
| 97 | |
| 98 while (STACK_NOT_EMPTY) | |
| 99 { | |
| 100 char *left_ptr; | |
| 101 char *right_ptr; | |
| 102 { | |
| 103 char *pivot = pivot_buffer; | |
| 104 { | |
| 105 /* Select median value from among LO, MID, and HI. Rearrange | |
| 106 LO and HI so the three values are sorted. This lowers the | |
| 107 probability of picking a pathological pivot value and | |
| 108 skips a comparison for both the LEFT_PTR and RIGHT_PTR. */ | |
| 109 | |
| 110 char *mid = lo + size * ((hi - lo) / size >> 1); | |
| 111 | |
| 112 if (CMP (mid, lo) < 0) | |
| 113 SWAP (mid, lo, size); | |
| 114 if (CMP (hi, mid) < 0) | |
| 115 SWAP (mid, hi, size); | |
| 116 else | |
| 117 goto jump_over; | |
| 118 if (CMP (mid, lo) < 0) | |
| 119 SWAP (mid, lo, size); | |
| 120 jump_over: | |
| 121 COPY (pivot, mid, size); | |
| 122 pivot = pivot_buffer; | |
| 123 } | |
| 124 left_ptr = lo + size; | |
| 125 right_ptr = hi - size; | |
| 126 | |
| 127 /* Here's the famous ``collapse the walls'' section of quicksort. | |
| 128 Gotta like those tight inner loops! They are the main reason | |
| 129 that this algorithm runs much faster than others. */ | |
| 130 do | |
| 131 { | |
| 132 while (CMP (left_ptr, pivot) < 0) | |
| 133 left_ptr += size; | |
| 134 | |
| 135 while (CMP (pivot, right_ptr) < 0) | |
| 136 right_ptr -= size; | |
| 137 | |
| 138 if (left_ptr < right_ptr) | |
| 139 { | |
| 140 SWAP (left_ptr, right_ptr, size); | |
| 141 left_ptr += size; | |
| 142 right_ptr -= size; | |
| 143 } | |
| 144 else if (left_ptr == right_ptr) | |
| 145 { | |
| 146 left_ptr += size; | |
| 147 right_ptr -= size; | |
| 148 break; | |
| 149 } | |
| 150 } | |
| 151 while (left_ptr <= right_ptr); | |
| 152 | |
| 153 } | |
| 154 | |
| 155 /* Set up pointers for next iteration. First determine whether | |
| 156 left and right partitions are below the threshold size. If so, | |
| 157 ignore one or both. Otherwise, push the larger partition's | |
| 158 bounds on the stack and continue sorting the smaller one. */ | |
| 159 | |
| 160 if ((right_ptr - lo) <= max_thresh) | |
| 161 { | |
| 162 if ((hi - left_ptr) <= max_thresh) /* Ignore both small partitions. */ | |
| 163 POP (lo, hi); | |
| 164 else /* Ignore small left partition. */ | |
| 165 lo = left_ptr; | |
| 166 } | |
| 167 else if ((hi - left_ptr) <= max_thresh) /* Ignore small right partition. */ | |
| 168 hi = right_ptr; | |
| 169 else if ((right_ptr - lo) > (hi - left_ptr)) /* Push larger left partition indices. */ | |
| 170 { | |
| 171 PUSH (lo, right_ptr); | |
| 172 lo = left_ptr; | |
| 173 } | |
| 174 else /* Push larger right partition indices. */ | |
| 175 { | |
| 176 PUSH (left_ptr, hi); | |
| 177 hi = right_ptr; | |
| 178 } | |
| 179 } | |
| 180 } | |
| 181 | |
| 182 /* Once the BASE_PTR array is partially sorted by quicksort the rest | |
| 183 is completely sorted using insertion sort, since this is efficient | |
| 184 for partitions below MAX_THRESH size. BASE_PTR points to the beginning | |
| 185 of the array to sort, and END_PTR points at the very last element in | |
| 186 the array (*not* one beyond it!). */ | |
| 187 | |
| 188 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) | |
| 189 | |
| 190 { | |
| 191 char *end_ptr = base_ptr + size * (total_elems - 1); | |
| 192 char *run_ptr; | |
| 193 char *tmp_ptr = base_ptr; | |
| 194 char *thresh = MIN (end_ptr, base_ptr + max_thresh); | |
| 195 | |
| 196 /* Find smallest element in first threshold and place it at the | |
| 197 array's beginning. This is the smallest array element, | |
| 198 and the operation speeds up insertion sort's inner loop. */ | |
| 199 | |
| 200 for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) | |
| 201 if (CMP (run_ptr, tmp_ptr) < 0) | |
| 202 tmp_ptr = run_ptr; | |
| 203 | |
| 204 if (tmp_ptr != base_ptr) | |
| 205 SWAP (tmp_ptr, base_ptr, size); | |
| 206 | |
| 207 /* Insertion sort, running from left-hand-side up to `right-hand-side.' | |
| 208 Pretty much straight out of the original GNU qsort routine. */ | |
| 209 | |
| 210 for (run_ptr = base_ptr + size; (tmp_ptr = run_ptr += size) <= end_ptr; ) | |
| 211 { | |
| 212 | |
| 213 while (CMP (run_ptr, tmp_ptr -= size) < 0) | |
| 214 ; | |
| 215 | |
| 216 if ((tmp_ptr += size) != run_ptr) | |
| 217 { | |
| 218 char *trav; | |
| 219 | |
| 220 for (trav = run_ptr + size; --trav >= run_ptr;) | |
| 221 { | |
| 222 char c = *trav; | |
| 223 char *hi, *lo; | |
| 224 | |
| 225 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) | |
| 226 *hi = *lo; | |
| 227 *hi = c; | |
| 228 } | |
| 229 } | |
| 230 | |
| 231 } | |
| 232 } | |
| 233 return 1; | |
| 234 } | |
| 235 |