xref: /haiku/src/add-ons/kernel/file_systems/ramfs/AttributeIndexImpl.cpp (revision 4a55cc230cf7566cadcbb23b1928eefff8aea9a2) 
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
21 template<typename Key>
22 static inline
23 int
24 compare_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
34 static
35 int
36 compare_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
67 class AttributeIndexImpl::PrimaryKey {
68 public:
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
85 class AttributeIndexImpl::GetPrimaryKey {
86 public:
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
99 class AttributeIndexImpl::PrimaryKeyCompare
100 {
101 public:
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
116 template<typename AttributeIterator>
117 class AttributeNodeIterator {
118 public:
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
143 class AttributeIndexImpl::AttributeTree
144 	: public TwoKeyAVLTree<Attribute*, PrimaryKey, PrimaryKeyCompare,
145 						   GetPrimaryKey> {
146 public:
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
158 class AttributeIndexImpl::Iterator
159 	: public NodeEntryIterator<
160 		AttributeNodeIterator<AttributeTree::Iterator> >,
161 	  public DoublyLinkedListLinkImpl<Iterator>, public EntryListener,
162 	  public NodeListener {
163 public:
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 
180 private:
181 	typedef NodeEntryIterator<
182 		AttributeNodeIterator<AttributeTree::Iterator> > BaseClass;
183 
184 private:
185 	AttributeIndexImpl	*fIndex;
186 };
187 
188 
189 // IteratorList
190 class AttributeIndexImpl::IteratorList : public DoublyLinkedList<Iterator> {};
191 
192 
193 // AttributeIndexImpl
194 
195 // constructor
196 AttributeIndexImpl::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
207 AttributeIndexImpl::~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
229 int32
230 AttributeIndexImpl::CountEntries() const
231 {
232 	return fAttributes->CountItems();
233 }
234 
235 // Changed
236 status_t
237 AttributeIndexImpl::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
276 status_t
277 AttributeIndexImpl::Added(Attribute *attribute)
278 {
279 PRINT("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
295 bool
296 AttributeIndexImpl::Removed(Attribute *attribute)
297 {
298 PRINT("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
309 AbstractIndexEntryIterator *
310 AttributeIndexImpl::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
323 AbstractIndexEntryIterator *
324 AttributeIndexImpl::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
339 void
340 AttributeIndexImpl::_AddIterator(Iterator *iterator)
341 {
342 	fIterators->Insert(iterator);
343 }
344 
345 // _RemoveIterator
346 void
347 AttributeIndexImpl::_RemoveIterator(Iterator *iterator)
348 {
349 	fIterators->Remove(iterator);
350 }
351 
352 
353 // Iterator
354 
355 // constructor
356 AttributeIndexImpl::Iterator::Iterator()
357 	: BaseClass(),
358 	  fIndex(NULL)
359 {
360 }
361 
362 // destructor
363 AttributeIndexImpl::Iterator::~Iterator()
364 {
365 	SetTo(NULL, NULL, 0);
366 }
367 
368 // GetCurrent
369 Entry *
370 AttributeIndexImpl::Iterator::GetCurrent()
371 {
372 	return BaseClass::GetCurrent();
373 }
374 
375 // GetCurrent
376 Entry *
377 AttributeIndexImpl::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
402 status_t
403 AttributeIndexImpl::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
424 status_t
425 AttributeIndexImpl::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
442 bool
443 AttributeIndexImpl::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
487 void
488 AttributeIndexImpl::Iterator::Unset()
489 {
490 	if (fIndex) {
491 		fIndex->_RemoveIterator(this);
492 		fIndex = NULL;
493 	}
494 	BaseClass::Unset();
495 }
496 
497 // EntryRemoved
498 void
499 AttributeIndexImpl::Iterator::EntryRemoved(Entry */*entry*/)
500 {
501 	Resume();
502 	fIsNext = BaseClass::GetNext();
503 	Suspend();
504 }
505 
506 // NodeRemoved
507 void
508 AttributeIndexImpl::Iterator::NodeRemoved(Node */*node*/)
509 {
510 	Resume();
511 	fEntry = NULL;
512 	fIsNext = BaseClass::GetNext();
513 	Suspend();
514 }
515 
516