src/hb-set-private.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_SET_PRIVATE_HH
  28 #define HB_SET_PRIVATE_HH
  29
  30 #include "hb-private.hh"
  31 #include "hb-set.h"
  32 #include "hb-object-private.hh"
  33
  34
  35 struct hb_set_digest_common_bits_t
  36 {
  37   ASSERT_POD ();
  38
  39   typedef unsigned int mask_t;
  40
  41   inline void init (void) {
  42     mask = ~0;
  43     value = (mask_t) -1;
  44   }
  45
  46   inline void add (hb_codepoint_t g) {
  47     if (unlikely (value == (mask_t) -1)) {
  48       value = g;
  49       return;
  50     }
  51
  52     mask ^= (g & mask) ^ value;
  53     value &= mask;
  54   }
  55
  56   inline void add_range (hb_codepoint_t a, hb_codepoint_t b) {
  57     /* The negation here stands for ~(x-1). */
  58     mask &= -(1 << _hb_bit_storage (a ^ b));
  59     value &= mask;
  60   }
  61
  62   inline bool may_have (hb_codepoint_t g) const {
  63     return (g & mask) == value;
  64   }
  65
  66   private:
  67   mask_t mask;
  68   mask_t value;
  69 };
  70
  71 struct hb_set_digest_lowest_bits_t
  72 {
  73   ASSERT_POD ();
  74
  75   typedef unsigned long mask_t;
  76
  77   inline void init (void) {
  78     mask = 0;
  79   }
  80
  81   inline void add (hb_codepoint_t g) {
  82     mask |= mask_for (g);
  83   }
  84
  85   inline void add_range (hb_codepoint_t a, hb_codepoint_t b) {
  86     if (b - a >= sizeof (mask_t) * 8 - 1)
  87       mask = (mask_t) -1;
  88     else {
  89       mask_t ma = mask_for (a);
  90       mask_t mb = mask_for (b);
  91       mask |= mb + (mb - ma) - (mb < ma);
  92     }
  93   }
  94
  95   inline bool may_have (hb_codepoint_t g) const {
  96     return !!(mask & mask_for (g));
  97   }
  98
  99   private:
 100
 101   mask_t mask_for (hb_codepoint_t g) const { return ((mask_t) 1) << (g & (sizeof (mask_t) * 8 - 1)); }
 102   mask_t mask;
 103 };
 104
 105 struct hb_set_digest_t
 106 {
 107   ASSERT_POD ();
 108
 109   inline void init (void) {
 110     digest1.init ();
 111     digest2.init ();
 112   }
 113
 114   inline void add (hb_codepoint_t g) {
 115     digest1.add (g);
 116     digest2.add (g);
 117   }
 118
 119   inline void add_range (hb_codepoint_t a, hb_codepoint_t b) {
 120     digest1.add_range (a, b);
 121     digest2.add_range (a, b);
 122   }
 123
 124   inline bool may_have (hb_codepoint_t g) const {
 125     return digest1.may_have (g) && digest2.may_have (g);
 126   }
 127
 128   private:
 129   hb_set_digest_common_bits_t digest1;
 130   hb_set_digest_lowest_bits_t digest2;
 131 };
 132
 133
 134 /* TODO Make this faster and memmory efficient. */
 135
 136 struct hb_set_t
 137 {
 138   hb_object_header_t header;
 139   ASSERT_POD ();
 140
 141   inline void init (void) {
 142     header.init ();
 143     clear ();
 144   }
 145   inline void fini (void) {
 146   }
 147   inline void clear (void) {
 148     memset (elts, 0, sizeof elts);
 149   }
 150   inline bool empty (void) const {
 151     for (unsigned int i = 0; i < ARRAY_LENGTH (elts); i++)
 152       if (elts[i])
 153         return false;
 154     return true;
 155   }
 156   inline void add (hb_codepoint_t g)
 157   {
 158     if (unlikely (g == SENTINEL)) return;
 159     if (unlikely (g > MAX_G)) return;
 160     elt (g) |= mask (g);
 161   }
 162   inline void add_range (hb_codepoint_t a, hb_codepoint_t b)
 163   {
 164     for (unsigned int i = a; i < b + 1; i++)
 165       add (i);
 166   }
 167   inline void del (hb_codepoint_t g)
 168   {
 169     if (unlikely (g > MAX_G)) return;
 170     elt (g) &= ~mask (g);
 171   }
 172   inline bool has (hb_codepoint_t g) const
 173   {
 174     if (unlikely (g > MAX_G)) return false;
 175     return !!(elt (g) & mask (g));
 176   }
 177   inline bool intersects (hb_codepoint_t first,
 178                           hb_codepoint_t last) const
 179   {
 180     if (unlikely (first > MAX_G)) return false;
 181     if (unlikely (last  > MAX_G)) last = MAX_G;
 182     unsigned int end = last + 1;
 183     for (hb_codepoint_t i = first; i < end; i++)
 184       if (has (i))
 185         return true;
 186     return false;
 187   }
 188   inline bool equal (const hb_set_t *other) const
 189   {
 190     for (unsigned int i = 0; i < ELTS; i++)
 191       if (elts[i] != other->elts[i])
 192         return false;
 193     return true;
 194   }
 195   inline void set (const hb_set_t *other)
 196   {
 197     for (unsigned int i = 0; i < ELTS; i++)
 198       elts[i] = other->elts[i];
 199   }
 200   inline void union_ (const hb_set_t *other)
 201   {
 202     for (unsigned int i = 0; i < ELTS; i++)
 203       elts[i] |= other->elts[i];
 204   }
 205   inline void intersect (const hb_set_t *other)
 206   {
 207     for (unsigned int i = 0; i < ELTS; i++)
 208       elts[i] &= other->elts[i];
 209   }
 210   inline void subtract (const hb_set_t *other)
 211   {
 212     for (unsigned int i = 0; i < ELTS; i++)
 213       elts[i] &= ~other->elts[i];
 214   }
 215   inline void symmetric_difference (const hb_set_t *other)
 216   {
 217     for (unsigned int i = 0; i < ELTS; i++)
 218       elts[i] ^= other->elts[i];
 219   }
 220   inline bool next (hb_codepoint_t *codepoint)
 221   {
 222     if (unlikely (*codepoint == SENTINEL)) {
 223       hb_codepoint_t i = get_min ();
 224       if (i != SENTINEL) {
 225         *codepoint = i;
 226         return true;
 227       } else
 228         return false;
 229     }
 230     for (hb_codepoint_t i = *codepoint + 1; i < MAX_G + 1; i++)
 231       if (has (i)) {
 232         *codepoint = i;
 233         return true;
 234       }
 235     return false;
 236   }
 237   inline hb_codepoint_t get_min (void) const
 238   {
 239     for (unsigned int i = 0; i < ELTS; i++)
 240       if (elts[i])
 241         for (unsigned int j = 0; i < BITS; j++)
 242           if (elts[i] & (1 << j))
 243             return i * BITS + j;
 244     return SENTINEL;
 245   }
 246   inline hb_codepoint_t get_max (void) const
 247   {
 248     for (unsigned int i = ELTS; i; i--)
 249       if (elts[i - 1])
 250         for (unsigned int j = BITS; j; j--)
 251           if (elts[i - 1] & (1 << (j - 1)))
 252             return (i - 1) * BITS + (j - 1);
 253     return SENTINEL;
 254   }
 255
 256   typedef uint32_t elt_t;
 257   static const unsigned int MAX_G = 65536 - 1; /* XXX Fix this... */
 258   static const unsigned int SHIFT = 5;
 259   static const unsigned int BITS = (1 << SHIFT);
 260   static const unsigned int MASK = BITS - 1;
 261   static const unsigned int ELTS = (MAX_G + 1 + (BITS - 1)) / BITS;
 262   static  const hb_codepoint_t SENTINEL = (hb_codepoint_t) -1;
 263
 264   elt_t &elt (hb_codepoint_t g) { return elts[g >> SHIFT]; }
 265   elt_t elt (hb_codepoint_t g) const { return elts[g >> SHIFT]; }
 266   elt_t mask (hb_codepoint_t g) const { return elt_t (1) << (g & MASK); }
 267
 268   elt_t elts[ELTS]; /* XXX 8kb */
 269
 270   ASSERT_STATIC (sizeof (elt_t) * 8 == BITS);
 271   ASSERT_STATIC (sizeof (elt_t) * 8 * ELTS > MAX_G);
 272 };
 273
 274
 275
 276 #endif /* HB_SET_PRIVATE_HH */