← Back to branch summary

~louis/ubuntu/trusty/clamav/lp799623_fix_logrotate

« back to all changes in this revision

Viewing changes to libclamav/qsort.c

  • Committer: Bazaar Package Importer
  • Author(s): Scott Kitterman
  • Date: 2010-03-12 11:30:04 UTC
  • mfrom: (0.41.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100312113004-b0fop4bkycszdd0z
Tags: 0.96~rc1+dfsg-0ubuntu1
https://launchpad.net/bugs/537636
* New upstream RC - FFE (LP: #537636):
  - Add OfficialDatabaseOnly option to clamav-base.postinst.in
  - Add LocalSocketGroup option to clamav-base.postinst.in
  - Add LocalSocketMode option to clamav-base.postinst.in
  - Add CrossFilesystems option to clamav-base.postinst.in
  - Add ClamukoScannerCount option to clamav-base.postinst.in
  - Add BytecodeSecurity opiton to clamav-base.postinst.in
  - Add DetectionStatsHostID option to clamav-freshclam.postinst.in
  - Add Bytecode option to clamav-freshclam.postinst.in
  - Add MilterSocketGroup option to clamav-milter.postinst.in
  - Add MilterSocketMode option to clamav-milter.postinst.in
  - Add ReportHostname option to clamav-milter.postinst.in
  - Bump libclamav SO version to 6.1.0 in libclamav6.install
  - Drop clamdmon from clamav.examples (no longer shipped by upstream)
  - Drop libclamav.a from libclamav-dev.install (not built by upstream)
  - Update SO version for lintian override for libclamav6
  - Add new Bytecode Testing Tool, usr/bin/clambc, to clamav.install
  - Add build-depends on python and python-setuptools for new test suite
  - Update debian/copyright for the embedded copy of llvm (using the system
    llvm is not currently feasible)

Show diffs side-by-side

added added

removed removed

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