aboutsummaryrefslogtreecommitdiff
path: root/stdlib
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>2007-11-13 17:21:43 +0000
committerUlrich Drepper <drepper@redhat.com>2007-11-13 17:21:43 +0000
commite458144c99ddc00769ffa6bd367c21d37e879d83 (patch)
tree55e549e9ab2672a3ebf613ca698f622c97aece8c /stdlib
parentbd63f380d8760a643dfa17d1907692f39e63195e (diff)
downloadglibc-e458144c99ddc00769ffa6bd367c21d37e879d83.zip
glibc-e458144c99ddc00769ffa6bd367c21d37e879d83.tar.gz
glibc-e458144c99ddc00769ffa6bd367c21d37e879d83.tar.bz2
* stdlib/stdlib.h: Define __compar_d_fn_t. Declare qsort_r.
* include/stdlib.h: Add hidden_proto for qsort_t and adjust protoype for _quicksort. * stdlib/msort.c (qsort): Now a wrapper around qsort_r. (qsort_r): Renamed from qsort. Take additional parameter and pass it on as third parameter to compare function and _quicksort. * stdlib/qsort.c (_quicksort): Take additional parameter and pass on to the compare function. * stdlib/Versions [libc] (GLIBC_2.8): Add qsort_r. * Versions.def: Add GLIBC_2.8 for libc.
Diffstat (limited to 'stdlib')
-rw-r--r--stdlib/Versions3
-rw-r--r--stdlib/msort.c36
-rw-r--r--stdlib/qsort.c16
-rw-r--r--stdlib/stdlib.h8
4 files changed, 43 insertions, 20 deletions
diff --git a/stdlib/Versions b/stdlib/Versions
index 9cc3b6d..f4a90c9 100644
--- a/stdlib/Versions
+++ b/stdlib/Versions
@@ -94,6 +94,9 @@ libc {
# Silent change in SUS.
realpath;
}
+ GLIBC_2.8 {
+ qsort_r;
+ }
GLIBC_PRIVATE {
# functions which have an additional interface since they are
# are cancelable.
diff --git a/stdlib/msort.c b/stdlib/msort.c
index 3961e9e..35cd4d0 100644
--- a/stdlib/msort.c
+++ b/stdlib/msort.c
@@ -30,7 +30,8 @@ struct msort_param
{
size_t s;
size_t var;
- __compar_fn_t cmp;
+ __compar_d_fn_t cmp;
+ void *arg;
char *t;
};
static void msort_with_tmp (const struct msort_param *p, void *b, size_t n);
@@ -54,13 +55,14 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
char *tmp = p->t;
const size_t s = p->s;
- __compar_fn_t cmp = p->cmp;
+ __compar_d_fn_t cmp = p->cmp;
+ void *arg = p->arg;
switch (p->var)
{
case 0:
while (n1 > 0 && n2 > 0)
{
- if ((*cmp) (b1, b2) <= 0)
+ if ((*cmp) (b1, b2, arg) <= 0)
{
*(uint32_t *) tmp = *(uint32_t *) b1;
b1 += sizeof (uint32_t);
@@ -78,7 +80,7 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
case 1:
while (n1 > 0 && n2 > 0)
{
- if ((*cmp) (b1, b2) <= 0)
+ if ((*cmp) (b1, b2, arg) <= 0)
{
*(uint64_t *) tmp = *(uint64_t *) b1;
b1 += sizeof (uint64_t);
@@ -100,7 +102,7 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
unsigned long *bl;
tmp += s;
- if ((*cmp) (b1, b2) <= 0)
+ if ((*cmp) (b1, b2, arg) <= 0)
{
bl = (unsigned long *) b1;
b1 += s;
@@ -119,7 +121,7 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
case 3:
while (n1 > 0 && n2 > 0)
{
- if ((*cmp) (*(const void **) b1, *(const void **) b2) <= 0)
+ if ((*cmp) (*(const void **) b1, *(const void **) b2, arg) <= 0)
{
*(void **) tmp = *(void **) b1;
b1 += sizeof (void *);
@@ -137,7 +139,7 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
default:
while (n1 > 0 && n2 > 0)
{
- if ((*cmp) (b1, b2) <= 0)
+ if ((*cmp) (b1, b2, arg) <= 0)
{
tmp = (char *) __mempcpy (tmp, b1, s);
b1 += s;
@@ -158,8 +160,9 @@ msort_with_tmp (const struct msort_param *p, void *b, size_t n)
memcpy (b, p->t, (n - n2) * s);
}
+
void
-qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
+qsort_r (void *b, size_t n, size_t s, __compar_d_fn_t cmp, void *arg)
{
size_t size = n * s;
char *tmp = NULL;
@@ -207,7 +210,7 @@ qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
/* If the memory requirements are too high don't allocate memory. */
if (size / pagesize > (size_t) phys_pages)
{
- _quicksort (b, n, s, cmp);
+ _quicksort (b, n, s, cmp, arg);
return;
}
@@ -219,15 +222,16 @@ qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
{
/* Couldn't get space, so use the slower algorithm
that doesn't need a temporary array. */
- _quicksort (b, n, s, cmp);
+ _quicksort (b, n, s, cmp, arg);
return;
}
p.t = tmp;
}
p.s = s;
- p.cmp = cmp;
p.var = 4;
+ p.cmp = cmp;
+ p.arg = arg;
if (s > 32)
{
@@ -269,7 +273,7 @@ qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
while (kp != ip);
tp[j] = jp;
- memcpy (jp, tmp_storage, s);
+ memcpy (jp, tmp_storage, s);
}
}
else
@@ -291,4 +295,12 @@ qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
}
free (tmp);
}
+libc_hidden_def (qsort_r)
+
+
+void
+qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
+{
+ return qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
+}
libc_hidden_def (qsort)
diff --git a/stdlib/qsort.c b/stdlib/qsort.c
index 6a33c52..b19e86e 100644
--- a/stdlib/qsort.c
+++ b/stdlib/qsort.c
@@ -88,7 +88,7 @@ typedef struct
void
_quicksort (void *const pbase, size_t total_elems, size_t size,
- __compar_fn_t cmp)
+ __compar_d_fn_t cmp, void *arg)
{
register char *base_ptr = (char *) pbase;
@@ -120,13 +120,13 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
char *mid = lo + size * ((hi - lo) / size >> 1);
- if ((*cmp) ((void *) mid, (void *) lo) < 0)
+ if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
SWAP (mid, lo, size);
- if ((*cmp) ((void *) hi, (void *) mid) < 0)
+ if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
SWAP (mid, hi, size);
else
goto jump_over;
- if ((*cmp) ((void *) mid, (void *) lo) < 0)
+ if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
SWAP (mid, lo, size);
jump_over:;
@@ -138,10 +138,10 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
that this algorithm runs much faster than others. */
do
{
- while ((*cmp) ((void *) left_ptr, (void *) mid) < 0)
+ while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
left_ptr += size;
- while ((*cmp) ((void *) mid, (void *) right_ptr) < 0)
+ while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
right_ptr -= size;
if (left_ptr < right_ptr)
@@ -214,7 +214,7 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
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)
+ if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
tmp_ptr = run_ptr;
if (tmp_ptr != base_ptr)
@@ -226,7 +226,7 @@ _quicksort (void *const pbase, size_t total_elems, size_t size,
while ((run_ptr += size) <= end_ptr)
{
tmp_ptr = run_ptr - size;
- while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr) < 0)
+ while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
tmp_ptr -= size;
tmp_ptr += size;
diff --git a/stdlib/stdlib.h b/stdlib/stdlib.h
index 3c2ea72..732e7d6 100644
--- a/stdlib/stdlib.h
+++ b/stdlib/stdlib.h
@@ -673,6 +673,9 @@ typedef int (*__compar_fn_t) (__const void *, __const void *);
typedef __compar_fn_t comparison_fn_t;
# endif
#endif
+#ifdef __USE_GNU
+typedef int (*__compar_d_fn_t) (__const void *, __const void *, void *);
+#endif
__BEGIN_NAMESPACE_STD
/* Do a binary search for KEY in BASE, which consists of NMEMB elements
@@ -685,6 +688,11 @@ extern void *bsearch (__const void *__key, __const void *__base,
using COMPAR to perform the comparisons. */
extern void qsort (void *__base, size_t __nmemb, size_t __size,
__compar_fn_t __compar) __nonnull ((1, 4));
+#ifdef __USE_GNU
+extern void qsort_r (void *__base, size_t __nmemb, size_t __size,
+ __compar_d_fn_t __compar, void *__arg)
+ __nonnull ((1, 4));
+#endif
/* Return the absolute value of X. */