e-util/e-bit-array.c

   1 /*
   2  *
   3  * This program is free software; you can redistribute it and/or modify it
   4  * under the terms of the GNU Lesser General Public License as published by
   5  * the Free Software Foundation.
   6  *
   7  * This program is distributed in the hope that it will be useful, but
   8  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   9  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  10  * for more details.
  11  *
  12  * You should have received a copy of the GNU Lesser General Public License
  13  * along with this program; if not, see <http://www.gnu.org/licenses/>.
  14  *
  15  *
  16  * Authors:
  17  *              Chris Lahey <clahey@ximian.com>
  18  *
  19  * Copyright (C) 1999-2008 Novell, Inc. (www.novell.com)
  20  *
  21  */
  22
  23 #ifdef HAVE_CONFIG_H
  24 #include <config.h>
  25 #endif
  26
  27 #include <gtk/gtk.h>
  28
  29 #include "e-bit-array.h"
  30
  31 #define ONES ((guint32) 0xffffffff)
  32
  33 #define BOX(n) ((n) / 32)
  34 #define OFFSET(n) (31 - ((n) % 32))
  35 #define BITMASK(n) ((guint32)(((guint32) 0x1) << OFFSET((n))))
  36 #define BITMASK_LEFT(n) ((((n) % 32) == 0) ? 0 : (ONES << (32 - ((n) % 32))))
  37 #define BITMASK_RIGHT(n) ((guint32)(((guint32) ONES) >> ((n) % 32)))
  38
  39 G_DEFINE_TYPE (
  40         EBitArray,
  41         e_bit_array,
  42         G_TYPE_OBJECT)
  43
  44 static void
  45 e_bit_array_insert_real (EBitArray *bit_array,
  46                          gint row)
  47 {
  48         gint box;
  49         gint i;
  50         if (bit_array->bit_count >= 0) {
  51                 /* Add another word if needed. */
  52                 if ((bit_array->bit_count & 0x1f) == 0) {
  53                         bit_array->data = g_renew (
  54                                 guint32, bit_array->data,
  55                                 (bit_array->bit_count >> 5) + 1);
  56                         bit_array->data[bit_array->bit_count >> 5] = 0;
  57                 }
  58
  59                 /* The box is the word that our row is in. */
  60                 box = BOX (row);
  61                 /* Shift all words to the right of our box right one bit. */
  62                 for (i = bit_array->bit_count >> 5; i > box; i--) {
  63                         bit_array->data[i] =
  64                                 (bit_array->data[i] >> 1) |
  65                                 (bit_array->data[i - 1] << 31);
  66                 }
  67
  68                 /* Shift right half of box one bit to the right. */
  69                 bit_array->data[box] =
  70                         (bit_array->data[box] & BITMASK_LEFT (row)) |
  71                         ((bit_array->data[box] & BITMASK_RIGHT (row)) >> 1);
  72                 bit_array->bit_count++;
  73         }
  74 }
  75
  76 static void
  77 e_bit_array_delete_real (EBitArray *bit_array,
  78                          gint row,
  79                          gboolean move_selection_mode)
  80 {
  81         gint box;
  82         gint i;
  83         gint last;
  84         gint selected = FALSE;
  85
  86         if (bit_array->bit_count > 0) {
  87                 guint32 bitmask;
  88                 box = row >> 5;
  89                 last = (bit_array->bit_count - 1) >> 5;
  90
  91                 /* Build bitmasks for the left and right half of the box */
  92                 bitmask = BITMASK_RIGHT (row) >> 1;
  93                 if (move_selection_mode)
  94                         selected = e_bit_array_value_at (bit_array, row);
  95                 /* Shift right half of box one bit to the left. */
  96                 bit_array->data[box] =
  97                         (bit_array->data[box] & BITMASK_LEFT (row)) |
  98                         ((bit_array->data[box] & bitmask) << 1);
  99
 100                 /* Shift all words to the right of our box left one bit. */
 101                 if (box < last) {
 102                         bit_array->data[box] &= bit_array->data[box + 1] >> 31;
 103
 104                         for (i = box + 1; i < last; i++) {
 105                                 bit_array->data[i] =
 106                                         (bit_array->data[i] << 1) |
 107                                         (bit_array->data[i + 1] >> 31);
 108                         }
 109                         /* this over-runs our memory! */
 110                         /*bit_array->data[i] = bit_array->data[i] << 1; */
 111                 }
 112                 bit_array->bit_count--;
 113                 /* Remove the last word if not needed. */
 114                 if ((bit_array->bit_count & 0x1f) == 0) {
 115                         bit_array->data = g_renew (guint32, bit_array->data, bit_array->bit_count >> 5);
 116                 }
 117                 if (move_selection_mode && selected && bit_array->bit_count > 0) {
 118                         e_bit_array_select_single_row (
 119                                 bit_array, row == bit_array->bit_count ? row - 1 : row);
 120                 }
 121         }
 122 }
 123
 124 /* FIXME : Improve efficiency here. */
 125 void
 126 e_bit_array_delete (EBitArray *bit_array,
 127                     gint row,
 128                     gint count)
 129 {
 130         gint i;
 131         for (i = 0; i < count; i++)
 132                 e_bit_array_delete_real (bit_array, row, FALSE);
 133 }
 134
 135 /* FIXME : Improve efficiency here. */
 136 void
 137 e_bit_array_delete_single_mode (EBitArray *bit_array,
 138                                 gint row,
 139                                 gint count)
 140 {
 141         gint i;
 142         for (i = 0; i < count; i++)
 143                 e_bit_array_delete_real (bit_array, row, TRUE);
 144 }
 145
 146 /* FIXME : Improve efficiency here. */
 147 void
 148 e_bit_array_insert (EBitArray *bit_array,
 149                     gint row,
 150                     gint count)
 151 {
 152         gint i;
 153         for (i = 0; i < count; i++)
 154                 e_bit_array_insert_real (bit_array, row);
 155 }
 156
 157 /* FIXME: Implement this more efficiently. */
 158 void
 159 e_bit_array_move_row (EBitArray *bit_array,
 160                       gint old_row,
 161                       gint new_row)
 162 {
 163         e_bit_array_delete_real (bit_array, old_row, FALSE);
 164         e_bit_array_insert_real (bit_array, new_row);
 165 }
 166
 167 static void
 168 bit_array_finalize (GObject *object)
 169 {
 170         EBitArray *bit_array;
 171
 172         bit_array = E_BIT_ARRAY (object);
 173
 174         g_free (bit_array->data);
 175
 176         /* Chain up to parent's finalize() method. */
 177         G_OBJECT_CLASS (e_bit_array_parent_class)->finalize (object);
 178 }
 179
 180 /**
 181  * e_bit_array_value_at
 182  * @bit_array: #EBitArray to check
 183  * @n: The row to check
 184  *
 185  * This routine calculates whether the given row is selected.
 186  *
 187  * Returns: %TRUE if the given row is selected
 188  */
 189 gboolean
 190 e_bit_array_value_at (EBitArray *bit_array,
 191                       gint n)
 192 {
 193         if (bit_array->bit_count < n || bit_array->bit_count == 0)
 194                 return 0;
 195         else
 196                 return (bit_array->data[BOX (n)] >> OFFSET (n)) & 0x1;
 197 }
 198
 199 /**
 200  * e_bit_array_foreach
 201  * @bit_array: #EBitArray to traverse
 202  * @callback: The callback function to call back.
 203  * @closure: The closure
 204  *
 205  * This routine calls the given callback function once for each
 206  * selected row, passing closure as the closure.
 207  */
 208 void
 209 e_bit_array_foreach (EBitArray *bit_array,
 210                      EForeachFunc callback,
 211                      gpointer closure)
 212 {
 213         gint i;
 214         gint last = (bit_array->bit_count + 31) / 32;
 215         for (i = 0; i < last; i++) {
 216                 if (bit_array->data[i]) {
 217                         gint j;
 218                         guint32 value = bit_array->data[i];
 219                         for (j = 0; j < 32; j++) {
 220                                 if (value & 0x80000000) {
 221                                         callback (i * 32 + j, closure);
 222                                 }
 223                                 value <<= 1;
 224                         }
 225                 }
 226         }
 227 }
 228
 229 #define PART(x,n) (((x) & (0x01010101 << n)) >> n)
 230 #define SECTION(x, n) (((x) >> (n * 8)) & 0xff)
 231
 232 /**
 233  * e_bit_array_selected_count
 234  * @bit_array: #EBitArray to count
 235  *
 236  * This routine calculates the number of rows selected.
 237  *
 238  * Returns: The number of rows selected in the given model.
 239  */
 240 gint
 241 e_bit_array_selected_count (EBitArray *bit_array)
 242 {
 243         gint count;
 244         gint i;
 245         gint last;
 246
 247         if (!bit_array->data)
 248                 return 0;
 249
 250         count = 0;
 251
 252         last = BOX (bit_array->bit_count - 1);
 253
 254         for (i = 0; i <= last; i++) {
 255                 gint j;
 256                 guint32 thiscount = 0;
 257                 for (j = 0; j < 8; j++)
 258                         thiscount += PART (bit_array->data[i], j);
 259                 for (j = 0; j < 4; j++)
 260                         count += SECTION (thiscount, j);
 261         }
 262
 263         return count;
 264 }
 265
 266 /**
 267  * e_bit_array_select_all
 268  * @bit_array: #EBitArray to select all
 269  *
 270  * This routine selects all the rows in the given
 271  * #EBitArray.
 272  */
 273 void
 274 e_bit_array_select_all (EBitArray *bit_array)
 275 {
 276         gint i;
 277
 278         if (!bit_array->data)
 279                 bit_array->data = g_new0 (guint32, (bit_array->bit_count + 31) / 32);
 280
 281         for (i = 0; i < (bit_array->bit_count + 31) / 32; i++) {
 282                 bit_array->data[i] = ONES;
 283         }
 284
 285         /* need to zero out the bits corresponding to the rows not
 286          * selected in the last full 32 bit mask */
 287         if (bit_array->bit_count % 32) {
 288                 gint unselected_mask = 0;
 289                 gint num_unselected_in_last_byte = 32 - bit_array->bit_count % 32;
 290
 291                 for (i = 0; i < num_unselected_in_last_byte; i++)
 292                         unselected_mask |= 1 << i;
 293
 294                 bit_array->data[(bit_array->bit_count + 31) / 32 - 1] &= ~unselected_mask;
 295         }
 296 }
 297
 298 gint
 299 e_bit_array_bit_count (EBitArray *bit_array)
 300 {
 301         return bit_array->bit_count;
 302 }
 303
 304 #define OPERATE(object, i,mask,grow) \
 305         ((grow) ? (((object)->data[(i)]) |= ((guint32) ~(mask))) : \
 306         (((object)->data[(i)]) &= (mask)))
 307
 308 void
 309 e_bit_array_change_one_row (EBitArray *bit_array,
 310                             gint row,
 311                             gboolean grow)
 312 {
 313         gint i;
 314         i = BOX (row);
 315
 316         OPERATE (bit_array, i, ~BITMASK (row), grow);
 317 }
 318
 319 void
 320 e_bit_array_change_range (EBitArray *bit_array,
 321                           gint start,
 322                           gint end,
 323                           gboolean grow)
 324 {
 325         gint i, last;
 326         if (start != end) {
 327                 i = BOX (start);
 328                 last = BOX (end);
 329
 330                 if (i == last) {
 331                         OPERATE (
 332                                 bit_array, i, BITMASK_LEFT (start) |
 333                                 BITMASK_RIGHT (end), grow);
 334                 } else {
 335                         OPERATE (bit_array, i, BITMASK_LEFT (start), grow);
 336                         if (grow)
 337                                 for (i++; i < last; i++)
 338                                         bit_array->data[i] = ONES;
 339                         else
 340                                 for (i++; i < last; i++)
 341                                         bit_array->data[i] = 0;
 342                         OPERATE (bit_array, i, BITMASK_RIGHT (end), grow);
 343                 }
 344         }
 345 }
 346
 347 void
 348 e_bit_array_select_single_row (EBitArray *bit_array,
 349                                gint row)
 350 {
 351         gint i;
 352         for (i = 0; i < ((bit_array->bit_count + 31) / 32); i++) {
 353                 if (!((i == BOX (row) && bit_array->data[i] == BITMASK (row)) ||
 354                       (i != BOX (row) && bit_array->data[i] == 0))) {
 355                         g_free (bit_array->data);
 356                         bit_array->data = g_new0 (guint32, (bit_array->bit_count + 31) / 32);
 357                         bit_array->data[BOX (row)] = BITMASK (row);
 358
 359                         break;
 360                 }
 361         }
 362 }
 363
 364 void
 365 e_bit_array_toggle_single_row (EBitArray *bit_array,
 366                                gint row)
 367 {
 368         if (bit_array->data[BOX (row)] & BITMASK (row))
 369                 bit_array->data[BOX (row)] &= ~BITMASK (row);
 370         else
 371                 bit_array->data[BOX (row)] |= BITMASK (row);
 372 }
 373
 374 static void
 375 e_bit_array_init (EBitArray *bit_array)
 376 {
 377         bit_array->data = NULL;
 378         bit_array->bit_count = 0;
 379 }
 380
 381 static void
 382 e_bit_array_class_init (EBitArrayClass *class)
 383 {
 384         GObjectClass *object_class;
 385
 386         object_class = G_OBJECT_CLASS (class);
 387         object_class->finalize = bit_array_finalize;
 388 }
 389
 390 EBitArray *
 391 e_bit_array_new (gint count)
 392 {
 393         EBitArray *bit_array;
 394
 395         bit_array = g_object_new (E_TYPE_BIT_ARRAY, NULL);
 396         bit_array->bit_count = count;
 397         bit_array->data = g_new0 (guint32, (bit_array->bit_count + 31) / 32);
 398
 399         return bit_array;
 400 }