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