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(), TwoKeyAVLTreeStandardCompare<Attribute*>(),
146			TwoKeyAVLTreeStandardGetKey<Attribute*, Attribute*>())
147	{
148	}
149};
150
151
152// Iterator
153class AttributeIndexImpl::Iterator
154	: public NodeEntryIterator<
155		AttributeNodeIterator<AttributeTree::Iterator> >,
156	  public DoublyLinkedListLinkImpl<Iterator>, public EntryListener,
157	  public NodeListener {
158public:
159	Iterator();
160	virtual ~Iterator();
161
162	virtual Entry *GetCurrent();
163	virtual Entry *GetCurrent(uint8 *buffer, size_t *keyLength);
164
165	virtual status_t Suspend();
166	virtual status_t Resume();
167
168	bool SetTo(AttributeIndexImpl *index, const uint8 *key, size_t length,
169			   bool ignoreValue = false);
170	void Unset();
171
172	virtual void EntryRemoved(Entry *entry);
173	virtual void NodeRemoved(Node *node);
174
175private:
176	typedef NodeEntryIterator<
177		AttributeNodeIterator<AttributeTree::Iterator> > BaseClass;
178
179private:
180	AttributeIndexImpl	*fIndex;
181};
182
183
184// IteratorList
185class AttributeIndexImpl::IteratorList : public DoublyLinkedList<Iterator> {};
186
187
188// AttributeIndexImpl
189
190// constructor
191AttributeIndexImpl::AttributeIndexImpl(Volume *volume, const char *name,
192									   uint32 type, size_t keyLength)
193	: AttributeIndex(volume, name, type, (keyLength > 0), keyLength),
194	  fAttributes(new(nothrow) AttributeTree(type)),
195	  fIterators(new(nothrow) IteratorList)
196{
197	if (fInitStatus == B_OK && (!fAttributes || !fIterators))
198		fInitStatus = B_NO_MEMORY;
199}
200
201// destructor
202AttributeIndexImpl::~AttributeIndexImpl()
203{
204	if (fIterators) {
205		// unset the iterators
206		for (Iterator *iterator = fIterators->First();
207			 iterator;
208			 iterator = fIterators->GetNext(iterator)) {
209			iterator->SetTo(NULL, NULL, 0);
210		}
211		delete fIterators;
212	}
213	// unset all attributes and delete the tree
214	if (fAttributes) {
215		AttributeTree::Iterator it;
216		fAttributes->GetIterator(&it);
217		for (Attribute **attribute = it.GetCurrent(); attribute; it.GetNext())
218			(*attribute)->SetIndex(NULL, false);
219		delete fAttributes;
220	}
221}
222
223// CountEntries
224int32
225AttributeIndexImpl::CountEntries() const
226{
227	return fAttributes->CountItems();
228}
229
230// Changed
231status_t
232AttributeIndexImpl::Changed(Attribute *attribute, const uint8 *oldKey,
233							size_t oldLength)
234{
235	status_t error = B_BAD_VALUE;
236	if (attribute && attribute->GetIndex() == this) {
237		// update the iterators and remove the attribute from the tree
238		error = B_OK;
239		if (attribute->IsInIndex()) {
240			AttributeTree::Iterator it;
241			Attribute **foundAttribute = fAttributes->Find(
242				PrimaryKey(attribute, oldKey, oldLength), attribute, &it);
243			if (foundAttribute && *foundAttribute == attribute) {
244				Node *node = attribute->GetNode();
245				// update the iterators
246				for (Iterator *iterator = fIterators->First();
247					 iterator;
248					 iterator = fIterators->GetNext(iterator)) {
249					if (iterator->GetCurrentNode() == node)
250						iterator->NodeRemoved(node);
251				}
252				// remove and re-insert the attribute
253				it.Remove();
254			}
255		}
256		// re-insert the attribute
257		if (fKeyLength > 0 && attribute->GetSize() != fKeyLength) {
258			attribute->SetIndex(this, false);
259		} else {
260			error = fAttributes->Insert(attribute);
261			if (error == B_OK)
262				attribute->SetIndex(this, true);
263			else
264				attribute->SetIndex(NULL, false);
265		}
266	}
267	return error;
268}
269
270// Added
271status_t
272AttributeIndexImpl::Added(Attribute *attribute)
273{
274PRINT(("AttributeIndex::Add(%p)\n", attribute));
275	status_t error = (attribute ? B_OK : B_BAD_VALUE);
276	if (error == B_OK) {
277		size_t size = attribute->GetSize();
278		if (fKeyLength > 0 && size != fKeyLength) {
279			attribute->SetIndex(this, false);
280		} else {
281			error = fAttributes->Insert(attribute);
282			if (error == B_OK)
283				attribute->SetIndex(this, true);
284		}
285	}
286	return error;
287}
288
289// Removed
290bool
291AttributeIndexImpl::Removed(Attribute *attribute)
292{
293PRINT(("AttributeIndex::Removed(%p)\n", attribute));
294	bool result = (attribute && attribute->GetIndex() == this);
295	if (result) {
296		if (attribute->IsInIndex())
297			fAttributes->Remove(attribute, attribute);
298		attribute->SetIndex(NULL, false);
299	}
300	return result;
301}
302
303// InternalGetIterator
304AbstractIndexEntryIterator *
305AttributeIndexImpl::InternalGetIterator()
306{
307	Iterator *iterator = new(nothrow) Iterator;
308	if (iterator) {
309		if (!iterator->SetTo(this, NULL, 0, true)) {
310			delete iterator;
311			iterator = NULL;
312		}
313	}
314	return iterator;
315}
316
317// InternalFind
318AbstractIndexEntryIterator *
319AttributeIndexImpl::InternalFind(const uint8 *key, size_t length)
320{
321	if (!key || (fKeyLength > 0 && length != fKeyLength))
322		return NULL;
323	Iterator *iterator = new(nothrow) Iterator;
324	if (iterator) {
325		if (!iterator->SetTo(this, key, length)) {
326			delete iterator;
327			iterator = NULL;
328		}
329	}
330	return iterator;
331}
332
333// _AddIterator
334void
335AttributeIndexImpl::_AddIterator(Iterator *iterator)
336{
337	fIterators->Insert(iterator);
338}
339
340// _RemoveIterator
341void
342AttributeIndexImpl::_RemoveIterator(Iterator *iterator)
343{
344	fIterators->Remove(iterator);
345}
346
347
348// Iterator
349
350// constructor
351AttributeIndexImpl::Iterator::Iterator()
352	: BaseClass(),
353	  fIndex(NULL)
354{
355}
356
357// destructor
358AttributeIndexImpl::Iterator::~Iterator()
359{
360	SetTo(NULL, NULL, 0);
361}
362
363// GetCurrent
364Entry *
365AttributeIndexImpl::Iterator::GetCurrent()
366{
367	return BaseClass::GetCurrent();
368}
369
370// GetCurrent
371Entry *
372AttributeIndexImpl::Iterator::GetCurrent(uint8 *buffer, size_t *keyLength)
373{
374	Entry *entry = GetCurrent();
375	if (entry) {
376		if (Attribute **attribute = fIterator.fIterator.GetCurrent()) {
377			if ((*attribute)->GetNode() == entry->GetNode()) {
378				(*attribute)->GetKey(buffer, keyLength);
379			} else {
380				FATAL(("Node of current attribute and node of current entry "
381					   "differ: %Ld vs. %Ld\n",
382					   (*attribute)->GetNode()->GetID(),
383					   entry->GetNode()->GetID()));
384				entry = NULL;
385			}
386		} else {
387			FATAL(("We have a current entry (`%s', node: %Ld), but no current "
388				   "attribute.\n", entry->GetName(),
389				   entry->GetNode()->GetID()));
390			entry = NULL;
391		}
392	}
393	return entry;
394}
395
396// Suspend
397status_t
398AttributeIndexImpl::Iterator::Suspend()
399{
400	status_t error = BaseClass::Suspend();
401	if (error == B_OK) {
402		if (fNode) {
403			error = fIndex->GetVolume()->AddNodeListener(this, fNode,
404														 NODE_LISTEN_REMOVED);
405			if (error == B_OK && fEntry) {
406				error = fIndex->GetVolume()->AddEntryListener(this, fEntry,
407					ENTRY_LISTEN_REMOVED);
408				if (error != B_OK)
409					fIndex->GetVolume()->RemoveNodeListener(this, fNode);
410			}
411			if (error != B_OK)
412				BaseClass::Resume();
413		}
414	}
415	return error;
416}
417
418// Resume
419status_t
420AttributeIndexImpl::Iterator::Resume()
421{
422	status_t error = BaseClass::Resume();
423	if (error == B_OK) {
424		if (fEntry)
425			error = fIndex->GetVolume()->RemoveEntryListener(this, fEntry);
426		if (fNode) {
427			if (error == B_OK)
428				error = fIndex->GetVolume()->RemoveNodeListener(this, fNode);
429			else
430				fIndex->GetVolume()->RemoveNodeListener(this, fNode);
431		}
432	}
433	return error;
434}
435
436// SetTo
437bool
438AttributeIndexImpl::Iterator::SetTo(AttributeIndexImpl *index,
439	const uint8 *key, size_t length, bool ignoreValue)
440{
441	Resume();
442	Unset();
443	// set the new values
444	fIndex = index;
445	if (fIndex)
446		fIndex->_AddIterator(this);
447	fInitialized = fIndex;
448	// get the attribute node's first entry
449	if (fIndex) {
450		// get the first node
451		bool found = true;
452		if (ignoreValue)
453			fIndex->fAttributes->GetIterator(&fIterator.fIterator);
454		else {
455			found = fIndex->fAttributes->FindFirst(PrimaryKey(key, length),
456												   &(fIterator.fIterator));
457		}
458		// get the first entry
459		if (found) {
460			if (Node **nodeP = fIterator.GetCurrent()) {
461				fNode = *nodeP;
462				fEntry = fNode->GetFirstReferrer();
463				if (!fEntry)
464					BaseClass::GetNext();
465				if (Attribute **attribute = fIterator.fIterator.GetCurrent()) {
466					const uint8 *attrKey;
467					size_t attrKeyLength;
468					(*attribute)->GetKey(&attrKey, &attrKeyLength);
469					if (!ignoreValue
470						&& compare_keys(attrKey, attrKeyLength, key, length,
471										fIndex->GetType()) != 0) {
472						Unset();
473					}
474				}
475			}
476		}
477	}
478	return fEntry;
479}
480
481// Unset
482void
483AttributeIndexImpl::Iterator::Unset()
484{
485	if (fIndex) {
486		fIndex->_RemoveIterator(this);
487		fIndex = NULL;
488	}
489	BaseClass::Unset();
490}
491
492// EntryRemoved
493void
494AttributeIndexImpl::Iterator::EntryRemoved(Entry */*entry*/)
495{
496	Resume();
497	fIsNext = BaseClass::GetNext();
498	Suspend();
499}
500
501// NodeRemoved
502void
503AttributeIndexImpl::Iterator::NodeRemoved(Node */*node*/)
504{
505	Resume();
506	fEntry = NULL;
507	fIsNext = BaseClass::GetNext();
508	Suspend();
509}
510
511