/*

 * 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

595k

  void init () { clear (); }

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

Line

Count

Source

53

22.4k

  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

595k

  {

57

153M

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

58

152M

      values[i] = -1;

59

595k

  }

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

Line

Count

Source

56

22.4k

  {

57

5.76M

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

58

5.74M

      values[i] = -1;

59

22.4k

  }

  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

50.7M

  {

63

50.7M

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

64

50.7M

    unsigned int v = values[k];

65

50.7M

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

66

50.7M

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

67

49.3M

      return false;

68

1.41M

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

69

1.41M

    return true;

70

50.7M

  }

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

Line

Count

Source

62

616k

  {

63

616k

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

64

616k

    unsigned int v = values[k];

65

616k

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

66

616k

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

67

175k

      return false;

68

441k

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

69

441k

    return true;

70

616k

  }

  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

2.22M

  {

74

2.22M

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

75

507k

      return false; /* Overflows */

76

1.71M

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

77

1.71M

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

78

1.71M

    values[k] = v;

79

1.71M

    return true;

80

2.22M

  }

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

Line

Count

Source

73

175k

  {

74

175k

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

75

118k

      return false; /* Overflows */

76

56.8k

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

77

56.8k

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

78

56.8k

    values[k] = v;

79

56.8k

    return true;

80

175k

  }

  private:

  item_t values[1u<<cache_bits];

};

#endif /* HB_CACHE_HH */