hb-private.hh 26.5 KB
Newer Older
B
Behdad Esfahbod 已提交
1
/*
B
Behdad Esfahbod 已提交
2
 * Copyright © 2007,2008,2009  Red Hat, Inc.
3
 * Copyright © 2011,2012  Google, Inc.
B
Behdad Esfahbod 已提交
4
 *
B
Behdad Esfahbod 已提交
5
 *  This is part of HarfBuzz, a text shaping library.
B
Behdad Esfahbod 已提交
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
 *
 * Permission is hereby granted, without written agreement and without
 * license or royalty fees, to use, copy, modify, and distribute this
 * software and its documentation for any purpose, provided that the
 * above copyright notice and the following two paragraphs appear in
 * all copies of this software.
 *
 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 *
 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 *
 * Red Hat Author(s): Behdad Esfahbod
B
Behdad Esfahbod 已提交
26
 * Google Author(s): Behdad Esfahbod
B
Behdad Esfahbod 已提交
27 28
 */

29 30
#ifndef HB_PRIVATE_HH
#define HB_PRIVATE_HH
B
Behdad Esfahbod 已提交
31

B
Minor  
Behdad Esfahbod 已提交
32
#ifdef HAVE_CONFIG_H
B
Behdad Esfahbod 已提交
33 34
#include "config.h"
#endif
B
Behdad Esfahbod 已提交
35

36 37
#include "hb.h"
#define HB_H_IN
B
Minor  
Behdad Esfahbod 已提交
38 39
#ifdef HAVE_OT
#include "hb-ot.h"
40
#define HB_OT_H_IN
B
Minor  
Behdad Esfahbod 已提交
41
#endif
42

B
Behdad Esfahbod 已提交
43
#include <stdlib.h>
44
#include <stddef.h>
B
Behdad Esfahbod 已提交
45 46
#include <string.h>
#include <assert.h>
B
Minor  
Behdad Esfahbod 已提交
47 48 49 50 51

/* We only use these two for debug output.  However, the debug code is
 * always seen by the compiler (and optimized out in non-debug builds.
 * If including these becomes a problem, we can start thinking about
 * someway around that. */
52 53
#include <stdio.h>
#include <errno.h>
54
#include <stdarg.h>
B
Behdad Esfahbod 已提交
55

B
Behdad Esfahbod 已提交
56

57 58 59 60 61 62
/* Compile-time custom allocator support. */

#if defined(hb_malloc_impl) \
 && defined(hb_calloc_impl) \
 && defined(hb_realloc_impl) \
 && defined(hb_free_impl)
63 64 65 66
extern "C" void* hb_malloc_impl(size_t size);
extern "C" void* hb_calloc_impl(size_t nmemb, size_t size);
extern "C" void* hb_realloc_impl(void *ptr, size_t size);
extern "C" void  hb_free_impl(void *ptr);
67 68 69 70 71 72 73
#define malloc hb_malloc_impl
#define calloc hb_calloc_impl
#define realloc hb_realloc_impl
#define free hb_free_impl
#endif


B
Behdad Esfahbod 已提交
74
/* Compiler attributes */
B
Behdad Esfahbod 已提交
75 76


B
Behdad Esfahbod 已提交
77 78 79 80 81 82 83
#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__)
#define _HB_BOOLEAN_EXPR(expr) ((expr) ? 1 : 0)
#define likely(expr) (__builtin_expect (_HB_BOOLEAN_EXPR(expr), 1))
#define unlikely(expr) (__builtin_expect (_HB_BOOLEAN_EXPR(expr), 0))
#else
#define likely(expr) (expr)
#define unlikely(expr) (expr)
B
Behdad Esfahbod 已提交
84 85
#endif

B
Behdad Esfahbod 已提交
86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106
#ifndef __GNUC__
#undef __attribute__
#define __attribute__(x)
#endif

#if __GNUC__ >= 3
#define HB_PURE_FUNC	__attribute__((pure))
#define HB_CONST_FUNC	__attribute__((const))
#define HB_PRINTF_FUNC(format_idx, arg_idx) __attribute__((__format__ (__printf__, format_idx, arg_idx)))
#else
#define HB_PURE_FUNC
#define HB_CONST_FUNC
#define HB_PRINTF_FUNC(format_idx, arg_idx)
#endif
#if __GNUC__ >= 4
#define HB_UNUSED	__attribute__((unused))
#else
#define HB_UNUSED
#endif

#ifndef HB_INTERNAL
107
# if !defined(__MINGW32__) && !defined(__CYGWIN__)
B
Behdad Esfahbod 已提交
108 109 110 111 112 113 114 115 116 117 118 119 120
#  define HB_INTERNAL __attribute__((__visibility__("hidden")))
# else
#  define HB_INTERNAL
# endif
#endif

#if __GNUC__ >= 3
#define HB_FUNC __PRETTY_FUNCTION__
#elif defined(_MSC_VER)
#define HB_FUNC __FUNCSIG__
#else
#define HB_FUNC __func__
#endif
B
Behdad Esfahbod 已提交
121

B
Behdad Esfahbod 已提交
122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151
/*
 * Borrowed from https://bugzilla.mozilla.org/show_bug.cgi?id=1215411
 * HB_FALLTHROUGH is an annotation to suppress compiler warnings about switch
 * cases that fall through without a break or return statement. HB_FALLTHROUGH
 * is only needed on cases that have code:
 *
 * switch (foo) {
 *   case 1: // These cases have no code. No fallthrough annotations are needed.
 *   case 2:
 *   case 3:
 *     foo = 4; // This case has code, so a fallthrough annotation is needed:
 *     HB_FALLTHROUGH;
 *   default:
 *     return foo;
 * }
 */
#if defined(__clang__) && __cplusplus >= 201103L
   /* clang's fallthrough annotations are only available starting in C++11. */
#  define HB_FALLTHROUGH [[clang::fallthrough]]
#elif defined(_MSC_VER)
   /*
    * MSVC's __fallthrough annotations are checked by /analyze (Code Analysis):
    * https://msdn.microsoft.com/en-us/library/ms235402%28VS.80%29.aspx
    */
#  include <sal.h>
#  define HB_FALLTHROUGH __fallthrough
#else
#  define HB_FALLTHROUGH /* FALLTHROUGH */
#endif

B
Behdad Esfahbod 已提交
152
#if defined(_WIN32) || defined(__CYGWIN__)
153 154 155 156 157 158 159 160 161
   /* We need Windows Vista for both Uniscribe backend and for
    * MemoryBarrier.  We don't support compiling on Windows XP,
    * though we run on it fine. */
#  if defined(_WIN32_WINNT) && _WIN32_WINNT < 0x0600
#    undef _WIN32_WINNT
#  endif
#  ifndef _WIN32_WINNT
#    define _WIN32_WINNT 0x0600
#  endif
162 163 164 165 166 167
#  ifndef WIN32_LEAN_AND_MEAN
#    define WIN32_LEAN_AND_MEAN 1
#  endif
#  ifndef STRICT
#    define STRICT 1
#  endif
B
Minor  
Behdad Esfahbod 已提交
168

K
Konstantin Ritt 已提交
169 170
#  if defined(_WIN32_WCE)
     /* Some things not defined on Windows CE. */
171
#    define strdup _strdup
K
Konstantin Ritt 已提交
172
#    define getenv(Name) NULL
K
Konstantin Ritt 已提交
173 174
#    if _WIN32_WCE < 0x800
#      define setlocale(Category, Locale) "C"
175
static int errno = 0; /* Use something better? */
K
Konstantin Ritt 已提交
176
#    endif
K
Konstantin Ritt 已提交
177 178 179
#  elif defined(WINAPI_FAMILY) && (WINAPI_FAMILY==WINAPI_FAMILY_PC_APP || WINAPI_FAMILY==WINAPI_FAMILY_PHONE_APP)
#    define getenv(Name) NULL
#  endif
180
#  if defined(_MSC_VER) && _MSC_VER < 1900
K
Konstantin Ritt 已提交
181 182
#    define snprintf _snprintf
#  endif
183 184
#endif

185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
#if HAVE_ATEXIT
/* atexit() is only safe to be called from shared libraries on certain
 * platforms.  Whitelist.
 * https://bugs.freedesktop.org/show_bug.cgi?id=82246 */
#  if defined(__linux) && defined(__GLIBC_PREREQ)
#    if __GLIBC_PREREQ(2,3)
/* From atexit() manpage, it's safe with glibc 2.2.3 on Linux. */
#      define HB_USE_ATEXIT 1
#    endif
#  elif defined(_MSC_VER) || defined(__MINGW32__)
/* For MSVC:
 * http://msdn.microsoft.com/en-ca/library/tze57ck3.aspx
 * http://msdn.microsoft.com/en-ca/library/zk17ww08.aspx
 * mingw32 headers say atexit is safe to use in shared libraries.
 */
#    define HB_USE_ATEXIT 1
#  elif defined(__ANDROID__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6))
/* This was fixed in Android NKD r8 or r8b:
 * https://code.google.com/p/android/issues/detail?id=6455
 * which introduced GCC 4.6:
 * https://developer.android.com/tools/sdk/ndk/index.html
 */
#    define HB_USE_ATEXIT 1
#  endif
#endif
B
Minor  
Behdad Esfahbod 已提交
210

B
Behdad Esfahbod 已提交
211 212
/* Basics */

213

B
Behdad Esfahbod 已提交
214 215 216 217
#ifndef NULL
# define NULL ((void *) 0)
#endif

B
Behdad Esfahbod 已提交
218
#undef MIN
219 220
template <typename Type>
static inline Type MIN (const Type &a, const Type &b) { return a < b ? a : b; }
B
Minor  
Behdad Esfahbod 已提交
221

222
#undef MAX
223 224
template <typename Type>
static inline Type MAX (const Type &a, const Type &b) { return a > b ? a : b; }
225

226 227 228
static inline unsigned int DIV_CEIL (const unsigned int a, unsigned int b)
{ return (a + (b - 1)) / b; }

229

B
Behdad Esfahbod 已提交
230
#undef  ARRAY_LENGTH
231
template <typename Type, unsigned int n>
B
Behdad Esfahbod 已提交
232
static inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; }
233 234
/* A const version, but does not detect erratically being called on pointers. */
#define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0])))
235

236 237
#define HB_STMT_START do
#define HB_STMT_END   while (0)
B
Behdad Esfahbod 已提交
238

239
#define _ASSERT_STATIC1(_line, _cond)	HB_UNUSED typedef int _static_assert_on_line_##_line##_failed[(_cond)?1:-1]
B
Minor  
Behdad Esfahbod 已提交
240 241
#define _ASSERT_STATIC0(_line, _cond)	_ASSERT_STATIC1 (_line, (_cond))
#define ASSERT_STATIC(_cond)		_ASSERT_STATIC0 (__LINE__, (_cond))
B
Behdad Esfahbod 已提交
242

243 244
/* Note: C++ allows sizeof() of variable-lengh arrays.  So, if _cond is not
 * constant, it still compiles (ouch!), but at least we'll get a -Wvla warning. */
B
Behdad Esfahbod 已提交
245
#define ASSERT_STATIC_EXPR_ZERO(_cond) (0 * (unsigned int) sizeof (char[(_cond) ? 1 : -1]))
B
Behdad Esfahbod 已提交
246

247 248
#define _PASTE1(a,b) a##b
#define PASTE(a,b) _PASTE1(a,b)
B
Behdad Esfahbod 已提交
249

B
Behdad Esfahbod 已提交
250 251 252 253 254 255 256 257 258 259 260
/* Lets assert int types.  Saves trouble down the road. */

ASSERT_STATIC (sizeof (int8_t) == 1);
ASSERT_STATIC (sizeof (uint8_t) == 1);
ASSERT_STATIC (sizeof (int16_t) == 2);
ASSERT_STATIC (sizeof (uint16_t) == 2);
ASSERT_STATIC (sizeof (int32_t) == 4);
ASSERT_STATIC (sizeof (uint32_t) == 4);
ASSERT_STATIC (sizeof (int64_t) == 8);
ASSERT_STATIC (sizeof (uint64_t) == 8);

B
Behdad Esfahbod 已提交
261 262 263
ASSERT_STATIC (sizeof (hb_codepoint_t) == 4);
ASSERT_STATIC (sizeof (hb_position_t) == 4);
ASSERT_STATIC (sizeof (hb_mask_t) == 4);
264
ASSERT_STATIC (sizeof (hb_var_int_t) == 4);
B
Behdad Esfahbod 已提交
265

266 267 268

/* We like our types POD */

B
Minor  
Behdad Esfahbod 已提交
269 270 271
#define _ASSERT_TYPE_POD1(_line, _type)	union _type_##_type##_on_line_##_line##_is_not_POD { _type instance; }
#define _ASSERT_TYPE_POD0(_line, _type)	_ASSERT_TYPE_POD1 (_line, _type)
#define ASSERT_TYPE_POD(_type)		_ASSERT_TYPE_POD0 (__LINE__, _type)
272 273

#ifdef __GNUC__
B
Behdad Esfahbod 已提交
274 275 276 277 278
# define _ASSERT_INSTANCE_POD1(_line, _instance) \
	HB_STMT_START { \
		typedef __typeof__(_instance) _type_##_line; \
		_ASSERT_TYPE_POD1 (_line, _type_##_line); \
	} HB_STMT_END
279
#else
B
Minor  
Behdad Esfahbod 已提交
280
# define _ASSERT_INSTANCE_POD1(_line, _instance)	typedef int _assertion_on_line_##_line##_not_tested
281
#endif
B
Minor  
Behdad Esfahbod 已提交
282 283
# define _ASSERT_INSTANCE_POD0(_line, _instance)	_ASSERT_INSTANCE_POD1 (_line, _instance)
# define ASSERT_INSTANCE_POD(_instance)			_ASSERT_INSTANCE_POD0 (__LINE__, _instance)
284 285 286

/* Check _assertion in a method environment */
#define _ASSERT_POD1(_line) \
B
Behdad Esfahbod 已提交
287
	HB_UNUSED inline void _static_assertion_on_line_##_line (void) const \
B
Minor  
Behdad Esfahbod 已提交
288 289 290
	{ _ASSERT_INSTANCE_POD1 (_line, *this); /* Make sure it's POD. */ }
# define _ASSERT_POD0(_line)	_ASSERT_POD1 (_line)
# define ASSERT_POD()		_ASSERT_POD0 (__LINE__)
291 292 293



B
Behdad Esfahbod 已提交
294 295
/* Misc */

B
Behdad Esfahbod 已提交
296 297
/* Void! */
struct _hb_void_t {};
298 299
typedef const _hb_void_t *hb_void_t;
#define HB_VOID ((const _hb_void_t *) NULL)
300

B
Behdad Esfahbod 已提交
301
/* Return the number of 1 bits in mask. */
B
Behdad Esfahbod 已提交
302
static inline HB_CONST_FUNC unsigned int
B
Behdad Esfahbod 已提交
303 304 305
_hb_popcount32 (uint32_t mask)
{
#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
B
Behdad Esfahbod 已提交
306
  return __builtin_popcount (mask);
B
Behdad Esfahbod 已提交
307
#else
B
Behdad Esfahbod 已提交
308
  /* "HACKMEM 169" */
309
  uint32_t y;
B
Behdad Esfahbod 已提交
310 311 312
  y = (mask >> 1) &033333333333;
  y = mask - y - ((y >>1) & 033333333333);
  return (((y + (y >> 3)) & 030707070707) % 077);
B
Behdad Esfahbod 已提交
313 314 315
#endif
}

B
Behdad Esfahbod 已提交
316 317 318 319 320
/* Returns the number of bits needed to store number */
static inline HB_CONST_FUNC unsigned int
_hb_bit_storage (unsigned int number)
{
#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__)
B
Behdad Esfahbod 已提交
321
  return likely (number) ? (sizeof (unsigned int) * 8 - __builtin_clz (number)) : 0;
B
Behdad Esfahbod 已提交
322
#else
323
  unsigned int n_bits = 0;
B
Behdad Esfahbod 已提交
324 325 326 327 328 329 330
  while (number) {
    n_bits++;
    number >>= 1;
  }
  return n_bits;
#endif
}
B
Behdad Esfahbod 已提交
331

B
Behdad Esfahbod 已提交
332 333 334 335 336 337 338
/* Returns the number of zero bits in the least significant side of number */
static inline HB_CONST_FUNC unsigned int
_hb_ctz (unsigned int number)
{
#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__)
  return likely (number) ? __builtin_ctz (number) : 0;
#else
339
  unsigned int n_bits = 0;
B
Behdad Esfahbod 已提交
340 341 342 343 344 345 346 347 348
  if (unlikely (!number)) return 0;
  while (!(number & 1)) {
    n_bits++;
    number >>= 1;
  }
  return n_bits;
#endif
}

349 350 351 352 353 354 355
static inline bool
_hb_unsigned_int_mul_overflows (unsigned int count, unsigned int size)
{
  return (size > 0) && (count >= ((unsigned int) -1) / size);
}


B
Behdad Esfahbod 已提交
356 357 358 359
/* Type of bsearch() / qsort() compare function */
typedef int (*hb_compare_func_t) (const void *, const void *);


B
Behdad Esfahbod 已提交
360 361 362 363 364


/* arrays and maps */


B
Behdad Esfahbod 已提交
365
#define HB_PREALLOCED_ARRAY_INIT {0, 0, NULL}
366
template <typename Type, unsigned int StaticSize=16>
B
Behdad Esfahbod 已提交
367 368
struct hb_prealloced_array_t
{
B
Behdad Esfahbod 已提交
369 370 371 372 373
  unsigned int len;
  unsigned int allocated;
  Type *array;
  Type static_array[StaticSize];

374
  void init (void) { memset (this, 0, sizeof (*this)); }
375

376 377
  inline Type& operator [] (unsigned int i) { return array[i]; }
  inline const Type& operator [] (unsigned int i) const { return array[i]; }
B
Behdad Esfahbod 已提交
378 379 380 381 382 383 384 385 386

  inline Type *push (void)
  {
    if (!array) {
      array = static_array;
      allocated = ARRAY_LENGTH (static_array);
    }
    if (likely (len < allocated))
      return &array[len++];
387

B
Behdad Esfahbod 已提交
388 389
    /* Need to reallocate */
    unsigned int new_allocated = allocated + (allocated >> 1) + 8;
390 391
    Type *new_array = NULL;

B
Behdad Esfahbod 已提交
392 393
    if (array == static_array) {
      new_array = (Type *) calloc (new_allocated, sizeof (Type));
394
      if (new_array)
B
Behdad Esfahbod 已提交
395 396
        memcpy (new_array, array, len * sizeof (Type));
    } else {
397
      bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overflows (new_allocated, sizeof (Type));
398
      if (likely (!overflows)) {
B
Behdad Esfahbod 已提交
399 400 401
	new_array = (Type *) realloc (array, new_allocated * sizeof (Type));
      }
    }
402 403

    if (unlikely (!new_array))
B
Behdad Esfahbod 已提交
404
      return NULL;
405 406 407 408

    array = new_array;
    allocated = new_allocated;
    return &array[len++];
B
Behdad Esfahbod 已提交
409 410 411 412 413
  }

  inline void pop (void)
  {
    len--;
B
Minor  
Behdad Esfahbod 已提交
414 415 416 417 418 419 420 421 422 423
  }

  inline void remove (unsigned int i)
  {
     if (unlikely (i >= len))
       return;
     memmove (static_cast<void *> (&array[i]),
	      static_cast<void *> (&array[i + 1]),
	      (len - i - 1) * sizeof (Type));
     len--;
B
Behdad Esfahbod 已提交
424
  }
425 426 427 428 429 430 431

  inline void shrink (unsigned int l)
  {
     if (l < len)
       len = l;
  }

432 433 434 435 436 437 438 439 440 441 442 443 444 445 446
  template <typename T>
  inline Type *find (T v) {
    for (unsigned int i = 0; i < len; i++)
      if (array[i] == v)
	return &array[i];
    return NULL;
  }
  template <typename T>
  inline const Type *find (T v) const {
    for (unsigned int i = 0; i < len; i++)
      if (array[i] == v)
	return &array[i];
    return NULL;
  }

B
Behdad Esfahbod 已提交
447
  inline void qsort (void)
448
  {
B
Behdad Esfahbod 已提交
449
    ::qsort (array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);
450
  }
451

B
Behdad Esfahbod 已提交
452
  inline void qsort (unsigned int start, unsigned int end)
453
  {
B
Behdad Esfahbod 已提交
454
    ::qsort (array + start, end - start, sizeof (Type), (hb_compare_func_t) Type::cmp);
455 456
  }

457 458 459 460 461 462 463 464 465 466
  template <typename T>
  inline Type *bsearch (T *key)
  {
    return (Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);
  }
  template <typename T>
  inline const Type *bsearch (T *key) const
  {
    return (const Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp);
  }
B
Behdad Esfahbod 已提交
467 468 469 470 471 472 473 474

  inline void finish (void)
  {
    if (array != static_array)
      free (array);
    array = NULL;
    allocated = len = 0;
  }
B
Behdad Esfahbod 已提交
475 476
};

B
Behdad Esfahbod 已提交
477
template <typename Type>
478
struct hb_auto_array_t : hb_prealloced_array_t <Type>
B
Behdad Esfahbod 已提交
479
{
480 481
  hb_auto_array_t (void) { hb_prealloced_array_t<Type>::init (); }
  ~hb_auto_array_t (void) { hb_prealloced_array_t<Type>::finish (); }
B
Behdad Esfahbod 已提交
482 483
};

484

B
Behdad Esfahbod 已提交
485
#define HB_LOCKABLE_SET_INIT {HB_PREALLOCED_ARRAY_INIT}
486 487
template <typename item_t, typename lock_t>
struct hb_lockable_set_t
B
Behdad Esfahbod 已提交
488
{
B
Behdad Esfahbod 已提交
489
  hb_prealloced_array_t <item_t, 2> items;
B
Behdad Esfahbod 已提交
490

491 492
  inline void init (void) { items.init (); }

493
  template <typename T>
494
  inline item_t *replace_or_insert (T v, lock_t &l, bool replace)
B
Behdad Esfahbod 已提交
495
  {
496
    l.lock ();
497
    item_t *item = items.find (v);
498
    if (item) {
499 500 501 502 503 504 505 506 507 508
      if (replace) {
	item_t old = *item;
	*item = v;
	l.unlock ();
	old.finish ();
      }
      else {
        item = NULL;
	l.unlock ();
      }
509
    } else {
B
Behdad Esfahbod 已提交
510
      item = items.push ();
511 512 513 514
      if (likely (item))
	*item = v;
      l.unlock ();
    }
515
    return item;
B
Behdad Esfahbod 已提交
516 517
  }

518
  template <typename T>
519
  inline void remove (T v, lock_t &l)
B
Behdad Esfahbod 已提交
520
  {
521
    l.lock ();
522
    item_t *item = items.find (v);
523 524 525 526 527 528 529 530 531
    if (item) {
      item_t old = *item;
      *item = items[items.len - 1];
      items.pop ();
      l.unlock ();
      old.finish ();
    } else {
      l.unlock ();
    }
B
Behdad Esfahbod 已提交
532
  }
533

534
  template <typename T>
535
  inline bool find (T v, item_t *i, lock_t &l)
B
Behdad Esfahbod 已提交
536
  {
537 538 539 540 541 542
    l.lock ();
    item_t *item = items.find (v);
    if (item)
      *i = *item;
    l.unlock ();
    return !!item;
543 544
  }

545
  template <typename T>
546 547 548 549
  inline item_t *find_or_insert (T v, lock_t &l)
  {
    l.lock ();
    item_t *item = items.find (v);
550 551 552 553 554
    if (!item) {
      item = items.push ();
      if (likely (item))
        *item = v;
    }
555
    l.unlock ();
556 557 558
    return item;
  }

559 560
  inline void finish (lock_t &l)
  {
561 562 563 564 565
    if (!items.len) {
      /* No need for locking. */
      items.finish ();
      return;
    }
566 567 568 569 570 571 572 573
    l.lock ();
    while (items.len) {
      item_t old = items[items.len - 1];
	items.pop ();
	l.unlock ();
	old.finish ();
	l.lock ();
    }
B
Behdad Esfahbod 已提交
574
    items.finish ();
575 576 577 578 579
    l.unlock ();
  }

};

B
Behdad Esfahbod 已提交
580

B
Behdad Esfahbod 已提交
581
/* ASCII tag/character handling */
B
Behdad Esfahbod 已提交
582

583
static inline bool ISALPHA (unsigned char c)
584
{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); }
585
static inline bool ISALNUM (unsigned char c)
586
{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); }
587 588
static inline bool ISSPACE (unsigned char c)
{ return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; }
589 590 591 592
static inline unsigned char TOUPPER (unsigned char c)
{ return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; }
static inline unsigned char TOLOWER (unsigned char c)
{ return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; }
B
Behdad Esfahbod 已提交
593

B
Behdad Esfahbod 已提交
594 595 596 597 598
#define HB_TAG_CHAR4(s)   (HB_TAG(((const char *) s)[0], \
				  ((const char *) s)[1], \
				  ((const char *) s)[2], \
				  ((const char *) s)[3]))

B
Behdad Esfahbod 已提交
599

B
Behdad Esfahbod 已提交
600 601 602 603 604
/* C++ helpers */

/* Makes class uncopyable.  Use in private: section. */
#define NO_COPY(T) \
  T (const T &o); \
B
Behdad Esfahbod 已提交
605
  T &operator = (const T &o)
B
Behdad Esfahbod 已提交
606 607


B
Behdad Esfahbod 已提交
608 609
/* Debug */

610

B
Behdad Esfahbod 已提交
611 612 613 614
#ifndef HB_DEBUG
#define HB_DEBUG 0
#endif

615 616 617 618 619 620 621
static inline bool
_hb_debug (unsigned int level,
	   unsigned int max_level)
{
  return level < max_level;
}

622 623
#define DEBUG_LEVEL_ENABLED(WHAT, LEVEL) (_hb_debug ((LEVEL), HB_DEBUG_##WHAT))
#define DEBUG_ENABLED(WHAT) (DEBUG_LEVEL_ENABLED (WHAT, 0))
624

B
Behdad Esfahbod 已提交
625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648
static inline void
_hb_print_func (const char *func)
{
  if (func)
  {
    unsigned int func_len = strlen (func);
    /* Skip "static" */
    if (0 == strncmp (func, "static ", 7))
      func += 7;
    /* Skip "typename" */
    if (0 == strncmp (func, "typename ", 9))
      func += 9;
    /* Skip return type */
    const char *space = strchr (func, ' ');
    if (space)
      func = space + 1;
    /* Skip parameter list */
    const char *paren = strchr (func, '(');
    if (paren)
      func_len = paren - func;
    fprintf (stderr, "%.*s", func_len, func);
  }
}

B
Behdad Esfahbod 已提交
649 650 651 652 653 654 655 656 657
template <int max_level> static inline void
_hb_debug_msg_va (const char *what,
		  const void *obj,
		  const char *func,
		  bool indented,
		  unsigned int level,
		  int level_dir,
		  const char *message,
		  va_list ap) HB_PRINTF_FUNC(7, 0);
658
template <int max_level> static inline void
659
_hb_debug_msg_va (const char *what,
B
Behdad Esfahbod 已提交
660 661 662 663 664 665 666
		  const void *obj,
		  const char *func,
		  bool indented,
		  unsigned int level,
		  int level_dir,
		  const char *message,
		  va_list ap)
667
{
B
Behdad Esfahbod 已提交
668
  if (!_hb_debug (level, max_level))
B
Minor  
Behdad Esfahbod 已提交
669
    return;
B
Behdad Esfahbod 已提交
670 671 672 673

  fprintf (stderr, "%-10s", what ? what : "");

  if (obj)
B
/Minor/  
Behdad Esfahbod 已提交
674
    fprintf (stderr, "(%0*lx) ", (unsigned int) (2 * sizeof (void *)), (unsigned long) obj);
B
Behdad Esfahbod 已提交
675 676 677
  else
    fprintf (stderr, " %*s  ", (unsigned int) (2 * sizeof (void *)), "");

678
  if (indented) {
679 680 681 682 683 684 685 686
/* One may want to add ASCII version of these.  See:
 * https://bugs.freedesktop.org/show_bug.cgi?id=50970 */
#define VBAR	"\342\224\202"	/* U+2502 BOX DRAWINGS LIGHT VERTICAL */
#define VRBAR	"\342\224\234"	/* U+251C BOX DRAWINGS LIGHT VERTICAL AND RIGHT */
#define DLBAR	"\342\225\256"	/* U+256E BOX DRAWINGS LIGHT ARC DOWN AND LEFT */
#define ULBAR	"\342\225\257"	/* U+256F BOX DRAWINGS LIGHT ARC UP AND LEFT */
#define LBAR	"\342\225\264"	/* U+2574 BOX DRAWINGS LIGHT LEFT */
    static const char bars[] = VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR VBAR;
687
    fprintf (stderr, "%2u %s" VRBAR "%s",
B
Behdad Esfahbod 已提交
688
	     level,
689 690
	     bars + sizeof (bars) - 1 - MIN ((unsigned int) sizeof (bars), (unsigned int) (sizeof (VBAR) - 1) * level),
	     level_dir ? (level_dir > 0 ? DLBAR : ULBAR) : LBAR);
691
  } else
692
    fprintf (stderr, "   " VRBAR LBAR);
B
Behdad Esfahbod 已提交
693

B
Behdad Esfahbod 已提交
694
  _hb_print_func (func);
B
Behdad Esfahbod 已提交
695 696

  if (message)
B
Behdad Esfahbod 已提交
697 698
  {
    fprintf (stderr, ": ");
B
Behdad Esfahbod 已提交
699
    vfprintf (stderr, message, ap);
B
Behdad Esfahbod 已提交
700
  }
B
Behdad Esfahbod 已提交
701 702

  fprintf (stderr, "\n");
703
}
B
Minor  
Behdad Esfahbod 已提交
704
template <> inline void
B
Behdad Esfahbod 已提交
705 706 707 708 709 710 711 712
_hb_debug_msg_va<0> (const char *what HB_UNUSED,
		     const void *obj HB_UNUSED,
		     const char *func HB_UNUSED,
		     bool indented HB_UNUSED,
		     unsigned int level HB_UNUSED,
		     int level_dir HB_UNUSED,
		     const char *message HB_UNUSED,
		     va_list ap HB_UNUSED) {}
713

714
template <int max_level> static inline void
715 716 717 718
_hb_debug_msg (const char *what,
	       const void *obj,
	       const char *func,
	       bool indented,
B
Behdad Esfahbod 已提交
719 720
	       unsigned int level,
	       int level_dir,
721
	       const char *message,
B
Behdad Esfahbod 已提交
722
	       ...) HB_PRINTF_FUNC(7, 8);
723
template <int max_level> static inline void
724 725 726 727
_hb_debug_msg (const char *what,
	       const void *obj,
	       const char *func,
	       bool indented,
B
Behdad Esfahbod 已提交
728 729
	       unsigned int level,
	       int level_dir,
730 731 732 733 734
	       const char *message,
	       ...)
{
  va_list ap;
  va_start (ap, message);
B
Minor  
Behdad Esfahbod 已提交
735
  _hb_debug_msg_va<max_level> (what, obj, func, indented, level, level_dir, message, ap);
736 737
  va_end (ap);
}
B
Minor  
Behdad Esfahbod 已提交
738
template <> inline void
B
Behdad Esfahbod 已提交
739 740 741 742 743 744 745
_hb_debug_msg<0> (const char *what HB_UNUSED,
		  const void *obj HB_UNUSED,
		  const char *func HB_UNUSED,
		  bool indented HB_UNUSED,
		  unsigned int level HB_UNUSED,
		  int level_dir HB_UNUSED,
		  const char *message HB_UNUSED,
B
Behdad Esfahbod 已提交
746
		  ...) HB_PRINTF_FUNC(7, 8);
B
Minor  
Behdad Esfahbod 已提交
747
template <> inline void
B
Behdad Esfahbod 已提交
748 749 750 751 752 753 754
_hb_debug_msg<0> (const char *what HB_UNUSED,
		  const void *obj HB_UNUSED,
		  const char *func HB_UNUSED,
		  bool indented HB_UNUSED,
		  unsigned int level HB_UNUSED,
		  int level_dir HB_UNUSED,
		  const char *message HB_UNUSED,
B
Minor  
Behdad Esfahbod 已提交
755
		  ...) {}
B
Behdad Esfahbod 已提交
756

757 758 759
#define DEBUG_MSG_LEVEL(WHAT, OBJ, LEVEL, LEVEL_DIR, ...)	_hb_debug_msg<HB_DEBUG_##WHAT> (#WHAT, (OBJ), NULL,    true, (LEVEL), (LEVEL_DIR), __VA_ARGS__)
#define DEBUG_MSG(WHAT, OBJ, ...) 				_hb_debug_msg<HB_DEBUG_##WHAT> (#WHAT, (OBJ), NULL,    false, 0, 0, __VA_ARGS__)
#define DEBUG_MSG_FUNC(WHAT, OBJ, ...)				_hb_debug_msg<HB_DEBUG_##WHAT> (#WHAT, (OBJ), HB_FUNC, false, 0, 0, __VA_ARGS__)
760 761


B
Minor  
Behdad Esfahbod 已提交
762 763 764 765 766
/*
 * Printer
 */

template <typename T>
B
Minor  
Behdad Esfahbod 已提交
767 768 769
struct hb_printer_t {
  const char *print (const T&) { return "something"; }
};
B
Minor  
Behdad Esfahbod 已提交
770 771 772 773 774 775 776

template <>
struct hb_printer_t<bool> {
  const char *print (bool v) { return v ? "true" : "false"; }
};

template <>
777
struct hb_printer_t<hb_void_t> {
B
Behdad Esfahbod 已提交
778
  const char *print (hb_void_t) { return ""; }
B
Minor  
Behdad Esfahbod 已提交
779 780 781
};


782 783 784 785
/*
 * Trace
 */

786 787 788 789
template <typename T>
static inline void _hb_warn_no_return (bool returned)
{
  if (unlikely (!returned)) {
B
Behdad Esfahbod 已提交
790
    fprintf (stderr, "OUCH, returned with no call to return_trace().  This is a bug, please report.\n");
791 792 793
  }
}
template <>
794
/*static*/ inline void _hb_warn_no_return<hb_void_t> (bool returned HB_UNUSED)
795 796 797
{}

template <int max_level, typename ret_t>
798 799
struct hb_auto_trace_t {
  explicit inline hb_auto_trace_t (unsigned int *plevel_,
B
Behdad Esfahbod 已提交
800 801
				   const char *what_,
				   const void *obj_,
802
				   const char *func,
803
				   const char *message,
B
Behdad Esfahbod 已提交
804
				   ...) : plevel (plevel_), what (what_), obj (obj_), returned (false)
805
  {
B
Behdad Esfahbod 已提交
806
    if (plevel) ++*plevel;
807 808 809

    va_list ap;
    va_start (ap, message);
810
    _hb_debug_msg_va<max_level> (what, obj, func, true, plevel ? *plevel : 0, +1, message, ap);
811
    va_end (ap);
812
  }
813
  inline ~hb_auto_trace_t (void)
B
Behdad Esfahbod 已提交
814
  {
815 816
    _hb_warn_no_return<ret_t> (returned);
    if (!returned) {
817
      _hb_debug_msg<max_level> (what, obj, NULL, true, plevel ? *plevel : 1, -1, " ");
818
    }
B
Behdad Esfahbod 已提交
819 820
    if (plevel) --*plevel;
  }
821

B
Behdad Esfahbod 已提交
822
  inline ret_t ret (ret_t v, unsigned int line = 0)
823 824
  {
    if (unlikely (returned)) {
B
Behdad Esfahbod 已提交
825
      fprintf (stderr, "OUCH, double calls to return_trace().  This is a bug, please report.\n");
826 827 828
      return v;
    }

829 830 831
    _hb_debug_msg<max_level> (what, obj, NULL, true, plevel ? *plevel : 1, -1,
			      "return %s (line %d)",
			      hb_printer_t<ret_t>().print (v), line);
832 833 834 835 836 837
    if (plevel) --*plevel;
    plevel = NULL;
    returned = true;
    return v;
  }

838 839
  private:
  unsigned int *plevel;
B
Behdad Esfahbod 已提交
840 841
  const char *what;
  const void *obj;
B
Behdad Esfahbod 已提交
842
  bool returned;
843
};
844 845
template <typename ret_t> /* Optimize when tracing is disabled */
struct hb_auto_trace_t<0, ret_t> {
B
Behdad Esfahbod 已提交
846 847 848 849 850
  explicit inline hb_auto_trace_t (unsigned int *plevel_ HB_UNUSED,
				   const char *what HB_UNUSED,
				   const void *obj HB_UNUSED,
				   const char *func HB_UNUSED,
				   const char *message HB_UNUSED,
851
				   ...) {}
852

B
Behdad Esfahbod 已提交
853
  inline ret_t ret (ret_t v, unsigned int line HB_UNUSED = 0) { return v; }
854 855
};

B
Behdad Esfahbod 已提交
856
#define return_trace(RET) return trace.ret (RET, __LINE__)
857 858 859

/* Misc */

B
Behdad Esfahbod 已提交
860 861
template <typename T> class hb_assert_unsigned_t;
template <> class hb_assert_unsigned_t<unsigned char> {};
862
template <> class hb_assert_unsigned_t<unsigned short> {};
B
Behdad Esfahbod 已提交
863 864
template <> class hb_assert_unsigned_t<unsigned int> {};
template <> class hb_assert_unsigned_t<unsigned long> {};
B
Behdad Esfahbod 已提交
865

B
Behdad Esfahbod 已提交
866
template <typename T> static inline bool
B
Minor  
Behdad Esfahbod 已提交
867
hb_in_range (T u, T lo, T hi)
B
Minor  
Behdad Esfahbod 已提交
868
{
869 870 871
  /* The sizeof() is here to force template instantiation.
   * I'm sure there are better ways to do this but can't think of
   * one right now.  Declaring a variable won't work as HB_UNUSED
B
Typo  
Behdad Esfahbod 已提交
872
   * is unusable on some platforms and unused types are less likely
873 874 875
   * to generate a warning than unused variables. */
  ASSERT_STATIC (sizeof (hb_assert_unsigned_t<T>) >= 0);

876 877 878
  /* The casts below are important as if T is smaller than int,
   * the subtract results will become a signed int! */
  return (T)(u - lo) <= (T)(hi - lo);
B
Minor  
Behdad Esfahbod 已提交
879 880
}

B
Behdad Esfahbod 已提交
881 882 883 884 885 886
template <typename T> static inline bool
hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2)
{
  return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2);
}

887
template <typename T> static inline bool
B
Behdad Esfahbod 已提交
888
hb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2, T lo3, T hi3)
889
{
B
Behdad Esfahbod 已提交
890
  return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2) || hb_in_range (u, lo3, hi3);
891 892
}

B
Minor  
Behdad Esfahbod 已提交
893

B
Behdad Esfahbod 已提交
894 895
/* Useful for set-operations on small enums.
 * For example, for testing "x ∈ {x1, x2, x3}" use:
896
 * (FLAG_SAFE(x) & (FLAG(x1) | FLAG(x2) | FLAG(x3)))
B
Behdad Esfahbod 已提交
897
 */
898 899
#define FLAG(x) (ASSERT_STATIC_EXPR_ZERO ((x) < 32) + (1U << (x)))
#define FLAG_SAFE(x) (1U << (x))
B
Behdad Esfahbod 已提交
900
#define FLAG_UNSAFE(x) ((x) < 32 ? FLAG_SAFE(x) : 0)
901
#define FLAG_RANGE(x,y) (ASSERT_STATIC_EXPR_ZERO ((x) < (y)) + FLAG(y+1) - FLAG(x))
B
Minor  
Behdad Esfahbod 已提交
902

B
Minor  
Behdad Esfahbod 已提交
903

B
Behdad Esfahbod 已提交
904
template <typename T, typename T2> static inline void
905
hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *), T2 *array2)
B
Behdad Esfahbod 已提交
906
{
907 908 909 910 911 912 913 914 915
  for (unsigned int i = 1; i < len; i++)
  {
    unsigned int j = i;
    while (j && compar (&array[j - 1], &array[i]) > 0)
      j--;
    if (i == j)
      continue;
    /* Move item i to occupy place for item j, shift what's in between. */
    {
B
Minor  
Behdad Esfahbod 已提交
916
      T t = array[i];
917 918 919 920 921
      memmove (&array[j + 1], &array[j], (i - j) * sizeof (T));
      array[j] = t;
    }
    if (array2)
    {
B
Minor  
Behdad Esfahbod 已提交
922
      T2 t = array2[i];
923 924 925 926
      memmove (&array2[j + 1], &array2[j], (i - j) * sizeof (T2));
      array2[j] = t;
    }
  }
B
Behdad Esfahbod 已提交
927 928
}

B
Behdad Esfahbod 已提交
929
template <typename T> static inline void
930
hb_stable_sort (T *array, unsigned int len, int(*compar)(const T *, const T *))
931
{
932
  hb_stable_sort (array, len, compar, (int *) NULL);
933
}
B
Behdad Esfahbod 已提交
934

935 936 937 938 939
static inline hb_bool_t
hb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out)
{
  /* Pain because we don't know whether s is nul-terminated. */
  char buf[64];
940 941 942
  len = MIN (ARRAY_LENGTH (buf) - 1, len);
  strncpy (buf, s, len);
  buf[len] = '\0';
943 944 945 946 947 948 949 950 951

  char *end;
  errno = 0;
  unsigned long v = strtoul (buf, &end, base);
  if (errno) return false;
  if (*end) return false;
  *out = v;
  return true;
}
B
Behdad Esfahbod 已提交
952

B
Behdad Esfahbod 已提交
953

954 955 956 957
/* Global runtime options. */

struct hb_options_t
{
B
Behdad Esfahbod 已提交
958 959
  unsigned int initialized : 1;
  unsigned int uniscribe_bug_compatible : 1;
960 961 962
};

union hb_options_union_t {
B
Behdad Esfahbod 已提交
963
  unsigned int i;
964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982
  hb_options_t opts;
};
ASSERT_STATIC (sizeof (int) == sizeof (hb_options_union_t));

HB_INTERNAL void
_hb_options_init (void);

extern HB_INTERNAL hb_options_union_t _hb_options;

static inline hb_options_t
hb_options (void)
{
  if (unlikely (!_hb_options.i))
    _hb_options_init ();

  return _hb_options.opts;
}


983
#endif /* HB_PRIVATE_HH */