dovecot/original-hg/dovecot-1.2: doc/thread-refs.txt annotate

annotate doc/thread-refs.txt @ 9301:85e39b7710ee HEAD

autocreate: Fixed autosubscribing to mailboxes in subscriptions=no namespaces. Also log autosubscribe failures if mail_debug=yes.

author	Timo Sirainen <tss@iki.fi>
date	Sun, 09 Aug 2009 14:55:11 -0400
parents	b296beccb70e
children

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
7963 7760a30a5f7e Updated thread index documentation. Timo Sirainen <tss@iki.fi> parents: 7952 diff changeset	12 many messages contain a "this message" -> "parent message" reference
7760a30a5f7e Updated thread index documentation. Timo Sirainen <tss@iki.fi> parents: 7952 diff changeset	13 (number of links to parent node). The first reference is usually added by
7760a30a5f7e Updated thread index documentation. Timo Sirainen <tss@iki.fi> parents: 7952 diff changeset	14 the message's own References: or In-Reply-To: header and the latter
7760a30a5f7e Updated thread index documentation. Timo Sirainen <tss@iki.fi> parents: 7952 diff changeset	15 references are added by References: headers. This link refcount must be
7760a30a5f7e Updated thread index documentation. Timo Sirainen <tss@iki.fi> parents: 7952 diff changeset	16 updated when adding and expunging messages. When the link refcount drops to
7760a30a5f7e Updated thread index documentation. Timo Sirainen <tss@iki.fi> parents: 7952 diff changeset	17 zero, the message becomes a root. The link refcount doesn't tell much about
7760a30a5f7e Updated thread index documentation. Timo Sirainen <tss@iki.fi> parents: 7952 diff changeset	18 the number of children the node has, because References: headers may
7760a30a5f7e Updated thread index documentation. Timo Sirainen <tss@iki.fi> parents: 7952 diff changeset	19 reference any number of its ancestors.
7800 524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	20
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	21 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	22 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	23 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	24 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	25 point to it.
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	26
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	27 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	28 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	29 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	30 cases are:
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	31
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	32 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	33 expunged, the thread tree must be rebuilt.
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	34
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	35 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	36 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	37 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	38 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	39 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	40 gets unreferenced.
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	41
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	42 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	43 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	44 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	45
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	46 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	47 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	48 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	49 parent.
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	50
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	51 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	52 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	53 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	54 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	55 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	56 (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	57 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	58 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	59
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	60 Pseudocode:
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	61
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	62 node {
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	63 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	64 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	65
7952 04a3be30e5a6 Thread index fixes and optimizations. Timo Sirainen <tss@iki.fi> parents: 7800 diff changeset	66 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	67 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	68 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	69 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	70 parent.
7800 524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	71 expunge_rebuilds: If this message gets expunged, rebuild the thread tree.
8145 b296beccb70e Minor cleanup to thread indexing document. Timo Sirainen <tss@iki.fi> parents: 7963 diff changeset	72 child_unref_rebuilds: If a link between this node and its child gets
7800 524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	73 unreferenced, rebuild the thread tree.
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
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	76 link_reference(parent_node, child_node)
7952 04a3be30e5a6 Thread index fixes and optimizations. Timo Sirainen <tss@iki.fi> parents: 7800 diff changeset	77 child_node.parent_link_refcount++
7800 524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	78 if is_ancestor(child_node, parent_node)
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	79 // 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	80 // 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	81 // 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	82 // 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	83 // #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	84 // #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	85 // #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	86 // 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	87 for node in nodes[parent_node.parent .. child_node]
8145 b296beccb70e Minor cleanup to thread indexing document. Timo Sirainen <tss@iki.fi> parents: 7963 diff changeset	88 node.child_unref_rebuilds = true
7800 524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	89 else if child_node.parent == parent_node
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	90 // The same link already exists
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	91 else
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	92 // Set parent_node as child_node's parent
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	93 if child_node.parent == NIL
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	94 child_node.parent = parent_node
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	95 else
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	96 // Conflicting parent already exists, keep the original.
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	97 // We get here only when handling References: header.
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	98 if child_node.uid != 0
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	99 // 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	100 // 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	101 // 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	102 child_node.expunge_rebuilds = true
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	103 else
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	104 // 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	105 // 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	106 // 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	107 // several ways:
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	108 // a) Link to original parent node gets unreferenced
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	109 // b) Link to this node gets unreferenced
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	110 // c) Any of the child nodes gets expunged
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	111 // b) is probably the least likely to happen, so use it
8145 b296beccb70e Minor cleanup to thread indexing document. Timo Sirainen <tss@iki.fi> parents: 7963 diff changeset	112 child_node.child_unref_rebuilds = true
7800 524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	113
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	114 thread_add_msg(uid)
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	115 // 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	116 (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	117
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	118 if msgid != NIL
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	119 if nodes[msgid].uid == 0
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	120 nodes[msgid].uid = uid
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	121 else
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	122 // 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	123 // rebuild the thread tree
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	124 nodes[msgid].expunge_rebuilds = true
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	125 msgid = NIL
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	126
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	127 if msgid == NIL
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	128 msgid = get_unique_msg_id()
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	129
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	130 node = nodes[msgid]
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	131 if node.parent != NIL and
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	132 (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	133 // 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	134 // to revert back to the original parent.
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	135 node.parent = NIL
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	136 node.expunge_rebuilds = true
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	137
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	138 if parent_msgid != NIL
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	139 link_reference(nodes[parent_msgid], node)
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	140
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	141 // go through References (skipping the last one)
7963 7760a30a5f7e Updated thread index documentation. Timo Sirainen <tss@iki.fi> parents: 7952 diff changeset	142 for (ref_parent, ref_child) in references
7760a30a5f7e Updated thread index documentation. Timo Sirainen <tss@iki.fi> parents: 7952 diff changeset	143 link_reference(nodes[ref_parent], nodes[ref_child])
7800 524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	144
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	145 unref_link(parent, child)
8145 b296beccb70e Minor cleanup to thread indexing document. Timo Sirainen <tss@iki.fi> parents: 7963 diff changeset	146 if parent.child_unref_rebuilds
7800 524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	147 return false
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	148
7952 04a3be30e5a6 Thread index fixes and optimizations. Timo Sirainen <tss@iki.fi> parents: 7800 diff changeset	149 child.parent_link_refcount--
04a3be30e5a6 Thread index fixes and optimizations. Timo Sirainen <tss@iki.fi> parents: 7800 diff changeset	150 if child.parent_link_refcount == 0
7800 524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	151 child.parent = NIL
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	152 return true
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	153
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	154 // 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	155 thread_expunge_msg(uid)
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	156 // 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	157 (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	158
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	159 node = nodes[msgid]
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	160 if node.uid != uid
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	161 // Removing a duplicate Message-ID
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	162 return false
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	163
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	164 if node.expunge_rebuilds
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	165 return false
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	166
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	167 if parent_msgid != NIL and
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	168 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	169 return false
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	170
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	171 if references != NIL
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	172 // go through References
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	173 for (parent_msgid, child_msgid) in references
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	174 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	175 return false
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	176 last_parent_msgid = references.last
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	177 else if in_reply_to_msgid != NIL
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	178 last_parent_msgid = in_reply_to_msgid
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	179
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	180 if last_parent_msgid != NIL and
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	181 not unref_link(nodes[last_parent_msgid], node)
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	182 return false
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	183
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	184 // mark this node as expunged
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	185 node.uid = 0
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	186 return true
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	187
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	188 thread_iterate()
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	189 root_nodes = []
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	190 referenced = []
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	191 children = [][]
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	192 // Steps (2) and (3)
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	193 for node in nodes
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	194 if node.parent != NIL
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	195 root_nodes[] = node
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	196 else
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	197 referenced[node.parent] = true
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	198 if node.uid != 0
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	199 // 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	200 // 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	201 // child.
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	202 nondummy_parent = node.parent
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	203 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	204 nondummy_parent = nondummy_parent.parent
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	205 children[nondummy_parent][] = node
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	206
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	207 for node in root_nodes
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	208 if node.uid == 0
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	209 if children[node] == NIL
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	210 // remove dummy roots that have no children.
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	211 delete(node)
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	212 else if count(children[node]) == 1
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	213 // 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	214 node = children[node]
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	215
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	216 for node in nodes
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	217 if node.uid == 0 and !referenced[node]
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	218 free(node)
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	219
524b4acad38b Added documentation about how thread indexes work. Timo Sirainen <tss@iki.fi> parents: diff changeset	220 // 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	221 // 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	222 // 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	223 // not) be used because it points its parent before steps (2) and (3).

Mercurial > dovecot > original-hg > dovecot-1.2

annotate doc/thread-refs.txt @ 9301:85e39b7710ee HEAD