1/*
2 * Copyright 2011, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#include "AttributeIndex.h"
8
9#include <new>
10
11#include <TypeConstants.h>
12
13#include <util/AVLTree.h>
14#include <util/SinglyLinkedList.h>
15
16#include <file_systems/QueryParserUtils.h>
17
18#include "AttributeIndexer.h"
19#include "DebugSupport.h"
20#include "IndexImpl.h"
21#include "Node.h"
22#include "Volume.h"
23
24
25struct AttributeIndexTreeKey {
26	const void*	data;
27	size_t		length;
28
29	AttributeIndexTreeKey()
30	{
31	}
32
33	AttributeIndexTreeKey(const void* data, size_t length)
34		:
35		data(data),
36		length(length)
37	{
38	}
39};
40
41
42struct AttributeIndexTreeValue : AVLTreeNode {
43	Node*					node;
44	IndexedAttributeOwner*	owner;
45	void*					attributeCookie;
46	size_t					length;
47	uint8					data[0];
48
49	static AttributeIndexTreeValue* Create(IndexedAttributeOwner* owner,
50		void* attributeCookie, size_t length)
51	{
52		AttributeIndexTreeValue* self = (AttributeIndexTreeValue*)malloc(
53			sizeof(AttributeIndexTreeValue) + length);
54		if (self == NULL)
55			return NULL;
56
57		self->owner = owner;
58		self->attributeCookie = attributeCookie;
59		self->length = length;
60		return self;
61	}
62
63	void Delete()
64	{
65		free(this);
66	}
67};
68
69
70struct AttributeIndex::TreeDefinition {
71	typedef TreeKey		Key;
72	typedef TreeValue	Value;
73
74	TreeDefinition(uint32 type)
75		:
76		fType(type)
77	{
78	}
79
80	AVLTreeNode* GetAVLTreeNode(Value* value) const
81	{
82		return value;
83	}
84
85	Value* GetValue(AVLTreeNode* node) const
86	{
87		return static_cast<Value*>(node);
88	}
89
90	int Compare(const Key& a, const Value* b) const
91	{
92		return QueryParser::compareKeys(fType, a.data, a.length, b->data,
93			b->length);
94	}
95
96	int Compare(const Value* a, const Value* b) const
97	{
98		return QueryParser::compareKeys(fType, a->data, a->length, b->data,
99			b->length);
100	}
101
102private:
103	uint32	fType;
104};
105
106
107// #pragma mark - NodeTree
108
109
110struct AttributeIndex::NodeTree : public AVLTree<TreeDefinition> {
111	typedef TreeValue	Node;
112
113	NodeTree(const TreeDefinition& definition)
114		:
115		AVLTree<TreeDefinition>(definition)
116	{
117	}
118};
119
120
121// #pragma mark - IteratorList
122
123
124class AttributeIndex::IteratorList : public SinglyLinkedList<Iterator> {};
125
126
127// #pragma mark - Iterator
128
129
130struct AttributeIndex::IteratorPolicy {
131	typedef AttributeIndex				Index;
132	typedef TreeKey						Value;
133	typedef AttributeIndex::NodeTree	NodeTree;
134	typedef TreeValue					TreeNode;
135	typedef IteratorPolicy				TreePolicy;
136
137	static NodeTree* GetNodeTree(Index* index)
138	{
139		return index->fNodes;
140	}
141
142	static void GetTreeNodeValue(TreeNode* node, void* buffer,
143		size_t* _keyLength)
144	{
145		if (node->length > 0)
146			memcpy(buffer, node->data, node->length);
147		*_keyLength = node->length;
148	}
149
150	static Node* GetNode(TreeNode* treeNode)
151	{
152		return treeNode->node;
153	}
154
155	static TreeNode* GetFirstTreeNode(Index* index)
156	{
157		return index->fNodes->GetIterator().Next();
158	}
159
160	static TreeNode* FindClosestTreeNode(Index* index, const Value& value)
161	{
162		return index->fNodes->FindClosest(value, false);
163	}
164};
165
166
167class AttributeIndex::Iterator : public GenericIndexIterator<IteratorPolicy>,
168	public SinglyLinkedListLinkImpl<Iterator> {
169public:
170	virtual	void				NodeChanged(Node* node, uint32 statFields,
171									const OldNodeAttributes& oldAttributes);
172};
173
174
175// #pragma mark - AttributeIndexer
176
177
178AttributeIndexer::AttributeIndexer(AttributeIndex* index)
179	:
180	fIndex(index),
181	fIndexName(index->Name()),
182	fIndexType(index->Type()),
183	fCookie(NULL)
184{
185}
186
187
188AttributeIndexer::~AttributeIndexer()
189{
190}
191
192
193status_t
194AttributeIndexer::CreateCookie(IndexedAttributeOwner* owner,
195	void* attributeCookie, uint32 attributeType, size_t attributeSize,
196	void*& _data, size_t& _toRead)
197{
198	// check the attribute type and size
199	if (attributeType != fIndexType)
200		return B_ERROR;
201
202	if (fIndex->HasFixedKeyLength()) {
203		if (attributeSize != fIndex->KeyLength())
204			return B_ERROR;
205	} else if (attributeSize > kMaxIndexKeyLength)
206		attributeSize = kMaxIndexKeyLength;
207
208	// create the tree value
209	fCookie = AttributeIndexTreeValue::Create(owner, attributeCookie,
210		attributeSize);
211	if (fCookie == NULL)
212		return B_NO_MEMORY;
213
214	_data = fCookie->data;
215	_toRead = attributeSize;
216
217	return B_OK;
218}
219
220
221void
222AttributeIndexer::DeleteCookie()
223{
224	fCookie->Delete();
225	fCookie = NULL;
226}
227
228
229// #pragma mark - AttributeIndex
230
231
232AttributeIndex::AttributeIndex()
233	:
234	Index(),
235	fNodes(NULL),
236	fIteratorsToUpdate(NULL),
237	fIndexer(NULL)
238{
239}
240
241
242AttributeIndex::~AttributeIndex()
243{
244	if (IsListening())
245		fVolume->RemoveNodeListener(this);
246
247	ASSERT(fIteratorsToUpdate->IsEmpty());
248
249	delete fIteratorsToUpdate;
250	delete fNodes;
251	delete fIndexer;
252}
253
254
255status_t
256AttributeIndex::Init(Volume* volume, const char* name,  uint32 type,
257	size_t keyLength)
258{
259	status_t error = Index::Init(volume, name, type, keyLength > 0, keyLength);
260	if (error != B_OK)
261		return error;
262
263	// TODO: Letting each attribute index be a listener is gets more expensive
264	// the more attribute indices we have. Since most attribute indices are
265	// rather sparse, it might be a good idea to rather let Volume iterate
266	// through the actual attributes of an added node and look up and call the
267	// index for each one explicitly. When removing the node, the volume would
268	// iterate through the attributes again and determine based on the index
269	// cookie whether an index has to be notified.
270	fVolume->AddNodeListener(this, NULL);
271
272	fNodes = new(std::nothrow) NodeTree(TreeDefinition(type));
273	fIteratorsToUpdate = new(std::nothrow) IteratorList;
274	fIndexer = new(std::nothrow) AttributeIndexer(this);
275
276	if (fNodes == NULL || fIteratorsToUpdate == NULL || fIndexer == NULL)
277		return B_NO_MEMORY;
278
279	return B_OK;
280}
281
282
283int32
284AttributeIndex::CountEntries() const
285{
286	return fNodes->Count();
287}
288
289
290void
291AttributeIndex::NodeAdded(Node* node)
292{
293	if (node->IndexAttribute(fIndexer) != B_OK)
294		return;
295
296	TreeValue* treeValue = fIndexer->Cookie();
297	treeValue->node = node;
298
299	fNodes->Insert(treeValue);
300}
301
302
303void
304AttributeIndex::NodeRemoved(Node* node)
305{
306	TreeValue* treeValue = (TreeValue*)node->IndexCookieForAttribute(Name());
307	if (treeValue == NULL)
308		return;
309
310	treeValue->owner->UnsetIndexCookie(treeValue->attributeCookie);
311	fNodes->Remove(treeValue);
312}
313
314
315void
316AttributeIndex::NodeChanged(Node* node, uint32 statFields,
317	const OldNodeAttributes& oldAttributes)
318{
319	IteratorList iterators;
320	iterators.MoveFrom(fIteratorsToUpdate);
321
322	TreeValue* oldTreeValue
323		= (TreeValue*)oldAttributes.IndexCookieForAttribute(Name());
324	TreeValue* treeValue = (TreeValue*)node->IndexCookieForAttribute(Name());
325	if (treeValue == NULL && oldTreeValue == NULL)
326		return;
327
328	// move the iterators that point to the node to the previous node
329	if (oldTreeValue != NULL) {
330		for (IteratorList::Iterator it = iterators.GetIterator();
331				Iterator* iterator = it.Next();) {
332			iterator->NodeChangeBegin(node);
333		}
334
335		// remove the node
336		fNodes->Remove(oldTreeValue);
337	}
338
339	// re-insert the node
340	if (treeValue != NULL)
341		fNodes->Insert(treeValue);
342
343	// Move the iterators to the next node again. If the node hasn't changed
344	// its place, they will point to it again, otherwise to the node originally
345	// succeeding it.
346	if (oldTreeValue != NULL) {
347		for (IteratorList::Iterator it = iterators.GetIterator();
348				Iterator* iterator = it.Next();) {
349			iterator->NodeChangeEnd(node);
350		}
351	}
352
353	// update live queries
354	fVolume->UpdateLiveQueries(node, Name(), Type(),
355		oldTreeValue != NULL ? oldTreeValue->data : NULL,
356		oldTreeValue != NULL ? oldTreeValue->length : 0,
357		treeValue != NULL ? treeValue->data : NULL,
358		treeValue != NULL ? treeValue->length : 0);
359
360	if (oldTreeValue != NULL)
361		oldTreeValue->Delete();
362}
363
364
365AbstractIndexIterator*
366AttributeIndex::InternalGetIterator()
367{
368	Iterator* iterator = new(std::nothrow) Iterator;
369	if (iterator != NULL) {
370		if (!iterator->SetTo(this, TreeKey(), true)) {
371			delete iterator;
372			iterator = NULL;
373		}
374	}
375	return iterator;
376}
377
378
379AbstractIndexIterator*
380AttributeIndex::InternalFind(const void* key, size_t length)
381{
382	if (HasFixedKeyLength() && length != KeyLength())
383		return NULL;
384
385	Iterator* iterator = new(std::nothrow) Iterator;
386	if (iterator != NULL) {
387		if (!iterator->SetTo(this, TreeKey(key, length))) {
388			delete iterator;
389			iterator = NULL;
390		}
391	}
392	return iterator;
393}
394
395
396void
397AttributeIndex::_AddIteratorToUpdate(Iterator* iterator)
398{
399	fIteratorsToUpdate->Add(iterator);
400}
401
402
403// #pragma mark - Iterator
404
405
406void
407AttributeIndex::Iterator::NodeChanged(Node* node, uint32 statFields,
408	const OldNodeAttributes& oldAttributes)
409{
410	fIndex->_AddIteratorToUpdate(this);
411}
412