src/hb-cache.hh

   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
  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 */