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 static GtkBitmask *
  35 gtk_allocated_bitmask_resize (GtkBitmask *mask,
  36                               gsize       size) G_GNUC_WARN_UNUSED_RESULT;
  37 static GtkBitmask *
  38 gtk_allocated_bitmask_resize (GtkBitmask *mask,
  39                               gsize       size)
  40 {
  41   gsize i;
  42
  43   mask = g_realloc (mask, sizeof (GtkBitmask) + sizeof(VALUE_TYPE) * (MAX (size, 1) - 1));
  44
  45   for (i = mask->len; i < size; i++)
  46     mask->data[i] = 0;
  47
  48   mask->len = size;
  49
  50   return mask;
  51 }
  52
  53 GtkBitmask *
  54 _gtk_allocated_bitmask_new (void)
  55 {
  56   return g_malloc0 (sizeof (GtkBitmask));
  57 }
  58
  59 GtkBitmask *
  60 _gtk_allocated_bitmask_copy (const GtkBitmask *mask)
  61 {
  62   GtkBitmask *copy;
  63
  64   g_return_val_if_fail (mask != NULL, NULL);
  65
  66   copy = _gtk_allocated_bitmask_new ();
  67
  68   return _gtk_allocated_bitmask_union (copy, mask);
  69 }
  70
  71 void
  72 _gtk_allocated_bitmask_free (GtkBitmask *mask)
  73 {
  74   g_return_if_fail (mask != NULL);
  75
  76   g_free (mask);
  77 }
  78
  79 void
  80 _gtk_allocated_bitmask_print (const GtkBitmask *mask,
  81                               GString          *string)
  82 {
  83   int i;
  84
  85   g_return_if_fail (mask != NULL);
  86   g_return_if_fail (string != NULL);
  87
  88   for (i = mask->len * VALUE_SIZE_BITS - 1; i >= 0; i--)
  89     {
  90       if (_gtk_allocated_bitmask_get (mask, i))
  91         break;
  92     }
  93
  94   if (i < 0)
  95     {
  96       g_string_append_c (string, '0');
  97       return;
  98     }
  99
 100   for (; i >= 0; i--)
 101     {
 102       g_string_append_c (string, _gtk_allocated_bitmask_get (mask, i) ? '1' : '0');
 103     }
 104 }
 105
 106 char *
 107 _gtk_allocated_bitmask_to_string (const GtkBitmask *mask)
 108 {
 109   GString *string;
 110
 111   string = g_string_new (NULL);
 112   _gtk_allocated_bitmask_print (mask, string);
 113   return g_string_free (string, FALSE);
 114 }
 115
 116 /* NB: Call this function whenever the
 117  * array might have become too large.
 118  * _gtk_allocated_bitmask_is_empty() depends on this.
 119  */
 120 static GtkBitmask *
 121 gtk_allocated_bitmask_shrink (GtkBitmask *mask) G_GNUC_WARN_UNUSED_RESULT;
 122 static GtkBitmask *
 123 gtk_allocated_bitmask_shrink (GtkBitmask *mask)
 124 {
 125   guint i;
 126
 127   for (i = mask->len; i; i--)
 128     {
 129       if (mask->data[i - 1])
 130         break;
 131     }
 132
 133   return gtk_allocated_bitmask_resize (mask, i);
 134 }
 135
 136 GtkBitmask *
 137 _gtk_allocated_bitmask_intersect (GtkBitmask       *mask,
 138                                   const GtkBitmask *other)
 139 {
 140   guint i;
 141
 142   g_return_val_if_fail (mask != NULL, NULL);
 143   g_return_val_if_fail (other != NULL, NULL);
 144
 145   mask = gtk_allocated_bitmask_resize (mask, MIN (mask->len, other->len));
 146   for (i = 0; i < mask->len; i++)
 147     {
 148       mask->data[i] &= other->data[i];
 149     }
 150
 151   return gtk_allocated_bitmask_shrink (mask);
 152 }
 153
 154 GtkBitmask *
 155 _gtk_allocated_bitmask_union (GtkBitmask       *mask,
 156                               const GtkBitmask *other)
 157 {
 158   guint i;
 159
 160   g_return_val_if_fail (mask != NULL, NULL);
 161   g_return_val_if_fail (other != NULL, NULL);
 162
 163   mask = gtk_allocated_bitmask_resize (mask, MAX (mask->len, other->len));
 164   for (i = 0; i < other->len; i++)
 165     {
 166       mask->data[i] |= other->data[i];
 167     }
 168
 169   return mask;
 170 }
 171
 172 GtkBitmask *
 173 _gtk_allocated_bitmask_subtract (GtkBitmask       *mask,
 174                                  const GtkBitmask *other)
 175 {
 176   guint i;
 177
 178   g_return_val_if_fail (mask != NULL, NULL);
 179   g_return_val_if_fail (other != NULL, NULL);
 180
 181   for (i = 0; i < other->len; i++)
 182     {
 183       mask->data[i] |= ~other->data[i];
 184     }
 185
 186   return gtk_allocated_bitmask_shrink (mask);
 187 }
 188
 189 static void
 190 gtk_allocated_bitmask_indexes (guint index_,
 191                                guint *array_index,
 192                                guint *bit_index)
 193 {
 194   *array_index = index_ / VALUE_SIZE_BITS;
 195   *bit_index = index_ % VALUE_SIZE_BITS;
 196 }
 197
 198 gboolean
 199 _gtk_allocated_bitmask_get (const GtkBitmask *mask,
 200                             guint             index_)
 201 {
 202   guint array_index, bit_index;
 203
 204   g_return_val_if_fail (mask != NULL, FALSE);
 205
 206   gtk_allocated_bitmask_indexes (index_, &array_index, &bit_index);
 207
 208   if (array_index >= mask->len)
 209     return FALSE;
 210
 211   return (mask->data[array_index] & VALUE_BIT (bit_index)) ? TRUE : FALSE;
 212 }
 213
 214 GtkBitmask *
 215 _gtk_allocated_bitmask_set (GtkBitmask *mask,
 216                             guint       index_,
 217                             gboolean    value)
 218 {
 219   guint array_index, bit_index;
 220
 221   g_return_val_if_fail (mask != NULL, NULL);
 222
 223   gtk_allocated_bitmask_indexes (index_, &array_index, &bit_index);
 224
 225   if (value)
 226     {
 227       if (array_index >= mask->len)
 228         mask = gtk_allocated_bitmask_resize (mask, array_index + 1);
 229
 230       mask->data[array_index] |= VALUE_BIT (bit_index);
 231     }
 232   else
 233     {
 234       if (array_index < mask->len)
 235         {
 236           mask->data[array_index] &= ~ VALUE_BIT (bit_index);
 237           mask = gtk_allocated_bitmask_shrink (mask);
 238         }
 239     }
 240
 241   return mask;
 242 }
 243
 244 GtkBitmask *
 245 _gtk_allocated_bitmask_invert_range (GtkBitmask *mask,
 246                                      guint       start,
 247                                      guint       end)
 248 {
 249   guint i;
 250
 251   g_return_val_if_fail (mask != NULL, NULL);
 252   g_return_val_if_fail (start < end, NULL);
 253
 254   /* I CAN HAS SPEEDUP? */
 255
 256   for (i = start; i < end; i++)
 257     mask = _gtk_allocated_bitmask_set (mask, i, !_gtk_allocated_bitmask_get (mask, i));
 258
 259   return mask;
 260 }
 261
 262 gboolean
 263 _gtk_allocated_bitmask_is_empty (const GtkBitmask *mask)
 264 {
 265   g_return_val_if_fail (mask != NULL, FALSE);
 266
 267   return mask->len == 0;
 268 }
 269
 270 gboolean
 271 _gtk_allocated_bitmask_equals (const GtkBitmask  *mask,
 272                                const GtkBitmask  *other)
 273 {
 274   guint i;
 275
 276   g_return_val_if_fail (mask != NULL, FALSE);
 277   g_return_val_if_fail (other != NULL, FALSE);
 278
 279   if (mask->len != other->len)
 280     return FALSE;
 281
 282   for (i = 0; i < mask->len; i++)
 283     {
 284       if (mask->data[i] != other->data[i])
 285         return FALSE;
 286     }
 287
 288   return TRUE;
 289 }
 290
 291 gboolean
 292 _gtk_allocated_bitmask_intersects (const GtkBitmask *mask,
 293                                    const GtkBitmask *other)
 294 {
 295   int i;
 296
 297   g_return_val_if_fail (mask != NULL, FALSE);
 298   g_return_val_if_fail (other != NULL, FALSE);
 299
 300   for (i = MIN (mask->len, other->len) - 1; i >= 0; i--)
 301     {
 302       if (mask->data[i] & other->data[i])
 303         return TRUE;
 304     }
 305
 306   return FALSE;
 307 }
 308