1/*
2 * Copyright 2011, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include "SizeIndex.h"
8
9#include <new>
10
11#include <TypeConstants.h>
12
13#include <util/SinglyLinkedList.h>
14
15#include "DebugSupport.h"
16#include "IndexImpl.h"
17#include "Node.h"
18#include "TwoKeyAVLTree.h"
19#include "Volume.h"
20
21
22// #pragma mark - SizeIndexPrimaryKey
23
24
25class SizeIndexPrimaryKey {
26public:
27	SizeIndexPrimaryKey(Node* node, off_t size)
28		:
29		node(node),
30		size(size)
31	{
32	}
33
34	SizeIndexPrimaryKey(Node* node)
35		:
36		node(node),
37		size(node->FileSize())
38	{
39	}
40
41	SizeIndexPrimaryKey(off_t size)
42		:
43		node(NULL),
44		size(size)
45	{
46	}
47
48	Node*	node;
49	off_t	size;
50};
51
52
53// #pragma mark - SizeIndexGetPrimaryKey
54
55
56class SizeIndexGetPrimaryKey {
57public:
58	inline SizeIndexPrimaryKey operator()(Node* a)
59	{
60		return SizeIndexPrimaryKey(a);
61	}
62
63	inline SizeIndexPrimaryKey operator()(Node* a) const
64	{
65		return SizeIndexPrimaryKey(a);
66	}
67};
68
69
70// #pragma mark - SizeIndexPrimaryKeyCompare
71
72
73class SizeIndexPrimaryKeyCompare {
74public:
75	inline int operator()(const SizeIndexPrimaryKey &a,
76		const SizeIndexPrimaryKey &b) const
77	{
78		if (a.node != NULL && a.node == b.node)
79			return 0;
80		if (a.size < b.size)
81			return -1;
82		if (a.size > b.size)
83			return 1;
84		return 0;
85	}
86};
87
88
89// #pragma mark - NodeTree
90
91
92typedef TwoKeyAVLTree<Node*, SizeIndexPrimaryKey, SizeIndexPrimaryKeyCompare,
93	SizeIndexGetPrimaryKey> _NodeTree;
94class SizeIndex::NodeTree : public _NodeTree {};
95
96
97// #pragma mark - IteratorList
98
99
100class SizeIndex::IteratorList : public SinglyLinkedList<Iterator> {};
101
102
103// #pragma mark - Iterator
104
105
106struct SizeIndex::IteratorPolicy {
107	typedef SizeIndex										Index;
108	typedef off_t											Value;
109	typedef SizeIndex::NodeTree								NodeTree;
110	typedef GenericIndexIteratorTreePolicy<IteratorPolicy>	TreePolicy;
111
112	static NodeTree* GetNodeTree(Index* index)
113	{
114		return index->fNodes;
115	}
116
117	static void GetNodeValue(Node* node, void* buffer, size_t* _keyLength)
118	{
119		*(off_t*)buffer = node->FileSize();
120		*_keyLength = sizeof(off_t);
121	}
122};
123
124
125class SizeIndex::Iterator : public GenericIndexIterator<IteratorPolicy>,
126	public SinglyLinkedListLinkImpl<Iterator> {
127public:
128	virtual	void				NodeChanged(Node* node, uint32 statFields,
129									const OldNodeAttributes& oldAttributes);
130};
131
132
133// #pragma mark - SizeIndex
134
135
136SizeIndex::SizeIndex()
137	:
138	Index(),
139	fNodes(NULL),
140	fIteratorsToUpdate(NULL)
141{
142}
143
144
145SizeIndex::~SizeIndex()
146{
147	if (IsListening())
148		fVolume->RemoveNodeListener(this);
149
150	ASSERT(fIteratorsToUpdate->IsEmpty());
151
152	delete fIteratorsToUpdate;
153	delete fNodes;
154}
155
156
157status_t
158SizeIndex::Init(Volume* volume)
159{
160	status_t error = Index::Init(volume, "size", B_INT64_TYPE, true,
161		sizeof(off_t));
162	if (error != B_OK)
163		return error;
164
165	fVolume->AddNodeListener(this, NULL);
166
167	fNodes = new(std::nothrow) NodeTree;
168	fIteratorsToUpdate = new(std::nothrow) IteratorList;
169	if (fNodes == NULL || fIteratorsToUpdate == NULL)
170		return B_NO_MEMORY;
171
172	return B_OK;
173}
174
175
176int32
177SizeIndex::CountEntries() const
178{
179	return fNodes->CountItems();
180}
181
182
183void
184SizeIndex::NodeAdded(Node* node)
185{
186	fNodes->Insert(node);
187}
188
189
190void
191SizeIndex::NodeRemoved(Node* node)
192{
193	fNodes->Remove(node, node);
194}
195
196
197void
198SizeIndex::NodeChanged(Node* node, uint32 statFields,
199	const OldNodeAttributes& oldAttributes)
200{
201	IteratorList iterators;
202	iterators.MoveFrom(fIteratorsToUpdate);
203
204	off_t oldSize = oldAttributes.FileSize();
205	off_t newSize = node->FileSize();
206	if (newSize == oldSize)
207		return;
208
209	NodeTree::Iterator nodeIterator;
210	Node** foundNode = fNodes->Find(SizeIndexPrimaryKey(node, oldSize), node,
211		&nodeIterator);
212
213	if (foundNode == NULL || *foundNode != node)
214		return;
215
216	// move the iterators that point to the node to the previous node
217	for (IteratorList::Iterator it = iterators.GetIterator();
218			Iterator* iterator = it.Next();) {
219		iterator->NodeChangeBegin(node);
220	}
221
222	// remove and re-insert the node
223	nodeIterator.Remove();
224	if (fNodes->Insert(node) != B_OK) {
225		fIteratorsToUpdate->MakeEmpty();
226		return;
227	}
228
229	// Move the iterators to the next node again. If the node hasn't changed
230	// its place, they will point to it again, otherwise to the node originally
231	// succeeding it.
232	for (IteratorList::Iterator it = iterators.GetIterator();
233			Iterator* iterator = it.Next();) {
234		iterator->NodeChangeEnd(node);
235	}
236
237	// update live queries
238	fVolume->UpdateLiveQueries(node, Name(), Type(),
239		(const uint8*)&oldSize, sizeof(oldSize), (const uint8*)&newSize,
240		sizeof(newSize));
241}
242
243
244AbstractIndexIterator*
245SizeIndex::InternalGetIterator()
246{
247	Iterator* iterator = new(std::nothrow) Iterator;
248	if (iterator != NULL) {
249		if (!iterator->SetTo(this, 0, true)) {
250			delete iterator;
251			iterator = NULL;
252		}
253	}
254	return iterator;
255}
256
257
258AbstractIndexIterator*
259SizeIndex::InternalFind(const void* key, size_t length)
260{
261	if (length != sizeof(off_t))
262		return NULL;
263	Iterator* iterator = new(std::nothrow) Iterator;
264	if (iterator != NULL) {
265		if (!iterator->SetTo(this, *(const off_t*)key)) {
266			delete iterator;
267			iterator = NULL;
268		}
269	}
270	return iterator;
271}
272
273
274void
275SizeIndex::_AddIteratorToUpdate(Iterator* iterator)
276{
277	fIteratorsToUpdate->Add(iterator);
278}
279
280
281// #pragma mark - Iterator
282
283
284void
285SizeIndex::Iterator::NodeChanged(Node* node, uint32 statFields,
286	const OldNodeAttributes& oldAttributes)
287{
288	fIndex->_AddIteratorToUpdate(this);
289}
290