1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
// Copyright (c) AlphaSierraPapa for the SharpDevelop Team (for details please see \doc\copyright.txt)
// This code is distributed under the GNU LGPL (for details please see \doc\license.txt)
using System;
namespace Tango.Scripting.Editors.Document
{
using LineNode = DocumentLine;
// A tree node in the document line tree.
// For the purpose of the invariants, "children", "descendents", "siblings" etc. include the DocumentLine object,
// it is treated as a third child node between left and right.
// Originally, this was a separate class, with a reference to the documentLine. The documentLine had a reference
// back to the node. To save memory, the same object is used for both the documentLine and the line node.
// This saves 16 bytes per line (8 byte object overhead + two pointers).
// sealed class LineNode
// {
// internal readonly DocumentLine documentLine;
partial class DocumentLine
{
internal DocumentLine left, right, parent;
internal bool color;
// optimization note: I tried packing color and isDeleted into a single byte field, but that
// actually increased the memory requirements. The JIT packs two bools and a byte (delimiterSize)
// into a single DWORD, but two bytes get each their own DWORD. Three bytes end up in the same DWORD, so
// apparently the JIT only optimizes for memory when there are at least three small fields.
// Currently, DocumentLine takes 36 bytes on x86 (8 byte object overhead, 3 pointers, 3 ints, and another DWORD
// for the small fields).
// TODO: a possible optimization would be to combine 'totalLength' and the small fields into a single uint.
// delimiterSize takes only two bits, the two bools take another two bits; so there's still
// 28 bits left for totalLength. 268435455 characters per line should be enough for everyone :)
/// <summary>
/// Resets the line to enable its reuse after a document rebuild.
/// </summary>
internal void ResetLine()
{
totalLength = delimiterLength = 0;
isDeleted = color = false;
left = right = parent = null;
}
internal LineNode InitLineNode()
{
this.nodeTotalCount = 1;
this.nodeTotalLength = this.TotalLength;
return this;
}
internal LineNode LeftMost {
get {
LineNode node = this;
while (node.left != null)
node = node.left;
return node;
}
}
internal LineNode RightMost {
get {
LineNode node = this;
while (node.right != null)
node = node.right;
return node;
}
}
/// <summary>
/// The number of lines in this node and its child nodes.
/// Invariant:
/// nodeTotalCount = 1 + left.nodeTotalCount + right.nodeTotalCount
/// </summary>
internal int nodeTotalCount;
/// <summary>
/// The total text length of this node and its child nodes.
/// Invariant:
/// nodeTotalLength = left.nodeTotalLength + documentLine.TotalLength + right.nodeTotalLength
/// </summary>
internal int nodeTotalLength;
}
}
|
