4 * This file contains code that manages the B-tree representation
5 * of text for the text buffer and implements character and
6 * toggle segment types.
8 * Copyright (c) 1992-1994 The Regents of the University of California.
9 * Copyright (c) 1994-1995 Sun Microsystems, Inc.
10 * Copyright (c) 2000 Red Hat, Inc.
11 * Tk -> Gtk port by Havoc Pennington <hp@redhat.com>
13 * This software is copyrighted by the Regents of the University of
14 * California, Sun Microsystems, Inc., and other parties. The
15 * following terms apply to all files associated with the software
16 * unless explicitly disclaimed in individual files.
18 * The authors hereby grant permission to use, copy, modify,
19 * distribute, and license this software and its documentation for any
20 * purpose, provided that existing copyright notices are retained in
21 * all copies and that this notice is included verbatim in any
22 * distributions. No written agreement, license, or royalty fee is
23 * required for any of the authorized uses. Modifications to this
24 * software may be copyrighted by their authors and need not follow
25 * the licensing terms described here, provided that the new terms are
26 * clearly indicated on the first page of each file where they apply.
28 * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
29 * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
30 * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
31 * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
32 * OF THE POSSIBILITY OF SUCH DAMAGE.
34 * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
35 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
36 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
37 * NON-INFRINGEMENT. THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
38 * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
39 * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
41 * GOVERNMENT USE: If you are acquiring this software on behalf of the
42 * U.S. government, the Government shall have only "Restricted Rights"
43 * in the software and related documentation as defined in the Federal
44 * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2). If you
45 * are acquiring the software on behalf of the Department of Defense,
46 * the software shall be classified as "Commercial Computer Software"
47 * and the Government shall have only "Restricted Rights" as defined
48 * in Clause 252.227-7013 (c) (1) of DFARs. Notwithstanding the
49 * foregoing, the authors grant the U.S. Government and others acting
50 * in its behalf permission to use and distribute the software in
51 * accordance with the terms specified in this license.
55 #include "gtktextbtree.h"
60 #include "gtksignal.h"
61 #include "gtktexttag.h"
62 #include "gtktexttagtable.h"
63 #include "gtktextlayout.h"
64 #include "gtktextiterprivate.h"
66 #include "gtktextmarkprivate.h"
74 * The structure below is used to pass information between
75 * gtk_text_btree_get_tags and inc_count:
78 typedef struct TagInfo {
79 int numTags; /* Number of tags for which there
80 * is currently information in
82 int arraySize; /* Number of entries allocated for
84 GtkTextTag **tags; /* Array of tags seen so far.
86 int *counts; /* Toggle count (so far) for each
87 * entry in tags. Malloc-ed. */
92 * This is used to store per-view width/height info at the tree nodes.
95 typedef struct _NodeData NodeData;
101 /* Height and width of this node */
105 /* boolean indicating whether the height/width need to be recomputed */
111 * The data structure below keeps summary information about one tag as part
112 * of the tag information in a node.
115 typedef struct Summary {
116 GtkTextTagInfo *info; /* Handle for tag. */
117 int toggle_count; /* Number of transitions into or
118 * out of this tag that occur in
119 * the subtree rooted at this node. */
120 struct Summary *next; /* Next in list of all tags for same
121 * node, or NULL if at end of list. */
125 * The data structure below defines a node in the B-tree.
128 struct _GtkTextBTreeNode {
129 GtkTextBTreeNode *parent; /* Pointer to parent node, or NULL if
130 * this is the root. */
131 GtkTextBTreeNode *next; /* Next in list of siblings with the
132 * same parent node, or NULL for end
134 Summary *summary; /* First in malloc-ed list of info
135 * about tags in this subtree (NULL if
136 * no tag info in the subtree). */
137 int level; /* Level of this node in the B-tree.
138 * 0 refers to the bottom of the tree
139 * (children are lines, not nodes). */
140 union { /* First in linked list of children. */
141 struct _GtkTextBTreeNode *node; /* Used if level > 0. */
142 GtkTextLine *line; /* Used if level == 0. */
144 int num_children; /* Number of children of this node. */
145 int num_lines; /* Total number of lines (leaves) in
146 * the subtree rooted here. */
147 int num_chars; /* Number of chars below here */
154 * Used to store the list of views in our btree
157 typedef struct _BTreeView BTreeView;
161 GtkTextLayout *layout;
167 * And the tree itself
170 struct _GtkTextBTree {
171 GtkTextBTreeNode *root_node; /* Pointer to root of B-tree. */
172 GtkTextTagTable *table;
173 GHashTable *mark_table;
175 GtkTextLineSegment *insert_mark;
176 GtkTextLineSegment *selection_bound_mark;
177 GtkTextBuffer *buffer;
180 guint tag_changed_handler;
181 guint tag_removed_handler;
182 /* Incremented when a segment with a byte size > 0
183 is added to or removed from the tree (i.e. the
184 length of a line may have changed, and lines may
185 have been added or removed). This invalidates
186 all outstanding iterators.
188 guint chars_changed_stamp;
189 /* Incremented when any segments are added or deleted;
190 this makes outstanding iterators recalculate their
191 pointed-to segment and segment offset.
193 guint segments_changed_stamp;
195 GtkTextLine *end_iter_line;
197 guint end_iter_line_stamp;
202 * Upper and lower bounds on how many children a node may have:
203 * rebalance when either of these limits is exceeded. MAX_CHILDREN
204 * should be twice MIN_CHILDREN and MIN_CHILDREN must be >= 2.
207 /* Tk used MAX of 12 and MIN of 6. This makes the tree wide and
208 shallow. It appears to be faster to locate a particular line number
209 if the tree is narrow and deep, since it is more finely sorted. I
210 guess this may increase memory use though, and make it slower to
211 walk the tree in order, or locate a particular byte index (which
212 is done by walking the tree in order).
214 There's basically a tradeoff here. However I'm thinking we want to
215 add pixels, byte counts, and char counts to the tree nodes,
216 at that point narrow and deep should speed up all operations,
217 not just the line number searches.
221 #define MAX_CHILDREN 12
222 #define MIN_CHILDREN 6
224 #define MAX_CHILDREN 6
225 #define MIN_CHILDREN 3
232 static BTreeView *gtk_text_btree_get_view (GtkTextBTree *tree,
234 static void gtk_text_btree_rebalance (GtkTextBTree *tree,
235 GtkTextBTreeNode *node);
236 static GtkTextLine * get_last_line (GtkTextBTree *tree);
237 static void post_insert_fixup (GtkTextBTree *tree,
238 GtkTextLine *insert_line,
239 gint char_count_delta,
240 gint line_count_delta);
241 static void gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
242 GtkTextTagInfo *info,
244 static gboolean gtk_text_btree_node_has_tag (GtkTextBTreeNode *node,
247 static void segments_changed (GtkTextBTree *tree);
248 static void chars_changed (GtkTextBTree *tree);
249 static void summary_list_destroy (Summary *summary);
250 static GtkTextLine *gtk_text_line_new (void);
251 static void gtk_text_line_destroy (GtkTextBTree *tree,
253 static void gtk_text_line_set_parent (GtkTextLine *line,
254 GtkTextBTreeNode *node);
255 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
259 static NodeData *node_data_new (gpointer view_id);
260 static void node_data_destroy (NodeData *nd);
261 static void node_data_list_destroy (NodeData *nd);
262 static NodeData *node_data_find (NodeData *nd,
265 static GtkTextBTreeNode *gtk_text_btree_node_new (void);
266 static void gtk_text_btree_node_invalidate_downward (GtkTextBTreeNode *node);
267 static void gtk_text_btree_node_invalidate_upward (GtkTextBTreeNode *node,
269 static NodeData * gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
271 static NodeData * gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
273 static void gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
276 static void gtk_text_btree_node_remove_view (BTreeView *view,
277 GtkTextBTreeNode *node,
279 static void gtk_text_btree_node_destroy (GtkTextBTree *tree,
280 GtkTextBTreeNode *node);
281 static NodeData * gtk_text_btree_node_ensure_data (GtkTextBTreeNode *node,
283 static void gtk_text_btree_node_remove_data (GtkTextBTreeNode *node,
285 static void gtk_text_btree_node_get_size (GtkTextBTreeNode *node,
289 static GtkTextBTreeNode * gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
290 GtkTextBTreeNode *node2);
291 static void get_tree_bounds (GtkTextBTree *tree,
294 static void tag_changed_cb (GtkTextTagTable *table,
296 gboolean size_changed,
298 static void tag_removed_cb (GtkTextTagTable *table,
301 static void cleanup_line (GtkTextLine *line);
302 static void recompute_node_counts (GtkTextBTree *tree,
303 GtkTextBTreeNode *node);
304 static void inc_count (GtkTextTag *tag,
306 TagInfo *tagInfoPtr);
308 static void summary_destroy (Summary *summary);
310 static void gtk_text_btree_link_segment (GtkTextLineSegment *seg,
311 const GtkTextIter *iter);
312 static void gtk_text_btree_unlink_segment (GtkTextBTree *tree,
313 GtkTextLineSegment *seg,
317 static GtkTextTagInfo *gtk_text_btree_get_tag_info (GtkTextBTree *tree,
319 static GtkTextTagInfo *gtk_text_btree_get_existing_tag_info (GtkTextBTree *tree,
321 static void gtk_text_btree_remove_tag_info (GtkTextBTree *tree,
325 /* Inline thingies */
328 segments_changed(GtkTextBTree *tree)
330 tree->segments_changed_stamp += 1;
334 chars_changed(GtkTextBTree *tree)
336 tree->chars_changed_stamp += 1;
344 gtk_text_btree_new (GtkTextTagTable *table,
345 GtkTextBuffer *buffer)
348 GtkTextBTreeNode *root_node;
349 GtkTextLine *line, *line2;
351 g_return_val_if_fail(GTK_IS_TEXT_TAG_TABLE(table), NULL);
352 g_return_val_if_fail(GTK_IS_TEXT_BUFFER(buffer), NULL);
355 * The tree will initially have two empty lines. The second line
356 * isn't actually part of the tree's contents, but its presence
357 * makes several operations easier. The tree will have one GtkTextBTreeNode,
358 * which is also the root of the tree.
361 /* Create the root node. */
363 root_node = gtk_text_btree_node_new();
365 line = gtk_text_line_new();
366 line2 = gtk_text_line_new();
368 root_node->parent = NULL;
369 root_node->next = NULL;
370 root_node->summary = NULL;
371 root_node->level = 0;
372 root_node->children.line = line;
373 root_node->num_children = 2;
374 root_node->num_lines = 2;
375 root_node->num_chars = 2;
377 line->parent = root_node;
380 line->segments = char_segment_new("\n", 1);
382 line2->parent = root_node;
384 line2->segments = char_segment_new("\n", 1);
386 /* Create the tree itself */
388 tree = g_new0(GtkTextBTree, 1);
389 tree->root_node = root_node;
393 /* Set these to values that are unlikely to be found
394 in random memory garbage. */
395 tree->chars_changed_stamp = 49;
396 tree->segments_changed_stamp = 243;
398 tree->end_iter_line_stamp = tree->chars_changed_stamp - 1;
399 tree->end_iter_line = NULL;
401 gtk_object_ref(GTK_OBJECT(tree->table));
402 gtk_object_sink(GTK_OBJECT(tree->table));
404 tree->tag_changed_handler = gtk_signal_connect(GTK_OBJECT(tree->table),
406 GTK_SIGNAL_FUNC(tag_changed_cb),
409 tree->tag_removed_handler = gtk_signal_connect(GTK_OBJECT(tree->table),
411 GTK_SIGNAL_FUNC(tag_removed_cb),
414 tree->mark_table = g_hash_table_new(g_str_hash, g_str_equal);
416 /* We don't ref the buffer, since the buffer owns us;
417 we'd have some circularity issues. The buffer always
418 lasts longer than the BTree
420 tree->buffer = buffer;
425 gtk_text_btree_get_iter_at_line_char(tree, &start, 0, 0);
429 (GtkTextLineSegment*) gtk_text_btree_set_mark(tree,
436 tree->insert_mark->body.mark.not_deleteable = TRUE;
438 tree->insert_mark->body.mark.visible = TRUE;
440 tree->selection_bound_mark =
441 (GtkTextLineSegment*) gtk_text_btree_set_mark(tree,
448 tree->selection_bound_mark->body.mark.not_deleteable = TRUE;
450 mark_segment_ref(tree->insert_mark);
451 mark_segment_ref(tree->selection_bound_mark);
460 gtk_text_btree_ref (GtkTextBTree *tree)
462 g_return_if_fail(tree != NULL);
463 g_return_if_fail(tree->refcount > 0);
469 mark_destroy_foreach(gpointer key, gpointer value, gpointer user_data)
471 mark_segment_unref(value);
475 gtk_text_btree_unref (GtkTextBTree *tree)
477 g_return_if_fail(tree != NULL);
478 g_return_if_fail(tree->refcount > 0);
482 if (tree->refcount == 0)
484 gtk_text_btree_node_destroy(tree, tree->root_node);
486 g_hash_table_foreach(tree->mark_table,
487 mark_destroy_foreach,
489 g_hash_table_destroy(tree->mark_table);
491 mark_segment_unref(tree->insert_mark);
492 mark_segment_unref(tree->selection_bound_mark);
494 gtk_signal_disconnect(GTK_OBJECT(tree->table),
495 tree->tag_changed_handler);
497 gtk_signal_disconnect(GTK_OBJECT(tree->table),
498 tree->tag_removed_handler);
500 gtk_object_unref(GTK_OBJECT(tree->table));
507 gtk_text_btree_get_buffer (GtkTextBTree *tree)
513 gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
515 return tree->chars_changed_stamp;
519 gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
521 return tree->segments_changed_stamp;
525 gtk_text_btree_segments_changed (GtkTextBTree *tree)
527 g_return_if_fail(tree != NULL);
528 segments_changed(tree);
532 * Indexable segment mutation
536 gtk_text_btree_delete (GtkTextIter *start,
539 GtkTextLineSegment *prev_seg; /* The segment just before the start
540 * of the deletion range. */
541 GtkTextLineSegment *last_seg; /* The segment just after the end
542 * of the deletion range. */
543 GtkTextLineSegment *seg, *next;
544 GtkTextLine *curline;
545 GtkTextBTreeNode *curnode, *node;
547 GtkTextLine *start_line;
548 GtkTextLine *end_line;
549 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
550 gint start_byte_offset;
552 g_return_if_fail(start != NULL);
553 g_return_if_fail(end != NULL);
554 g_return_if_fail(gtk_text_iter_get_btree(start) ==
555 gtk_text_iter_get_btree(end));
557 gtk_text_iter_reorder(start, end);
559 tree = gtk_text_iter_get_btree(start);
563 * The code below is ugly, but it's needed to make sure there
564 * is always a dummy empty line at the end of the text. If the
565 * final newline of the file (just before the dummy line) is being
566 * deleted, then back up index to just before the newline. If
567 * there is a newline just before the first character being deleted,
568 * then back up the first index too, so that an even number of lines
569 * gets deleted. Furthermore, remove any tags that are present on
570 * the newline that isn't going to be deleted after all (this simulates
571 * deleting the newline and then adding a "clean" one back again).
577 line1 = gtk_text_iter_get_line(start);
578 line2 = gtk_text_iter_get_line(end);
580 if (line2 == gtk_text_btree_line_count(tree))
584 GtkTextIter orig_end;
587 gtk_text_iter_prev_char(end);
591 if (gtk_text_iter_get_line_offset(start) == 0 &&
594 gtk_text_iter_prev_char(start);
598 tags = gtk_text_btree_get_tags(end,
606 while (i < array_size)
608 gtk_text_btree_tag(end, &orig_end, tags[i], FALSE);
618 /* Broadcast the need for redisplay before we break the iterators */
619 gtk_text_btree_invalidate_region(tree, start, end);
621 /* Save the byte offset so we can reset the iterators */
622 start_byte_offset = gtk_text_iter_get_line_index(start);
624 start_line = gtk_text_iter_get_text_line(start);
625 end_line = gtk_text_iter_get_text_line(end);
628 * Split the start and end segments, so we have a place
629 * to insert our new text.
631 * Tricky point: split at end first; otherwise the split
632 * at end may invalidate seg and/or prev_seg. This allows
633 * us to avoid invalidating segments for start.
636 last_seg = gtk_text_line_segment_split(end);
637 if (last_seg != NULL)
638 last_seg = last_seg->next;
640 last_seg = end_line->segments;
642 prev_seg = gtk_text_line_segment_split(start);
643 if (prev_seg != NULL)
645 seg = prev_seg->next;
646 prev_seg->next = last_seg;
650 seg = start_line->segments;
651 start_line->segments = last_seg;
654 /* notify iterators that their segments need recomputation,
655 just for robustness. */
656 segments_changed(tree);
659 * Delete all of the segments between prev_seg and last_seg.
662 curline = start_line;
663 curnode = curline->parent;
664 while (seg != last_seg)
670 GtkTextLine *nextline;
673 * We just ran off the end of a line. First find the
674 * next line, then go back to the old line and delete it
675 * (unless it's the starting line for the range).
678 nextline = gtk_text_line_next(curline);
679 if (curline != start_line)
681 if (curnode == start_line->parent)
682 start_line->next = curline->next;
684 curnode->children.line = curline->next;
686 for (node = curnode; node != NULL;
689 node->num_lines -= 1;
692 curnode->num_children -= 1;
693 curline->next = deleted_lines;
694 deleted_lines = curline;
698 seg = curline->segments;
701 * If the GtkTextBTreeNode is empty then delete it and its parents,
702 * recursively upwards until a non-empty GtkTextBTreeNode is found.
705 while (curnode->num_children == 0)
707 GtkTextBTreeNode *parent;
709 parent = curnode->parent;
710 if (parent->children.node == curnode)
712 parent->children.node = curnode->next;
716 GtkTextBTreeNode *prevnode = parent->children.node;
717 while (prevnode->next != curnode)
719 prevnode = prevnode->next;
721 prevnode->next = curnode->next;
723 parent->num_children--;
727 curnode = curline->parent;
732 char_count = seg->char_count;
734 if ((*seg->type->deleteFunc)(seg, curline, 0) != 0)
737 * This segment refuses to die. Move it to prev_seg and
738 * advance prev_seg if the segment has left gravity.
741 if (prev_seg == NULL)
743 seg->next = start_line->segments;
744 start_line->segments = seg;
748 seg->next = prev_seg->next;
749 prev_seg->next = seg;
751 if (seg->type->leftGravity)
758 /* Segment is gone. Decrement the char count of the node and
760 for (node = curnode; node != NULL;
763 node->num_chars -= char_count;
771 * If the beginning and end of the deletion range are in different
772 * lines, join the two lines together and discard the ending line.
775 if (start_line != end_line)
778 GtkTextBTreeNode *ancestor_node;
780 GtkTextLine *prevline;
782 for (seg = last_seg; seg != NULL;
785 if (seg->type->lineChangeFunc != NULL)
787 (*seg->type->lineChangeFunc)(seg, end_line);
790 curnode = end_line->parent;
791 for (node = curnode; node != NULL;
796 curnode->num_children--;
797 prevline = curnode->children.line;
798 if (prevline == end_line)
800 curnode->children.line = end_line->next;
804 while (prevline->next != end_line)
806 prevline = prevline->next;
808 prevline->next = end_line->next;
810 end_line->next = deleted_lines;
811 deleted_lines = end_line;
813 /* We now fix up the per-view aggregates. We add all the height and
814 * width for the deleted lines to the start line, so that when revalidation
815 * occurs, the correct change in size is seen.
817 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
824 gint deleted_width = 0;
825 gint deleted_height = 0;
827 line = deleted_lines;
830 GtkTextLine *next_line = line->next;
831 ld = gtk_text_line_get_data (line, view->view_id);
835 deleted_width = MAX (deleted_width, ld->width);
836 deleted_height += ld->height;
840 gtk_text_line_destroy(tree, line);
845 if (deleted_width > 0 || deleted_height > 0)
847 ld = gtk_text_line_get_data (start_line, view->view_id);
849 /* FIXME: ld is _NOT_ necessarily non-null here, but there is currently
850 * no way to add ld without also validating the node, which would
851 * be improper at this point.
853 /* This assertion does actually fail sometimes, must
854 fix before stable release -hp */
857 ld->width = MAX (deleted_width, ld->width);
858 ld->height += deleted_height;
862 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
863 if (ancestor_node->parent)
864 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
869 gtk_text_btree_rebalance(tree, curnode);
873 * Cleanup the segments in the new line.
876 cleanup_line(start_line);
879 * Lastly, rebalance the first GtkTextBTreeNode of the range.
882 gtk_text_btree_rebalance(tree, start_line->parent);
884 /* Notify outstanding iterators that they
887 segments_changed(tree);
889 if (gtk_debug_flags & GTK_DEBUG_TEXT)
890 gtk_text_btree_check(tree);
892 /* Re-initialize our iterators */
893 gtk_text_btree_get_iter_at_line(tree, start, start_line, start_byte_offset);
898 gtk_text_btree_insert (GtkTextIter *iter,
902 GtkTextLineSegment *prev_seg; /* The segment just before the first
903 * new segment (NULL means new segment
904 * is at beginning of line). */
905 GtkTextLineSegment *cur_seg; /* Current segment; new characters
906 * are inserted just after this one.
907 * NULL means insert at beginning of
909 GtkTextLine *line; /* Current line (new segments are
910 * added to this line). */
911 GtkTextLineSegment *seg;
912 GtkTextLine *newline;
913 int chunkSize; /* # characters in current chunk. */
914 guint sol; /* start of line */
915 guint eol; /* Pointer to character just after last
916 * one in current chunk. */
917 int line_count_delta; /* Counts change to total number of
920 int char_count_delta; /* change to number of chars */
922 gint start_byte_index;
923 GtkTextLine *start_line;
925 g_return_if_fail(text != NULL);
926 g_return_if_fail(iter != NULL);
931 /* extract iterator info */
932 tree = gtk_text_iter_get_btree(iter);
933 line = gtk_text_iter_get_text_line(iter);
935 start_byte_index = gtk_text_iter_get_line_index(iter);
937 /* Get our insertion segment split */
938 prev_seg = gtk_text_line_segment_split(iter);
941 /* Invalidate all iterators */
943 segments_changed(tree);
946 * Chop the text up into lines and create a new segment for
947 * each line, plus a new line for the leftovers from the
953 line_count_delta = 0;
954 char_count_delta = 0;
957 for (; eol < len; eol++)
959 if (text[eol] == '\n')
965 chunkSize = eol - sol;
967 seg = char_segment_new(&text[sol], chunkSize);
969 char_count_delta += seg->char_count;
973 seg->next = line->segments;
974 line->segments = seg;
978 seg->next = cur_seg->next;
982 if (text[eol-1] != '\n')
988 * The chunk ended with a newline, so create a new GtkTextLine
989 * and move the remainder of the old line to it.
992 newline = gtk_text_line_new();
993 gtk_text_line_set_parent(newline, line->parent);
994 newline->next = line->next;
995 line->next = newline;
996 newline->segments = seg->next;
1006 * Cleanup the starting line for the insertion, plus the ending
1007 * line if it's different.
1010 cleanup_line(start_line);
1011 if (line != start_line)
1016 post_insert_fixup(tree, line, line_count_delta, char_count_delta);
1018 /* Invalidate our region, and reset the iterator the user
1019 passed in to point to the end of the inserted text. */
1025 gtk_text_btree_get_iter_at_line(tree,
1031 /* We could almost certainly be more efficient here
1032 by saving the information from the insertion loop
1034 gtk_text_iter_forward_chars(&end, char_count_delta);
1036 gtk_text_btree_invalidate_region(tree,
1040 /* Convenience for the user */
1046 gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1049 GtkTextLineSegment *seg;
1051 GtkTextLineSegment *prevPtr;
1054 gint start_byte_offset;
1056 line = gtk_text_iter_get_text_line(iter);
1057 tree = gtk_text_iter_get_btree(iter);
1058 start_byte_offset = gtk_text_iter_get_line_index(iter);
1060 seg = gtk_text_pixbuf_segment_new (pixbuf);
1062 prevPtr = gtk_text_line_segment_split(iter);
1063 if (prevPtr == NULL)
1065 seg->next = line->segments;
1066 line->segments = seg;
1070 seg->next = prevPtr->next;
1071 prevPtr->next = seg;
1074 post_insert_fixup(tree, line, 0, seg->char_count);
1076 chars_changed(tree);
1077 segments_changed(tree);
1079 /* reset *iter for the user, and invalidate tree nodes */
1081 gtk_text_btree_get_iter_at_line(tree, &start, line, start_byte_offset);
1084 gtk_text_iter_next_char(iter); /* skip forward past the pixmap */
1086 gtk_text_btree_invalidate_region(tree, &start, iter);
1095 find_line_by_y(GtkTextBTree *tree, BTreeView *view,
1096 GtkTextBTreeNode *node, gint y, gint *line_top,
1097 GtkTextLine *last_line)
1101 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1102 gtk_text_btree_check(tree);
1104 if (node->level == 0)
1108 line = node->children.line;
1110 while (line != NULL && line != last_line)
1112 GtkTextLineData *ld;
1114 ld = gtk_text_line_get_data (line, view->view_id);
1118 if (y < (current_y + (ld ? ld->height : 0)))
1121 current_y += ld->height;
1122 *line_top += ld->height;
1131 GtkTextBTreeNode *child;
1133 child = node->children.node;
1135 while (child != NULL)
1140 gtk_text_btree_node_get_size(child, view->view_id,
1143 if (y < (current_y + height))
1144 return find_line_by_y(tree, view, child,
1145 y - current_y, line_top,
1148 current_y += height;
1149 *line_top += height;
1151 child = child->next;
1159 gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1166 GtkTextLine *last_line;
1169 view = gtk_text_btree_get_view (tree, view_id);
1170 g_return_val_if_fail (view != NULL, NULL);
1172 last_line = get_last_line (tree);
1174 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1178 *line_top_out = line_top;
1184 find_line_top_in_line_list(GtkTextBTree *tree,
1187 GtkTextLine *target_line,
1190 while (line != NULL)
1192 GtkTextLineData *ld;
1194 if (line == target_line)
1197 ld = gtk_text_line_get_data (line, view->view_id);
1204 g_assert_not_reached(); /* If we get here, our
1205 target line didn't exist
1206 under its parent node */
1211 gtk_text_btree_find_line_top (GtkTextBTree *tree,
1212 GtkTextLine *target_line,
1219 GtkTextBTreeNode *node;
1221 view = gtk_text_btree_get_view(tree, view_id);
1223 g_return_val_if_fail(view != NULL, 0);
1226 node = target_line->parent;
1227 while (node != NULL)
1229 nodes = g_slist_prepend(nodes, node);
1230 node = node->parent;
1234 while (iter != NULL)
1238 if (node->level == 0)
1240 g_slist_free(nodes);
1241 return find_line_top_in_line_list(tree, view,
1242 node->children.line,
1247 GtkTextBTreeNode *child;
1248 GtkTextBTreeNode *target_node;
1250 g_assert(iter->next != NULL); /* not at level 0 */
1251 target_node = iter->next->data;
1253 child = node->children.node;
1255 while (child != NULL)
1260 if (child == target_node)
1264 gtk_text_btree_node_get_size(child, view->view_id,
1268 child = child->next;
1270 g_assert(child != NULL); /* should have broken out before we
1274 iter = g_slist_next(iter);
1277 g_assert_not_reached(); /* we return when we find the target line */
1282 gtk_text_btree_add_view (GtkTextBTree *tree,
1283 GtkTextLayout *layout)
1286 GtkTextLine *last_line;
1287 GtkTextLineData *line_data;
1289 g_return_if_fail(tree != NULL);
1291 view = g_new(BTreeView, 1);
1293 view->view_id = layout;
1294 view->layout = layout;
1296 view->next = tree->views;
1301 /* The last line in the buffer has identity values for the per-view
1302 * data so that we can avoid special case checks for it in a large
1305 last_line = get_last_line (tree);
1307 line_data = g_new (GtkTextLineData, 1);
1308 line_data->view_id = layout;
1309 line_data->next = NULL;
1310 line_data->width = 0;
1311 line_data->height = 0;
1312 line_data->valid = TRUE;
1314 gtk_text_line_add_data (last_line, line_data);
1318 gtk_text_btree_remove_view (GtkTextBTree *tree,
1322 GtkTextLine *last_line;
1323 GtkTextLineData *line_data;
1325 g_return_if_fail(tree != NULL);
1329 while (view != NULL)
1331 if (view->view_id == view_id)
1337 g_return_if_fail(view != NULL);
1340 view->next->prev = view->prev;
1343 view->prev->next = view->next;
1345 if (view == tree->views)
1346 tree->views = view->next;
1348 /* Remove the line data for the last line which we added ourselves.
1349 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1351 last_line = get_last_line (tree);
1352 line_data = gtk_text_line_remove_data (last_line, view_id);
1355 gtk_text_btree_node_remove_view(view, tree->root_node, view_id);
1361 gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1362 const GtkTextIter *start,
1363 const GtkTextIter *end)
1369 while (view != NULL)
1371 gtk_text_layout_invalidate(view->layout, start, end);
1378 gtk_text_btree_get_view_size (GtkTextBTree *tree,
1383 g_return_if_fail(tree != NULL);
1384 g_return_if_fail(view_id != NULL);
1386 gtk_text_btree_node_get_size(tree->root_node, view_id,
1401 iter_stack_new(void)
1404 stack = g_new(IterStack, 1);
1405 stack->iters = NULL;
1412 iter_stack_push(IterStack *stack, const GtkTextIter *iter)
1415 if (stack->count > stack->alloced)
1417 stack->alloced = stack->count*2;
1418 stack->iters = g_realloc(stack->iters,
1419 stack->alloced*sizeof(GtkTextIter));
1421 stack->iters[stack->count-1] = *iter;
1425 iter_stack_pop(IterStack *stack, GtkTextIter *iter)
1427 if (stack->count == 0)
1432 *iter = stack->iters[stack->count];
1438 iter_stack_free(IterStack *stack)
1440 g_free(stack->iters);
1445 iter_stack_invert(IterStack *stack)
1447 if (stack->count > 0)
1450 guint j = stack->count - 1;
1455 tmp = stack->iters[i];
1456 stack->iters[i] = stack->iters[j];
1457 stack->iters[j] = tmp;
1466 gtk_text_btree_tag (const GtkTextIter *start_orig,
1467 const GtkTextIter *end_orig,
1471 GtkTextLineSegment *seg, *prev;
1472 GtkTextLine *cleanupline;
1473 gboolean toggled_on;
1474 GtkTextLine *start_line;
1475 GtkTextLine *end_line;
1477 GtkTextIter start, end;
1480 GtkTextTagInfo *info;
1482 g_return_if_fail(start_orig != NULL);
1483 g_return_if_fail(end_orig != NULL);
1484 g_return_if_fail(GTK_IS_TEXT_TAG(tag));
1485 g_return_if_fail(gtk_text_iter_get_btree(start_orig) ==
1486 gtk_text_iter_get_btree(end_orig));
1489 printf("%s tag %s from %d to %d\n",
1490 add ? "Adding" : "Removing",
1492 gtk_text_buffer_get_offset(start_orig),
1493 gtk_text_buffer_get_offset(end_orig));
1496 if (gtk_text_iter_equal(start_orig, end_orig))
1499 start = *start_orig;
1502 gtk_text_iter_reorder(&start, &end);
1504 tree = gtk_text_iter_get_btree(&start);
1506 info = gtk_text_btree_get_tag_info(tree, tag);
1508 start_line = gtk_text_iter_get_text_line(&start);
1509 end_line = gtk_text_iter_get_text_line(&end);
1511 /* Find all tag toggles in the region; we are going to delete them.
1512 We need to find them in advance, because
1513 forward_find_tag_toggle() won't work once we start playing around
1515 stack = iter_stack_new();
1517 /* We don't want to delete a toggle that's at the start iterator. */
1518 gtk_text_iter_next_char(&iter);
1519 while (gtk_text_iter_forward_to_tag_toggle(&iter, tag))
1521 if (gtk_text_iter_compare(&iter, &end) >= 0)
1524 iter_stack_push(stack, &iter);
1527 /* We need to traverse the toggles in order. */
1528 iter_stack_invert(stack);
1531 * See whether the tag is present at the start of the range. If
1532 * the state doesn't already match what we want then add a toggle
1536 toggled_on = gtk_text_iter_has_tag(&start, tag);
1537 if ( (add && !toggled_on) ||
1538 (!add && toggled_on) )
1540 /* This could create a second toggle at the start position;
1541 cleanup_line() will remove it if so. */
1542 seg = toggle_segment_new(info, add);
1544 prev = gtk_text_line_segment_split(&start);
1547 seg->next = start_line->segments;
1548 start_line->segments = seg;
1552 seg->next = prev->next;
1556 /* cleanup_line adds the new toggle to the node counts. */
1558 printf("added toggle at start\n");
1560 /* we should probably call segments_changed, but in theory
1561 any still-cached segments in the iters we are about to
1562 use are still valid, since they're in front
1568 * Scan the range of characters and delete any internal tag
1569 * transitions. Keep track of what the old state was at the end
1570 * of the range, and add a toggle there if it's needed.
1574 cleanupline = start_line;
1575 while (iter_stack_pop(stack, &iter))
1577 GtkTextLineSegment *indexable_seg;
1580 line = gtk_text_iter_get_text_line(&iter);
1581 seg = gtk_text_iter_get_any_segment(&iter);
1582 indexable_seg = gtk_text_iter_get_indexable_segment(&iter);
1584 g_assert(seg != NULL);
1585 g_assert(indexable_seg != NULL);
1586 g_assert(seg != indexable_seg);
1588 prev = line->segments;
1590 /* Find the segment that actually toggles this tag. */
1591 while (seg != indexable_seg)
1593 g_assert(seg != NULL);
1594 g_assert(indexable_seg != NULL);
1595 g_assert(seg != indexable_seg);
1597 if ( (seg->type == >k_text_toggle_on_type ||
1598 seg->type == >k_text_toggle_off_type) &&
1599 (seg->body.toggle.info == info) )
1605 g_assert(seg != NULL);
1606 g_assert(indexable_seg != NULL);
1608 g_assert(seg != indexable_seg); /* If this happens, then
1609 forward_to_tag_toggle was
1611 g_assert(seg->body.toggle.info->tag == tag);
1613 /* If this happens, when previously tagging we didn't merge
1614 overlapping tags. */
1615 g_assert( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1616 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1618 toggled_on = !toggled_on;
1621 printf("deleting %s toggle\n",
1622 seg->type == >k_text_toggle_on_type ? "on" : "off");
1624 /* Remove toggle segment from the list. */
1627 line->segments = seg->next;
1631 while (prev->next != seg)
1635 prev->next = seg->next;
1638 /* Inform iterators we've hosed them. This actually reflects a
1639 bit of inefficiency; if you have the same tag toggled on and
1640 off a lot in a single line, we keep having the rescan from
1641 the front of the line. Of course we have to do that to get
1642 "prev" anyway, but here we are doing it an additional
1644 segments_changed(tree);
1646 /* Update node counts */
1647 if (seg->body.toggle.inNodeCounts)
1649 change_node_toggle_count(line->parent,
1651 seg->body.toggle.inNodeCounts = FALSE;
1656 /* We only clean up lines when we're done with them, saves some
1657 gratuitous line-segment-traversals */
1659 if (cleanupline != line)
1661 cleanup_line(cleanupline);
1666 iter_stack_free(stack);
1668 /* toggled_on now reflects the toggle state _just before_ the
1669 end iterator. The end iterator could already have a toggle
1670 on or a toggle off. */
1671 if ( (add && !toggled_on) ||
1672 (!add && toggled_on) )
1674 /* This could create a second toggle at the start position;
1675 cleanup_line() will remove it if so. */
1677 seg = toggle_segment_new(info, !add);
1679 prev = gtk_text_line_segment_split(&end);
1682 seg->next = end_line->segments;
1683 end_line->segments = seg;
1687 seg->next = prev->next;
1690 /* cleanup_line adds the new toggle to the node counts. */
1691 g_assert(seg->body.toggle.inNodeCounts == FALSE);
1693 printf("added toggle at end\n");
1698 * Cleanup cleanupline and the last line of the range, if
1699 * these are different.
1702 cleanup_line(cleanupline);
1703 if (cleanupline != end_line)
1705 cleanup_line(end_line);
1708 segments_changed(tree);
1710 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1711 gtk_text_btree_check(tree);
1720 gtk_text_btree_get_line (GtkTextBTree *tree,
1722 gint *real_line_number)
1724 GtkTextBTreeNode *node;
1729 line_count = gtk_text_btree_line_count(tree);
1731 if (line_number < 0)
1733 line_number = line_count;
1735 else if (line_number > line_count)
1737 line_number = line_count;
1740 if (real_line_number)
1741 *real_line_number = line_number;
1743 node = tree->root_node;
1744 lines_left = line_number;
1747 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1751 while (node->level != 0)
1753 for (node = node->children.node;
1754 node->num_lines <= lines_left;
1760 g_error("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1763 lines_left -= node->num_lines;
1768 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1771 for (line = node->children.line; lines_left > 0;
1777 g_error("gtk_text_btree_find_line ran out of lines");
1786 gtk_text_btree_get_line_at_char(GtkTextBTree *tree,
1788 gint *line_start_index,
1789 gint *real_char_index)
1791 GtkTextBTreeNode *node;
1793 GtkTextLineSegment *seg;
1798 node = tree->root_node;
1800 /* Clamp to valid indexes (-1 is magic for "highest index") */
1801 if (char_index < 0 || char_index >= node->num_chars)
1803 char_index = node->num_chars - 1;
1806 *real_char_index = char_index;
1809 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1813 chars_left = char_index;
1814 while (node->level != 0)
1816 for (node = node->children.node;
1817 chars_left >= node->num_chars;
1820 chars_left -= node->num_chars;
1822 g_assert(chars_left >= 0);
1826 if (chars_left == 0)
1828 /* Start of a line */
1830 *line_start_index = char_index;
1831 return node->children.line;
1835 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1841 for (line = node->children.line; line != NULL; line = line->next)
1843 seg = line->segments;
1846 if (chars_in_line + seg->char_count > chars_left)
1847 goto found; /* found our line/segment */
1849 chars_in_line += seg->char_count;
1854 chars_left -= chars_in_line;
1862 g_assert(line != NULL); /* hosage, ran out of lines */
1863 g_assert(seg != NULL);
1865 *line_start_index = char_index - chars_left;
1870 gtk_text_btree_get_tags (const GtkTextIter *iter,
1873 GtkTextBTreeNode *node;
1874 GtkTextLine *siblingline;
1875 GtkTextLineSegment *seg;
1876 int src, dst, index;
1882 #define NUM_TAG_INFOS 10
1884 line = gtk_text_iter_get_text_line(iter);
1885 tree = gtk_text_iter_get_btree(iter);
1886 byte_index = gtk_text_iter_get_line_index(iter);
1888 tagInfo.numTags = 0;
1889 tagInfo.arraySize = NUM_TAG_INFOS;
1890 tagInfo.tags = g_new(GtkTextTag*, NUM_TAG_INFOS);
1891 tagInfo.counts = g_new(int, NUM_TAG_INFOS);
1894 * Record tag toggles within the line of indexPtr but preceding
1895 * indexPtr. Note that if this loop segfaults, your
1896 * byte_index probably points past the sum of all
1897 * seg->byte_count */
1899 for (index = 0, seg = line->segments;
1900 (index + seg->byte_count) <= byte_index;
1901 index += seg->byte_count, seg = seg->next)
1903 if ((seg->type == >k_text_toggle_on_type)
1904 || (seg->type == >k_text_toggle_off_type))
1906 inc_count(seg->body.toggle.info->tag, 1, &tagInfo);
1911 * Record toggles for tags in lines that are predecessors of
1912 * line but under the same level-0 GtkTextBTreeNode.
1915 for (siblingline = line->parent->children.line;
1916 siblingline != line;
1917 siblingline = siblingline->next)
1919 for (seg = siblingline->segments; seg != NULL;
1922 if ((seg->type == >k_text_toggle_on_type)
1923 || (seg->type == >k_text_toggle_off_type))
1925 inc_count(seg->body.toggle.info->tag, 1, &tagInfo);
1931 * For each GtkTextBTreeNode in the ancestry of this line, record tag
1932 * toggles for all siblings that precede that GtkTextBTreeNode.
1935 for (node = line->parent; node->parent != NULL;
1936 node = node->parent)
1938 GtkTextBTreeNode *siblingPtr;
1941 for (siblingPtr = node->parent->children.node;
1942 siblingPtr != node; siblingPtr = siblingPtr->next)
1944 for (summary = siblingPtr->summary; summary != NULL;
1945 summary = summary->next)
1947 if (summary->toggle_count & 1)
1949 inc_count(summary->info->tag, summary->toggle_count,
1957 * Go through the tag information and squash out all of the tags
1958 * that have even toggle counts (these tags exist before the point
1959 * of interest, but not at the desired character itself).
1962 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
1964 if (tagInfo.counts[src] & 1)
1966 g_assert(GTK_IS_TEXT_TAG(tagInfo.tags[src]));
1967 tagInfo.tags[dst] = tagInfo.tags[src];
1973 g_free(tagInfo.counts);
1976 g_free(tagInfo.tags);
1979 return tagInfo.tags;
1983 copy_segment(GString *string,
1984 gboolean include_hidden,
1985 gboolean include_nonchars,
1986 const GtkTextIter *start,
1987 const GtkTextIter *end)
1989 GtkTextLineSegment *end_seg;
1990 GtkTextLineSegment *seg;
1992 if (gtk_text_iter_equal(start, end))
1995 seg = gtk_text_iter_get_indexable_segment(start);
1996 end_seg = gtk_text_iter_get_indexable_segment(end);
1998 if (seg->type == >k_text_char_type)
2000 gboolean copy = TRUE;
2001 gint copy_bytes = 0;
2002 gint copy_start = 0;
2004 /* Don't copy if we're invisible; segments are invisible/not
2005 as a whole, no need to check each char */
2006 if (!include_hidden &&
2007 gtk_text_btree_char_is_invisible(start))
2010 /* printf(" <invisible>\n"); */
2013 copy_start = gtk_text_iter_get_segment_byte(start);
2017 /* End is in the same segment; need to copy fewer bytes. */
2018 gint end_byte = gtk_text_iter_get_segment_byte(end);
2020 copy_bytes = end_byte - copy_start;
2023 copy_bytes = seg->byte_count - copy_start;
2025 g_assert(copy_bytes != 0); /* Due to iter equality check at
2026 front of this function. */
2030 g_assert((copy_start + copy_bytes) <= seg->byte_count);
2032 g_string_append_len(string,
2033 seg->body.chars + copy_start,
2037 /* printf(" :%s\n", string->str); */
2039 else if (seg->type == >k_text_pixbuf_type)
2041 gboolean copy = TRUE;
2043 if (!include_nonchars)
2047 else if (!include_hidden &&
2048 gtk_text_btree_char_is_invisible(start))
2055 g_string_append_len(string,
2056 gtk_text_unknown_char_utf8,
2064 gtk_text_btree_get_text (const GtkTextIter *start_orig,
2065 const GtkTextIter *end_orig,
2066 gboolean include_hidden,
2067 gboolean include_nonchars)
2069 GtkTextLineSegment *seg;
2070 GtkTextLineSegment *end_seg;
2078 g_return_val_if_fail(start_orig != NULL, NULL);
2079 g_return_val_if_fail(end_orig != NULL, NULL);
2080 g_return_val_if_fail(gtk_text_iter_get_btree(start_orig) ==
2081 gtk_text_iter_get_btree(end_orig), NULL);
2083 start = *start_orig;
2086 gtk_text_iter_reorder(&start, &end);
2088 retval = g_string_new("");
2090 tree = gtk_text_iter_get_btree(&start);
2092 end_seg = gtk_text_iter_get_indexable_segment(&end);
2094 seg = gtk_text_iter_get_indexable_segment(&iter);
2095 while (seg != end_seg)
2097 copy_segment(retval, include_hidden, include_nonchars,
2100 gtk_text_iter_forward_indexable_segment(&iter);
2102 seg = gtk_text_iter_get_indexable_segment(&iter);
2105 copy_segment(retval, include_hidden, include_nonchars, &iter, &end);
2108 g_string_free(retval, FALSE);
2113 gtk_text_btree_line_count (GtkTextBTree *tree)
2115 /* Subtract bogus line at the end; we return a count
2117 return tree->root_node->num_lines - 1;
2121 gtk_text_btree_char_count (GtkTextBTree *tree)
2123 /* Exclude newline in bogus last line */
2124 return tree->root_node->num_chars - 1;
2127 #define LOTSA_TAGS 1000
2129 gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2131 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2133 int deftagCnts[LOTSA_TAGS];
2134 int *tagCnts = deftagCnts;
2135 GtkTextTag *deftags[LOTSA_TAGS];
2136 GtkTextTag **tags = deftags;
2138 GtkTextBTreeNode *node;
2139 GtkTextLine *siblingline;
2140 GtkTextLineSegment *seg;
2147 line = gtk_text_iter_get_text_line(iter);
2148 tree = gtk_text_iter_get_btree(iter);
2149 byte_index = gtk_text_iter_get_line_index(iter);
2151 numTags = gtk_text_tag_table_size(tree->table);
2153 /* almost always avoid malloc, so stay out of system calls */
2154 if (LOTSA_TAGS < numTags)
2156 tagCnts = g_new(int, numTags);
2157 tags = g_new(GtkTextTag*, numTags);
2160 for (i=0; i<numTags; i++)
2166 * Record tag toggles within the line of indexPtr but preceding
2170 for (index = 0, seg = line->segments;
2171 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2172 index += seg->byte_count, seg = seg->next)
2174 if ((seg->type == >k_text_toggle_on_type)
2175 || (seg->type == >k_text_toggle_off_type))
2177 tag = seg->body.toggle.info->tag;
2178 if (tag->invisible_set && tag->values->invisible)
2180 tags[tag->priority] = tag;
2181 tagCnts[tag->priority]++;
2187 * Record toggles for tags in lines that are predecessors of
2188 * line but under the same level-0 GtkTextBTreeNode.
2191 for (siblingline = line->parent->children.line;
2192 siblingline != line;
2193 siblingline = siblingline->next)
2195 for (seg = siblingline->segments; seg != NULL;
2198 if ((seg->type == >k_text_toggle_on_type)
2199 || (seg->type == >k_text_toggle_off_type))
2201 tag = seg->body.toggle.info->tag;
2202 if (tag->invisible_set && tag->values->invisible)
2204 tags[tag->priority] = tag;
2205 tagCnts[tag->priority]++;
2212 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2213 * for all siblings that precede that GtkTextBTreeNode.
2216 for (node = line->parent; node->parent != NULL;
2217 node = node->parent)
2219 GtkTextBTreeNode *siblingPtr;
2222 for (siblingPtr = node->parent->children.node;
2223 siblingPtr != node; siblingPtr = siblingPtr->next)
2225 for (summary = siblingPtr->summary; summary != NULL;
2226 summary = summary->next)
2228 if (summary->toggle_count & 1)
2230 tag = summary->info->tag;
2231 if (tag->invisible_set && tag->values->invisible)
2233 tags[tag->priority] = tag;
2234 tagCnts[tag->priority] += summary->toggle_count;
2242 * Now traverse from highest priority to lowest,
2243 * take invisible value from first odd count (= on)
2246 for (i = numTags-1; i >=0; i--)
2250 /* FIXME not sure this should be if 0 */
2252 #ifndef ALWAYS_SHOW_SELECTION
2253 /* who would make the selection invisible? */
2254 if ((tag == tkxt->seltag)
2255 && !(tkxt->flags & GOT_FOCUS))
2261 invisible = tags[i]->values->invisible;
2266 if (LOTSA_TAGS < numTags)
2281 redisplay_region (GtkTextBTree *tree,
2282 const GtkTextIter *start,
2283 const GtkTextIter *end)
2286 GtkTextLine *start_line, *end_line;
2288 if (gtk_text_iter_compare (start, end) > 0)
2290 const GtkTextIter *tmp = start;
2295 start_line = gtk_text_iter_get_text_line (start);
2296 end_line = gtk_text_iter_get_text_line (end);
2299 while (view != NULL)
2301 gint start_y, end_y;
2302 GtkTextLineData *ld;
2304 start_y = gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2306 if (end_line == start_line)
2309 end_y = gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2311 ld = gtk_text_line_get_data (end_line, view->view_id);
2313 end_y += ld->height;
2315 gtk_text_layout_changed (view->layout, start_y, end_y - start_y, end_y - start_y);
2322 redisplay_mark(GtkTextLineSegment *mark)
2327 gtk_text_btree_get_iter_at_mark(mark->body.mark.tree,
2329 (GtkTextMark*)mark);
2332 gtk_text_iter_next_char(&end);
2334 gtk_text_btree_invalidate_region(mark->body.mark.tree,
2339 redisplay_mark_if_visible(GtkTextLineSegment *mark)
2341 if (!mark->body.mark.visible)
2344 redisplay_mark(mark);
2348 ensure_not_off_end(GtkTextBTree *tree,
2349 GtkTextLineSegment *mark,
2352 if (gtk_text_iter_get_line(iter) ==
2353 gtk_text_btree_line_count(tree))
2354 gtk_text_iter_prev_char(iter);
2357 static GtkTextLineSegment*
2358 real_set_mark(GtkTextBTree *tree,
2359 GtkTextMark *existing_mark,
2361 gboolean left_gravity,
2362 const GtkTextIter *where,
2363 gboolean should_exist,
2364 gboolean redraw_selections)
2366 GtkTextLineSegment *mark;
2369 g_return_val_if_fail(tree != NULL, NULL);
2370 g_return_val_if_fail(where != NULL, NULL);
2371 g_return_val_if_fail(gtk_text_iter_get_btree(where) == tree, NULL);
2374 mark = (GtkTextLineSegment*) existing_mark;
2375 else if (name != NULL)
2376 mark = g_hash_table_lookup(tree->mark_table,
2381 if (should_exist && mark == NULL)
2383 g_warning("No mark `%s' exists!", name);
2387 /* OK if !should_exist and it does already exist, in that case
2394 if (redraw_selections &&
2395 (mark == tree->insert_mark ||
2396 mark == tree->selection_bound_mark))
2398 GtkTextIter old_pos;
2400 gtk_text_btree_get_iter_at_mark (tree, &old_pos, (GtkTextMark*)mark);
2401 redisplay_region (tree, &old_pos, where);
2405 * don't let visible marks be after the final newline of the
2409 if (mark->body.mark.visible)
2411 ensure_not_off_end(tree, mark, &iter);
2414 /* Redraw the mark's old location. */
2415 redisplay_mark_if_visible(mark);
2417 /* Unlink mark from its current location.
2418 This could hose our iterator... */
2419 gtk_text_btree_unlink_segment(tree, mark,
2420 mark->body.mark.line);
2421 mark->body.mark.line = gtk_text_iter_get_text_line(&iter);
2422 g_assert(mark->body.mark.line == gtk_text_iter_get_text_line(&iter));
2424 segments_changed(tree); /* make sure the iterator recomputes its
2429 mark = mark_segment_new(tree,
2433 mark->body.mark.line = gtk_text_iter_get_text_line(&iter);
2435 if (mark->body.mark.name)
2436 g_hash_table_insert(tree->mark_table,
2437 mark->body.mark.name,
2441 /* Link mark into new location */
2442 gtk_text_btree_link_segment(mark, &iter);
2444 /* Invalidate some iterators. */
2445 segments_changed(tree);
2448 * update the screen at the mark's new location.
2451 redisplay_mark_if_visible(mark);
2458 gtk_text_btree_set_mark (GtkTextBTree *tree,
2459 GtkTextMark *existing_mark,
2461 gboolean left_gravity,
2462 const GtkTextIter *iter,
2463 gboolean should_exist)
2465 return (GtkTextMark*)real_set_mark(tree, existing_mark,
2466 name, left_gravity, iter, should_exist,
2471 gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2475 GtkTextIter tmp_start, tmp_end;
2477 gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2478 (GtkTextMark*)tree->insert_mark);
2479 gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2480 (GtkTextMark*)tree->selection_bound_mark);
2482 if (gtk_text_iter_equal(&tmp_start, &tmp_end))
2492 gtk_text_iter_reorder(&tmp_start, &tmp_end);
2505 gtk_text_btree_place_cursor(GtkTextBTree *tree,
2506 const GtkTextIter *iter)
2508 GtkTextIter start, end;
2510 if (gtk_text_btree_get_selection_bounds (tree, &start, &end))
2511 redisplay_region(tree, &start, &end);
2513 /* Move insert AND selection_bound before we redisplay */
2514 real_set_mark(tree, (GtkTextMark*) tree->insert_mark,
2515 "insert", FALSE, iter, TRUE, FALSE);
2516 real_set_mark(tree, (GtkTextMark*) tree->selection_bound_mark,
2517 "selection_bound", FALSE, iter, TRUE, FALSE);
2521 gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2526 g_return_if_fail(tree != NULL);
2527 g_return_if_fail(name != NULL);
2529 mark = g_hash_table_lookup(tree->mark_table,
2532 gtk_text_btree_remove_mark(tree, mark);
2536 gtk_text_btree_remove_mark (GtkTextBTree *tree,
2539 GtkTextLineSegment *segment = (GtkTextLineSegment*) mark;
2541 g_return_if_fail (segment != NULL);
2542 g_return_if_fail (tree != NULL);
2544 if (segment->body.mark.not_deleteable)
2546 g_warning("Can't delete special mark `%s'", segment->body.mark.name);
2550 /* This calls cleanup_line and segments_changed */
2551 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2553 if (segment->body.mark.name)
2554 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2556 mark_segment_unref (segment);
2558 segment->body.mark.tree = NULL;
2559 segment->body.mark.line = NULL;
2563 gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2564 GtkTextMark *segment)
2566 return segment == (GtkTextMark*) tree->insert_mark;
2570 gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2571 GtkTextMark *segment)
2573 return segment == (GtkTextMark*) tree->selection_bound_mark;
2577 gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2580 g_return_val_if_fail(tree != NULL, NULL);
2581 g_return_val_if_fail(name != NULL, NULL);
2583 return g_hash_table_lookup(tree->mark_table, name);
2587 gtk_text_mark_set_visible (GtkTextMark *mark,
2590 GtkTextLineSegment *seg;
2592 g_return_if_fail(mark != NULL);
2594 seg = (GtkTextLineSegment*)mark;
2596 if (seg->body.mark.visible == setting)
2600 seg->body.mark.visible = setting;
2602 redisplay_mark(seg);
2607 gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2610 GtkTextBTreeNode *node;
2611 GtkTextTagInfo *info;
2613 g_return_val_if_fail(tree != NULL, NULL);
2617 info = gtk_text_btree_get_existing_tag_info(tree, tag);
2622 if (info->tag_root == NULL)
2625 node = info->tag_root;
2627 /* We know the tag root has instances of the given
2630 continue_outer_loop:
2631 g_assert(node != NULL);
2632 while (node->level > 0)
2634 g_assert(node != NULL); /* Failure probably means bad tag summaries. */
2635 node = node->children.node;
2636 while (node != NULL)
2638 if (gtk_text_btree_node_has_tag(node, tag))
2639 goto continue_outer_loop;
2643 g_assert(node != NULL);
2646 g_assert(node != NULL); /* The tag summaries said some node had
2649 g_assert(node->level == 0);
2651 return node->children.line;
2655 /* Looking for any tag at all (tag == NULL).
2656 Unfortunately this can't be done in a simple and efficient way
2657 right now; so I'm just going to return the
2658 first line in the btree. FIXME */
2659 return gtk_text_btree_get_line (tree, 0, NULL);
2664 gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2667 GtkTextBTreeNode *node;
2668 GtkTextBTreeNode *last_node;
2670 GtkTextTagInfo *info;
2672 g_return_val_if_fail(tree != NULL, NULL);
2676 info = gtk_text_btree_get_existing_tag_info(tree, tag);
2678 if (info->tag_root == NULL)
2681 node = info->tag_root;
2682 /* We know the tag root has instances of the given
2685 while (node->level > 0)
2687 g_assert(node != NULL); /* Failure probably means bad tag summaries. */
2689 node = node->children.node;
2690 while (node != NULL)
2692 if (gtk_text_btree_node_has_tag(node, tag))
2700 g_assert(node != NULL); /* The tag summaries said some node had
2703 g_assert(node->level == 0);
2705 /* Find the last line in this node */
2706 line = node->children.line;
2707 while (line->next != NULL)
2714 /* This search can't be done efficiently at the moment,
2715 at least not without complexity.
2716 So, we just return the last line.
2718 return gtk_text_btree_get_line (tree, -1, NULL);
2728 gtk_text_line_get_number (GtkTextLine *line)
2731 GtkTextBTreeNode *node, *parent, *node2;
2735 * First count how many lines precede this one in its level-0
2739 node = line->parent;
2741 for (line2 = node->children.line; line2 != line;
2742 line2 = line2->next)
2746 g_error("gtk_text_btree_line_number couldn't find line");
2752 * Now work up through the levels of the tree one at a time,
2753 * counting how many lines are in GtkTextBTreeNodes preceding the current
2757 for (parent = node->parent ; parent != NULL;
2758 node = parent, parent = parent->parent)
2760 for (node2 = parent->children.node; node2 != node;
2761 node2 = node2->next)
2765 g_error("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2767 index += node2->num_lines;
2773 static GtkTextLineSegment*
2774 find_toggle_segment_before_char(GtkTextLine *line,
2778 GtkTextLineSegment *seg;
2779 GtkTextLineSegment *toggle_seg;
2784 seg = line->segments;
2785 while ( (index + seg->char_count) <= char_in_line )
2787 if (((seg->type == >k_text_toggle_on_type)
2788 || (seg->type == >k_text_toggle_off_type))
2789 && (seg->body.toggle.info->tag == tag))
2792 index += seg->char_count;
2799 static GtkTextLineSegment*
2800 find_toggle_segment_before_byte(GtkTextLine *line,
2804 GtkTextLineSegment *seg;
2805 GtkTextLineSegment *toggle_seg;
2810 seg = line->segments;
2811 while ( (index + seg->byte_count) <= byte_in_line )
2813 if (((seg->type == >k_text_toggle_on_type)
2814 || (seg->type == >k_text_toggle_off_type))
2815 && (seg->body.toggle.info->tag == tag))
2818 index += seg->byte_count;
2826 find_toggle_outside_current_line(GtkTextLine *line,
2830 GtkTextBTreeNode *node;
2831 GtkTextLine *sibling_line;
2832 GtkTextLineSegment *seg;
2833 GtkTextLineSegment *toggle_seg;
2835 GtkTextTagInfo *info = NULL;
2838 * No toggle in this line. Look for toggles for the tag in lines
2839 * that are predecessors of line but under the same
2840 * level-0 GtkTextBTreeNode.
2843 sibling_line = line->parent->children.line;
2844 while (sibling_line != line)
2846 seg = sibling_line->segments;
2849 if (((seg->type == >k_text_toggle_on_type)
2850 || (seg->type == >k_text_toggle_off_type))
2851 && (seg->body.toggle.info->tag == tag))
2857 sibling_line = sibling_line->next;
2860 if (toggle_seg != NULL)
2861 return (toggle_seg->type == >k_text_toggle_on_type);
2864 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
2865 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
2866 * siblings that precede that GtkTextBTreeNode.
2869 info = gtk_text_btree_get_existing_tag_info(tree, tag);
2875 node = line->parent;
2876 while (node->parent != NULL)
2878 GtkTextBTreeNode *sibling_node;
2880 sibling_node = node->parent->children.node;
2881 while (sibling_node != node)
2885 summary = sibling_node->summary;
2886 while (summary != NULL)
2888 if (summary->info == info)
2889 toggles += summary->toggle_count;
2891 summary = summary->next;
2894 sibling_node = sibling_node->next;
2897 if (node == info->tag_root)
2900 node = node->parent;
2904 * An odd number of toggles means that the tag is present at the
2908 return (toggles & 1) != 0;
2911 /* FIXME this function is far too slow, for no good reason. */
2913 gtk_text_line_char_has_tag (GtkTextLine *line,
2918 GtkTextLineSegment *toggle_seg;
2920 g_return_val_if_fail(line != NULL, FALSE);
2923 * Check for toggles for the tag in the line but before
2924 * the char. If there is one, its type indicates whether or
2925 * not the character is tagged.
2928 toggle_seg = find_toggle_segment_before_char(line, char_in_line, tag);
2930 if (toggle_seg != NULL)
2931 return (toggle_seg->type == >k_text_toggle_on_type);
2933 return find_toggle_outside_current_line(line, tree, tag);
2937 gtk_text_line_byte_has_tag (GtkTextLine *line,
2942 GtkTextLineSegment *toggle_seg;
2944 g_return_val_if_fail(line != NULL, FALSE);
2947 * Check for toggles for the tag in the line but before
2948 * the char. If there is one, its type indicates whether or
2949 * not the character is tagged.
2952 toggle_seg = find_toggle_segment_before_byte(line, byte_in_line, tag);
2954 if (toggle_seg != NULL)
2955 return (toggle_seg->type == >k_text_toggle_on_type);
2957 return find_toggle_outside_current_line(line, tree, tag);
2961 gtk_text_line_is_last (GtkTextLine *line,
2964 return line == get_last_line (tree);
2968 gtk_text_line_next (GtkTextLine *line)
2970 GtkTextBTreeNode *node;
2972 if (line->next != NULL)
2977 * This was the last line associated with the particular parent
2978 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
2979 * then search down from that GtkTextBTreeNode to find the first
2983 node = line->parent;
2984 while (node != NULL && node->next == NULL)
2985 node = node->parent;
2991 while (node->level > 0)
2993 node = node->children.node;
2996 g_assert(node->children.line != line);
2998 return node->children.line;
3003 gtk_text_line_previous (GtkTextLine *line)
3005 GtkTextBTreeNode *node;
3006 GtkTextBTreeNode *node2;
3010 * Find the line under this GtkTextBTreeNode just before the starting line.
3012 prev = line->parent->children.line; /* First line at leaf */
3013 while (prev != line)
3015 if (prev->next == line)
3021 g_error("gtk_text_btree_previous_line ran out of lines");
3025 * This was the first line associated with the particular parent
3026 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3027 * then search down from that GtkTextBTreeNode to find its last line.
3029 for (node = line->parent; ; node = node->parent)
3031 if (node == NULL || node->parent == NULL)
3033 else if (node != node->parent->children.node)
3037 for (node2 = node->parent->children.node; ;
3038 node2 = node2->children.node)
3040 while (node2->next != node)
3041 node2 = node2->next;
3043 if (node2->level == 0)
3049 for (prev = node2->children.line ; ; prev = prev->next)
3051 if (prev->next == NULL)
3055 g_assert_not_reached();
3060 gtk_text_line_add_data (GtkTextLine *line,
3061 GtkTextLineData *data)
3063 g_return_if_fail(line != NULL);
3064 g_return_if_fail(data != NULL);
3065 g_return_if_fail(data->view_id != NULL);
3069 data->next = line->views;
3079 gtk_text_line_remove_data (GtkTextLine *line,
3082 GtkTextLineData *prev;
3083 GtkTextLineData *iter;
3085 g_return_val_if_fail(line != NULL, NULL);
3086 g_return_val_if_fail(view_id != NULL, NULL);
3090 while (iter != NULL)
3092 if (iter->view_id == view_id)
3101 prev->next = iter->next;
3103 line->views = iter->next;
3112 gtk_text_line_get_data (GtkTextLine *line,
3115 GtkTextLineData *iter;
3117 g_return_val_if_fail(line != NULL, NULL);
3118 g_return_val_if_fail(view_id != NULL, NULL);
3121 while (iter != NULL)
3123 if (iter->view_id == view_id)
3132 gtk_text_line_invalidate_wrap (GtkTextLine *line,
3133 GtkTextLineData *ld)
3135 /* For now this is totally unoptimized. FIXME?
3137 We could probably optimize the case where the width removed
3138 is less than the max width for the parent node,
3139 and the case where the height is unchanged when we re-wrap.
3142 g_return_if_fail(ld != NULL);
3145 gtk_text_btree_node_invalidate_upward(line->parent, ld->view_id);
3149 gtk_text_line_char_count (GtkTextLine *line)
3151 GtkTextLineSegment *seg;
3155 seg = line->segments;
3158 size += seg->char_count;
3165 gtk_text_line_byte_count (GtkTextLine *line)
3167 GtkTextLineSegment *seg;
3171 seg = line->segments;
3174 size += seg->byte_count;
3182 gtk_text_line_char_index (GtkTextLine *target_line)
3184 GSList *node_stack = NULL;
3185 GtkTextBTreeNode *iter;
3189 /* Push all our parent nodes onto a stack */
3190 iter = target_line->parent;
3192 g_assert(iter != NULL);
3194 while (iter != NULL)
3196 node_stack = g_slist_prepend(node_stack, iter);
3198 iter = iter->parent;
3201 /* Check that we have the root node on top of the stack. */
3202 g_assert(node_stack != NULL &&
3203 node_stack->data != NULL &&
3204 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3206 /* Add up chars in all nodes before the nodes in our stack.
3210 iter = node_stack->data;
3211 while (iter != NULL)
3213 GtkTextBTreeNode *child_iter;
3214 GtkTextBTreeNode *next_node;
3216 next_node = node_stack->next ?
3217 node_stack->next->data : NULL;
3218 node_stack = g_slist_remove(node_stack, node_stack->data);
3220 if (iter->level == 0)
3222 /* stack should be empty when we're on the last node */
3223 g_assert(node_stack == NULL);
3224 break; /* Our children are now lines */
3227 g_assert(next_node != NULL);
3228 g_assert(iter != NULL);
3229 g_assert(next_node->parent == iter);
3231 /* Add up chars before us in the tree */
3232 child_iter = iter->children.node;
3233 while (child_iter != next_node)
3235 g_assert(child_iter != NULL);
3237 num_chars += child_iter->num_chars;
3239 child_iter = child_iter->next;
3245 g_assert(iter != NULL);
3246 g_assert(iter == target_line->parent);
3248 /* Since we don't store char counts in lines, only in segments, we
3249 have to iterate over the lines adding up segment char counts
3250 until we find our line. */
3251 line = iter->children.line;
3252 while (line != target_line)
3254 g_assert(line != NULL);
3256 num_chars += gtk_text_line_char_count(line);
3261 g_assert(line == target_line);
3267 gtk_text_line_byte_to_segment (GtkTextLine *line,
3271 GtkTextLineSegment *seg;
3274 g_return_val_if_fail(line != NULL, NULL);
3276 offset = byte_offset;
3277 seg = line->segments;
3279 while (offset >= seg->byte_count)
3281 g_assert(seg != NULL); /* means an invalid byte index */
3282 offset -= seg->byte_count;
3287 *seg_offset = offset;
3293 gtk_text_line_char_to_segment (GtkTextLine *line,
3297 GtkTextLineSegment *seg;
3300 g_return_val_if_fail(line != NULL, NULL);
3302 offset = char_offset;
3303 seg = line->segments;
3305 while (offset >= seg->char_count)
3307 g_assert(seg != NULL); /* means an invalid char index */
3308 offset -= seg->char_count;
3313 *seg_offset = offset;
3319 gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3323 GtkTextLineSegment *seg;
3326 g_return_val_if_fail(line != NULL, NULL);
3328 offset = byte_offset;
3329 seg = line->segments;
3331 while (offset > 0 && offset >= seg->byte_count)
3333 g_assert(seg != NULL); /* means an invalid byte index */
3334 offset -= seg->byte_count;
3339 *seg_offset = offset;
3345 gtk_text_line_char_to_any_segment (GtkTextLine *line,
3349 GtkTextLineSegment *seg;
3352 g_return_val_if_fail(line != NULL, NULL);
3354 offset = char_offset;
3355 seg = line->segments;
3357 while (offset > 0 && offset >= seg->char_count)
3359 g_assert(seg != NULL); /* means an invalid byte index */
3360 offset -= seg->char_count;
3365 *seg_offset = offset;
3371 gtk_text_line_byte_to_char (GtkTextLine *line,
3375 GtkTextLineSegment *seg;
3377 g_return_val_if_fail(line != NULL, 0);
3378 g_return_val_if_fail(byte_offset >= 0, 0);
3381 seg = line->segments;
3382 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3383 the next segment) */
3385 g_assert(seg != NULL); /* our byte_index was bogus if this happens */
3387 byte_offset -= seg->byte_count;
3388 char_offset += seg->char_count;
3393 g_assert(seg != NULL);
3395 /* Now byte_offset is the offset into the current segment,
3396 and char_offset is the start of the current segment.
3397 Optimize the case where no chars use > 1 byte */
3398 if (seg->byte_count == seg->char_count)
3399 return char_offset + byte_offset;
3402 if (seg->type == >k_text_char_type)
3403 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3406 g_assert(seg->char_count == 1);
3407 g_assert(byte_offset == 0);
3415 gtk_text_line_char_to_byte (GtkTextLine *line,
3418 g_warning("FIXME not implemented");
3422 /* FIXME sync with char_locate (or figure out a clean
3423 way to merge the two functions) */
3425 gtk_text_line_byte_locate (GtkTextLine *line,
3427 GtkTextLineSegment **segment,
3428 GtkTextLineSegment **any_segment,
3429 gint *seg_byte_offset,
3430 gint *line_byte_offset)
3432 GtkTextLineSegment *seg;
3433 GtkTextLineSegment *after_prev_indexable;
3434 GtkTextLineSegment *after_last_indexable;
3435 GtkTextLineSegment *last_indexable;
3439 g_return_if_fail(line != NULL);
3441 if (byte_offset < 0)
3443 /* -1 means end of line; we here assume no line is
3444 longer than 1 bazillion bytes, of course we assumed
3445 that anyway since we'd wrap around... */
3447 byte_offset = G_MAXINT;
3451 *any_segment = NULL;
3454 offset = byte_offset;
3456 last_indexable = NULL;
3457 after_last_indexable = line->segments;
3458 after_prev_indexable = line->segments;
3459 seg = line->segments;
3461 /* The loop ends when we're inside a segment;
3462 last_indexable refers to the last segment
3463 we passed entirely. */
3464 while (seg && offset >= seg->byte_count)
3466 if (seg->char_count > 0)
3468 offset -= seg->byte_count;
3469 bytes_in_line += seg->byte_count;
3470 last_indexable = seg;
3471 after_prev_indexable = after_last_indexable;
3472 after_last_indexable = last_indexable->next;
3480 /* We went off the end of the line */
3481 *segment = last_indexable;
3482 *any_segment = after_prev_indexable;
3483 /* subtracting 1 is OK, we know it's a newline at the end. */
3484 offset = (*segment)->byte_count - 1;
3485 bytes_in_line -= (*segment)->byte_count;
3490 if (after_last_indexable != NULL)
3491 *any_segment = after_last_indexable;
3493 *any_segment = *segment;
3496 /* Override any_segment if we're in the middle of a segment. */
3498 *any_segment = *segment;
3500 *seg_byte_offset = offset;
3502 g_assert(*segment != NULL);
3503 g_assert(*any_segment != NULL);
3504 g_assert(*seg_byte_offset < (*segment)->byte_count);
3506 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3509 /* FIXME sync with byte_locate (or figure out a clean
3510 way to merge the two functions) */
3512 gtk_text_line_char_locate (GtkTextLine *line,
3514 GtkTextLineSegment **segment,
3515 GtkTextLineSegment **any_segment,
3516 gint *seg_char_offset,
3517 gint *line_char_offset)
3519 GtkTextLineSegment *seg;
3520 GtkTextLineSegment *after_prev_indexable;
3521 GtkTextLineSegment *after_last_indexable;
3522 GtkTextLineSegment *last_indexable;
3526 g_return_if_fail(line != NULL);
3528 if (char_offset < 0)
3530 /* -1 means end of line; we here assume no line is
3531 longer than 1 bazillion chars, of course we assumed
3532 that anyway since we'd wrap around... */
3534 char_offset = G_MAXINT;
3538 *any_segment = NULL;
3541 offset = char_offset;
3543 last_indexable = NULL;
3544 after_last_indexable = line->segments;
3545 after_prev_indexable = line->segments;
3546 seg = line->segments;
3548 /* The loop ends when we're inside a segment;
3549 last_indexable refers to the last segment
3550 we passed entirely. */
3551 while (seg && offset >= seg->char_count)
3553 if (seg->char_count > 0)
3555 offset -= seg->char_count;
3556 chars_in_line += seg->char_count;
3557 last_indexable = seg;
3558 after_prev_indexable = after_last_indexable;
3559 after_last_indexable = last_indexable->next;
3567 /* We went off the end of the line */
3568 *segment = last_indexable;
3569 *any_segment = after_prev_indexable;
3570 /* subtracting 1 is OK, we know it's a newline at the end. */
3571 offset = (*segment)->char_count - 1;
3572 chars_in_line -= (*segment)->char_count;
3577 if (after_last_indexable != NULL)
3578 *any_segment = after_last_indexable;
3580 *any_segment = *segment;
3583 /* Override any_segment if we're in the middle of a segment. */
3585 *any_segment = *segment;
3587 *seg_char_offset = offset;
3589 g_assert(*segment != NULL);
3590 g_assert(*any_segment != NULL);
3591 g_assert(*seg_char_offset < (*segment)->char_count);
3593 *line_char_offset = chars_in_line + *seg_char_offset;
3597 gtk_text_line_byte_to_char_offsets(GtkTextLine *line,
3599 gint *line_char_offset,
3600 gint *seg_char_offset)
3602 GtkTextLineSegment *seg;
3605 g_return_if_fail(line != NULL);
3606 g_return_if_fail(byte_offset >= 0);
3608 *line_char_offset = 0;
3610 offset = byte_offset;
3611 seg = line->segments;
3613 while (offset >= seg->byte_count)
3615 offset -= seg->byte_count;
3616 *line_char_offset += seg->char_count;
3618 g_assert(seg != NULL); /* means an invalid char offset */
3621 g_assert(seg->char_count > 0); /* indexable. */
3623 /* offset is now the number of bytes into the current segment we
3624 want to go. Count chars into the current segment. */
3626 if (seg->type == >k_text_char_type)
3628 *seg_char_offset = g_utf8_strlen(seg->body.chars, offset);
3630 g_assert(*seg_char_offset < seg->char_count);
3632 *line_char_offset += *seg_char_offset;
3636 g_assert(offset == 0);
3637 *seg_char_offset = 0;
3642 gtk_text_line_char_to_byte_offsets(GtkTextLine *line,
3644 gint *line_byte_offset,
3645 gint *seg_byte_offset)
3647 GtkTextLineSegment *seg;
3650 g_return_if_fail(line != NULL);
3651 g_return_if_fail(char_offset >= 0);
3653 *line_byte_offset = 0;
3655 offset = char_offset;
3656 seg = line->segments;
3658 while (offset >= seg->char_count)
3660 offset -= seg->char_count;
3661 *line_byte_offset += seg->byte_count;
3663 g_assert(seg != NULL); /* means an invalid char offset */
3666 g_assert(seg->char_count > 0); /* indexable. */
3668 /* offset is now the number of chars into the current segment we
3669 want to go. Count bytes into the current segment. */
3671 if (seg->type == >k_text_char_type)
3673 *seg_byte_offset = 0;
3677 const char * start = seg->body.chars + *seg_byte_offset;
3679 bytes = g_utf8_next_char (start) - start;
3680 *seg_byte_offset += bytes;
3684 g_assert(*seg_byte_offset < seg->byte_count);
3686 *line_byte_offset += *seg_byte_offset;
3690 g_assert(offset == 0);
3691 *seg_byte_offset = 0;
3695 /* remember that tag == NULL means "any tag" */
3697 gtk_text_line_next_could_contain_tag(GtkTextLine *line,
3701 GtkTextBTreeNode *node;
3702 GtkTextTagInfo *info;
3703 gboolean below_tag_root;
3705 g_return_val_if_fail(line != NULL, NULL);
3707 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3708 gtk_text_btree_check (tree);
3712 /* Right now we can only offer linear-search if the user wants
3713 to know about any tag toggle at all. */
3714 return gtk_text_line_next (line);
3717 /* Our tag summaries only have node precision, not line
3718 precision. This means that if any line under a node could contain a
3719 tag, then any of the others could also contain a tag.
3721 In the future we could have some mechanism to keep track of how
3722 many toggles we've found under a node so far, since we have a
3723 count of toggles under the node. But for now I'm going with KISS.
3726 /* return same-node line, if any. */
3730 info = gtk_text_btree_get_existing_tag_info(tree, tag);
3734 if (info->tag_root == NULL)
3737 /* We need to go up out of this node, and on to the next one with
3738 toggles for the target tag. If we're below the tag root, we need to
3739 find the next node below the tag root that has tag summaries. If
3740 we're not below the tag root, we need to see if the tag root is
3741 after us in the tree, and if so, return the first line underneath
3744 node = line->parent;
3745 below_tag_root = FALSE;
3746 while (node != NULL)
3748 if (node == info->tag_root)
3750 below_tag_root = TRUE;
3754 node = node->parent;
3759 node = line->parent;
3760 while (node != info->tag_root)
3762 if (node->next == NULL)
3763 node = node->parent;
3768 if (gtk_text_btree_node_has_tag(node, tag))
3776 GtkTextBTreeNode * iter;
3777 GtkTextBTreeNode * common_parent;
3778 GtkTextBTreeNode * parent_of_tag_root;
3779 GtkTextBTreeNode * parent_of_node;
3781 /* Find common parent between our current line, and the tag
3782 root. Save the child nodes of the common parent we used to get
3783 to the common parent; we then use these two child nodes to
3784 determine whether the ordering of the tag root and the current
3785 line in the tree. (Nice code cleanup: write
3786 gtk_btree_node_compare() to compute node ordering.)
3789 /* Get on the same level */
3790 node = line->parent;
3791 while (node->level < info->tag_root->level)
3792 node = node->parent;
3794 common_parent = info->tag_root->parent;
3796 /* Find common parent, and children of that parent above
3797 tag root and our current node */
3798 parent_of_node = node;
3799 parent_of_tag_root = info->tag_root;
3801 while (node->parent != common_parent)
3803 parent_of_node = node;
3804 parent_of_tag_root = common_parent;
3805 node = node->parent;
3806 common_parent = common_parent->parent;
3809 /* See which is first in the list of common_parent's children */
3810 iter = common_parent->children.node;
3811 while (iter != NULL)
3813 if (iter == parent_of_tag_root)
3814 return NULL; /* Tag root was before us in the tree */
3815 else if (iter == parent_of_node)
3817 /* We want the first inside-tag-root node,
3818 since we're before the tag root */
3819 node = info->tag_root;
3831 g_assert(node != NULL);
3833 /* We have to find the first sub-node of this node that contains
3836 continue_outer_loop:
3837 while (node->level > 0)
3839 g_assert(node != NULL); /* If this fails, it likely means an
3840 incorrect tag summary led us on a
3841 wild goose chase down this branch of
3843 node = node->children.node;
3844 while (node != NULL)
3846 if (gtk_text_btree_node_has_tag(node, tag))
3847 goto continue_outer_loop;
3850 g_assert(node != NULL);
3853 g_assert(node != NULL);
3854 g_assert(node->level == 0);
3856 return node->children.line;
3860 gtk_text_line_previous_could_contain_tag(GtkTextLine *line,
3869 * Non-public function implementations */
3872 summary_list_destroy(Summary *summary)
3875 while (summary != NULL)
3877 next = summary->next;
3878 summary_destroy (summary);
3884 get_last_line(GtkTextBTree *tree)
3886 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
3892 n_lines = gtk_text_btree_line_count(tree);
3894 g_assert(n_lines >= 1); /* num_lines doesn't return bogus last line. */
3896 line = gtk_text_btree_get_line(tree, n_lines, &real_line);
3898 tree->end_iter_line_stamp = tree->chars_changed_stamp;
3899 tree->end_iter_line = line;
3902 return tree->end_iter_line;
3910 gtk_text_line_new(void)
3914 line = g_new0(GtkTextLine, 1);
3920 gtk_text_line_destroy(GtkTextBTree *tree, GtkTextLine *line)
3922 GtkTextLineData *ld;
3923 GtkTextLineData *next;
3925 g_return_if_fail(line != NULL);
3932 view = gtk_text_btree_get_view (tree, ld->view_id);
3934 g_assert(view != NULL);
3937 gtk_text_layout_free_line_data (view->layout, line, ld);
3946 gtk_text_line_set_parent(GtkTextLine *line,
3947 GtkTextBTreeNode *node)
3949 if (line->parent == node)
3951 line->parent = node;
3952 gtk_text_btree_node_invalidate_upward(node, NULL);
3956 cleanup_line(GtkTextLine *line)
3958 GtkTextLineSegment *seg, **prev_p;
3962 * Make a pass over all of the segments in the line, giving each
3963 * a chance to clean itself up. This could potentially change
3964 * the structure of the line, e.g. by merging two segments
3965 * together or having two segments cancel themselves; if so,
3966 * then repeat the whole process again, since the first structure
3967 * change might make other structure changes possible. Repeat
3968 * until eventually there are no changes.
3975 for (prev_p = &line->segments, seg = *prev_p;
3977 prev_p = &(*prev_p)->next, seg = *prev_p)
3979 if (seg->type->cleanupFunc != NULL)
3981 *prev_p = (*seg->type->cleanupFunc)(seg, line);
3994 node_data_new(gpointer view_id)
3998 nd = g_new(NodeData, 1);
4000 nd->view_id = view_id;
4010 node_data_destroy(NodeData *nd)
4017 node_data_list_destroy(NodeData *nd)
4023 while (iter != NULL)
4026 node_data_destroy(iter);
4032 node_data_find(NodeData *nd, gpointer view_id)
4036 if (nd->view_id == view_id)
4044 summary_destroy (Summary *summary)
4046 /* Fill with error-triggering garbage */
4047 summary->info = (void*)0x1;
4048 summary->toggle_count = 567;
4049 summary->next = (void*)0x1;
4053 static GtkTextBTreeNode*
4054 gtk_text_btree_node_new(void)
4056 GtkTextBTreeNode *node;
4058 node = g_new(GtkTextBTreeNode, 1);
4060 node->node_data = NULL;
4066 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4067 GtkTextTagInfo *info,
4072 summary = node->summary;
4073 while (summary != NULL)
4075 if (summary->info == info)
4077 summary->toggle_count += adjust;
4081 summary = summary->next;
4084 if (summary == NULL)
4086 /* didn't find a summary for our tag. */
4087 g_return_if_fail(adjust > 0);
4088 summary = g_new(Summary, 1);
4089 summary->info = info;
4090 summary->toggle_count = adjust;
4091 summary->next = node->summary;
4092 node->summary = summary;
4096 /* Note that the tag root and above do not have summaries
4097 for the tag; only nodes below the tag root have
4100 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4104 summary = node->summary;
4105 while (summary != NULL)
4108 summary->info->tag == tag)
4111 summary = summary->next;
4117 /* Add node and all children to the damage region. */
4119 gtk_text_btree_node_invalidate_downward(GtkTextBTreeNode *node)
4123 nd = node->node_data;
4130 if (node->level == 0)
4134 line = node->children.line;
4135 while (line != NULL)
4137 GtkTextLineData *ld;
4151 GtkTextBTreeNode *child;
4153 child = node->children.node;
4155 while (child != NULL)
4157 gtk_text_btree_node_invalidate_downward(child);
4159 child = child->next;
4165 gtk_text_btree_node_invalidate_upward(GtkTextBTreeNode *node, gpointer view_id)
4167 GtkTextBTreeNode *iter;
4170 while (iter != NULL)
4176 nd = node_data_find (iter->node_data, view_id);
4178 if (nd == NULL || !nd->valid)
4179 break; /* Once a node is invalid, we know its parents are as well. */
4185 gboolean should_continue = FALSE;
4187 nd = iter->node_data;
4192 should_continue = TRUE;
4199 if (!should_continue)
4200 break; /* This node was totally invalidated, so are its
4204 iter = iter->parent;
4210 * gtk_text_btree_is_valid:
4211 * @tree: a #GtkTextBTree
4212 * @view_id: ID for the view
4214 * Check to see if the entire #GtkTextBTree is valid or not for
4217 * Return value: %TRUE if the entire #GtkTextBTree is valid
4220 gtk_text_btree_is_valid (GtkTextBTree *tree,
4224 g_return_val_if_fail (tree != NULL, FALSE);
4226 nd = node_data_find (tree->root_node->node_data, view_id);
4227 return (nd && nd->valid);
4230 typedef struct _ValidateState ValidateState;
4232 struct _ValidateState
4234 gint remaining_pixels;
4235 gboolean in_validation;
4242 gtk_text_btree_node_validate (BTreeView *view,
4243 GtkTextBTreeNode *node,
4245 ValidateState *state)
4247 gint node_valid = TRUE;
4248 gint node_width = 0;
4249 gint node_height = 0;
4251 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4252 g_return_if_fail (!nd->valid);
4254 if (node->level == 0)
4256 GtkTextLine *line = node->children.line;
4257 GtkTextLineData *ld;
4259 /* Iterate over leading valid lines */
4260 while (line != NULL)
4262 ld = gtk_text_line_get_data (line, view_id);
4264 if (!ld || !ld->valid)
4266 else if (state->in_validation)
4268 state->in_validation = FALSE;
4273 state->y += ld->height;
4274 node_width = MAX (ld->width, node_width);
4275 node_height += ld->height;
4281 state->in_validation = TRUE;
4283 /* Iterate over invalid lines */
4284 while (line != NULL)
4286 ld = gtk_text_line_get_data (line, view_id);
4288 if (ld && ld->valid)
4293 state->old_height += ld->height;
4294 ld = gtk_text_layout_wrap (view->layout, line, ld);
4295 state->new_height += ld->height;
4297 node_width = MAX (ld->width, node_width);
4298 node_height += ld->height;
4300 state->remaining_pixels -= ld->height;
4301 if (state->remaining_pixels <= 0)
4311 /* Iterate over the remaining lines */
4312 while (line != NULL)
4314 ld = gtk_text_line_get_data (line, view_id);
4315 state->in_validation = FALSE;
4317 if (!ld || !ld->valid)
4322 node_width = MAX (ld->width, node_width);
4323 node_height += ld->height;
4331 GtkTextBTreeNode *child;
4334 child = node->children.node;
4336 /* Iterate over leading valid nodes */
4339 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4341 if (!child_nd->valid)
4343 else if (state->in_validation)
4345 state->in_validation = FALSE;
4350 state->y += child_nd->height;
4351 node_width = MAX (node_width, child_nd->width);
4352 node_height += child_nd->height;
4355 child = child->next;
4358 /* Iterate over invalid nodes */
4361 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4363 if (child_nd->valid)
4367 gtk_text_btree_node_validate (view, child, view_id, state);
4369 if (!child_nd->valid)
4371 node_width = MAX (node_width, child_nd->width);
4372 node_height += child_nd->height;
4374 if (!state->in_validation || state->remaining_pixels <= 0)
4376 child = child->next;
4381 child = child->next;
4384 /* Iterate over the remaining lines */
4387 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4388 state->in_validation = FALSE;
4390 if (!child_nd->valid)
4393 node_width = MAX (child_nd->width, node_width);
4394 node_height += child_nd->height;
4396 child = child->next;
4400 nd->width = node_width;
4401 nd->height = node_height;
4402 nd->valid = node_valid;
4406 * gtk_text_btree_validate:
4407 * @tree: a #GtkTextBTree
4409 * @max_pixels: the maximum number of pixels to validate. (No more
4410 * than one paragraph beyond this limit will be validated)
4411 * @y: location to store starting y coordinate of validated region
4412 * @old_height: location to store old height of validated region
4413 * @new_height: location to store new height of validated region
4415 * Validate a single contiguous invalid region of a #GtkTextBTree for
4418 * Return value: %TRUE if a region has been validated, %FALSE if the
4419 * entire tree was already valid.
4422 gtk_text_btree_validate (GtkTextBTree *tree,
4431 g_return_val_if_fail (tree != NULL, FALSE);
4433 view = gtk_text_btree_get_view (tree, view_id);
4434 g_return_val_if_fail (view != NULL, FALSE);
4436 if (!gtk_text_btree_is_valid (tree, view_id))
4438 ValidateState state;
4440 state.remaining_pixels = max_pixels;
4441 state.in_validation = FALSE;
4443 state.old_height = 0;
4444 state.new_height = 0;
4446 gtk_text_btree_node_validate (view,
4453 *old_height = state.old_height;
4455 *new_height = state.new_height;
4457 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4458 gtk_text_btree_check(tree);
4467 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4471 gboolean *valid_out)
4475 gboolean valid = TRUE;
4477 if (node->level == 0)
4479 GtkTextLine *line = node->children.line;
4481 while (line != NULL)
4483 GtkTextLineData *ld = gtk_text_line_get_data (line, view_id);
4485 if (!ld || !ld->valid)
4490 width = MAX (ld->width, width);
4491 height += ld->height;
4499 GtkTextBTreeNode *child = node->children.node;
4503 NodeData *child_nd = node_data_find (child->node_data, view_id);
4505 if (!child_nd || !child_nd->valid)
4510 width = MAX (child_nd->width, width);
4511 height += child_nd->height;
4514 child = child->next;
4519 *height_out = height;
4524 /* Recompute the validity and size of the view data for a given
4525 * view at this node from the immediate children of the node
4528 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4531 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4536 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4537 &width, &height, &valid);
4539 nd->height = height;
4546 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4551 gtk_text_btree_node_check_valid (node, view_id);
4552 node = node->parent;
4557 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4560 if (node->level == 0)
4562 return gtk_text_btree_node_check_valid (node, view_id);
4566 GtkTextBTreeNode *child = node->children.node;
4568 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4576 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
4578 if (!child_nd->valid)
4580 nd->width = MAX (child_nd->width, nd->width);
4581 nd->height += child_nd->height;
4583 child = child->next;
4592 * gtk_text_btree_validate_line:
4593 * @tree: a #GtkTextBTree
4594 * @line: line to validate
4595 * @view_id: view ID for the view to validate
4597 * Revalidate a single line of the btree for the given view, propagate
4598 * results up through the entire tree.
4601 gtk_text_btree_validate_line (GtkTextBTree *tree,
4605 GtkTextLineData *ld;
4606 GtkTextLine *last_line;
4609 g_return_if_fail (tree != NULL);
4610 g_return_if_fail (line != NULL);
4612 view = gtk_text_btree_get_view (tree, view_id);
4613 g_return_if_fail (view != NULL);
4615 ld = gtk_text_line_get_data(line, view_id);
4616 if (!ld || !ld->valid)
4618 ld = gtk_text_layout_wrap (view->layout, line, ld);
4619 last_line = get_last_line (tree);
4621 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
4626 gtk_text_btree_node_remove_view(BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
4628 if (node->level == 0)
4632 line = node->children.line;
4633 while (line != NULL)
4635 GtkTextLineData *ld;
4637 ld = gtk_text_line_remove_data(line, view_id);
4640 gtk_text_layout_free_line_data (view->layout, line, ld);
4647 GtkTextBTreeNode *child;
4649 child = node->children.node;
4651 while (child != NULL)
4654 gtk_text_btree_node_remove_view(view, child, view_id);
4656 child = child->next;
4660 gtk_text_btree_node_remove_data(node, view_id);
4664 gtk_text_btree_node_destroy(GtkTextBTree *tree, GtkTextBTreeNode *node)
4666 if (node->level == 0)
4669 GtkTextLineSegment *seg;
4671 while (node->children.line != NULL)
4673 line = node->children.line;
4674 node->children.line = line->next;
4675 while (line->segments != NULL)
4677 seg = line->segments;
4678 line->segments = seg->next;
4679 (*seg->type->deleteFunc)(seg, line, 1);
4681 gtk_text_line_destroy(tree, line);
4686 GtkTextBTreeNode *childPtr;
4688 while (node->children.node != NULL)
4690 childPtr = node->children.node;
4691 node->children.node = childPtr->next;
4692 gtk_text_btree_node_destroy(tree, childPtr);
4695 summary_list_destroy(node->summary);
4696 node_data_list_destroy(node->node_data);
4701 gtk_text_btree_node_ensure_data(GtkTextBTreeNode *node, gpointer view_id)
4705 nd = node->node_data;
4708 if (nd->view_id == view_id)
4715 nd = node_data_new(view_id);
4717 if (node->node_data)
4718 nd->next = node->node_data;
4720 node->node_data = nd;
4727 gtk_text_btree_node_remove_data(GtkTextBTreeNode *node, gpointer view_id)
4733 nd = node->node_data;
4736 if (nd->view_id == view_id)
4747 prev->next = nd->next;
4749 if (node->node_data == nd)
4750 node->node_data = nd->next;
4754 node_data_destroy(nd);
4758 gtk_text_btree_node_get_size(GtkTextBTreeNode *node, gpointer view_id,
4759 gint *width, gint *height)
4763 g_return_if_fail(width != NULL);
4764 g_return_if_fail(height != NULL);
4766 nd = gtk_text_btree_node_ensure_data(node, view_id);
4771 *height = nd->height;
4774 /* Find the closest common ancestor of the two nodes. FIXME: The interface
4775 * here isn't quite right, since for a lot of operations we want to
4776 * know which children of the common parent correspond to the two nodes
4777 * (e.g., when computing the order of two iters)
4779 static GtkTextBTreeNode *
4780 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
4781 GtkTextBTreeNode *node2)
4783 while (node1->level < node2->level)
4784 node1 = node1->parent;
4785 while (node2->level < node1->level)
4786 node2 = node2->parent;
4787 while (node1 != node2)
4789 node1 = node1->parent;
4790 node2 = node2->parent;
4801 gtk_text_btree_get_view(GtkTextBTree *tree, gpointer view_id)
4806 while (view != NULL)
4808 if (view->view_id == view_id)
4817 get_tree_bounds(GtkTextBTree *tree,
4821 gtk_text_btree_get_iter_at_line_char(tree, start, 0, 0);
4822 gtk_text_btree_get_last_iter(tree, end);
4826 tag_changed_cb(GtkTextTagTable *table,
4828 gboolean size_changed,
4833 /* We need to queue a redisplay on all regions that are tagged with
4839 if (gtk_text_btree_get_iter_at_first_toggle(tree, &start, tag))
4841 /* Must be a last toggle if there was a first one. */
4842 gtk_text_btree_get_iter_at_last_toggle(tree, &end, tag);
4843 gtk_text_btree_invalidate_region(tree,
4854 while (view != NULL)
4858 gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
4859 gtk_text_layout_changed (view->layout, 0, height, height);
4867 tag_removed_cb(GtkTextTagTable *table,
4871 /* Remove the tag from the tree */
4876 get_tree_bounds(tree, &start, &end);
4878 gtk_text_btree_tag(&start, &end, tag, FALSE);
4879 gtk_text_btree_remove_tag_info (tree, tag);
4883 /* Rebalance the out-of-whack node "node" */
4885 gtk_text_btree_rebalance(GtkTextBTree *tree,
4886 GtkTextBTreeNode *node)
4889 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
4890 * up through the tree one GtkTextBTreeNode at a time until the root
4891 * GtkTextBTreeNode has been processed.
4894 while (node != NULL)
4896 GtkTextBTreeNode *new_node, *child;
4901 * Check to see if the GtkTextBTreeNode has too many children. If it does,
4902 * then split off all but the first MIN_CHILDREN into a separate
4903 * GtkTextBTreeNode following the original one. Then repeat until the
4904 * GtkTextBTreeNode has a decent size.
4907 if (node->num_children > MAX_CHILDREN)
4912 * If the GtkTextBTreeNode being split is the root
4913 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
4917 if (node->parent == NULL)
4919 new_node = gtk_text_btree_node_new();
4920 new_node->parent = NULL;
4921 new_node->next = NULL;
4922 new_node->summary = NULL;
4923 new_node->level = node->level + 1;
4924 new_node->children.node = node;
4925 recompute_node_counts(tree, new_node);
4926 tree->root_node = new_node;
4928 new_node = gtk_text_btree_node_new();
4929 new_node->parent = node->parent;
4930 new_node->next = node->next;
4931 node->next = new_node;
4932 new_node->summary = NULL;
4933 new_node->level = node->level;
4934 new_node->num_children = node->num_children - MIN_CHILDREN;
4935 if (node->level == 0)
4937 for (i = MIN_CHILDREN-1,
4938 line = node->children.line;
4939 i > 0; i--, line = line->next)
4941 /* Empty loop body. */
4943 new_node->children.line = line->next;
4948 for (i = MIN_CHILDREN-1,
4949 child = node->children.node;
4950 i > 0; i--, child = child->next)
4952 /* Empty loop body. */
4954 new_node->children.node = child->next;
4957 recompute_node_counts(tree, node);
4958 node->parent->num_children++;
4960 if (node->num_children <= MAX_CHILDREN)
4962 recompute_node_counts(tree, node);
4968 while (node->num_children < MIN_CHILDREN)
4970 GtkTextBTreeNode *other;
4971 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
4972 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
4973 int total_children, first_children, i;
4976 * Too few children for this GtkTextBTreeNode. If this is the root then,
4977 * it's OK for it to have less than MIN_CHILDREN children
4978 * as long as it's got at least two. If it has only one
4979 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
4980 * the tree and use its child as the new root.
4983 if (node->parent == NULL)
4985 if ((node->num_children == 1) && (node->level > 0))
4987 tree->root_node = node->children.node;
4988 tree->root_node->parent = NULL;
4989 summary_list_destroy(node->summary);
4996 * Not the root. Make sure that there are siblings to
5000 if (node->parent->num_children < 2)
5002 gtk_text_btree_rebalance(tree, node->parent);
5007 * Find a sibling neighbor to borrow from, and arrange for
5008 * node to be the earlier of the pair.
5011 if (node->next == NULL)
5013 for (other = node->parent->children.node;
5014 other->next != node;
5015 other = other->next)
5017 /* Empty loop body. */
5024 * We're going to either merge the two siblings together
5025 * into one GtkTextBTreeNode or redivide the children among them to
5026 * balance their loads. As preparation, join their two
5027 * child lists into a single list and remember the half-way
5028 * point in the list.
5031 total_children = node->num_children + other->num_children;
5032 first_children = total_children/2;
5033 if (node->children.node == NULL)
5035 node->children = other->children;
5036 other->children.node = NULL;
5037 other->children.line = NULL;
5039 if (node->level == 0)
5043 for (line = node->children.line, i = 1;
5045 line = line->next, i++)
5047 if (i == first_children)
5052 line->next = other->children.line;
5053 while (i <= first_children)
5062 GtkTextBTreeNode *child;
5064 for (child = node->children.node, i = 1;
5065 child->next != NULL;
5066 child = child->next, i++)
5068 if (i <= first_children)
5070 if (i == first_children)
5072 halfwaynode = child;
5076 child->next = other->children.node;
5077 while (i <= first_children)
5079 halfwaynode = child;
5080 child = child->next;
5086 * If the two siblings can simply be merged together, do it.
5089 if (total_children <= MAX_CHILDREN)
5091 recompute_node_counts(tree, node);
5092 node->next = other->next;
5093 node->parent->num_children--;
5094 summary_list_destroy(other->summary);
5100 * The siblings can't be merged, so just divide their
5101 * children evenly between them.
5104 if (node->level == 0)
5106 other->children.line = halfwayline->next;
5107 halfwayline->next = NULL;
5111 other->children.node = halfwaynode->next;
5112 halfwaynode->next = NULL;
5115 recompute_node_counts(tree, node);
5116 recompute_node_counts(tree, other);
5119 node = node->parent;
5124 post_insert_fixup(GtkTextBTree *tree,
5126 gint line_count_delta,
5127 gint char_count_delta)
5130 GtkTextBTreeNode *node;
5133 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5134 * point, then rebalance the tree if necessary.
5137 for (node = line->parent ; node != NULL;
5138 node = node->parent)
5140 node->num_lines += line_count_delta;
5141 node->num_chars += char_count_delta;
5143 node = line->parent;
5144 node->num_children += line_count_delta;
5146 if (node->num_children > MAX_CHILDREN)
5148 gtk_text_btree_rebalance(tree, node);
5151 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5152 gtk_text_btree_check(tree);
5155 static GtkTextTagInfo*
5156 gtk_text_btree_get_existing_tag_info(GtkTextBTree *tree,
5159 GtkTextTagInfo *info;
5163 list = tree->tag_infos;
5164 while (list != NULL)
5167 if (info->tag == tag)
5170 list = g_slist_next(list);
5176 static GtkTextTagInfo*
5177 gtk_text_btree_get_tag_info(GtkTextBTree *tree,
5180 GtkTextTagInfo *info;
5182 info = gtk_text_btree_get_existing_tag_info(tree, tag);
5186 /* didn't find it, create. */
5188 info = g_new(GtkTextTagInfo, 1);
5191 gtk_object_ref(GTK_OBJECT(tag));
5192 info->tag_root = NULL;
5193 info->toggle_count = 0;
5195 tree->tag_infos = g_slist_prepend(tree->tag_infos, info);
5202 gtk_text_btree_remove_tag_info(GtkTextBTree *tree,
5205 GtkTextTagInfo *info;
5210 list = tree->tag_infos;
5211 while (list != NULL)
5214 if (info->tag == tag)
5218 prev->next = list->next;
5222 tree->tag_infos = list->next;
5227 gtk_object_unref(GTK_OBJECT(info->tag));
5233 list = g_slist_next(list);
5236 g_assert_not_reached();
5241 recompute_level_zero_counts(GtkTextBTreeNode *node)
5244 GtkTextLineSegment *seg;
5246 g_assert(node->level == 0);
5248 line = node->children.line;
5249 while (line != NULL)
5251 node->num_children++;
5254 if (line->parent != node)
5255 gtk_text_line_set_parent(line, node);
5257 seg = line->segments;
5261 node->num_chars += seg->char_count;
5263 if (((seg->type != >k_text_toggle_on_type)
5264 && (seg->type != >k_text_toggle_off_type))
5265 || !(seg->body.toggle.inNodeCounts))
5271 GtkTextTagInfo *info;
5273 info = seg->body.toggle.info;
5275 gtk_text_btree_node_adjust_toggle_count(node, info, 1);
5286 recompute_level_nonzero_counts(GtkTextBTreeNode *node)
5289 GtkTextBTreeNode *child;
5291 g_assert(node->level > 0);
5293 child = node->children.node;
5294 while (child != NULL)
5296 node->num_children += 1;
5297 node->num_lines += child->num_lines;
5298 node->num_chars += child->num_chars;
5300 if (child->parent != node)
5302 child->parent = node;
5303 gtk_text_btree_node_invalidate_upward(node, NULL);
5306 summary = child->summary;
5307 while (summary != NULL)
5309 gtk_text_btree_node_adjust_toggle_count(node,
5311 summary->toggle_count);
5313 summary = summary->next;
5316 child = child->next;
5321 *----------------------------------------------------------------------
5323 * recompute_node_counts --
5325 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5326 * (tags, child information, etc.) by scanning the information in
5327 * its descendants. This procedure is called during rebalancing
5328 * when a GtkTextBTreeNode's child structure has changed.
5334 * The tag counts for node are modified to reflect its current
5335 * child structure, as are its num_children, num_lines, num_chars fields.
5336 * Also, all of the childrens' parent fields are made to point
5339 *----------------------------------------------------------------------
5343 recompute_node_counts(GtkTextBTree *tree, GtkTextBTreeNode *node)
5346 Summary *summary, *summary2;
5349 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5350 * the existing Summary records (most of them will probably be reused).
5353 summary = node->summary;
5354 while (summary != NULL)
5356 summary->toggle_count = 0;
5357 summary = summary->next;
5360 node->num_children = 0;
5361 node->num_lines = 0;
5362 node->num_chars = 0;
5365 * Scan through the children, adding the childrens' tag counts into
5366 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5370 if (node->level == 0)
5371 recompute_level_zero_counts(node);
5373 recompute_level_nonzero_counts(node);
5378 gtk_text_btree_node_check_valid (node, view->view_id);
5383 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5384 * records that still have a zero count, or that have all the toggles.
5385 * The GtkTextBTreeNode with the children that account for all the tags toggles
5386 * have no summary information, and they become the tag_root for the tag.
5390 for (summary = node->summary; summary != NULL; )
5392 if (summary->toggle_count > 0 &&
5393 summary->toggle_count < summary->info->toggle_count)
5395 if (node->level == summary->info->tag_root->level)
5398 * The tag's root GtkTextBTreeNode split and some toggles left.
5399 * The tag root must move up a level.
5401 summary->info->tag_root = node->parent;
5404 summary = summary->next;
5407 if (summary->toggle_count == summary->info->toggle_count)
5410 * A GtkTextBTreeNode merge has collected all the toggles under
5411 * one GtkTextBTreeNode. Push the root down to this level.
5413 summary->info->tag_root = node;
5415 if (summary2 != NULL)
5417 summary2->next = summary->next;
5418 summary_destroy (summary);
5419 summary = summary2->next;
5423 node->summary = summary->next;
5424 summary_destroy (summary);
5425 summary = node->summary;
5431 change_node_toggle_count(GtkTextBTreeNode *node,
5432 GtkTextTagInfo *info,
5433 gint delta) /* may be negative */
5435 Summary *summary, *prevPtr;
5436 GtkTextBTreeNode *node2Ptr;
5437 int rootLevel; /* Level of original tag root */
5439 info->toggle_count += delta;
5441 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5443 info->tag_root = node;
5448 * Note the level of the existing root for the tag so we can detect
5449 * if it needs to be moved because of the toggle count change.
5452 rootLevel = info->tag_root->level;
5455 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5456 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5460 for ( ; node != info->tag_root; node = node->parent)
5463 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5464 * perhaps all we have to do is adjust its count.
5467 for (prevPtr = NULL, summary = node->summary;
5469 prevPtr = summary, summary = summary->next)
5471 if (summary->info == info)
5476 if (summary != NULL)
5478 summary->toggle_count += delta;
5479 if (summary->toggle_count > 0 &&
5480 summary->toggle_count < info->toggle_count)
5484 if (summary->toggle_count != 0)
5487 * Should never find a GtkTextBTreeNode with max toggle count at this
5488 * point (there shouldn't have been a summary entry in the
5492 g_error("change_node_toggle_count: bad toggle count (%d) max (%d)",
5493 summary->toggle_count, info->toggle_count);
5497 * Zero toggle count; must remove this tag from the list.
5500 if (prevPtr == NULL)
5502 node->summary = summary->next;
5506 prevPtr->next = summary->next;
5508 summary_destroy (summary);
5513 * This tag isn't currently in the summary information list.
5516 if (rootLevel == node->level)
5520 * The old tag root is at the same level in the tree as this
5521 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5522 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5523 * as well as the old root (if not, we'll move it up again
5524 * the next time through the loop). To push it up one level
5525 * we copy the original toggle count into the summary
5526 * information at the old root and change the root to its
5527 * parent GtkTextBTreeNode.
5530 GtkTextBTreeNode *rootnode = info->tag_root;
5531 summary = (Summary *) g_malloc(sizeof(Summary));
5532 summary->info = info;
5533 summary->toggle_count = info->toggle_count - delta;
5534 summary->next = rootnode->summary;
5535 rootnode->summary = summary;
5536 rootnode = rootnode->parent;
5537 rootLevel = rootnode->level;
5538 info->tag_root = rootnode;
5540 summary = (Summary *) g_malloc(sizeof(Summary));
5541 summary->info = info;
5542 summary->toggle_count = delta;
5543 summary->next = node->summary;
5544 node->summary = summary;
5549 * If we've decremented the toggle count, then it may be necessary
5550 * to push the tag root down one or more levels.
5557 if (info->toggle_count == 0)
5559 info->tag_root = (GtkTextBTreeNode *) NULL;
5562 node = info->tag_root;
5563 while (node->level > 0)
5566 * See if a single child GtkTextBTreeNode accounts for all of the tag's
5567 * toggles. If so, push the root down one level.
5570 for (node2Ptr = node->children.node;
5571 node2Ptr != (GtkTextBTreeNode *)NULL ;
5572 node2Ptr = node2Ptr->next)
5574 for (prevPtr = NULL, summary = node2Ptr->summary;
5576 prevPtr = summary, summary = summary->next)
5578 if (summary->info == info)
5583 if (summary == NULL)
5587 if (summary->toggle_count != info->toggle_count)
5590 * No GtkTextBTreeNode has all toggles, so the root is still valid.
5597 * This GtkTextBTreeNode has all the toggles, so push down the root.
5600 if (prevPtr == NULL)
5602 node2Ptr->summary = summary->next;
5606 prevPtr->next = summary->next;
5608 summary_destroy (summary);
5609 info->tag_root = node2Ptr;
5612 node = info->tag_root;
5617 *----------------------------------------------------------------------
5621 * This is a utility procedure used by gtk_text_btree_get_tags. It
5622 * increments the count for a particular tag, adding a new
5623 * entry for that tag if there wasn't one previously.
5629 * The information at *tagInfoPtr may be modified, and the arrays
5630 * may be reallocated to make them larger.
5632 *----------------------------------------------------------------------
5636 inc_count(GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
5641 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
5642 count > 0; tag_p++, count--)
5646 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
5652 * There isn't currently an entry for this tag, so we have to
5653 * make a new one. If the arrays are full, then enlarge the
5657 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
5659 GtkTextTag **newTags;
5660 int *newCounts, newSize;
5662 newSize = 2*tagInfoPtr->arraySize;
5663 newTags = (GtkTextTag **) g_malloc((unsigned)
5664 (newSize*sizeof(GtkTextTag *)));
5665 memcpy((void *) newTags, (void *) tagInfoPtr->tags,
5666 tagInfoPtr->arraySize *sizeof(GtkTextTag *));
5667 g_free((char *) tagInfoPtr->tags);
5668 tagInfoPtr->tags = newTags;
5669 newCounts = (int *) g_malloc((unsigned) (newSize*sizeof(int)));
5670 memcpy((void *) newCounts, (void *) tagInfoPtr->counts,
5671 tagInfoPtr->arraySize *sizeof(int));
5672 g_free((char *) tagInfoPtr->counts);
5673 tagInfoPtr->counts = newCounts;
5674 tagInfoPtr->arraySize = newSize;
5677 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
5678 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
5679 tagInfoPtr->numTags++;
5683 gtk_text_btree_link_segment(GtkTextLineSegment *seg,
5684 const GtkTextIter *iter)
5686 GtkTextLineSegment *prev;
5690 line = gtk_text_iter_get_text_line(iter);
5691 tree = gtk_text_iter_get_btree(iter);
5693 prev = gtk_text_line_segment_split(iter);
5696 seg->next = line->segments;
5697 line->segments = seg;
5701 seg->next = prev->next;
5705 segments_changed(tree);
5707 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5708 gtk_text_btree_check(tree);
5712 gtk_text_btree_unlink_segment(GtkTextBTree *tree,
5713 GtkTextLineSegment *seg,
5716 GtkTextLineSegment *prev;
5718 if (line->segments == seg)
5720 line->segments = seg->next;
5724 for (prev = line->segments; prev->next != seg;
5727 /* Empty loop body. */
5729 prev->next = seg->next;
5732 segments_changed(tree);
5736 * This is here because it requires BTree internals, it logically
5737 * belongs in gtktextsegment.c
5742 *--------------------------------------------------------------
5744 * toggle_segment_check_func --
5746 * This procedure is invoked to perform consistency checks
5747 * on toggle segments.
5753 * If a consistency problem is found the procedure g_errors.
5755 *--------------------------------------------------------------
5759 toggle_segment_check_func(GtkTextLineSegment *segPtr,
5765 if (segPtr->byte_count != 0)
5767 g_error("toggle_segment_check_func: segment had non-zero size");
5769 if (!segPtr->body.toggle.inNodeCounts)
5771 g_error("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
5773 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
5774 for (summary = line->parent->summary; ;
5775 summary = summary->next)
5777 if (summary == NULL)
5781 g_error("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
5788 if (summary->info == segPtr->body.toggle.info)
5792 g_error("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
5804 gtk_text_btree_node_view_check_consistency (GtkTextBTreeNode *node,
5811 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
5812 &width, &height, &valid);
5813 if (nd->width != width ||
5814 nd->height != height ||
5815 !nd->valid != !valid)
5817 g_error ("Node aggregates for view %p are invalid:\n"
5818 "Are (%d,%d,%s), should be (%d,%d,%s)",
5820 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
5821 width, height, valid ? "TRUE" : "FALSE");
5826 gtk_text_btree_node_check_consistency(GtkTextBTreeNode *node)
5828 GtkTextBTreeNode *childnode;
5829 Summary *summary, *summary2;
5831 GtkTextLineSegment *segPtr;
5832 int num_children, num_lines, num_chars, toggle_count, min_children;
5833 GtkTextLineData *ld;
5836 if (node->parent != NULL)
5838 min_children = MIN_CHILDREN;
5840 else if (node->level > 0)
5847 if ((node->num_children < min_children)
5848 || (node->num_children > MAX_CHILDREN))
5850 g_error("gtk_text_btree_node_check_consistency: bad child count (%d)",
5851 node->num_children);
5854 nd = node->node_data;
5857 gtk_text_btree_node_view_check_consistency (node, nd);
5864 if (node->level == 0)
5866 for (line = node->children.line; line != NULL;
5869 if (line->parent != node)
5871 g_error("gtk_text_btree_node_check_consistency: line doesn't point to parent");
5873 if (line->segments == NULL)
5875 g_error("gtk_text_btree_node_check_consistency: line has no segments");
5881 /* Just ensuring we don't segv while doing this loop */
5886 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
5888 if (segPtr->type->checkFunc != NULL)
5890 (*segPtr->type->checkFunc)(segPtr, line);
5892 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
5893 && (segPtr->next != NULL)
5894 && (segPtr->next->byte_count == 0)
5895 && (segPtr->next->type->leftGravity))
5897 g_error("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
5899 if ((segPtr->next == NULL)
5900 && (segPtr->type != >k_text_char_type))
5902 g_error("gtk_text_btree_node_check_consistency: line ended with wrong type");
5905 num_chars += segPtr->char_count;
5914 for (childnode = node->children.node; childnode != NULL;
5915 childnode = childnode->next)
5917 if (childnode->parent != node)
5919 g_error("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
5921 if (childnode->level != (node->level-1))
5923 g_error("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
5924 node->level, childnode->level);
5926 gtk_text_btree_node_check_consistency (childnode);
5927 for (summary = childnode->summary; summary != NULL;
5928 summary = summary->next)
5930 for (summary2 = node->summary; ;
5931 summary2 = summary2->next)
5933 if (summary2 == NULL)
5935 if (summary->info->tag_root == node)
5939 g_error("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
5940 summary->info->tag->name,
5941 "present in parent summaries");
5943 if (summary->info == summary2->info)
5950 num_lines += childnode->num_lines;
5951 num_chars += childnode->num_chars;
5954 if (num_children != node->num_children)
5956 g_error("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
5957 num_children, node->num_children);
5959 if (num_lines != node->num_lines)
5961 g_error("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
5962 num_lines, node->num_lines);
5964 if (num_chars != node->num_chars)
5966 g_error("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
5967 num_chars, node->num_chars);
5970 for (summary = node->summary; summary != NULL;
5971 summary = summary->next)
5973 if (summary->info->toggle_count == summary->toggle_count)
5975 g_error("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
5976 summary->info->tag->name);
5979 if (node->level == 0)
5981 for (line = node->children.line; line != NULL;
5984 for (segPtr = line->segments; segPtr != NULL;
5985 segPtr = segPtr->next)
5987 if ((segPtr->type != >k_text_toggle_on_type)
5988 && (segPtr->type != >k_text_toggle_off_type))
5992 if (segPtr->body.toggle.info == summary->info)
5994 if (!segPtr->body.toggle.inNodeCounts)
5995 g_error ("Toggle segment not in the node counts");
6004 for (childnode = node->children.node;
6006 childnode = childnode->next)
6008 for (summary2 = childnode->summary;
6010 summary2 = summary2->next)
6012 if (summary2->info == summary->info)
6014 toggle_count += summary2->toggle_count;
6019 if (toggle_count != summary->toggle_count)
6021 g_error("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6022 toggle_count, summary->toggle_count);
6024 for (summary2 = summary->next; summary2 != NULL;
6025 summary2 = summary2->next)
6027 if (summary2->info == summary->info)
6029 g_error("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6030 summary->info->tag->name);
6037 listify_foreach(GtkTextTag *tag, gpointer user_data)
6039 GSList** listp = user_data;
6041 *listp = g_slist_prepend(*listp, tag);
6045 list_of_tags(GtkTextTagTable *table)
6047 GSList *list = NULL;
6049 gtk_text_tag_table_foreach(table, listify_foreach, &list);
6055 gtk_text_btree_check (GtkTextBTree *tree)
6058 GtkTextBTreeNode *node;
6060 GtkTextLineSegment *seg;
6062 GSList *taglist = NULL;
6064 GtkTextTagInfo *info;
6067 * Make sure that the tag toggle counts and the tag root pointers are OK.
6069 for (taglist = list_of_tags(tree->table);
6070 taglist != NULL ; taglist = taglist->next)
6072 tag = taglist->data;
6073 info = gtk_text_btree_get_existing_tag_info(tree, tag);
6076 node = info->tag_root;
6079 if (info->toggle_count != 0)
6081 g_error("gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6082 tag->name, info->toggle_count);
6084 continue; /* no ranges for the tag */
6086 else if (info->toggle_count == 0)
6088 g_error("gtk_text_btree_check found root for \"%s\" with no toggles",
6091 else if (info->toggle_count & 1)
6093 g_error("gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6094 tag->name, info->toggle_count);
6096 for (summary = node->summary; summary != NULL;
6097 summary = summary->next)
6099 if (summary->info->tag == tag)
6101 g_error("gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6105 if (node->level > 0)
6107 for (node = node->children.node ; node != NULL ;
6110 for (summary = node->summary; summary != NULL;
6111 summary = summary->next)
6113 if (summary->info->tag == tag)
6115 count += summary->toggle_count;
6122 GtkTextLineSegmentClass * last = NULL;
6124 for (line = node->children.line ; line != NULL ;
6127 for (seg = line->segments; seg != NULL;
6130 if ((seg->type == >k_text_toggle_on_type ||
6131 seg->type == >k_text_toggle_off_type) &&
6132 seg->body.toggle.info->tag == tag)
6134 if (last == seg->type)
6135 g_error ("Two consecutive toggles on or off weren't merged");
6136 if (!seg->body.toggle.inNodeCounts)
6137 g_error ("Toggle segment not in the node counts");
6146 if (count != info->toggle_count)
6148 g_error("gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6149 info->toggle_count, tag->name, count);
6154 g_slist_free(taglist);
6158 * Call a recursive procedure to do the main body of checks.
6161 node = tree->root_node;
6162 gtk_text_btree_node_check_consistency(tree->root_node);
6165 * Make sure that there are at least two lines in the text and
6166 * that the last line has no characters except a newline.
6169 if (node->num_lines < 2)
6171 g_error("gtk_text_btree_check: less than 2 lines in tree");
6173 if (node->num_chars < 2)
6175 g_error("gtk_text_btree_check: less than 2 chars in tree");
6177 while (node->level > 0)
6179 node = node->children.node;
6180 while (node->next != NULL)
6185 line = node->children.line;
6186 while (line->next != NULL)
6190 seg = line->segments;
6191 while ((seg->type == >k_text_toggle_off_type)
6192 || (seg->type == >k_text_right_mark_type)
6193 || (seg->type == >k_text_left_mark_type))
6196 * It's OK to toggle a tag off in the last line, but
6197 * not to start a new range. It's also OK to have marks
6203 if (seg->type != >k_text_char_type)
6205 g_error("gtk_text_btree_check: last line has bogus segment type");
6207 if (seg->next != NULL)
6209 g_error("gtk_text_btree_check: last line has too many segments");
6211 if (seg->byte_count != 1)
6213 g_error("gtk_text_btree_check: last line has wrong # characters: %d",
6216 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6218 g_error("gtk_text_btree_check: last line had bad value: %s",
6223 void gtk_text_btree_spew_line(GtkTextBTree* tree, GtkTextLine* line);
6224 void gtk_text_btree_spew_segment(GtkTextBTree* tree, GtkTextLineSegment* seg);
6225 void gtk_text_btree_spew_node(GtkTextBTreeNode *node, int indent);
6226 void gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6229 gtk_text_btree_spew (GtkTextBTree *tree)
6234 printf("%d lines in tree %p\n",
6235 gtk_text_btree_line_count(tree), tree);
6237 line = gtk_text_btree_get_line(tree, 0, &real_line);
6239 while (line != NULL)
6241 gtk_text_btree_spew_line(tree, line);
6242 line = gtk_text_line_next(line);
6245 printf("=================== Tag information\n");
6250 list = tree->tag_infos;
6252 while (list != NULL)
6254 GtkTextTagInfo *info;
6258 printf (" tag `%s': root at %p, toggle count %d\n",
6259 info->tag->name, info->tag_root, info->toggle_count);
6261 list = g_slist_next (list);
6265 printf("=================== Tree nodes\n");
6268 gtk_text_btree_spew_node (tree->root_node, 0);
6273 gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6276 GtkTextLineSegment *seg;
6278 spaces = g_strnfill (indent, ' ');
6280 printf ("%sline %p chars %d bytes %d\n",
6282 gtk_text_line_char_count (line),
6283 gtk_text_line_byte_count (line));
6285 seg = line->segments;
6288 if (seg->type == >k_text_char_type)
6290 gchar* str = g_strndup(seg->body.chars, MIN (seg->byte_count, 10));
6299 printf("%s chars `%s'...\n", spaces, str);
6302 else if (seg->type == >k_text_right_mark_type)
6304 printf("%s right mark `%s'\n", spaces, seg->body.mark.name);
6306 else if (seg->type == >k_text_left_mark_type)
6308 printf("%s left mark `%s'\n", spaces, seg->body.mark.name);
6310 else if (seg->type == >k_text_toggle_on_type ||
6311 seg->type == >k_text_toggle_off_type)
6313 printf("%s tag `%s' %s\n",
6314 spaces, seg->body.toggle.info->tag->name,
6315 seg->type == >k_text_toggle_off_type ? "off" : "on");
6325 gtk_text_btree_spew_node(GtkTextBTreeNode *node, int indent)
6328 GtkTextBTreeNode *iter;
6331 spaces = g_strnfill (indent, ' ');
6333 printf ("%snode %p level %d children %d lines %d chars %d\n",
6334 spaces, node, node->level,
6335 node->num_children, node->num_lines, node->num_chars);
6340 printf ("%s %d toggles of `%s' below this node\n",
6341 spaces, s->toggle_count, s->info->tag->name);
6347 if (node->level > 0)
6349 iter = node->children.node;
6350 while (iter != NULL)
6352 gtk_text_btree_spew_node (iter, indent + 2);
6359 GtkTextLine *line = node->children.line;
6360 while (line != NULL)
6362 gtk_text_btree_spew_line_short (line, indent + 2);
6370 gtk_text_btree_spew_line(GtkTextBTree* tree, GtkTextLine* line)
6372 GtkTextLineSegment * seg;
6374 printf("%4d| line: %p parent: %p next: %p\n",
6375 gtk_text_line_get_number(line), line, line->parent, line->next);
6377 seg = line->segments;
6381 gtk_text_btree_spew_segment(tree, seg);
6387 gtk_text_btree_spew_segment(GtkTextBTree* tree, GtkTextLineSegment * seg)
6389 printf(" segment: %p type: %s bytes: %d chars: %d\n",
6390 seg, seg->type->name, seg->byte_count, seg->char_count);
6392 if (seg->type == >k_text_char_type)
6394 gchar* str = g_strndup(seg->body.chars, seg->byte_count);
6395 printf(" `%s'\n", str);
6398 else if (seg->type == >k_text_right_mark_type)
6400 printf(" right mark `%s'\n", seg->body.mark.name);
6402 else if (seg->type == >k_text_left_mark_type)
6404 printf(" left mark `%s'\n", seg->body.mark.name);
6406 else if (seg->type == >k_text_toggle_on_type ||
6407 seg->type == >k_text_toggle_off_type)
6409 printf(" tag `%s' priority %d\n",
6410 seg->body.toggle.info->tag->name,
6411 seg->body.toggle.info->tag->priority);