From 658d70ae9cc37440535100ae5dd95cb8e7ba7778 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Sat, 13 Dec 2003 07:17:25 +0000 Subject: [PATCH] * qsort.c: Removed because it was unused. * Makefile.am: Revised accordingly, and simplified because Automake 1.7 is smarter than 1.4 was. --- lib/misc/ChangeLog | 7 ++ lib/misc/Makefile.am | 9 +- lib/misc/qsort.c | 257 ------------------------------------------- 3 files changed, 9 insertions(+), 264 deletions(-) delete mode 100644 lib/misc/qsort.c diff --git a/lib/misc/ChangeLog b/lib/misc/ChangeLog index 9bcae51a..3845fa6e 100644 --- a/lib/misc/ChangeLog +++ b/lib/misc/ChangeLog @@ -1,3 +1,10 @@ +Fri Dec 12 22:59:37 2003 Ben Pfaff + + * qsort.c: Removed because it was unused. + + * Makefile.am: Revised accordingly, and simplified because + Automake 1.7 is smarter than 1.4 was. + Sun Jan 2 21:35:47 2000 Ben Pfaff * qsort.c: Change headers. Fix __attribute__ for gcc 2.7.2. diff --git a/lib/misc/Makefile.am b/lib/misc/Makefile.am index e47445a1..15a2a9a0 100644 --- a/lib/misc/Makefile.am +++ b/lib/misc/Makefile.am @@ -5,12 +5,7 @@ noinst_LIBRARIES = libmisc.a INCLUDES = -I$(srcdir) -I$(top_srcdir)/src -I$(top_srcdir) \ -I$(top_srcdir)/intl -libmisc_a_SOURCES = qsort.c -libmisc_a_LIBADD = @ALLOCA@ @LIBOBJS@ -libmisc_a_DEPENDENCIES = @ALLOCA@ @LIBOBJS@ - -EXTRA_DIST = alloca.c getdelim.c getline.c memchr.c memcmp.c memcpy.c \ -memmem.c memmove.c memset.c stpcpy.c strcasecmp.c strerror.c \ -strncasecmp.c strpbrk.c strstr.c strtok_r.c strtol.c strtoul.c +libmisc_a_SOURCES = +libmisc_a_LIBADD = $(ALLOCA) $(LIBOBJS) MAINTAINERCLEANFILES = Makefile.in diff --git a/lib/misc/qsort.c b/lib/misc/qsort.c deleted file mode 100644 index 23f47c58..00000000 --- a/lib/misc/qsort.c +++ /dev/null @@ -1,257 +0,0 @@ -/* Copyright (C) 1991, 1992 Free Software Foundation, Inc. - This file is part of the GNU C Library. - Written by Douglas C. Schmidt (schmidt@ics.uci.edu). - - The GNU C Library is free software; you can redistribute it and/or - modify it under the terms of the GNU Library General Public License as - published by the Free Software Foundation; either version 2 of the - License, or (at your option) any later version. - - The GNU C Library is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Library General Public License for more details. - - You should have received a copy of the GNU Library General Public - License along with the GNU C Library; see the file COPYING.LIB. If - not, write to the Free Software Foundation, Inc., 675 Mass Ave, - Cambridge, MA 02139, USA. */ - -/* Modified 12/15/96 by Ben Pfaff for PSPP. */ - -#include -#include -#include -#include "alloc.h" - -/* Byte-wise swap two items of size SIZE. */ -#define SWAP(a, b, size) \ - do \ - { \ - register size_t __size = (size); \ - register char *__a = (a), *__b = (b); \ - do \ - { \ - char __tmp = *__a; \ - *__a++ = *__b; \ - *__b++ = __tmp; \ - } while (--__size > 0); \ - } while (0) - -/* Discontinue quicksort algorithm when partition gets below this size. - This particular magic number was chosen to work best on a Sun 4/260. */ -#define MAX_THRESH 4 - -/* Stack node declarations used to store unfulfilled partition obligations. */ -typedef struct - { - char *lo; - char *hi; - } -stack_node; - -/* The next 4 #defines implement a very fast in-line stack abstraction. */ -#define STACK_SIZE (8 * sizeof(unsigned long int)) -#define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top)) -#define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi))) -#define STACK_NOT_EMPTY (stack < top) - - -/* Order size using quicksort. This implementation incorporates - four optimizations discussed in Sedgewick: - - 1. Non-recursive, using an explicit stack of pointer that store the - next array partition to sort. To save time, this maximum amount - of space required to store an array of MAX_INT is allocated on the - stack. Assuming a 32-bit integer, this needs only 32 * - sizeof(stack_node) == 136 bits. Pretty cheap, actually. - - 2. Chose the pivot element using a median-of-three decision tree. - This reduces the probability of selecting a bad pivot value and - eliminates certain extraneous comparisons. - - 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving - insertion sort to order the MAX_THRESH items within each partition. - This is a big win, since insertion sort is faster for small, mostly - sorted array segements. - - 4. The larger of the two sub-partitions is always pushed onto the - stack first, with the algorithm then concentrating on the - smaller partition. This *guarantees* no more than log (n) - stack size is needed (actually O(1) in this case)! */ - -void -blp_quicksort (void *pbase, size_t total_elems, size_t size, - int (*cmp) (const void *, const void *), - void *temp_buf -#if HAVE_ALLOCA - unused -#endif - ) -{ - register char *base_ptr = (char *) pbase; - - /* Allocating SIZE bytes for a pivot buffer facilitates a better - algorithm below since we can do comparisons directly on the pivot. */ -#if HAVE_ALLOCA - char *pivot_buffer = (char *) local_alloc (size); -#else - char *pivot_buffer = temp_buf; -#endif - const size_t max_thresh = MAX_THRESH * size; - - if (total_elems == 0) - { - /* Avoid lossage with unsigned arithmetic below. */ - local_free (pivot_buffer); - return; - } - - if (total_elems > MAX_THRESH) - { - char *lo = base_ptr; - char *hi = &lo[size * (total_elems - 1)]; - /* Largest size needed for 32-bit int!!! */ - stack_node stack[STACK_SIZE]; - stack_node *top = stack + 1; - - while (STACK_NOT_EMPTY) - { - char *left_ptr; - char *right_ptr; - - char *pivot = pivot_buffer; - - /* Select median value from among LO, MID, and HI. Rearrange - LO and HI so the three values are sorted. This lowers the - probability of picking a pathological pivot value and - skips a comparison for both the LEFT_PTR and RIGHT_PTR. */ - - char *mid = lo + size * ((hi - lo) / size >> 1); - - if ((*cmp) ((void *) mid, (void *) lo) < 0) - SWAP (mid, lo, size); - if ((*cmp) ((void *) hi, (void *) mid) < 0) - SWAP (mid, hi, size); - else - goto jump_over; - if ((*cmp) ((void *) mid, (void *) lo) < 0) - SWAP (mid, lo, size); - jump_over:; - memcpy (pivot, mid, size); - pivot = pivot_buffer; - - left_ptr = lo + size; - right_ptr = hi - size; - - /* Here's the famous ``collapse the walls'' section of quicksort. - Gotta like those tight inner loops! They are the main reason - that this algorithm runs much faster than others. */ - do - { - while ((*cmp) ((void *) left_ptr, (void *) pivot) < 0) - left_ptr += size; - - while ((*cmp) ((void *) pivot, (void *) right_ptr) < 0) - right_ptr -= size; - - if (left_ptr < right_ptr) - { - SWAP (left_ptr, right_ptr, size); - left_ptr += size; - right_ptr -= size; - } - else if (left_ptr == right_ptr) - { - left_ptr += size; - right_ptr -= size; - break; - } - } - while (left_ptr <= right_ptr); - - /* Set up pointers for next iteration. First determine whether - left and right partitions are below the threshold size. If so, - ignore one or both. Otherwise, push the larger partition's - bounds on the stack and continue sorting the smaller one. */ - - if ((size_t) (right_ptr - lo) <= max_thresh) - { - if ((size_t) (hi - left_ptr) <= max_thresh) - /* Ignore both small partitions. */ - POP (lo, hi); - else - /* Ignore small left partition. */ - lo = left_ptr; - } - else if ((size_t) (hi - left_ptr) <= max_thresh) - /* Ignore small right partition. */ - hi = right_ptr; - else if ((right_ptr - lo) > (hi - left_ptr)) - { - /* Push larger left partition indices. */ - PUSH (lo, right_ptr); - lo = left_ptr; - } - else - { - /* Push larger right partition indices. */ - PUSH (left_ptr, hi); - hi = right_ptr; - } - } - } - - /* Once the BASE_PTR array is partially sorted by quicksort the rest - is completely sorted using insertion sort, since this is efficient - for partitions below MAX_THRESH size. BASE_PTR points to the beginning - of the array to sort, and END_PTR points at the very last element in - the array (*not* one beyond it!). */ - -#define min(x, y) ((x) < (y) ? (x) : (y)) - - { - char *const end_ptr = &base_ptr[size * (total_elems - 1)]; - char *tmp_ptr = base_ptr; - char *thresh = min (end_ptr, base_ptr + max_thresh); - register char *run_ptr; - - /* Find smallest element in first threshold and place it at the - array's beginning. This is the smallest array element, - and the operation speeds up insertion sort's inner loop. */ - - for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) - if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr) < 0) - tmp_ptr = run_ptr; - - if (tmp_ptr != base_ptr) - SWAP (tmp_ptr, base_ptr, size); - - /* Insertion sort, running from left-hand-side up to right-hand-side. */ - - run_ptr = base_ptr + size; - while ((run_ptr += size) <= end_ptr) - { - tmp_ptr = run_ptr - size; - while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr) < 0) - tmp_ptr -= size; - - tmp_ptr += size; - if (tmp_ptr != run_ptr) - { - char *trav; - - trav = run_ptr + size; - while (--trav >= run_ptr) - { - char c = *trav; - char *hi, *lo; - - for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) - *hi = *lo; - *hi = c; - } - } - } - } -} -- 2.30.2