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*
dma_sparse_buffer_alloc_transport(DmaSparseBuffer * buffer,guint lines,guint chars)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
dma_sparse_buffer_free_transport(DmaSparseBufferTransport * trans)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*
dma_sparse_buffer_find(DmaSparseBuffer * buffer,guint address)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
on_dma_sparse_buffer_changed(const DmaSparseBuffer * buffer)173 on_dma_sparse_buffer_changed (const DmaSparseBuffer *buffer)
174 {
175 }
176
177 /* Public functions
178 *---------------------------------------------------------------------------*/
179
180 DmaSparseBufferNode*
dma_sparse_buffer_lookup(DmaSparseBuffer * buffer,guint address)181 dma_sparse_buffer_lookup (DmaSparseBuffer *buffer, guint address)
182 {
183 return dma_sparse_buffer_find (buffer, address);
184 }
185
186 DmaSparseBufferNode*
dma_sparse_buffer_first(DmaSparseBuffer * buffer)187 dma_sparse_buffer_first (DmaSparseBuffer *buffer)
188 {
189 return buffer->head;
190 }
191
192 void
dma_sparse_buffer_insert(DmaSparseBuffer * buffer,DmaSparseBufferNode * node)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
dma_sparse_buffer_remove(DmaSparseBuffer * buffer,DmaSparseBufferNode * node)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
dma_sparse_buffer_remove_all(DmaSparseBuffer * buffer)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
dma_sparse_buffer_get_lower(const DmaSparseBuffer * buffer)307 dma_sparse_buffer_get_lower (const DmaSparseBuffer *buffer)
308 {
309 return buffer->lower;
310 }
311
312 guint
dma_sparse_buffer_get_upper(const DmaSparseBuffer * buffer)313 dma_sparse_buffer_get_upper (const DmaSparseBuffer *buffer)
314 {
315 return buffer->upper;
316 }
317
318 void
dma_sparse_buffer_changed(const DmaSparseBuffer * buffer)319 dma_sparse_buffer_changed (const DmaSparseBuffer *buffer)
320 {
321 g_signal_emit (G_OBJECT (buffer), signals[CHANGED], 0);
322 }
323
324 void
dma_sparse_buffer_add_mark(DmaSparseBuffer * buffer,guint address,gint mark)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
dma_sparse_buffer_remove_mark(DmaSparseBuffer * buffer,guint address,gint mark)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
on_remove_mark(gpointer key,gpointer value,gpointer user_data)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
on_remove_empty_mark(gpointer key,gpointer value,gpointer user_data)378 on_remove_empty_mark (gpointer key, gpointer value, gpointer user_data)
379 {
380 return (value == NULL);
381 }
382
383 void
dma_sparse_buffer_remove_all_mark(DmaSparseBuffer * buffer,gint mark)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
dma_sparse_buffer_get_marks(DmaSparseBuffer * buffer,guint address)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
dma_sparse_iter_forward_line(DmaSparseIter * iter)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
dma_sparse_iter_backward_line(DmaSparseIter * iter)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
dma_sparse_iter_insert_line(DmaSparseIter * iter,GtkTextIter * dst)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
dma_sparse_buffer_get_iterator_at_address(DmaSparseBuffer * buffer,DmaSparseIter * iter,guint address)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
dma_sparse_buffer_get_iterator_near_address(DmaSparseBuffer * buffer,DmaSparseIter * iter,guint address)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
dma_sparse_iter_copy(DmaSparseIter * dst,const DmaSparseIter * src)464 dma_sparse_iter_copy (DmaSparseIter *dst, const DmaSparseIter *src)
465 {
466 memcpy(dst, src, sizeof (DmaSparseIter));
467 }
468
469 void
dma_sparse_iter_move_at(DmaSparseIter * iter,guint address)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
dma_sparse_iter_move_near(DmaSparseIter * iter,guint address)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
dma_sparse_iter_refresh(DmaSparseIter * iter)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
dma_sparse_iter_round(DmaSparseIter * iter,gboolean round_up)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
dma_sparse_iter_get_address(DmaSparseIter * iter)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
dma_sparse_iter_forward_lines(DmaSparseIter * iter,gint count)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
dma_sparse_iter_insert_lines(DmaSparseIter * src,GtkTextIter * dst,guint count)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
dma_sparse_buffer_dispose(GObject * object)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
dma_sparse_buffer_finalize(GObject * object)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
dma_sparse_buffer_instance_init(DmaSparseBuffer * buffer)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
dma_sparse_buffer_class_init(DmaSparseBufferClass * klass)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
dma_sparse_buffer_get_type(void)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*
dma_sparse_buffer_new(guint lower,guint upper)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
dma_sparse_buffer_free(DmaSparseBuffer * buffer)703 dma_sparse_buffer_free (DmaSparseBuffer *buffer)
704 {
705 g_object_unref (buffer);
706 }
707
708