xref: /haiku/src/add-ons/kernel/file_systems/ramfs/AttributeIndexImpl.cpp (revision b028e77473189065f2baefc6f5e10d451cf591e2) 
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
18 template<typename Key>
19 static inline
20 int
21 compare_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
31 static
32 int
33 compare_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
64 class AttributeIndexImpl::PrimaryKey {
65 public:
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
80 class AttributeIndexImpl::GetPrimaryKey {
81 public:
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
94 class AttributeIndexImpl::PrimaryKeyCompare
95 {
96 public:
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
111 template<typename AttributeIterator>
112 class AttributeNodeIterator {
113 public:
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
138 class AttributeIndexImpl::AttributeTree
139 	: public TwoKeyAVLTree<Attribute*, PrimaryKey, PrimaryKeyCompare,
140 						   GetPrimaryKey> {
141 public:
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
157 class AttributeIndexImpl::Iterator
158 	: public NodeEntryIterator<
159 		AttributeNodeIterator<AttributeTree::Iterator> >,
160 	  public DLListLinkImpl<Iterator>, public EntryListener,
161 	  public NodeListener {
162 public:
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 
179 private:
180 	typedef NodeEntryIterator<
181 		AttributeNodeIterator<AttributeTree::Iterator> > BaseClass;
182 
183 private:
184 	AttributeIndexImpl	*fIndex;
185 };
186 
187 
188 // IteratorList
189 class AttributeIndexImpl::IteratorList : public DLList<Iterator> {};
190 
191 
192 // AttributeIndexImpl
193 
194 // constructor
195 AttributeIndexImpl::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
206 AttributeIndexImpl::~AttributeIndexImpl()
207 {
208 	if (fIterators) {
209 		// unset the iterators
210 		for (Iterator *iterator = fIterators->GetFirst();
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
228 int32
229 AttributeIndexImpl::CountEntries() const
230 {
231 	return fAttributes->CountItems();
232 }
233 
234 // Changed
235 status_t
236 AttributeIndexImpl::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->GetFirst();
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
275 status_t
276 AttributeIndexImpl::Added(Attribute *attribute)
277 {
278 PRINT(("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
294 bool
295 AttributeIndexImpl::Removed(Attribute *attribute)
296 {
297 PRINT(("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
308 AbstractIndexEntryIterator *
309 AttributeIndexImpl::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
322 AbstractIndexEntryIterator *
323 AttributeIndexImpl::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
338 void
339 AttributeIndexImpl::_AddIterator(Iterator *iterator)
340 {
341 	fIterators->Insert(iterator);
342 }
343 
344 // _RemoveIterator
345 void
346 AttributeIndexImpl::_RemoveIterator(Iterator *iterator)
347 {
348 	fIterators->Remove(iterator);
349 }
350 
351 
352 // Iterator
353 
354 // constructor
355 AttributeIndexImpl::Iterator::Iterator()
356 	: BaseClass(),
357 	  fIndex(NULL)
358 {
359 }
360 
361 // destructor
362 AttributeIndexImpl::Iterator::~Iterator()
363 {
364 	SetTo(NULL, NULL, 0);
365 }
366 
367 // GetCurrent
368 Entry *
369 AttributeIndexImpl::Iterator::GetCurrent()
370 {
371 	return BaseClass::GetCurrent();
372 }
373 
374 // GetCurrent
375 Entry *
376 AttributeIndexImpl::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
401 status_t
402 AttributeIndexImpl::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
423 status_t
424 AttributeIndexImpl::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
441 bool
442 AttributeIndexImpl::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
486 void
487 AttributeIndexImpl::Iterator::Unset()
488 {
489 	if (fIndex) {
490 		fIndex->_RemoveIterator(this);
491 		fIndex = NULL;
492 	}
493 	BaseClass::Unset();
494 }
495 
496 // EntryRemoved
497 void
498 AttributeIndexImpl::Iterator::EntryRemoved(Entry */*entry*/)
499 {
500 	Resume();
501 	fIsNext = BaseClass::GetNext();
502 	Suspend();
503 }
504 
505 // NodeRemoved
506 void
507 AttributeIndexImpl::Iterator::NodeRemoved(Node */*node*/)
508 {
509 	Resume();
510 	fEntry = NULL;
511 	fIsNext = BaseClass::GetNext();
512 	Suspend();
513 }
514 
515