OLD | NEW |
(Empty) | |
| 1 /* |
| 2 * Copyright © 2007,2008,2009 Red Hat, Inc. |
| 3 * Copyright © 2011 Google, Inc. |
| 4 * |
| 5 * This is part of HarfBuzz, a text shaping library. |
| 6 * |
| 7 * Permission is hereby granted, without written agreement and without |
| 8 * license or royalty fees, to use, copy, modify, and distribute this |
| 9 * software and its documentation for any purpose, provided that the |
| 10 * above copyright notice and the following two paragraphs appear in |
| 11 * all copies of this software. |
| 12 * |
| 13 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR |
| 14 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES |
| 15 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN |
| 16 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH |
| 17 * DAMAGE. |
| 18 * |
| 19 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, |
| 20 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND |
| 21 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS |
| 22 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO |
| 23 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. |
| 24 * |
| 25 * Red Hat Author(s): Behdad Esfahbod |
| 26 * Google Author(s): Behdad Esfahbod |
| 27 */ |
| 28 |
| 29 #ifndef HB_PRIVATE_HH |
| 30 #define HB_PRIVATE_HH |
| 31 |
| 32 #ifdef HAVE_CONFIG_H |
| 33 #include "config.h" |
| 34 #endif |
| 35 |
| 36 #include "hb-common.h" |
| 37 |
| 38 #include <stdlib.h> |
| 39 #include <stddef.h> |
| 40 #include <string.h> |
| 41 #include <assert.h> |
| 42 |
| 43 /* We only use these two for debug output. However, the debug code is |
| 44 * always seen by the compiler (and optimized out in non-debug builds. |
| 45 * If including these becomes a problem, we can start thinking about |
| 46 * someway around that. */ |
| 47 #include <stdio.h> |
| 48 #include <errno.h> |
| 49 #include <stdarg.h> |
| 50 |
| 51 |
| 52 |
| 53 /* Essentials */ |
| 54 |
| 55 #ifndef NULL |
| 56 # define NULL ((void *) 0) |
| 57 #endif |
| 58 |
| 59 #undef FALSE |
| 60 #define FALSE 0 |
| 61 |
| 62 #undef TRUE |
| 63 #define TRUE 1 |
| 64 |
| 65 |
| 66 /* Basics */ |
| 67 |
| 68 |
| 69 #undef MIN |
| 70 template <typename Type> static inline Type MIN (const Type &a, const Type &b) {
return a < b ? a : b; } |
| 71 |
| 72 #undef MAX |
| 73 template <typename Type> static inline Type MAX (const Type &a, const Type &b) {
return a > b ? a : b; } |
| 74 |
| 75 |
| 76 #undef ARRAY_LENGTH |
| 77 #define ARRAY_LENGTH(__array) ((signed int) (sizeof (__array) / sizeof (__array[
0]))) |
| 78 |
| 79 #define HB_STMT_START do |
| 80 #define HB_STMT_END while (0) |
| 81 |
| 82 #define _ASSERT_STATIC1(_line, _cond) typedef int _static_assert_on_line_##_line
##_failed[(_cond)?1:-1] |
| 83 #define _ASSERT_STATIC0(_line, _cond) _ASSERT_STATIC1 (_line, (_cond)) |
| 84 #define ASSERT_STATIC(_cond) _ASSERT_STATIC0 (__LINE__, (_cond)) |
| 85 |
| 86 #define ASSERT_STATIC_EXPR(_cond) ((void) sizeof (char[(_cond) ? 1 : -1])) |
| 87 #define ASSERT_STATIC_EXPR_ZERO(_cond) (0 * sizeof (char[(_cond) ? 1 : -1])) |
| 88 |
| 89 |
| 90 /* Lets assert int types. Saves trouble down the road. */ |
| 91 |
| 92 ASSERT_STATIC (sizeof (int8_t) == 1); |
| 93 ASSERT_STATIC (sizeof (uint8_t) == 1); |
| 94 ASSERT_STATIC (sizeof (int16_t) == 2); |
| 95 ASSERT_STATIC (sizeof (uint16_t) == 2); |
| 96 ASSERT_STATIC (sizeof (int32_t) == 4); |
| 97 ASSERT_STATIC (sizeof (uint32_t) == 4); |
| 98 ASSERT_STATIC (sizeof (int64_t) == 8); |
| 99 ASSERT_STATIC (sizeof (uint64_t) == 8); |
| 100 |
| 101 ASSERT_STATIC (sizeof (hb_codepoint_t) == 4); |
| 102 ASSERT_STATIC (sizeof (hb_position_t) == 4); |
| 103 ASSERT_STATIC (sizeof (hb_mask_t) == 4); |
| 104 ASSERT_STATIC (sizeof (hb_var_int_t) == 4); |
| 105 |
| 106 /* Misc */ |
| 107 |
| 108 |
| 109 #if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__) |
| 110 #define _HB_BOOLEAN_EXPR(expr) ((expr) ? 1 : 0) |
| 111 #define likely(expr) (__builtin_expect (_HB_BOOLEAN_EXPR(expr), 1)) |
| 112 #define unlikely(expr) (__builtin_expect (_HB_BOOLEAN_EXPR(expr), 0)) |
| 113 #else |
| 114 #define likely(expr) (expr) |
| 115 #define unlikely(expr) (expr) |
| 116 #endif |
| 117 |
| 118 #ifndef __GNUC__ |
| 119 #undef __attribute__ |
| 120 #define __attribute__(x) |
| 121 #endif |
| 122 |
| 123 #if __GNUC__ >= 3 |
| 124 #define HB_PURE_FUNC __attribute__((pure)) |
| 125 #define HB_CONST_FUNC __attribute__((const)) |
| 126 #define HB_PRINTF_FUNC(format_idx, arg_idx) __attribute__((__format__ (__printf_
_, format_idx, arg_idx))) |
| 127 #else |
| 128 #define HB_PURE_FUNC |
| 129 #define HB_CONST_FUNC |
| 130 #define HB_PRINTF_FUNC(format_idx, arg_idx) |
| 131 #endif |
| 132 #if __GNUC__ >= 4 |
| 133 #define HB_UNUSED __attribute__((unused)) |
| 134 #else |
| 135 #define HB_UNUSED |
| 136 #endif |
| 137 |
| 138 #ifndef HB_INTERNAL |
| 139 # ifndef __MINGW32__ |
| 140 # define HB_INTERNAL __attribute__((__visibility__("hidden"))) |
| 141 # else |
| 142 # define HB_INTERNAL |
| 143 # endif |
| 144 #endif |
| 145 |
| 146 |
| 147 #if (defined(__WIN32__) && !defined(__WINE__)) || defined(_MSC_VER) |
| 148 #define snprintf _snprintf |
| 149 #endif |
| 150 |
| 151 #ifdef _MSC_VER |
| 152 #undef inline |
| 153 #define inline __inline |
| 154 #endif |
| 155 |
| 156 #ifdef __STRICT_ANSI__ |
| 157 #undef inline |
| 158 #define inline __inline__ |
| 159 #endif |
| 160 |
| 161 |
| 162 #if __GNUC__ >= 3 |
| 163 #define HB_FUNC __PRETTY_FUNCTION__ |
| 164 #elif defined(_MSC_VER) |
| 165 #define HB_FUNC __FUNCSIG__ |
| 166 #else |
| 167 #define HB_FUNC __func__ |
| 168 #endif |
| 169 |
| 170 |
| 171 /* Return the number of 1 bits in mask. */ |
| 172 static inline HB_CONST_FUNC unsigned int |
| 173 _hb_popcount32 (uint32_t mask) |
| 174 { |
| 175 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) |
| 176 return __builtin_popcount (mask); |
| 177 #else |
| 178 /* "HACKMEM 169" */ |
| 179 register uint32_t y; |
| 180 y = (mask >> 1) &033333333333; |
| 181 y = mask - y - ((y >>1) & 033333333333); |
| 182 return (((y + (y >> 3)) & 030707070707) % 077); |
| 183 #endif |
| 184 } |
| 185 |
| 186 /* Returns the number of bits needed to store number */ |
| 187 static inline HB_CONST_FUNC unsigned int |
| 188 _hb_bit_storage (unsigned int number) |
| 189 { |
| 190 #if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__) |
| 191 return likely (number) ? (sizeof (unsigned int) * 8 - __builtin_clz (number))
: 0; |
| 192 #else |
| 193 register unsigned int n_bits = 0; |
| 194 while (number) { |
| 195 n_bits++; |
| 196 number >>= 1; |
| 197 } |
| 198 return n_bits; |
| 199 #endif |
| 200 } |
| 201 |
| 202 /* Returns the number of zero bits in the least significant side of number */ |
| 203 static inline HB_CONST_FUNC unsigned int |
| 204 _hb_ctz (unsigned int number) |
| 205 { |
| 206 #if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__) |
| 207 return likely (number) ? __builtin_ctz (number) : 0; |
| 208 #else |
| 209 register unsigned int n_bits = 0; |
| 210 if (unlikely (!number)) return 0; |
| 211 while (!(number & 1)) { |
| 212 n_bits++; |
| 213 number >>= 1; |
| 214 } |
| 215 return n_bits; |
| 216 #endif |
| 217 } |
| 218 |
| 219 static inline bool |
| 220 _hb_unsigned_int_mul_overflows (unsigned int count, unsigned int size) |
| 221 { |
| 222 return (size > 0) && (count >= ((unsigned int) -1) / size); |
| 223 } |
| 224 |
| 225 |
| 226 /* Type of bsearch() / qsort() compare function */ |
| 227 typedef int (*hb_compare_func_t) (const void *, const void *); |
| 228 |
| 229 |
| 230 |
| 231 |
| 232 /* arrays and maps */ |
| 233 |
| 234 |
| 235 template <typename Type, unsigned int StaticSize> |
| 236 struct hb_prealloced_array_t { |
| 237 |
| 238 unsigned int len; |
| 239 unsigned int allocated; |
| 240 Type *array; |
| 241 Type static_array[StaticSize]; |
| 242 |
| 243 hb_prealloced_array_t (void) { memset (this, 0, sizeof (*this)); } |
| 244 |
| 245 inline Type& operator [] (unsigned int i) { return array[i]; } |
| 246 inline const Type& operator [] (unsigned int i) const { return array[i]; } |
| 247 |
| 248 inline Type *push (void) |
| 249 { |
| 250 if (!array) { |
| 251 array = static_array; |
| 252 allocated = ARRAY_LENGTH (static_array); |
| 253 } |
| 254 if (likely (len < allocated)) |
| 255 return &array[len++]; |
| 256 |
| 257 /* Need to reallocate */ |
| 258 unsigned int new_allocated = allocated + (allocated >> 1) + 8; |
| 259 Type *new_array = NULL; |
| 260 |
| 261 if (array == static_array) { |
| 262 new_array = (Type *) calloc (new_allocated, sizeof (Type)); |
| 263 if (new_array) |
| 264 memcpy (new_array, array, len * sizeof (Type)); |
| 265 } else { |
| 266 bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overf
lows (new_allocated, sizeof (Type)); |
| 267 if (likely (!overflows)) { |
| 268 new_array = (Type *) realloc (array, new_allocated * sizeof (Type)); |
| 269 } |
| 270 } |
| 271 |
| 272 if (unlikely (!new_array)) |
| 273 return NULL; |
| 274 |
| 275 array = new_array; |
| 276 allocated = new_allocated; |
| 277 return &array[len++]; |
| 278 } |
| 279 |
| 280 inline void pop (void) |
| 281 { |
| 282 len--; |
| 283 /* TODO: shrink array if needed */ |
| 284 } |
| 285 |
| 286 inline void shrink (unsigned int l) |
| 287 { |
| 288 if (l < len) |
| 289 len = l; |
| 290 /* TODO: shrink array if needed */ |
| 291 } |
| 292 |
| 293 template <typename T> |
| 294 inline Type *find (T v) { |
| 295 for (unsigned int i = 0; i < len; i++) |
| 296 if (array[i] == v) |
| 297 return &array[i]; |
| 298 return NULL; |
| 299 } |
| 300 template <typename T> |
| 301 inline const Type *find (T v) const { |
| 302 for (unsigned int i = 0; i < len; i++) |
| 303 if (array[i] == v) |
| 304 return &array[i]; |
| 305 return NULL; |
| 306 } |
| 307 |
| 308 inline void sort (void) |
| 309 { |
| 310 qsort (array, len, sizeof (Type), (hb_compare_func_t) Type::cmp); |
| 311 } |
| 312 |
| 313 inline void sort (unsigned int start, unsigned int end) |
| 314 { |
| 315 qsort (array + start, end - start, sizeof (Type), (hb_compare_func_t) Type::
cmp); |
| 316 } |
| 317 |
| 318 template <typename T> |
| 319 inline Type *bsearch (T *key) |
| 320 { |
| 321 return (Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_
t) Type::cmp); |
| 322 } |
| 323 template <typename T> |
| 324 inline const Type *bsearch (T *key) const |
| 325 { |
| 326 return (const Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare
_func_t) Type::cmp); |
| 327 } |
| 328 |
| 329 inline void finish (void) |
| 330 { |
| 331 if (array != static_array) |
| 332 free (array); |
| 333 array = NULL; |
| 334 allocated = len = 0; |
| 335 } |
| 336 }; |
| 337 |
| 338 template <typename Type> |
| 339 struct hb_array_t : hb_prealloced_array_t<Type, 2> {}; |
| 340 |
| 341 |
| 342 template <typename item_t, typename lock_t> |
| 343 struct hb_lockable_set_t |
| 344 { |
| 345 hb_array_t <item_t> items; |
| 346 |
| 347 template <typename T> |
| 348 inline item_t *replace_or_insert (T v, lock_t &l, bool replace) |
| 349 { |
| 350 l.lock (); |
| 351 item_t *item = items.find (v); |
| 352 if (item) { |
| 353 if (replace) { |
| 354 item_t old = *item; |
| 355 *item = v; |
| 356 l.unlock (); |
| 357 old.finish (); |
| 358 } |
| 359 else { |
| 360 item = NULL; |
| 361 l.unlock (); |
| 362 } |
| 363 } else { |
| 364 item = items.push (); |
| 365 if (likely (item)) |
| 366 *item = v; |
| 367 l.unlock (); |
| 368 } |
| 369 return item; |
| 370 } |
| 371 |
| 372 template <typename T> |
| 373 inline void remove (T v, lock_t &l) |
| 374 { |
| 375 l.lock (); |
| 376 item_t *item = items.find (v); |
| 377 if (item) { |
| 378 item_t old = *item; |
| 379 *item = items[items.len - 1]; |
| 380 items.pop (); |
| 381 l.unlock (); |
| 382 old.finish (); |
| 383 } else { |
| 384 l.unlock (); |
| 385 } |
| 386 } |
| 387 |
| 388 template <typename T> |
| 389 inline bool find (T v, item_t *i, lock_t &l) |
| 390 { |
| 391 l.lock (); |
| 392 item_t *item = items.find (v); |
| 393 if (item) |
| 394 *i = *item; |
| 395 l.unlock (); |
| 396 return !!item; |
| 397 } |
| 398 |
| 399 template <typename T> |
| 400 inline item_t *find_or_insert (T v, lock_t &l) |
| 401 { |
| 402 l.lock (); |
| 403 item_t *item = items.find (v); |
| 404 if (!item) { |
| 405 item = items.push (); |
| 406 if (likely (item)) |
| 407 *item = v; |
| 408 } |
| 409 l.unlock (); |
| 410 return item; |
| 411 } |
| 412 |
| 413 inline void finish (lock_t &l) |
| 414 { |
| 415 l.lock (); |
| 416 while (items.len) { |
| 417 item_t old = items[items.len - 1]; |
| 418 items.pop (); |
| 419 l.unlock (); |
| 420 old.finish (); |
| 421 l.lock (); |
| 422 } |
| 423 items.finish (); |
| 424 l.unlock (); |
| 425 } |
| 426 |
| 427 }; |
| 428 |
| 429 |
| 430 |
| 431 |
| 432 /* Big-endian handling */ |
| 433 |
| 434 static inline uint16_t hb_be_uint16 (const uint16_t v) |
| 435 { |
| 436 const uint8_t *V = (const uint8_t *) &v; |
| 437 return (uint16_t) (V[0] << 8) + V[1]; |
| 438 } |
| 439 |
| 440 #define hb_be_uint16_put(v,V) HB_STMT_START { v[0] = (V>>8); v[1] = (V); } HB_
STMT_END |
| 441 #define hb_be_uint16_get(v) (uint16_t) ((v[0] << 8) + v[1]) |
| 442 #define hb_be_uint16_eq(a,b) (a[0] == b[0] && a[1] == b[1]) |
| 443 |
| 444 #define hb_be_uint32_put(v,V) HB_STMT_START { v[0] = (V>>24); v[1] = (V>>16);
v[2] = (V>>8); v[3] = (V); } HB_STMT_END |
| 445 #define hb_be_uint32_get(v) (uint32_t) ((v[0] << 24) + (v[1] << 16) + (v[2]
<< 8) + v[3]) |
| 446 #define hb_be_uint32_eq(a,b) (a[0] == b[0] && a[1] == b[1] && a[2] == b[2] &&
a[3] == b[3]) |
| 447 |
| 448 |
| 449 /* ASCII tag/character handling */ |
| 450 |
| 451 static inline unsigned char ISALPHA (unsigned char c) |
| 452 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); } |
| 453 static inline unsigned char ISALNUM (unsigned char c) |
| 454 { return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '
9'); } |
| 455 static inline unsigned char TOUPPER (unsigned char c) |
| 456 { return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; } |
| 457 static inline unsigned char TOLOWER (unsigned char c) |
| 458 { return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; } |
| 459 |
| 460 #define HB_TAG_CHAR4(s) (HB_TAG(((const char *) s)[0], \ |
| 461 ((const char *) s)[1], \ |
| 462 ((const char *) s)[2], \ |
| 463 ((const char *) s)[3])) |
| 464 |
| 465 |
| 466 /* C++ helpers */ |
| 467 |
| 468 /* Makes class uncopyable. Use in private: section. */ |
| 469 #define NO_COPY(T) \ |
| 470 T (const T &o); \ |
| 471 T &operator = (const T &o) |
| 472 |
| 473 |
| 474 /* Debug */ |
| 475 |
| 476 |
| 477 #ifndef HB_DEBUG |
| 478 #define HB_DEBUG 0 |
| 479 #endif |
| 480 |
| 481 static inline bool |
| 482 _hb_debug (unsigned int level, |
| 483 unsigned int max_level) |
| 484 { |
| 485 return level < max_level; |
| 486 } |
| 487 |
| 488 #define DEBUG_LEVEL(WHAT, LEVEL) (_hb_debug ((LEVEL), HB_DEBUG_##WHAT)) |
| 489 #define DEBUG(WHAT) (DEBUG_LEVEL (WHAT, 0)) |
| 490 |
| 491 template <int max_level> inline bool /* always returns TRUE */ |
| 492 _hb_debug_msg (const char *what, |
| 493 const void *obj, |
| 494 const char *func, |
| 495 bool indented, |
| 496 int level, |
| 497 const char *message, |
| 498 ...) HB_PRINTF_FUNC(6, 7); |
| 499 template <int max_level> inline bool /* always returns TRUE */ |
| 500 _hb_debug_msg (const char *what, |
| 501 const void *obj, |
| 502 const char *func, |
| 503 bool indented, |
| 504 int level, |
| 505 const char *message, |
| 506 ...) |
| 507 { |
| 508 va_list ap; |
| 509 va_start (ap, message); |
| 510 |
| 511 (void) (_hb_debug (level, max_level) && |
| 512 fprintf (stderr, "%s", what) && |
| 513 (obj && fprintf (stderr, "(%p)", obj), TRUE) && |
| 514 fprintf (stderr, ": ") && |
| 515 (func && fprintf (stderr, "%s: ", func), TRUE) && |
| 516 (indented && fprintf (stderr, "%-*d-> ", level + 1, level), TRUE) && |
| 517 vfprintf (stderr, message, ap) && |
| 518 fprintf (stderr, "\n")); |
| 519 |
| 520 va_end (ap); |
| 521 |
| 522 return TRUE; |
| 523 } |
| 524 template <> inline bool /* always returns TRUE */ |
| 525 _hb_debug_msg<0> (const char *what, |
| 526 const void *obj, |
| 527 const char *func, |
| 528 bool indented, |
| 529 int level, |
| 530 const char *message, |
| 531 ...) HB_PRINTF_FUNC(6, 7); |
| 532 template <> inline bool /* always returns TRUE */ |
| 533 _hb_debug_msg<0> (const char *what, |
| 534 const void *obj, |
| 535 const char *func, |
| 536 bool indented, |
| 537 int level, |
| 538 const char *message, |
| 539 ...) |
| 540 { |
| 541 return TRUE; |
| 542 } |
| 543 |
| 544 #define DEBUG_MSG_LEVEL(WHAT, OBJ, LEVEL, ...) _hb_debug_msg<HB_DEBUG_##WHAT> (#
WHAT, (OBJ), NULL, FALSE, (LEVEL), __VA_ARGS__) |
| 545 #define DEBUG_MSG(WHAT, OBJ, ...) DEBUG_MSG_LEVEL (WHAT, OBJ, 0, __VA_ARGS__) |
| 546 #define DEBUG_MSG_FUNC(WHAT, OBJ, ...) _hb_debug_msg<HB_DEBUG_##WHAT> (#WHAT, (O
BJ), HB_FUNC, FALSE, 0, __VA_ARGS__) |
| 547 |
| 548 |
| 549 /* |
| 550 * Trace |
| 551 */ |
| 552 |
| 553 template <int max_level> |
| 554 struct hb_auto_trace_t { |
| 555 explicit inline hb_auto_trace_t (unsigned int *plevel_, |
| 556 const char *what, |
| 557 const void *obj, |
| 558 const char *func, |
| 559 const char *message) : plevel(plevel_) |
| 560 { |
| 561 if (max_level) ++*plevel; |
| 562 /* TODO support variadic args here */ |
| 563 _hb_debug_msg<max_level> (what, obj, func, TRUE, *plevel, "%s", message); |
| 564 } |
| 565 ~hb_auto_trace_t (void) { if (max_level) --*plevel; } |
| 566 |
| 567 private: |
| 568 unsigned int *plevel; |
| 569 }; |
| 570 template <> /* Optimize when tracing is disabled */ |
| 571 struct hb_auto_trace_t<0> { |
| 572 explicit inline hb_auto_trace_t (unsigned int *plevel_, |
| 573 const char *what, |
| 574 const void *obj, |
| 575 const char *func, |
| 576 const char *message) {} |
| 577 }; |
| 578 |
| 579 |
| 580 /* Misc */ |
| 581 |
| 582 |
| 583 /* Pre-mature optimization: |
| 584 * Checks for lo <= u <= hi but with an optimization if lo and hi |
| 585 * are only different in a contiguous set of lower-most bits. |
| 586 */ |
| 587 template <typename T> inline bool |
| 588 hb_in_range (T u, T lo, T hi) |
| 589 { |
| 590 if ( ((lo^hi) & lo) == 0 && |
| 591 ((lo^hi) & hi) == (lo^hi) && |
| 592 ((lo^hi) & ((lo^hi) + 1)) == 0 ) |
| 593 return (u & ~(lo^hi)) == lo; |
| 594 else |
| 595 return lo <= u && u <= hi; |
| 596 } |
| 597 |
| 598 |
| 599 /* Useful for set-operations on small enums. |
| 600 * For example, for testing "x ∈ {x1, x2, x3}" use: |
| 601 * (FLAG(x) & (FLAG(x1) | FLAG(x2) | FLAG(x3))) |
| 602 */ |
| 603 #define FLAG(x) (1<<(x)) |
| 604 |
| 605 |
| 606 template <typename T> inline void |
| 607 hb_bubble_sort (T *array, unsigned int len, int(*compar)(const T *, const T *)) |
| 608 { |
| 609 if (unlikely (!len)) |
| 610 return; |
| 611 |
| 612 unsigned int k = len - 1; |
| 613 do { |
| 614 unsigned int new_k = 0; |
| 615 |
| 616 for (unsigned int j = 0; j < k; j++) |
| 617 if (compar (&array[j], &array[j+1]) > 0) { |
| 618 T t; |
| 619 t = array[j]; |
| 620 array[j] = array[j + 1]; |
| 621 array[j + 1] = t; |
| 622 |
| 623 new_k = j; |
| 624 } |
| 625 k = new_k; |
| 626 } while (k); |
| 627 } |
| 628 |
| 629 |
| 630 |
| 631 |
| 632 #endif /* HB_PRIVATE_HH */ |
OLD | NEW |