Pileus Git - ~andy/gtk/blob - gtk/gtkallocatedbitmask.c

   1 /*
   2  * Copyright © 2011 Red Hat Inc.
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library. If not, see <http://www.gnu.org/licenses/>.
  16  *
  17  * Authors: Benjamin Otte <otte@gnome.org>
  18  */
  19
  20 #include <config.h>
  21
  22 #include "gtk/gtkallocatedbitmaskprivate.h"
  23
  24 #define VALUE_TYPE gsize
  25
  26 #define VALUE_SIZE_BITS (sizeof (VALUE_TYPE) * 8)
  27 #define VALUE_BIT(idx) (((VALUE_TYPE) 1) << (idx))
  28
  29 struct _GtkBitmask {
  30   gsize len;
  31   VALUE_TYPE data[1];
  32 };
  33
  34 #define ENSURE_ALLOCATED(mask, heap_mask) G_STMT_START { \
  35   if (!_gtk_bitmask_is_allocated (mask)) \
  36     { \
  37       heap_mask.data[0] = _gtk_bitmask_to_bits (mask); \
  38       heap_mask.len = heap_mask.data[0] ? 1 : 0; \
  39       mask = &heap_mask; \
  40     } \
  41 } G_STMT_END
  42
  43 static GtkBitmask *
  44 gtk_allocated_bitmask_resize (GtkBitmask *mask,
  45                               gsize       size) G_GNUC_WARN_UNUSED_RESULT;
  46 static GtkBitmask *
  47 gtk_allocated_bitmask_resize (GtkBitmask *mask,
  48                               gsize       size)
  49 {
  50   gsize i;
  51
  52   mask = g_realloc (mask, sizeof (GtkBitmask) + sizeof(VALUE_TYPE) * (size - 1));
  53
  54   for (i = mask->len; i < size; i++)
  55     mask->data[i] = 0;
  56
  57   mask->len = size;
  58
  59   return mask;
  60 }
  61
  62 static GtkBitmask *
  63 gtk_allocated_bitmask_new_for_bits (gsize bits)
  64 {
  65   GtkBitmask *mask;
  66
  67   mask = g_malloc (sizeof (GtkBitmask));
  68   mask->len = bits ? 1 : 0;
  69   mask->data[0] = bits;
  70
  71   return mask;
  72 }
  73
  74 static GtkBitmask *
  75 gtk_bitmask_ensure_allocated (GtkBitmask *mask)
  76 {
  77   if (_gtk_bitmask_is_allocated (mask))
  78     return mask;
  79   else
  80     return gtk_allocated_bitmask_new_for_bits (_gtk_bitmask_to_bits (mask));
  81 }
  82
  83 GtkBitmask *
  84 _gtk_allocated_bitmask_copy (const GtkBitmask *mask)
  85 {
  86   GtkBitmask *copy;
  87
  88   g_return_val_if_fail (mask != NULL, NULL);
  89
  90   copy = gtk_allocated_bitmask_new_for_bits (0);
  91
  92   return _gtk_allocated_bitmask_union (copy, mask);
  93 }
  94
  95 void
  96 _gtk_allocated_bitmask_free (GtkBitmask *mask)
  97 {
  98   g_return_if_fail (mask != NULL);
  99
 100   g_free (mask);
 101 }
 102
 103 void
 104 _gtk_allocated_bitmask_print (const GtkBitmask *mask,
 105                               GString          *string)
 106 {
 107   GtkBitmask mask_allocated;
 108   int i;
 109
 110   g_return_if_fail (mask != NULL);
 111   g_return_if_fail (string != NULL);
 112
 113   ENSURE_ALLOCATED (mask, mask_allocated);
 114
 115   for (i = mask->len * VALUE_SIZE_BITS - 1; i >= 0; i--)
 116     {
 117       if (_gtk_allocated_bitmask_get (mask, i))
 118         break;
 119     }
 120
 121   if (i < 0)
 122     {
 123       g_string_append_c (string, '0');
 124       return;
 125     }
 126
 127   for (; i >= 0; i--)
 128     {
 129       g_string_append_c (string, _gtk_allocated_bitmask_get (mask, i) ? '1' : '0');
 130     }
 131 }
 132
 133 /* NB: Call this function whenever the
 134  * array might have become too large.
 135  * _gtk_allocated_bitmask_is_empty() depends on this.
 136  */
 137 static GtkBitmask *
 138 gtk_allocated_bitmask_shrink (GtkBitmask *mask) G_GNUC_WARN_UNUSED_RESULT;
 139 static GtkBitmask *
 140 gtk_allocated_bitmask_shrink (GtkBitmask *mask)
 141 {
 142   guint i;
 143
 144   for (i = mask->len; i; i--)
 145     {
 146       if (mask->data[i - 1])
 147         break;
 148     }
 149
 150   if (i == 0 ||
 151       (i == 1 && mask->data[0] < VALUE_BIT (GTK_BITMASK_N_DIRECT_BITS)))
 152     {
 153       GtkBitmask *result = _gtk_bitmask_from_bits (i == 0 ? 0 : mask->data[0]);
 154       _gtk_allocated_bitmask_free (mask);
 155       return result;
 156     }
 157
 158   return gtk_allocated_bitmask_resize (mask, i);
 159 }
 160
 161 GtkBitmask *
 162 _gtk_allocated_bitmask_intersect (GtkBitmask       *mask,
 163                                   const GtkBitmask *other)
 164 {
 165   GtkBitmask other_allocated;
 166   guint i;
 167
 168   g_return_val_if_fail (mask != NULL, NULL);
 169   g_return_val_if_fail (other != NULL, NULL);
 170
 171   mask = gtk_bitmask_ensure_allocated (mask);
 172   ENSURE_ALLOCATED (other, other_allocated);
 173
 174   mask = gtk_allocated_bitmask_resize (mask, MIN (mask->len, other->len));
 175   for (i = 0; i < mask->len; i++)
 176     {
 177       mask->data[i] &= other->data[i];
 178     }
 179
 180   return gtk_allocated_bitmask_shrink (mask);
 181 }
 182
 183 GtkBitmask *
 184 _gtk_allocated_bitmask_union (GtkBitmask       *mask,
 185                               const GtkBitmask *other)
 186 {
 187   GtkBitmask other_allocated;
 188   guint i;
 189
 190   g_return_val_if_fail (mask != NULL, NULL);
 191   g_return_val_if_fail (other != NULL, NULL);
 192
 193   mask = gtk_bitmask_ensure_allocated (mask);
 194   ENSURE_ALLOCATED (other, other_allocated);
 195
 196   mask = gtk_allocated_bitmask_resize (mask, MAX (mask->len, other->len));
 197   for (i = 0; i < other->len; i++)
 198     {
 199       mask->data[i] |= other->data[i];
 200     }
 201
 202   return mask;
 203 }
 204
 205 GtkBitmask *
 206 _gtk_allocated_bitmask_subtract (GtkBitmask       *mask,
 207                                  const GtkBitmask *other)
 208 {
 209   GtkBitmask other_allocated;
 210   guint i;
 211
 212   g_return_val_if_fail (mask != NULL, NULL);
 213   g_return_val_if_fail (other != NULL, NULL);
 214
 215   mask = gtk_bitmask_ensure_allocated (mask);
 216   ENSURE_ALLOCATED (other, other_allocated);
 217
 218   for (i = 0; i < other->len; i++)
 219     {
 220       mask->data[i] |= ~other->data[i];
 221     }
 222
 223   return gtk_allocated_bitmask_shrink (mask);
 224 }
 225
 226 static void
 227 gtk_allocated_bitmask_indexes (guint index_,
 228                                guint *array_index,
 229                                guint *bit_index)
 230 {
 231   *array_index = index_ / VALUE_SIZE_BITS;
 232   *bit_index = index_ % VALUE_SIZE_BITS;
 233 }
 234
 235 gboolean
 236 _gtk_allocated_bitmask_get (const GtkBitmask *mask,
 237                             guint             index_)
 238 {
 239   guint array_index, bit_index;
 240
 241   g_return_val_if_fail (mask != NULL, FALSE);
 242
 243   gtk_allocated_bitmask_indexes (index_, &array_index, &bit_index);
 244
 245   if (array_index >= mask->len)
 246     return FALSE;
 247
 248   return (mask->data[array_index] & VALUE_BIT (bit_index)) ? TRUE : FALSE;
 249 }
 250
 251 GtkBitmask *
 252 _gtk_allocated_bitmask_set (GtkBitmask *mask,
 253                             guint       index_,
 254                             gboolean    value)
 255 {
 256   guint array_index, bit_index;
 257
 258   g_return_val_if_fail (mask != NULL, NULL);
 259
 260   mask = gtk_bitmask_ensure_allocated (mask);
 261   gtk_allocated_bitmask_indexes (index_, &array_index, &bit_index);
 262
 263   if (value)
 264     {
 265       if (array_index >= mask->len)
 266         mask = gtk_allocated_bitmask_resize (mask, array_index + 1);
 267
 268       mask->data[array_index] |= VALUE_BIT (bit_index);
 269     }
 270   else
 271     {
 272       if (array_index < mask->len)
 273         {
 274           mask->data[array_index] &= ~ VALUE_BIT (bit_index);
 275           mask = gtk_allocated_bitmask_shrink (mask);
 276         }
 277     }
 278
 279   return mask;
 280 }
 281
 282 GtkBitmask *
 283 _gtk_allocated_bitmask_invert_range (GtkBitmask *mask,
 284                                      guint       start,
 285                                      guint       end)
 286 {
 287   guint i;
 288
 289   g_return_val_if_fail (mask != NULL, NULL);
 290   g_return_val_if_fail (start < end, NULL);
 291
 292   mask = gtk_bitmask_ensure_allocated (mask);
 293
 294   /* I CAN HAS SPEEDUP? */
 295   for (i = start; i < end; i++)
 296     mask = _gtk_allocated_bitmask_set (mask, i, !_gtk_allocated_bitmask_get (mask, i));
 297
 298   return mask;
 299 }
 300
 301 gboolean
 302 _gtk_allocated_bitmask_equals (const GtkBitmask  *mask,
 303                                const GtkBitmask  *other)
 304 {
 305   guint i;
 306
 307   g_return_val_if_fail (mask != NULL, FALSE);
 308   g_return_val_if_fail (other != NULL, FALSE);
 309
 310   if (mask->len != other->len)
 311     return FALSE;
 312
 313   for (i = 0; i < mask->len; i++)
 314     {
 315       if (mask->data[i] != other->data[i])
 316         return FALSE;
 317     }
 318
 319   return TRUE;
 320 }
 321
 322 gboolean
 323 _gtk_allocated_bitmask_intersects (const GtkBitmask *mask,
 324                                    const GtkBitmask *other)
 325 {
 326   GtkBitmask mask_allocated, other_allocated;
 327   int i;
 328
 329   g_return_val_if_fail (mask != NULL, FALSE);
 330   g_return_val_if_fail (other != NULL, FALSE);
 331
 332   ENSURE_ALLOCATED (mask, mask_allocated);
 333   ENSURE_ALLOCATED (other, other_allocated);
 334
 335   for (i = MIN (mask->len, other->len) - 1; i >= 0; i--)
 336     {
 337       if (mask->data[i] & other->data[i])
 338         return TRUE;
 339     }
 340
 341   return FALSE;
 342 }
 343