← Back to branch summary

~ubuntu-branches/ubuntu/precise/kompozer/precise

« back to all changes in this revision

Viewing changes to mozilla/xpcom/ds/nsQuickSort.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Anthony Yarusso
  • Date: 2007-08-27 01:11:03 UTC
  • Revision ID: james.westby@ubuntu.com-20070827011103-2jgf4s6532gqu2ka
Tags: upstream-0.7.10
Import upstream version 0.7.10

Show diffs side-by-side

added added

removed removed

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