xref: /haiku/src/kits/support/List.cpp (revision 1294543de9ac0eff000eaea1b18368c36435d08e) 
1 /*
2  * Copyright 2001-2009, Haiku, Inc. All Rights Reserved.
3  * Distributed under the terms of the MIT License.
4  *
5  * Authors:
6  *		The Storage kit Team
7  *		Isaac Yonemoto
8  *		Rene Gollent
9  *		Stephan Aßmus
10  */
11 
12 //!	BList class provides storage for pointers. Not thread safe.
13 
14 
15 #include <List.h>
16 
17 #include <stdio.h>
18 #include <stdlib.h>
19 #include <string.h>
20 
21 
22 // helper function
23 static inline void
24 move_items(void** items, int32 offset, int32 count)
25 {
26 	if (count > 0 && offset != 0)
27 		memmove(items + offset, items, count * sizeof(void*));
28 }
29 
30 
31 BList::BList(int32 count)
32 	:
33 	fObjectList(NULL),
34 	fPhysicalSize(0),
35 	fItemCount(0),
36 	fBlockSize(count),
37 	fResizeThreshold(0)
38 {
39 	if (fBlockSize <= 0)
40 		fBlockSize = 1;
41 	_ResizeArray(fItemCount);
42 }
43 
44 
45 BList::BList(const BList& anotherList)
46 	:
47 	fObjectList(NULL),
48 	fPhysicalSize(0),
49 	fItemCount(0),
50 	fBlockSize(anotherList.fBlockSize)
51 {
52 	*this = anotherList;
53 }
54 
55 
56 BList::~BList()
57 {
58 	free(fObjectList);
59 }
60 
61 
62 BList&
63 BList::operator=(const BList& list)
64 {
65 	if (&list != this) {
66 		fBlockSize = list.fBlockSize;
67 		if (_ResizeArray(list.fItemCount)) {
68 			fItemCount = list.fItemCount;
69 			memcpy(fObjectList, list.fObjectList, fItemCount * sizeof(void*));
70 		}
71 	}
72 
73 	return *this;
74 }
75 
76 
77 bool
78 BList::operator==(const BList& list) const
79 {
80 	if (&list == this)
81 		return true;
82 
83 	if (list.fItemCount != fItemCount)
84 		return false;
85 
86 	if (fItemCount > 0) {
87 		return memcmp(fObjectList, list.fObjectList,
88 			fItemCount * sizeof(void*)) == 0;
89 	}
90 
91 	return true;
92 }
93 
94 
95 bool
96 BList::operator!=(const BList& list) const
97 {
98 	return !(*this == list);
99 }
100 
101 
102 bool
103 BList::AddItem(void* item, int32 index)
104 {
105 	if (index < 0 || index > fItemCount)
106 		return false;
107 
108 	bool result = true;
109 
110 	if (fItemCount + 1 > fPhysicalSize)
111 		result = _ResizeArray(fItemCount + 1);
112 	if (result) {
113 		++fItemCount;
114 		move_items(fObjectList + index, 1, fItemCount - index - 1);
115 		fObjectList[index] = item;
116 	}
117 	return result;
118 }
119 
120 
121 bool
122 BList::AddItem(void* item)
123 {
124 	bool result = true;
125 	if (fPhysicalSize > fItemCount) {
126 		fObjectList[fItemCount] = item;
127 		++fItemCount;
128 	} else {
129 		if ((result = _ResizeArray(fItemCount + 1))) {
130 			fObjectList[fItemCount] = item;
131 			++fItemCount;
132 		}
133 	}
134 	return result;
135 }
136 
137 
138 bool
139 BList::AddList(const BList* list, int32 index)
140 {
141 	bool result = (list && index >= 0 && index <= fItemCount);
142 	if (result && list->fItemCount > 0) {
143 		int32 count = list->fItemCount;
144 		if (fItemCount + count > fPhysicalSize)
145 			result = _ResizeArray(fItemCount + count);
146 		if (result) {
147 			fItemCount += count;
148 			move_items(fObjectList + index, count, fItemCount - index - count);
149 			memcpy(fObjectList + index, list->fObjectList,
150 				list->fItemCount * sizeof(void*));
151 		}
152 	}
153 	return result;
154 }
155 
156 
157 bool
158 BList::AddList(const BList* list)
159 {
160 	bool result = (list != NULL);
161 	if (result && list->fItemCount > 0) {
162 		int32 index = fItemCount;
163 		int32 count = list->fItemCount;
164 		if (fItemCount + count > fPhysicalSize)
165 			result = _ResizeArray(fItemCount + count);
166 		if (result) {
167 			fItemCount += count;
168 			memcpy(fObjectList + index, list->fObjectList,
169 				list->fItemCount * sizeof(void*));
170 		}
171 	}
172 	return result;
173 }
174 
175 
176 bool
177 BList::RemoveItem(void* item)
178 {
179 	int32 index = IndexOf(item);
180 	bool result = (index >= 0);
181 	if (result)
182 		RemoveItem(index);
183 	return result;
184 }
185 
186 
187 void*
188 BList::RemoveItem(int32 index)
189 {
190 	void* item = NULL;
191 	if (index >= 0 && index < fItemCount) {
192 		item = fObjectList[index];
193 		move_items(fObjectList + index + 1, -1, fItemCount - index - 1);
194 		--fItemCount;
195 		if (fItemCount <= fResizeThreshold)
196 			_ResizeArray(fItemCount);
197 	}
198 	return item;
199 }
200 
201 
202 bool
203 BList::RemoveItems(int32 index, int32 count)
204 {
205 	bool result = (index >= 0 && index <= fItemCount);
206 	if (result) {
207 		if (index + count > fItemCount)
208 			count = fItemCount - index;
209 		if (count > 0) {
210 			move_items(fObjectList + index + count, -count,
211 					   fItemCount - index - count);
212 			fItemCount -= count;
213 			if (fItemCount <= fResizeThreshold)
214 				_ResizeArray(fItemCount);
215 		} else
216 			result = false;
217 	}
218 	return result;
219 }
220 
221 
222 bool
223 BList::ReplaceItem(int32 index, void* newItem)
224 {
225 	bool result = false;
226 
227 	if (index >= 0 && index < fItemCount) {
228 		fObjectList[index] = newItem;
229 		result = true;
230 	}
231 	return result;
232 }
233 
234 
235 void
236 BList::MakeEmpty()
237 {
238 	fItemCount = 0;
239 	_ResizeArray(0);
240 }
241 
242 
243 // #pragma mark - Reordering items.
244 
245 
246 void
247 BList::SortItems(int (*compareFunc)(const void*, const void*))
248 {
249 	if (compareFunc)
250 		qsort(fObjectList, fItemCount, sizeof(void*), compareFunc);
251 }
252 
253 
254 bool
255 BList::SwapItems(int32 indexA, int32 indexB)
256 {
257 	bool result = false;
258 
259 	if (indexA >= 0 && indexA < fItemCount
260 		&& indexB >= 0 && indexB < fItemCount) {
261 
262 		void* tmpItem = fObjectList[indexA];
263 		fObjectList[indexA] = fObjectList[indexB];
264 		fObjectList[indexB] = tmpItem;
265 
266 		result = true;
267 	}
268 
269 	return result;
270 }
271 
272 
273 /*! This moves a list item from posititon a to position b, moving the
274 	appropriate block of list elements to make up for the move. For example,
275 	in the array:
276 	A B C D E F G H I J
277 		Moveing 1(B)->6(G) would result in this:
278 	A C D E F G B H I J
279 */
280 bool
281 BList::MoveItem(int32 fromIndex, int32 toIndex)
282 {
283 	if ((fromIndex >= fItemCount) || (toIndex >= fItemCount) || (fromIndex < 0)
284 		|| (toIndex < 0)) {
285 		return false;
286 	}
287 
288 	void* tmpMover = fObjectList[fromIndex];
289 	if (fromIndex < toIndex) {
290 		memmove(fObjectList + fromIndex, fObjectList + fromIndex + 1,
291 			(toIndex - fromIndex) * sizeof(void*));
292 	} else if (fromIndex > toIndex) {
293 		memmove(fObjectList + toIndex + 1, fObjectList + toIndex,
294 			(fromIndex - toIndex) * sizeof(void*));
295 	};
296 	fObjectList[toIndex] = tmpMover;
297 
298 	return true;
299 }
300 
301 
302 // #pragma mark - Retrieving items.
303 
304 
305 void*
306 BList::ItemAt(int32 index) const
307 {
308 	void *item = NULL;
309 	if (index >= 0 && index < fItemCount)
310 		item = fObjectList[index];
311 	return item;
312 }
313 
314 
315 void*
316 BList::FirstItem() const
317 {
318 	void *item = NULL;
319 	if (fItemCount > 0)
320 		item = fObjectList[0];
321 	return item;
322 }
323 
324 
325 void*
326 BList::ItemAtFast(int32 index) const
327 {
328 	return fObjectList[index];
329 }
330 
331 
332 void*
333 BList::Items() const
334 {
335 	return fObjectList;
336 }
337 
338 
339 void*
340 BList::LastItem() const
341 {
342 	void* item = NULL;
343 	if (fItemCount > 0)
344 		item = fObjectList[fItemCount - 1];
345 	return item;
346 }
347 
348 
349 // #pragma mark - Querying the list.
350 
351 
352 bool
353 BList::HasItem(void* item) const
354 {
355 	return (IndexOf(item) >= 0);
356 }
357 
358 
359 bool
360 BList::HasItem(const void* item) const
361 {
362 	return (IndexOf(item) >= 0);
363 }
364 
365 
366 int32
367 BList::IndexOf(void* item) const
368 {
369 	for (int32 i = 0; i < fItemCount; i++) {
370 		if (fObjectList[i] == item)
371 			return i;
372 	}
373 	return -1;
374 }
375 
376 
377 int32
378 BList::IndexOf(const void* item) const
379 {
380 	for (int32 i = 0; i < fItemCount; i++) {
381 		if (fObjectList[i] == item)
382 			return i;
383 	}
384 	return -1;
385 }
386 
387 
388 int32
389 BList::CountItems() const
390 {
391 	return fItemCount;
392 }
393 
394 
395 bool
396 BList::IsEmpty() const
397 {
398 	return fItemCount == 0;
399 }
400 
401 
402 // #pragma mark - Iterating over the list.
403 
404 /*!	Iterate a function over the whole list. If the function outputs a true
405 	value, then the process is terminated.
406 */
407 void
408 BList::DoForEach(bool (*func)(void*))
409 {
410 	if (func == NULL)
411 		return;
412 
413 	bool terminate = false;
414 	int32 index = 0;
415 
416 	while ((!terminate) && (index < fItemCount)) {
417 		terminate = func(fObjectList[index]);
418 		index++;
419 	}
420 }
421 
422 
423 /*!	Iterate a function over the whole list. If the function outputs a true
424 	value, then the process is terminated. This version takes an additional
425 	argument which is passed to the function.
426 */
427 void
428 BList::DoForEach(bool (*func)(void*, void*), void* arg)
429 {
430 	if (func == NULL)
431 		return;
432 
433 	bool terminate = false; int32 index = 0;
434 	while ((!terminate) && (index < fItemCount)) {
435 		terminate = func(fObjectList[index], arg);
436 		index++;
437 	}
438 }
439 
440 
441 #if (__GNUC__ == 2)
442 
443 // This is somewhat of a hack for backwards compatibility -
444 // the reason these functions are defined this way rather than simply
445 // being made private members is that if they are included, then whenever
446 // gcc encounters someone calling AddList() with a non-const BList pointer,
447 // it will try to use the private version and fail with a compiler error.
448 
449 // obsolete AddList(BList* list, int32 index) and AddList(BList* list)
450 // AddList
451 extern "C" bool
452 AddList__5BListP5BListl(BList* self, BList* list, int32 index)
453 {
454 	return self->AddList((const BList*)list, index);
455 }
456 
457 // AddList
458 extern "C" bool
459 AddList__5BListP5BList(BList* self, BList* list)
460 {
461 	return self->AddList((const BList*)list);
462 }
463 #endif
464 
465 // FBC
466 void BList::_ReservedList1() {}
467 void BList::_ReservedList2() {}
468 
469 
470 /*!	Resizes fObjectList to be large enough to contain count items.
471 */
472 bool
473 BList::_ResizeArray(int32 count)
474 {
475 	bool result = true;
476 	// calculate the new physical size
477 	// by doubling the existing size
478 	// until we can hold at least count items
479 	int32 newSize = fPhysicalSize > 0 ? fPhysicalSize : fBlockSize;
480 	int32 targetSize = count;
481 	if (targetSize <= 0)
482 		targetSize = fBlockSize;
483 	if (targetSize > fPhysicalSize) {
484 		while (newSize < targetSize)
485 			newSize <<= 1;
486 	} else if (targetSize <= fResizeThreshold) {
487 		newSize = fResizeThreshold;
488 	}
489 
490 	// resize if necessary
491 	if (newSize != fPhysicalSize) {
492 		void** newObjectList
493 			= (void**)realloc(fObjectList, newSize * sizeof(void*));
494 		if (newObjectList) {
495 			fObjectList = newObjectList;
496 			fPhysicalSize = newSize;
497 			// set our lower bound to either 1/4
498 			//of the current physical size, or 0
499 			fResizeThreshold = fPhysicalSize >> 2 >= fBlockSize
500 				? fPhysicalSize >> 2 : 0;
501 		} else
502 			result = false;
503 	}
504 	return result;
505 }
506 
507