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;
437 tree->insert_mark->body.mark.visible = TRUE;
439 tree->selection_bound_mark =
440 (GtkTextLineSegment*) gtk_text_btree_set_mark(tree,
447 tree->selection_bound_mark->body.mark.not_deleteable = TRUE;
449 _mark_segment_ref(tree->insert_mark);
450 _mark_segment_ref(tree->selection_bound_mark);
459 gtk_text_btree_ref (GtkTextBTree *tree)
461 g_return_if_fail(tree != NULL);
462 g_return_if_fail(tree->refcount > 0);
468 mark_destroy_foreach (gpointer key, gpointer value, gpointer user_data)
470 _mark_segment_unref (value);
474 gtk_text_btree_unref (GtkTextBTree *tree)
476 g_return_if_fail(tree != NULL);
477 g_return_if_fail(tree->refcount > 0);
481 if (tree->refcount == 0)
483 gtk_text_btree_node_destroy(tree, tree->root_node);
485 g_hash_table_foreach(tree->mark_table,
486 mark_destroy_foreach,
488 g_hash_table_destroy(tree->mark_table);
490 _mark_segment_unref(tree->insert_mark);
491 _mark_segment_unref(tree->selection_bound_mark);
493 gtk_signal_disconnect(GTK_OBJECT(tree->table),
494 tree->tag_changed_handler);
496 gtk_signal_disconnect(GTK_OBJECT(tree->table),
497 tree->tag_removed_handler);
499 gtk_object_unref(GTK_OBJECT(tree->table));
506 gtk_text_btree_get_buffer (GtkTextBTree *tree)
512 gtk_text_btree_get_chars_changed_stamp (GtkTextBTree *tree)
514 return tree->chars_changed_stamp;
518 gtk_text_btree_get_segments_changed_stamp (GtkTextBTree *tree)
520 return tree->segments_changed_stamp;
524 gtk_text_btree_segments_changed (GtkTextBTree *tree)
526 g_return_if_fail(tree != NULL);
527 segments_changed(tree);
531 * Indexable segment mutation
535 gtk_text_btree_delete (GtkTextIter *start,
538 GtkTextLineSegment *prev_seg; /* The segment just before the start
539 * of the deletion range. */
540 GtkTextLineSegment *last_seg; /* The segment just after the end
541 * of the deletion range. */
542 GtkTextLineSegment *seg, *next;
543 GtkTextLine *curline;
544 GtkTextBTreeNode *curnode, *node;
546 GtkTextLine *start_line;
547 GtkTextLine *end_line;
548 GtkTextLine *deleted_lines = NULL; /* List of lines we've deleted */
549 gint start_byte_offset;
551 g_return_if_fail(start != NULL);
552 g_return_if_fail(end != NULL);
553 g_return_if_fail(gtk_text_iter_get_btree(start) ==
554 gtk_text_iter_get_btree(end));
556 gtk_text_iter_reorder(start, end);
558 tree = gtk_text_iter_get_btree(start);
562 * The code below is ugly, but it's needed to make sure there
563 * is always a dummy empty line at the end of the text. If the
564 * final newline of the file (just before the dummy line) is being
565 * deleted, then back up index to just before the newline. If
566 * there is a newline just before the first character being deleted,
567 * then back up the first index too, so that an even number of lines
568 * gets deleted. Furthermore, remove any tags that are present on
569 * the newline that isn't going to be deleted after all (this simulates
570 * deleting the newline and then adding a "clean" one back again).
576 line1 = gtk_text_iter_get_line(start);
577 line2 = gtk_text_iter_get_line(end);
579 if (line2 == gtk_text_btree_line_count(tree))
583 GtkTextIter orig_end;
586 gtk_text_iter_prev_char(end);
590 if (gtk_text_iter_get_line_offset(start) == 0 &&
593 gtk_text_iter_prev_char(start);
597 tags = gtk_text_btree_get_tags(end,
605 while (i < array_size)
607 gtk_text_btree_tag(end, &orig_end, tags[i], FALSE);
617 /* Broadcast the need for redisplay before we break the iterators */
618 gtk_text_btree_invalidate_region(tree, start, end);
620 /* Save the byte offset so we can reset the iterators */
621 start_byte_offset = gtk_text_iter_get_line_index(start);
623 start_line = gtk_text_iter_get_text_line(start);
624 end_line = gtk_text_iter_get_text_line(end);
627 * Split the start and end segments, so we have a place
628 * to insert our new text.
630 * Tricky point: split at end first; otherwise the split
631 * at end may invalidate seg and/or prev_seg. This allows
632 * us to avoid invalidating segments for start.
635 last_seg = gtk_text_line_segment_split(end);
636 if (last_seg != NULL)
637 last_seg = last_seg->next;
639 last_seg = end_line->segments;
641 prev_seg = gtk_text_line_segment_split(start);
642 if (prev_seg != NULL)
644 seg = prev_seg->next;
645 prev_seg->next = last_seg;
649 seg = start_line->segments;
650 start_line->segments = last_seg;
653 /* notify iterators that their segments need recomputation,
654 just for robustness. */
655 segments_changed(tree);
658 * Delete all of the segments between prev_seg and last_seg.
661 curline = start_line;
662 curnode = curline->parent;
663 while (seg != last_seg)
669 GtkTextLine *nextline;
672 * We just ran off the end of a line. First find the
673 * next line, then go back to the old line and delete it
674 * (unless it's the starting line for the range).
677 nextline = gtk_text_line_next(curline);
678 if (curline != start_line)
680 if (curnode == start_line->parent)
681 start_line->next = curline->next;
683 curnode->children.line = curline->next;
685 for (node = curnode; node != NULL;
688 node->num_lines -= 1;
691 curnode->num_children -= 1;
692 curline->next = deleted_lines;
693 deleted_lines = curline;
697 seg = curline->segments;
700 * If the GtkTextBTreeNode is empty then delete it and its parents,
701 * recursively upwards until a non-empty GtkTextBTreeNode is found.
704 while (curnode->num_children == 0)
706 GtkTextBTreeNode *parent;
708 parent = curnode->parent;
709 if (parent->children.node == curnode)
711 parent->children.node = curnode->next;
715 GtkTextBTreeNode *prevnode = parent->children.node;
716 while (prevnode->next != curnode)
718 prevnode = prevnode->next;
720 prevnode->next = curnode->next;
722 parent->num_children--;
726 curnode = curline->parent;
731 char_count = seg->char_count;
733 if ((*seg->type->deleteFunc)(seg, curline, 0) != 0)
736 * This segment refuses to die. Move it to prev_seg and
737 * advance prev_seg if the segment has left gravity.
740 if (prev_seg == NULL)
742 seg->next = start_line->segments;
743 start_line->segments = seg;
747 seg->next = prev_seg->next;
748 prev_seg->next = seg;
750 if (seg->type->leftGravity)
757 /* Segment is gone. Decrement the char count of the node and
759 for (node = curnode; node != NULL;
762 node->num_chars -= char_count;
770 * If the beginning and end of the deletion range are in different
771 * lines, join the two lines together and discard the ending line.
774 if (start_line != end_line)
777 GtkTextBTreeNode *ancestor_node;
779 GtkTextLine *prevline;
781 for (seg = last_seg; seg != NULL;
784 if (seg->type->lineChangeFunc != NULL)
786 (*seg->type->lineChangeFunc)(seg, end_line);
789 curnode = end_line->parent;
790 for (node = curnode; node != NULL;
795 curnode->num_children--;
796 prevline = curnode->children.line;
797 if (prevline == end_line)
799 curnode->children.line = end_line->next;
803 while (prevline->next != end_line)
805 prevline = prevline->next;
807 prevline->next = end_line->next;
809 end_line->next = deleted_lines;
810 deleted_lines = end_line;
812 /* We now fix up the per-view aggregates. We add all the height and
813 * width for the deleted lines to the start line, so that when revalidation
814 * occurs, the correct change in size is seen.
816 ancestor_node = gtk_text_btree_node_common_parent (curnode, start_line->parent);
823 gint deleted_width = 0;
824 gint deleted_height = 0;
826 line = deleted_lines;
829 GtkTextLine *next_line = line->next;
830 ld = gtk_text_line_get_data (line, view->view_id);
834 deleted_width = MAX (deleted_width, ld->width);
835 deleted_height += ld->height;
839 gtk_text_line_destroy(tree, line);
844 if (deleted_width > 0 || deleted_height > 0)
846 ld = gtk_text_line_get_data (start_line, view->view_id);
848 /* FIXME: ld is _NOT_ necessarily non-null here, but there is currently
849 * no way to add ld without also validating the node, which would
850 * be improper at this point.
852 /* This assertion does actually fail sometimes, must
853 fix before stable release -hp */
856 ld->width = MAX (deleted_width, ld->width);
857 ld->height += deleted_height;
861 gtk_text_btree_node_check_valid_downward (ancestor_node, view->view_id);
862 if (ancestor_node->parent)
863 gtk_text_btree_node_check_valid_upward (ancestor_node->parent, view->view_id);
868 gtk_text_btree_rebalance(tree, curnode);
872 * Cleanup the segments in the new line.
875 cleanup_line(start_line);
878 * Lastly, rebalance the first GtkTextBTreeNode of the range.
881 gtk_text_btree_rebalance(tree, start_line->parent);
883 /* Notify outstanding iterators that they
886 segments_changed(tree);
888 if (gtk_debug_flags & GTK_DEBUG_TEXT)
889 gtk_text_btree_check(tree);
891 /* Re-initialize our iterators */
892 gtk_text_btree_get_iter_at_line(tree, start, start_line, start_byte_offset);
897 gtk_text_btree_insert (GtkTextIter *iter,
901 GtkTextLineSegment *prev_seg; /* The segment just before the first
902 * new segment (NULL means new segment
903 * is at beginning of line). */
904 GtkTextLineSegment *cur_seg; /* Current segment; new characters
905 * are inserted just after this one.
906 * NULL means insert at beginning of
908 GtkTextLine *line; /* Current line (new segments are
909 * added to this line). */
910 GtkTextLineSegment *seg;
911 GtkTextLine *newline;
912 int chunkSize; /* # characters in current chunk. */
913 guint sol; /* start of line */
914 guint eol; /* Pointer to character just after last
915 * one in current chunk. */
916 int line_count_delta; /* Counts change to total number of
919 int char_count_delta; /* change to number of chars */
921 gint start_byte_index;
922 GtkTextLine *start_line;
924 g_return_if_fail(text != NULL);
925 g_return_if_fail(iter != NULL);
930 /* extract iterator info */
931 tree = gtk_text_iter_get_btree(iter);
932 line = gtk_text_iter_get_text_line(iter);
934 start_byte_index = gtk_text_iter_get_line_index(iter);
936 /* Get our insertion segment split */
937 prev_seg = gtk_text_line_segment_split(iter);
940 /* Invalidate all iterators */
942 segments_changed(tree);
945 * Chop the text up into lines and create a new segment for
946 * each line, plus a new line for the leftovers from the
952 line_count_delta = 0;
953 char_count_delta = 0;
956 for (; eol < len; eol++)
958 if (text[eol] == '\n')
964 chunkSize = eol - sol;
966 seg = char_segment_new(&text[sol], chunkSize);
968 char_count_delta += seg->char_count;
972 seg->next = line->segments;
973 line->segments = seg;
977 seg->next = cur_seg->next;
981 if (text[eol-1] != '\n')
987 * The chunk ended with a newline, so create a new GtkTextLine
988 * and move the remainder of the old line to it.
991 newline = gtk_text_line_new();
992 gtk_text_line_set_parent(newline, line->parent);
993 newline->next = line->next;
994 line->next = newline;
995 newline->segments = seg->next;
1005 * Cleanup the starting line for the insertion, plus the ending
1006 * line if it's different.
1009 cleanup_line(start_line);
1010 if (line != start_line)
1015 post_insert_fixup(tree, line, line_count_delta, char_count_delta);
1017 /* Invalidate our region, and reset the iterator the user
1018 passed in to point to the end of the inserted text. */
1024 gtk_text_btree_get_iter_at_line(tree,
1030 /* We could almost certainly be more efficient here
1031 by saving the information from the insertion loop
1033 gtk_text_iter_forward_chars(&end, char_count_delta);
1035 gtk_text_btree_invalidate_region(tree,
1039 /* Convenience for the user */
1045 gtk_text_btree_insert_pixbuf (GtkTextIter *iter,
1048 GtkTextLineSegment *seg;
1050 GtkTextLineSegment *prevPtr;
1053 gint start_byte_offset;
1055 line = gtk_text_iter_get_text_line(iter);
1056 tree = gtk_text_iter_get_btree(iter);
1057 start_byte_offset = gtk_text_iter_get_line_index(iter);
1059 seg = _pixbuf_segment_new (pixbuf);
1061 prevPtr = gtk_text_line_segment_split(iter);
1062 if (prevPtr == NULL)
1064 seg->next = line->segments;
1065 line->segments = seg;
1069 seg->next = prevPtr->next;
1070 prevPtr->next = seg;
1073 post_insert_fixup(tree, line, 0, seg->char_count);
1075 chars_changed(tree);
1076 segments_changed(tree);
1078 /* reset *iter for the user, and invalidate tree nodes */
1080 gtk_text_btree_get_iter_at_line(tree, &start, line, start_byte_offset);
1083 gtk_text_iter_next_char(iter); /* skip forward past the pixmap */
1085 gtk_text_btree_invalidate_region(tree, &start, iter);
1094 find_line_by_y(GtkTextBTree *tree, BTreeView *view,
1095 GtkTextBTreeNode *node, gint y, gint *line_top,
1096 GtkTextLine *last_line)
1100 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1101 gtk_text_btree_check(tree);
1103 if (node->level == 0)
1107 line = node->children.line;
1109 while (line != NULL && line != last_line)
1111 GtkTextLineData *ld;
1113 ld = gtk_text_line_get_data (line, view->view_id);
1117 if (y < (current_y + (ld ? ld->height : 0)))
1120 current_y += ld->height;
1121 *line_top += ld->height;
1130 GtkTextBTreeNode *child;
1132 child = node->children.node;
1134 while (child != NULL)
1139 gtk_text_btree_node_get_size(child, view->view_id,
1142 if (y < (current_y + height))
1143 return find_line_by_y(tree, view, child,
1144 y - current_y, line_top,
1147 current_y += height;
1148 *line_top += height;
1150 child = child->next;
1158 gtk_text_btree_find_line_by_y (GtkTextBTree *tree,
1165 GtkTextLine *last_line;
1168 view = gtk_text_btree_get_view (tree, view_id);
1169 g_return_val_if_fail (view != NULL, NULL);
1171 last_line = get_last_line (tree);
1173 line = find_line_by_y (tree, view, tree->root_node, ypixel, &line_top,
1177 *line_top_out = line_top;
1183 find_line_top_in_line_list(GtkTextBTree *tree,
1186 GtkTextLine *target_line,
1189 while (line != NULL)
1191 GtkTextLineData *ld;
1193 if (line == target_line)
1196 ld = gtk_text_line_get_data (line, view->view_id);
1203 g_assert_not_reached(); /* If we get here, our
1204 target line didn't exist
1205 under its parent node */
1210 gtk_text_btree_find_line_top (GtkTextBTree *tree,
1211 GtkTextLine *target_line,
1218 GtkTextBTreeNode *node;
1220 view = gtk_text_btree_get_view(tree, view_id);
1222 g_return_val_if_fail(view != NULL, 0);
1225 node = target_line->parent;
1226 while (node != NULL)
1228 nodes = g_slist_prepend(nodes, node);
1229 node = node->parent;
1233 while (iter != NULL)
1237 if (node->level == 0)
1239 g_slist_free(nodes);
1240 return find_line_top_in_line_list(tree, view,
1241 node->children.line,
1246 GtkTextBTreeNode *child;
1247 GtkTextBTreeNode *target_node;
1249 g_assert(iter->next != NULL); /* not at level 0 */
1250 target_node = iter->next->data;
1252 child = node->children.node;
1254 while (child != NULL)
1259 if (child == target_node)
1263 gtk_text_btree_node_get_size(child, view->view_id,
1267 child = child->next;
1269 g_assert(child != NULL); /* should have broken out before we
1273 iter = g_slist_next(iter);
1276 g_assert_not_reached(); /* we return when we find the target line */
1281 gtk_text_btree_add_view (GtkTextBTree *tree,
1282 GtkTextLayout *layout)
1285 GtkTextLine *last_line;
1286 GtkTextLineData *line_data;
1288 g_return_if_fail(tree != NULL);
1290 view = g_new(BTreeView, 1);
1292 view->view_id = layout;
1293 view->layout = layout;
1295 view->next = tree->views;
1300 /* The last line in the buffer has identity values for the per-view
1301 * data so that we can avoid special case checks for it in a large
1304 last_line = get_last_line (tree);
1306 line_data = g_new (GtkTextLineData, 1);
1307 line_data->view_id = layout;
1308 line_data->next = NULL;
1309 line_data->width = 0;
1310 line_data->height = 0;
1311 line_data->valid = TRUE;
1313 gtk_text_line_add_data (last_line, line_data);
1317 gtk_text_btree_remove_view (GtkTextBTree *tree,
1321 GtkTextLine *last_line;
1322 GtkTextLineData *line_data;
1324 g_return_if_fail(tree != NULL);
1328 while (view != NULL)
1330 if (view->view_id == view_id)
1336 g_return_if_fail(view != NULL);
1339 view->next->prev = view->prev;
1342 view->prev->next = view->next;
1344 if (view == tree->views)
1345 tree->views = view->next;
1347 /* Remove the line data for the last line which we added ourselves.
1348 * (Do this first, so that we don't try to call the view's line data destructor on it.)
1350 last_line = get_last_line (tree);
1351 line_data = gtk_text_line_remove_data (last_line, view_id);
1354 gtk_text_btree_node_remove_view(view, tree->root_node, view_id);
1360 gtk_text_btree_invalidate_region (GtkTextBTree *tree,
1361 const GtkTextIter *start,
1362 const GtkTextIter *end)
1368 while (view != NULL)
1370 gtk_text_layout_invalidate(view->layout, start, end);
1377 gtk_text_btree_get_view_size (GtkTextBTree *tree,
1382 g_return_if_fail(tree != NULL);
1383 g_return_if_fail(view_id != NULL);
1385 gtk_text_btree_node_get_size(tree->root_node, view_id,
1400 iter_stack_new(void)
1403 stack = g_new(IterStack, 1);
1404 stack->iters = NULL;
1411 iter_stack_push(IterStack *stack, const GtkTextIter *iter)
1414 if (stack->count > stack->alloced)
1416 stack->alloced = stack->count*2;
1417 stack->iters = g_realloc(stack->iters,
1418 stack->alloced*sizeof(GtkTextIter));
1420 stack->iters[stack->count-1] = *iter;
1424 iter_stack_pop(IterStack *stack, GtkTextIter *iter)
1426 if (stack->count == 0)
1431 *iter = stack->iters[stack->count];
1437 iter_stack_free(IterStack *stack)
1439 g_free(stack->iters);
1444 iter_stack_invert(IterStack *stack)
1446 if (stack->count > 0)
1449 guint j = stack->count - 1;
1454 tmp = stack->iters[i];
1455 stack->iters[i] = stack->iters[j];
1456 stack->iters[j] = tmp;
1465 gtk_text_btree_tag (const GtkTextIter *start_orig,
1466 const GtkTextIter *end_orig,
1470 GtkTextLineSegment *seg, *prev;
1471 GtkTextLine *cleanupline;
1472 gboolean toggled_on;
1473 GtkTextLine *start_line;
1474 GtkTextLine *end_line;
1476 GtkTextIter start, end;
1479 GtkTextTagInfo *info;
1481 g_return_if_fail(start_orig != NULL);
1482 g_return_if_fail(end_orig != NULL);
1483 g_return_if_fail(GTK_IS_TEXT_TAG(tag));
1484 g_return_if_fail(gtk_text_iter_get_btree(start_orig) ==
1485 gtk_text_iter_get_btree(end_orig));
1488 printf("%s tag %s from %d to %d\n",
1489 add ? "Adding" : "Removing",
1491 gtk_text_buffer_get_offset(start_orig),
1492 gtk_text_buffer_get_offset(end_orig));
1495 if (gtk_text_iter_equal(start_orig, end_orig))
1498 start = *start_orig;
1501 gtk_text_iter_reorder(&start, &end);
1503 tree = gtk_text_iter_get_btree(&start);
1505 info = gtk_text_btree_get_tag_info(tree, tag);
1507 start_line = gtk_text_iter_get_text_line(&start);
1508 end_line = gtk_text_iter_get_text_line(&end);
1510 /* Find all tag toggles in the region; we are going to delete them.
1511 We need to find them in advance, because
1512 forward_find_tag_toggle() won't work once we start playing around
1514 stack = iter_stack_new();
1516 /* We don't want to delete a toggle that's at the start iterator. */
1517 gtk_text_iter_next_char(&iter);
1518 while (gtk_text_iter_forward_to_tag_toggle(&iter, tag))
1520 if (gtk_text_iter_compare(&iter, &end) >= 0)
1523 iter_stack_push(stack, &iter);
1526 /* We need to traverse the toggles in order. */
1527 iter_stack_invert(stack);
1530 * See whether the tag is present at the start of the range. If
1531 * the state doesn't already match what we want then add a toggle
1535 toggled_on = gtk_text_iter_has_tag(&start, tag);
1536 if ( (add && !toggled_on) ||
1537 (!add && toggled_on) )
1539 /* This could create a second toggle at the start position;
1540 cleanup_line() will remove it if so. */
1541 seg = toggle_segment_new(info, add);
1543 prev = gtk_text_line_segment_split(&start);
1546 seg->next = start_line->segments;
1547 start_line->segments = seg;
1551 seg->next = prev->next;
1555 /* cleanup_line adds the new toggle to the node counts. */
1557 printf("added toggle at start\n");
1559 /* we should probably call segments_changed, but in theory
1560 any still-cached segments in the iters we are about to
1561 use are still valid, since they're in front
1567 * Scan the range of characters and delete any internal tag
1568 * transitions. Keep track of what the old state was at the end
1569 * of the range, and add a toggle there if it's needed.
1573 cleanupline = start_line;
1574 while (iter_stack_pop(stack, &iter))
1576 GtkTextLineSegment *indexable_seg;
1579 line = gtk_text_iter_get_text_line(&iter);
1580 seg = gtk_text_iter_get_any_segment(&iter);
1581 indexable_seg = gtk_text_iter_get_indexable_segment(&iter);
1583 g_assert(seg != NULL);
1584 g_assert(indexable_seg != NULL);
1585 g_assert(seg != indexable_seg);
1587 prev = line->segments;
1589 /* Find the segment that actually toggles this tag. */
1590 while (seg != indexable_seg)
1592 g_assert(seg != NULL);
1593 g_assert(indexable_seg != NULL);
1594 g_assert(seg != indexable_seg);
1596 if ( (seg->type == >k_text_toggle_on_type ||
1597 seg->type == >k_text_toggle_off_type) &&
1598 (seg->body.toggle.info == info) )
1604 g_assert(seg != NULL);
1605 g_assert(indexable_seg != NULL);
1607 g_assert(seg != indexable_seg); /* If this happens, then
1608 forward_to_tag_toggle was
1610 g_assert(seg->body.toggle.info->tag == tag);
1612 /* If this happens, when previously tagging we didn't merge
1613 overlapping tags. */
1614 g_assert( (toggled_on && seg->type == >k_text_toggle_off_type) ||
1615 (!toggled_on && seg->type == >k_text_toggle_on_type) );
1617 toggled_on = !toggled_on;
1620 printf("deleting %s toggle\n",
1621 seg->type == >k_text_toggle_on_type ? "on" : "off");
1623 /* Remove toggle segment from the list. */
1626 line->segments = seg->next;
1630 while (prev->next != seg)
1634 prev->next = seg->next;
1637 /* Inform iterators we've hosed them. This actually reflects a
1638 bit of inefficiency; if you have the same tag toggled on and
1639 off a lot in a single line, we keep having the rescan from
1640 the front of the line. Of course we have to do that to get
1641 "prev" anyway, but here we are doing it an additional
1643 segments_changed(tree);
1645 /* Update node counts */
1646 if (seg->body.toggle.inNodeCounts)
1648 change_node_toggle_count(line->parent,
1650 seg->body.toggle.inNodeCounts = FALSE;
1655 /* We only clean up lines when we're done with them, saves some
1656 gratuitous line-segment-traversals */
1658 if (cleanupline != line)
1660 cleanup_line(cleanupline);
1665 iter_stack_free(stack);
1667 /* toggled_on now reflects the toggle state _just before_ the
1668 end iterator. The end iterator could already have a toggle
1669 on or a toggle off. */
1670 if ( (add && !toggled_on) ||
1671 (!add && toggled_on) )
1673 /* This could create a second toggle at the start position;
1674 cleanup_line() will remove it if so. */
1676 seg = toggle_segment_new(info, !add);
1678 prev = gtk_text_line_segment_split(&end);
1681 seg->next = end_line->segments;
1682 end_line->segments = seg;
1686 seg->next = prev->next;
1689 /* cleanup_line adds the new toggle to the node counts. */
1690 g_assert(seg->body.toggle.inNodeCounts == FALSE);
1692 printf("added toggle at end\n");
1697 * Cleanup cleanupline and the last line of the range, if
1698 * these are different.
1701 cleanup_line(cleanupline);
1702 if (cleanupline != end_line)
1704 cleanup_line(end_line);
1707 segments_changed(tree);
1709 if (gtk_debug_flags & GTK_DEBUG_TEXT)
1710 gtk_text_btree_check(tree);
1719 gtk_text_btree_get_line (GtkTextBTree *tree,
1721 gint *real_line_number)
1723 GtkTextBTreeNode *node;
1728 line_count = gtk_text_btree_line_count(tree);
1730 if (line_number < 0)
1732 line_number = line_count;
1734 else if (line_number > line_count)
1736 line_number = line_count;
1739 if (real_line_number)
1740 *real_line_number = line_number;
1742 node = tree->root_node;
1743 lines_left = line_number;
1746 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1750 while (node->level != 0)
1752 for (node = node->children.node;
1753 node->num_lines <= lines_left;
1759 g_error("gtk_text_btree_find_line ran out of GtkTextBTreeNodes");
1762 lines_left -= node->num_lines;
1767 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1770 for (line = node->children.line; lines_left > 0;
1776 g_error("gtk_text_btree_find_line ran out of lines");
1785 gtk_text_btree_get_line_at_char(GtkTextBTree *tree,
1787 gint *line_start_index,
1788 gint *real_char_index)
1790 GtkTextBTreeNode *node;
1792 GtkTextLineSegment *seg;
1797 node = tree->root_node;
1799 /* Clamp to valid indexes (-1 is magic for "highest index") */
1800 if (char_index < 0 || char_index >= node->num_chars)
1802 char_index = node->num_chars - 1;
1805 *real_char_index = char_index;
1808 * Work down through levels of the tree until a GtkTextBTreeNode is found at
1812 chars_left = char_index;
1813 while (node->level != 0)
1815 for (node = node->children.node;
1816 chars_left >= node->num_chars;
1819 chars_left -= node->num_chars;
1821 g_assert(chars_left >= 0);
1825 if (chars_left == 0)
1827 /* Start of a line */
1829 *line_start_index = char_index;
1830 return node->children.line;
1834 * Work through the lines attached to the level-0 GtkTextBTreeNode.
1840 for (line = node->children.line; line != NULL; line = line->next)
1842 seg = line->segments;
1845 if (chars_in_line + seg->char_count > chars_left)
1846 goto found; /* found our line/segment */
1848 chars_in_line += seg->char_count;
1853 chars_left -= chars_in_line;
1861 g_assert(line != NULL); /* hosage, ran out of lines */
1862 g_assert(seg != NULL);
1864 *line_start_index = char_index - chars_left;
1869 gtk_text_btree_get_tags (const GtkTextIter *iter,
1872 GtkTextBTreeNode *node;
1873 GtkTextLine *siblingline;
1874 GtkTextLineSegment *seg;
1875 int src, dst, index;
1881 #define NUM_TAG_INFOS 10
1883 line = gtk_text_iter_get_text_line(iter);
1884 tree = gtk_text_iter_get_btree(iter);
1885 byte_index = gtk_text_iter_get_line_index(iter);
1887 tagInfo.numTags = 0;
1888 tagInfo.arraySize = NUM_TAG_INFOS;
1889 tagInfo.tags = g_new(GtkTextTag*, NUM_TAG_INFOS);
1890 tagInfo.counts = g_new(int, NUM_TAG_INFOS);
1893 * Record tag toggles within the line of indexPtr but preceding
1894 * indexPtr. Note that if this loop segfaults, your
1895 * byte_index probably points past the sum of all
1896 * seg->byte_count */
1898 for (index = 0, seg = line->segments;
1899 (index + seg->byte_count) <= byte_index;
1900 index += seg->byte_count, seg = seg->next)
1902 if ((seg->type == >k_text_toggle_on_type)
1903 || (seg->type == >k_text_toggle_off_type))
1905 inc_count(seg->body.toggle.info->tag, 1, &tagInfo);
1910 * Record toggles for tags in lines that are predecessors of
1911 * line but under the same level-0 GtkTextBTreeNode.
1914 for (siblingline = line->parent->children.line;
1915 siblingline != line;
1916 siblingline = siblingline->next)
1918 for (seg = siblingline->segments; seg != NULL;
1921 if ((seg->type == >k_text_toggle_on_type)
1922 || (seg->type == >k_text_toggle_off_type))
1924 inc_count(seg->body.toggle.info->tag, 1, &tagInfo);
1930 * For each GtkTextBTreeNode in the ancestry of this line, record tag
1931 * toggles for all siblings that precede that GtkTextBTreeNode.
1934 for (node = line->parent; node->parent != NULL;
1935 node = node->parent)
1937 GtkTextBTreeNode *siblingPtr;
1940 for (siblingPtr = node->parent->children.node;
1941 siblingPtr != node; siblingPtr = siblingPtr->next)
1943 for (summary = siblingPtr->summary; summary != NULL;
1944 summary = summary->next)
1946 if (summary->toggle_count & 1)
1948 inc_count(summary->info->tag, summary->toggle_count,
1956 * Go through the tag information and squash out all of the tags
1957 * that have even toggle counts (these tags exist before the point
1958 * of interest, but not at the desired character itself).
1961 for (src = 0, dst = 0; src < tagInfo.numTags; src++)
1963 if (tagInfo.counts[src] & 1)
1965 g_assert(GTK_IS_TEXT_TAG(tagInfo.tags[src]));
1966 tagInfo.tags[dst] = tagInfo.tags[src];
1972 g_free(tagInfo.counts);
1975 g_free(tagInfo.tags);
1978 return tagInfo.tags;
1982 copy_segment(GString *string,
1983 gboolean include_hidden,
1984 gboolean include_nonchars,
1985 const GtkTextIter *start,
1986 const GtkTextIter *end)
1988 GtkTextLineSegment *end_seg;
1989 GtkTextLineSegment *seg;
1991 if (gtk_text_iter_equal(start, end))
1994 seg = gtk_text_iter_get_indexable_segment(start);
1995 end_seg = gtk_text_iter_get_indexable_segment(end);
1997 if (seg->type == >k_text_char_type)
1999 gboolean copy = TRUE;
2000 gint copy_bytes = 0;
2001 gint copy_start = 0;
2003 /* Don't copy if we're invisible; segments are invisible/not
2004 as a whole, no need to check each char */
2005 if (!include_hidden &&
2006 gtk_text_btree_char_is_invisible(start))
2009 /* printf(" <invisible>\n"); */
2012 copy_start = gtk_text_iter_get_segment_byte(start);
2016 /* End is in the same segment; need to copy fewer bytes. */
2017 gint end_byte = gtk_text_iter_get_segment_byte(end);
2019 copy_bytes = end_byte - copy_start;
2022 copy_bytes = seg->byte_count - copy_start;
2024 g_assert(copy_bytes != 0); /* Due to iter equality check at
2025 front of this function. */
2029 g_assert((copy_start + copy_bytes) <= seg->byte_count);
2031 g_string_append_len(string,
2032 seg->body.chars + copy_start,
2036 /* printf(" :%s\n", string->str); */
2038 else if (seg->type == >k_text_pixbuf_type)
2040 gboolean copy = TRUE;
2042 if (!include_nonchars)
2046 else if (!include_hidden &&
2047 gtk_text_btree_char_is_invisible(start))
2054 g_string_append_len(string,
2055 gtk_text_unknown_char_utf8,
2063 gtk_text_btree_get_text (const GtkTextIter *start_orig,
2064 const GtkTextIter *end_orig,
2065 gboolean include_hidden,
2066 gboolean include_nonchars)
2068 GtkTextLineSegment *seg;
2069 GtkTextLineSegment *end_seg;
2077 g_return_val_if_fail(start_orig != NULL, NULL);
2078 g_return_val_if_fail(end_orig != NULL, NULL);
2079 g_return_val_if_fail(gtk_text_iter_get_btree(start_orig) ==
2080 gtk_text_iter_get_btree(end_orig), NULL);
2082 start = *start_orig;
2085 gtk_text_iter_reorder(&start, &end);
2087 retval = g_string_new("");
2089 tree = gtk_text_iter_get_btree(&start);
2091 end_seg = gtk_text_iter_get_indexable_segment(&end);
2093 seg = gtk_text_iter_get_indexable_segment(&iter);
2094 while (seg != end_seg)
2096 copy_segment(retval, include_hidden, include_nonchars,
2099 gtk_text_iter_forward_indexable_segment(&iter);
2101 seg = gtk_text_iter_get_indexable_segment(&iter);
2104 copy_segment(retval, include_hidden, include_nonchars, &iter, &end);
2107 g_string_free(retval, FALSE);
2112 gtk_text_btree_line_count (GtkTextBTree *tree)
2114 /* Subtract bogus line at the end; we return a count
2116 return tree->root_node->num_lines - 1;
2120 gtk_text_btree_char_count (GtkTextBTree *tree)
2122 /* Exclude newline in bogus last line */
2123 return tree->root_node->num_chars - 1;
2126 #define LOTSA_TAGS 1000
2128 gtk_text_btree_char_is_invisible (const GtkTextIter *iter)
2130 gboolean invisible = FALSE; /* if nobody says otherwise, it's visible */
2132 int deftagCnts[LOTSA_TAGS];
2133 int *tagCnts = deftagCnts;
2134 GtkTextTag *deftags[LOTSA_TAGS];
2135 GtkTextTag **tags = deftags;
2137 GtkTextBTreeNode *node;
2138 GtkTextLine *siblingline;
2139 GtkTextLineSegment *seg;
2146 line = gtk_text_iter_get_text_line(iter);
2147 tree = gtk_text_iter_get_btree(iter);
2148 byte_index = gtk_text_iter_get_line_index(iter);
2150 numTags = gtk_text_tag_table_size(tree->table);
2152 /* almost always avoid malloc, so stay out of system calls */
2153 if (LOTSA_TAGS < numTags)
2155 tagCnts = g_new(int, numTags);
2156 tags = g_new(GtkTextTag*, numTags);
2159 for (i=0; i<numTags; i++)
2165 * Record tag toggles within the line of indexPtr but preceding
2169 for (index = 0, seg = line->segments;
2170 (index + seg->byte_count) <= byte_index; /* segfault here means invalid index */
2171 index += seg->byte_count, seg = seg->next)
2173 if ((seg->type == >k_text_toggle_on_type)
2174 || (seg->type == >k_text_toggle_off_type))
2176 tag = seg->body.toggle.info->tag;
2177 if (tag->invisible_set && tag->values->invisible)
2179 tags[tag->priority] = tag;
2180 tagCnts[tag->priority]++;
2186 * Record toggles for tags in lines that are predecessors of
2187 * line but under the same level-0 GtkTextBTreeNode.
2190 for (siblingline = line->parent->children.line;
2191 siblingline != line;
2192 siblingline = siblingline->next)
2194 for (seg = siblingline->segments; seg != NULL;
2197 if ((seg->type == >k_text_toggle_on_type)
2198 || (seg->type == >k_text_toggle_off_type))
2200 tag = seg->body.toggle.info->tag;
2201 if (tag->invisible_set && tag->values->invisible)
2203 tags[tag->priority] = tag;
2204 tagCnts[tag->priority]++;
2211 * For each GtkTextBTreeNode in the ancestry of this line, record tag toggles
2212 * for all siblings that precede that GtkTextBTreeNode.
2215 for (node = line->parent; node->parent != NULL;
2216 node = node->parent)
2218 GtkTextBTreeNode *siblingPtr;
2221 for (siblingPtr = node->parent->children.node;
2222 siblingPtr != node; siblingPtr = siblingPtr->next)
2224 for (summary = siblingPtr->summary; summary != NULL;
2225 summary = summary->next)
2227 if (summary->toggle_count & 1)
2229 tag = summary->info->tag;
2230 if (tag->invisible_set && tag->values->invisible)
2232 tags[tag->priority] = tag;
2233 tagCnts[tag->priority] += summary->toggle_count;
2241 * Now traverse from highest priority to lowest,
2242 * take invisible value from first odd count (= on)
2245 for (i = numTags-1; i >=0; i--)
2249 /* FIXME not sure this should be if 0 */
2251 #ifndef ALWAYS_SHOW_SELECTION
2252 /* who would make the selection invisible? */
2253 if ((tag == tkxt->seltag)
2254 && !(tkxt->flags & GOT_FOCUS))
2260 invisible = tags[i]->values->invisible;
2265 if (LOTSA_TAGS < numTags)
2280 redisplay_region (GtkTextBTree *tree,
2281 const GtkTextIter *start,
2282 const GtkTextIter *end)
2285 GtkTextLine *start_line, *end_line;
2287 if (gtk_text_iter_compare (start, end) > 0)
2289 const GtkTextIter *tmp = start;
2294 start_line = gtk_text_iter_get_text_line (start);
2295 end_line = gtk_text_iter_get_text_line (end);
2298 while (view != NULL)
2300 gint start_y, end_y;
2301 GtkTextLineData *ld;
2303 start_y = gtk_text_btree_find_line_top (tree, start_line, view->view_id);
2305 if (end_line == start_line)
2308 end_y = gtk_text_btree_find_line_top (tree, end_line, view->view_id);
2310 ld = gtk_text_line_get_data (end_line, view->view_id);
2312 end_y += ld->height;
2314 gtk_text_layout_changed (view->layout, start_y, end_y - start_y, end_y - start_y);
2321 redisplay_mark(GtkTextLineSegment *mark)
2326 gtk_text_btree_get_iter_at_mark(mark->body.mark.tree,
2328 (GtkTextMark*)mark);
2331 gtk_text_iter_next_char(&end);
2333 gtk_text_btree_invalidate_region(mark->body.mark.tree,
2338 redisplay_mark_if_visible(GtkTextLineSegment *mark)
2340 if (!mark->body.mark.visible)
2343 redisplay_mark(mark);
2347 ensure_not_off_end(GtkTextBTree *tree,
2348 GtkTextLineSegment *mark,
2351 if (gtk_text_iter_get_line(iter) ==
2352 gtk_text_btree_line_count(tree))
2353 gtk_text_iter_prev_char(iter);
2356 static GtkTextLineSegment*
2357 real_set_mark(GtkTextBTree *tree,
2358 GtkTextMark *existing_mark,
2360 gboolean left_gravity,
2361 const GtkTextIter *where,
2362 gboolean should_exist,
2363 gboolean redraw_selections)
2365 GtkTextLineSegment *mark;
2368 g_return_val_if_fail(tree != NULL, NULL);
2369 g_return_val_if_fail(where != NULL, NULL);
2370 g_return_val_if_fail(gtk_text_iter_get_btree(where) == tree, NULL);
2373 mark = (GtkTextLineSegment*) existing_mark;
2374 else if (name != NULL)
2375 mark = g_hash_table_lookup(tree->mark_table,
2380 if (should_exist && mark == NULL)
2382 g_warning("No mark `%s' exists!", name);
2386 /* OK if !should_exist and it does already exist, in that case
2393 if (redraw_selections &&
2394 (mark == tree->insert_mark ||
2395 mark == tree->selection_bound_mark))
2397 GtkTextIter old_pos;
2399 gtk_text_btree_get_iter_at_mark (tree, &old_pos, (GtkTextMark*)mark);
2400 redisplay_region (tree, &old_pos, where);
2404 * don't let visible marks be after the final newline of the
2408 if (mark->body.mark.visible)
2410 ensure_not_off_end(tree, mark, &iter);
2413 /* Redraw the mark's old location. */
2414 redisplay_mark_if_visible(mark);
2416 /* Unlink mark from its current location.
2417 This could hose our iterator... */
2418 gtk_text_btree_unlink_segment(tree, mark,
2419 mark->body.mark.line);
2420 mark->body.mark.line = gtk_text_iter_get_text_line(&iter);
2421 g_assert(mark->body.mark.line == gtk_text_iter_get_text_line(&iter));
2423 segments_changed(tree); /* make sure the iterator recomputes its
2428 mark = _mark_segment_new (tree,
2432 mark->body.mark.line = gtk_text_iter_get_text_line(&iter);
2434 if (mark->body.mark.name)
2435 g_hash_table_insert(tree->mark_table,
2436 mark->body.mark.name,
2440 /* Link mark into new location */
2441 gtk_text_btree_link_segment(mark, &iter);
2443 /* Invalidate some iterators. */
2444 segments_changed(tree);
2447 * update the screen at the mark's new location.
2450 redisplay_mark_if_visible(mark);
2457 gtk_text_btree_set_mark (GtkTextBTree *tree,
2458 GtkTextMark *existing_mark,
2460 gboolean left_gravity,
2461 const GtkTextIter *iter,
2462 gboolean should_exist)
2464 return (GtkTextMark*)real_set_mark(tree, existing_mark,
2465 name, left_gravity, iter, should_exist,
2470 gtk_text_btree_get_selection_bounds (GtkTextBTree *tree,
2474 GtkTextIter tmp_start, tmp_end;
2476 gtk_text_btree_get_iter_at_mark (tree, &tmp_start,
2477 (GtkTextMark*)tree->insert_mark);
2478 gtk_text_btree_get_iter_at_mark (tree, &tmp_end,
2479 (GtkTextMark*)tree->selection_bound_mark);
2481 if (gtk_text_iter_equal(&tmp_start, &tmp_end))
2493 gtk_text_iter_reorder(&tmp_start, &tmp_end);
2506 gtk_text_btree_place_cursor(GtkTextBTree *tree,
2507 const GtkTextIter *iter)
2509 GtkTextIter start, end;
2511 if (gtk_text_btree_get_selection_bounds (tree, &start, &end))
2512 redisplay_region(tree, &start, &end);
2514 /* Move insert AND selection_bound before we redisplay */
2515 real_set_mark(tree, (GtkTextMark*) tree->insert_mark,
2516 "insert", FALSE, iter, TRUE, FALSE);
2517 real_set_mark(tree, (GtkTextMark*) tree->selection_bound_mark,
2518 "selection_bound", FALSE, iter, TRUE, FALSE);
2522 gtk_text_btree_remove_mark_by_name (GtkTextBTree *tree,
2527 g_return_if_fail(tree != NULL);
2528 g_return_if_fail(name != NULL);
2530 mark = g_hash_table_lookup(tree->mark_table,
2533 gtk_text_btree_remove_mark(tree, mark);
2537 gtk_text_btree_remove_mark (GtkTextBTree *tree,
2540 GtkTextLineSegment *segment = (GtkTextLineSegment*) mark;
2542 g_return_if_fail (segment != NULL);
2543 g_return_if_fail (tree != NULL);
2545 if (segment->body.mark.not_deleteable)
2547 g_warning("Can't delete special mark `%s'", segment->body.mark.name);
2551 /* This calls cleanup_line and segments_changed */
2552 gtk_text_btree_unlink_segment (tree, segment, segment->body.mark.line);
2554 if (segment->body.mark.name)
2555 g_hash_table_remove (tree->mark_table, segment->body.mark.name);
2557 _mark_segment_unref (segment);
2559 segment->body.mark.tree = NULL;
2560 segment->body.mark.line = NULL;
2564 gtk_text_btree_mark_is_insert (GtkTextBTree *tree,
2565 GtkTextMark *segment)
2567 return segment == (GtkTextMark*) tree->insert_mark;
2571 gtk_text_btree_mark_is_selection_bound (GtkTextBTree *tree,
2572 GtkTextMark *segment)
2574 return segment == (GtkTextMark*) tree->selection_bound_mark;
2578 gtk_text_btree_get_mark_by_name (GtkTextBTree *tree,
2581 g_return_val_if_fail(tree != NULL, NULL);
2582 g_return_val_if_fail(name != NULL, NULL);
2584 return g_hash_table_lookup(tree->mark_table, name);
2588 gtk_text_mark_set_visible (GtkTextMark *mark,
2591 GtkTextLineSegment *seg;
2593 g_return_if_fail(mark != NULL);
2595 seg = (GtkTextLineSegment*)mark;
2597 if (seg->body.mark.visible == setting)
2601 seg->body.mark.visible = setting;
2603 redisplay_mark (seg);
2608 gtk_text_btree_first_could_contain_tag (GtkTextBTree *tree,
2611 GtkTextBTreeNode *node;
2612 GtkTextTagInfo *info;
2614 g_return_val_if_fail(tree != NULL, NULL);
2618 info = gtk_text_btree_get_existing_tag_info(tree, tag);
2623 if (info->tag_root == NULL)
2626 node = info->tag_root;
2628 /* We know the tag root has instances of the given
2631 continue_outer_loop:
2632 g_assert(node != NULL);
2633 while (node->level > 0)
2635 g_assert(node != NULL); /* Failure probably means bad tag summaries. */
2636 node = node->children.node;
2637 while (node != NULL)
2639 if (gtk_text_btree_node_has_tag(node, tag))
2640 goto continue_outer_loop;
2644 g_assert(node != NULL);
2647 g_assert(node != NULL); /* The tag summaries said some node had
2650 g_assert(node->level == 0);
2652 return node->children.line;
2656 /* Looking for any tag at all (tag == NULL).
2657 Unfortunately this can't be done in a simple and efficient way
2658 right now; so I'm just going to return the
2659 first line in the btree. FIXME */
2660 return gtk_text_btree_get_line (tree, 0, NULL);
2665 gtk_text_btree_last_could_contain_tag (GtkTextBTree *tree,
2668 GtkTextBTreeNode *node;
2669 GtkTextBTreeNode *last_node;
2671 GtkTextTagInfo *info;
2673 g_return_val_if_fail(tree != NULL, NULL);
2677 info = gtk_text_btree_get_existing_tag_info(tree, tag);
2679 if (info->tag_root == NULL)
2682 node = info->tag_root;
2683 /* We know the tag root has instances of the given
2686 while (node->level > 0)
2688 g_assert(node != NULL); /* Failure probably means bad tag summaries. */
2690 node = node->children.node;
2691 while (node != NULL)
2693 if (gtk_text_btree_node_has_tag(node, tag))
2701 g_assert(node != NULL); /* The tag summaries said some node had
2704 g_assert(node->level == 0);
2706 /* Find the last line in this node */
2707 line = node->children.line;
2708 while (line->next != NULL)
2715 /* This search can't be done efficiently at the moment,
2716 at least not without complexity.
2717 So, we just return the last line.
2719 return gtk_text_btree_get_line (tree, -1, NULL);
2729 gtk_text_line_get_number (GtkTextLine *line)
2732 GtkTextBTreeNode *node, *parent, *node2;
2736 * First count how many lines precede this one in its level-0
2740 node = line->parent;
2742 for (line2 = node->children.line; line2 != line;
2743 line2 = line2->next)
2747 g_error("gtk_text_btree_line_number couldn't find line");
2753 * Now work up through the levels of the tree one at a time,
2754 * counting how many lines are in GtkTextBTreeNodes preceding the current
2758 for (parent = node->parent ; parent != NULL;
2759 node = parent, parent = parent->parent)
2761 for (node2 = parent->children.node; node2 != node;
2762 node2 = node2->next)
2766 g_error("gtk_text_btree_line_number couldn't find GtkTextBTreeNode");
2768 index += node2->num_lines;
2774 static GtkTextLineSegment*
2775 find_toggle_segment_before_char(GtkTextLine *line,
2779 GtkTextLineSegment *seg;
2780 GtkTextLineSegment *toggle_seg;
2785 seg = line->segments;
2786 while ( (index + seg->char_count) <= char_in_line )
2788 if (((seg->type == >k_text_toggle_on_type)
2789 || (seg->type == >k_text_toggle_off_type))
2790 && (seg->body.toggle.info->tag == tag))
2793 index += seg->char_count;
2800 static GtkTextLineSegment*
2801 find_toggle_segment_before_byte(GtkTextLine *line,
2805 GtkTextLineSegment *seg;
2806 GtkTextLineSegment *toggle_seg;
2811 seg = line->segments;
2812 while ( (index + seg->byte_count) <= byte_in_line )
2814 if (((seg->type == >k_text_toggle_on_type)
2815 || (seg->type == >k_text_toggle_off_type))
2816 && (seg->body.toggle.info->tag == tag))
2819 index += seg->byte_count;
2827 find_toggle_outside_current_line(GtkTextLine *line,
2831 GtkTextBTreeNode *node;
2832 GtkTextLine *sibling_line;
2833 GtkTextLineSegment *seg;
2834 GtkTextLineSegment *toggle_seg;
2836 GtkTextTagInfo *info = NULL;
2839 * No toggle in this line. Look for toggles for the tag in lines
2840 * that are predecessors of line but under the same
2841 * level-0 GtkTextBTreeNode.
2844 sibling_line = line->parent->children.line;
2845 while (sibling_line != line)
2847 seg = sibling_line->segments;
2850 if (((seg->type == >k_text_toggle_on_type)
2851 || (seg->type == >k_text_toggle_off_type))
2852 && (seg->body.toggle.info->tag == tag))
2858 sibling_line = sibling_line->next;
2861 if (toggle_seg != NULL)
2862 return (toggle_seg->type == >k_text_toggle_on_type);
2865 * No toggle in this GtkTextBTreeNode. Scan upwards through the ancestors of
2866 * this GtkTextBTreeNode, counting the number of toggles of the given tag in
2867 * siblings that precede that GtkTextBTreeNode.
2870 info = gtk_text_btree_get_existing_tag_info(tree, tag);
2876 node = line->parent;
2877 while (node->parent != NULL)
2879 GtkTextBTreeNode *sibling_node;
2881 sibling_node = node->parent->children.node;
2882 while (sibling_node != node)
2886 summary = sibling_node->summary;
2887 while (summary != NULL)
2889 if (summary->info == info)
2890 toggles += summary->toggle_count;
2892 summary = summary->next;
2895 sibling_node = sibling_node->next;
2898 if (node == info->tag_root)
2901 node = node->parent;
2905 * An odd number of toggles means that the tag is present at the
2909 return (toggles & 1) != 0;
2912 /* FIXME this function is far too slow, for no good reason. */
2914 gtk_text_line_char_has_tag (GtkTextLine *line,
2919 GtkTextLineSegment *toggle_seg;
2921 g_return_val_if_fail(line != NULL, FALSE);
2924 * Check for toggles for the tag in the line but before
2925 * the char. If there is one, its type indicates whether or
2926 * not the character is tagged.
2929 toggle_seg = find_toggle_segment_before_char(line, char_in_line, tag);
2931 if (toggle_seg != NULL)
2932 return (toggle_seg->type == >k_text_toggle_on_type);
2934 return find_toggle_outside_current_line(line, tree, tag);
2938 gtk_text_line_byte_has_tag (GtkTextLine *line,
2943 GtkTextLineSegment *toggle_seg;
2945 g_return_val_if_fail(line != NULL, FALSE);
2948 * Check for toggles for the tag in the line but before
2949 * the char. If there is one, its type indicates whether or
2950 * not the character is tagged.
2953 toggle_seg = find_toggle_segment_before_byte(line, byte_in_line, tag);
2955 if (toggle_seg != NULL)
2956 return (toggle_seg->type == >k_text_toggle_on_type);
2958 return find_toggle_outside_current_line(line, tree, tag);
2962 gtk_text_line_is_last (GtkTextLine *line,
2965 return line == get_last_line (tree);
2969 gtk_text_line_next (GtkTextLine *line)
2971 GtkTextBTreeNode *node;
2973 if (line->next != NULL)
2978 * This was the last line associated with the particular parent
2979 * GtkTextBTreeNode. Search up the tree for the next GtkTextBTreeNode,
2980 * then search down from that GtkTextBTreeNode to find the first
2984 node = line->parent;
2985 while (node != NULL && node->next == NULL)
2986 node = node->parent;
2992 while (node->level > 0)
2994 node = node->children.node;
2997 g_assert(node->children.line != line);
2999 return node->children.line;
3004 gtk_text_line_previous (GtkTextLine *line)
3006 GtkTextBTreeNode *node;
3007 GtkTextBTreeNode *node2;
3011 * Find the line under this GtkTextBTreeNode just before the starting line.
3013 prev = line->parent->children.line; /* First line at leaf */
3014 while (prev != line)
3016 if (prev->next == line)
3022 g_error("gtk_text_btree_previous_line ran out of lines");
3026 * This was the first line associated with the particular parent
3027 * GtkTextBTreeNode. Search up the tree for the previous GtkTextBTreeNode,
3028 * then search down from that GtkTextBTreeNode to find its last line.
3030 for (node = line->parent; ; node = node->parent)
3032 if (node == NULL || node->parent == NULL)
3034 else if (node != node->parent->children.node)
3038 for (node2 = node->parent->children.node; ;
3039 node2 = node2->children.node)
3041 while (node2->next != node)
3042 node2 = node2->next;
3044 if (node2->level == 0)
3050 for (prev = node2->children.line ; ; prev = prev->next)
3052 if (prev->next == NULL)
3056 g_assert_not_reached ();
3061 gtk_text_line_add_data (GtkTextLine *line,
3062 GtkTextLineData *data)
3064 g_return_if_fail(line != NULL);
3065 g_return_if_fail(data != NULL);
3066 g_return_if_fail(data->view_id != NULL);
3070 data->next = line->views;
3080 gtk_text_line_remove_data (GtkTextLine *line,
3083 GtkTextLineData *prev;
3084 GtkTextLineData *iter;
3086 g_return_val_if_fail(line != NULL, NULL);
3087 g_return_val_if_fail(view_id != NULL, NULL);
3091 while (iter != NULL)
3093 if (iter->view_id == view_id)
3102 prev->next = iter->next;
3104 line->views = iter->next;
3113 gtk_text_line_get_data (GtkTextLine *line,
3116 GtkTextLineData *iter;
3118 g_return_val_if_fail(line != NULL, NULL);
3119 g_return_val_if_fail(view_id != NULL, NULL);
3122 while (iter != NULL)
3124 if (iter->view_id == view_id)
3133 gtk_text_line_invalidate_wrap (GtkTextLine *line,
3134 GtkTextLineData *ld)
3136 /* For now this is totally unoptimized. FIXME?
3138 We could probably optimize the case where the width removed
3139 is less than the max width for the parent node,
3140 and the case where the height is unchanged when we re-wrap.
3143 g_return_if_fail(ld != NULL);
3146 gtk_text_btree_node_invalidate_upward(line->parent, ld->view_id);
3150 gtk_text_line_char_count (GtkTextLine *line)
3152 GtkTextLineSegment *seg;
3156 seg = line->segments;
3159 size += seg->char_count;
3166 gtk_text_line_byte_count (GtkTextLine *line)
3168 GtkTextLineSegment *seg;
3172 seg = line->segments;
3175 size += seg->byte_count;
3183 gtk_text_line_char_index (GtkTextLine *target_line)
3185 GSList *node_stack = NULL;
3186 GtkTextBTreeNode *iter;
3190 /* Push all our parent nodes onto a stack */
3191 iter = target_line->parent;
3193 g_assert(iter != NULL);
3195 while (iter != NULL)
3197 node_stack = g_slist_prepend(node_stack, iter);
3199 iter = iter->parent;
3202 /* Check that we have the root node on top of the stack. */
3203 g_assert(node_stack != NULL &&
3204 node_stack->data != NULL &&
3205 ((GtkTextBTreeNode*)node_stack->data)->parent == NULL);
3207 /* Add up chars in all nodes before the nodes in our stack.
3211 iter = node_stack->data;
3212 while (iter != NULL)
3214 GtkTextBTreeNode *child_iter;
3215 GtkTextBTreeNode *next_node;
3217 next_node = node_stack->next ?
3218 node_stack->next->data : NULL;
3219 node_stack = g_slist_remove(node_stack, node_stack->data);
3221 if (iter->level == 0)
3223 /* stack should be empty when we're on the last node */
3224 g_assert(node_stack == NULL);
3225 break; /* Our children are now lines */
3228 g_assert(next_node != NULL);
3229 g_assert(iter != NULL);
3230 g_assert(next_node->parent == iter);
3232 /* Add up chars before us in the tree */
3233 child_iter = iter->children.node;
3234 while (child_iter != next_node)
3236 g_assert(child_iter != NULL);
3238 num_chars += child_iter->num_chars;
3240 child_iter = child_iter->next;
3246 g_assert(iter != NULL);
3247 g_assert(iter == target_line->parent);
3249 /* Since we don't store char counts in lines, only in segments, we
3250 have to iterate over the lines adding up segment char counts
3251 until we find our line. */
3252 line = iter->children.line;
3253 while (line != target_line)
3255 g_assert(line != NULL);
3257 num_chars += gtk_text_line_char_count(line);
3262 g_assert(line == target_line);
3268 gtk_text_line_byte_to_segment (GtkTextLine *line,
3272 GtkTextLineSegment *seg;
3275 g_return_val_if_fail(line != NULL, NULL);
3277 offset = byte_offset;
3278 seg = line->segments;
3280 while (offset >= seg->byte_count)
3282 g_assert(seg != NULL); /* means an invalid byte index */
3283 offset -= seg->byte_count;
3288 *seg_offset = offset;
3294 gtk_text_line_char_to_segment (GtkTextLine *line,
3298 GtkTextLineSegment *seg;
3301 g_return_val_if_fail(line != NULL, NULL);
3303 offset = char_offset;
3304 seg = line->segments;
3306 while (offset >= seg->char_count)
3308 g_assert(seg != NULL); /* means an invalid char index */
3309 offset -= seg->char_count;
3314 *seg_offset = offset;
3320 gtk_text_line_byte_to_any_segment (GtkTextLine *line,
3324 GtkTextLineSegment *seg;
3327 g_return_val_if_fail(line != NULL, NULL);
3329 offset = byte_offset;
3330 seg = line->segments;
3332 while (offset > 0 && offset >= seg->byte_count)
3334 g_assert(seg != NULL); /* means an invalid byte index */
3335 offset -= seg->byte_count;
3340 *seg_offset = offset;
3346 gtk_text_line_char_to_any_segment (GtkTextLine *line,
3350 GtkTextLineSegment *seg;
3353 g_return_val_if_fail(line != NULL, NULL);
3355 offset = char_offset;
3356 seg = line->segments;
3358 while (offset > 0 && offset >= seg->char_count)
3360 g_assert(seg != NULL); /* means an invalid byte index */
3361 offset -= seg->char_count;
3366 *seg_offset = offset;
3372 gtk_text_line_byte_to_char (GtkTextLine *line,
3376 GtkTextLineSegment *seg;
3378 g_return_val_if_fail(line != NULL, 0);
3379 g_return_val_if_fail(byte_offset >= 0, 0);
3382 seg = line->segments;
3383 while (byte_offset >= seg->byte_count) /* while (we need to go farther than
3384 the next segment) */
3386 g_assert(seg != NULL); /* our byte_index was bogus if this happens */
3388 byte_offset -= seg->byte_count;
3389 char_offset += seg->char_count;
3394 g_assert(seg != NULL);
3396 /* Now byte_offset is the offset into the current segment,
3397 and char_offset is the start of the current segment.
3398 Optimize the case where no chars use > 1 byte */
3399 if (seg->byte_count == seg->char_count)
3400 return char_offset + byte_offset;
3403 if (seg->type == >k_text_char_type)
3404 return char_offset + g_utf8_strlen (seg->body.chars, byte_offset);
3407 g_assert(seg->char_count == 1);
3408 g_assert(byte_offset == 0);
3416 gtk_text_line_char_to_byte (GtkTextLine *line,
3419 g_warning("FIXME not implemented");
3424 /* FIXME sync with char_locate (or figure out a clean
3425 way to merge the two functions) */
3427 gtk_text_line_byte_locate (GtkTextLine *line,
3429 GtkTextLineSegment **segment,
3430 GtkTextLineSegment **any_segment,
3431 gint *seg_byte_offset,
3432 gint *line_byte_offset)
3434 GtkTextLineSegment *seg;
3435 GtkTextLineSegment *after_prev_indexable;
3436 GtkTextLineSegment *after_last_indexable;
3437 GtkTextLineSegment *last_indexable;
3441 g_return_if_fail(line != NULL);
3443 if (byte_offset < 0)
3445 /* -1 means end of line; we here assume no line is
3446 longer than 1 bazillion bytes, of course we assumed
3447 that anyway since we'd wrap around... */
3449 byte_offset = G_MAXINT;
3453 *any_segment = NULL;
3456 offset = byte_offset;
3458 last_indexable = NULL;
3459 after_last_indexable = line->segments;
3460 after_prev_indexable = line->segments;
3461 seg = line->segments;
3463 /* The loop ends when we're inside a segment;
3464 last_indexable refers to the last segment
3465 we passed entirely. */
3466 while (seg && offset >= seg->byte_count)
3468 if (seg->char_count > 0)
3470 offset -= seg->byte_count;
3471 bytes_in_line += seg->byte_count;
3472 last_indexable = seg;
3473 after_prev_indexable = after_last_indexable;
3474 after_last_indexable = last_indexable->next;
3482 /* We went off the end of the line */
3483 *segment = last_indexable;
3484 *any_segment = after_prev_indexable;
3485 /* subtracting 1 is OK, we know it's a newline at the end. */
3486 offset = (*segment)->byte_count - 1;
3487 bytes_in_line -= (*segment)->byte_count;
3492 if (after_last_indexable != NULL)
3493 *any_segment = after_last_indexable;
3495 *any_segment = *segment;
3498 /* Override any_segment if we're in the middle of a segment. */
3500 *any_segment = *segment;
3502 *seg_byte_offset = offset;
3504 g_assert(*segment != NULL);
3505 g_assert(*any_segment != NULL);
3506 g_assert(*seg_byte_offset < (*segment)->byte_count);
3508 *line_byte_offset = bytes_in_line + *seg_byte_offset;
3511 /* FIXME sync with byte_locate (or figure out a clean
3512 way to merge the two functions) */
3514 gtk_text_line_char_locate (GtkTextLine *line,
3516 GtkTextLineSegment **segment,
3517 GtkTextLineSegment **any_segment,
3518 gint *seg_char_offset,
3519 gint *line_char_offset)
3521 GtkTextLineSegment *seg;
3522 GtkTextLineSegment *after_prev_indexable;
3523 GtkTextLineSegment *after_last_indexable;
3524 GtkTextLineSegment *last_indexable;
3528 g_return_if_fail(line != NULL);
3530 if (char_offset < 0)
3532 /* -1 means end of line; we here assume no line is
3533 longer than 1 bazillion chars, of course we assumed
3534 that anyway since we'd wrap around... */
3536 char_offset = G_MAXINT;
3540 *any_segment = NULL;
3543 offset = char_offset;
3545 last_indexable = NULL;
3546 after_last_indexable = line->segments;
3547 after_prev_indexable = line->segments;
3548 seg = line->segments;
3550 /* The loop ends when we're inside a segment;
3551 last_indexable refers to the last segment
3552 we passed entirely. */
3553 while (seg && offset >= seg->char_count)
3555 if (seg->char_count > 0)
3557 offset -= seg->char_count;
3558 chars_in_line += seg->char_count;
3559 last_indexable = seg;
3560 after_prev_indexable = after_last_indexable;
3561 after_last_indexable = last_indexable->next;
3569 /* We went off the end of the line */
3570 *segment = last_indexable;
3571 *any_segment = after_prev_indexable;
3572 /* subtracting 1 is OK, we know it's a newline at the end. */
3573 offset = (*segment)->char_count - 1;
3574 chars_in_line -= (*segment)->char_count;
3579 if (after_last_indexable != NULL)
3580 *any_segment = after_last_indexable;
3582 *any_segment = *segment;
3585 /* Override any_segment if we're in the middle of a segment. */
3587 *any_segment = *segment;
3589 *seg_char_offset = offset;
3591 g_assert(*segment != NULL);
3592 g_assert(*any_segment != NULL);
3593 g_assert(*seg_char_offset < (*segment)->char_count);
3595 *line_char_offset = chars_in_line + *seg_char_offset;
3599 gtk_text_line_byte_to_char_offsets(GtkTextLine *line,
3601 gint *line_char_offset,
3602 gint *seg_char_offset)
3604 GtkTextLineSegment *seg;
3607 g_return_if_fail(line != NULL);
3608 g_return_if_fail(byte_offset >= 0);
3610 *line_char_offset = 0;
3612 offset = byte_offset;
3613 seg = line->segments;
3615 while (offset >= seg->byte_count)
3617 offset -= seg->byte_count;
3618 *line_char_offset += seg->char_count;
3620 g_assert(seg != NULL); /* means an invalid char offset */
3623 g_assert(seg->char_count > 0); /* indexable. */
3625 /* offset is now the number of bytes into the current segment we
3626 want to go. Count chars into the current segment. */
3628 if (seg->type == >k_text_char_type)
3630 *seg_char_offset = g_utf8_strlen(seg->body.chars, offset);
3632 g_assert(*seg_char_offset < seg->char_count);
3634 *line_char_offset += *seg_char_offset;
3638 g_assert(offset == 0);
3639 *seg_char_offset = 0;
3644 gtk_text_line_char_to_byte_offsets(GtkTextLine *line,
3646 gint *line_byte_offset,
3647 gint *seg_byte_offset)
3649 GtkTextLineSegment *seg;
3652 g_return_if_fail(line != NULL);
3653 g_return_if_fail(char_offset >= 0);
3655 *line_byte_offset = 0;
3657 offset = char_offset;
3658 seg = line->segments;
3660 while (offset >= seg->char_count)
3662 offset -= seg->char_count;
3663 *line_byte_offset += seg->byte_count;
3665 g_assert(seg != NULL); /* means an invalid char offset */
3668 g_assert(seg->char_count > 0); /* indexable. */
3670 /* offset is now the number of chars into the current segment we
3671 want to go. Count bytes into the current segment. */
3673 if (seg->type == >k_text_char_type)
3675 *seg_byte_offset = 0;
3679 const char * start = seg->body.chars + *seg_byte_offset;
3681 bytes = g_utf8_next_char (start) - start;
3682 *seg_byte_offset += bytes;
3686 g_assert(*seg_byte_offset < seg->byte_count);
3688 *line_byte_offset += *seg_byte_offset;
3692 g_assert(offset == 0);
3693 *seg_byte_offset = 0;
3698 node_compare (GtkTextBTreeNode *lhs,
3699 GtkTextBTreeNode *rhs)
3701 GtkTextBTreeNode *iter;
3702 GtkTextBTreeNode *node;
3703 GtkTextBTreeNode *common_parent;
3704 GtkTextBTreeNode *parent_of_lower;
3705 GtkTextBTreeNode *parent_of_higher;
3706 gboolean lhs_is_lower;
3707 GtkTextBTreeNode *lower;
3708 GtkTextBTreeNode *higher;
3710 /* This function assumes that lhs and rhs are not underneath each
3717 if (lhs->level < rhs->level)
3719 lhs_is_lower = TRUE;
3725 lhs_is_lower = FALSE;
3730 /* Algorithm: find common parent of lhs/rhs. Save the child nodes
3731 * of the common parent we used to reach the common parent; the
3732 * ordering of these child nodes in the child list is the ordering
3736 /* Get on the same level (may be on same level already) */
3738 while (node->level < higher->level)
3739 node = node->parent;
3741 g_assert (node->level == higher->level);
3743 g_assert (node != higher); /* Happens if lower is underneath higher */
3745 /* Go up until we have two children with a common parent.
3747 parent_of_lower = node;
3748 parent_of_higher = higher;
3750 while (parent_of_lower->parent != parent_of_higher->parent)
3752 parent_of_lower = parent_of_lower->parent;
3753 parent_of_higher = parent_of_higher->parent;
3756 g_assert (parent_of_lower->parent == parent_of_higher->parent);
3758 common_parent = parent_of_lower->parent;
3760 g_assert (common_parent != NULL);
3762 /* See which is first in the list of common_parent's children */
3763 iter = common_parent->children.node;
3764 while (iter != NULL)
3766 if (iter == parent_of_higher)
3768 /* higher is less than lower */
3771 return 1; /* lhs > rhs */
3775 else if (iter == parent_of_lower)
3777 /* lower is less than higher */
3780 return -1; /* lhs < rhs */
3788 g_assert_not_reached ();
3792 /* remember that tag == NULL means "any tag" */
3794 gtk_text_line_next_could_contain_tag(GtkTextLine *line,
3798 GtkTextBTreeNode *node;
3799 GtkTextTagInfo *info;
3800 gboolean below_tag_root;
3802 g_return_val_if_fail(line != NULL, NULL);
3804 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3805 gtk_text_btree_check (tree);
3809 /* Right now we can only offer linear-search if the user wants
3810 * to know about any tag toggle at all.
3812 return gtk_text_line_next (line);
3815 /* Our tag summaries only have node precision, not line
3816 precision. This means that if any line under a node could contain a
3817 tag, then any of the others could also contain a tag.
3819 In the future we could have some mechanism to keep track of how
3820 many toggles we've found under a node so far, since we have a
3821 count of toggles under the node. But for now I'm going with KISS.
3824 /* return same-node line, if any. */
3828 info = gtk_text_btree_get_existing_tag_info(tree, tag);
3832 if (info->tag_root == NULL)
3835 if (info->tag_root == line->parent)
3836 return NULL; /* we were at the last line under the tag root */
3838 /* We need to go up out of this node, and on to the next one with
3839 toggles for the target tag. If we're below the tag root, we need to
3840 find the next node below the tag root that has tag summaries. If
3841 we're not below the tag root, we need to see if the tag root is
3842 after us in the tree, and if so, return the first line underneath
3845 node = line->parent;
3846 below_tag_root = FALSE;
3847 while (node != NULL)
3849 if (node == info->tag_root)
3851 below_tag_root = TRUE;
3855 node = node->parent;
3860 node = line->parent;
3861 while (node != info->tag_root)
3863 if (node->next == NULL)
3864 node = node->parent;
3869 if (gtk_text_btree_node_has_tag(node, tag))
3879 ordering = node_compare (line->parent, info->tag_root);
3883 /* Tag root is ahead of us, so search there. */
3884 node = info->tag_root;
3889 /* Tag root is after us, so no more lines that
3890 * could contain the tag.
3895 g_assert_not_reached ();
3900 g_assert(node != NULL);
3902 /* We have to find the first sub-node of this node that contains
3906 while (node->level > 0)
3908 g_assert (node != NULL); /* If this fails, it likely means an
3909 incorrect tag summary led us on a
3910 wild goose chase down this branch of
3912 node = node->children.node;
3913 while (node != NULL)
3915 if (gtk_text_btree_node_has_tag (node, tag))
3921 g_assert (node != NULL);
3922 g_assert (node->level == 0);
3924 return node->children.line;
3928 prev_line_under_node (GtkTextBTreeNode *node,
3933 prev = node->children.line;
3939 while (prev->next != line)
3949 gtk_text_line_previous_could_contain_tag (GtkTextLine *line,
3953 GtkTextBTreeNode *node;
3954 GtkTextBTreeNode *found_node = NULL;
3955 GtkTextTagInfo *info;
3956 gboolean below_tag_root;
3958 GtkTextBTreeNode *line_ancestor;
3959 GtkTextBTreeNode *line_ancestor_parent;
3961 /* See next_could_contain_tag() for more extensive comments
3962 * on what's going on here.
3965 g_return_val_if_fail(line != NULL, NULL);
3967 if (gtk_debug_flags & GTK_DEBUG_TEXT)
3968 gtk_text_btree_check (tree);
3972 /* Right now we can only offer linear-search if the user wants
3973 * to know about any tag toggle at all.
3975 return gtk_text_line_previous (line);
3978 /* Return same-node line, if any. */
3979 prev = prev_line_under_node (line->parent, line);
3983 info = gtk_text_btree_get_existing_tag_info (tree, tag);
3987 if (info->tag_root == NULL)
3990 if (info->tag_root == line->parent)
3991 return NULL; /* we were at the first line under the tag root */
3993 /* Are we below the tag root */
3994 node = line->parent;
3995 below_tag_root = FALSE;
3996 while (node != NULL)
3998 if (node == info->tag_root)
4000 below_tag_root = TRUE;
4004 node = node->parent;
4009 /* Look for a previous node under this tag root that has our
4013 /* this assertion holds because line->parent is not the
4014 * tag root, we are below the tag root, and the tag
4017 g_assert (line->parent->parent != NULL);
4019 line_ancestor = line->parent;
4020 line_ancestor_parent = line->parent->parent;
4022 node = line_ancestor_parent->children.node;
4023 while (node != line_ancestor &&
4024 line_ancestor != info->tag_root)
4026 GSList *child_nodes = NULL;
4029 /* Create reverse-order list of nodes before
4032 while (node != line_ancestor
4035 child_nodes = g_slist_prepend (child_nodes, node);
4040 /* Try to find a node with our tag on it in the list */
4044 GtkTextBTreeNode *this_node = tmp->data;
4046 g_assert (this_node != line_ancestor);
4048 if (gtk_text_btree_node_has_tag (this_node, tag))
4050 found_node = this_node;
4051 g_slist_free (child_nodes);
4055 tmp = g_slist_next (tmp);
4058 g_slist_free (child_nodes);
4060 /* Didn't find anything on this level; go up one level. */
4061 line_ancestor = line_ancestor_parent;
4062 line_ancestor_parent = line_ancestor->parent;
4064 node = line_ancestor_parent->children.node;
4074 ordering = node_compare (line->parent, info->tag_root);
4078 /* Tag root is ahead of us, so no more lines
4085 /* Tag root is after us, so grab last tagged
4086 * line underneath the tag root.
4088 found_node = info->tag_root;
4092 g_assert_not_reached ();
4097 g_assert (found_node != NULL);
4099 /* We have to find the last sub-node of this node that contains
4104 while (node->level > 0)
4106 GSList *child_nodes = NULL;
4108 g_assert (node != NULL); /* If this fails, it likely means an
4109 incorrect tag summary led us on a
4110 wild goose chase down this branch of
4113 node = node->children.node;
4114 while (node != NULL)
4116 child_nodes = g_slist_prepend (child_nodes, node);
4120 node = NULL; /* detect failure to find a child node. */
4123 while (iter != NULL)
4125 if (gtk_text_btree_node_has_tag (iter->data, tag))
4127 /* recurse into this node. */
4132 iter = g_slist_next (iter);
4135 g_slist_free (child_nodes);
4137 g_assert (node != NULL);
4140 g_assert (node != NULL);
4141 g_assert (node->level == 0);
4143 /* this assertion is correct, but slow. */
4144 /* g_assert (node_compare (node, line->parent) < 0); */
4146 /* Return last line in this node. */
4148 prev = node->children.line;
4156 * Non-public function implementations
4160 summary_list_destroy(Summary *summary)
4163 while (summary != NULL)
4165 next = summary->next;
4166 summary_destroy (summary);
4172 get_last_line(GtkTextBTree *tree)
4174 if (tree->end_iter_line_stamp != tree->chars_changed_stamp)
4180 n_lines = gtk_text_btree_line_count(tree);
4182 g_assert(n_lines >= 1); /* num_lines doesn't return bogus last line. */
4184 line = gtk_text_btree_get_line(tree, n_lines, &real_line);
4186 tree->end_iter_line_stamp = tree->chars_changed_stamp;
4187 tree->end_iter_line = line;
4190 return tree->end_iter_line;
4198 gtk_text_line_new(void)
4202 line = g_new0(GtkTextLine, 1);
4208 gtk_text_line_destroy(GtkTextBTree *tree, GtkTextLine *line)
4210 GtkTextLineData *ld;
4211 GtkTextLineData *next;
4213 g_return_if_fail(line != NULL);
4220 view = gtk_text_btree_get_view (tree, ld->view_id);
4222 g_assert(view != NULL);
4225 gtk_text_layout_free_line_data (view->layout, line, ld);
4234 gtk_text_line_set_parent(GtkTextLine *line,
4235 GtkTextBTreeNode *node)
4237 if (line->parent == node)
4239 line->parent = node;
4240 gtk_text_btree_node_invalidate_upward(node, NULL);
4244 cleanup_line(GtkTextLine *line)
4246 GtkTextLineSegment *seg, **prev_p;
4250 * Make a pass over all of the segments in the line, giving each
4251 * a chance to clean itself up. This could potentially change
4252 * the structure of the line, e.g. by merging two segments
4253 * together or having two segments cancel themselves; if so,
4254 * then repeat the whole process again, since the first structure
4255 * change might make other structure changes possible. Repeat
4256 * until eventually there are no changes.
4263 for (prev_p = &line->segments, seg = *prev_p;
4265 prev_p = &(*prev_p)->next, seg = *prev_p)
4267 if (seg->type->cleanupFunc != NULL)
4269 *prev_p = (*seg->type->cleanupFunc)(seg, line);
4282 node_data_new(gpointer view_id)
4286 nd = g_new(NodeData, 1);
4288 nd->view_id = view_id;
4298 node_data_destroy(NodeData *nd)
4305 node_data_list_destroy(NodeData *nd)
4311 while (iter != NULL)
4314 node_data_destroy(iter);
4320 node_data_find(NodeData *nd, gpointer view_id)
4324 if (nd->view_id == view_id)
4332 summary_destroy (Summary *summary)
4334 /* Fill with error-triggering garbage */
4335 summary->info = (void*)0x1;
4336 summary->toggle_count = 567;
4337 summary->next = (void*)0x1;
4341 static GtkTextBTreeNode*
4342 gtk_text_btree_node_new(void)
4344 GtkTextBTreeNode *node;
4346 node = g_new(GtkTextBTreeNode, 1);
4348 node->node_data = NULL;
4354 gtk_text_btree_node_adjust_toggle_count (GtkTextBTreeNode *node,
4355 GtkTextTagInfo *info,
4360 summary = node->summary;
4361 while (summary != NULL)
4363 if (summary->info == info)
4365 summary->toggle_count += adjust;
4369 summary = summary->next;
4372 if (summary == NULL)
4374 /* didn't find a summary for our tag. */
4375 g_return_if_fail(adjust > 0);
4376 summary = g_new(Summary, 1);
4377 summary->info = info;
4378 summary->toggle_count = adjust;
4379 summary->next = node->summary;
4380 node->summary = summary;
4384 /* Note that the tag root and above do not have summaries
4385 for the tag; only nodes below the tag root have
4388 gtk_text_btree_node_has_tag (GtkTextBTreeNode *node, GtkTextTag *tag)
4392 summary = node->summary;
4393 while (summary != NULL)
4396 summary->info->tag == tag)
4399 summary = summary->next;
4405 /* Add node and all children to the damage region. */
4407 gtk_text_btree_node_invalidate_downward(GtkTextBTreeNode *node)
4411 nd = node->node_data;
4418 if (node->level == 0)
4422 line = node->children.line;
4423 while (line != NULL)
4425 GtkTextLineData *ld;
4439 GtkTextBTreeNode *child;
4441 child = node->children.node;
4443 while (child != NULL)
4445 gtk_text_btree_node_invalidate_downward(child);
4447 child = child->next;
4453 gtk_text_btree_node_invalidate_upward(GtkTextBTreeNode *node, gpointer view_id)
4455 GtkTextBTreeNode *iter;
4458 while (iter != NULL)
4464 nd = node_data_find (iter->node_data, view_id);
4466 if (nd == NULL || !nd->valid)
4467 break; /* Once a node is invalid, we know its parents are as well. */
4473 gboolean should_continue = FALSE;
4475 nd = iter->node_data;
4480 should_continue = TRUE;
4487 if (!should_continue)
4488 break; /* This node was totally invalidated, so are its
4492 iter = iter->parent;
4498 * gtk_text_btree_is_valid:
4499 * @tree: a #GtkTextBTree
4500 * @view_id: ID for the view
4502 * Check to see if the entire #GtkTextBTree is valid or not for
4505 * Return value: %TRUE if the entire #GtkTextBTree is valid
4508 gtk_text_btree_is_valid (GtkTextBTree *tree,
4512 g_return_val_if_fail (tree != NULL, FALSE);
4514 nd = node_data_find (tree->root_node->node_data, view_id);
4515 return (nd && nd->valid);
4518 typedef struct _ValidateState ValidateState;
4520 struct _ValidateState
4522 gint remaining_pixels;
4523 gboolean in_validation;
4530 gtk_text_btree_node_validate (BTreeView *view,
4531 GtkTextBTreeNode *node,
4533 ValidateState *state)
4535 gint node_valid = TRUE;
4536 gint node_width = 0;
4537 gint node_height = 0;
4539 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4540 g_return_if_fail (!nd->valid);
4542 if (node->level == 0)
4544 GtkTextLine *line = node->children.line;
4545 GtkTextLineData *ld;
4547 /* Iterate over leading valid lines */
4548 while (line != NULL)
4550 ld = gtk_text_line_get_data (line, view_id);
4552 if (!ld || !ld->valid)
4554 else if (state->in_validation)
4556 state->in_validation = FALSE;
4561 state->y += ld->height;
4562 node_width = MAX (ld->width, node_width);
4563 node_height += ld->height;
4569 state->in_validation = TRUE;
4571 /* Iterate over invalid lines */
4572 while (line != NULL)
4574 ld = gtk_text_line_get_data (line, view_id);
4576 if (ld && ld->valid)
4581 state->old_height += ld->height;
4582 ld = gtk_text_layout_wrap (view->layout, line, ld);
4583 state->new_height += ld->height;
4585 node_width = MAX (ld->width, node_width);
4586 node_height += ld->height;
4588 state->remaining_pixels -= ld->height;
4589 if (state->remaining_pixels <= 0)
4599 /* Iterate over the remaining lines */
4600 while (line != NULL)
4602 ld = gtk_text_line_get_data (line, view_id);
4603 state->in_validation = FALSE;
4605 if (!ld || !ld->valid)
4610 node_width = MAX (ld->width, node_width);
4611 node_height += ld->height;
4619 GtkTextBTreeNode *child;
4622 child = node->children.node;
4624 /* Iterate over leading valid nodes */
4627 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4629 if (!child_nd->valid)
4631 else if (state->in_validation)
4633 state->in_validation = FALSE;
4638 state->y += child_nd->height;
4639 node_width = MAX (node_width, child_nd->width);
4640 node_height += child_nd->height;
4643 child = child->next;
4646 /* Iterate over invalid nodes */
4649 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4651 if (child_nd->valid)
4655 gtk_text_btree_node_validate (view, child, view_id, state);
4657 if (!child_nd->valid)
4659 node_width = MAX (node_width, child_nd->width);
4660 node_height += child_nd->height;
4662 if (!state->in_validation || state->remaining_pixels <= 0)
4664 child = child->next;
4669 child = child->next;
4672 /* Iterate over the remaining lines */
4675 child_nd = gtk_text_btree_node_ensure_data (child, view_id);
4676 state->in_validation = FALSE;
4678 if (!child_nd->valid)
4681 node_width = MAX (child_nd->width, node_width);
4682 node_height += child_nd->height;
4684 child = child->next;
4688 nd->width = node_width;
4689 nd->height = node_height;
4690 nd->valid = node_valid;
4694 * gtk_text_btree_validate:
4695 * @tree: a #GtkTextBTree
4697 * @max_pixels: the maximum number of pixels to validate. (No more
4698 * than one paragraph beyond this limit will be validated)
4699 * @y: location to store starting y coordinate of validated region
4700 * @old_height: location to store old height of validated region
4701 * @new_height: location to store new height of validated region
4703 * Validate a single contiguous invalid region of a #GtkTextBTree for
4706 * Return value: %TRUE if a region has been validated, %FALSE if the
4707 * entire tree was already valid.
4710 gtk_text_btree_validate (GtkTextBTree *tree,
4719 g_return_val_if_fail (tree != NULL, FALSE);
4721 view = gtk_text_btree_get_view (tree, view_id);
4722 g_return_val_if_fail (view != NULL, FALSE);
4724 if (!gtk_text_btree_is_valid (tree, view_id))
4726 ValidateState state;
4728 state.remaining_pixels = max_pixels;
4729 state.in_validation = FALSE;
4731 state.old_height = 0;
4732 state.new_height = 0;
4734 gtk_text_btree_node_validate (view,
4741 *old_height = state.old_height;
4743 *new_height = state.new_height;
4745 if (gtk_debug_flags & GTK_DEBUG_TEXT)
4746 gtk_text_btree_check(tree);
4755 gtk_text_btree_node_compute_view_aggregates (GtkTextBTreeNode *node,
4759 gboolean *valid_out)
4763 gboolean valid = TRUE;
4765 if (node->level == 0)
4767 GtkTextLine *line = node->children.line;
4769 while (line != NULL)
4771 GtkTextLineData *ld = gtk_text_line_get_data (line, view_id);
4773 if (!ld || !ld->valid)
4778 width = MAX (ld->width, width);
4779 height += ld->height;
4787 GtkTextBTreeNode *child = node->children.node;
4791 NodeData *child_nd = node_data_find (child->node_data, view_id);
4793 if (!child_nd || !child_nd->valid)
4798 width = MAX (child_nd->width, width);
4799 height += child_nd->height;
4802 child = child->next;
4807 *height_out = height;
4812 /* Recompute the validity and size of the view data for a given
4813 * view at this node from the immediate children of the node
4816 gtk_text_btree_node_check_valid (GtkTextBTreeNode *node,
4819 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4824 gtk_text_btree_node_compute_view_aggregates (node, view_id,
4825 &width, &height, &valid);
4827 nd->height = height;
4834 gtk_text_btree_node_check_valid_upward (GtkTextBTreeNode *node,
4839 gtk_text_btree_node_check_valid (node, view_id);
4840 node = node->parent;
4845 gtk_text_btree_node_check_valid_downward (GtkTextBTreeNode *node,
4848 if (node->level == 0)
4850 return gtk_text_btree_node_check_valid (node, view_id);
4854 GtkTextBTreeNode *child = node->children.node;
4856 NodeData *nd = gtk_text_btree_node_ensure_data (node, view_id);
4864 NodeData *child_nd = gtk_text_btree_node_check_valid_downward (child, view_id);
4866 if (!child_nd->valid)
4868 nd->width = MAX (child_nd->width, nd->width);
4869 nd->height += child_nd->height;
4871 child = child->next;
4880 * gtk_text_btree_validate_line:
4881 * @tree: a #GtkTextBTree
4882 * @line: line to validate
4883 * @view_id: view ID for the view to validate
4885 * Revalidate a single line of the btree for the given view, propagate
4886 * results up through the entire tree.
4889 gtk_text_btree_validate_line (GtkTextBTree *tree,
4893 GtkTextLineData *ld;
4894 GtkTextLine *last_line;
4897 g_return_if_fail (tree != NULL);
4898 g_return_if_fail (line != NULL);
4900 view = gtk_text_btree_get_view (tree, view_id);
4901 g_return_if_fail (view != NULL);
4903 ld = gtk_text_line_get_data(line, view_id);
4904 if (!ld || !ld->valid)
4906 ld = gtk_text_layout_wrap (view->layout, line, ld);
4907 last_line = get_last_line (tree);
4909 gtk_text_btree_node_check_valid_upward (line->parent, view_id);
4914 gtk_text_btree_node_remove_view(BTreeView *view, GtkTextBTreeNode *node, gpointer view_id)
4916 if (node->level == 0)
4920 line = node->children.line;
4921 while (line != NULL)
4923 GtkTextLineData *ld;
4925 ld = gtk_text_line_remove_data(line, view_id);
4928 gtk_text_layout_free_line_data (view->layout, line, ld);
4935 GtkTextBTreeNode *child;
4937 child = node->children.node;
4939 while (child != NULL)
4942 gtk_text_btree_node_remove_view(view, child, view_id);
4944 child = child->next;
4948 gtk_text_btree_node_remove_data(node, view_id);
4952 gtk_text_btree_node_destroy(GtkTextBTree *tree, GtkTextBTreeNode *node)
4954 if (node->level == 0)
4957 GtkTextLineSegment *seg;
4959 while (node->children.line != NULL)
4961 line = node->children.line;
4962 node->children.line = line->next;
4963 while (line->segments != NULL)
4965 seg = line->segments;
4966 line->segments = seg->next;
4967 (*seg->type->deleteFunc)(seg, line, 1);
4969 gtk_text_line_destroy(tree, line);
4974 GtkTextBTreeNode *childPtr;
4976 while (node->children.node != NULL)
4978 childPtr = node->children.node;
4979 node->children.node = childPtr->next;
4980 gtk_text_btree_node_destroy(tree, childPtr);
4983 summary_list_destroy(node->summary);
4984 node_data_list_destroy(node->node_data);
4989 gtk_text_btree_node_ensure_data(GtkTextBTreeNode *node, gpointer view_id)
4993 nd = node->node_data;
4996 if (nd->view_id == view_id)
5003 nd = node_data_new(view_id);
5005 if (node->node_data)
5006 nd->next = node->node_data;
5008 node->node_data = nd;
5015 gtk_text_btree_node_remove_data(GtkTextBTreeNode *node, gpointer view_id)
5021 nd = node->node_data;
5024 if (nd->view_id == view_id)
5035 prev->next = nd->next;
5037 if (node->node_data == nd)
5038 node->node_data = nd->next;
5042 node_data_destroy(nd);
5046 gtk_text_btree_node_get_size(GtkTextBTreeNode *node, gpointer view_id,
5047 gint *width, gint *height)
5051 g_return_if_fail(width != NULL);
5052 g_return_if_fail(height != NULL);
5054 nd = gtk_text_btree_node_ensure_data(node, view_id);
5059 *height = nd->height;
5062 /* Find the closest common ancestor of the two nodes. FIXME: The interface
5063 * here isn't quite right, since for a lot of operations we want to
5064 * know which children of the common parent correspond to the two nodes
5065 * (e.g., when computing the order of two iters)
5067 static GtkTextBTreeNode *
5068 gtk_text_btree_node_common_parent (GtkTextBTreeNode *node1,
5069 GtkTextBTreeNode *node2)
5071 while (node1->level < node2->level)
5072 node1 = node1->parent;
5073 while (node2->level < node1->level)
5074 node2 = node2->parent;
5075 while (node1 != node2)
5077 node1 = node1->parent;
5078 node2 = node2->parent;
5089 gtk_text_btree_get_view(GtkTextBTree *tree, gpointer view_id)
5094 while (view != NULL)
5096 if (view->view_id == view_id)
5105 get_tree_bounds(GtkTextBTree *tree,
5109 gtk_text_btree_get_iter_at_line_char(tree, start, 0, 0);
5110 gtk_text_btree_get_last_iter(tree, end);
5114 tag_changed_cb(GtkTextTagTable *table,
5116 gboolean size_changed,
5121 /* We need to queue a redisplay on all regions that are tagged with
5127 if (gtk_text_btree_get_iter_at_first_toggle(tree, &start, tag))
5129 /* Must be a last toggle if there was a first one. */
5130 gtk_text_btree_get_iter_at_last_toggle(tree, &end, tag);
5131 gtk_text_btree_invalidate_region(tree,
5142 while (view != NULL)
5146 gtk_text_btree_get_view_size (tree, view->view_id, &width, &height);
5147 gtk_text_layout_changed (view->layout, 0, height, height);
5155 tag_removed_cb(GtkTextTagTable *table,
5159 /* Remove the tag from the tree */
5164 get_tree_bounds(tree, &start, &end);
5166 gtk_text_btree_tag(&start, &end, tag, FALSE);
5167 gtk_text_btree_remove_tag_info (tree, tag);
5171 /* Rebalance the out-of-whack node "node" */
5173 gtk_text_btree_rebalance(GtkTextBTree *tree,
5174 GtkTextBTreeNode *node)
5177 * Loop over the entire ancestral chain of the GtkTextBTreeNode, working
5178 * up through the tree one GtkTextBTreeNode at a time until the root
5179 * GtkTextBTreeNode has been processed.
5182 while (node != NULL)
5184 GtkTextBTreeNode *new_node, *child;
5189 * Check to see if the GtkTextBTreeNode has too many children. If it does,
5190 * then split off all but the first MIN_CHILDREN into a separate
5191 * GtkTextBTreeNode following the original one. Then repeat until the
5192 * GtkTextBTreeNode has a decent size.
5195 if (node->num_children > MAX_CHILDREN)
5200 * If the GtkTextBTreeNode being split is the root
5201 * GtkTextBTreeNode, then make a new root GtkTextBTreeNode above
5205 if (node->parent == NULL)
5207 new_node = gtk_text_btree_node_new();
5208 new_node->parent = NULL;
5209 new_node->next = NULL;
5210 new_node->summary = NULL;
5211 new_node->level = node->level + 1;
5212 new_node->children.node = node;
5213 recompute_node_counts(tree, new_node);
5214 tree->root_node = new_node;
5216 new_node = gtk_text_btree_node_new();
5217 new_node->parent = node->parent;
5218 new_node->next = node->next;
5219 node->next = new_node;
5220 new_node->summary = NULL;
5221 new_node->level = node->level;
5222 new_node->num_children = node->num_children - MIN_CHILDREN;
5223 if (node->level == 0)
5225 for (i = MIN_CHILDREN-1,
5226 line = node->children.line;
5227 i > 0; i--, line = line->next)
5229 /* Empty loop body. */
5231 new_node->children.line = line->next;
5236 for (i = MIN_CHILDREN-1,
5237 child = node->children.node;
5238 i > 0; i--, child = child->next)
5240 /* Empty loop body. */
5242 new_node->children.node = child->next;
5245 recompute_node_counts(tree, node);
5246 node->parent->num_children++;
5248 if (node->num_children <= MAX_CHILDREN)
5250 recompute_node_counts(tree, node);
5256 while (node->num_children < MIN_CHILDREN)
5258 GtkTextBTreeNode *other;
5259 GtkTextBTreeNode *halfwaynode = NULL; /* Initialization needed only */
5260 GtkTextLine *halfwayline = NULL; /* to prevent cc warnings. */
5261 int total_children, first_children, i;
5264 * Too few children for this GtkTextBTreeNode. If this is the root then,
5265 * it's OK for it to have less than MIN_CHILDREN children
5266 * as long as it's got at least two. If it has only one
5267 * (and isn't at level 0), then chop the root GtkTextBTreeNode out of
5268 * the tree and use its child as the new root.
5271 if (node->parent == NULL)
5273 if ((node->num_children == 1) && (node->level > 0))
5275 tree->root_node = node->children.node;
5276 tree->root_node->parent = NULL;
5277 summary_list_destroy(node->summary);
5284 * Not the root. Make sure that there are siblings to
5288 if (node->parent->num_children < 2)
5290 gtk_text_btree_rebalance(tree, node->parent);
5295 * Find a sibling neighbor to borrow from, and arrange for
5296 * node to be the earlier of the pair.
5299 if (node->next == NULL)
5301 for (other = node->parent->children.node;
5302 other->next != node;
5303 other = other->next)
5305 /* Empty loop body. */
5312 * We're going to either merge the two siblings together
5313 * into one GtkTextBTreeNode or redivide the children among them to
5314 * balance their loads. As preparation, join their two
5315 * child lists into a single list and remember the half-way
5316 * point in the list.
5319 total_children = node->num_children + other->num_children;
5320 first_children = total_children/2;
5321 if (node->children.node == NULL)
5323 node->children = other->children;
5324 other->children.node = NULL;
5325 other->children.line = NULL;
5327 if (node->level == 0)
5331 for (line = node->children.line, i = 1;
5333 line = line->next, i++)
5335 if (i == first_children)
5340 line->next = other->children.line;
5341 while (i <= first_children)
5350 GtkTextBTreeNode *child;
5352 for (child = node->children.node, i = 1;
5353 child->next != NULL;
5354 child = child->next, i++)
5356 if (i <= first_children)
5358 if (i == first_children)
5360 halfwaynode = child;
5364 child->next = other->children.node;
5365 while (i <= first_children)
5367 halfwaynode = child;
5368 child = child->next;
5374 * If the two siblings can simply be merged together, do it.
5377 if (total_children <= MAX_CHILDREN)
5379 recompute_node_counts(tree, node);
5380 node->next = other->next;
5381 node->parent->num_children--;
5382 summary_list_destroy(other->summary);
5388 * The siblings can't be merged, so just divide their
5389 * children evenly between them.
5392 if (node->level == 0)
5394 other->children.line = halfwayline->next;
5395 halfwayline->next = NULL;
5399 other->children.node = halfwaynode->next;
5400 halfwaynode->next = NULL;
5403 recompute_node_counts(tree, node);
5404 recompute_node_counts(tree, other);
5407 node = node->parent;
5412 post_insert_fixup(GtkTextBTree *tree,
5414 gint line_count_delta,
5415 gint char_count_delta)
5418 GtkTextBTreeNode *node;
5421 * Increment the line counts in all the parent GtkTextBTreeNodes of the insertion
5422 * point, then rebalance the tree if necessary.
5425 for (node = line->parent ; node != NULL;
5426 node = node->parent)
5428 node->num_lines += line_count_delta;
5429 node->num_chars += char_count_delta;
5431 node = line->parent;
5432 node->num_children += line_count_delta;
5434 if (node->num_children > MAX_CHILDREN)
5436 gtk_text_btree_rebalance(tree, node);
5439 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5440 gtk_text_btree_check(tree);
5443 static GtkTextTagInfo*
5444 gtk_text_btree_get_existing_tag_info(GtkTextBTree *tree,
5447 GtkTextTagInfo *info;
5451 list = tree->tag_infos;
5452 while (list != NULL)
5455 if (info->tag == tag)
5458 list = g_slist_next(list);
5464 static GtkTextTagInfo*
5465 gtk_text_btree_get_tag_info(GtkTextBTree *tree,
5468 GtkTextTagInfo *info;
5470 info = gtk_text_btree_get_existing_tag_info(tree, tag);
5474 /* didn't find it, create. */
5476 info = g_new(GtkTextTagInfo, 1);
5479 gtk_object_ref(GTK_OBJECT(tag));
5480 info->tag_root = NULL;
5481 info->toggle_count = 0;
5483 tree->tag_infos = g_slist_prepend(tree->tag_infos, info);
5490 gtk_text_btree_remove_tag_info(GtkTextBTree *tree,
5493 GtkTextTagInfo *info;
5498 list = tree->tag_infos;
5499 while (list != NULL)
5502 if (info->tag == tag)
5506 prev->next = list->next;
5510 tree->tag_infos = list->next;
5515 gtk_object_unref(GTK_OBJECT(info->tag));
5521 list = g_slist_next(list);
5524 g_assert_not_reached();
5529 recompute_level_zero_counts(GtkTextBTreeNode *node)
5532 GtkTextLineSegment *seg;
5534 g_assert(node->level == 0);
5536 line = node->children.line;
5537 while (line != NULL)
5539 node->num_children++;
5542 if (line->parent != node)
5543 gtk_text_line_set_parent(line, node);
5545 seg = line->segments;
5549 node->num_chars += seg->char_count;
5551 if (((seg->type != >k_text_toggle_on_type)
5552 && (seg->type != >k_text_toggle_off_type))
5553 || !(seg->body.toggle.inNodeCounts))
5559 GtkTextTagInfo *info;
5561 info = seg->body.toggle.info;
5563 gtk_text_btree_node_adjust_toggle_count(node, info, 1);
5574 recompute_level_nonzero_counts(GtkTextBTreeNode *node)
5577 GtkTextBTreeNode *child;
5579 g_assert(node->level > 0);
5581 child = node->children.node;
5582 while (child != NULL)
5584 node->num_children += 1;
5585 node->num_lines += child->num_lines;
5586 node->num_chars += child->num_chars;
5588 if (child->parent != node)
5590 child->parent = node;
5591 gtk_text_btree_node_invalidate_upward(node, NULL);
5594 summary = child->summary;
5595 while (summary != NULL)
5597 gtk_text_btree_node_adjust_toggle_count(node,
5599 summary->toggle_count);
5601 summary = summary->next;
5604 child = child->next;
5609 *----------------------------------------------------------------------
5611 * recompute_node_counts --
5613 * This procedure is called to recompute all the counts in a GtkTextBTreeNode
5614 * (tags, child information, etc.) by scanning the information in
5615 * its descendants. This procedure is called during rebalancing
5616 * when a GtkTextBTreeNode's child structure has changed.
5622 * The tag counts for node are modified to reflect its current
5623 * child structure, as are its num_children, num_lines, num_chars fields.
5624 * Also, all of the childrens' parent fields are made to point
5627 *----------------------------------------------------------------------
5631 recompute_node_counts(GtkTextBTree *tree, GtkTextBTreeNode *node)
5634 Summary *summary, *summary2;
5637 * Zero out all the existing counts for the GtkTextBTreeNode, but don't delete
5638 * the existing Summary records (most of them will probably be reused).
5641 summary = node->summary;
5642 while (summary != NULL)
5644 summary->toggle_count = 0;
5645 summary = summary->next;
5648 node->num_children = 0;
5649 node->num_lines = 0;
5650 node->num_chars = 0;
5653 * Scan through the children, adding the childrens' tag counts into
5654 * the GtkTextBTreeNode's tag counts and adding new Summary structures if
5658 if (node->level == 0)
5659 recompute_level_zero_counts(node);
5661 recompute_level_nonzero_counts(node);
5666 gtk_text_btree_node_check_valid (node, view->view_id);
5671 * Scan through the GtkTextBTreeNode's tag records again and delete any Summary
5672 * records that still have a zero count, or that have all the toggles.
5673 * The GtkTextBTreeNode with the children that account for all the tags toggles
5674 * have no summary information, and they become the tag_root for the tag.
5678 for (summary = node->summary; summary != NULL; )
5680 if (summary->toggle_count > 0 &&
5681 summary->toggle_count < summary->info->toggle_count)
5683 if (node->level == summary->info->tag_root->level)
5686 * The tag's root GtkTextBTreeNode split and some toggles left.
5687 * The tag root must move up a level.
5689 summary->info->tag_root = node->parent;
5692 summary = summary->next;
5695 if (summary->toggle_count == summary->info->toggle_count)
5698 * A GtkTextBTreeNode merge has collected all the toggles under
5699 * one GtkTextBTreeNode. Push the root down to this level.
5701 summary->info->tag_root = node;
5703 if (summary2 != NULL)
5705 summary2->next = summary->next;
5706 summary_destroy (summary);
5707 summary = summary2->next;
5711 node->summary = summary->next;
5712 summary_destroy (summary);
5713 summary = node->summary;
5719 change_node_toggle_count(GtkTextBTreeNode *node,
5720 GtkTextTagInfo *info,
5721 gint delta) /* may be negative */
5723 Summary *summary, *prevPtr;
5724 GtkTextBTreeNode *node2Ptr;
5725 int rootLevel; /* Level of original tag root */
5727 info->toggle_count += delta;
5729 if (info->tag_root == (GtkTextBTreeNode *) NULL)
5731 info->tag_root = node;
5736 * Note the level of the existing root for the tag so we can detect
5737 * if it needs to be moved because of the toggle count change.
5740 rootLevel = info->tag_root->level;
5743 * Iterate over the GtkTextBTreeNode and its ancestors up to the tag root, adjusting
5744 * summary counts at each GtkTextBTreeNode and moving the tag's root upwards if
5748 for ( ; node != info->tag_root; node = node->parent)
5751 * See if there's already an entry for this tag for this GtkTextBTreeNode. If so,
5752 * perhaps all we have to do is adjust its count.
5755 for (prevPtr = NULL, summary = node->summary;
5757 prevPtr = summary, summary = summary->next)
5759 if (summary->info == info)
5764 if (summary != NULL)
5766 summary->toggle_count += delta;
5767 if (summary->toggle_count > 0 &&
5768 summary->toggle_count < info->toggle_count)
5772 if (summary->toggle_count != 0)
5775 * Should never find a GtkTextBTreeNode with max toggle count at this
5776 * point (there shouldn't have been a summary entry in the
5780 g_error("change_node_toggle_count: bad toggle count (%d) max (%d)",
5781 summary->toggle_count, info->toggle_count);
5785 * Zero toggle count; must remove this tag from the list.
5788 if (prevPtr == NULL)
5790 node->summary = summary->next;
5794 prevPtr->next = summary->next;
5796 summary_destroy (summary);
5801 * This tag isn't currently in the summary information list.
5804 if (rootLevel == node->level)
5808 * The old tag root is at the same level in the tree as this
5809 * GtkTextBTreeNode, but it isn't at this GtkTextBTreeNode. Move the tag root up
5810 * a level, in the hopes that it will now cover this GtkTextBTreeNode
5811 * as well as the old root (if not, we'll move it up again
5812 * the next time through the loop). To push it up one level
5813 * we copy the original toggle count into the summary
5814 * information at the old root and change the root to its
5815 * parent GtkTextBTreeNode.
5818 GtkTextBTreeNode *rootnode = info->tag_root;
5819 summary = (Summary *) g_malloc(sizeof(Summary));
5820 summary->info = info;
5821 summary->toggle_count = info->toggle_count - delta;
5822 summary->next = rootnode->summary;
5823 rootnode->summary = summary;
5824 rootnode = rootnode->parent;
5825 rootLevel = rootnode->level;
5826 info->tag_root = rootnode;
5828 summary = (Summary *) g_malloc(sizeof(Summary));
5829 summary->info = info;
5830 summary->toggle_count = delta;
5831 summary->next = node->summary;
5832 node->summary = summary;
5837 * If we've decremented the toggle count, then it may be necessary
5838 * to push the tag root down one or more levels.
5845 if (info->toggle_count == 0)
5847 info->tag_root = (GtkTextBTreeNode *) NULL;
5850 node = info->tag_root;
5851 while (node->level > 0)
5854 * See if a single child GtkTextBTreeNode accounts for all of the tag's
5855 * toggles. If so, push the root down one level.
5858 for (node2Ptr = node->children.node;
5859 node2Ptr != (GtkTextBTreeNode *)NULL ;
5860 node2Ptr = node2Ptr->next)
5862 for (prevPtr = NULL, summary = node2Ptr->summary;
5864 prevPtr = summary, summary = summary->next)
5866 if (summary->info == info)
5871 if (summary == NULL)
5875 if (summary->toggle_count != info->toggle_count)
5878 * No GtkTextBTreeNode has all toggles, so the root is still valid.
5885 * This GtkTextBTreeNode has all the toggles, so push down the root.
5888 if (prevPtr == NULL)
5890 node2Ptr->summary = summary->next;
5894 prevPtr->next = summary->next;
5896 summary_destroy (summary);
5897 info->tag_root = node2Ptr;
5900 node = info->tag_root;
5905 *----------------------------------------------------------------------
5909 * This is a utility procedure used by gtk_text_btree_get_tags. It
5910 * increments the count for a particular tag, adding a new
5911 * entry for that tag if there wasn't one previously.
5917 * The information at *tagInfoPtr may be modified, and the arrays
5918 * may be reallocated to make them larger.
5920 *----------------------------------------------------------------------
5924 inc_count(GtkTextTag *tag, int inc, TagInfo *tagInfoPtr)
5929 for (tag_p = tagInfoPtr->tags, count = tagInfoPtr->numTags;
5930 count > 0; tag_p++, count--)
5934 tagInfoPtr->counts[tagInfoPtr->numTags-count] += inc;
5940 * There isn't currently an entry for this tag, so we have to
5941 * make a new one. If the arrays are full, then enlarge the
5945 if (tagInfoPtr->numTags == tagInfoPtr->arraySize)
5947 GtkTextTag **newTags;
5948 int *newCounts, newSize;
5950 newSize = 2*tagInfoPtr->arraySize;
5951 newTags = (GtkTextTag **) g_malloc((unsigned)
5952 (newSize*sizeof(GtkTextTag *)));
5953 memcpy((void *) newTags, (void *) tagInfoPtr->tags,
5954 tagInfoPtr->arraySize *sizeof(GtkTextTag *));
5955 g_free((char *) tagInfoPtr->tags);
5956 tagInfoPtr->tags = newTags;
5957 newCounts = (int *) g_malloc((unsigned) (newSize*sizeof(int)));
5958 memcpy((void *) newCounts, (void *) tagInfoPtr->counts,
5959 tagInfoPtr->arraySize *sizeof(int));
5960 g_free((char *) tagInfoPtr->counts);
5961 tagInfoPtr->counts = newCounts;
5962 tagInfoPtr->arraySize = newSize;
5965 tagInfoPtr->tags[tagInfoPtr->numTags] = tag;
5966 tagInfoPtr->counts[tagInfoPtr->numTags] = inc;
5967 tagInfoPtr->numTags++;
5971 gtk_text_btree_link_segment(GtkTextLineSegment *seg,
5972 const GtkTextIter *iter)
5974 GtkTextLineSegment *prev;
5978 line = gtk_text_iter_get_text_line(iter);
5979 tree = gtk_text_iter_get_btree(iter);
5981 prev = gtk_text_line_segment_split(iter);
5984 seg->next = line->segments;
5985 line->segments = seg;
5989 seg->next = prev->next;
5993 segments_changed(tree);
5995 if (gtk_debug_flags & GTK_DEBUG_TEXT)
5996 gtk_text_btree_check(tree);
6000 gtk_text_btree_unlink_segment(GtkTextBTree *tree,
6001 GtkTextLineSegment *seg,
6004 GtkTextLineSegment *prev;
6006 if (line->segments == seg)
6008 line->segments = seg->next;
6012 for (prev = line->segments; prev->next != seg;
6015 /* Empty loop body. */
6017 prev->next = seg->next;
6020 segments_changed(tree);
6024 * This is here because it requires BTree internals, it logically
6025 * belongs in gtktextsegment.c
6030 *--------------------------------------------------------------
6032 * toggle_segment_check_func --
6034 * This procedure is invoked to perform consistency checks
6035 * on toggle segments.
6041 * If a consistency problem is found the procedure g_errors.
6043 *--------------------------------------------------------------
6047 toggle_segment_check_func(GtkTextLineSegment *segPtr,
6053 if (segPtr->byte_count != 0)
6055 g_error("toggle_segment_check_func: segment had non-zero size");
6057 if (!segPtr->body.toggle.inNodeCounts)
6059 g_error("toggle_segment_check_func: toggle counts not updated in GtkTextBTreeNodes");
6061 needSummary = (segPtr->body.toggle.info->tag_root != line->parent);
6062 for (summary = line->parent->summary; ;
6063 summary = summary->next)
6065 if (summary == NULL)
6069 g_error("toggle_segment_check_func: tag not present in GtkTextBTreeNode");
6076 if (summary->info == segPtr->body.toggle.info)
6080 g_error("toggle_segment_check_func: tag present in root GtkTextBTreeNode summary");
6092 gtk_text_btree_node_view_check_consistency (GtkTextBTreeNode *node,
6099 gtk_text_btree_node_compute_view_aggregates (node, nd->view_id,
6100 &width, &height, &valid);
6101 if (nd->width != width ||
6102 nd->height != height ||
6103 !nd->valid != !valid)
6105 g_error ("Node aggregates for view %p are invalid:\n"
6106 "Are (%d,%d,%s), should be (%d,%d,%s)",
6108 nd->width, nd->height, nd->valid ? "TRUE" : "FALSE",
6109 width, height, valid ? "TRUE" : "FALSE");
6114 gtk_text_btree_node_check_consistency(GtkTextBTreeNode *node)
6116 GtkTextBTreeNode *childnode;
6117 Summary *summary, *summary2;
6119 GtkTextLineSegment *segPtr;
6120 int num_children, num_lines, num_chars, toggle_count, min_children;
6121 GtkTextLineData *ld;
6124 if (node->parent != NULL)
6126 min_children = MIN_CHILDREN;
6128 else if (node->level > 0)
6135 if ((node->num_children < min_children)
6136 || (node->num_children > MAX_CHILDREN))
6138 g_error("gtk_text_btree_node_check_consistency: bad child count (%d)",
6139 node->num_children);
6142 nd = node->node_data;
6145 gtk_text_btree_node_view_check_consistency (node, nd);
6152 if (node->level == 0)
6154 for (line = node->children.line; line != NULL;
6157 if (line->parent != node)
6159 g_error("gtk_text_btree_node_check_consistency: line doesn't point to parent");
6161 if (line->segments == NULL)
6163 g_error("gtk_text_btree_node_check_consistency: line has no segments");
6169 /* Just ensuring we don't segv while doing this loop */
6174 for (segPtr = line->segments; segPtr != NULL; segPtr = segPtr->next)
6176 if (segPtr->type->checkFunc != NULL)
6178 (*segPtr->type->checkFunc)(segPtr, line);
6180 if ((segPtr->byte_count == 0) && (!segPtr->type->leftGravity)
6181 && (segPtr->next != NULL)
6182 && (segPtr->next->byte_count == 0)
6183 && (segPtr->next->type->leftGravity))
6185 g_error("gtk_text_btree_node_check_consistency: wrong segment order for gravity");
6187 if ((segPtr->next == NULL)
6188 && (segPtr->type != >k_text_char_type))
6190 g_error("gtk_text_btree_node_check_consistency: line ended with wrong type");
6193 num_chars += segPtr->char_count;
6202 for (childnode = node->children.node; childnode != NULL;
6203 childnode = childnode->next)
6205 if (childnode->parent != node)
6207 g_error("gtk_text_btree_node_check_consistency: GtkTextBTreeNode doesn't point to parent");
6209 if (childnode->level != (node->level-1))
6211 g_error("gtk_text_btree_node_check_consistency: level mismatch (%d %d)",
6212 node->level, childnode->level);
6214 gtk_text_btree_node_check_consistency (childnode);
6215 for (summary = childnode->summary; summary != NULL;
6216 summary = summary->next)
6218 for (summary2 = node->summary; ;
6219 summary2 = summary2->next)
6221 if (summary2 == NULL)
6223 if (summary->info->tag_root == node)
6227 g_error("gtk_text_btree_node_check_consistency: GtkTextBTreeNode tag \"%s\" not %s",
6228 summary->info->tag->name,
6229 "present in parent summaries");
6231 if (summary->info == summary2->info)
6238 num_lines += childnode->num_lines;
6239 num_chars += childnode->num_chars;
6242 if (num_children != node->num_children)
6244 g_error("gtk_text_btree_node_check_consistency: mismatch in num_children (%d %d)",
6245 num_children, node->num_children);
6247 if (num_lines != node->num_lines)
6249 g_error("gtk_text_btree_node_check_consistency: mismatch in num_lines (%d %d)",
6250 num_lines, node->num_lines);
6252 if (num_chars != node->num_chars)
6254 g_error("gtk_text_btree_node_check_consistency: mismatch in num_chars (%d %d)",
6255 num_chars, node->num_chars);
6258 for (summary = node->summary; summary != NULL;
6259 summary = summary->next)
6261 if (summary->info->toggle_count == summary->toggle_count)
6263 g_error("gtk_text_btree_node_check_consistency: found unpruned root for \"%s\"",
6264 summary->info->tag->name);
6267 if (node->level == 0)
6269 for (line = node->children.line; line != NULL;
6272 for (segPtr = line->segments; segPtr != NULL;
6273 segPtr = segPtr->next)
6275 if ((segPtr->type != >k_text_toggle_on_type)
6276 && (segPtr->type != >k_text_toggle_off_type))
6280 if (segPtr->body.toggle.info == summary->info)
6282 if (!segPtr->body.toggle.inNodeCounts)
6283 g_error ("Toggle segment not in the node counts");
6292 for (childnode = node->children.node;
6294 childnode = childnode->next)
6296 for (summary2 = childnode->summary;
6298 summary2 = summary2->next)
6300 if (summary2->info == summary->info)
6302 toggle_count += summary2->toggle_count;
6307 if (toggle_count != summary->toggle_count)
6309 g_error("gtk_text_btree_node_check_consistency: mismatch in toggle_count (%d %d)",
6310 toggle_count, summary->toggle_count);
6312 for (summary2 = summary->next; summary2 != NULL;
6313 summary2 = summary2->next)
6315 if (summary2->info == summary->info)
6317 g_error("gtk_text_btree_node_check_consistency: duplicated GtkTextBTreeNode tag: %s",
6318 summary->info->tag->name);
6325 listify_foreach(GtkTextTag *tag, gpointer user_data)
6327 GSList** listp = user_data;
6329 *listp = g_slist_prepend(*listp, tag);
6333 list_of_tags(GtkTextTagTable *table)
6335 GSList *list = NULL;
6337 gtk_text_tag_table_foreach(table, listify_foreach, &list);
6343 gtk_text_btree_check (GtkTextBTree *tree)
6346 GtkTextBTreeNode *node;
6348 GtkTextLineSegment *seg;
6350 GSList *taglist = NULL;
6352 GtkTextTagInfo *info;
6355 * Make sure that the tag toggle counts and the tag root pointers are OK.
6357 for (taglist = list_of_tags(tree->table);
6358 taglist != NULL ; taglist = taglist->next)
6360 tag = taglist->data;
6361 info = gtk_text_btree_get_existing_tag_info(tree, tag);
6364 node = info->tag_root;
6367 if (info->toggle_count != 0)
6369 g_error("gtk_text_btree_check found \"%s\" with toggles (%d) but no root",
6370 tag->name, info->toggle_count);
6372 continue; /* no ranges for the tag */
6374 else if (info->toggle_count == 0)
6376 g_error("gtk_text_btree_check found root for \"%s\" with no toggles",
6379 else if (info->toggle_count & 1)
6381 g_error("gtk_text_btree_check found odd toggle count for \"%s\" (%d)",
6382 tag->name, info->toggle_count);
6384 for (summary = node->summary; summary != NULL;
6385 summary = summary->next)
6387 if (summary->info->tag == tag)
6389 g_error("gtk_text_btree_check found root GtkTextBTreeNode with summary info");
6393 if (node->level > 0)
6395 for (node = node->children.node ; node != NULL ;
6398 for (summary = node->summary; summary != NULL;
6399 summary = summary->next)
6401 if (summary->info->tag == tag)
6403 count += summary->toggle_count;
6410 GtkTextLineSegmentClass * last = NULL;
6412 for (line = node->children.line ; line != NULL ;
6415 for (seg = line->segments; seg != NULL;
6418 if ((seg->type == >k_text_toggle_on_type ||
6419 seg->type == >k_text_toggle_off_type) &&
6420 seg->body.toggle.info->tag == tag)
6422 if (last == seg->type)
6423 g_error ("Two consecutive toggles on or off weren't merged");
6424 if (!seg->body.toggle.inNodeCounts)
6425 g_error ("Toggle segment not in the node counts");
6434 if (count != info->toggle_count)
6436 g_error("gtk_text_btree_check toggle_count (%d) wrong for \"%s\" should be (%d)",
6437 info->toggle_count, tag->name, count);
6442 g_slist_free(taglist);
6446 * Call a recursive procedure to do the main body of checks.
6449 node = tree->root_node;
6450 gtk_text_btree_node_check_consistency(tree->root_node);
6453 * Make sure that there are at least two lines in the text and
6454 * that the last line has no characters except a newline.
6457 if (node->num_lines < 2)
6459 g_error("gtk_text_btree_check: less than 2 lines in tree");
6461 if (node->num_chars < 2)
6463 g_error("gtk_text_btree_check: less than 2 chars in tree");
6465 while (node->level > 0)
6467 node = node->children.node;
6468 while (node->next != NULL)
6473 line = node->children.line;
6474 while (line->next != NULL)
6478 seg = line->segments;
6479 while ((seg->type == >k_text_toggle_off_type)
6480 || (seg->type == >k_text_right_mark_type)
6481 || (seg->type == >k_text_left_mark_type))
6484 * It's OK to toggle a tag off in the last line, but
6485 * not to start a new range. It's also OK to have marks
6491 if (seg->type != >k_text_char_type)
6493 g_error("gtk_text_btree_check: last line has bogus segment type");
6495 if (seg->next != NULL)
6497 g_error("gtk_text_btree_check: last line has too many segments");
6499 if (seg->byte_count != 1)
6501 g_error("gtk_text_btree_check: last line has wrong # characters: %d",
6504 if ((seg->body.chars[0] != '\n') || (seg->body.chars[1] != 0))
6506 g_error("gtk_text_btree_check: last line had bad value: %s",
6511 void gtk_text_btree_spew_line(GtkTextBTree* tree, GtkTextLine* line);
6512 void gtk_text_btree_spew_segment(GtkTextBTree* tree, GtkTextLineSegment* seg);
6513 void gtk_text_btree_spew_node(GtkTextBTreeNode *node, int indent);
6514 void gtk_text_btree_spew_line_short (GtkTextLine *line, int indent);
6517 gtk_text_btree_spew (GtkTextBTree *tree)
6522 printf("%d lines in tree %p\n",
6523 gtk_text_btree_line_count(tree), tree);
6525 line = gtk_text_btree_get_line(tree, 0, &real_line);
6527 while (line != NULL)
6529 gtk_text_btree_spew_line(tree, line);
6530 line = gtk_text_line_next(line);
6533 printf("=================== Tag information\n");
6538 list = tree->tag_infos;
6540 while (list != NULL)
6542 GtkTextTagInfo *info;
6546 printf (" tag `%s': root at %p, toggle count %d\n",
6547 info->tag->name, info->tag_root, info->toggle_count);
6549 list = g_slist_next (list);
6552 if (tree->tag_infos == NULL)
6554 printf (" (no tags in the tree)\n");
6558 printf("=================== Tree nodes\n");
6561 gtk_text_btree_spew_node (tree->root_node, 0);
6566 gtk_text_btree_spew_line_short (GtkTextLine *line, int indent)
6569 GtkTextLineSegment *seg;
6571 spaces = g_strnfill (indent, ' ');
6573 printf ("%sline %p chars %d bytes %d\n",
6575 gtk_text_line_char_count (line),
6576 gtk_text_line_byte_count (line));
6578 seg = line->segments;
6581 if (seg->type == >k_text_char_type)
6583 gchar* str = g_strndup(seg->body.chars, MIN (seg->byte_count, 10));
6592 printf("%s chars `%s'...\n", spaces, str);
6595 else if (seg->type == >k_text_right_mark_type)
6597 printf("%s right mark `%s' visible: %d\n",
6599 seg->body.mark.name,
6600 seg->body.mark.visible);
6602 else if (seg->type == >k_text_left_mark_type)
6604 printf("%s left mark `%s' visible: %d\n",
6606 seg->body.mark.name,
6607 seg->body.mark.visible);
6609 else if (seg->type == >k_text_toggle_on_type ||
6610 seg->type == >k_text_toggle_off_type)
6612 printf("%s tag `%s' %s\n",
6613 spaces, seg->body.toggle.info->tag->name,
6614 seg->type == >k_text_toggle_off_type ? "off" : "on");
6624 gtk_text_btree_spew_node(GtkTextBTreeNode *node, int indent)
6627 GtkTextBTreeNode *iter;
6630 spaces = g_strnfill (indent, ' ');
6632 printf ("%snode %p level %d children %d lines %d chars %d\n",
6633 spaces, node, node->level,
6634 node->num_children, node->num_lines, node->num_chars);
6639 printf ("%s %d toggles of `%s' below this node\n",
6640 spaces, s->toggle_count, s->info->tag->name);
6646 if (node->level > 0)
6648 iter = node->children.node;
6649 while (iter != NULL)
6651 gtk_text_btree_spew_node (iter, indent + 2);
6658 GtkTextLine *line = node->children.line;
6659 while (line != NULL)
6661 gtk_text_btree_spew_line_short (line, indent + 2);
6669 gtk_text_btree_spew_line(GtkTextBTree* tree, GtkTextLine* line)
6671 GtkTextLineSegment * seg;
6673 printf("%4d| line: %p parent: %p next: %p\n",
6674 gtk_text_line_get_number(line), line, line->parent, line->next);
6676 seg = line->segments;
6680 gtk_text_btree_spew_segment(tree, seg);
6686 gtk_text_btree_spew_segment(GtkTextBTree* tree, GtkTextLineSegment * seg)
6688 printf(" segment: %p type: %s bytes: %d chars: %d\n",
6689 seg, seg->type->name, seg->byte_count, seg->char_count);
6691 if (seg->type == >k_text_char_type)
6693 gchar* str = g_strndup(seg->body.chars, seg->byte_count);
6694 printf(" `%s'\n", str);
6697 else if (seg->type == >k_text_right_mark_type)
6699 printf(" right mark `%s' visible: %d not_deleteable: %d\n",
6700 seg->body.mark.name,
6701 seg->body.mark.visible,
6702 seg->body.mark.not_deleteable);
6704 else if (seg->type == >k_text_left_mark_type)
6706 printf(" left mark `%s' visible: %d not_deleteable: %d\n",
6707 seg->body.mark.name,
6708 seg->body.mark.visible,
6709 seg->body.mark.not_deleteable);
6711 else if (seg->type == >k_text_toggle_on_type ||
6712 seg->type == >k_text_toggle_off_type)
6714 printf(" tag `%s' priority %d\n",
6715 seg->body.toggle.info->tag->name,
6716 seg->body.toggle.info->tag->priority);