/*

 * Copyright © 2012  Google, Inc.

 *

 *  This is part of HarfBuzz, a text shaping library.

 *

 * Permission is hereby granted, without written agreement and without

 * license or royalty fees, to use, copy, modify, and distribute this

 * software and its documentation for any purpose, provided that the

 * above copyright notice and the following two paragraphs appear in

 * all copies of this software.

 *

 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR

 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES

 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN

 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH

 * DAMAGE.

 *

 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,

 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND

 * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS

 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO

 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.

 *

 * Google Author(s): Behdad Esfahbod

 */

#ifndef HB_CACHE_HH

#define HB_CACHE_HH

#include "hb.hh"

/* Implements a lockfree cache for int->int functions. */

template <unsigned int key_bits=16,

   unsigned int value_bits=8 + 32 - key_bits,

   unsigned int cache_bits=8,

   bool thread_safe=true>

struct hb_cache_t

{

  using item_t = typename std::conditional<thread_safe,

             hb_atomic_int_t,

             typename std::conditional<key_bits + value_bits - cache_bits <= 16,

                     short,

                     int>::type

            >::type;

  static_assert ((key_bits >= cache_bits), "");

  static_assert ((key_bits + value_bits <= cache_bits + 8 * sizeof (item_t)), "");

  hb_cache_t () { init (); }

  void init () { clear (); }

hb_cache_t<21u, 16u, 8u, true>::init()

Line

Count

Source

53

594k

  void init () { clear (); }

hb_cache_t<24u, 16u, 8u, true>::init()

Line

Count

Source

53

28.5k

  void init () { clear (); }

  void clear ()

  {

    for (unsigned i = 0; i < ARRAY_LENGTH (values); i++)

      values[i] = -1;

  }

hb_cache_t<21u, 16u, 8u, true>::clear()

Line

Count

Source

56

594k

  {

57

152M

    for (unsigned i = 0; i < ARRAY_LENGTH (values); i++)

58

152M

      values[i] = -1;

59

594k

  }

hb_cache_t<24u, 16u, 8u, true>::clear()

Line

Count

Source

56

28.5k

  {

57

7.32M

    for (unsigned i = 0; i < ARRAY_LENGTH (values); i++)

58

7.29M

      values[i] = -1;

59

28.5k

  }

  bool get (unsigned int key, unsigned int *value) const

  {

    unsigned int k = key & ((1u<<cache_bits)-1);

    unsigned int v = values[k];

    if ((key_bits + value_bits - cache_bits == 8 * sizeof (item_t) && v == (unsigned int) -1) ||

  (v >> value_bits) != (key >> cache_bits))

      return false;

    *value = v & ((1u<<value_bits)-1);

    return true;

  }

hb_cache_t<21u, 16u, 8u, true>::get(unsigned int, unsigned int*) const

Line

Count

Source

62

47.4M

  {

63

47.4M

    unsigned int k = key & ((1u<<cache_bits)-1);

64

47.4M

    unsigned int v = values[k];

65

47.4M

    if ((key_bits + value_bits - cache_bits == 8 * sizeof (item_t) && v == (unsigned int) -1) ||

66

47.4M

  (v >> value_bits) != (key >> cache_bits))

67

46.3M

      return false;

68

1.05M

    *value = v & ((1u<<value_bits)-1);

69

1.05M

    return true;

70

47.4M

  }

hb_cache_t<24u, 16u, 8u, true>::get(unsigned int, unsigned int*) const

Line

Count

Source

62

900k

  {

63

900k

    unsigned int k = key & ((1u<<cache_bits)-1);

64

900k

    unsigned int v = values[k];

65

900k

    if ((key_bits + value_bits - cache_bits == 8 * sizeof (item_t) && v == (unsigned int) -1) ||

66

900k

  (v >> value_bits) != (key >> cache_bits))

67

260k

      return false;

68

639k

    *value = v & ((1u<<value_bits)-1);

69

639k

    return true;

70

900k

  }

  bool set (unsigned int key, unsigned int value)

  {

    if (unlikely ((key >> key_bits) || (value >> value_bits)))

      return false; /* Overflows */

    unsigned int k = key & ((1u<<cache_bits)-1);

    unsigned int v = ((key>>cache_bits)<<value_bits) | value;

    values[k] = v;

    return true;

  }

hb_cache_t<21u, 16u, 8u, true>::set(unsigned int, unsigned int)

Line

Count

Source

73

1.66M

  {

74

1.66M

    if (unlikely ((key >> key_bits) || (value >> value_bits)))

75

244k

      return false; /* Overflows */

76

1.42M

    unsigned int k = key & ((1u<<cache_bits)-1);

77

1.42M

    unsigned int v = ((key>>cache_bits)<<value_bits) | value;

78

1.42M

    values[k] = v;

79

1.42M

    return true;

80

1.66M

  }

hb_cache_t<24u, 16u, 8u, true>::set(unsigned int, unsigned int)

Line

Count

Source

73

260k

  {

74

260k

    if (unlikely ((key >> key_bits) || (value >> value_bits)))

75

130k

      return false; /* Overflows */

76

129k

    unsigned int k = key & ((1u<<cache_bits)-1);

77

129k

    unsigned int v = ((key>>cache_bits)<<value_bits) | value;

78

129k

    values[k] = v;

79

129k

    return true;

80

260k

  }

  private:

  item_t values[1u<<cache_bits];

};

#endif /* HB_CACHE_HH */