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 * The cache is a fixed-size array of 16-bit or 32-bit integers. 36 * The key is split into two parts: the cache index and the rest. 37 * 38 * The cache index is used to index into the array. The rest is used 39 * to store the key and the value. 40 * 41 * The value is stored in the least significant bits of the integer. 42 * The key is stored in the most significant bits of the integer. 43 * The key is shifted by cache_bits to the left to make room for the 44 * value. 45 */ 46 47 template <unsigned int key_bits=16, 48 unsigned int value_bits=8 + 32 - key_bits, 49 unsigned int cache_bits=8, 50 bool thread_safe=true> 51 struct hb_cache_t 52 { 53 using item_t = typename std::conditional<thread_safe, 54 typename std::conditional<key_bits + value_bits - cache_bits <= 16, 55 hb_atomic_short_t, 56 hb_atomic_int_t>::type, 57 typename std::conditional<key_bits + value_bits - cache_bits <= 16, 58 short, 59 int>::type 60 >::type; 61 62 static_assert ((key_bits >= cache_bits), ""); 63 static_assert ((key_bits + value_bits <= cache_bits + 8 * sizeof (item_t)), ""); 64 hb_cache_thb_cache_t65 hb_cache_t () { clear (); } 66 clearhb_cache_t67 void clear () 68 { 69 for (auto &v : values) 70 v = -1; 71 } 72 gethb_cache_t73 bool get (unsigned int key, unsigned int *value) const 74 { 75 unsigned int k = key & ((1u<<cache_bits)-1); 76 unsigned int v = values[k]; 77 if ((key_bits + value_bits - cache_bits == 8 * sizeof (item_t) && v == (unsigned int) -1) || 78 (v >> value_bits) != (key >> cache_bits)) 79 return false; 80 *value = v & ((1u<<value_bits)-1); 81 return true; 82 } 83 sethb_cache_t84 bool set (unsigned int key, unsigned int value) 85 { 86 if (unlikely ((key >> key_bits) || (value >> value_bits))) 87 return false; /* Overflows */ 88 unsigned int k = key & ((1u<<cache_bits)-1); 89 unsigned int v = ((key>>cache_bits)<<value_bits) | value; 90 values[k] = v; 91 return true; 92 } 93 94 private: 95 item_t values[1u<<cache_bits]; 96 }; 97 98 99 #endif /* HB_CACHE_HH */ 100