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