plugins/debug-manager/sparse_buffer.c

   1 /* -*- Mode: C; indent-tabs-mode: t; c-basic-offset: 4; tab-width: 4 -*- */
   2 /*
   3     sparse_buffer.c
   4     Copyright (C) 2006 Sebastien Granjoux
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  19 */
  20
  21 #include "sparse_buffer.h"
  22
  23 #include "anjuta-marshal.h"
  24
  25 #include <string.h>
  26
  27 /*#define DEBUG*/
  28 #include <libanjuta/anjuta-debug.h>
  29
  30 /*
  31  * This object works with the DmaSparseView which is a text view window allowing
  32  * to display very big amount of data. Only the part of the data currently
  33  * displayed is kept in memory.
  34  *
  35  * This object doesn't replace the GtkTextBuffer in the corresponding
  36  * DmaSparseView. The GtkTextBuffer of each DmaSparseView contains only the data
  37  * displayed by the view. So several view displaying the same DmaSparseBuffer
  38  * will probably have GtkTextBuffer containing different data.
  39  *
  40  * The DmaSparseBuffer object contains the data necessary for each view and
  41  * try to maintain a cache of recently used data. The data should be split in
  42  * blocks having a address and a size. The buffer does not care about the
  43  * exact content of each block.
  44  *
  45  * The DmaSparseBuffer does not have any graphical knowledge, like which data
  46  * correspond to one line in the GtkTextBuffer.
  47  *---------------------------------------------------------------------------*/
  48
  49 enum
  50 {
  51         DMA_SPARSE_BUFFER_NODE_SIZE = 512,
  52         DMA_SPARSE_BUFFER_MAX_PAGE = 60,
  53 };
  54
  55 static GObjectClass *parent_class = NULL;
  56
  57 enum
  58 {
  59         CHANGED,
  60         LAST_SIGNAL
  61 };
  62
  63 static guint signals[LAST_SIGNAL] = {0};
  64
  65 /* Helper functions
  66  *---------------------------------------------------------------------------*/
  67
  68 /* DmaBufferNode functions
  69  *---------------------------------------------------------------------------*/
  70
  71 /* Transport functions
  72  *---------------------------------------------------------------------------*/
  73
  74 DmaSparseBufferTransport*
  75 dma_sparse_buffer_alloc_transport (DmaSparseBuffer *buffer, guint lines, guint chars)
  76 {
  77         DmaSparseBufferTransport *trans;
  78
  79         trans = g_slice_new0 (DmaSparseBufferTransport);
  80
  81         trans->buffer = buffer;
  82         trans->lines = lines;
  83         trans->chars = chars;
  84         trans->next = buffer->pending;
  85         buffer->pending = trans;
  86
  87         return trans;
  88 }
  89
  90 void
  91 dma_sparse_buffer_free_transport (DmaSparseBufferTransport *trans)
  92 {
  93         DmaSparseBufferTransport **prev;
  94
  95         g_return_if_fail (trans != NULL);
  96
  97         for (prev = &trans->buffer->pending; *prev != trans; prev = &(*prev)->next)
  98         {
  99                 if (*prev == NULL)
 100                 {
 101                         g_warning ("transport structure is missing");
 102                         return;
 103                 }
 104         }
 105
 106         /* Remove transport structure and free it */
 107         *prev = trans->next;
 108
 109         g_slice_free (DmaSparseBufferTransport, trans);
 110 }
 111
 112 /* Private functions
 113  *---------------------------------------------------------------------------*/
 114
 115 static DmaSparseBufferNode*
 116 dma_sparse_buffer_find (DmaSparseBuffer *buffer, guint address)
 117 {
 118         DmaSparseBufferNode *node = NULL;
 119         DmaSparseBufferNode *next;
 120
 121         /* Look in last node */
 122         if (buffer->cache.head != NULL)
 123         {
 124                 gint gap = buffer->cache.head->lower - address + DMA_SPARSE_BUFFER_NODE_SIZE * 4;
 125
 126                 if (gap < DMA_SPARSE_BUFFER_NODE_SIZE * 9)
 127                 {
 128                         /* node should be quite near */
 129                         node = buffer->cache.head;
 130                 }
 131                 else
 132                 {
 133                         node = buffer->head;
 134                 }
 135         }
 136         else
 137         {
 138                 node = buffer->head;
 139         }
 140
 141         for (;;)
 142         {
 143                 if (node == NULL) break;
 144
 145                 if (node->lower > address)
 146                 {
 147                         /* Search backward */
 148                         node = node->prev;
 149                 }
 150                 else if (node->upper < address)
 151                 {
 152                         /* Search forward */
 153                         next = node->next;
 154
 155                         if ((next == NULL) || (next->lower > address))
 156                         {
 157                                 /* Corresponding node doesn't exist */
 158                                 break;
 159                         }
 160                         node = next;
 161                 }
 162                 else
 163                 {
 164                         /* Find current node */
 165                         break;
 166                 }
 167         }
 168
 169         return node;
 170 }
 171
 172 static void
 173 on_dma_sparse_buffer_changed (const DmaSparseBuffer *buffer)
 174 {
 175 }
 176
 177 /* Public functions
 178  *---------------------------------------------------------------------------*/
 179
 180 DmaSparseBufferNode*
 181 dma_sparse_buffer_lookup (DmaSparseBuffer *buffer, guint address)
 182 {
 183         return dma_sparse_buffer_find (buffer, address);
 184 }
 185
 186 DmaSparseBufferNode*
 187 dma_sparse_buffer_first (DmaSparseBuffer *buffer)
 188 {
 189         return buffer->head;
 190 }
 191
 192 void
 193 dma_sparse_buffer_insert (DmaSparseBuffer *buffer, DmaSparseBufferNode *node)
 194 {
 195         /* New node should have been allocated by caller with g_new */
 196         DmaSparseBufferNode *prev;
 197
 198         DEBUG_PRINT ("insert block %p %x %x", node, node->lower, node->upper);
 199         /* Look for previous node */
 200         prev = dma_sparse_buffer_find (buffer, node->lower);
 201         while ((prev != NULL) && (node->lower <= prev->upper))
 202         {
 203                 DmaSparseBufferNode *tmp;
 204
 205                 DEBUG_PRINT ("remove previous block %x %x", prev->lower, prev->upper);
 206                 /* node overlap, remove it */
 207                 tmp = prev->prev;
 208                 dma_sparse_buffer_remove (buffer, prev);
 209                 prev = tmp;
 210         }
 211
 212         /* Insert node just after prev */
 213         if (prev == NULL)
 214         {
 215                 /* Insert at the beginning */
 216                 node->prev = NULL;
 217                 node->next = buffer->head;
 218                 buffer->head = node;
 219         }
 220         else
 221         {
 222                 node->prev = prev;
 223                 node->next = prev->next;
 224                 prev->next = node;
 225         }
 226         if (node->next != NULL)
 227         {
 228                 node->next->prev = node;
 229         }
 230
 231         /* Check if new node overlap next one */
 232         while ((node->next != NULL) && (node->upper >= node->next->lower))
 233         {
 234                 DEBUG_PRINT ("remove next block %p %x %x", node->next, node->next->lower, node->next->upper);
 235                 /* node overlap, remove it */
 236                 dma_sparse_buffer_remove (buffer, node->next);
 237         }
 238
 239         /* Insert node at the beginning of cache list */
 240         node->cache.prev = NULL;
 241         node->cache.next = buffer->cache.head;
 242         if (buffer->cache.head != NULL)
 243         {
 244                 buffer->cache.head->prev = node;
 245         }
 246         buffer->stamp++;
 247 }
 248
 249 void
 250 dma_sparse_buffer_remove (DmaSparseBuffer *buffer, DmaSparseBufferNode *node)
 251 {
 252         /* Remove node from node list */
 253         if (node->next != NULL)
 254         {
 255                 node->next->prev = node->prev;
 256         }
 257         if (node->prev != NULL)
 258         {
 259                 node->prev->next = node->next;
 260         }
 261         if (buffer->head == node)
 262         {
 263                 buffer->head = node->next;
 264         }
 265
 266         /* Remove node from cache list */
 267         if (node->cache.next != NULL)
 268         {
 269                 node->cache.next->prev = node->cache.prev;
 270         }
 271         if (node->cache.prev != NULL)
 272         {
 273                 node->cache.prev->next = node->cache.next;
 274         }
 275         if (buffer->cache.head == node)
 276         {
 277                 buffer->cache.head = node->cache.next;
 278         }
 279         if (buffer->cache.tail == node)
 280         {
 281                 buffer->cache.tail = node->cache.prev;
 282         }
 283
 284         g_free (node);
 285
 286         buffer->stamp++;
 287 }
 288
 289 void
 290 dma_sparse_buffer_remove_all (DmaSparseBuffer *buffer)
 291 {
 292         DmaSparseBufferNode *node;
 293         DmaSparseBufferNode *next;
 294
 295         for (node = buffer->head; node != NULL; node = next)
 296         {
 297                 next = node->next;
 298                 g_free (node);
 299         }
 300         buffer->cache.head = NULL;
 301         buffer->cache.tail = NULL;
 302         buffer->head = NULL;
 303         buffer->stamp++;
 304 }
 305
 306 guint
 307 dma_sparse_buffer_get_lower (const DmaSparseBuffer *buffer)
 308 {
 309         return buffer->lower;
 310 }
 311
 312 guint
 313 dma_sparse_buffer_get_upper (const DmaSparseBuffer *buffer)
 314 {
 315         return buffer->upper;
 316 }
 317
 318 void
 319 dma_sparse_buffer_changed (const DmaSparseBuffer *buffer)
 320 {
 321                 g_signal_emit (G_OBJECT (buffer), signals[CHANGED], 0);
 322 }
 323
 324 void
 325 dma_sparse_buffer_add_mark (DmaSparseBuffer *buffer, guint address, gint mark)
 326 {
 327         gint markers;
 328
 329         if (buffer->mark == NULL)
 330         {
 331                 /* Create new hash table */
 332                 buffer->mark = g_hash_table_new (g_direct_hash, g_direct_equal);
 333         }
 334
 335         /* Add mark */
 336         markers = GPOINTER_TO_INT (g_hash_table_lookup (buffer->mark, GINT_TO_POINTER (address)));
 337         markers |= 1 << mark;
 338         g_hash_table_replace (buffer->mark, GINT_TO_POINTER (address), GINT_TO_POINTER (markers));
 339 }
 340
 341 void
 342 dma_sparse_buffer_remove_mark (DmaSparseBuffer *buffer, guint address, gint mark)
 343 {
 344         gint markers;
 345
 346         if (buffer->mark == NULL) return;       /* No mark */
 347
 348         /* Remove one mark */
 349         markers = GPOINTER_TO_INT (g_hash_table_lookup (buffer->mark, GINT_TO_POINTER (address)));
 350         markers &= ~ (1 << mark);
 351
 352         if (markers == 0)
 353         {
 354                 g_hash_table_remove (buffer->mark, GINT_TO_POINTER (address));
 355         }
 356         else
 357         {
 358                 g_hash_table_replace (buffer->mark, GINT_TO_POINTER (address), GINT_TO_POINTER (markers));
 359         }
 360 }
 361
 362 struct RemoveMarkPacket
 363 {
 364         GHashTable *hash;
 365         gint mark;
 366 };
 367
 368 static void
 369 on_remove_mark (gpointer key, gpointer value, gpointer user_data)
 370 {
 371         struct RemoveMarkPacket* pack = (struct RemoveMarkPacket *)user_data;
 372
 373         value = GINT_TO_POINTER (GPOINTER_TO_INT (value) & ~(1<< pack->mark));
 374         g_hash_table_replace (pack->hash, key, value);
 375 }
 376
 377 static gboolean
 378 on_remove_empty_mark (gpointer key, gpointer value, gpointer user_data)
 379 {
 380         return (value == NULL);
 381 }
 382
 383 void
 384 dma_sparse_buffer_remove_all_mark (DmaSparseBuffer *buffer, gint mark)
 385 {
 386         /* marker hash table could be null, is no marks have been set */
 387         if (buffer->mark != NULL)
 388         {
 389                 struct RemoveMarkPacket pack;
 390
 391                 pack.hash = buffer->mark;
 392                 pack.mark = mark;
 393
 394                 g_hash_table_foreach (buffer->mark, on_remove_mark, &pack);
 395                 g_hash_table_foreach_remove (buffer->mark, on_remove_empty_mark, NULL);
 396         }
 397 }
 398
 399 gint
 400 dma_sparse_buffer_get_marks (DmaSparseBuffer *buffer, guint address)
 401 {
 402         if (buffer->mark == NULL) return 0;
 403
 404         return GPOINTER_TO_INT (g_hash_table_lookup (buffer->mark, GINT_TO_POINTER (address)));
 405 }
 406
 407 /* Iterator private functions
 408  *---------------------------------------------------------------------------*/
 409
 410 static gboolean
 411 dma_sparse_iter_forward_line (DmaSparseIter *iter)
 412 {
 413         return DMA_GET_SPARSE_BUFFER_CLASS (iter->buffer)->forward_line (iter);
 414 }
 415
 416 static gboolean
 417 dma_sparse_iter_backward_line (DmaSparseIter *iter)
 418 {
 419         return DMA_GET_SPARSE_BUFFER_CLASS (iter->buffer)->backward_line (iter);
 420 }
 421
 422 static void
 423 dma_sparse_iter_insert_line (DmaSparseIter *iter, GtkTextIter *dst)
 424 {
 425         DMA_GET_SPARSE_BUFFER_CLASS (iter->buffer)->insert_line (iter, dst);
 426 }
 427
 428 /* Iterator public functions
 429  *---------------------------------------------------------------------------*/
 430
 431 void
 432 dma_sparse_buffer_get_iterator_at_address (DmaSparseBuffer *buffer, DmaSparseIter *iter, guint address)
 433 {
 434         g_return_if_fail (iter != NULL);
 435         g_return_if_fail (DMA_IS_SPARSE_BUFFER (buffer));
 436
 437         iter->buffer = buffer;
 438         iter->node = dma_sparse_buffer_find (buffer, address);
 439         iter->base = address;
 440         iter->offset = 0;
 441         iter->stamp = buffer->stamp;
 442         iter->line = 0;
 443
 444     DMA_GET_SPARSE_BUFFER_CLASS (iter->buffer)->refresh_iter (iter);
 445 }
 446
 447 void
 448 dma_sparse_buffer_get_iterator_near_address (DmaSparseBuffer *buffer, DmaSparseIter *iter, guint address)
 449 {
 450         g_return_if_fail (iter != NULL);
 451         g_return_if_fail (DMA_IS_SPARSE_BUFFER (buffer));
 452
 453         iter->buffer = buffer;
 454         iter->node = dma_sparse_buffer_find (buffer, address);
 455         iter->base = address;
 456         iter->offset = 1;
 457         iter->line = 0;
 458         iter->stamp = buffer->stamp;
 459
 460     DMA_GET_SPARSE_BUFFER_CLASS (iter->buffer)->refresh_iter (iter);
 461 }
 462
 463 void
 464 dma_sparse_iter_copy (DmaSparseIter *dst, const DmaSparseIter *src)
 465 {
 466         memcpy(dst, src, sizeof (DmaSparseIter));
 467 }
 468
 469 void
 470 dma_sparse_iter_move_at (DmaSparseIter *iter, guint address)
 471 {
 472         dma_sparse_buffer_get_iterator_at_address (iter->buffer, iter, address);
 473 }
 474
 475 void
 476 dma_sparse_iter_move_near (DmaSparseIter *iter, guint address)
 477 {
 478         dma_sparse_buffer_get_iterator_near_address (iter->buffer, iter, address);
 479 }
 480
 481 void
 482 dma_sparse_iter_refresh (DmaSparseIter *iter)
 483 {
 484         if (iter->buffer->stamp != iter->stamp)
 485         {
 486                 iter->node = dma_sparse_buffer_find (iter->buffer, iter->base);
 487                 iter->stamp = iter->buffer->stamp;
 488         DMA_GET_SPARSE_BUFFER_CLASS (iter->buffer)->refresh_iter (iter);
 489         }
 490 }
 491
 492 void
 493 dma_sparse_iter_round (DmaSparseIter *iter, gboolean round_up)
 494 {
 495         if (iter->buffer->stamp != iter->stamp)
 496         {
 497                 iter->node = dma_sparse_buffer_find (iter->buffer, iter->base);
 498                 iter->stamp = iter->buffer->stamp;
 499         }
 500     DMA_GET_SPARSE_BUFFER_CLASS (iter->buffer)->round_iter (iter, round_up);
 501 }
 502
 503 gulong
 504 dma_sparse_iter_get_address (DmaSparseIter *iter)
 505 {
 506         return DMA_GET_SPARSE_BUFFER_CLASS (iter->buffer)->get_address (iter);
 507 }
 508
 509 gboolean
 510 dma_sparse_iter_forward_lines (DmaSparseIter *iter, gint count)
 511 {
 512         gint i;
 513
 514         dma_sparse_iter_refresh (iter);
 515
 516         if (count < 0)
 517         {
 518                 for (i = 0; i > count; --i)
 519                 {
 520                         if (!dma_sparse_iter_backward_line (iter)) return FALSE;
 521                 }
 522         }
 523         else if (count > 0)
 524         {
 525                 for (i = 0; i < count; i++)
 526                 {
 527                         if (!dma_sparse_iter_forward_line (iter)) return FALSE;
 528                 }
 529         }
 530
 531         return TRUE;
 532 }
 533
 534 void
 535 dma_sparse_iter_insert_lines (DmaSparseIter *src, GtkTextIter *dst, guint count)
 536 {
 537         DmaSparseIter iter;
 538         guint line = 0;
 539         GtkTextBuffer *buffer;
 540
 541         buffer = gtk_text_iter_get_buffer (dst);
 542
 543         /* It is possible to get an iterator that doesn't point to any node
 544          * if it has been move to a fixed address without rounding it to
 545          * the nearest line */
 546
 547         dma_sparse_iter_copy (&iter, src);
 548         dma_sparse_iter_refresh (&iter);
 549
 550         /* Fill with data */
 551         for (; line < count; line++)
 552         {
 553                 dma_sparse_iter_insert_line (&iter, dst);
 554                 if (!dma_sparse_iter_forward_line (&iter))
 555                 {
 556                         /* no more data */
 557                         break;
 558                 }
 559                 if (line != count - 1) gtk_text_buffer_insert (buffer, dst, "\n", 1);
 560         }
 561 }
 562
 563 /* GObject functions
 564  *---------------------------------------------------------------------------*/
 565
 566 /* Used in dispose and finalize */
 567
 568 /* dispose is the first destruction step. It is used to unref object created
 569  * with instance_init in order to break reference counting cycles. This
 570  * function could be called several times. All function should still work
 571  * after this call. It has to called its parents.*/
 572
 573 static void
 574 dma_sparse_buffer_dispose (GObject *object)
 575 {
 576         /*DmaSparseBuffer *self = DMA_DATA_BUFFER (object);*/
 577
 578         G_OBJECT_CLASS (parent_class)->dispose (object);
 579 }
 580
 581 /* finalize is the last destruction step. It must free all memory allocated
 582  * with instance_init. It is called only one time just before releasing all
 583  * memory */
 584
 585 static void
 586 dma_sparse_buffer_finalize (GObject *object)
 587 {
 588         DmaSparseBuffer *buffer = DMA_SPARSE_BUFFER (object);
 589         DmaSparseBufferTransport *trans;
 590
 591         dma_sparse_buffer_remove_all (buffer);
 592
 593         /* Free all remaining transport structure */
 594         for (trans = buffer->pending; trans != NULL;)
 595         {
 596                 DmaSparseBufferTransport *next = trans->next;
 597
 598                 g_slice_free (DmaSparseBufferTransport, trans);
 599                 trans = next;
 600         }
 601
 602         /* Free marker hash table */
 603         if (buffer->mark != NULL)
 604         {
 605                 g_hash_table_destroy (buffer->mark);
 606                 buffer->mark = NULL;
 607         }
 608
 609         G_OBJECT_CLASS (parent_class)->finalize (object);
 610 }
 611
 612 /* instance_init is the constructor. All functions should work after this
 613  * call. */
 614
 615 static void
 616 dma_sparse_buffer_instance_init (DmaSparseBuffer *buffer)
 617 {
 618         buffer->lower = 0;
 619         buffer->upper = 0;
 620
 621         buffer->cache.head = NULL;
 622         buffer->cache.tail = NULL;
 623         buffer->head = NULL;
 624         buffer->stamp = 0;
 625         buffer->pending = NULL;
 626         buffer->mark = NULL;
 627 }
 628
 629 /* class_init intialize the class itself not the instance */
 630
 631 static void
 632 dma_sparse_buffer_class_init (DmaSparseBufferClass * klass)
 633 {
 634         GObjectClass *object_class;
 635
 636         g_return_if_fail (klass != NULL);
 637
 638         parent_class = g_type_class_peek_parent (klass);
 639
 640         object_class = G_OBJECT_CLASS (klass);
 641
 642         object_class->dispose = dma_sparse_buffer_dispose;
 643         object_class->finalize = dma_sparse_buffer_finalize;
 644
 645         klass->changed = on_dma_sparse_buffer_changed;
 646
 647         signals[CHANGED] = g_signal_new ("changed",
 648                                                                          G_OBJECT_CLASS_TYPE (object_class),
 649                                                                          G_SIGNAL_RUN_LAST,
 650                                                                          G_STRUCT_OFFSET (DmaSparseBufferClass, changed),
 651                                                                          NULL, NULL,
 652                                                                          anjuta_marshal_VOID__VOID,
 653                                                                          G_TYPE_NONE,
 654                                                                          0);
 655 }
 656
 657 GType
 658 dma_sparse_buffer_get_type (void)
 659 {
 660         static GType type = 0;
 661
 662         if (!type)
 663         {
 664                 static const GTypeInfo type_info =
 665                 {
 666                         sizeof (DmaSparseBufferClass),
 667                         (GBaseInitFunc) NULL,
 668                         (GBaseFinalizeFunc) NULL,
 669                         (GClassInitFunc) dma_sparse_buffer_class_init,
 670                         (GClassFinalizeFunc) NULL,
 671                         NULL,           /* class_data */
 672                         sizeof (DmaSparseBuffer),
 673                         0,              /* n_preallocs */
 674                         (GInstanceInitFunc) dma_sparse_buffer_instance_init,
 675                         NULL            /* value_table */
 676                 };
 677
 678                 type = g_type_register_static (G_TYPE_OBJECT,
 679                                             "DmaSparseBuffer", &type_info, 0);
 680         }
 681
 682         return type;
 683 }
 684
 685 /* Creation and Destruction
 686  *---------------------------------------------------------------------------*/
 687
 688 DmaSparseBuffer*
 689 dma_sparse_buffer_new (guint lower, guint upper)
 690 {
 691         DmaSparseBuffer *buffer;
 692
 693         buffer = g_object_new (DMA_SPARSE_BUFFER_TYPE, NULL);
 694         g_assert (buffer != NULL);
 695
 696         buffer->lower = lower;
 697         buffer->upper = upper;
 698
 699         return buffer;
 700 }
 701
 702 void
 703 dma_sparse_buffer_free (DmaSparseBuffer *buffer)
 704 {
 705         g_object_unref (buffer);
 706 }
 707