src/hb-dsalgs.hh

   1 /*
   2  * Copyright © 2017  Google, Inc.
   3  *
   4  *  This is part of HarfBuzz, a text shaping library.
   5  *
   6  * Permission is hereby granted, without written agreement and without
   7  * license or royalty fees, to use, copy, modify, and distribute this
   8  * software and its documentation for any purpose, provided that the
   9  * above copyright notice and the following two paragraphs appear in
  10  * all copies of this software.
  11  *
  12  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
  13  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
  14  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
  15  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
  16  * DAMAGE.
  17  *
  18  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
  19  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  20  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  21  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
  22  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  23  *
  24  * Google Author(s): Behdad Esfahbod
  25  */
  26
  27 #ifndef HB_DSALGS_HH
  28 #define HB_DSALGS_HH
  29
  30 #include "hb-private.hh"
  31
  32
  33 static inline void *
  34 hb_bsearch_r (const void *key, const void *base,
  35               size_t nmemb, size_t size,
  36               int (*compar)(const void *_key, const void *_item, void *_arg),
  37               void *arg)
  38 {
  39   int min = 0, max = (int) nmemb - 1;
  40   while (min <= max)
  41   {
  42     int mid = (min + max) / 2;
  43     const void *p = (const void *) (((const char *) base) + (mid * size));
  44     int c = compar (key, p, arg);
  45     if (c < 0)
  46       max = mid - 1;
  47     else if (c > 0)
  48       min = mid + 1;
  49     else
  50       return (void *) p;
  51   }
  52   return nullptr;
  53 }
  54
  55
  56
  57 /* From https://github.com/noporpoise/sort_r */
  58
  59 /* Isaac Turner 29 April 2014 Public Domain */
  60
  61 /*
  62
  63 hb_sort_r function to be exported.
  64
  65 Parameters:
  66   base is the array to be sorted
  67   nel is the number of elements in the array
  68   width is the size in bytes of each element of the array
  69   compar is the comparison function
  70   arg is a pointer to be passed to the comparison function
  71
  72 void hb_sort_r(void *base, size_t nel, size_t width,
  73                int (*compar)(const void *_a, const void *_b, void *_arg),
  74                void *arg);
  75 */
  76
  77
  78 /* swap a, b iff a>b */
  79 /* __restrict is same as restrict but better support on old machines */
  80 static int sort_r_cmpswap(char *__restrict a, char *__restrict b, size_t w,
  81                           int (*compar)(const void *_a, const void *_b,
  82                                         void *_arg),
  83                           void *arg)
  84 {
  85   char tmp, *end = a+w;
  86   if(compar(a, b, arg) > 0) {
  87     for(; a < end; a++, b++) { tmp = *a; *a = *b; *b = tmp; }
  88     return 1;
  89   }
  90   return 0;
  91 }
  92
  93 /* Note: quicksort is not stable, equivalent values may be swapped */
  94 static inline void sort_r_simple(void *base, size_t nel, size_t w,
  95                                  int (*compar)(const void *_a, const void *_b,
  96                                                void *_arg),
  97                                  void *arg)
  98 {
  99   char *b = (char *)base, *end = b + nel*w;
 100   if(nel < 7) {
 101     /* Insertion sort for arbitrarily small inputs */
 102     char *pi, *pj;
 103     for(pi = b+w; pi < end; pi += w) {
 104       for(pj = pi; pj > b && sort_r_cmpswap(pj-w,pj,w,compar,arg); pj -= w) {}
 105     }
 106   }
 107   else
 108   {
 109     /* nel > 6; Quicksort */
 110
 111     /* Use median of first, middle and last items as pivot */
 112     char *x, *y, *xend, ch;
 113     char *pl, *pr;
 114     char *last = b+w*(nel-1), *tmp;
 115     char *l[3];
 116     l[0] = b;
 117     l[1] = b+w*(nel/2);
 118     l[2] = last;
 119
 120     if(compar(l[0],l[1],arg) > 0) { tmp=l[0]; l[0]=l[1]; l[1]=tmp; }
 121     if(compar(l[1],l[2],arg) > 0) {
 122       tmp=l[1]; l[1]=l[2]; l[2]=tmp; /* swap(l[1],l[2]) */
 123       if(compar(l[0],l[1],arg) > 0) { tmp=l[0]; l[0]=l[1]; l[1]=tmp; }
 124     }
 125
 126     /* swap l[id], l[2] to put pivot as last element */
 127     for(x = l[1], y = last, xend = x+w; x<xend; x++, y++) {
 128       ch = *x; *x = *y; *y = ch;
 129     }
 130
 131     pl = b;
 132     pr = last;
 133
 134     while(pl < pr) {
 135       for(; pl < pr; pl += w) {
 136         if(sort_r_cmpswap(pl, pr, w, compar, arg)) {
 137           pr -= w; /* pivot now at pl */
 138           break;
 139         }
 140       }
 141       for(; pl < pr; pr -= w) {
 142         if(sort_r_cmpswap(pl, pr, w, compar, arg)) {
 143           pl += w; /* pivot now at pr */
 144           break;
 145         }
 146       }
 147     }
 148
 149     sort_r_simple(b, (pl-b)/w, w, compar, arg);
 150     sort_r_simple(pl+w, (end-(pl+w))/w, w, compar, arg);
 151   }
 152 }
 153
 154 static inline void hb_sort_r(void *base, size_t nel, size_t width,
 155                              int (*compar)(const void *_a, const void *_b, void *_arg),
 156                              void *arg)
 157 {
 158     sort_r_simple(base, nel, width, compar, arg);
 159 }
 160
 161 #endif /* HB_DSALGS_HH */