1e9e74b7bSStephan Aßmus/*
209d44cecSStephan Aßmus * Copyright 2009-2013, Stephan A��mus <superstippi@gmx.de>
33369e03dSAndrew Lindesay * Copyright 2018, Andrew Lindesay <apl@lindesay.co.nz>
4e9e74b7bSStephan Aßmus * All rights reserved. Distributed under the terms of the MIT License.
5e9e74b7bSStephan Aßmus */
6e9e74b7bSStephan Aßmus#ifndef LIST_H
7e9e74b7bSStephan Aßmus#define LIST_H
8e9e74b7bSStephan Aßmus
9e9e74b7bSStephan Aßmus
10e9e74b7bSStephan Aßmus#include <new>
1129f98e1fSAndrew Lindesay#include <stdio.h>
12e9e74b7bSStephan Aßmus#include <stdlib.h>
132ae82f9fSStephan Aßmus#include <string.h>
14e9e74b7bSStephan Aßmus
15e9e74b7bSStephan Aßmus#include <SupportDefs.h>
16e9e74b7bSStephan Aßmus
17e9e74b7bSStephan Aßmus
183094fef3SAndrew Lindesay#define BINARY_SEARCH_LINEAR_THRESHOLD 4
193094fef3SAndrew Lindesay
203094fef3SAndrew Lindesay
21e9e74b7bSStephan Aßmustemplate <typename ItemType, bool PlainOldData, uint32 BlockSize = 8>
22e9e74b7bSStephan Aßmusclass List {
23e9e74b7bSStephan Aßmus	typedef List<ItemType, PlainOldData, BlockSize> SelfType;
243369e03dSAndrew Lindesay	typedef int32 (*CompareItemFn)(const ItemType& one, const ItemType& two);
253369e03dSAndrew Lindesay	typedef int32 (*CompareContextFn)(const void* context,
263369e03dSAndrew Lindesay		const ItemType& item);
27e9e74b7bSStephan Aßmuspublic:
28e9e74b7bSStephan Aßmus	List()
29e9e74b7bSStephan Aßmus		:
30e9e74b7bSStephan Aßmus		fItems(NULL),
31e9e74b7bSStephan Aßmus		fCount(0),
323369e03dSAndrew Lindesay		fAllocatedCount(0),
333369e03dSAndrew Lindesay		fCompareItemsFunction(NULL),
343369e03dSAndrew Lindesay		fCompareContextFunction(NULL)
353369e03dSAndrew Lindesay	{
363369e03dSAndrew Lindesay	}
373369e03dSAndrew Lindesay
383369e03dSAndrew Lindesay	List(CompareItemFn compareItemsFunction,
393369e03dSAndrew Lindesay		CompareContextFn compareContextFunction)
403369e03dSAndrew Lindesay		:
413369e03dSAndrew Lindesay		fItems(NULL),
423369e03dSAndrew Lindesay		fCount(0),
433369e03dSAndrew Lindesay		fAllocatedCount(0),
443369e03dSAndrew Lindesay		fCompareItemsFunction(compareItemsFunction),
453369e03dSAndrew Lindesay		fCompareContextFunction(compareContextFunction)
46e9e74b7bSStephan Aßmus	{
47e9e74b7bSStephan Aßmus	}
48e9e74b7bSStephan Aßmus
49e9e74b7bSStephan Aßmus	List(const SelfType& other)
50e9e74b7bSStephan Aßmus		:
51e9e74b7bSStephan Aßmus		fItems(NULL),
52e9e74b7bSStephan Aßmus		fCount(0),
533369e03dSAndrew Lindesay		fAllocatedCount(0),
543369e03dSAndrew Lindesay		fCompareItemsFunction(other.fCompareItemsFunction),
553369e03dSAndrew Lindesay		fCompareContextFunction(other.fCompareContextFunction)
56e9e74b7bSStephan Aßmus	{
573369e03dSAndrew Lindesay		_AddAllVerbatim(other);
58e9e74b7bSStephan Aßmus	}
59e9e74b7bSStephan Aßmus
60e9e74b7bSStephan Aßmus	virtual ~List()
61e9e74b7bSStephan Aßmus	{
62e9e74b7bSStephan Aßmus		if (!PlainOldData) {
63e9e74b7bSStephan Aßmus			// Make sure to call destructors of old objects.
64e9e74b7bSStephan Aßmus			_Resize(0);
65e9e74b7bSStephan Aßmus		}
66e9e74b7bSStephan Aßmus		free(fItems);
67e9e74b7bSStephan Aßmus	}
68e9e74b7bSStephan Aßmus
69e9e74b7bSStephan Aßmus	SelfType& operator=(const SelfType& other)
70e9e74b7bSStephan Aßmus	{
713369e03dSAndrew Lindesay		if (this != &other)
723369e03dSAndrew Lindesay			_AddAllVerbatim(other);
73e9e74b7bSStephan Aßmus		return *this;
74e9e74b7bSStephan Aßmus	}
75e9e74b7bSStephan Aßmus
763369e03dSAndrew Lindesay
77e9e74b7bSStephan Aßmus	bool operator==(const SelfType& other) const
78e9e74b7bSStephan Aßmus	{
79e9e74b7bSStephan Aßmus		if (this == &other)
80e9e74b7bSStephan Aßmus			return true;
81e9e74b7bSStephan Aßmus
82e9e74b7bSStephan Aßmus		if (fCount != other.fCount)
83e9e74b7bSStephan Aßmus			return false;
84e9e74b7bSStephan Aßmus		if (fCount == 0)
85e9e74b7bSStephan Aßmus			return true;
86e9e74b7bSStephan Aßmus
87e9e74b7bSStephan Aßmus		if (PlainOldData) {
88e9e74b7bSStephan Aßmus			return memcmp(fItems, other.fItems,
89e9e74b7bSStephan Aßmus				fCount * sizeof(ItemType)) == 0;
90e9e74b7bSStephan Aßmus		} else {
91e9e74b7bSStephan Aßmus			for (uint32 i = 0; i < other.fCount; i++) {
92e9e74b7bSStephan Aßmus				if (ItemAtFast(i) != other.ItemAtFast(i))
93e9e74b7bSStephan Aßmus					return false;
94e9e74b7bSStephan Aßmus			}
95e9e74b7bSStephan Aßmus		}
96e9e74b7bSStephan Aßmus		return true;
97e9e74b7bSStephan Aßmus	}
98e9e74b7bSStephan Aßmus
99e9e74b7bSStephan Aßmus	bool operator!=(const SelfType& other) const
100e9e74b7bSStephan Aßmus	{
101e9e74b7bSStephan Aßmus		return !(*this == other);
102e9e74b7bSStephan Aßmus	}
103e9e74b7bSStephan Aßmus
104e9e74b7bSStephan Aßmus	inline void Clear()
105e9e74b7bSStephan Aßmus	{
106e9e74b7bSStephan Aßmus		_Resize(0);
107e9e74b7bSStephan Aßmus	}
10887084745SMichael Lotz
109863f0b19SStephan Aßmus	inline bool IsEmpty() const
110863f0b19SStephan Aßmus	{
111863f0b19SStephan Aßmus		return fCount == 0;
112863f0b19SStephan Aßmus	}
113e9e74b7bSStephan Aßmus
114e9e74b7bSStephan Aßmus	inline int32 CountItems() const
115e9e74b7bSStephan Aßmus	{
116e9e74b7bSStephan Aßmus		return fCount;
117e9e74b7bSStephan Aßmus	}
118e9e74b7bSStephan Aßmus
1193369e03dSAndrew Lindesay/*! Note that the use of this method will depend on the list being sorted.
1203094fef3SAndrew Lindesay*/
1213094fef3SAndrew Lindesay
1223369e03dSAndrew Lindesay	inline int32 Search(const void* context) const
1233094fef3SAndrew Lindesay	{
1243369e03dSAndrew Lindesay		if (fCount == 0 || fCompareContextFunction == NULL)
1253094fef3SAndrew Lindesay			return -1;
1263094fef3SAndrew Lindesay
1273369e03dSAndrew Lindesay		return _BinarySearchBounded(context, 0, fCount - 1);
1283094fef3SAndrew Lindesay	}
1293094fef3SAndrew Lindesay
1303369e03dSAndrew Lindesay	/*! This function will add the item into the list.  If the list is sorted
1313369e03dSAndrew Lindesay	    then the item will be insert in order.  If the list is not sorted then
1323369e03dSAndrew Lindesay	    the item will be inserted at the end of the list.
1333369e03dSAndrew Lindesay	*/
1343094fef3SAndrew Lindesay
135e9e74b7bSStephan Aßmus	inline bool Add(const ItemType& copyFrom)
136e9e74b7bSStephan Aßmus	{
1373369e03dSAndrew Lindesay		if (fCompareItemsFunction != NULL) {
1383369e03dSAndrew Lindesay			return _AddOrdered(copyFrom);
139e9e74b7bSStephan Aßmus		}
1403369e03dSAndrew Lindesay
1413369e03dSAndrew Lindesay		return _AddTail(copyFrom);
142e9e74b7bSStephan Aßmus	}
143e9e74b7bSStephan Aßmus
144be42d7a9SStephan Aßmus	inline bool Add(const ItemType& copyFrom, int32 index)
145be42d7a9SStephan Aßmus	{
1463369e03dSAndrew Lindesay		// if the list is sorted then ignore the index and just insert in
1473369e03dSAndrew Lindesay		// order.
1483369e03dSAndrew Lindesay		if (fCompareItemsFunction != NULL) {
1493369e03dSAndrew Lindesay			return _AddOrdered(copyFrom);
1503369e03dSAndrew Lindesay		}
151be42d7a9SStephan Aßmus
1523369e03dSAndrew Lindesay		return _AddAtIndex(copyFrom, index);
153be42d7a9SStephan Aßmus	}
154be42d7a9SStephan Aßmus
1554bbad05eSStephan Aßmus	inline bool Remove()
156e9e74b7bSStephan Aßmus	{
1574bbad05eSStephan Aßmus		if (fCount > 0) {
158e9e74b7bSStephan Aßmus			_Resize(fCount - 1);
1594bbad05eSStephan Aßmus			return true;
1604bbad05eSStephan Aßmus		}
1614bbad05eSStephan Aßmus		return false;
162e9e74b7bSStephan Aßmus	}
1631f67148fSRene Gollent
1644bbad05eSStephan Aßmus	inline bool Remove(int32 index)
165e9e74b7bSStephan Aßmus	{
166e9e74b7bSStephan Aßmus		if (index < 0 || index >= (int32)fCount)
1674bbad05eSStephan Aßmus			return false;
168e9e74b7bSStephan Aßmus
169e9e74b7bSStephan Aßmus		if (!PlainOldData) {
170e9e74b7bSStephan Aßmus			ItemType* object = fItems + index;
171e9e74b7bSStephan Aßmus			object->~ItemType();
172e9e74b7bSStephan Aßmus		}
173e9e74b7bSStephan Aßmus
174e9e74b7bSStephan Aßmus		int32 nextIndex = index + 1;
175e75fda02SStephan Aßmus		if ((int32)fCount > nextIndex) {
176e9e74b7bSStephan Aßmus			memcpy(fItems + index, fItems + nextIndex,
177e9e74b7bSStephan Aßmus				(fCount - nextIndex) * sizeof(ItemType));
178e75fda02SStephan Aßmus		}
1791f67148fSRene Gollent
180e9e74b7bSStephan Aßmus		fCount--;
1814bbad05eSStephan Aßmus		return true;
182e9e74b7bSStephan Aßmus	}
183e9e74b7bSStephan Aßmus
1844bbad05eSStephan Aßmus	inline bool Remove(const ItemType& item)
1852c3e4eaaSStephan Aßmus	{
1864bbad05eSStephan Aßmus		return Remove(IndexOf(item));
1872c3e4eaaSStephan Aßmus	}
1882c3e4eaaSStephan Aßmus
189036fabe9SStephan Aßmus	inline bool Replace(int32 index, const ItemType& copyFrom)
190be42d7a9SStephan Aßmus	{
1913369e03dSAndrew Lindesay		if (fCompareItemsFunction != NULL) {
1923369e03dSAndrew Lindesay			bool result = Remove(index);
1933369e03dSAndrew Lindesay			_AddOrdered(copyFrom);
1943369e03dSAndrew Lindesay			return result;
1953369e03dSAndrew Lindesay		}
1963369e03dSAndrew Lindesay
197be42d7a9SStephan Aßmus		if (index < 0 || index >= (int32)fCount)
198be42d7a9SStephan Aßmus			return false;
1991f67148fSRene Gollent
200be42d7a9SStephan Aßmus		ItemType* item = fItems + index;
201be42d7a9SStephan Aßmus		// Initialize the new object from the original.
202be42d7a9SStephan Aßmus		if (!PlainOldData) {
203be42d7a9SStephan Aßmus			item->~ItemType();
204be42d7a9SStephan Aßmus			new (item) ItemType(copyFrom);
205be42d7a9SStephan Aßmus		} else
206be42d7a9SStephan Aßmus			*item = copyFrom;
207be42d7a9SStephan Aßmus		return true;
208be42d7a9SStephan Aßmus	}
209be42d7a9SStephan Aßmus
210e9e74b7bSStephan Aßmus	inline const ItemType& ItemAt(int32 index) const
211e9e74b7bSStephan Aßmus	{
21296c5f7edSStephan Aßmus		if (index < 0 || index >= (int32)fCount)
213e9e74b7bSStephan Aßmus			return fNullItem;
214e9e74b7bSStephan Aßmus		return ItemAtFast(index);
215e9e74b7bSStephan Aßmus	}
216e9e74b7bSStephan Aßmus
217e9e74b7bSStephan Aßmus	inline const ItemType& ItemAtFast(int32 index) const
218e9e74b7bSStephan Aßmus	{
219e9e74b7bSStephan Aßmus		return *(fItems + index);
220e9e74b7bSStephan Aßmus	}
221e9e74b7bSStephan Aßmus
222e9e74b7bSStephan Aßmus	inline const ItemType& LastItem() const
223e9e74b7bSStephan Aßmus	{
22496c5f7edSStephan Aßmus		if (fCount == 0)
22596c5f7edSStephan Aßmus			return fNullItem;
226e9e74b7bSStephan Aßmus		return ItemAt((int32)fCount - 1);
227e9e74b7bSStephan Aßmus	}
228e9e74b7bSStephan Aßmus
2292c3e4eaaSStephan Aßmus	inline int32 IndexOf(const ItemType& item) const
2302c3e4eaaSStephan Aßmus	{
2312c3e4eaaSStephan Aßmus		for (uint32 i = 0; i < fCount; i++) {
2322c3e4eaaSStephan Aßmus			if (ItemAtFast(i) == item)
2332c3e4eaaSStephan Aßmus				return i;
2342c3e4eaaSStephan Aßmus		}
2352c3e4eaaSStephan Aßmus		return -1;
2362c3e4eaaSStephan Aßmus	}
2372c3e4eaaSStephan Aßmus
2382c3e4eaaSStephan Aßmus	inline bool Contains(const ItemType& item) const
2392c3e4eaaSStephan Aßmus	{
2402c3e4eaaSStephan Aßmus		return IndexOf(item) >= 0;
2412c3e4eaaSStephan Aßmus	}
2422c3e4eaaSStephan Aßmus
243e9e74b7bSStephan Aßmusprivate:
2443094fef3SAndrew Lindesay	inline int32 _BinarySearchLinearBounded(
2453094fef3SAndrew Lindesay		const void* context,
2463369e03dSAndrew Lindesay		int32 start, int32 end) const
2473094fef3SAndrew Lindesay	{
2483094fef3SAndrew Lindesay		for(int32 i = start; i <= end; i++) {
2493369e03dSAndrew Lindesay			if (fCompareContextFunction(context, ItemAtFast(i)) == 0)
2503094fef3SAndrew Lindesay				return i;
2513094fef3SAndrew Lindesay		}
2523094fef3SAndrew Lindesay
2533094fef3SAndrew Lindesay		return -1;
2543094fef3SAndrew Lindesay	}
2553094fef3SAndrew Lindesay
2563094fef3SAndrew Lindesay	inline int32 _BinarySearchBounded(
2573369e03dSAndrew Lindesay		const void* context, int32 start, int32 end) const
2583094fef3SAndrew Lindesay	{
2593094fef3SAndrew Lindesay		if (end - start < BINARY_SEARCH_LINEAR_THRESHOLD)
2603369e03dSAndrew Lindesay			return _BinarySearchLinearBounded(context, start, end);
2613094fef3SAndrew Lindesay
262b3a7d91bSAndrew Lindesay		int32 mid = start + ((end - start) >> 1);
2633094fef3SAndrew Lindesay
2643369e03dSAndrew Lindesay		if (fCompareContextFunction(context, ItemAtFast(mid)) >= 0)
2653369e03dSAndrew Lindesay			return _BinarySearchBounded(context, mid, end);
2663369e03dSAndrew Lindesay		return _BinarySearchBounded(context, start, mid - 1);
2673094fef3SAndrew Lindesay	}
2683094fef3SAndrew Lindesay
2693369e03dSAndrew Lindesay	inline void _AddAllVerbatim(const SelfType& other)
2703369e03dSAndrew Lindesay	{
2713369e03dSAndrew Lindesay		if (PlainOldData) {
2723369e03dSAndrew Lindesay			if (_Resize(other.fCount))
2733369e03dSAndrew Lindesay				memcpy(fItems, other.fItems, fCount * sizeof(ItemType));
2743369e03dSAndrew Lindesay		} else {
2753369e03dSAndrew Lindesay			// Make sure to call destructors of old objects.
2763369e03dSAndrew Lindesay			// NOTE: Another option would be to use
2773369e03dSAndrew Lindesay			// ItemType::operator=(const ItemType& other), but then
2783369e03dSAndrew Lindesay			// we would need to be careful which objects are already
2793369e03dSAndrew Lindesay			// initialized. Also ItemType would be required to implement the
2803369e03dSAndrew Lindesay			// operator, while doing it this way requires only a copy
2813369e03dSAndrew Lindesay			// constructor.
2823369e03dSAndrew Lindesay			_Resize(0);
2833369e03dSAndrew Lindesay			for (uint32 i = 0; i < other.fCount; i++) {
2843369e03dSAndrew Lindesay				if (!Add(other.ItemAtFast(i)))
2853369e03dSAndrew Lindesay					break;
2863369e03dSAndrew Lindesay			}
2873369e03dSAndrew Lindesay		}
2883369e03dSAndrew Lindesay	}
2893369e03dSAndrew Lindesay
2903369e03dSAndrew Lindesay
2913094fef3SAndrew Lindesay	inline bool _AddOrderedLinearBounded(
2923369e03dSAndrew Lindesay		const ItemType& copyFrom, int32 start, int32 end)
2933094fef3SAndrew Lindesay	{
2943094fef3SAndrew Lindesay		for(int32 i = start; i <= (end + 1); i++) {
2953094fef3SAndrew Lindesay			bool greaterBefore = (i == start)
2963369e03dSAndrew Lindesay				|| (fCompareItemsFunction(copyFrom, ItemAtFast(i - 1)) > 0);
2973094fef3SAndrew Lindesay
2983094fef3SAndrew Lindesay			if (greaterBefore) {
2993094fef3SAndrew Lindesay				bool lessAfter = (i == end + 1)
3003369e03dSAndrew Lindesay					|| (fCompareItemsFunction(copyFrom, ItemAtFast(i)) <= 0);
3013094fef3SAndrew Lindesay
3023094fef3SAndrew Lindesay				if (lessAfter)
3033369e03dSAndrew Lindesay					return _AddAtIndex(copyFrom, i);
3043094fef3SAndrew Lindesay			}
3053094fef3SAndrew Lindesay		}
3063094fef3SAndrew Lindesay
3073094fef3SAndrew Lindesay		printf("illegal state; unable to insert item into list\n");
3083094fef3SAndrew Lindesay		exit(EXIT_FAILURE);
3093094fef3SAndrew Lindesay	}
3103094fef3SAndrew Lindesay
3113094fef3SAndrew Lindesay	inline bool _AddOrderedBounded(
3123369e03dSAndrew Lindesay		const ItemType& copyFrom, int32 start, int32 end)
3133094fef3SAndrew Lindesay	{
3143094fef3SAndrew Lindesay		if(end - start < BINARY_SEARCH_LINEAR_THRESHOLD)
3153369e03dSAndrew Lindesay			return _AddOrderedLinearBounded(copyFrom, start, end);
3163094fef3SAndrew Lindesay
317b3a7d91bSAndrew Lindesay		int32 mid = start + ((end - start) >> 1);
3183094fef3SAndrew Lindesay
3193369e03dSAndrew Lindesay		if (fCompareItemsFunction(copyFrom, ItemAtFast(mid)) >= 0)
3203369e03dSAndrew Lindesay			return _AddOrderedBounded(copyFrom, mid, end);
3213369e03dSAndrew Lindesay		return _AddOrderedBounded(copyFrom, start, mid - 1);
3223369e03dSAndrew Lindesay	}
3233369e03dSAndrew Lindesay
3243369e03dSAndrew Lindesay	inline bool _AddTail(const ItemType& copyFrom)
3253369e03dSAndrew Lindesay	{
3263369e03dSAndrew Lindesay		if (_Resize(fCount + 1)) {
3273369e03dSAndrew Lindesay			ItemType* item = fItems + fCount - 1;
3283369e03dSAndrew Lindesay			// Initialize the new object from the original.
3293369e03dSAndrew Lindesay			if (!PlainOldData)
3303369e03dSAndrew Lindesay				new (item) ItemType(copyFrom);
3313369e03dSAndrew Lindesay			else
3323369e03dSAndrew Lindesay				*item = copyFrom;
3333369e03dSAndrew Lindesay			return true;
3343369e03dSAndrew Lindesay		}
3353369e03dSAndrew Lindesay		return false;
3363369e03dSAndrew Lindesay	}
3373369e03dSAndrew Lindesay
3383369e03dSAndrew Lindesay
3393369e03dSAndrew Lindesay	inline bool _AddAtIndex(const ItemType& copyFrom, int32 index)
3403369e03dSAndrew Lindesay	{
3413369e03dSAndrew Lindesay		if (index < 0 || index > (int32)fCount)
3423369e03dSAndrew Lindesay			return false;
3433369e03dSAndrew Lindesay
3443369e03dSAndrew Lindesay		if (!_Resize(fCount + 1))
3453369e03dSAndrew Lindesay			return false;
3463369e03dSAndrew Lindesay
3473369e03dSAndrew Lindesay		int32 nextIndex = index + 1;
3483369e03dSAndrew Lindesay		if ((int32)fCount > nextIndex)
3493369e03dSAndrew Lindesay			memmove(fItems + nextIndex, fItems + index,
3503369e03dSAndrew Lindesay				(fCount - nextIndex) * sizeof(ItemType));
3513369e03dSAndrew Lindesay
3523369e03dSAndrew Lindesay		ItemType* item = fItems + index;
3533369e03dSAndrew Lindesay		if (!PlainOldData)
3543369e03dSAndrew Lindesay			new (item) ItemType(copyFrom);
3553369e03dSAndrew Lindesay		else
3563369e03dSAndrew Lindesay			*item = copyFrom;
3573369e03dSAndrew Lindesay
3583369e03dSAndrew Lindesay		return true;
3593369e03dSAndrew Lindesay	}
3603369e03dSAndrew Lindesay
3613369e03dSAndrew Lindesay
3623369e03dSAndrew Lindesay	inline bool _AddOrdered(const ItemType& copyFrom)
3633369e03dSAndrew Lindesay	{
3643369e03dSAndrew Lindesay		// special case