aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>2000-02-28 08:14:33 +0000
committerUlrich Drepper <drepper@redhat.com>2000-02-28 08:14:33 +0000
commit8358825c703091ef71f4e8a49d0186343c67368c (patch)
treecff4387b561bb0c0a1fac089a394d18eced17793
parente5aa91c34ac93ad91b910b55fd8781c267a81780 (diff)
downloadglibc-8358825c703091ef71f4e8a49d0186343c67368c.zip
glibc-8358825c703091ef71f4e8a49d0186343c67368c.tar.gz
glibc-8358825c703091ef71f4e8a49d0186343c67368c.tar.bz2
Update.
2000-02-28 Ulrich Drepper <drepper@redhat.com> * stdlib/msort.c (qsort): Limit the amount of memory spend on a temporary array for the mergesort.
-rw-r--r--ChangeLog5
-rw-r--r--stdlib/msort.c60
2 files changed, 54 insertions, 11 deletions
diff --git a/ChangeLog b/ChangeLog
index aa6e20a..3354baf 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2000-02-28 Ulrich Drepper <drepper@redhat.com>
+
+ * stdlib/msort.c (qsort): Limit the amount of memory spend on a
+ temporary array for the mergesort.
+
2000-02-28 Andreas Jaeger <aj@suse.de>
* stdlib/canonicalize.c: Include <stddef.h> for ptrdiff_t.
diff --git a/stdlib/msort.c b/stdlib/msort.c
index c03f6f2..d174edd 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);
}
}