gtkallocatedbitmask.c 8.76 KB
Newer Older
Benjamin Otte's avatar
Benjamin Otte committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14
/*
 * Copyright © 2011 Red Hat Inc.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
Javier Jardón's avatar
Javier Jardón committed
15
 * License along with this library. If not, see <http://www.gnu.org/licenses/>.
Benjamin Otte's avatar
Benjamin Otte committed
16 17 18 19 20 21
 *
 * Authors: Benjamin Otte <otte@gnome.org>
 */

#include <config.h>

22 23 24
#include "gtkallocatedbitmaskprivate.h"
#include "gtkprivate.h"

Benjamin Otte's avatar
Benjamin Otte committed
25 26 27 28 29

#define VALUE_TYPE gsize

#define VALUE_SIZE_BITS (sizeof (VALUE_TYPE) * 8)
#define VALUE_BIT(idx) (((VALUE_TYPE) 1) << (idx))
30
#define ALL_BITS (~((VALUE_TYPE) 0))
Benjamin Otte's avatar
Benjamin Otte committed
31

32 33 34 35 36
struct _GtkBitmask {
  gsize len;
  VALUE_TYPE data[1];
};

37 38 39 40 41 42 43 44 45
#define ENSURE_ALLOCATED(mask, heap_mask) G_STMT_START { \
  if (!_gtk_bitmask_is_allocated (mask)) \
    { \
      heap_mask.data[0] = _gtk_bitmask_to_bits (mask); \
      heap_mask.len = heap_mask.data[0] ? 1 : 0; \
      mask = &heap_mask; \
    } \
} G_STMT_END

46
static GtkBitmask *
47 48
gtk_allocated_bitmask_resize (GtkBitmask *mask,
                              gsize       size) G_GNUC_WARN_UNUSED_RESULT;
49
static GtkBitmask *
50 51
gtk_allocated_bitmask_resize (GtkBitmask *mask,
                              gsize       size)
52 53 54
{
  gsize i;

55 56 57
  if (size == mask->len)
    return mask;

58
  mask = g_realloc (mask, sizeof (GtkBitmask) + sizeof(VALUE_TYPE) * (size - 1));
59 60 61 62 63 64 65 66 67

  for (i = mask->len; i < size; i++)
    mask->data[i] = 0;

  mask->len = size;

  return mask;
}

68 69 70 71 72 73 74 75 76 77 78 79 80 81
static GtkBitmask *
gtk_allocated_bitmask_new_for_bits (gsize bits)
{
  GtkBitmask *mask;
  
  mask = g_malloc (sizeof (GtkBitmask));
  mask->len = bits ? 1 : 0;
  mask->data[0] = bits;

  return mask;
}

static GtkBitmask *
gtk_bitmask_ensure_allocated (GtkBitmask *mask)
Benjamin Otte's avatar
Benjamin Otte committed
82
{
83 84 85 86
  if (_gtk_bitmask_is_allocated (mask))
    return mask;
  else
    return gtk_allocated_bitmask_new_for_bits (_gtk_bitmask_to_bits (mask));
Benjamin Otte's avatar
Benjamin Otte committed
87 88 89
}

GtkBitmask *
90
_gtk_allocated_bitmask_copy (const GtkBitmask *mask)
Benjamin Otte's avatar
Benjamin Otte committed
91 92 93
{
  GtkBitmask *copy;

94
  gtk_internal_return_val_if_fail (mask != NULL, NULL);
Benjamin Otte's avatar
Benjamin Otte committed
95

96
  copy = gtk_allocated_bitmask_new_for_bits (0);
97
  
98
  return _gtk_allocated_bitmask_union (copy, mask);
Benjamin Otte's avatar
Benjamin Otte committed
99 100 101
}

void
102
_gtk_allocated_bitmask_free (GtkBitmask *mask)
Benjamin Otte's avatar
Benjamin Otte committed
103
{
104
  gtk_internal_return_if_fail (mask != NULL);
Benjamin Otte's avatar
Benjamin Otte committed
105

106
  g_free (mask);
Benjamin Otte's avatar
Benjamin Otte committed
107 108 109
}

void
110 111
_gtk_allocated_bitmask_print (const GtkBitmask *mask,
                              GString          *string)
Benjamin Otte's avatar
Benjamin Otte committed
112
{
113
  GtkBitmask mask_allocated;
Benjamin Otte's avatar
Benjamin Otte committed
114 115
  int i;

116 117
  gtk_internal_return_if_fail (mask != NULL);
  gtk_internal_return_if_fail (string != NULL);
Benjamin Otte's avatar
Benjamin Otte committed
118

119 120
  ENSURE_ALLOCATED (mask, mask_allocated);

Benjamin Otte's avatar
Benjamin Otte committed
121 122
  for (i = mask->len * VALUE_SIZE_BITS - 1; i >= 0; i--)
    {
123
      if (_gtk_allocated_bitmask_get (mask, i))
Benjamin Otte's avatar
Benjamin Otte committed
124 125 126 127 128 129 130 131 132 133 134
        break;
    }

  if (i < 0)
    {
      g_string_append_c (string, '0');
      return;
    }

  for (; i >= 0; i--)
    {
135
      g_string_append_c (string, _gtk_allocated_bitmask_get (mask, i) ? '1' : '0');
Benjamin Otte's avatar
Benjamin Otte committed
136 137 138 139 140
    }
}

/* NB: Call this function whenever the
 * array might have become too large.
141
 * _gtk_allocated_bitmask_is_empty() depends on this.
Benjamin Otte's avatar
Benjamin Otte committed
142
 */
143
static GtkBitmask *
144
gtk_allocated_bitmask_shrink (GtkBitmask *mask) G_GNUC_WARN_UNUSED_RESULT;
145
static GtkBitmask *
146
gtk_allocated_bitmask_shrink (GtkBitmask *mask)
Benjamin Otte's avatar
Benjamin Otte committed
147 148 149 150 151
{
  guint i;

  for (i = mask->len; i; i--)
    {
152
      if (mask->data[i - 1])
Benjamin Otte's avatar
Benjamin Otte committed
153 154 155
        break;
    }

156 157 158 159 160 161 162 163
  if (i == 0 ||
      (i == 1 && mask->data[0] < VALUE_BIT (GTK_BITMASK_N_DIRECT_BITS)))
    {
      GtkBitmask *result = _gtk_bitmask_from_bits (i == 0 ? 0 : mask->data[0]);
      _gtk_allocated_bitmask_free (mask);
      return result;
    }

164
  return gtk_allocated_bitmask_resize (mask, i);
Benjamin Otte's avatar
Benjamin Otte committed
165 166
}

167
GtkBitmask *
168 169
_gtk_allocated_bitmask_intersect (GtkBitmask       *mask,
                                  const GtkBitmask *other)
Benjamin Otte's avatar
Benjamin Otte committed
170
{
171
  GtkBitmask other_allocated;
Benjamin Otte's avatar
Benjamin Otte committed
172 173
  guint i;

174 175
  gtk_internal_return_val_if_fail (mask != NULL, NULL);
  gtk_internal_return_val_if_fail (other != NULL, NULL);
Benjamin Otte's avatar
Benjamin Otte committed
176

177 178 179
  mask = gtk_bitmask_ensure_allocated (mask);
  ENSURE_ALLOCATED (other, other_allocated);

180
  for (i = 0; i < MIN (mask->len, other->len); i++)
Benjamin Otte's avatar
Benjamin Otte committed
181
    {
182
      mask->data[i] &= other->data[i];
Benjamin Otte's avatar
Benjamin Otte committed
183
    }
184 185 186 187
  for (; i < mask->len; i++)
    {
      mask->data[i] = 0;
    }
Benjamin Otte's avatar
Benjamin Otte committed
188

189
  return gtk_allocated_bitmask_shrink (mask);
Benjamin Otte's avatar
Benjamin Otte committed
190 191
}

192
GtkBitmask *
193 194
_gtk_allocated_bitmask_union (GtkBitmask       *mask,
                              const GtkBitmask *other)
Benjamin Otte's avatar
Benjamin Otte committed
195
{
196
  GtkBitmask other_allocated;
Benjamin Otte's avatar
Benjamin Otte committed
197 198
  guint i;

199 200
  gtk_internal_return_val_if_fail (mask != NULL, NULL);
  gtk_internal_return_val_if_fail (other != NULL, NULL);
Benjamin Otte's avatar
Benjamin Otte committed
201

202 203 204
  mask = gtk_bitmask_ensure_allocated (mask);
  ENSURE_ALLOCATED (other, other_allocated);

205
  mask = gtk_allocated_bitmask_resize (mask, MAX (mask->len, other->len));
Benjamin Otte's avatar
Benjamin Otte committed
206 207
  for (i = 0; i < other->len; i++)
    {
208
      mask->data[i] |= other->data[i];
Benjamin Otte's avatar
Benjamin Otte committed
209
    }
210 211

  return mask;
Benjamin Otte's avatar
Benjamin Otte committed
212 213
}

214
GtkBitmask *
215 216
_gtk_allocated_bitmask_subtract (GtkBitmask       *mask,
                                 const GtkBitmask *other)
Benjamin Otte's avatar
Benjamin Otte committed
217
{
218
  GtkBitmask other_allocated;
219
  guint i, len;
Benjamin Otte's avatar
Benjamin Otte committed
220

221 222
  gtk_internal_return_val_if_fail (mask != NULL, NULL);
  gtk_internal_return_val_if_fail (other != NULL, NULL);
Benjamin Otte's avatar
Benjamin Otte committed
223

224 225 226
  mask = gtk_bitmask_ensure_allocated (mask);
  ENSURE_ALLOCATED (other, other_allocated);

227 228
  len = MIN (mask->len, other->len);
  for (i = 0; i < len; i++)
Benjamin Otte's avatar
Benjamin Otte committed
229
    {
230
      mask->data[i] &= ~other->data[i];
Benjamin Otte's avatar
Benjamin Otte committed
231 232
    }

233
  return gtk_allocated_bitmask_shrink (mask);
Benjamin Otte's avatar
Benjamin Otte committed
234 235
}

236
static inline void
237 238 239
gtk_allocated_bitmask_indexes (guint index_,
                               guint *array_index,
                               guint *bit_index)
Benjamin Otte's avatar
Benjamin Otte committed
240 241 242 243 244 245
{
  *array_index = index_ / VALUE_SIZE_BITS;
  *bit_index = index_ % VALUE_SIZE_BITS;
}

gboolean
246 247
_gtk_allocated_bitmask_get (const GtkBitmask *mask,
                            guint             index_)
Benjamin Otte's avatar
Benjamin Otte committed
248 249 250
{
  guint array_index, bit_index;

251
  gtk_internal_return_val_if_fail (mask != NULL, FALSE);
Benjamin Otte's avatar
Benjamin Otte committed
252

253
  gtk_allocated_bitmask_indexes (index_, &array_index, &bit_index);
Benjamin Otte's avatar
Benjamin Otte committed
254 255 256 257

  if (array_index >= mask->len)
    return FALSE;

258
  return (mask->data[array_index] & VALUE_BIT (bit_index)) ? TRUE : FALSE;
Benjamin Otte's avatar
Benjamin Otte committed
259 260
}

261
GtkBitmask *
262 263 264
_gtk_allocated_bitmask_set (GtkBitmask *mask,
                            guint       index_,
                            gboolean    value)
Benjamin Otte's avatar
Benjamin Otte committed
265 266 267
{
  guint array_index, bit_index;

268
  gtk_internal_return_val_if_fail (mask != NULL, NULL);
Benjamin Otte's avatar
Benjamin Otte committed
269

270
  mask = gtk_bitmask_ensure_allocated (mask);
271
  gtk_allocated_bitmask_indexes (index_, &array_index, &bit_index);
Benjamin Otte's avatar
Benjamin Otte committed
272 273 274 275

  if (value)
    {
      if (array_index >= mask->len)
276
        mask = gtk_allocated_bitmask_resize (mask, array_index + 1);
Benjamin Otte's avatar
Benjamin Otte committed
277
      
278
      mask->data[array_index] |= VALUE_BIT (bit_index);
Benjamin Otte's avatar
Benjamin Otte committed
279 280 281 282 283
    }
  else
    {
      if (array_index < mask->len)
        {
284
          mask->data[array_index] &= ~ VALUE_BIT (bit_index);
285
          mask = gtk_allocated_bitmask_shrink (mask);
Benjamin Otte's avatar
Benjamin Otte committed
286 287
        }
    }
288 289

  return mask;
Benjamin Otte's avatar
Benjamin Otte committed
290 291
}

292
GtkBitmask *
293 294 295
_gtk_allocated_bitmask_invert_range (GtkBitmask *mask,
                                     guint       start,
                                     guint       end)
Benjamin Otte's avatar
Benjamin Otte committed
296 297
{
  guint i;
298 299
  guint start_word, start_bit;
  guint end_word, end_bit;
Benjamin Otte's avatar
Benjamin Otte committed
300

301 302
  gtk_internal_return_val_if_fail (mask != NULL, NULL);
  gtk_internal_return_val_if_fail (start < end, NULL);
Benjamin Otte's avatar
Benjamin Otte committed
303

304
  mask = gtk_bitmask_ensure_allocated (mask);
Benjamin Otte's avatar
Benjamin Otte committed
305

306 307
  gtk_allocated_bitmask_indexes (start, &start_word, &start_bit);
  gtk_allocated_bitmask_indexes (end - 1, &end_word, &end_bit);
308

309 310 311
  if (end_word >= mask->len)
    mask = gtk_allocated_bitmask_resize (mask, end_word + 1);

312 313 314
  for (i = start_word; i <= end_word; i++)
    mask->data[i] ^= ALL_BITS;
  mask->data[start_word] ^= (((VALUE_TYPE) 1) << start_bit) - 1;
315
  if (end_bit != VALUE_SIZE_BITS - 1)
316
    mask->data[end_word] ^= ALL_BITS << (end_bit + 1);
317 318

  return gtk_allocated_bitmask_shrink (mask);
Benjamin Otte's avatar
Benjamin Otte committed
319 320 321
}

gboolean
322 323
_gtk_allocated_bitmask_equals (const GtkBitmask  *mask,
                               const GtkBitmask  *other)
Benjamin Otte's avatar
Benjamin Otte committed
324 325 326
{
  guint i;

327 328
  gtk_internal_return_val_if_fail (mask != NULL, FALSE);
  gtk_internal_return_val_if_fail (other != NULL, FALSE);
Benjamin Otte's avatar
Benjamin Otte committed
329 330 331 332 333 334

  if (mask->len != other->len)
    return FALSE;

  for (i = 0; i < mask->len; i++)
    {
335
      if (mask->data[i] != other->data[i])
Benjamin Otte's avatar
Benjamin Otte committed
336 337 338 339 340 341 342
        return FALSE;
    }

  return TRUE;
}

gboolean
343 344
_gtk_allocated_bitmask_intersects (const GtkBitmask *mask,
                                   const GtkBitmask *other)
Benjamin Otte's avatar
Benjamin Otte committed
345
{
346
  GtkBitmask mask_allocated, other_allocated;
Benjamin Otte's avatar
Benjamin Otte committed
347 348
  int i;

349 350
  gtk_internal_return_val_if_fail (mask != NULL, FALSE);
  gtk_internal_return_val_if_fail (other != NULL, FALSE);
Benjamin Otte's avatar
Benjamin Otte committed
351

352 353 354
  ENSURE_ALLOCATED (mask, mask_allocated);
  ENSURE_ALLOCATED (other, other_allocated);

Benjamin Otte's avatar
Benjamin Otte committed
355 356
  for (i = MIN (mask->len, other->len) - 1; i >= 0; i--)
    {
357
      if (mask->data[i] & other->data[i])
Benjamin Otte's avatar
Benjamin Otte committed
358 359 360 361 362 363
        return TRUE;
    }

  return FALSE;
}