1/*
2 * Copyright 2009-2013, Stephan A��mus <superstippi@gmx.de>
3 * Copyright 2018, Andrew Lindesay <apl@lindesay.co.nz>
4 * All rights reserved. Distributed under the terms of the MIT License.
5 */
6#ifndef LIST_H
7#define LIST_H
8
9
10#include <new>
11#include <stdio.h>
12#include <stdlib.h>
13#include <string.h>
14
15#include <SupportDefs.h>
16
17
18#define BINARY_SEARCH_LINEAR_THRESHOLD 4
19
20
21template <typename ItemType, bool PlainOldData, uint32 BlockSize = 8>
22class List {
23	typedef List<ItemType, PlainOldData, BlockSize> SelfType;
24	typedef int32 (*CompareItemFn)(const ItemType& one, const ItemType& two);
25	typedef int32 (*CompareContextFn)(const void* context,
26		const ItemType& item);
27public:
28	List()
29		:
30		fItems(NULL),
31		fCount(0),
32		fAllocatedCount(0),
33		fCompareItemsFunction(NULL),
34		fCompareContextFunction(NULL)
35	{
36	}
37
38	List(CompareItemFn compareItemsFunction,
39		CompareContextFn compareContextFunction)
40		:
41		fItems(NULL),
42		fCount(0),
43		fAllocatedCount(0),
44		fCompareItemsFunction(compareItemsFunction),
45		fCompareContextFunction(compareContextFunction)
46	{
47	}
48
49	List(const SelfType& other)
50		:
51		fItems(NULL),
52		fCount(0),
53		fAllocatedCount(0),
54		fCompareItemsFunction(other.fCompareItemsFunction),
55		fCompareContextFunction(other.fCompareContextFunction)
56	{
57		_AddAllVerbatim(other);
58	}
59
60	virtual ~List()
61	{
62		if (!PlainOldData) {
63			// Make sure to call destructors of old objects.
64			_Resize(0);
65		}
66		free(fItems);
67	}
68
69	SelfType& operator=(const SelfType& other)
70	{
71		if (this != &other)
72			_AddAllVerbatim(other);
73		return *this;
74	}
75
76
77	bool operator==(const SelfType& other) const
78	{
79		if (this == &other)
80			return true;
81
82		if (fCount != other.fCount)
83			return false;
84		if (fCount == 0)
85			return true;
86
87		if (PlainOldData) {
88			return memcmp(fItems, other.fItems,
89				fCount * sizeof(ItemType)) == 0;
90		} else {
91			for (uint32 i = 0; i < other.fCount; i++) {
92				if (ItemAtFast(i) != other.ItemAtFast(i))
93					return false;
94			}
95		}
96		return true;
97	}
98
99	bool operator!=(const SelfType& other) const
100	{
101		return !(*this == other);
102	}
103
104	inline void Clear()
105	{
106		_Resize(0);
107	}
108
109	inline bool IsEmpty() const
110	{
111		return fCount == 0;
112	}
113
114	inline int32 CountItems() const
115	{
116		return fCount;
117	}
118
119/*! Note that the use of this method will depend on the list being sorted.
120*/
121
122	inline int32 Search(const void* context) const
123	{
124		if (fCount == 0 || fCompareContextFunction == NULL)
125			return -1;
126
127		return _BinarySearchBounded(context, 0, fCount - 1);
128	}
129
130	/*! This function will add the item into the list.  If the list is sorted
131	    then the item will be insert in order.  If the list is not sorted then
132	    the item will be inserted at the end of the list.
133	*/
134
135	inline bool Add(const ItemType& copyFrom)
136	{
137		if (fCompareItemsFunction != NULL) {
138			return _AddOrdered(copyFrom);
139		}
140
141		return _AddTail(copyFrom);
142	}
143
144	inline bool Add(const ItemType& copyFrom, int32 index)
145	{
146		// if the list is sorted then ignore the index and just insert in
147		// order.
148		if (fCompareItemsFunction != NULL) {
149			return _AddOrdered(copyFrom);
150		}
151
152		return _AddAtIndex(copyFrom, index);
153	}
154
155	inline bool Remove()
156	{
157		if (fCount > 0) {
158			_Resize(fCount - 1);
159			return true;
160		}
161		return false;
162	}
163
164	inline bool Remove(int32 index)
165	{
166		if (index < 0 || index >= (int32)fCount)
167			return false;
168
169		if (!PlainOldData) {
170			ItemType* object = fItems + index;
171			object->~ItemType();
172		}
173
174		int32 nextIndex = index + 1;
175		if ((int32)fCount > nextIndex) {
176			memcpy(fItems + index, fItems + nextIndex,
177				(fCount - nextIndex) * sizeof(ItemType));
178		}
179
180		fCount--;
181		return true;
182	}
183
184	inline bool Remove(const ItemType& item)
185	{
186		return Remove(IndexOf(item));
187	}
188
189	inline bool Replace(int32 index, const ItemType& copyFrom)
190	{
191		if (fCompareItemsFunction != NULL) {
192			bool result = Remove(index);
193			_AddOrdered(copyFrom);
194			return result;
195		}
196
197		if (index < 0 || index >= (int32)fCount)
198			return false;
199
200		ItemType* item = fItems + index;
201		// Initialize the new object from the original.
202		if (!PlainOldData) {
203			item->~ItemType();
204			new (item) ItemType(copyFrom);
205		} else
206			*item = copyFrom;
207		return true;
208	}
209
210	inline const ItemType& ItemAt(int32 index) const
211	{
212		if (index < 0 || index >= (int32)fCount)
213			return fNullItem;
214		return ItemAtFast(index);
215	}
216
217	inline const ItemType& ItemAtFast(int32 index) const
218	{
219		return *(fItems + index);
220	}
221
222	inline const ItemType& LastItem() const
223	{
224		if (fCount == 0)
225			return fNullItem;
226		return ItemAt((int32)fCount - 1);
227	}
228
229	inline int32 IndexOf(const ItemType& item) const
230	{
231		for (uint32 i = 0; i < fCount; i++) {
232			if (ItemAtFast(i) == item)
233				return i;
234		}
235		return -1;
236	}
237
238	inline bool Contains(const ItemType& item) const
239	{
240		return IndexOf(item) >= 0;
241	}
242
243private:
244	inline int32 _BinarySearchLinearBounded(
245		const void* context,
246		int32 start, int32 end) const
247	{
248		for(int32 i = start; i <= end; i++) {
249			if (fCompareContextFunction(context, ItemAtFast(i)) == 0)
250				return i;
251		}
252
253		return -1;
254	}
255
256	inline int32 _BinarySearchBounded(
257		const void* context, int32 start, int32 end) const
258	{
259		if (end - start < BINARY_SEARCH_LINEAR_THRESHOLD)
260			return _BinarySearchLinearBounded(context, start, end);
261
262		int32 mid = start + ((end - start) >> 1);
263
264		if (fCompareContextFunction(context, ItemAtFast(mid)) >= 0)
265			return _BinarySearchBounded(context, mid, end);
266		return _BinarySearchBounded(context, start, mid - 1);
267	}
268
269	inline void _AddAllVerbatim(const SelfType& other)
270	{
271		if (PlainOldData) {
272			if (_Resize(other.fCount))
273				memcpy(fItems, other.fItems, fCount * sizeof(ItemType));
274		} else {
275			// Make sure to call destructors of old objects.
276			// NOTE: Another option would be to use
277			// ItemType::operator=(const ItemType& other), but then
278			// we would need to be careful which objects are already
279			// initialized. Also ItemType would be required to implement the
280			// operator, while doing it this way requires only a copy
281			// constructor.
282			_Resize(0);
283			for (uint32 i = 0; i < other.fCount; i++) {
284				if (!Add(other.ItemAtFast(i)))
285					break;
286			}
287		}
288	}
289
290
291	inline bool _AddOrderedLinearBounded(
292		const ItemType& copyFrom, int32 start, int32 end)
293	{
294		for(int32 i = start; i <= (end + 1); i++) {
295			bool greaterBefore = (i == start)
296				|| (fCompareItemsFunction(copyFrom, ItemAtFast(i - 1)) > 0);
297
298			if (greaterBefore) {
299				bool lessAfter = (i == end + 1)
300					|| (fCompareItemsFunction(copyFrom, ItemAtFast(i)) <= 0);
301
302				if (lessAfter)
303					return _AddAtIndex(copyFrom, i);
304			}
305		}
306
307		printf("illegal state; unable to insert item into list\n");
308		exit(EXIT_FAILURE);
309	}
310
311	inline bool _AddOrderedBounded(
312		const ItemType& copyFrom, int32 start, int32 end)
313	{
314		if(end - start < BINARY_SEARCH_LINEAR_THRESHOLD)
315			return _AddOrderedLinearBounded(copyFrom, start, end);
316
317		int32 mid = start + ((end - start) >> 1);
318
319		if (fCompareItemsFunction(copyFrom, ItemAtFast(mid)) >= 0)
320			return _AddOrderedBounded(copyFrom, mid, end);
321		return _AddOrderedBounded(copyFrom, start, mid - 1);
322	}
323
324	inline bool _AddTail(const ItemType& copyFrom)
325	{
326		if (_Resize(fCount + 1)) {
327			ItemType* item = fItems + fCount - 1;
328			// Initialize the new object from the original.
329			if (!PlainOldData)
330				new (item) ItemType(copyFrom);
331			else
332				*item = copyFrom;
333			return true;
334		}
335		return false;
336	}
337
338
339	inline bool _AddAtIndex(const ItemType& copyFrom, int32 index)
340	{
341		if (index < 0 || index > (int32)fCount)
342			return false;
343
344		if (!_Resize(fCount + 1))
345			return false;
346
347		int32 nextIndex = index + 1;
348		if ((int32)fCount > nextIndex)
349			memmove(fItems + nextIndex, fItems + index,
350				(fCount - nextIndex) * sizeof(ItemType));
351
352		ItemType* item = fItems + index;
353		if (!PlainOldData)
354			new (item) ItemType(copyFrom);
355		else
356			*item = copyFrom;
357
358		return true;
359	}
360
361
362	inline bool _AddOrdered(const ItemType& copyFrom)
363	{
364		// special case
365		if (fCount == 0
366			|| fCompareItemsFunction(copyFrom, ItemAtFast(fCount - 1)) > 0) {
367			return _AddTail(copyFrom);
368		}
369
370		return _AddOrderedBounded(copyFrom, 0, fCount - 1);
371	}
372
373	inline bool _Resize(uint32 count)
374	{
375		if (count > fAllocatedCount) {
376			uint32 allocationCount = (count + BlockSize - 1)
377				/ BlockSize * BlockSize;
378			ItemType* items = reinterpret_cast<ItemType*>(
379				realloc(fItems, allocationCount * sizeof(ItemType)));
380			if (items == NULL)
381				return false;
382			fItems = items;
383
384			fAllocatedCount = allocationCount;
385		} else if (count < fCount) {
386			if (!PlainOldData) {
387				// Uninit old objects so that we can re-use them when
388				// appending objects without the need to re-allocate.
389				for (uint32 i = count; i < fCount; i++) {
390					ItemType* object = fItems + i;
391					object->~ItemType();
392				}
393			}
394		}
395		fCount = count;
396		return true;
397	}
398
399	ItemType*			fItems;
400	ItemType			fNullItem;
401	uint32				fCount;
402	uint32				fAllocatedCount;
403	CompareItemFn		fCompareItemsFunction;
404	CompareContextFn	fCompareContextFunction;
405};
406
407
408#endif // LIST_H
409