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 | #if defined(__ghs) |
33 | // GHS compiler doesn't support the __restrict keyword |
34 | #define __restrict |
35 | #endif |
36 | |
37 | |
38 | |
39 | static inline void * |
40 | hb_bsearch_r (const void *key, const void *base, |
41 | size_t nmemb, size_t size, |
42 | int (*compar)(const void *_key, const void *_item, void *_arg), |
43 | void *arg) |
44 | { |
45 | int min = 0, max = (int) nmemb - 1; |
46 | while (min <= max) |
47 | { |
48 | int mid = (min + max) / 2; |
49 | const void *p = (const void *) (((const char *) base) + (mid * size)); |
50 | int c = compar (key, p, arg); |
51 | if (c < 0) |
52 | max = mid - 1; |
53 | else if (c > 0) |
54 | min = mid + 1; |
55 | else |
56 | return (void *) p; |
57 | } |
58 | return NULL; |
59 | } |
60 | |
61 | |
62 | |
63 | /* From https://github.com/noporpoise/sort_r */ |
64 | |
65 | /* Isaac Turner 29 April 2014 Public Domain */ |
66 | |
67 | /* |
68 | |
69 | hb_sort_r function to be exported. |
70 | |
71 | Parameters: |
72 | base is the array to be sorted |
73 | nel is the number of elements in the array |
74 | width is the size in bytes of each element of the array |
75 | compar is the comparison function |
76 | arg is a pointer to be passed to the comparison function |
77 | |
78 | void hb_sort_r(void *base, size_t nel, size_t width, |
79 | int (*compar)(const void *_a, const void *_b, void *_arg), |
80 | void *arg); |
81 | */ |
82 | |
83 | |
84 | /* swap a, b iff a>b */ |
85 | /* __restrict is same as restrict but better support on old machines */ |
86 | static int sort_r_cmpswap(char *__restrict a, char *__restrict b, size_t w, |
87 | int (*compar)(const void *_a, const void *_b, |
88 | void *_arg), |
89 | void *arg) |
90 | { |
91 | char tmp, *end = a+w; |
92 | if(compar(a, b, arg) > 0) { |
93 | for(; a < end; a++, b++) { tmp = *a; *a = *b; *b = tmp; } |
94 | return 1; |
95 | } |
96 | return 0; |
97 | } |
98 | |
99 | /* Note: quicksort is not stable, equivalent values may be swapped */ |
100 | static inline void sort_r_simple(void *base, size_t nel, size_t w, |
101 | int (*compar)(const void *_a, const void *_b, |
102 | void *_arg), |
103 | void *arg) |
104 | { |
105 | char *b = (char *)base, *end = b + nel*w; |
106 | if(nel < 7) { |
107 | /* Insertion sort for arbitrarily small inputs */ |
108 | char *pi, *pj; |
109 | for(pi = b+w; pi < end; pi += w) { |
110 | for(pj = pi; pj > b && sort_r_cmpswap(a: pj-w,b: pj,w,compar,arg); pj -= w) {} |
111 | } |
112 | } |
113 | else |
114 | { |
115 | /* nel > 6; Quicksort */ |
116 | |
117 | /* Use median of first, middle and last items as pivot */ |
118 | char *x, *y, *xend, ch; |
119 | char *pl, *pr; |
120 | char *last = b+w*(nel-1), *tmp; |
121 | char *l[3]; |
122 | l[0] = b; |
123 | l[1] = b+w*(nel/2); |
124 | l[2] = last; |
125 | |
126 | if(compar(l[0],l[1],arg) > 0) { tmp=l[0]; l[0]=l[1]; l[1]=tmp; } |
127 | if(compar(l[1],l[2],arg) > 0) { |
128 | tmp=l[1]; l[1]=l[2]; l[2]=tmp; /* swap(l[1],l[2]) */ |
129 | if(compar(l[0],l[1],arg) > 0) { tmp=l[0]; l[0]=l[1]; l[1]=tmp; } |
130 | } |
131 | |
132 | /* swap l[id], l[2] to put pivot as last element */ |
133 | for(x = l[1], y = last, xend = x+w; x<xend; x++, y++) { |
134 | ch = *x; *x = *y; *y = ch; |
135 | } |
136 | |
137 | pl = b; |
138 | pr = last; |
139 | |
140 | while(pl < pr) { |
141 | for(; pl < pr; pl += w) { |
142 | if(sort_r_cmpswap(a: pl, b: pr, w, compar, arg)) { |
143 | pr -= w; /* pivot now at pl */ |
144 | break; |
145 | } |
146 | } |
147 | for(; pl < pr; pr -= w) { |
148 | if(sort_r_cmpswap(a: pl, b: pr, w, compar, arg)) { |
149 | pl += w; /* pivot now at pr */ |
150 | break; |
151 | } |
152 | } |
153 | } |
154 | |
155 | sort_r_simple(base: b, nel: (pl-b)/w, w, compar, arg); |
156 | sort_r_simple(base: pl+w, nel: (end-(pl+w))/w, w, compar, arg); |
157 | } |
158 | } |
159 | |
160 | static inline void hb_sort_r(void *base, size_t nel, size_t width, |
161 | int (*compar)(const void *_a, const void *_b, void *_arg), |
162 | void *arg) |
163 | { |
164 | sort_r_simple(base, nel, w: width, compar, arg); |
165 | } |
166 | |
167 | #endif /* HB_DSALGS_HH */ |
168 | |