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		int cmp = QueryParser::compareKeys(fType, a.data, a.length, b->data,
93			b->length);
94		if (cmp != 0)
95			return cmp;
96
97		// The attribute value is the same. Since the tree value is the tree
98		// node itself, we must not return 0, though. We consider a node-less
99		// key always less than an actual tree node with the same attribute
100		// value.
101		return -1;
102	}
103
104	int Compare(const Value* a, const Value* b) const
105	{
106		if (a == b)
107			return 0;
108
109		int cmp = QueryParser::compareKeys(fType, a->data, a->length, b->data,
110			b->length);
111		if (cmp != 0)
112			return cmp;
113
114		return a < b ? -1 : 1;
115	}
116
117private:
118	uint32	fType;
119};
120
121
122// #pragma mark - NodeTree
123
124
125struct AttributeIndex::NodeTree : public AVLTree<TreeDefinition> {
126	typedef TreeValue	Node;
127
128	NodeTree(const TreeDefinition& definition)
129		:
130		AVLTree<TreeDefinition>(definition)
131	{
132	}
133};
134
135
136// #pragma mark - IteratorList
137
138
139class AttributeIndex::IteratorList : public SinglyLinkedList<Iterator> {};
140
141
142// #pragma mark - Iterator
143
144
145struct AttributeIndex::IteratorPolicy {
146	typedef AttributeIndex				Index;
147	typedef TreeKey						Value;
148	typedef AttributeIndex::NodeTree	NodeTree;
149	typedef TreeValue					TreeNode;
150	typedef IteratorPolicy				TreePolicy;
151
152	static NodeTree* GetNodeTree(Index* index)
153	{
154		return index->fNodes;
155	}
156
157	static void GetTreeNodeValue(TreeNode* node, void* buffer,
158		size_t* _keyLength)
159	{
160		if (node->length > 0)
161			memcpy(buffer, node->data, node->length);
162		*_keyLength = node->length;
163	}
164
165	static Node* GetNode(TreeNode* treeNode)
166	{
167		return treeNode->node;
168	}
169
170	static TreeNode* GetFirstTreeNode(Index* index)
171	{
172		return index->fNodes->GetIterator().Next();
173	}
174
175	static TreeNode* FindClosestTreeNode(Index* index, const Value& value)
176	{
177		return index->fNodes->FindClosest(value, false);
178	}
179};
180
181
182class AttributeIndex::Iterator : public GenericIndexIterator<IteratorPolicy>,
183	public SinglyLinkedListLinkImpl<Iterator> {
184public:
185	virtual	void				NodeChanged(Node* node, uint32 statFields,
186									const OldNodeAttributes& oldAttributes);
187};
188
189
190// #pragma mark - AttributeIndexer
191
192
193AttributeIndexer::AttributeIndexer(AttributeIndex* index)
194	:
195	fIndex(index),
196	fIndexName(index->Name()),
197	fIndexType(index->Type()),
198	fCookie(NULL)
199{
200}
201
202
203AttributeIndexer::~AttributeIndexer()
204{
205}
206
207
208status_t
209AttributeIndexer::CreateCookie(IndexedAttributeOwner* owner,
210	void* attributeCookie, uint32 attributeType, size_t attributeSize,
211	void*& _data, size_t& _toRead)
212{
213	// check the attribute type and size
214	if (attributeType != fIndexType)
215		return B_ERROR;
216
217	if (fIndex->HasFixedKeyLength()) {
218		if (attributeSize != fIndex->KeyLength())
219			return B_ERROR;
220	} else if (attributeSize > kMaxIndexKeyLength)
221		attributeSize = kMaxIndexKeyLength;
222
223	// create the tree value
224	fCookie = AttributeIndexTreeValue::Create(owner, attributeCookie,
225		attributeSize);
226	if (fCookie == NULL)
227		return B_NO_MEMORY;
228
229	_data = fCookie->data;
230	_toRead = attributeSize;
231
232	return B_OK;
233}
234
235
236void
237AttributeIndexer::DeleteCookie()
238{
239	fCookie->Delete();
240	fCookie = NULL;
241}
242
243
244// #pragma mark - AttributeIndex
245
246
247AttributeIndex::AttributeIndex()
248	:
249	Index(),
250	fNodes(NULL),
251	fIteratorsToUpdate(NULL),
252	fIndexer(NULL)
253{
254}
255
256
257AttributeIndex::~AttributeIndex()
258{
259	if (IsListening())
260		fVolume->RemoveNodeListener(this);
261
262	ASSERT(fIteratorsToUpdate->IsEmpty());
263
264	delete fIteratorsToUpdate;
265	delete fNodes;
266	delete fIndexer;
267}
268
269
270status_t
271AttributeIndex::Init(Volume* volume, const char* name,  uint32 type,
272	size_t keyLength)
273{
274	status_t error = Index::Init(volume, name, type, keyLength > 0, keyLength);
275	if (error != B_OK)
276		return error;
277
278	// TODO: Letting each attribute index be a listener is gets more expensive
279	// the more attribute indices we have. Since most attribute indices are
280	// rather sparse, it might be a good idea to rather let Volume iterate
281	// through the actual attributes of an added node and look up and call the
282	// index for each one explicitly. When removing the node, the volume would
283	// iterate through the attributes again and determine based on the index
284	// cookie whether an index has to be notified.
285	fVolume->AddNodeListener(this, NULL);
286
287	fNodes = new(std::nothrow) NodeTree(TreeDefinition(type));
288	fIteratorsToUpdate = new(std::nothrow) IteratorList;
289	fIndexer = new(std::nothrow) AttributeIndexer(this);
290
291	if (fNodes == NULL || fIteratorsToUpdate == NULL || fIndexer == NULL)
292		return B_NO_MEMORY;
293
294	return B_OK;
295}
296
297
298int32
299AttributeIndex::CountEntries() const
300{
301	return fNodes->Count();
302}
303
304
305void
306AttributeIndex::NodeAdded(Node* node)
307{
308	if (node->IndexAttribute(fIndexer) != B_OK)
309		return;
310
311	TreeValue* treeValue = fIndexer->Cookie();
312	treeValue->node = node;
313
314	fNodes->Insert(treeValue);
315}
316
317
318void
319AttributeIndex::NodeRemoved(Node* node)
320{
321	TreeValue* treeValue = (TreeValue*)node->IndexCookieForAttribute(Name());
322	if (treeValue == NULL)
323		return;
324
325	treeValue->owner->UnsetIndexCookie(treeValue->attributeCookie);
326	fNodes->Remove(treeValue);
327}
328
329
330void
331AttributeIndex::NodeChanged(Node* node, uint32 statFields,
332	const OldNodeAttributes& oldAttributes)
333{
334	IteratorList iterators;
335	iterators.MoveFrom(fIteratorsToUpdate);
336
337	TreeValue* oldTreeValue
338		= (TreeValue*)oldAttributes.IndexCookieForAttribute(Name());
339	TreeValue* treeValue = (TreeValue*)node->IndexCookieForAttribute(Name());
340	if (treeValue == NULL && oldTreeValue == NULL)
341		return;
342
343	// move the iterators that point to the node to the previous node
344	if (oldTreeValue != NULL) {
345		for (IteratorList::Iterator it = iterators.GetIterator();
346				Iterator* iterator = it.Next();) {
347			iterator->NodeChangeBegin(node);
348		}
349
350		// remove the node
351		fNodes->Remove(oldTreeValue);
352	}
353
354	// re-insert the node
355	if (treeValue != NULL)
356		fNodes->Insert(treeValue);
357
358	// Move the iterators to the next node again. If the node hasn't changed
359	// its place, they will point to it again, otherwise to the node originally
360	// succeeding it.
361	if (oldTreeValue != NULL) {
362		for (IteratorList::Iterator it = iterators.GetIterator();
363				Iterator* iterator = it.Next();) {
364			iterator->NodeChangeEnd(node);
365		}
366	}
367
368	// update live queries
369	fVolume->UpdateLiveQueries(node, Name(), Type(),
370		oldTreeValue != NULL ? oldTreeValue->data : NULL,
371		oldTreeValue != NULL ? oldTreeValue->length : 0,
372		treeValue != NULL ? treeValue->data : NULL,
373		treeValue != NULL ? treeValue->length : 0);
374
375	if (oldTreeValue != NULL)
376		oldTreeValue->Delete();
377}
378
379
380AbstractIndexIterator*
381AttributeIndex::InternalGetIterator()
382{
383	Iterator* iterator = new(std::nothrow) Iterator;
384	if (iterator != NULL) {
385		if (!iterator->SetTo(this, TreeKey(), true)) {
386			delete iterator;
387			iterator = NULL;
388		}
389	}
390	return iterator;
391}
392
393
394AbstractIndexIterator*
395AttributeIndex::InternalFind(const void* key, size_t length)
396{
397	if (HasFixedKeyLength() && length != KeyLength())
398		return NULL;
399
400	Iterator* iterator = new(std::nothrow) Iterator;
401	if (iterator != NULL) {
402		if (!iterator->SetTo(this, TreeKey(key, length))) {
403			delete iterator;
404			iterator = NULL;
405		}
406	}
407	return iterator;
408}
409
410
411void
412AttributeIndex::_AddIteratorToUpdate(Iterator* iterator)
413{
414	fIteratorsToUpdate->Add(iterator);
415}
416
417
418// #pragma mark - Iterator
419
420
421void
422AttributeIndex::Iterator::NodeChanged(Node* node, uint32 statFields,
423	const OldNodeAttributes& oldAttributes)
424{
425	fIndex->_AddIteratorToUpdate(this);
426}
427