diff options
Diffstat (limited to 'stdlib')
| -rw-r--r-- | stdlib/msort.c | 60 |
1 files changed, 49 insertions, 11 deletions
diff --git a/stdlib/msort.c b/stdlib/msort.c index c03f6f2982..d174edd3b7 100644 --- a/stdlib/msort.c +++ b/stdlib/msort.c @@ -1,6 +1,6 @@ /* An alternative to qsort, with an identical interface. This file is part of the GNU C Library. - Copyright (C) 1992, 1995, 1996, 1997, 1999 Free Software Foundation, Inc. + Copyright (C) 1992, 1995-1997, 1999, 2000 Free Software Foundation, Inc. Written by Mike Haertel, September 1988. The GNU C Library is free software; you can redistribute it and/or @@ -21,6 +21,7 @@ #include <alloca.h> #include <stdlib.h> #include <string.h> +#include <unistd.h> #include <memcopy.h> #include <errno.h> @@ -94,20 +95,57 @@ qsort (void *b, size_t n, size_t s, __compar_fn_t cmp) msort_with_tmp (b, n, s, cmp, __alloca (size)); else { - /* It's somewhat large, so malloc it. */ - int save = errno; - char *tmp = malloc (size); - if (tmp == NULL) + /* We should avoid allocating too much memory since this might + have to be backed up by swap space. */ + static long int phys_pages; + static int pagesize; + + if (phys_pages == 0) { - /* Couldn't get space, so use the slower algorithm - that doesn't need a temporary array. */ - _quicksort (b, n, s, cmp); + phys_pages = __sysconf (_SC_PHYS_PAGES); + + if (phys_pages == -1) + /* Error while determining the memory size. So let's + assume there is enough memory. Otherwise the + implementer should provide a complete implementation of + the `sysconf' function. */ + phys_pages = (long int) (~0ul >> 1); + + /* The following determines that we will never use more than + a quarter of the physical memory. */ + phys_pages /= 4; + + pagesize = __sysconf (_SC_PAGESIZE); } + + /* Just a comment here. We cannot compute + phys_pages * pagesize + and compare the needed amount of memory against this value. + The problem is that some systems might have more physical + memory then can be represented with a `size_t' value (when + measured in bytes. */ + + /* If the memory requirements are too high don't allocate memory. */ + if (size / pagesize > phys_pages) + _quicksort (b, n, s, cmp); else { - msort_with_tmp (b, n, s, cmp, tmp); - free (tmp); + /* It's somewhat large, so malloc it. */ + int save = errno; + char *tmp = malloc (size); + if (tmp == NULL) + { + /* Couldn't get space, so use the slower algorithm + that doesn't need a temporary array. */ + __set_errno (save); + _quicksort (b, n, s, cmp); + } + else + { + __set_errno (save); + msort_with_tmp (b, n, s, cmp, tmp); + free (tmp); + } } - __set_errno (save); } } |