Back to home page

Redis cross reference

 
 

    


0001 /* The following is the NetBSD libc qsort implementation modified in order to
0002  * support partial sorting of ranges for Redis.
0003  *
0004  * Copyright(C) 2009-2012 Salvatore Sanfilippo. All rights reserved.
0005  *
0006  * The original copyright notice follows. */
0007 
0008 
0009 /*  $NetBSD: qsort.c,v 1.19 2009/01/30 23:38:44 lukem Exp $ */
0010 
0011 /*-
0012  * Copyright (c) 1992, 1993
0013  *  The Regents of the University of California.  All rights reserved.
0014  *
0015  * Redistribution and use in source and binary forms, with or without
0016  * modification, are permitted provided that the following conditions
0017  * are met:
0018  * 1. Redistributions of source code must retain the above copyright
0019  *    notice, this list of conditions and the following disclaimer.
0020  * 2. Redistributions in binary form must reproduce the above copyright
0021  *    notice, this list of conditions and the following disclaimer in the
0022  *    documentation and/or other materials provided with the distribution.
0023  * 3. Neither the name of the University nor the names of its contributors
0024  *    may be used to endorse or promote products derived from this software
0025  *    without specific prior written permission.
0026  *
0027  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
0028  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
0029  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
0030  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
0031  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
0032  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
0033  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
0034  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
0035  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
0036  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
0037  * SUCH DAMAGE.
0038  */
0039 
0040 #include <sys/types.h>
0041 
0042 #include <assert.h>
0043 #include <errno.h>
0044 #include <stdlib.h>
0045 
0046 static inline char  *med3 (char *, char *, char *,
0047     int (*)(const void *, const void *));
0048 static inline void   swapfunc (char *, char *, size_t, int);
0049 
0050 #define min(a, b)   (a) < (b) ? a : b
0051 
0052 /*
0053  * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
0054  */
0055 #define swapcode(TYPE, parmi, parmj, n) {       \
0056     size_t i = (n) / sizeof (TYPE);         \
0057     TYPE *pi = (TYPE *)(void *)(parmi);         \
0058     TYPE *pj = (TYPE *)(void *)(parmj);         \
0059     do {                        \
0060         TYPE    t = *pi;            \
0061         *pi++ = *pj;                \
0062         *pj++ = t;              \
0063         } while (--i > 0);              \
0064 }
0065 
0066 #define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
0067     es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
0068 
0069 static inline void
0070 swapfunc(char *a, char *b, size_t n, int swaptype)
0071 {
0072 
0073     if (swaptype <= 1) 
0074         swapcode(long, a, b, n)
0075     else
0076         swapcode(char, a, b, n)
0077 }
0078 
0079 #define swap(a, b)                      \
0080     if (swaptype == 0) {                    \
0081         long t = *(long *)(void *)(a);          \
0082         *(long *)(void *)(a) = *(long *)(void *)(b);    \
0083         *(long *)(void *)(b) = t;           \
0084     } else                          \
0085         swapfunc(a, b, es, swaptype)
0086 
0087 #define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n), swaptype)
0088 
0089 static inline char *
0090 med3(char *a, char *b, char *c,
0091     int (*cmp) (const void *, const void *))
0092 {
0093 
0094     return cmp(a, b) < 0 ?
0095            (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ))
0096               :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ));
0097 }
0098 
0099 static void
0100 _pqsort(void *a, size_t n, size_t es,
0101     int (*cmp) (const void *, const void *), void *lrange, void *rrange)
0102 {
0103     char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
0104     size_t d, r;
0105     int swaptype, swap_cnt, cmp_result;
0106 
0107 loop:   SWAPINIT(a, es);
0108     swap_cnt = 0;
0109     if (n < 7) {
0110         for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
0111             for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
0112                  pl -= es)
0113                 swap(pl, pl - es);
0114         return;
0115     }
0116     pm = (char *) a + (n / 2) * es;
0117     if (n > 7) {
0118         pl = (char *) a;
0119         pn = (char *) a + (n - 1) * es;
0120         if (n > 40) {
0121             d = (n / 8) * es;
0122             pl = med3(pl, pl + d, pl + 2 * d, cmp);
0123             pm = med3(pm - d, pm, pm + d, cmp);
0124             pn = med3(pn - 2 * d, pn - d, pn, cmp);
0125         }
0126         pm = med3(pl, pm, pn, cmp);
0127     }
0128     swap(a, pm);
0129     pa = pb = (char *) a + es;
0130 
0131     pc = pd = (char *) a + (n - 1) * es;
0132     for (;;) {
0133         while (pb <= pc && (cmp_result = cmp(pb, a)) <= 0) {
0134             if (cmp_result == 0) {
0135                 swap_cnt = 1;
0136                 swap(pa, pb);
0137                 pa += es;
0138             }
0139             pb += es;
0140         }
0141         while (pb <= pc && (cmp_result = cmp(pc, a)) >= 0) {
0142             if (cmp_result == 0) {
0143                 swap_cnt = 1;
0144                 swap(pc, pd);
0145                 pd -= es;
0146             }
0147             pc -= es;
0148         }
0149         if (pb > pc)
0150             break;
0151         swap(pb, pc);
0152         swap_cnt = 1;
0153         pb += es;
0154         pc -= es;
0155     }
0156     if (swap_cnt == 0) {  /* Switch to insertion sort */
0157         for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
0158             for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; 
0159                  pl -= es)
0160                 swap(pl, pl - es);
0161         return;
0162     }
0163 
0164     pn = (char *) a + n * es;
0165     r = min(pa - (char *) a, pb - pa);
0166     vecswap(a, pb - r, r);
0167     r = min((size_t)(pd - pc), pn - pd - es);
0168     vecswap(pb, pn - r, r);
0169     if ((r = pb - pa) > es) {
0170                 void *_l = a, *_r = ((unsigned char*)a)+r-1;
0171                 if (!((lrange < _l && rrange < _l) ||
0172                     (lrange > _r && rrange > _r)))
0173             _pqsort(a, r / es, es, cmp, lrange, rrange);
0174         }
0175     if ((r = pd - pc) > es) { 
0176                 void *_l, *_r;
0177                 
0178         /* Iterate rather than recurse to save stack space */
0179         a = pn - r;
0180         n = r / es;
0181 
0182                 _l = a;
0183                 _r = ((unsigned char*)a)+r-1;
0184                 if (!((lrange < _l && rrange < _l) ||
0185                     (lrange > _r && rrange > _r)))
0186             goto loop;
0187     }
0188 /*      qsort(pn - r, r / es, es, cmp);*/
0189 }
0190 
0191 void
0192 pqsort(void *a, size_t n, size_t es,
0193     int (*cmp) (const void *, const void *), size_t lrange, size_t rrange)
0194 {
0195     _pqsort(a,n,es,cmp,((unsigned char*)a)+(lrange*es),
0196                        ((unsigned char*)a)+((rrange+1)*es)-1);
0197 }