1/*
2 * Copyright 2007, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * All rights reserved. Distributed under the terms of the MIT license.
4 */
5
6#include <TypeConstants.h>
7
8#include "AttributeIndexImpl.h"
9#include "DebugSupport.h"
10#include "Entry.h"
11#include "EntryListener.h"
12#include "IndexImpl.h"
13#include "Misc.h"
14#include "Node.h"
15#include "NodeListener.h"
16#include "ramfs.h"
17#include "TwoKeyAVLTree.h"
18#include "Volume.h"
19
20// compare_integral
21template<typename Key>
22static inline
23int
24compare_integral(const Key &a, const Key &b)
25{
26	if (a < b)
27		return -1;
28	else if (a > b)
29		return 1;
30	return 0;
31}
32
33// compare_keys
34static
35int
36compare_keys(const uint8 *key1, size_t length1, const uint8 *key2,
37			 size_t length2, uint32 type)
38{
39	switch (type) {
40		case B_INT32_TYPE:
41			return compare_integral(*(int32*)key1, *(int32*)key2);
42		case B_UINT32_TYPE:
43			return compare_integral(*(uint32*)key1, *(uint32*)key2);
44		case B_INT64_TYPE:
45			return compare_integral(*(int64*)key1, *(int64*)key2);
46		case B_UINT64_TYPE:
47			return compare_integral(*(uint64*)key1, *(uint64*)key2);
48		case B_FLOAT_TYPE:
49			return compare_integral(*(float*)key1, *(float*)key2);
50		case B_DOUBLE_TYPE:
51			return compare_integral(*(double*)key1, *(double*)key2);
52		case B_STRING_TYPE:
53		{
54			int result = strncmp((const char*)key1, (const char*)key2,
55								 min(length1, length2));
56			if (result == 0) {
57				result = compare_integral(strnlen((const char*)key1, length1),
58										  strnlen((const char*)key2, length2));
59			}
60			return result;
61		}
62	}
63	return -1;
64}
65
66// PrimaryKey
67class AttributeIndexImpl::PrimaryKey {
68public:
69	PrimaryKey(Attribute *attribute, const uint8 *theKey,
70			   size_t length)
71		: attribute(attribute), length(length)
72			{ memcpy(key, theKey, length); }
73	PrimaryKey(Attribute *attribute)
74		: attribute(attribute) { attribute->GetKey(key, &length); }
75	PrimaryKey(const uint8 *theKey, size_t length)
76		: attribute(NULL), length(length)
77			{ memcpy(key, theKey, length); }
78
79	Attribute	*attribute;
80	uint8		key[kMaxIndexKeyLength];
81	size_t		length;
82};
83
84// GetPrimaryKey
85class AttributeIndexImpl::GetPrimaryKey {
86public:
87	inline PrimaryKey operator()(Attribute *a)
88	{
89		return PrimaryKey(a);
90	}
91
92	inline PrimaryKey operator()(Attribute *a) const
93	{
94		return PrimaryKey(a);
95	}
96};
97
98// PrimaryKeyCompare
99class AttributeIndexImpl::PrimaryKeyCompare
100{
101public:
102	PrimaryKeyCompare(uint32 type) : fType(type) {}
103
104	inline int operator()(const PrimaryKey &a,
105						  const PrimaryKey &b) const
106	{
107		if (a.attribute != NULL && a.attribute == b.attribute)
108			return 0;
109		return compare_keys(a.key, a.length, b.key, b.length, fType);
110	}
111
112	uint32	fType;
113};
114
115// AttributeNodeIterator
116template<typename AttributeIterator>
117class AttributeNodeIterator {
118public:
119	inline Node **GetCurrent()
120	{
121		if (Attribute **attribute = fIterator.GetCurrent()) {
122			fNode = (*attribute)->GetNode();
123			return &fNode;
124		}
125		return NULL;
126	}
127
128	inline Node **GetNext()
129	{
130		if (Attribute **attribute = fIterator.GetNext()) {
131			fNode = (*attribute)->GetNode();
132			return &fNode;
133		}
134		return NULL;
135	}
136
137	AttributeIterator	fIterator;
138	Node				*fNode;
139};
140
141
142// AttributeTree
143class AttributeIndexImpl::AttributeTree
144	: public TwoKeyAVLTree<Attribute*, PrimaryKey, PrimaryKeyCompare,
145						   GetPrimaryKey> {
146public:
147	AttributeTree(uint32 type)
148		: TwoKeyAVLTree<Attribute*, PrimaryKey, PrimaryKeyCompare,
149						GetPrimaryKey>(PrimaryKeyCompare(type),
150		  	GetPrimaryKey(), TwoKeyAVLTreeStandardCompare<Attribute*>(),
151			TwoKeyAVLTreeStandardGetKey<Attribute*, Attribute*>())
152	{
153	}
154};
155
156
157// Iterator
158class AttributeIndexImpl::Iterator
159	: public NodeEntryIterator<
160		AttributeNodeIterator<AttributeTree::Iterator> >,
161	  public DoublyLinkedListLinkImpl<Iterator>, public EntryListener,
162	  public NodeListener {
163public:
164	Iterator();
165	virtual ~Iterator();
166
167	virtual Entry *GetCurrent();
168	virtual Entry *GetCurrent(uint8 *buffer, size_t *keyLength);
169
170	virtual status_t Suspend();
171	virtual status_t Resume();
172
173	bool SetTo(AttributeIndexImpl *index, const uint8 *key, size_t length,
174			   bool ignoreValue = false);
175	void Unset();
176
177	virtual void EntryRemoved(Entry *entry);
178	virtual void NodeRemoved(Node *node);
179
180private:
181	typedef NodeEntryIterator<
182		AttributeNodeIterator<AttributeTree::Iterator> > BaseClass;
183
184private:
185	AttributeIndexImpl	*fIndex;
186};
187
188
189// IteratorList
190class AttributeIndexImpl::IteratorList : public DoublyLinkedList<Iterator> {};
191
192
193// AttributeIndexImpl
194
195// constructor
196AttributeIndexImpl::AttributeIndexImpl(Volume *volume, const char *name,
197									   uint32 type, size_t keyLength)
198	: AttributeIndex(volume, name, type, (keyLength > 0), keyLength),
199	  fAttributes(new(nothrow) AttributeTree(type)),
200	  fIterators(new(nothrow) IteratorList)
201{
202	if (fInitStatus == B_OK && (!fAttributes || !fIterators))
203		fInitStatus = B_NO_MEMORY;
204}
205
206// destructor
207AttributeIndexImpl::~AttributeIndexImpl()
208{
209	if (fIterators) {
210		// unset the iterators
211		for (Iterator *iterator = fIterators->First();
212			 iterator;
213			 iterator = fIterators->GetNext(iterator)) {
214			iterator->SetTo(NULL, NULL, 0);
215		}
216		delete fIterators;
217	}
218	// unset all attributes and delete the tree
219	if (fAttributes) {
220		AttributeTree::Iterator it;
221		fAttributes->GetIterator(&it);
222		for (Attribute **attribute = it.GetCurrent(); attribute; it.GetNext())
223			(*attribute)->SetIndex(NULL, false);
224		delete fAttributes;
225	}
226}
227
228// CountEntries
229int32
230AttributeIndexImpl::CountEntries() const
231{
232	return fAttributes->CountItems();
233}
234
235// Changed
236status_t
237AttributeIndexImpl::Changed(Attribute *attribute, const uint8 *oldKey,
238							size_t oldLength)
239{
240	status_t error = B_BAD_VALUE;
241	if (attribute && attribute->GetIndex() == this) {
242		// update the iterators and remove the attribute from the tree
243		error = B_OK;
244		if (attribute->IsInIndex()) {
245			AttributeTree::Iterator it;
246			Attribute **foundAttribute = fAttributes->Find(
247				PrimaryKey(attribute, oldKey, oldLength), attribute, &it);
248			if (foundAttribute && *foundAttribute == attribute) {
249				Node *node = attribute->GetNode();
250				// update the iterators
251				for (Iterator *iterator = fIterators->First();
252					 iterator;
253					 iterator = fIterators->GetNext(iterator)) {
254					if (iterator->GetCurrentNode() == node)
255						iterator->NodeRemoved(node);
256				}
257				// remove and re-insert the attribute
258				it.Remove();
259			}
260		}
261		// re-insert the attribute
262		if (fKeyLength > 0 && attribute->GetSize() != (off_t)fKeyLength) {
263			attribute->SetIndex(this, false);
264		} else {
265			error = fAttributes->Insert(attribute);
266			if (error == B_OK)
267				attribute->SetIndex(this, true);
268			else
269				attribute->SetIndex(NULL, false);
270		}
271	}
272	return error;
273}
274
275// Added
276status_t
277AttributeIndexImpl::Added(Attribute *attribute)
278{
279PRINT("AttributeIndex::Add(%p)\n", attribute);
280	status_t error = (attribute ? B_OK : B_BAD_VALUE);
281	if (error == B_OK) {
282		size_t size = attribute->GetSize();
283		if (fKeyLength > 0 && size != fKeyLength) {
284			attribute->SetIndex(this, false);
285		} else {
286			error = fAttributes->Insert(attribute);
287			if (error == B_OK)
288				attribute->SetIndex(this, true);
289		}
290	}
291	return error;
292}
293
294// Removed
295bool
296AttributeIndexImpl::Removed(Attribute *attribute)
297{
298PRINT("AttributeIndex::Removed(%p)\n", attribute);
299	bool result = (attribute && attribute->GetIndex() == this);
300	if (result) {
301		if (attribute->IsInIndex())
302			fAttributes->Remove(attribute, attribute);
303		attribute->SetIndex(NULL, false);
304	}
305	return result;
306}
307
308// InternalGetIterator
309AbstractIndexEntryIterator *
310AttributeIndexImpl::InternalGetIterator()
311{
312	Iterator *iterator = new(nothrow) Iterator;
313	if (iterator) {
314		if (!iterator->SetTo(this, NULL, 0, true)) {
315			delete iterator;
316			iterator = NULL;
317		}
318	}
319	return iterator;
320}
321
322// InternalFind
323AbstractIndexEntryIterator *
324AttributeIndexImpl::InternalFind(const uint8 *key, size_t length)
325{
326	if (!key || (fKeyLength > 0 && length != fKeyLength))
327		return NULL;
328	Iterator *iterator = new(nothrow) Iterator;
329	if (iterator) {
330		if (!iterator->SetTo(this, key, length)) {
331			delete iterator;
332			iterator = NULL;
333		}
334	}
335	return iterator;
336}
337
338// _AddIterator
339void
340AttributeIndexImpl::_AddIterator(Iterator *iterator)
341{
342	fIterators->Insert(iterator);
343}
344
345// _RemoveIterator
346void
347AttributeIndexImpl::_RemoveIterator(Iterator *iterator)
348{
349	fIterators->Remove(iterator);
350}
351
352
353// Iterator
354
355// constructor
356AttributeIndexImpl::Iterator::Iterator()
357	: BaseClass(),
358	  fIndex(NULL)
359{
360}
361
362// destructor
363AttributeIndexImpl::Iterator::~Iterator()
364{
365	SetTo(NULL, NULL, 0);
366}
367
368// GetCurrent
369Entry *
370AttributeIndexImpl::Iterator::GetCurrent()
371{
372	return BaseClass::GetCurrent();
373}
374
375// GetCurrent
376Entry *
377AttributeIndexImpl::Iterator::GetCurrent(uint8 *buffer, size_t *keyLength)
378{
379	Entry *entry = GetCurrent();
380	if (entry) {
381		if (Attribute **attribute = fIterator.fIterator.GetCurrent()) {
382			if ((*attribute)->GetNode() == entry->GetNode()) {
383				(*attribute)->GetKey(buffer, keyLength);
384			} else {
385				FATAL("Node of current attribute and node of current entry "
386					   "differ: %" B_PRIdINO " vs. %" B_PRIdINO "\n",
387					   (*attribute)->GetNode()->GetID(),
388					   entry->GetNode()->GetID());
389				entry = NULL;
390			}
391		} else {
392			FATAL("We have a current entry (`%s', node: %" B_PRIdINO "), but no current "
393				   "attribute.\n", entry->GetName(),
394				   entry->GetNode()->GetID());
395			entry = NULL;
396		}
397	}
398	return entry;
399}
400
401// Suspend
402status_t
403AttributeIndexImpl::Iterator::Suspend()
404{
405	status_t error = BaseClass::Suspend();
406	if (error == B_OK) {
407		if (fNode) {
408			error = fIndex->GetVolume()->AddNodeListener(this, fNode,
409														 NODE_LISTEN_REMOVED);
410			if (error == B_OK && fEntry) {
411				error = fIndex->GetVolume()->AddEntryListener(this, fEntry,
412					ENTRY_LISTEN_REMOVED);
413				if (error != B_OK)
414					fIndex->GetVolume()->RemoveNodeListener(this, fNode);
415			}
416			if (error != B_OK)
417				BaseClass::Resume();
418		}
419	}
420	return error;
421}
422
423// Resume
424status_t
425AttributeIndexImpl::Iterator::Resume()
426{
427	status_t error = BaseClass::Resume();
428	if (error == B_OK) {
429		if (fEntry)
430			error = fIndex->GetVolume()->RemoveEntryListener(this, fEntry);
431		if (fNode) {
432			if (error == B_OK)
433				error = fIndex->GetVolume()->RemoveNodeListener(this, fNode);
434			else
435				fIndex->GetVolume()->RemoveNodeListener(this, fNode);
436		}
437	}
438	return error;
439}
440
441// SetTo
442bool
443AttributeIndexImpl::Iterator::SetTo(AttributeIndexImpl *index,
444	const uint8 *key, size_t length, bool ignoreValue)
445{
446	Resume();
447	Unset();
448	// set the new values
449	fIndex = index;
450	if (fIndex)
451		fIndex->_AddIterator(this);
452	fInitialized = fIndex;
453	// get the attribute node's first entry
454	if (fIndex) {
455		// get the first node
456		bool found = true;
457		if (ignoreValue)
458			fIndex->fAttributes->GetIterator(&fIterator.fIterator);
459		else {
460			found = fIndex->fAttributes->FindFirst(PrimaryKey(key, length),
461												   &(fIterator.fIterator));
462		}
463		// get the first entry
464		if (found) {
465			if (Node **nodeP = fIterator.GetCurrent()) {
466				fNode = *nodeP;
467				fEntry = fNode->GetFirstReferrer();
468				if (!fEntry)
469					BaseClass::GetNext();
470				if (Attribute **attribute = fIterator.fIterator.GetCurrent()) {
471					uint8 attrKey[kMaxIndexKeyLength];
472					size_t attrKeyLength;
473					(*attribute)->GetKey(attrKey, &attrKeyLength);
474					if (!ignoreValue
475						&& compare_keys(attrKey, attrKeyLength, key, length,
476										fIndex->GetType()) != 0) {
477						Unset();
478					}
479				}
480			}
481		}
482	}
483	return fEntry;
484}
485
486// Unset
487void
488AttributeIndexImpl::Iterator::Unset()
489{
490	if (fIndex) {
491		fIndex->_RemoveIterator(this);
492		fIndex = NULL;
493	}
494	BaseClass::Unset();
495}
496
497// EntryRemoved
498void
499AttributeIndexImpl::Iterator::EntryRemoved(Entry */*entry*/)
500{
501	Resume();
502	fIsNext = BaseClass::GetNext();
503	Suspend();
504}
505
506// NodeRemoved
507void
508AttributeIndexImpl::Iterator::NodeRemoved(Node */*node*/)
509{
510	Resume();
511	fEntry = NULL;
512	fIsNext = BaseClass::GetNext();
513	Suspend();
514}
515
516