Mercurial > dovecot > original-hg > dovecot-1.2

annotate doc/thread-refs.txt @ 7952:04a3be30e5a6 HEAD

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Thread index fixes and optimizations.
author Timo Sirainen <tss@iki.fi>
date Thu, 26 Jun 2008 19:11:56 +0300
parents 524b4acad38b
children 7760a30a5f7e
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
7800
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
1 Optimistic incremental THREAD=REFERENCES
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
2
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
3 Step (1) is the slowest stage for building a THREAD=REFERENCES tree. If its
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
4 result tree is permanently saved, the following thread builds can be based
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
5 on it by updating the tree incrementally.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
6
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
7 Adding new messages to the tree is simple: simply follow the normal rules
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
8 as when building a new tree from scratch. Expunging messages gets more
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
9 problematic though.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
10
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
11 Each node in the tree keeps a "link reference count" which specifies how
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
12 many messages contain a "this message" -> "parent message" reference. The
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
13 first reference is usually added by the message's own References: or
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
14 In-Reply-To: header and the latter references are added by References:
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
15 headers. This link refcount must be updated when adding and expunging
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
16 messages. When the link refcount drops to zero, the message becomes a root.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
17 The link refcount doesn't tell much about the number of children the node
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
18 has, because References: headers may reference any number of its ancestors.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
19
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
20 The optimistic approach assumes that usually there are no problematic
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
21 links. In such case expunging a message simply updates the link refcounts
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
22 and marks the message's node as expunged. Expunged messages may still act
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
23 as dummy nodes. The node may be removed only after there are no nodes which
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
24 point to it.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
25
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
26 Problematic links are handled by marking nodes affected by them. If such a
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
27 node is expunged or its link is unreferenced, the thread tree must be
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
28 rebuilt. This is assumed to be a rarely occurring event. The problematic
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
29 cases are:
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
30
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
31 1) Duplicate Message-ID: headers. If the first message having it is
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
32 expunged, the thread tree must be rebuilt.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
33
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
34 2) Message-ID loops. If a message referencing the looping path gets
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
35 expunged, the loop may break and the thread tree must be rebuilt. Because
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
36 it can't be determined easily which loops get broken by which expunges,
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
37 this case can be handled in a bit easier way: When detecting a loop between
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
38 parent and child, rebuild the tree if any link between the parent and child
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
39 gets unreferenced.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
40
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
41 3) A message changes its parent because an earlier message's References:
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
42 header contained a different link. If the message gets expunged, the thread
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
43 tree must be rebuilt to get the original parent back.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
44
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
45 4) A link in a message's References: header is ignored, because the
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
46 referenced child already specified a different parent to itself. If the
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
47 message gets expunged, the thread tree must be rebuilt to determine its new
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
48 parent.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
49
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
50 5) A link in a message's References: header is ignored, because an earlier
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
51 message's References: header already specified a different link. If the
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
52 earlier message gets expunged, the parent may change. The earlier message
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
53 could be found out quickly by keeping some extra state (or with a slow
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
54 scan), but since this is assumed to be a rare problem, there's an easier
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
55 (but less specific) way to handle this: Rebuild the tree if a link to the
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
56 child node is unreferenced (or alternatively if a link to the original
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
57 parent node is unreferenced, but it probably happens more often).
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
58
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
59 Pseudocode:
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
60
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
61 node {
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
62 parent: Pointer to parent node. Children pointers aren't required.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
63 uid: Message's UID (0 = expunged or never even existed)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
64
7952
04a3be30e5a6 Thread index fixes and optimizations.
Timo Sirainen <tss@iki.fi>
parents: 7800
diff changeset
65 parent_link_refcount: Number of messages containing "this message" -> "parent
04a3be30e5a6 Thread index fixes and optimizations.
Timo Sirainen <tss@iki.fi>
parents: 7800
diff changeset
66 message" link, i.e. "number of links to parent node". However since parents
04a3be30e5a6 Thread index fixes and optimizations.
Timo Sirainen <tss@iki.fi>
parents: 7800
diff changeset
67 can change, not all of these references might be from our current child
04a3be30e5a6 Thread index fixes and optimizations.
Timo Sirainen <tss@iki.fi>
parents: 7800
diff changeset
68 nodes. When this refcount reaches 0, it means we must detach from our
04a3be30e5a6 Thread index fixes and optimizations.
Timo Sirainen <tss@iki.fi>
parents: 7800
diff changeset
69 parent.
7800
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
70 expunge_rebuilds: If this message gets expunged, rebuild the thread tree.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
71 parent_unref_rebuilds: If a link between this node and its child gets
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
72 unreferenced, rebuild the thread tree.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
73 }
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
74
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
75 link_reference(parent_node, child_node)
7952
04a3be30e5a6 Thread index fixes and optimizations.
Timo Sirainen <tss@iki.fi>
parents: 7800
diff changeset
76 child_node.parent_link_refcount++
7800
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
77 if is_ancestor(child_node, parent_node)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
78 // child_node is an ancestor of parent_node. Adding child_node ->
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
79 // parent_node would introduce a loop. If any messages referencing the
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
80 // path between parent_node's parent and child_node get expunged, we
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
81 // have to rebuild the tree because the loop might break. For example:
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
82 // #1: a -> b (a.ref=1, b.ref=1)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
83 // #2: b -> a (a.ref=2, b.ref=2)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
84 // #3: c -> a -> b (a.ref=3, b.ref=3, c.ref=1)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
85 // Expunging #3 wouldn't break the loop, but expunging #1 would.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
86 for node in nodes[parent_node.parent .. child_node]
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
87 node.parent_unref_rebuilds = true
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
88 else if child_node.parent == parent_node
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
89 // The same link already exists
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
90 else
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
91 // Set parent_node as child_node's parent
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
92 if child_node.parent == NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
93 child_node.parent = parent_node
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
94 else
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
95 // Conflicting parent already exists, keep the original.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
96 // We get here only when handling References: header.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
97 if child_node.uid != 0
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
98 // We've already seen this message. It specifies its own parent and
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
99 // it doesn't matter what any other reference says. The only way its
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
100 // parent can change is if the message itself gets expunged.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
101 child_node.expunge_rebuilds = true
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
102 else
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
103 // Message doesn't exist, so it was one of the node's children
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
104 // that created the original reference. If that reference gets
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
105 // dropped, the parent is changed. We could catch this in one of
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
106 // several ways:
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
107 // a) Link to original parent node gets unreferenced
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
108 // b) Link to this node gets unreferenced
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
109 // c) Any of the child nodes gets expunged
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
110 // b) is probably the least likely to happen, so use it
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
111 child_node.parent_unref_rebuilds = true
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
112
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
113 thread_add_msg(uid)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
114 // get the Message-IDs as specified by the thread spec
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
115 (msgid, parent_msgid, references) = message_get_thread_headers(uid)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
116
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
117 if msgid != NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
118 if nodes[msgid].uid == 0
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
119 nodes[msgid].uid = uid
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
120 else
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
121 // duplicate Message-ID. if the original ever gets expunged,
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
122 // rebuild the thread tree
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
123 nodes[msgid].expunge_rebuilds = true
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
124 msgid = NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
125
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
126 if msgid == NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
127 msgid = get_unique_msg_id()
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
128
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
129 node = nodes[msgid]
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
130 if node.parent != NIL and
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
131 (parent_msgid == NIL or node.parent.msgid != parent_msgid)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
132 // Conflicting parent, remove it. If this message gets expunged, we have
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
133 // to revert back to the original parent.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
134 node.parent = NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
135 node.expunge_rebuilds = true
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
136
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
137 if parent_msgid != NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
138 link_reference(nodes[parent_msgid], node)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
139
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
140 // go through References (skipping the last one)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
141 for (parent_msgid, child_msgid) in references
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
142 link_reference(nodes[parent_msgid], nodes[child_msgid])
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
143
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
144 unref_link(parent, child)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
145 if parent.parent_unref_rebuilds
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
146 return false
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
147
7952
04a3be30e5a6 Thread index fixes and optimizations.
Timo Sirainen <tss@iki.fi>
parents: 7800
diff changeset
148 child.parent_link_refcount--
04a3be30e5a6 Thread index fixes and optimizations.
Timo Sirainen <tss@iki.fi>
parents: 7800
diff changeset
149 if child.parent_link_refcount == 0
7800
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
150 child.parent = NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
151 return true
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
152
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
153 // returns false if thread tree needs to be rebuilt
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
154 thread_expunge_msg(uid)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
155 // get the Message-IDs as specified by the thread spec
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
156 (msgid, in_reply_to_msgid, references) = message_get_thread_headers(uid)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
157
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
158 node = nodes[msgid]
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
159 if node.uid != uid
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
160 // Removing a duplicate Message-ID
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
161 return false
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
162
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
163 if node.expunge_rebuilds
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
164 return false
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
165
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
166 if parent_msgid != NIL and
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
167 not unref_link(nodes[parent_msgid], nodes[child_msgid])
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
168 return false
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
169
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
170 if references != NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
171 // go through References
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
172 for (parent_msgid, child_msgid) in references
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
173 if not unref_link(nodes[parent_msgid], nodes[child_msgid])
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
174 return false
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
175 last_parent_msgid = references.last
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
176 else if in_reply_to_msgid != NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
177 last_parent_msgid = in_reply_to_msgid
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
178
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
179 if last_parent_msgid != NIL and
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
180 not unref_link(nodes[last_parent_msgid], node)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
181 return false
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
182
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
183 // mark this node as expunged
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
184 node.uid = 0
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
185 return true
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
186
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
187 thread_iterate()
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
188 root_nodes = []
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
189 referenced = []
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
190 children = [][]
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
191 // Steps (2) and (3)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
192 for node in nodes
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
193 if node.parent != NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
194 root_nodes[] = node
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
195 else
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
196 referenced[node.parent] = true
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
197 if node.uid != 0
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
198 // Find the node's first non-dummy parent and add the node as its child.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
199 // If there are no non-dummy parents, add it as the highest dummy's
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
200 // child.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
201 nondummy_parent = node.parent
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
202 while nondummy_parent.uid == 0 and nondummy_parent.parent != NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
203 nondummy_parent = nondummy_parent.parent
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
204 children[nondummy_parent][] = node
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
205
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
206 for node in root_nodes
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
207 if node.uid == 0
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
208 if children[node] == NIL
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
209 // remove dummy roots that have no children.
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
210 delete(node)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
211 else if count(children[node]) == 1
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
212 // dummy root has a single child, replace the root with its child
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
213 node = children[node]
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
214
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
215 for node in nodes
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
216 if node.uid == 0 and !referenced[node]
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
217 free(node)
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
218
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
219 // root_nodes and children now contain a tree equivalent to a tree built by
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
220 // THREAD=REFERENCES specification steps (1)-(3). The rest of the steps
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
221 // can be performed using them. Note that node.parent should not (and need
524b4acad38b Added documentation about how thread indexes work.
Timo Sirainen <tss@iki.fi>
parents:
diff changeset
222 // not) be used because it points its parent before steps (2) and (3).