164aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod/* 22409d5f8d7dd8b535ce5ea29e933f7db27d33793Behdad Esfahbod * Copyright © 2007,2008,2009 Red Hat, Inc. 30ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod * Copyright © 2011,2012 Google, Inc. 464aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * 5c755cb3e3ac55156d0d2ec05adea7a650b97cc41Behdad Esfahbod * This is part of HarfBuzz, a text shaping library. 664aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * 764aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * Permission is hereby granted, without written agreement and without 864aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * license or royalty fees, to use, copy, modify, and distribute this 964aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * software and its documentation for any purpose, provided that the 1064aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * above copyright notice and the following two paragraphs appear in 1164aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * all copies of this software. 1264aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * 1364aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 1464aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 1564aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 1664aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 1764aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * DAMAGE. 1864aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * 1964aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 2064aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 2164aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 2264aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 2364aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 2464aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * 2564aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod * Red Hat Author(s): Behdad Esfahbod 262409d5f8d7dd8b535ce5ea29e933f7db27d33793Behdad Esfahbod * Google Author(s): Behdad Esfahbod 2764aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod */ 2864aef3a54999496fd1de4f5aa5b019e4c03b3836Behdad Esfahbod 29c57d454accff66e5f2c58006e8fb40bc020b6182Behdad Esfahbod#ifndef HB_PRIVATE_HH 30c57d454accff66e5f2c58006e8fb40bc020b6182Behdad Esfahbod#define HB_PRIVATE_HH 315b3f7702a64fe0513d08a67bdb72704e46fd7cd4Behdad Esfahbod 325ddd9cc499f2470eca239ae357a5c8a3626c0809Behdad Esfahbod#ifdef HAVE_CONFIG_H 33df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#include "config.h" 34df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#endif 35c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod 36d1c9eb458c843215da8df84b596bfae51fee135bBehdad Esfahbod#include "hb.h" 37d1c9eb458c843215da8df84b596bfae51fee135bBehdad Esfahbod#define HB_H_IN 383e32cd9570fd8b09901fb790b80365ae425f681aBehdad Esfahbod#ifdef HAVE_OT 393e32cd9570fd8b09901fb790b80365ae425f681aBehdad Esfahbod#include "hb-ot.h" 40d1c9eb458c843215da8df84b596bfae51fee135bBehdad Esfahbod#define HB_OT_H_IN 413e32cd9570fd8b09901fb790b80365ae425f681aBehdad Esfahbod#endif 42b28815c1f6e46d38471cacbc31248ca6fda8c4d1Behdad Esfahbod 43c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod#include <stdlib.h> 44b65c06025d2b54a44f716e030d4b10072c65bea8Behdad Esfahbod#include <stddef.h> 45f0954d1e08ae288eda9904e17108fc73f48c0b98Behdad Esfahbod#include <string.h> 46f0954d1e08ae288eda9904e17108fc73f48c0b98Behdad Esfahbod#include <assert.h> 471d52151a19ed8ec776276aac5cc6ce3769e0d947Behdad Esfahbod 481d52151a19ed8ec776276aac5cc6ce3769e0d947Behdad Esfahbod/* We only use these two for debug output. However, the debug code is 491d52151a19ed8ec776276aac5cc6ce3769e0d947Behdad Esfahbod * always seen by the compiler (and optimized out in non-debug builds. 501d52151a19ed8ec776276aac5cc6ce3769e0d947Behdad Esfahbod * If including these becomes a problem, we can start thinking about 511d52151a19ed8ec776276aac5cc6ce3769e0d947Behdad Esfahbod * someway around that. */ 527acb389569cf99c6bae9db31a8ed7c7007fbb566Behdad Esfahbod#include <stdio.h> 537acb389569cf99c6bae9db31a8ed7c7007fbb566Behdad Esfahbod#include <errno.h> 54cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod#include <stdarg.h> 55c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod 56acdba3f90b232fc12fcb200dca2584481b339118Behdad Esfahbod 57bc200457430c083914a64bf4b056153506749610Behdad Esfahbod 58bc200457430c083914a64bf4b056153506749610Behdad Esfahbod/* Essentials */ 59bc200457430c083914a64bf4b056153506749610Behdad Esfahbod 60bc200457430c083914a64bf4b056153506749610Behdad Esfahbod#ifndef NULL 61bc200457430c083914a64bf4b056153506749610Behdad Esfahbod# define NULL ((void *) 0) 62bc200457430c083914a64bf4b056153506749610Behdad Esfahbod#endif 63bc200457430c083914a64bf4b056153506749610Behdad Esfahbod 64a794ebf4be9896393f4badf02905a4007981a588Behdad Esfahbod 65dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod/* Void! */ 665f9569c1391c65d7addff363ad6e5ec9b087f01aBehdad Esfahbodstruct _hb_void_t {}; 67130bb3f6144afe5c88bb5b4e4c98e7cba03b1e26Behdad Esfahbodtypedef const _hb_void_t &hb_void_t; 68130bb3f6144afe5c88bb5b4e4c98e7cba03b1e26Behdad Esfahbod#define HB_VOID (* (const _hb_void_t *) NULL) 69dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod 70dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod 71c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod/* Basics */ 72c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod 73153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbod 74c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod#undef MIN 7525326c2359b0a3e25222b94acd142bc36eff78a4Behdad Esfahbodtemplate <typename Type> 7625326c2359b0a3e25222b94acd142bc36eff78a4Behdad Esfahbodstatic inline Type MIN (const Type &a, const Type &b) { return a < b ? a : b; } 777586089c6fa8185cad8387869d3703c637e5cbb1Behdad Esfahbod 788a3511ac6c795226699c2b36e03401ecdf88f5f8Behdad Esfahbod#undef MAX 7925326c2359b0a3e25222b94acd142bc36eff78a4Behdad Esfahbodtemplate <typename Type> 8025326c2359b0a3e25222b94acd142bc36eff78a4Behdad Esfahbodstatic inline Type MAX (const Type &a, const Type &b) { return a > b ? a : b; } 81153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbod 828a3511ac6c795226699c2b36e03401ecdf88f5f8Behdad Esfahbod 834591753ad4b5ec0224e3f1befdfe4fc5f6075562Behdad Esfahbod#undef ARRAY_LENGTH 8425326c2359b0a3e25222b94acd142bc36eff78a4Behdad Esfahbodtemplate <typename Type, unsigned int n> 850beb66e3a61ae8bb1fa66e54b1ff1abb2f8711e9Behdad Esfahbodstatic inline unsigned int ARRAY_LENGTH (const Type (&)[n]) { return n; } 86fabd3113a98c5f4114f48920fa7ea38bd65a8d32Behdad Esfahbod/* A const version, but does not detect erratically being called on pointers. */ 87fabd3113a98c5f4114f48920fa7ea38bd65a8d32Behdad Esfahbod#define ARRAY_LENGTH_CONST(__array) ((signed int) (sizeof (__array) / sizeof (__array[0]))) 8812360f7c159826ae72271b34486dee59d96aa8caBehdad Esfahbod 8935a7383c6138fd705560f0d4bb30659cbd1ab64cBehdad Esfahbod#define HB_STMT_START do 9035a7383c6138fd705560f0d4bb30659cbd1ab64cBehdad Esfahbod#define HB_STMT_END while (0) 915b3f7702a64fe0513d08a67bdb72704e46fd7cd4Behdad Esfahbod 9273cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod#define _ASSERT_STATIC1(_line, _cond) typedef int _static_assert_on_line_##_line##_failed[(_cond)?1:-1] 9373cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod#define _ASSERT_STATIC0(_line, _cond) _ASSERT_STATIC1 (_line, (_cond)) 9473cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod#define ASSERT_STATIC(_cond) _ASSERT_STATIC0 (__LINE__, (_cond)) 95303fe62824d4e99df554b6bfaacba05d068522fbBehdad Esfahbod 9679e2b4791fe95ede9a1e6b1c71ccc6e36c4fc0e5Behdad Esfahbod#define ASSERT_STATIC_EXPR(_cond)((void) sizeof (char[(_cond) ? 1 : -1])) 974ec30aec3014be6effc09cbbc88dcd075f3826dfBehdad Esfahbod#define ASSERT_STATIC_EXPR_ZERO(_cond) (0 * sizeof (char[(_cond) ? 1 : -1])) 98dcb7026f33cbcdf60e9b7fcdd44c64cc08702c74Behdad Esfahbod 994be46bade26faf13f7b4d447e9cc608e183955dcBehdad Esfahbod#define _PASTE1(a,b) a##b 1004be46bade26faf13f7b4d447e9cc608e183955dcBehdad Esfahbod#define PASTE(a,b) _PASTE1(a,b) 101bc200457430c083914a64bf4b056153506749610Behdad Esfahbod 1026fd5364bdc3a2b459175377e9e16c86cff054232Behdad Esfahbod/* Lets assert int types. Saves trouble down the road. */ 1036fd5364bdc3a2b459175377e9e16c86cff054232Behdad Esfahbod 1046fd5364bdc3a2b459175377e9e16c86cff054232Behdad EsfahbodASSERT_STATIC (sizeof (int8_t) == 1); 1056fd5364bdc3a2b459175377e9e16c86cff054232Behdad EsfahbodASSERT_STATIC (sizeof (uint8_t) == 1); 1066fd5364bdc3a2b459175377e9e16c86cff054232Behdad EsfahbodASSERT_STATIC (sizeof (int16_t) == 2); 1076fd5364bdc3a2b459175377e9e16c86cff054232Behdad EsfahbodASSERT_STATIC (sizeof (uint16_t) == 2); 1086fd5364bdc3a2b459175377e9e16c86cff054232Behdad EsfahbodASSERT_STATIC (sizeof (int32_t) == 4); 1096fd5364bdc3a2b459175377e9e16c86cff054232Behdad EsfahbodASSERT_STATIC (sizeof (uint32_t) == 4); 1106fd5364bdc3a2b459175377e9e16c86cff054232Behdad EsfahbodASSERT_STATIC (sizeof (int64_t) == 8); 1116fd5364bdc3a2b459175377e9e16c86cff054232Behdad EsfahbodASSERT_STATIC (sizeof (uint64_t) == 8); 1126fd5364bdc3a2b459175377e9e16c86cff054232Behdad Esfahbod 113b13640de6992de9ee9d07e3581c33b8181b70ff9Behdad EsfahbodASSERT_STATIC (sizeof (hb_codepoint_t) == 4); 114b13640de6992de9ee9d07e3581c33b8181b70ff9Behdad EsfahbodASSERT_STATIC (sizeof (hb_position_t) == 4); 115b13640de6992de9ee9d07e3581c33b8181b70ff9Behdad EsfahbodASSERT_STATIC (sizeof (hb_mask_t) == 4); 116ae9eeaff9300f3bb7bed588c5478e8e5461b3df0Behdad EsfahbodASSERT_STATIC (sizeof (hb_var_int_t) == 4); 1176fd5364bdc3a2b459175377e9e16c86cff054232Behdad Esfahbod 118a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod 119a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod/* We like our types POD */ 120a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod 12173cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod#define _ASSERT_TYPE_POD1(_line, _type) union _type_##_type##_on_line_##_line##_is_not_POD { _type instance; } 12273cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod#define _ASSERT_TYPE_POD0(_line, _type) _ASSERT_TYPE_POD1 (_line, _type) 12373cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod#define ASSERT_TYPE_POD(_type) _ASSERT_TYPE_POD0 (__LINE__, _type) 124a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod 125a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod#ifdef __GNUC__ 12679e2b4791fe95ede9a1e6b1c71ccc6e36c4fc0e5Behdad Esfahbod# define _ASSERT_INSTANCE_POD1(_line, _instance) \ 12779e2b4791fe95ede9a1e6b1c71ccc6e36c4fc0e5Behdad Esfahbod HB_STMT_START { \ 12879e2b4791fe95ede9a1e6b1c71ccc6e36c4fc0e5Behdad Esfahbod typedef __typeof__(_instance) _type_##_line; \ 12979e2b4791fe95ede9a1e6b1c71ccc6e36c4fc0e5Behdad Esfahbod _ASSERT_TYPE_POD1 (_line, _type_##_line); \ 13079e2b4791fe95ede9a1e6b1c71ccc6e36c4fc0e5Behdad Esfahbod } HB_STMT_END 131a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod#else 13273cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod# define _ASSERT_INSTANCE_POD1(_line, _instance) typedef int _assertion_on_line_##_line##_not_tested 133a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod#endif 13473cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod# define _ASSERT_INSTANCE_POD0(_line, _instance) _ASSERT_INSTANCE_POD1 (_line, _instance) 13573cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod# define ASSERT_INSTANCE_POD(_instance) _ASSERT_INSTANCE_POD0 (__LINE__, _instance) 136a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod 137a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod/* Check _assertion in a method environment */ 138a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod#define _ASSERT_POD1(_line) \ 13973cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod inline void _static_assertion_on_line_##_line (void) const \ 14073cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod { _ASSERT_INSTANCE_POD1 (_line, *this); /* Make sure it's POD. */ } 14173cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod# define _ASSERT_POD0(_line) _ASSERT_POD1 (_line) 14273cb02de2dd28b09d4aa76230132248215cfe83dBehdad Esfahbod# define ASSERT_POD() _ASSERT_POD0 (__LINE__) 143a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod 144a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod 145a00a63b5ef503fafa87e26b517732b2214e01719Behdad Esfahbod 146bc200457430c083914a64bf4b056153506749610Behdad Esfahbod/* Misc */ 147bc200457430c083914a64bf4b056153506749610Behdad Esfahbod 148c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod 149df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#if defined(__GNUC__) && (__GNUC__ > 2) && defined(__OPTIMIZE__) 150494d28ad988e505c1c45cc35a7ec6b880cfec5fcBehdad Esfahbod#define _HB_BOOLEAN_EXPR(expr) ((expr) ? 1 : 0) 15164d3fc8d0dada673245cc8c0b1c12cd849b30997Behdad Esfahbod#define likely(expr) (__builtin_expect (_HB_BOOLEAN_EXPR(expr), 1)) 15264d3fc8d0dada673245cc8c0b1c12cd849b30997Behdad Esfahbod#define unlikely(expr) (__builtin_expect (_HB_BOOLEAN_EXPR(expr), 0)) 153df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#else 15464d3fc8d0dada673245cc8c0b1c12cd849b30997Behdad Esfahbod#define likely(expr) (expr) 15564d3fc8d0dada673245cc8c0b1c12cd849b30997Behdad Esfahbod#define unlikely(expr) (expr) 156df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#endif 157df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod 158df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#ifndef __GNUC__ 159df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#undef __attribute__ 160df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#define __attribute__(x) 161df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#endif 162df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod 163df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#if __GNUC__ >= 3 16433d13fdda99acaeffa9600737e8870278d053ebeBehdad Esfahbod#define HB_PURE_FUNC __attribute__((pure)) 16533d13fdda99acaeffa9600737e8870278d053ebeBehdad Esfahbod#define HB_CONST_FUNC __attribute__((const)) 166cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod#define HB_PRINTF_FUNC(format_idx, arg_idx) __attribute__((__format__ (__printf__, format_idx, arg_idx))) 167df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#else 16833d13fdda99acaeffa9600737e8870278d053ebeBehdad Esfahbod#define HB_PURE_FUNC 16933d13fdda99acaeffa9600737e8870278d053ebeBehdad Esfahbod#define HB_CONST_FUNC 17044b4f50d05fd51d8056a78e359fbb00fbcac43a0Behdad Esfahbod#define HB_PRINTF_FUNC(format_idx, arg_idx) 171df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#endif 172bc7830e4259755ce7549025c6f5bf750e78c2ff1Behdad Esfahbod#if __GNUC__ >= 4 17333d13fdda99acaeffa9600737e8870278d053ebeBehdad Esfahbod#define HB_UNUSED __attribute__((unused)) 174bc7830e4259755ce7549025c6f5bf750e78c2ff1Behdad Esfahbod#else 17533d13fdda99acaeffa9600737e8870278d053ebeBehdad Esfahbod#define HB_UNUSED 176bc7830e4259755ce7549025c6f5bf750e78c2ff1Behdad Esfahbod#endif 177df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod 178eee8598d75d3af692d9ececf7e8ac458e892ba9eBehdad Esfahbod#ifndef HB_INTERNAL 179f60271c0c2b0101e7b2725f9a9ad950c277a616cBehdad Esfahbod# ifndef __MINGW32__ 180f60271c0c2b0101e7b2725f9a9ad950c277a616cBehdad Esfahbod# define HB_INTERNAL __attribute__((__visibility__("hidden"))) 181f60271c0c2b0101e7b2725f9a9ad950c277a616cBehdad Esfahbod# else 182f60271c0c2b0101e7b2725f9a9ad950c277a616cBehdad Esfahbod# define HB_INTERNAL 183f60271c0c2b0101e7b2725f9a9ad950c277a616cBehdad Esfahbod# endif 184eee8598d75d3af692d9ececf7e8ac458e892ba9eBehdad Esfahbod#endif 185eee8598d75d3af692d9ececf7e8ac458e892ba9eBehdad Esfahbod 186df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod 187df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#if (defined(__WIN32__) && !defined(__WINE__)) || defined(_MSC_VER) 188df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#define snprintf _snprintf 189df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#endif 190df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod 191df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#ifdef _MSC_VER 192df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#undef inline 193df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#define inline __inline 194df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#endif 195df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod 196df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#ifdef __STRICT_ANSI__ 197df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#undef inline 198df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#define inline __inline__ 199df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod#endif 200df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod 201df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod 2027d3a126334f8e6f6441561c1bb592bd3fa7a2c5cBehdad Esfahbod#if __GNUC__ >= 3 2037d3a126334f8e6f6441561c1bb592bd3fa7a2c5cBehdad Esfahbod#define HB_FUNC __PRETTY_FUNCTION__ 2047d3a126334f8e6f6441561c1bb592bd3fa7a2c5cBehdad Esfahbod#elif defined(_MSC_VER) 2057d3a126334f8e6f6441561c1bb592bd3fa7a2c5cBehdad Esfahbod#define HB_FUNC __FUNCSIG__ 2067d3a126334f8e6f6441561c1bb592bd3fa7a2c5cBehdad Esfahbod#else 2077d3a126334f8e6f6441561c1bb592bd3fa7a2c5cBehdad Esfahbod#define HB_FUNC __func__ 2087d3a126334f8e6f6441561c1bb592bd3fa7a2c5cBehdad Esfahbod#endif 2097d3a126334f8e6f6441561c1bb592bd3fa7a2c5cBehdad Esfahbod 2107d3a126334f8e6f6441561c1bb592bd3fa7a2c5cBehdad Esfahbod 2119b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod/* Return the number of 1 bits in mask. */ 21297e7f8f305c47caf2968a9da3b8407825547286dBehdad Esfahbodstatic inline HB_CONST_FUNC unsigned int 213c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod_hb_popcount32 (uint32_t mask) 214c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod{ 215c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod#if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4) 2169b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod return __builtin_popcount (mask); 217c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod#else 2189b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod /* "HACKMEM 169" */ 2199b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod register uint32_t y; 2209b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod y = (mask >> 1) &033333333333; 2219b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod y = mask - y - ((y >>1) & 033333333333); 2229b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod return (((y + (y >> 3)) & 030707070707) % 077); 223c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod#endif 224c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod} 225c7d457aa3ae7138630f52ca7263f663a3ea284c0Behdad Esfahbod 2269b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod/* Returns the number of bits needed to store number */ 2279b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbodstatic inline HB_CONST_FUNC unsigned int 2289b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod_hb_bit_storage (unsigned int number) 2299b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod{ 2309b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__) 231f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod return likely (number) ? (sizeof (unsigned int) * 8 - __builtin_clz (number)) : 0; 2329b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod#else 2339b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod register unsigned int n_bits = 0; 2349b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod while (number) { 2359b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod n_bits++; 2369b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod number >>= 1; 2379b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod } 2389b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod return n_bits; 2399b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod#endif 2409b6023338530a2dbb8214eb4391ef3e8372f3892Behdad Esfahbod} 241df66028781a7609a515980e64396e6f1044d764aBehdad Esfahbod 242f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod/* Returns the number of zero bits in the least significant side of number */ 243f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbodstatic inline HB_CONST_FUNC unsigned int 244f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod_hb_ctz (unsigned int number) 245f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod{ 246f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod#if defined(__GNUC__) && (__GNUC__ >= 4) && defined(__OPTIMIZE__) 247f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod return likely (number) ? __builtin_ctz (number) : 0; 248f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod#else 249f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod register unsigned int n_bits = 0; 250f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod if (unlikely (!number)) return 0; 251f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod while (!(number & 1)) { 252f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod n_bits++; 253f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod number >>= 1; 254f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod } 255f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod return n_bits; 256f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod#endif 257f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod} 258f7acd8df5146155b51d6f50aeb04f54f3030c1c3Behdad Esfahbod 259080a0eb7d82d7195be72c16ece6e0a3ffed636b6Behdad Esfahbodstatic inline bool 260080a0eb7d82d7195be72c16ece6e0a3ffed636b6Behdad Esfahbod_hb_unsigned_int_mul_overflows (unsigned int count, unsigned int size) 261080a0eb7d82d7195be72c16ece6e0a3ffed636b6Behdad Esfahbod{ 262080a0eb7d82d7195be72c16ece6e0a3ffed636b6Behdad Esfahbod return (size > 0) && (count >= ((unsigned int) -1) / size); 263080a0eb7d82d7195be72c16ece6e0a3ffed636b6Behdad Esfahbod} 264080a0eb7d82d7195be72c16ece6e0a3ffed636b6Behdad Esfahbod 265080a0eb7d82d7195be72c16ece6e0a3ffed636b6Behdad Esfahbod 2668f08c3275040870a645ef034a38d30c05c619f21Behdad Esfahbod/* Type of bsearch() / qsort() compare function */ 2678f08c3275040870a645ef034a38d30c05c619f21Behdad Esfahbodtypedef int (*hb_compare_func_t) (const void *, const void *); 2688f08c3275040870a645ef034a38d30c05c619f21Behdad Esfahbod 2698f08c3275040870a645ef034a38d30c05c619f21Behdad Esfahbod 270852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod 271852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod 272852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod/* arrays and maps */ 273852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod 274852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod 2750e253e97af71e2a7ead153589f61fd579a247502Behdad Esfahbod#define HB_PREALLOCED_ARRAY_INIT {0} 276852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbodtemplate <typename Type, unsigned int StaticSize> 2770e253e97af71e2a7ead153589f61fd579a247502Behdad Esfahbodstruct hb_prealloced_array_t 2780e253e97af71e2a7ead153589f61fd579a247502Behdad Esfahbod{ 279852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod unsigned int len; 280852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod unsigned int allocated; 281852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod Type *array; 282852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod Type static_array[StaticSize]; 283852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod 284bf93b636c4963cbc32d5fba7ace1053db6719192Behdad Esfahbod void init (void) { memset (this, 0, sizeof (*this)); } 285efde8113258b117ec0a7fbffe6d681442d045c41Behdad Esfahbod 286265ac614ea6d26041c7d64739098b76a82bbc4f4Behdad Esfahbod inline Type& operator [] (unsigned int i) { return array[i]; } 287265ac614ea6d26041c7d64739098b76a82bbc4f4Behdad Esfahbod inline const Type& operator [] (unsigned int i) const { return array[i]; } 288852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod 289852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod inline Type *push (void) 290852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod { 291852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod if (!array) { 292852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod array = static_array; 293852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod allocated = ARRAY_LENGTH (static_array); 294852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod } 295852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod if (likely (len < allocated)) 296852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod return &array[len++]; 2975a5030366e40baa8d96ca67b47a52ad5af143157Behdad Esfahbod 298852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod /* Need to reallocate */ 299852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod unsigned int new_allocated = allocated + (allocated >> 1) + 8; 3005a5030366e40baa8d96ca67b47a52ad5af143157Behdad Esfahbod Type *new_array = NULL; 3015a5030366e40baa8d96ca67b47a52ad5af143157Behdad Esfahbod 302852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod if (array == static_array) { 303852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod new_array = (Type *) calloc (new_allocated, sizeof (Type)); 3045a5030366e40baa8d96ca67b47a52ad5af143157Behdad Esfahbod if (new_array) 305852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod memcpy (new_array, array, len * sizeof (Type)); 306852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod } else { 307080a0eb7d82d7195be72c16ece6e0a3ffed636b6Behdad Esfahbod bool overflows = (new_allocated < allocated) || _hb_unsigned_int_mul_overflows (new_allocated, sizeof (Type)); 3085a5030366e40baa8d96ca67b47a52ad5af143157Behdad Esfahbod if (likely (!overflows)) { 309852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod new_array = (Type *) realloc (array, new_allocated * sizeof (Type)); 310852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod } 311852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod } 3125a5030366e40baa8d96ca67b47a52ad5af143157Behdad Esfahbod 3135a5030366e40baa8d96ca67b47a52ad5af143157Behdad Esfahbod if (unlikely (!new_array)) 314852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod return NULL; 3155a5030366e40baa8d96ca67b47a52ad5af143157Behdad Esfahbod 3165a5030366e40baa8d96ca67b47a52ad5af143157Behdad Esfahbod array = new_array; 3175a5030366e40baa8d96ca67b47a52ad5af143157Behdad Esfahbod allocated = new_allocated; 3185a5030366e40baa8d96ca67b47a52ad5af143157Behdad Esfahbod return &array[len++]; 319852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod } 320852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod 321852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod inline void pop (void) 322852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod { 323852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod len--; 324852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod /* TODO: shrink array if needed */ 325852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod } 32644b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod 32744b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod inline void shrink (unsigned int l) 32844b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod { 32944b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod if (l < len) 33044b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod len = l; 33144b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod /* TODO: shrink array if needed */ 33244b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod } 33344b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod 3346843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod template <typename T> 3356843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod inline Type *find (T v) { 3366843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod for (unsigned int i = 0; i < len; i++) 3376843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod if (array[i] == v) 3386843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod return &array[i]; 3396843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod return NULL; 3406843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod } 3416843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod template <typename T> 3426843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod inline const Type *find (T v) const { 3436843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod for (unsigned int i = 0; i < len; i++) 3446843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod if (array[i] == v) 3456843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod return &array[i]; 3466843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod return NULL; 3476843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod } 3486843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod 34944b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod inline void sort (void) 35044b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod { 35144b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod qsort (array, len, sizeof (Type), (hb_compare_func_t) Type::cmp); 35244b0a4d2fc62689fc56ef57f412b4bb1e439a614Behdad Esfahbod } 3536843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod 354b70c96dbe41d6512b80fe3d966a1942e1ef64a4bBehdad Esfahbod inline void sort (unsigned int start, unsigned int end) 355b70c96dbe41d6512b80fe3d966a1942e1ef64a4bBehdad Esfahbod { 356b70c96dbe41d6512b80fe3d966a1942e1ef64a4bBehdad Esfahbod qsort (array + start, end - start, sizeof (Type), (hb_compare_func_t) Type::cmp); 357b70c96dbe41d6512b80fe3d966a1942e1ef64a4bBehdad Esfahbod } 358b70c96dbe41d6512b80fe3d966a1942e1ef64a4bBehdad Esfahbod 3596843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod template <typename T> 3606843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod inline Type *bsearch (T *key) 3616843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod { 3626843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod return (Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp); 3636843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod } 3646843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod template <typename T> 3656843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod inline const Type *bsearch (T *key) const 3666843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod { 3676843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod return (const Type *) ::bsearch (key, array, len, sizeof (Type), (hb_compare_func_t) Type::cmp); 3686843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod } 3696a7ac79e26e85f6781186cf708a12825c0857324Behdad Esfahbod 3706a7ac79e26e85f6781186cf708a12825c0857324Behdad Esfahbod inline void finish (void) 3716a7ac79e26e85f6781186cf708a12825c0857324Behdad Esfahbod { 3726a7ac79e26e85f6781186cf708a12825c0857324Behdad Esfahbod if (array != static_array) 3736a7ac79e26e85f6781186cf708a12825c0857324Behdad Esfahbod free (array); 3746a7ac79e26e85f6781186cf708a12825c0857324Behdad Esfahbod array = NULL; 3756a7ac79e26e85f6781186cf708a12825c0857324Behdad Esfahbod allocated = len = 0; 3766a7ac79e26e85f6781186cf708a12825c0857324Behdad Esfahbod } 377852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod}; 378852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod 379c5d91f39802078fc6f6de71940739ec4d04eca07Behdad Esfahbod#define HB_AUTO_ARRAY_PREALLOCED 64 380c5d91f39802078fc6f6de71940739ec4d04eca07Behdad Esfahbodtemplate <typename Type> 381c5d91f39802078fc6f6de71940739ec4d04eca07Behdad Esfahbodstruct hb_auto_array_t : hb_prealloced_array_t <Type, HB_AUTO_ARRAY_PREALLOCED> 382c5d91f39802078fc6f6de71940739ec4d04eca07Behdad Esfahbod{ 383c5d91f39802078fc6f6de71940739ec4d04eca07Behdad Esfahbod hb_auto_array_t (void) { hb_prealloced_array_t<Type, HB_AUTO_ARRAY_PREALLOCED>::init (); } 384c5d91f39802078fc6f6de71940739ec4d04eca07Behdad Esfahbod ~hb_auto_array_t (void) { hb_prealloced_array_t<Type, HB_AUTO_ARRAY_PREALLOCED>::finish (); } 385c5d91f39802078fc6f6de71940739ec4d04eca07Behdad Esfahbod}; 386c5d91f39802078fc6f6de71940739ec4d04eca07Behdad Esfahbod 387a9f24c802956d57180d71b83e96a0fb81197df4aBehdad Esfahbod 3880e253e97af71e2a7ead153589f61fd579a247502Behdad Esfahbod#define HB_LOCKABLE_SET_INIT {HB_PREALLOCED_ARRAY_INIT} 38945bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbodtemplate <typename item_t, typename lock_t> 39045bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbodstruct hb_lockable_set_t 391852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod{ 3920e253e97af71e2a7ead153589f61fd579a247502Behdad Esfahbod hb_prealloced_array_t <item_t, 2> items; 393852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod 394bf93b636c4963cbc32d5fba7ace1053db6719192Behdad Esfahbod inline void init (void) { items.init (); } 395bf93b636c4963cbc32d5fba7ace1053db6719192Behdad Esfahbod 396478a42536ff7ab777a7774fbfdb9c5e51334a14eBehdad Esfahbod template <typename T> 39733ccc77902660ed4b49184e5ec99f4fd0ef63175Behdad Esfahbod inline item_t *replace_or_insert (T v, lock_t &l, bool replace) 398852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod { 39945bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.lock (); 4006843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod item_t *item = items.find (v); 40145bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod if (item) { 40233ccc77902660ed4b49184e5ec99f4fd0ef63175Behdad Esfahbod if (replace) { 40333ccc77902660ed4b49184e5ec99f4fd0ef63175Behdad Esfahbod item_t old = *item; 40433ccc77902660ed4b49184e5ec99f4fd0ef63175Behdad Esfahbod *item = v; 40533ccc77902660ed4b49184e5ec99f4fd0ef63175Behdad Esfahbod l.unlock (); 40633ccc77902660ed4b49184e5ec99f4fd0ef63175Behdad Esfahbod old.finish (); 40733ccc77902660ed4b49184e5ec99f4fd0ef63175Behdad Esfahbod } 40833ccc77902660ed4b49184e5ec99f4fd0ef63175Behdad Esfahbod else { 40933ccc77902660ed4b49184e5ec99f4fd0ef63175Behdad Esfahbod item = NULL; 41033ccc77902660ed4b49184e5ec99f4fd0ef63175Behdad Esfahbod l.unlock (); 41133ccc77902660ed4b49184e5ec99f4fd0ef63175Behdad Esfahbod } 41245bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod } else { 413852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod item = items.push (); 41445bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod if (likely (item)) 41545bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod *item = v; 41645bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.unlock (); 41745bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod } 418b45f32ee4e599c515ce93e44315283d236b073bbBehdad Esfahbod return item; 419852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod } 420852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod 421811482bd650fb5652a9835471ae8ecf0fb185611Behdad Esfahbod template <typename T> 42245bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod inline void remove (T v, lock_t &l) 423852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod { 42445bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.lock (); 4256843569d2c70c1771ce964e3d1a4cf91e14e7687Behdad Esfahbod item_t *item = items.find (v); 42645bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod if (item) { 42745bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod item_t old = *item; 42845bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod *item = items[items.len - 1]; 42945bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod items.pop (); 43045bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.unlock (); 43145bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod old.finish (); 43245bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod } else { 43345bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.unlock (); 43445bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod } 435852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod } 436a9f24c802956d57180d71b83e96a0fb81197df4aBehdad Esfahbod 437478a42536ff7ab777a7774fbfdb9c5e51334a14eBehdad Esfahbod template <typename T> 43845bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod inline bool find (T v, item_t *i, lock_t &l) 439852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod { 44045bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.lock (); 44145bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod item_t *item = items.find (v); 44245bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod if (item) 44345bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod *i = *item; 44445bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.unlock (); 44545bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod return !!item; 446811482bd650fb5652a9835471ae8ecf0fb185611Behdad Esfahbod } 447811482bd650fb5652a9835471ae8ecf0fb185611Behdad Esfahbod 448b45f32ee4e599c515ce93e44315283d236b073bbBehdad Esfahbod template <typename T> 44945bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod inline item_t *find_or_insert (T v, lock_t &l) 45045bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod { 45145bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.lock (); 45245bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod item_t *item = items.find (v); 453b45f32ee4e599c515ce93e44315283d236b073bbBehdad Esfahbod if (!item) { 454b45f32ee4e599c515ce93e44315283d236b073bbBehdad Esfahbod item = items.push (); 455b45f32ee4e599c515ce93e44315283d236b073bbBehdad Esfahbod if (likely (item)) 456b45f32ee4e599c515ce93e44315283d236b073bbBehdad Esfahbod *item = v; 457b45f32ee4e599c515ce93e44315283d236b073bbBehdad Esfahbod } 45845bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.unlock (); 459b45f32ee4e599c515ce93e44315283d236b073bbBehdad Esfahbod return item; 460b45f32ee4e599c515ce93e44315283d236b073bbBehdad Esfahbod } 461b45f32ee4e599c515ce93e44315283d236b073bbBehdad Esfahbod 46245bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod inline void finish (lock_t &l) 46345bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod { 4643f4764bb56bb7e42ba8859f1905810bd2f998838Behdad Esfahbod if (!items.len) { 4653f4764bb56bb7e42ba8859f1905810bd2f998838Behdad Esfahbod /* No need for locking. */ 4663f4764bb56bb7e42ba8859f1905810bd2f998838Behdad Esfahbod items.finish (); 4673f4764bb56bb7e42ba8859f1905810bd2f998838Behdad Esfahbod return; 4683f4764bb56bb7e42ba8859f1905810bd2f998838Behdad Esfahbod } 46945bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.lock (); 47045bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod while (items.len) { 47145bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod item_t old = items[items.len - 1]; 47245bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod items.pop (); 47345bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.unlock (); 47445bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod old.finish (); 47545bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.lock (); 47645bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod } 4776a7ac79e26e85f6781186cf708a12825c0857324Behdad Esfahbod items.finish (); 47845bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod l.unlock (); 47945bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod } 48045bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod 48145bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod}; 48245bfa99034512e886d75b1d45a5a649647f4711fBehdad Esfahbod 483852e08ec8fbfbce1d50e571d0bb0b52ef4d4cc58Behdad Esfahbod 484a9f24c802956d57180d71b83e96a0fb81197df4aBehdad Esfahbod 485a9f24c802956d57180d71b83e96a0fb81197df4aBehdad Esfahbod 486f60f2166c48d07f556ff83f04e95181946eb03dfBehdad Esfahbod/* Big-endian handling */ 487f60f2166c48d07f556ff83f04e95181946eb03dfBehdad Esfahbod 488153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbodstatic inline uint16_t hb_be_uint16 (const uint16_t v) 489153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbod{ 490153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbod const uint8_t *V = (const uint8_t *) &v; 491fcd6f5326166e993b8f5222efbaffe916da98f0aBehdad Esfahbod return (V[0] << 8) | V[1]; 492fcd6f5326166e993b8f5222efbaffe916da98f0aBehdad Esfahbod} 493fcd6f5326166e993b8f5222efbaffe916da98f0aBehdad Esfahbod 494fcd6f5326166e993b8f5222efbaffe916da98f0aBehdad Esfahbodstatic inline uint16_t hb_uint16_swap (const uint16_t v) 495fcd6f5326166e993b8f5222efbaffe916da98f0aBehdad Esfahbod{ 496fcd6f5326166e993b8f5222efbaffe916da98f0aBehdad Esfahbod return (v >> 8) | (v << 8); 497fcd6f5326166e993b8f5222efbaffe916da98f0aBehdad Esfahbod} 498fcd6f5326166e993b8f5222efbaffe916da98f0aBehdad Esfahbod 499fcd6f5326166e993b8f5222efbaffe916da98f0aBehdad Esfahbodstatic inline uint32_t hb_uint32_swap (const uint32_t v) 500fcd6f5326166e993b8f5222efbaffe916da98f0aBehdad Esfahbod{ 501fcd6f5326166e993b8f5222efbaffe916da98f0aBehdad Esfahbod return (hb_uint16_swap (v) << 16) | hb_uint16_swap (v >> 16); 502153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbod} 5037a52f281178867379adb6e6c6fb0022102f75d17Behdad Esfahbod 504e74616b8898b5f18d9bf82b9e81aefad056c1e36Behdad Esfahbod/* Note, of the following macros, uint16_get is the one called many many times. 505e74616b8898b5f18d9bf82b9e81aefad056c1e36Behdad Esfahbod * If there is any optimizations to be done, it's in that macro. However, I 506e74616b8898b5f18d9bf82b9e81aefad056c1e36Behdad Esfahbod * already confirmed that on my T400 ThinkPad at least, using bswap_16(), which 507e74616b8898b5f18d9bf82b9e81aefad056c1e36Behdad Esfahbod * results in a single ror instruction, does NOT speed this up. In fact, it 508e74616b8898b5f18d9bf82b9e81aefad056c1e36Behdad Esfahbod * resulted in a minor slowdown. At any rate, note that v may not be correctly 509e74616b8898b5f18d9bf82b9e81aefad056c1e36Behdad Esfahbod * aligned, so I think the current implementation is optimal. 510e74616b8898b5f18d9bf82b9e81aefad056c1e36Behdad Esfahbod */ 511e74616b8898b5f18d9bf82b9e81aefad056c1e36Behdad Esfahbod 512e032ed9f75d4a0f365649a25706871bbb5ae6651Behdad Esfahbod#define hb_be_uint16_put(v,V) HB_STMT_START { v[0] = (V>>8); v[1] = (V); } HB_STMT_END 5137a52f281178867379adb6e6c6fb0022102f75d17Behdad Esfahbod#define hb_be_uint16_get(v) (uint16_t) ((v[0] << 8) + v[1]) 514153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbod#define hb_be_uint16_eq(a,b) (a[0] == b[0] && a[1] == b[1]) 5157a52f281178867379adb6e6c6fb0022102f75d17Behdad Esfahbod 516e032ed9f75d4a0f365649a25706871bbb5ae6651Behdad Esfahbod#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 5177a52f281178867379adb6e6c6fb0022102f75d17Behdad Esfahbod#define hb_be_uint32_get(v) (uint32_t) ((v[0] << 24) + (v[1] << 16) + (v[2] << 8) + v[3]) 518153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbod#define hb_be_uint32_eq(a,b) (a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3]) 519f60f2166c48d07f556ff83f04e95181946eb03dfBehdad Esfahbod 520bd61bc13ea8ff350ada5449b2cfeb612e66ecafaBehdad Esfahbod#define hb_be_uint24_put(v,V) HB_STMT_START { v[0] = (V>>16); v[1] = (V>>8); v[2] (V); } HB_STMT_END 521bd61bc13ea8ff350ada5449b2cfeb612e66ecafaBehdad Esfahbod#define hb_be_uint24_get(v) (uint32_t) ((v[0] << 16) + (v[1] << 8) + v[2]) 522bd61bc13ea8ff350ada5449b2cfeb612e66ecafaBehdad Esfahbod#define hb_be_uint24_eq(a,b) (a[0] == b[0] && a[1] == b[1] && a[2] == b[2]) 523bd61bc13ea8ff350ada5449b2cfeb612e66ecafaBehdad Esfahbod 524f60f2166c48d07f556ff83f04e95181946eb03dfBehdad Esfahbod 5254188096a7722f09ffa9319986c0286071da10a27Behdad Esfahbod/* ASCII tag/character handling */ 526db5227c40e5c35fe2ffb750f32b639cb44424a1dBehdad Esfahbod 52720b817ac21147e0a8edbf23ef071c2f4ce6c2b95Behdad Esfahbodstatic inline bool ISALPHA (unsigned char c) 528153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbod{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'); } 52920b817ac21147e0a8edbf23ef071c2f4ce6c2b95Behdad Esfahbodstatic inline bool ISALNUM (unsigned char c) 530153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbod{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'); } 53120b817ac21147e0a8edbf23ef071c2f4ce6c2b95Behdad Esfahbodstatic inline bool ISSPACE (unsigned char c) 53220b817ac21147e0a8edbf23ef071c2f4ce6c2b95Behdad Esfahbod{ return c == ' ' || c =='\f'|| c =='\n'|| c =='\r'|| c =='\t'|| c =='\v'; } 533153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbodstatic inline unsigned char TOUPPER (unsigned char c) 534153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbod{ return (c >= 'a' && c <= 'z') ? c - 'a' + 'A' : c; } 535153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbodstatic inline unsigned char TOLOWER (unsigned char c) 536153142dac8dd9abaf164bb88af07c600c17fc3a1Behdad Esfahbod{ return (c >= 'A' && c <= 'Z') ? c - 'A' + 'a' : c; } 537db5227c40e5c35fe2ffb750f32b639cb44424a1dBehdad Esfahbod 5384188096a7722f09ffa9319986c0286071da10a27Behdad Esfahbod#define HB_TAG_CHAR4(s) (HB_TAG(((const char *) s)[0], \ 5394188096a7722f09ffa9319986c0286071da10a27Behdad Esfahbod ((const char *) s)[1], \ 5404188096a7722f09ffa9319986c0286071da10a27Behdad Esfahbod ((const char *) s)[2], \ 5414188096a7722f09ffa9319986c0286071da10a27Behdad Esfahbod ((const char *) s)[3])) 5424188096a7722f09ffa9319986c0286071da10a27Behdad Esfahbod 543db5227c40e5c35fe2ffb750f32b639cb44424a1dBehdad Esfahbod 544831886a9b4073cfe27f7e1db0e957cbd5913fd31Behdad Esfahbod/* C++ helpers */ 545831886a9b4073cfe27f7e1db0e957cbd5913fd31Behdad Esfahbod 546831886a9b4073cfe27f7e1db0e957cbd5913fd31Behdad Esfahbod/* Makes class uncopyable. Use in private: section. */ 547831886a9b4073cfe27f7e1db0e957cbd5913fd31Behdad Esfahbod#define NO_COPY(T) \ 548831886a9b4073cfe27f7e1db0e957cbd5913fd31Behdad Esfahbod T (const T &o); \ 549970e092dc23cbeb7897d4c7bb58c042209f518fbBehdad Esfahbod T &operator = (const T &o) 550831886a9b4073cfe27f7e1db0e957cbd5913fd31Behdad Esfahbod 551831886a9b4073cfe27f7e1db0e957cbd5913fd31Behdad Esfahbod 552bc200457430c083914a64bf4b056153506749610Behdad Esfahbod/* Debug */ 553bc200457430c083914a64bf4b056153506749610Behdad Esfahbod 554cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod 555bc200457430c083914a64bf4b056153506749610Behdad Esfahbod#ifndef HB_DEBUG 556bc200457430c083914a64bf4b056153506749610Behdad Esfahbod#define HB_DEBUG 0 557bc200457430c083914a64bf4b056153506749610Behdad Esfahbod#endif 558bc200457430c083914a64bf4b056153506749610Behdad Esfahbod 559cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbodstatic inline bool 560cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod_hb_debug (unsigned int level, 561cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod unsigned int max_level) 562cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod{ 563cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod return level < max_level; 564cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod} 565cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod 566cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod#define DEBUG_LEVEL(WHAT, LEVEL) (_hb_debug ((LEVEL), HB_DEBUG_##WHAT)) 56743ff203d8ea3e1b09e316e3aae1a4e5ec15bfdd2Behdad Esfahbod#define DEBUG(WHAT) (DEBUG_LEVEL (WHAT, 0)) 56843ff203d8ea3e1b09e316e3aae1a4e5ec15bfdd2Behdad Esfahbod 5692d1dcb3ce3354c2d5e2b4d1d291beb8d23cdea22Behdad Esfahbodtemplate <int max_level> static inline void 570208109703c929428c684ddcf9310b8ba780c4c31Behdad Esfahbod_hb_debug_msg_va (const char *what, 5711e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod const void *obj, 5721e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod const char *func, 5731e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod bool indented, 5741e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod unsigned int level, 5751e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod int level_dir, 5761e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod const char *message, 5771e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod va_list ap) 578208109703c929428c684ddcf9310b8ba780c4c31Behdad Esfahbod{ 5796eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod if (!_hb_debug (level, max_level)) 580829e814ff358c5e700ba4df54932696801aa9f65Behdad Esfahbod return; 5816eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod 5826eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod fprintf (stderr, "%-10s", what ? what : ""); 5836eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod 5846eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod if (obj) 5855ccfe8e2154ad0b58dabcc236bbe9478c17b02abBehdad Esfahbod fprintf (stderr, "(%0*lx) ", (unsigned int) (2 * sizeof (void *)), (unsigned long) obj); 5866eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod else 5876eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod fprintf (stderr, " %*s ", (unsigned int) (2 * sizeof (void *)), ""); 5886eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod 589d7bba01a353efc7432c474dd8755a02db4abd2aeBehdad Esfahbod if (indented) { 5906932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod/* One may want to add ASCII version of these. See: 5916932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod * https://bugs.freedesktop.org/show_bug.cgi?id=50970 */ 5926932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod#define VBAR "\342\224\202" /* U+2502 BOX DRAWINGS LIGHT VERTICAL */ 5936932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod#define VRBAR "\342\224\234" /* U+251C BOX DRAWINGS LIGHT VERTICAL AND RIGHT */ 5946932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod#define DLBAR "\342\225\256" /* U+256E BOX DRAWINGS LIGHT ARC DOWN AND LEFT */ 5956932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod#define ULBAR "\342\225\257" /* U+256F BOX DRAWINGS LIGHT ARC UP AND LEFT */ 5966932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod#define LBAR "\342\225\264" /* U+2574 BOX DRAWINGS LIGHT LEFT */ 5976932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod 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; 5986932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod fprintf (stderr, "%2d %s" VRBAR "%s", 5996eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod level, 6006932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod bars + sizeof (bars) - 1 - MIN ((unsigned int) sizeof (bars), (unsigned int) (sizeof (VBAR) - 1) * level), 6016932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod level_dir ? (level_dir > 0 ? DLBAR : ULBAR) : LBAR); 602d7bba01a353efc7432c474dd8755a02db4abd2aeBehdad Esfahbod } else 6036932a41fb61ffc2901c260587b1e98ed9c2a7ea1Behdad Esfahbod fprintf (stderr, " " VRBAR LBAR); 6046eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod 605adf7758a27a11fb1a8a14a2673867589437d22a3Behdad Esfahbod if (func) 606adf7758a27a11fb1a8a14a2673867589437d22a3Behdad Esfahbod { 60729ff25481584e20a2fa39195f295c8eb4bf3bad0Behdad Esfahbod unsigned int func_len = strlen (func); 60829ff25481584e20a2fa39195f295c8eb4bf3bad0Behdad Esfahbod#ifndef HB_DEBUG_VERBOSE 609adf7758a27a11fb1a8a14a2673867589437d22a3Behdad Esfahbod /* Skip "typename" */ 610adf7758a27a11fb1a8a14a2673867589437d22a3Behdad Esfahbod if (0 == strncmp (func, "typename ", 9)) 611adf7758a27a11fb1a8a14a2673867589437d22a3Behdad Esfahbod func += 9; 612fabd3113a98c5f4114f48920fa7ea38bd65a8d32Behdad Esfahbod /* Skip return type */ 613d7bba01a353efc7432c474dd8755a02db4abd2aeBehdad Esfahbod const char *space = strchr (func, ' '); 614fabd3113a98c5f4114f48920fa7ea38bd65a8d32Behdad Esfahbod if (space) 615d7bba01a353efc7432c474dd8755a02db4abd2aeBehdad Esfahbod func = space + 1; 616fabd3113a98c5f4114f48920fa7ea38bd65a8d32Behdad Esfahbod /* Skip parameter list */ 617fabd3113a98c5f4114f48920fa7ea38bd65a8d32Behdad Esfahbod const char *paren = strchr (func, '('); 61829ff25481584e20a2fa39195f295c8eb4bf3bad0Behdad Esfahbod if (paren) 61929ff25481584e20a2fa39195f295c8eb4bf3bad0Behdad Esfahbod func_len = paren - func; 62029ff25481584e20a2fa39195f295c8eb4bf3bad0Behdad Esfahbod#endif 621d7bba01a353efc7432c474dd8755a02db4abd2aeBehdad Esfahbod fprintf (stderr, "%.*s: ", func_len, func); 62285f73fa8da1fbb864aef0f3a592b1d65e24d593dBehdad Esfahbod } 6236eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod 6246eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod if (message) 6256eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod vfprintf (stderr, message, ap); 6266eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod 6276eec6f406d2cc13dbca422e88492d3d498af02bfBehdad Esfahbod fprintf (stderr, "\n"); 628208109703c929428c684ddcf9310b8ba780c4c31Behdad Esfahbod} 629829e814ff358c5e700ba4df54932696801aa9f65Behdad Esfahbodtemplate <> inline void 63093345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod_hb_debug_msg_va<0> (const char *what HB_UNUSED, 63193345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const void *obj HB_UNUSED, 63293345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const char *func HB_UNUSED, 63393345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod bool indented HB_UNUSED, 63493345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod unsigned int level HB_UNUSED, 63593345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod int level_dir HB_UNUSED, 63693345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const char *message HB_UNUSED, 63793345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod va_list ap HB_UNUSED) {} 638208109703c929428c684ddcf9310b8ba780c4c31Behdad Esfahbod 6392d1dcb3ce3354c2d5e2b4d1d291beb8d23cdea22Behdad Esfahbodtemplate <int max_level> static inline void 640cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod_hb_debug_msg (const char *what, 641cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod const void *obj, 642cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod const char *func, 643cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod bool indented, 6441e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod unsigned int level, 6451e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod int level_dir, 646cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod const char *message, 6471e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod ...) HB_PRINTF_FUNC(7, 8); 6482d1dcb3ce3354c2d5e2b4d1d291beb8d23cdea22Behdad Esfahbodtemplate <int max_level> static inline void 649cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod_hb_debug_msg (const char *what, 650cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod const void *obj, 651cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod const char *func, 652cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod bool indented, 6531e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod unsigned int level, 6541e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod int level_dir, 655cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod const char *message, 656cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod ...) 657cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod{ 658cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod va_list ap; 659cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod va_start (ap, message); 660829e814ff358c5e700ba4df54932696801aa9f65Behdad Esfahbod _hb_debug_msg_va<max_level> (what, obj, func, indented, level, level_dir, message, ap); 661cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod va_end (ap); 662cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod} 663829e814ff358c5e700ba4df54932696801aa9f65Behdad Esfahbodtemplate <> inline void 66493345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod_hb_debug_msg<0> (const char *what HB_UNUSED, 66593345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const void *obj HB_UNUSED, 66693345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const char *func HB_UNUSED, 66793345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod bool indented HB_UNUSED, 66893345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod unsigned int level HB_UNUSED, 66993345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod int level_dir HB_UNUSED, 67093345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const char *message HB_UNUSED, 6711e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod ...) HB_PRINTF_FUNC(7, 8); 672829e814ff358c5e700ba4df54932696801aa9f65Behdad Esfahbodtemplate <> inline void 67393345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod_hb_debug_msg<0> (const char *what HB_UNUSED, 67493345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const void *obj HB_UNUSED, 67593345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const char *func HB_UNUSED, 67693345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod bool indented HB_UNUSED, 67793345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod unsigned int level HB_UNUSED, 67893345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod int level_dir HB_UNUSED, 67993345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const char *message HB_UNUSED, 680829e814ff358c5e700ba4df54932696801aa9f65Behdad Esfahbod ...) {} 681bc200457430c083914a64bf4b056153506749610Behdad Esfahbod 6820594a2448440208efa0acac9a5d8d52d43108289Behdad Esfahbod#define DEBUG_MSG_LEVEL(WHAT, OBJ, LEVEL, LEVEL_DIR, ...) _hb_debug_msg<HB_DEBUG_##WHAT> (#WHAT, (OBJ), NULL, true, (LEVEL), (LEVEL_DIR), __VA_ARGS__) 6830594a2448440208efa0acac9a5d8d52d43108289Behdad Esfahbod#define DEBUG_MSG(WHAT, OBJ, ...) _hb_debug_msg<HB_DEBUG_##WHAT> (#WHAT, (OBJ), NULL, false, 0, 0, __VA_ARGS__) 6840594a2448440208efa0acac9a5d8d52d43108289Behdad Esfahbod#define DEBUG_MSG_FUNC(WHAT, OBJ, ...) _hb_debug_msg<HB_DEBUG_##WHAT> (#WHAT, (OBJ), HB_FUNC, false, 0, 0, __VA_ARGS__) 685cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod 686cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod 687cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod/* 688dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod * Printer 689dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod */ 690dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod 691dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbodtemplate <typename T> 692dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbodstruct hb_printer_t {}; 693dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod 694dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbodtemplate <> 695dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbodstruct hb_printer_t<bool> { 696dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod const char *print (bool v) { return v ? "true" : "false"; } 697dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod}; 698dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod 699dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbodtemplate <> 700130bb3f6144afe5c88bb5b4e4c98e7cba03b1e26Behdad Esfahbodstruct hb_printer_t<hb_void_t> { 7010beb66e3a61ae8bb1fa66e54b1ff1abb2f8711e9Behdad Esfahbod const char *print (hb_void_t) { return ""; } 702dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod}; 703dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod 704dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod 705dabe698fcbeb02911128b17aa8e3b2d864795960Behdad Esfahbod/* 706cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod * Trace 707cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod */ 708cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod 709902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbodtemplate <typename T> 710902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbodstatic inline void _hb_warn_no_return (bool returned) 711902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod{ 712902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod if (unlikely (!returned)) { 713902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod fprintf (stderr, "OUCH, returned with no call to TRACE_RETURN. This is a bug, please report.\n"); 714902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod } 715902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod} 716902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbodtemplate <> 7170beb66e3a61ae8bb1fa66e54b1ff1abb2f8711e9Behdad Esfahbodinline void _hb_warn_no_return<hb_void_t> (bool returned HB_UNUSED) 718902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod{} 719902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod 720902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbodtemplate <int max_level, typename ret_t> 721cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbodstruct hb_auto_trace_t { 722cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod explicit inline hb_auto_trace_t (unsigned int *plevel_, 7239659523ca32b0e254d0e5fe387d817208d9cb6bfBehdad Esfahbod const char *what_, 7249659523ca32b0e254d0e5fe387d817208d9cb6bfBehdad Esfahbod const void *obj_, 725cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod const char *func, 726208109703c929428c684ddcf9310b8ba780c4c31Behdad Esfahbod const char *message, 7279659523ca32b0e254d0e5fe387d817208d9cb6bfBehdad Esfahbod ...) : plevel (plevel_), what (what_), obj (obj_), returned (false) 728cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod { 7291e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod if (plevel) ++*plevel; 730208109703c929428c684ddcf9310b8ba780c4c31Behdad Esfahbod 731208109703c929428c684ddcf9310b8ba780c4c31Behdad Esfahbod va_list ap; 732208109703c929428c684ddcf9310b8ba780c4c31Behdad Esfahbod va_start (ap, message); 7330594a2448440208efa0acac9a5d8d52d43108289Behdad Esfahbod _hb_debug_msg_va<max_level> (what, obj, func, true, plevel ? *plevel : 0, +1, message, ap); 734208109703c929428c684ddcf9310b8ba780c4c31Behdad Esfahbod va_end (ap); 735cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod } 7360ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod inline ~hb_auto_trace_t (void) 7371e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod { 738902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod _hb_warn_no_return<ret_t> (returned); 739902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod if (!returned) { 7400594a2448440208efa0acac9a5d8d52d43108289Behdad Esfahbod _hb_debug_msg<max_level> (what, obj, NULL, true, plevel ? *plevel : 1, -1, " "); 7410ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod } 7421e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod if (plevel) --*plevel; 7431e08830b4fac3a60ae52349cab6e101d389d30cdBehdad Esfahbod } 744cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod 7452c9d6485a1f89c11f84e720d3c7978dc11a5039aBehdad Esfahbod inline ret_t ret (ret_t v, unsigned int line = 0) 7460ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod { 7470ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod if (unlikely (returned)) { 7480ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod fprintf (stderr, "OUCH, double calls to TRACE_RETURN. This is a bug, please report.\n"); 7490ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod return v; 7500ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod } 7510ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod 752902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod _hb_debug_msg<max_level> (what, obj, NULL, true, plevel ? *plevel : 1, -1, 753902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod "return %s (line %d)", 754902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbod hb_printer_t<ret_t>().print (v), line); 7550ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod if (plevel) --*plevel; 7560ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod plevel = NULL; 7570ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod returned = true; 7580ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod return v; 7590ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod } 7600ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod 761cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod private: 762cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod unsigned int *plevel; 7639659523ca32b0e254d0e5fe387d817208d9cb6bfBehdad Esfahbod const char *what; 7649659523ca32b0e254d0e5fe387d817208d9cb6bfBehdad Esfahbod const void *obj; 765c779d82b2fc801eec0d349a106c0e860448fcf4eBehdad Esfahbod bool returned; 766cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod}; 767902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbodtemplate <typename ret_t> /* Optimize when tracing is disabled */ 768902cc8aca0b3ff25eeee50b3a84d729e31731ef3Behdad Esfahbodstruct hb_auto_trace_t<0, ret_t> { 76993345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod explicit inline hb_auto_trace_t (unsigned int *plevel_ HB_UNUSED, 77093345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const char *what HB_UNUSED, 77193345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const void *obj HB_UNUSED, 77293345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const char *func HB_UNUSED, 77393345edcbea49bdf0e22f26b5b74a23e601dfab4Behdad Esfahbod const char *message HB_UNUSED, 774208109703c929428c684ddcf9310b8ba780c4c31Behdad Esfahbod ...) {} 7750ab8c8621712d33e1e91dfdb4ad0b335e3d2a3fbBehdad Esfahbod 7760beb66e3a61ae8bb1fa66e54b1ff1abb2f8711e9Behdad Esfahbod inline ret_t ret (ret_t v, unsigned int line HB_UNUSED = 0) { return v; } 777cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod}; 778cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod 779ae63cf206291befe3920adfe015e6cd0961580e5Behdad Esfahbod#define TRACE_RETURN(RET) trace.ret (RET, __LINE__) 780cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod 781cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod/* Misc */ 782cc06c243d8be3ebb1190281653d2dba504c16c0fBehdad Esfahbod 783f60f2166c48d07f556ff83f04e95181946eb03dfBehdad Esfahbod 7847b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod/* Pre-mature optimization: 7857b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod * Checks for lo <= u <= hi but with an optimization if lo and hi 7867b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod * are only different in a contiguous set of lower-most bits. 7877b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod */ 788b5aeb95afeb13a66177caada9f5d5ad4cddbd35fBehdad Esfahbodtemplate <typename T> static inline bool 7898f0b64fb6988f9502d2c5e39768a9af133d9a83fBehdad Esfahbodhb_in_range (T u, T lo, T hi) 7907b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod{ 7917b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod if ( ((lo^hi) & lo) == 0 && 7927b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod ((lo^hi) & hi) == (lo^hi) && 7937b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod ((lo^hi) & ((lo^hi) + 1)) == 0 ) 7947b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod return (u & ~(lo^hi)) == lo; 7957b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod else 7967b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod return lo <= u && u <= hi; 7977b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod} 7987b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod 7994a7f4f3e56f8f7640ae7337aa1b3324f31e0d4abBehdad Esfahbodtemplate <typename T> static inline bool 800093cd583263a5d427e3377b31585043fb55d2557Behdad Esfahbodhb_in_ranges (T u, T lo1, T hi1, T lo2, T hi2, T lo3, T hi3) 8014a7f4f3e56f8f7640ae7337aa1b3324f31e0d4abBehdad Esfahbod{ 802093cd583263a5d427e3377b31585043fb55d2557Behdad Esfahbod return hb_in_range (u, lo1, hi1) || hb_in_range (u, lo2, hi2) || hb_in_range (u, lo3, hi3); 8034a7f4f3e56f8f7640ae7337aa1b3324f31e0d4abBehdad Esfahbod} 8044a7f4f3e56f8f7640ae7337aa1b3324f31e0d4abBehdad Esfahbod 8057b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod 80645d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod/* Useful for set-operations on small enums. 80745d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod * For example, for testing "x ∈ {x1, x2, x3}" use: 80845d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod * (FLAG(x) & (FLAG(x1) | FLAG(x2) | FLAG(x3))) 80945d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod */ 810efb4ad735691837a52447bedc1a66a87d0d9af51Behdad Esfahbod#define FLAG(x) (1<<(x)) 8112c372b80f6befad69e216e3f218b38640b8cc044Behdad Esfahbod#define FLAG_RANGE(x,y) (ASSERT_STATIC_EXPR_ZERO ((x) < (y)) + FLAG(y+1) - FLAG(x)) 8127b08b0a7f2057937dfc3ab2ec191656bf2386463Behdad Esfahbod 8138f0b64fb6988f9502d2c5e39768a9af133d9a83fBehdad Esfahbod 81439b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbodtemplate <typename T, typename T2> inline void 81539b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbodhb_bubble_sort (T *array, unsigned int len, int(*compar)(const T *, const T *), T2 *array2) 81645d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod{ 81745d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod if (unlikely (!len)) 81845d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod return; 81945d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod 82045d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod unsigned int k = len - 1; 82145d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod do { 82245d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod unsigned int new_k = 0; 82345d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod 82445d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod for (unsigned int j = 0; j < k; j++) 82539b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod if (compar (&array[j], &array[j+1]) > 0) 82639b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod { 82739b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod { 82839b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod T t; 82939b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod t = array[j]; 83039b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod array[j] = array[j + 1]; 83139b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod array[j + 1] = t; 83239b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod } 83339b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod if (array2) 83439b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod { 83539b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod T2 t; 83639b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod t = array2[j]; 83739b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod array2[j] = array2[j + 1]; 83839b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod array2[j + 1] = t; 83939b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod } 84045d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod 84145d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod new_k = j; 84245d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod } 84345d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod k = new_k; 84445d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod } while (k); 84545d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod} 84645d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod 84739b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbodtemplate <typename T> inline void 84839b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbodhb_bubble_sort (T *array, unsigned int len, int(*compar)(const T *, const T *)) 84939b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod{ 85039b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod hb_bubble_sort (array, len, compar, (int *) NULL); 85139b17837b4064d59c18cebb49c1c0b5b8cc0c117Behdad Esfahbod} 85245d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod 8536f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbodstatic inline hb_bool_t 8546f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbodhb_codepoint_parse (const char *s, unsigned int len, int base, hb_codepoint_t *out) 8556f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod{ 8566f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod /* Pain because we don't know whether s is nul-terminated. */ 8576f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod char buf[64]; 858847794e929831750e97525137ab5e285ccd1064eBehdad Esfahbod len = MIN (ARRAY_LENGTH (buf) - 1, len); 859847794e929831750e97525137ab5e285ccd1064eBehdad Esfahbod strncpy (buf, s, len); 860847794e929831750e97525137ab5e285ccd1064eBehdad Esfahbod buf[len] = '\0'; 8616f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod 8626f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod char *end; 8636f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod errno = 0; 8646f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod unsigned long v = strtoul (buf, &end, base); 8656f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod if (errno) return false; 8666f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod if (*end) return false; 8676f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod *out = v; 8686f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod return true; 8696f3a300138f659020c21c3e08b7981c78df5f332Behdad Esfahbod} 87045d6f29f15f1d2323bcaa2498aed23ff0c8a1567Behdad Esfahbod 871acdba3f90b232fc12fcb200dca2584481b339118Behdad Esfahbod 872bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod/* Global runtime options. */ 873bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod 874bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbodstruct hb_options_t 875bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod{ 876bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod int initialized : 1; 877bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod int uniscribe_bug_compatible : 1; 878bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod}; 879bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod 880bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbodunion hb_options_union_t { 881bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod int i; 882bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod hb_options_t opts; 883bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod}; 884bab02d339f39ed5168daaef9461227f78e596a2fBehdad EsfahbodASSERT_STATIC (sizeof (int) == sizeof (hb_options_union_t)); 885bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod 886bab02d339f39ed5168daaef9461227f78e596a2fBehdad EsfahbodHB_INTERNAL void 887bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod_hb_options_init (void); 888bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod 889bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbodextern HB_INTERNAL hb_options_union_t _hb_options; 890bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod 891bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbodstatic inline hb_options_t 892bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbodhb_options (void) 893bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod{ 894bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod if (unlikely (!_hb_options.i)) 895bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod _hb_options_init (); 896bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod 897bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod return _hb_options.opts; 898bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod} 899bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod 900bab02d339f39ed5168daaef9461227f78e596a2fBehdad Esfahbod 901c57d454accff66e5f2c58006e8fb40bc020b6182Behdad Esfahbod#endif /* HB_PRIVATE_HH */ 902