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
47template <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>
51struct 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
65 hb_cache_t () { clear (); }
66
67 void clear ()
68 {
69 for (auto &v : values)
70 v = -1;
71 }
72
73 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
84 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