← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/virtualbox-ose/gutsy

« back to all changes in this revision

Viewing changes to src/libs/xpcom18a4/xpcom/ds/nsQuickSort.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Steve Kowalik
  • Date: 2007-09-08 16:44:58 UTC
  • Revision ID: james.westby@ubuntu.com-20070908164458-wao29470vqtr8ksy
Tags: upstream-1.5.0-dfsg2
Import upstream version 1.5.0-dfsg2

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libs/xpcom18a4/xpcom/ds/nsQuickSort.cpp
 
1
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
 
2
 
 
3
/*-
 
4
 * Copyright (c) 1992, 1993
 
5
 *      The Regents of the University of California.  All rights reserved.
 
6
 *
 
7
 * Redistribution and use in source and binary forms, with or without
 
8
 * modification, are permitted provided that the following conditions
 
9
 * are met:
 
10
 * 1. Redistributions of source code must retain the above copyright
 
11
 *    notice, this list of conditions and the following disclaimer.
 
12
 * 2. Redistributions in binary form must reproduce the above copyright
 
13
 *    notice, this list of conditions and the following disclaimer in the
 
14
 *    documentation and/or other materials provided with the distribution.
 
15
 * 3. Neither the name of the University nor the names of its contributors
 
16
 *    may be used to endorse or promote products derived from this software
 
17
 *    without specific prior written permission.
 
18
 *
 
19
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 
20
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
21
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
22
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 
23
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 
24
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 
25
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 
26
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 
27
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 
28
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 
29
 * SUCH DAMAGE.
 
30
 */
 
31
 
 
32
/* We need this because Solaris' version of qsort is broken and
 
33
 * causes array bounds reads.
 
34
 */
 
35
 
 
36
#include <stdlib.h>
 
37
#include "prtypes.h"
 
38
#include "nsQuickSort.h"
 
39
 
 
40
PR_BEGIN_EXTERN_C
 
41
 
 
42
#if !defined(DEBUG) && (defined(__cplusplus) || defined(__gcc))
 
43
# ifndef INLINE
 
44
#  define INLINE inline
 
45
# endif
 
46
#else
 
47
# define INLINE
 
48
#endif
 
49
 
 
50
typedef int              cmp_t(const void *, const void *, void *);
 
51
static INLINE char      *med3(char *, char *, char *, cmp_t *, void *);
 
52
static INLINE void      swapfunc(char *, char *, int, int);
 
53
 
 
54
/*
 
55
 * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
 
56
 */
 
57
#define swapcode(TYPE, parmi, parmj, n) {               \
 
58
        long i = (n) / sizeof (TYPE);                   \
 
59
        register TYPE *pi = (TYPE *) (parmi);           \
 
60
        register TYPE *pj = (TYPE *) (parmj);           \
 
61
        do {                                            \
 
62
                register TYPE   t = *pi;                \
 
63
                *pi++ = *pj;                            \
 
64
                *pj++ = t;                              \
 
65
        } while (--i > 0);                              \
 
66
}
 
67
 
 
68
#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
 
69
        es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
 
70
 
 
71
static INLINE void
 
72
swapfunc(char *a, char *b, int n, int swaptype)
 
73
{
 
74
        if(swaptype <= 1)
 
75
                swapcode(long, a, b, n)
 
76
        else
 
77
                swapcode(char, a, b, n)
 
78
}
 
79
 
 
80
#define swap(a, b)                                      \
 
81
        if (swaptype == 0) {                            \
 
82
                long t = *(long *)(a);                  \
 
83
                *(long *)(a) = *(long *)(b);            \
 
84
                *(long *)(b) = t;                       \
 
85
        } else                                          \
 
86
                swapfunc((char *)a, (char*)b, (int)es, swaptype)
 
87
 
 
88
#define vecswap(a, b, n)        if ((n) > 0) swapfunc((char *)a, (char *)b, (int)n, swaptype)
 
89
 
 
90
static INLINE char *
 
91
med3(char *a, char *b, char *c, cmp_t* cmp, void *data)
 
92
{
 
93
        return cmp(a, b, data) < 0 ?
 
94
               (cmp(b, c, data) < 0 ? b : (cmp(a, c, data) < 0 ? c : a ))
 
95
              :(cmp(b, c, data) > 0 ? b : (cmp(a, c, data) < 0 ? a : c ));
 
96
}
 
97
 
 
98
void NS_QuickSort (
 
99
        void *a,
 
100
        unsigned int n,
 
101
    unsigned int es,
 
102
        cmp_t *cmp,
 
103
        void *data
 
104
    )
 
105
{
 
106
        char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
 
107
        int d, r, swaptype, swap_cnt;
 
108
 
 
109
loop:   SWAPINIT(a, es);
 
110
        swap_cnt = 0;
 
111
        if (n < 7) {
 
112
                for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
 
113
                        for (pl = pm; pl > (char *)a && cmp(pl - es, pl, data) > 0;
 
114
                             pl -= es)
 
115
                                swap(pl, pl - es);
 
116
                return;
 
117
        }
 
118
        pm = (char *)a + (n / 2) * es;
 
119
        if (n > 7) {
 
120
                pl = (char *)a;
 
121
                pn = (char *)a + (n - 1) * es;
 
122
                if (n > 40) {
 
123
                        d = (n / 8) * es;
 
124
                        pl = med3(pl, pl + d, pl + 2 * d, cmp, data);
 
125
                        pm = med3(pm - d, pm, pm + d, cmp, data);
 
126
                        pn = med3(pn - 2 * d, pn - d, pn, cmp, data);
 
127
                }
 
128
                pm = med3(pl, pm, pn, cmp, data);
 
129
        }
 
130
        swap(a, pm);
 
131
        pa = pb = (char *)a + es;
 
132
 
 
133
        pc = pd = (char *)a + (n - 1) * es;
 
134
        for (;;) {
 
135
                while (pb <= pc && (r = cmp(pb, a, data)) <= 0) {
 
136
                        if (r == 0) {
 
137
                                swap_cnt = 1;
 
138
                                swap(pa, pb);
 
139
                                pa += es;
 
140
                        }
 
141
                        pb += es;
 
142
                }
 
143
                while (pb <= pc && (r = cmp(pc, a, data)) >= 0) {
 
144
                        if (r == 0) {
 
145
                                swap_cnt = 1;
 
146
                                swap(pc, pd);
 
147
                                pd -= es;
 
148
                        }
 
149
                        pc -= es;
 
150
                }
 
151
                if (pb > pc)
 
152
                        break;
 
153
                swap(pb, pc);
 
154
                swap_cnt = 1;
 
155
                pb += es;
 
156
                pc -= es;
 
157
        }
 
158
        if (swap_cnt == 0) {  /* Switch to insertion sort */
 
159
                for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
 
160
                        for (pl = pm; pl > (char *)a && cmp(pl - es, pl, data) > 0;
 
161
                             pl -= es)
 
162
                                swap(pl, pl - es);
 
163
                return;
 
164
        }
 
165
 
 
166
        pn = (char *)a + n * es;
 
167
        r = PR_MIN(pa - (char *)a, pb - pa);
 
168
        vecswap(a, pb - r, r);
 
169
        r = PR_MIN(pd - pc, (int)(pn - pd - es));
 
170
        vecswap(pb, pn - r, r);
 
171
        if ((r = pb - pa) > (int)es)
 
172
        NS_QuickSort(a, r / es, es, cmp, data);
 
173
        if ((r = pd - pc) > (int)es) {
 
174
                /* Iterate rather than recurse to save stack space */
 
175
                a = pn - r;
 
176
                n = r / es;
 
177
                goto loop;
 
178
        }
 
179
/*              NS_QuickSort(pn - r, r / es, es, cmp, data);*/
 
180
}
 
181
 
 
182
PR_END_EXTERN_C