1 /* 2 * Copyright © 2012 Google, Inc. 3 * 4 * This is part of HarfBuzz, a text shaping library. 5 * 6 * Permission is hereby granted, without written agreement and without 7 * license or royalty fees, to use, copy, modify, and distribute this 8 * software and its documentation for any purpose, provided that the 9 * above copyright notice and the following two paragraphs appear in 10 * all copies of this software. 11 * 12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR 13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES 14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN 15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH 16 * DAMAGE. 17 * 18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, 19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS 21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO 22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. 23 * 24 * Google Author(s): Behdad Esfahbod 25 */ 26 27 #ifndef HB_CACHE_HH 28 #define HB_CACHE_HH 29 30 #include "hb.hh" 31 32 33 /* Implements a lock-free cache for int->int functions. */ 34 35 template <unsigned int key_bits, unsigned int value_bits, unsigned int cache_bits> 36 struct hb_cache_t 37 { 38 static_assert ((key_bits >= cache_bits), ""); 39 static_assert ((key_bits + value_bits - cache_bits <= 8 * sizeof (hb_atomic_int_t)), ""); 40 static_assert (sizeof (hb_atomic_int_t) == sizeof (unsigned int), ""); 41 inithb_cache_t42 void init () { clear (); } finihb_cache_t43 void fini () {} 44 clearhb_cache_t45 void clear () 46 { 47 for (unsigned i = 0; i < ARRAY_LENGTH (values); i++) 48 values[i].set_relaxed (-1); 49 } 50 gethb_cache_t51 bool get (unsigned int key, unsigned int *value) const 52 { 53 unsigned int k = key & ((1u<<cache_bits)-1); 54 unsigned int v = values[k].get_relaxed (); 55 if ((key_bits + value_bits - cache_bits == 8 * sizeof (hb_atomic_int_t) && v == (unsigned int) -1) || 56 (v >> value_bits) != (key >> cache_bits)) 57 return false; 58 *value = v & ((1u<<value_bits)-1); 59 return true; 60 } 61 sethb_cache_t62 bool set (unsigned int key, unsigned int value) 63 { 64 if (unlikely ((key >> key_bits) || (value >> value_bits))) 65 return false; /* Overflows */ 66 unsigned int k = key & ((1u<<cache_bits)-1); 67 unsigned int v = ((key>>cache_bits)<<value_bits) | value; 68 values[k].set_relaxed (v); 69 return true; 70 } 71 72 private: 73 hb_atomic_int_t values[1u<<cache_bits]; 74 }; 75 76 typedef hb_cache_t<21, 16, 8> hb_cmap_cache_t; 77 typedef hb_cache_t<16, 24, 8> hb_advance_cache_t; 78 79 80 #endif /* HB_CACHE_HH */ 81