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 lockfree cache for int->int functions. */ 34 35 template <unsigned int key_bits=16, 36 unsigned int value_bits=8 + 32 - key_bits, 37 unsigned int cache_bits=8, 38 bool thread_safe=true> 39 struct hb_cache_t 40 { 41 using item_t = typename std::conditional<thread_safe, 42 hb_atomic_int_t, 43 typename std::conditional<key_bits + value_bits - cache_bits <= 16, 44 short, 45 int>::type 46 >::type; 47 48 static_assert ((key_bits >= cache_bits), ""); 49 static_assert ((key_bits + value_bits <= cache_bits + 8 * sizeof (item_t)), ""); 50 inithb_cache_t51 void init () { clear (); } finihb_cache_t52 void fini () {} 53 clearhb_cache_t54 void clear () 55 { 56 for (unsigned i = 0; i < ARRAY_LENGTH (values); i++) 57 values[i] = -1; 58 } 59 gethb_cache_t60 bool get (unsigned int key, unsigned int *value) const 61 { 62 unsigned int k = key & ((1u<<cache_bits)-1); 63 unsigned int v = values[k]; 64 if ((key_bits + value_bits - cache_bits == 8 * sizeof (item_t) && v == (unsigned int) -1) || 65 (v >> value_bits) != (key >> cache_bits)) 66 return false; 67 *value = v & ((1u<<value_bits)-1); 68 return true; 69 } 70 sethb_cache_t71 bool set (unsigned int key, unsigned int value) 72 { 73 if (unlikely ((key >> key_bits) || (value >> value_bits))) 74 return false; /* Overflows */ 75 unsigned int k = key & ((1u<<cache_bits)-1); 76 unsigned int v = ((key>>cache_bits)<<value_bits) | value; 77 values[k] = v; 78 return true; 79 } 80 81 private: 82 item_t values[1u<<cache_bits]; 83 }; 84 85 86 #endif /* HB_CACHE_HH */ 87