Branch
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195
/*
* 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.
*
* Author(s): Behdad Esfahbod
*/
#ifndef HB_BIT_VECTOR_HH
#define HB_BIT_VECTOR_HH
#include "hb.hh"
#include "hb-atomic.hh"
struct hb_min_max_t
{
void add (hb_codepoint_t v) { min_v = hb_min (min_v, v); max_v = hb_max (max_v, v); }
void add_range (hb_codepoint_t a, hb_codepoint_t b)
{
min_v = hb_min (min_v, a);
max_v = hb_max (max_v, b);
}
template <typename set_t>
void union_ (const set_t &set)
{
hb_codepoint_t set_min = set.get_min ();
if (unlikely (set_min == HB_CODEPOINT_INVALID))
return;
hb_codepoint_t set_max = set.get_max ();
min_v = hb_min (min_v, set_min);
max_v = hb_max (max_v, set_max);
}
hb_codepoint_t get_min () const { return min_v; }
hb_codepoint_t get_max () const { return max_v; }
private:
hb_codepoint_t min_v = HB_CODEPOINT_INVALID;
hb_codepoint_t max_v = 0;
};
template <bool atomic = false>
struct hb_bit_vector_t
{
using int_t = uint64_t;
using elt_t = typename std::conditional<atomic, hb_atomic_t<int_t>, int_t>::type;
hb_bit_vector_t () = delete;
hb_bit_vector_t (const hb_bit_vector_t &other) = delete;
hb_bit_vector_t &operator= (const hb_bit_vector_t &other) = delete;
// Move
hb_bit_vector_t (hb_bit_vector_t &&other)
: min_v (other.min_v), max_v (other.max_v), count (other.count), elts (other.elts)
{
other.min_v = other.max_v = other.count = 0;
other.elts = nullptr;
}
hb_bit_vector_t &operator= (hb_bit_vector_t &&other)
{
hb_swap (min_v, other.min_v);
hb_swap (max_v, other.max_v);
hb_swap (count, other.count);
hb_swap (elts, other.elts);
return *this;
}
hb_bit_vector_t (unsigned min_v, unsigned max_v)
: min_v (min_v), max_v (max_v)
{
if (unlikely (min_v >= max_v))
{
min_v = max_v = count = 0;
return;
}
unsigned num = (max_v - min_v + sizeof (int_t) * 8) / (sizeof (int_t) * 8);
elts = (elt_t *) hb_calloc (num, sizeof (int_t));
if (unlikely (!elts))
{
min_v = max_v = count = 0;
return;
}
count = max_v - min_v + 1;
}
~hb_bit_vector_t ()
{
hb_free (elts);
}
void add (hb_codepoint_t g) { elt (g) |= mask (g); }
void del (hb_codepoint_t g) { elt (g) &= ~mask (g); }
void set (hb_codepoint_t g, bool value) { if (value) add (g); else del (g); }
bool get (hb_codepoint_t g) const { return elt (g) & mask (g); }
bool has (hb_codepoint_t g) const { return get (g); }
bool may_have (hb_codepoint_t g) const { return get (g); }
bool operator [] (hb_codepoint_t g) const { return get (g); }
bool operator () (hb_codepoint_t g) const { return get (g); }
void add_range (hb_codepoint_t a, hb_codepoint_t b)
{
if (unlikely (!count || a > b || a < min_v || b > max_v))
return;
elt_t *la = &elt (a);
elt_t *lb = &elt (b);
if (la == lb)
*la |= (mask (b) << 1) - mask(a);
else
{
*la |= ~(mask (a) - 1llu);
la++;
hb_memset (la, 0xff, (char *) lb - (char *) la);
*lb |= ((mask (b) << 1) - 1llu);
}
}
void del_range (hb_codepoint_t a, hb_codepoint_t b)
{
if (unlikely (!count || a > b || a < min_v || b > max_v))
return;
elt_t *la = &elt (a);
elt_t *lb = &elt (b);
if (la == lb)
*la &= ~((mask (b) << 1llu) - mask(a));
else
{
*la &= mask (a) - 1;
la++;
hb_memset (la, 0, (char *) lb - (char *) la);
*lb &= ~((mask (b) << 1) - 1llu);
}
}
void set_range (hb_codepoint_t a, hb_codepoint_t b, bool v)
{ if (v) add_range (a, b); else del_range (a, b); }
template <typename set_t>
void union_ (const set_t &set)
{
for (hb_codepoint_t g : set)
add (g);
}
static const unsigned int ELT_BITS = sizeof (elt_t) * 8;
static constexpr unsigned ELT_MASK = ELT_BITS - 1;
static constexpr elt_t zero = 0;
elt_t &elt (hb_codepoint_t g)
{
g -= min_v;
if (unlikely (g >= count))
return Crap(elt_t);
return elts[g / ELT_BITS];
}
const elt_t& elt (hb_codepoint_t g) const
{
g -= min_v;
if (unlikely (g >= count))
return Null(elt_t);
return elts[g / ELT_BITS];
}
static constexpr int_t mask (hb_codepoint_t g) { return elt_t (1) << (g & ELT_MASK); }
hb_codepoint_t min_v = 0, max_v = 0, count = 0;
elt_t *elts = nullptr;
};
#endif /* HB_BIT_VECTOR_HH */