1 /*

     2  * Copyright © 2018  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_MAP_PRIVATE_HH

    28 #define HB_MAP_PRIVATE_HH

    29 

    30 #include "hb-private.hh"

    31 #include "hb-object-private.hh"

    32 

    33 

    34 template <typename T>

    35 inline uint32_t Hash (const T &v)

    36 {

    37   /* Knuth's multiplicative method: */

    38   return (uint32_t) v * 2654435761u;

    39 }

    40 

    41 

    42 /*

    43  * hb_map_t

    44  */

    45 

    46 struct hb_map_t

    47 {

    48   struct item_t

    49   {

    50     hb_codepoint_t key;

    51     hb_codepoint_t value;

    52 

    53     inline bool is_unused (void) const { return key == INVALID; }

    54     inline bool is_tombstone (void) const { return key != INVALID && value == INVALID; }

    55   };

    56 

    57   hb_object_header_t header;

    58   bool successful; /* Allocations successful */

    59   unsigned int population; /* Not including tombstones. */

    60   unsigned int occupancy; /* Including tombstones. */

    61   unsigned int mask;

    62   unsigned int prime;

    63   item_t *items;

    64 

    65   inline void init_shallow (void)

    66   {

    67     successful = true;

    68     population = occupancy = 0;

    69     mask = 0;

    70     prime = 0;

    71     items = nullptr;

    72   }

    73   inline void init (void)

    74   {

    75     hb_object_init (this);

    76     init_shallow ();

    77   }

    78   inline void fini_shallow (void)

    79   {

    80     free (items);

    81   }

    82   inline void fini (void)

    83   {

    84     hb_object_fini (this);

    85     fini_shallow ();

    86   }

    87 

    88   inline bool resize (void)

    89   {

    90     if (unlikely (!successful)) return false;

    91 

    92     unsigned int power = _hb_bit_storage (population * 2 + 8);

    93     unsigned int new_size = 1u << power;

    94     item_t *new_items = (item_t *) malloc ((size_t) new_size * sizeof (item_t));

    95     if (unlikely (!new_items))

    96     {

    97       successful = false;

    98       return false;

    99     }

   100     memset (new_items, 0xFF, (size_t) new_size * sizeof (item_t));

   101 

   102     unsigned int old_size = mask + 1;

   103     item_t *old_items = items;

   104 

   105     /* Switch to new, empty, array. */

   106     population = occupancy = 0;

   107     mask = new_size - 1;

   108     prime = prime_for (power);

   109     items = new_items;

   110 

   111     /* Insert back old items. */

   112     if (old_items)

   113       for (unsigned int i = 0; i < old_size; i++)

   114         if (old_items[i].key != INVALID && old_items[i].value != INVALID)

   115           set (old_items[i].key, old_items[i].value);

   116 

   117     free (old_items);

   118 

   119     return true;

   120   }

   121 

   122   inline void set (hb_codepoint_t key, hb_codepoint_t value)

   123   {

   124     if (unlikely (!successful)) return;

   125     if (unlikely (key == INVALID)) return;

   126     if ((occupancy + occupancy / 2) >= mask && !resize ()) return;

   127     unsigned int i = bucket_for (key);

   128 

   129     if (value == INVALID && items[i].key != key)

   130       return; /* Trying to delete non-existent key. */

   131 

   132     if (!items[i].is_unused ())

   133     {

   134       occupancy--;

   135       if (items[i].is_tombstone ())

   136         population--;

   137     }

   138 

   139     items[i].key = key;

   140     items[i].value = value;

   141 

   142     occupancy++;

   143     if (!items[i].is_tombstone ())

   144       population++;

   145 

   146   }

   147   inline hb_codepoint_t get (hb_codepoint_t key) const

   148   {

   149     if (unlikely (!items)) return INVALID;

   150     unsigned int i = bucket_for (key);

   151     return items[i].key == key ? items[i].value : INVALID;

   152   }

   153 

   154   inline void del (hb_codepoint_t key)

   155   {

   156     set (key, INVALID);

   157   }

   158   inline bool has (hb_codepoint_t key) const

   159   {

   160     return get (key) != INVALID;

   161   }

   162 

   163   inline hb_codepoint_t operator [] (unsigned int key) const

   164   { return get (key); }

   165 

   166   static const hb_codepoint_t INVALID = HB_MAP_VALUE_INVALID;

   167 

   168   inline void clear (void)

   169   {

   170     memset (items, 0xFF, ((size_t) mask + 1) * sizeof (item_t));

   171     population = occupancy = 0;

   172   }

   173 

   174   inline bool is_empty (void) const

   175   {

   176     return population != 0;

   177   }

   178 

   179   inline unsigned int get_population () const

   180   {

   181     return population;

   182   }

   183 

   184   protected:

   185 

   186   inline unsigned int bucket_for (hb_codepoint_t key) const

   187   {

   188     unsigned int i = Hash (key) % prime;

   189     unsigned int step = 0;

   190     unsigned int tombstone = INVALID;

   191     while (!items[i].is_unused ())

   192     {

   193       if (items[i].key == key)

   194         return i;

   195       if (tombstone == INVALID && items[i].is_tombstone ())

   196         tombstone = i;

   197       i = (i + ++step) & mask;

   198     }

   199     return tombstone == INVALID ? i : tombstone;

   200   }

   201 

   202   static inline unsigned int prime_for (unsigned int shift)

   203   {

   204     /* Following comment and table copied from glib. */

   205     /* Each table size has an associated prime modulo (the first prime

   206      * lower than the table size) used to find the initial bucket. Probing

   207      * then works modulo 2^n. The prime modulo is necessary to get a

   208      * good distribution with poor hash functions.

   209      */

   210     /* Not declaring static to make all kinds of compilers happy... */

   211     /*static*/ const unsigned int prime_mod [32] =

   212     {

   213       1,          /* For 1 << 0 */

   214       2,

   215       3,

   216       7,

   217       13,

   218       31,

   219       61,

   220       127,

   221       251,

   222       509,

   223       1021,

   224       2039,

   225       4093,

   226       8191,

   227       16381,

   228       32749,

   229       65521,      /* For 1 << 16 */

   230       131071,

   231       262139,

   232       524287,

   233       1048573,

   234       2097143,

   235       4194301,

   236       8388593,

   237       16777213,

   238       33554393,

   239       67108859,

   240       134217689,

   241       268435399,

   242       536870909,

   243       1073741789,

   244       2147483647  /* For 1 << 31 */

   245     };

   246 

   247     if (unlikely (shift >= ARRAY_LENGTH (prime_mod)))

   248       return prime_mod[ARRAY_LENGTH (prime_mod) - 1];

   249 

   250     return prime_mod[shift];

   251   }

   252 };

   253 

   254 

   255 #endif /* HB_MAP_PRIVATE_HH */