Mercurial > hg > xemacs-beta
annotate lib-src/qsort.c @ 4953:304aebb79cd3
function renamings to track names of char typedefs
-------------------- ChangeLog entries follow: --------------------
man/ChangeLog addition:
2010-01-27 Ben Wing <ben@xemacs.org>
* internals/internals.texi (lrecords):
* internals/internals.texi (The DFC API):
* internals/internals.texi (Conversion to and from External Data):
* internals/internals.texi (Mule-izing Code):
* internals/internals.texi (Pervasive changes throughout XEmacs sources):
* internals/internals.texi (Ben's README):
* internals/internals.texi (Future Work -- Localized Text/Messages):
* emodules.texi (Defining Variables):
Rename:
write_c_string -> write_cistring
build_intstring -> build_istring
build_string -> build_cistring
build_ext_string -> build_extstring
make_ext_string -> make_extstring
buffer_insert_c_string -> buffer_insert_ascstring
intern_int -> intern_istring
See comment in src/ChangeLog about this.
modules/ChangeLog addition:
2010-01-27 Ben Wing <ben@xemacs.org>
* postgresql/postgresql.c (print_pgconn):
* postgresql/postgresql.c (print_pgresult):
* postgresql/postgresql.c (Fpq_conn_defaults):
* postgresql/postgresql.c (Fpq_pgconn):
* postgresql/postgresql.c (Fpq_res_status):
* postgresql/postgresql.c (Fpq_result_error_message):
* postgresql/postgresql.c (Fpq_fname):
* postgresql/postgresql.c (Fpq_get_value):
* postgresql/postgresql.c (Fpq_cmd_status):
* postgresql/postgresql.c (Fpq_cmd_tuples):
* postgresql/postgresql.c (Fpq_notifies):
* postgresql/postgresql.c (Fpq_get_line):
* postgresql/postgresql.c (Fpq_get_line_async):
* postgresql/postgresql.c (FROB):
* postgresql/postgresql.c (init_postgresql_from_environment):
* ldap/eldap.c:
* ldap/eldap.c (Fldap_open):
* ldap/eldap.c (Fldap_search_basic):
* canna/canna_api.c:
* canna/canna_api.c (make_euc_string):
Rename:
write_c_string -> write_cistring
build_intstring -> build_istring
build_string -> build_cistring
build_ext_string -> build_extstring
make_ext_string -> make_extstring
buffer_insert_c_string -> buffer_insert_ascstring
intern_int -> intern_istring
See comment in src/ChangeLog about this.
src/ChangeLog addition:
2010-01-27 Ben Wing <ben@xemacs.org>
* .gdbinit.in.in:
* README:
* abbrev.c (write_abbrev):
* abbrev.c (describe_abbrev):
* alloc.c (make_extstring):
* alloc.c (build_istring):
* alloc.c (build_cistring):
* alloc.c (build_ascstring):
* alloc.c (build_extstring):
* alloc.c (build_msg_istring):
* alloc.c (build_defer_istring):
* buffer.c (Fgenerate_new_buffer_name):
* buffer.c (init_buffer_2):
* console-tty.c (tty_init_console):
* console-x.c (get_display_arg_connection):
* console-x.c (x_perhaps_init_unseen_key_defaults):
* database.c (dbm_map):
* database.c (dbm_get):
* database.c (berkdb_get):
* database.c (berkdb_map):
* device-gtk.c (FROB_PIXMAP):
* device-gtk.c (Fgtk_style_info):
* device-msw.c (msprinter_default_printer):
* device-msw.c (sync_printer_with_devmode):
* device-x.c (coding_system_of_xrm_database):
* device-x.c (x_init_device):
* device-x.c (signal_if_x_error):
* device-x.c (Fx_get_resource):
* device-x.c (Fx_server_vendor):
* device-x.c (Fx_get_font_path):
* dialog-x.c (maybe_run_dbox_text_callback):
* doc.c (extract_object_file_name):
* doc.c (unparesseuxify_doc_string):
* doc.c (get_doc_string):
* doc.c (get_object_file_name):
* doc.c (Fdocumentation):
* doc.c (Fsnarf_documentation):
* doc.c (Fsubstitute_command_keys):
* editfns.c (init_editfns):
* editfns.c (Ftemp_directory):
* editfns.c (Fuser_login_name):
* editfns.c (Fuser_real_login_name):
* editfns.c (Fuser_home_directory):
* editfns.c (Fformat_time_string):
* editfns.c (Fcurrent_time_string):
* editfns.c (Fcurrent_time_zone):
* emacs.c:
* emacs.c (main_1):
* emodules.c (Flist_modules):
* emodules.c (emodules_load):
* emodules.c (emodules_doc_sym):
* emodules.c (vars_of_module):
* event-Xt.c (x_has_keysym):
* event-gtk.c (emacs_gtk_format_magic_event):
* event-gtk.c (dragndrop_data_received):
* event-gtk.c (gtk_reset_key_mapping):
* event-msw.c (mswindows_dde_callback):
* event-msw.c (mswindows_wnd_proc):
* faces.c (complex_vars_of_faces):
* file-coding.c (find_coding_system):
* file-coding.c (setup_eol_coding_systems):
* file-coding.c (make_coding_system_1):
* file-coding.c (snarf_coding_system):
* fileio.c:
* fileio.c (lisp_strerror):
* fileio.c (Ffile_name_directory):
* fileio.c (Ffile_name_as_directory):
* fileio.c (Fdirectory_file_name):
* fileio.c (if):
* fileio.c (Ffile_symlink_p):
* fileio.c (Fencrypt_string):
* fileio.c (Fdecrypt_string):
* filelock.c (lock_file):
* filelock.c (Ffile_locked_p):
* floatfns.c (matherr):
* font-mgr.c (build_fcapi_string):
* font-mgr.c (make_xlfd_font_regexp):
* frame-msw.c (mswindows_window_id):
* frame-msw.c (mswindows_frame_property):
* frame-x.c:
* frame-x.c (color_to_string):
* frame-x.c (maybe_set_frame_title_format):
* frame-x.c (x_cde_transfer_callback):
* frame-x.c (Fx_window_id):
* glade.c (connector):
* glade.c (Fglade_xml_textdomain):
* glade.c (syms_of_glade):
* glyphs-eimage.c (jpeg_instantiate):
* glyphs-eimage.c (png_instantiate):
* glyphs-eimage.c (tiff_instantiate):
* glyphs-gtk.c (font_instantiate):
* glyphs-gtk.c (BUILD_GLYPH_INST):
* glyphs-x.c (x_locate_pixmap_file):
* glyphs-x.c (font_instantiate):
* glyphs-x.c (x_widget_property):
* glyphs-x.c (BUILD_GLYPH_INST):
* glyphs.c (print_image_instance):
* glyphs.c (bitmap_to_lisp_data):
* glyphs.c (pixmap_to_lisp_data):
* gpmevent.c (turn_off_gpm):
* gpmevent.c (Fgpm_enabled_p):
* gpmevent.c (Fgpm_enable):
* gtk-glue.c (__make_string_mapper):
* gtk-glue.c (xemacs_gtklist_to_list):
* gtk-xemacs.c (FROB_FACE):
* gtk-xemacs.c (xemacs_gtk_convert_color):
* hpplay.c (player_error_internal):
* hpplay.c (myHandler):
* insdel.c (buffer_insert_ascstring_1):
* insdel.h:
* insdel.h (buffer_insert_ascstring):
* intl.c (Fcurrent_locale):
* intl.c (Fset_current_locale):
* keymap.c (make_key_description):
* keymap.c (Ftext_char_description):
* keymap.c (describe_command):
* keymap.c (describe_map):
* lisp.h:
* lread.c:
* lread.c (locate_file_in_directory_mapper):
* lread.c (locate_file_construct_suffixed_files_mapper):
* mule-charset.c (Fmake_charset):
* nt.c (Fmswindows_short_file_name):
* nt.c (Fmswindows_long_file_name):
* objects-gtk.c (__get_gtk_font_truename):
* objects-gtk.c (__gtk_font_list_internal):
* objects-msw.c (font_enum_callback_2):
* objects-msw.c (create_hfont_from_font_spec):
* objects-msw.c (mswindows_font_list):
* objects-msw.c (mswindows_font_spec_matches_charset_stage_2):
* objects-tty.c (tty_initialize_font_instance):
* objects-x.c (x_font_truename):
* objects-x.c (x_font_instance_truename):
* objects-x.c (x_font_instance_properties):
* objects-x.c (x_font_list):
* print.c (write_cistring):
* print.c (print_vector_internal):
* print.c (print_cons):
* process-nt.c (nt_canonicalize_host_name):
* process-unix.c (unix_create_process):
* process-unix.c (unix_canonicalize_host_name):
* process.c (status_message):
* process.c (status_notify):
* process.c (init_xemacs_process):
* process.c (syms_of_process):
* redisplay-tty.c (term_get_fkeys_1):
* redisplay-tty.c (CONDITIONAL_REASSIGN):
* search.c (compile_pattern_1):
* select-common.h (selection_data_to_lisp_data):
* select-gtk.c (atom_to_symbol):
* select-gtk.c (PROCESSING_GTK_CODE):
* select-msw.c (mswindows_get_foreign_selection):
* select-x.c (x_atom_to_symbol):
* select-x.c (Fx_get_cutbuffer_internal):
* symbols.c (intern_istring):
* symbols.c (intern):
* symbols.c (intern_converting_underscores_to_dashes):
* symbols.c (Fintern):
* sysdep.c (init_system_name):
* sysdll.c (dll_error):
* sysdll.c (dll_open):
* syswindows.h:
* syswindows.h (build_tstr_string):
* tests.c (DFC_CHECK_LENGTH):
* tests.c (DFC_CHECK_CONTENT):
* tests.c (DFC_RESULT_PASS):
* tests.c (Ftest_data_format_conversion):
* text.c:
* text.c (new_dfc_convert_now_damn_it):
* text.h:
* text.h (build_wext_string):
* tooltalk.c (tt_build_c_string):
* tooltalk.c (Ftooltalk_default_procid):
* tooltalk.c (Ftooltalk_default_session):
* tooltalk.c (init_tooltalk):
* ui-byhand.c (Fgtk_clist_get_text):
* ui-byhand.c (Fgtk_clist_get_pixtext):
* ui-byhand.c (Fgtk_label_get):
* ui-byhand.c (Fgtk_notebook_query_tab_label_packing):
* ui-gtk.c (emacs_gtk_object_printer):
* ui-gtk.c (emacs_gtk_boxed_printer):
* ui-gtk.c (gtk_type_to_lisp):
* ui-gtk.c (symbol_to_enum):
* ui-gtk.c (enum_to_symbol):
* unexaix.c (report_error):
* unexaix.c (ERROR0):
* unexec.c (report_error):
* unexec.c (ERROR0):
* unicode.c (unicode_to_ichar):
* win32.c (tstr_to_local_file_format):
* win32.c (Fmswindows_cygwin_to_win32_path):
* win32.c (struct read_link_hash):
* xemacs.def.in.in:
Rename:
write_c_string -> write_cistring
build_intstring -> build_istring
build_string -> build_cistring
build_ext_string -> build_extstring
make_ext_string -> make_extstring
buffer_insert_c_string -> buffer_insert_ascstring
intern_int -> intern_istring
These functions have been renamed so that the naming harmonizes
with the typedefs for strings: `cistring' along with CIbyte *,
`istring' along with Ibyte *, `extstring' along with Extbyte *,
`ascstring' along with Ascbyte *.
Also make buffer_insert_ascstring take Ascbyte * and assert
that its argument is ASCII.
| author | Ben Wing <ben@xemacs.org> |
|---|---|
| date | Wed, 27 Jan 2010 00:35:36 -0600 |
| parents | 576fb035e263 |
| children | 061f4f90f874 |
| 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 | |
| 7 GNU QSORT is free software; you can redistribute it and/or modify | |
| 8 it under the terms of the GNU General Public License as published by | |
| 9 the Free Software Foundation; either version 2, or (at your option) | |
| 10 any later version. | |
| 11 | |
| 12 GNU QSORT is distributed in the hope that it will be useful, | |
| 13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 15 GNU General Public License for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 18 along with GNU QSORT; see the file COPYING. If not, write to | |
| 19 the Free the Free Software Foundation, Inc., 59 Temple Place - Suite 330, | |
| 20 Boston, MA 02111-1307, USA. */ | |
| 21 | |
| 22 /* Synched up with: FSF 19.28. */ | |
| 23 | |
| 24 #ifdef sparc | |
| 25 #include <alloca.h> | |
| 26 #endif | |
| 27 | |
| 28 /* Invoke the comparison function, returns either 0, < 0, or > 0. */ | |
| 29 #define CMP(A,B) ((*cmp)((A),(B))) | |
| 30 | |
| 31 /* Byte-wise swap two items of size SIZE. */ | |
| 32 #define SWAP(A,B,SIZE) do {int sz = (SIZE); char *a = (A); char *b = (B); \ | |
| 33 do { char _temp = *a;*a++ = *b;*b++ = _temp;} while (--sz);} while (0) | |
| 34 | |
| 35 /* Copy SIZE bytes from item B to item A. */ | |
| 36 #define COPY(A,B,SIZE) {int sz = (SIZE); do { *(A)++ = *(B)++; } while (--sz); } | |
| 37 | |
| 38 /* This should be replaced by a standard ANSI macro. */ | |
| 39 #define BYTES_PER_WORD 8 | |
| 40 | |
| 41 /* The next 4 #defines implement a very fast in-line stack abstraction. */ | |
| 42 #define STACK_SIZE (BYTES_PER_WORD * sizeof (long)) | |
| 43 #define PUSH(LOW,HIGH) do {top->lo = LOW;top++->hi = HIGH;} while (0) | |
| 44 #define POP(LOW,HIGH) do {LOW = (--top)->lo;HIGH = top->hi;} while (0) | |
| 45 #define STACK_NOT_EMPTY (stack < top) | |
| 46 | |
| 47 /* Discontinue quicksort algorithm when partition gets below this size. | |
| 48 This particular magic number was chosen to work best on a Sun 4/260. */ | |
| 49 #define MAX_THRESH 4 | |
| 50 | |
| 51 /* Stack node declarations used to store unfulfilled partition obligations. */ | |
| 52 typedef struct | |
| 53 { | |
| 54 char *lo; | |
| 55 char *hi; | |
| 56 } stack_node; | |
| 57 | |
| 58 /* Order size using quicksort. This implementation incorporates | |
| 59 four optimizations discussed in Sedgewick: | |
| 60 | |
| 61 1. Non-recursive, using an explicit stack of pointer that store the | |
| 62 next array partition to sort. To save time, this maximum amount | |
| 63 of space required to store an array of MAX_INT is allocated on the | |
| 64 stack. Assuming a 32-bit integer, this needs only 32 * | |
| 65 sizeof (stack_node) == 136 bits. Pretty cheap, actually. | |
| 66 | |
| 444 | 67 2. Choose the pivot element using a median-of-three decision tree. |
| 0 | 68 This reduces the probability of selecting a bad pivot value and |
| 69 eliminates certain extraneous comparisons. | |
| 70 | |
| 71 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving | |
| 72 insertion sort to order the MAX_THRESH items within each partition. | |
| 73 This is a big win, since insertion sort is faster for small, mostly | |
| 74 sorted array segments. | |
| 75 | |
| 76 4. The larger of the two sub-partitions is always pushed onto the | |
| 77 stack first, with the algorithm then concentrating on the | |
| 78 smaller partition. This *guarantees* no more than log (n) | |
| 79 stack size is needed (actually O(1) in this case)! */ | |
| 80 | |
| 81 int | |
| 82 qsort (base_ptr, total_elems, size, cmp) | |
| 83 char *base_ptr; | |
| 84 int total_elems; | |
| 85 int size; | |
| 86 int (*cmp)(); | |
| 87 { | |
| 88 /* Allocating SIZE bytes for a pivot buffer facilitates a better | |
| 89 algorithm below since we can do comparisons directly on the pivot. */ | |
| 90 char *pivot_buffer = (char *) alloca (size); | |
| 91 int max_thresh = MAX_THRESH * size; | |
| 92 | |
| 93 if (total_elems > MAX_THRESH) | |
| 94 { | |
| 95 char *lo = base_ptr; | |
| 96 char *hi = lo + size * (total_elems - 1); | |
| 97 stack_node stack[STACK_SIZE]; /* Largest size needed for 32-bit int!!! */ | |
| 98 stack_node *top = stack + 1; | |
| 99 | |
| 100 while (STACK_NOT_EMPTY) | |
| 101 { | |
| 102 char *left_ptr; | |
| 103 char *right_ptr; | |
| 104 { | |
| 105 char *pivot = pivot_buffer; | |
| 106 { | |
| 107 /* Select median value from among LO, MID, and HI. Rearrange | |
| 108 LO and HI so the three values are sorted. This lowers the | |
| 109 probability of picking a pathological pivot value and | |
| 110 skips a comparison for both the LEFT_PTR and RIGHT_PTR. */ | |
| 111 | |
| 112 char *mid = lo + size * ((hi - lo) / size >> 1); | |
| 113 | |
| 114 if (CMP (mid, lo) < 0) | |
| 115 SWAP (mid, lo, size); | |
| 116 if (CMP (hi, mid) < 0) | |
| 117 SWAP (mid, hi, size); | |
| 118 else | |
| 119 goto jump_over; | |
| 120 if (CMP (mid, lo) < 0) | |
| 121 SWAP (mid, lo, size); | |
| 122 jump_over: | |
| 123 COPY (pivot, mid, size); | |
| 124 pivot = pivot_buffer; | |
| 125 } | |
| 126 left_ptr = lo + size; | |
| 127 right_ptr = hi - size; | |
| 128 | |
| 129 /* Here's the famous ``collapse the walls'' section of quicksort. | |
| 130 Gotta like those tight inner loops! They are the main reason | |
| 131 that this algorithm runs much faster than others. */ | |
| 132 do | |
| 133 { | |
| 134 while (CMP (left_ptr, pivot) < 0) | |
| 135 left_ptr += size; | |
| 136 | |
| 137 while (CMP (pivot, right_ptr) < 0) | |
| 138 right_ptr -= size; | |
| 139 | |
| 140 if (left_ptr < right_ptr) | |
| 141 { | |
| 142 SWAP (left_ptr, right_ptr, size); | |
| 143 left_ptr += size; | |
| 144 right_ptr -= size; | |
| 145 } | |
| 146 else if (left_ptr == right_ptr) | |
| 147 { | |
| 148 left_ptr += size; | |
| 149 right_ptr -= size; | |
| 150 break; | |
| 151 } | |
| 152 } | |
| 153 while (left_ptr <= right_ptr); | |
| 154 | |
| 155 } | |
| 156 | |
| 157 /* Set up pointers for next iteration. First determine whether | |
| 158 left and right partitions are below the threshold size. If so, | |
| 159 ignore one or both. Otherwise, push the larger partition's | |
| 160 bounds on the stack and continue sorting the smaller one. */ | |
| 161 | |
| 162 if ((right_ptr - lo) <= max_thresh) | |
| 163 { | |
| 164 if ((hi - left_ptr) <= max_thresh) /* Ignore both small partitions. */ | |
| 165 POP (lo, hi); | |
| 166 else /* Ignore small left partition. */ | |
| 167 lo = left_ptr; | |
| 168 } | |
| 169 else if ((hi - left_ptr) <= max_thresh) /* Ignore small right partition. */ | |
| 170 hi = right_ptr; | |
| 171 else if ((right_ptr - lo) > (hi - left_ptr)) /* Push larger left partition indices. */ | |
| 172 { | |
| 173 PUSH (lo, right_ptr); | |
| 174 lo = left_ptr; | |
| 175 } | |
| 176 else /* Push larger right partition indices. */ | |
| 177 { | |
| 178 PUSH (left_ptr, hi); | |
| 179 hi = right_ptr; | |
| 180 } | |
| 181 } | |
| 182 } | |
| 183 | |
| 184 /* Once the BASE_PTR array is partially sorted by quicksort the rest | |
| 185 is completely sorted using insertion sort, since this is efficient | |
| 186 for partitions below MAX_THRESH size. BASE_PTR points to the beginning | |
| 187 of the array to sort, and END_PTR points at the very last element in | |
| 188 the array (*not* one beyond it!). */ | |
| 189 | |
| 190 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) | |
| 191 | |
| 192 { | |
| 193 char *end_ptr = base_ptr + size * (total_elems - 1); | |
| 194 char *run_ptr; | |
| 195 char *tmp_ptr = base_ptr; | |
| 196 char *thresh = MIN (end_ptr, base_ptr + max_thresh); | |
| 197 | |
| 198 /* Find smallest element in first threshold and place it at the | |
| 199 array's beginning. This is the smallest array element, | |
| 200 and the operation speeds up insertion sort's inner loop. */ | |
| 201 | |
| 202 for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) | |
| 203 if (CMP (run_ptr, tmp_ptr) < 0) | |
| 204 tmp_ptr = run_ptr; | |
| 205 | |
| 206 if (tmp_ptr != base_ptr) | |
| 207 SWAP (tmp_ptr, base_ptr, size); | |
| 208 | |
| 209 /* Insertion sort, running from left-hand-side up to `right-hand-side.' | |
| 210 Pretty much straight out of the original GNU qsort routine. */ | |
| 211 | |
| 212 for (run_ptr = base_ptr + size; (tmp_ptr = run_ptr += size) <= end_ptr; ) | |
| 213 { | |
| 214 | |
| 215 while (CMP (run_ptr, tmp_ptr -= size) < 0) | |
| 216 ; | |
| 217 | |
| 218 if ((tmp_ptr += size) != run_ptr) | |
| 219 { | |
| 220 char *trav; | |
| 221 | |
| 222 for (trav = run_ptr + size; --trav >= run_ptr;) | |
| 223 { | |
| 224 char c = *trav; | |
| 225 char *hi, *lo; | |
| 226 | |
| 227 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) | |
| 228 *hi = *lo; | |
| 229 *hi = c; | |
| 230 } | |
| 231 } | |
| 232 | |
| 233 } | |
| 234 } | |
| 235 return 1; | |
| 236 } | |
| 237 |