1/*
2 * Copyright 2003, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * All rights reserved. Distributed under the terms of the MIT license.
4 */
5#ifndef TEMPLATE_LIST_H
6#define TEMPLATE_LIST_H
7
8#ifdef _KERNEL_MODE
9	#include <kernel_cpp.h>
10#else
11	#include <new>
12#endif
13
14#include <stdlib.h>
15#include <string.h>
16
17#include <SupportDefs.h>
18
19template<typename ITEM>
20class DefaultDefaultItemCreator {
21public:
22	static inline ITEM GetItem() { return ITEM(0); }
23};
24
25/*!
26	\class TemplateList
27	\brief A generic list implementation.
28*/
29template<typename ITEM,
30		 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> >
31class TemplateList {
32public:
33	typedef ITEM					item_t;
34	typedef TemplateList			list_t;
35
36private:
37	static item_t					sDefaultItem;
38	static const size_t				kDefaultChunkSize = 10;
39	static const size_t				kMaximalChunkSize = 1024 * 1024;
40
41public:
42	TemplateList(size_t chunkSize = kDefaultChunkSize);
43	~TemplateList();
44
45	inline const item_t &GetDefaultItem() const;
46	inline item_t &GetDefaultItem();
47
48	bool AddItem(const item_t &item, int32 index);
49	bool AddItem(const item_t &item);
50//	bool AddList(list_t *list, int32 index);
51//	bool AddList(list_t *list);
52
53	bool RemoveItem(const item_t &item);
54	bool RemoveItem(int32 index);
55
56	bool ReplaceItem(int32 index, const item_t &item);
57
58	bool MoveItem(int32 oldIndex, int32 newIndex);
59
60	void MakeEmpty();
61
62	int32 CountItems() const;
63	bool IsEmpty() const;
64	const item_t &ItemAt(int32 index) const;
65	item_t &ItemAt(int32 index);
66	const item_t *Items() const;
67	int32 IndexOf(const item_t &item) const;
68	bool HasItem(const item_t &item) const;
69
70	// debugging
71	int32 GetCapacity() const	{ return fCapacity; }
72
73private:
74	inline static void _MoveItems(item_t* items, int32 offset, int32 count);
75	bool _Resize(size_t count);
76
77private:
78	size_t	fCapacity;
79	size_t	fChunkSize;
80	int32	fItemCount;
81	item_t	*fItems;
82};
83
84// sDefaultItem
85template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
86typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t
87	TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem(
88		DEFAULT_ITEM_SUPPLIER::GetItem());
89
90// constructor
91template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
92TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::TemplateList(size_t chunkSize)
93	: fCapacity(0),
94	  fChunkSize(chunkSize),
95	  fItemCount(0),
96	  fItems(NULL)
97{
98	if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize)
99		fChunkSize = kDefaultChunkSize;
100	_Resize(0);
101}
102
103// destructor
104template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
105TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::~TemplateList()
106{
107	MakeEmpty();
108	free(fItems);
109}
110
111// GetDefaultItem
112template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
113inline
114const typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
115TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const
116{
117	return sDefaultItem;
118}
119
120// GetDefaultItem
121template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
122inline
123typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
124TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem()
125{
126	return sDefaultItem;
127}
128
129// _MoveItems
130template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
131inline
132void
133TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::_MoveItems(item_t* items, int32 offset, int32 count)
134{
135	if (count > 0 && offset != 0)
136		memmove(items + offset, items, count * sizeof(item_t));
137}
138
139// AddItem
140template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
141bool
142TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item, int32 index)
143{
144	bool result = (index >= 0 && index <= fItemCount
145				   && _Resize(fItemCount + 1));
146	if (result) {
147		_MoveItems(fItems + index, 1, fItemCount - index - 1);
148		new(fItems + index) item_t(item);
149	}
150	return result;
151}
152
153// AddItem
154template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
155bool
156TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item)
157{
158	bool result = true;
159	if ((int32)fCapacity > fItemCount) {
160		new(fItems + fItemCount) item_t(item);
161		fItemCount++;
162	} else {
163		if ((result = _Resize(fItemCount + 1)))
164			new(fItems + (fItemCount - 1)) item_t(item);
165	}
166	return result;
167}
168
169// These don't use the copy constructor!
170/*
171// AddList
172template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
173bool
174TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list, int32 index)
175{
176	bool result = (list && index >= 0 && index <= fItemCount);
177	if (result && list->fItemCount > 0) {
178		int32 count = list->fItemCount;
179		result = _Resize(fItemCount + count);
180		if (result) {
181			_MoveItems(fItems + index, count, fItemCount - index - count);
182			memcpy(fItems + index, list->fItems,
183				   list->fItemCount * sizeof(item_t));
184		}
185	}
186	return result;
187}
188
189// AddList
190template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
191bool
192TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list)
193{
194	bool result = (list);
195	if (result && list->fItemCount > 0) {
196		int32 index = fItemCount;
197		int32 count = list->fItemCount;
198		result = _Resize(fItemCount + count);
199		if (result) {
200			memcpy(fItems + index, list->fItems,
201				   list->fItemCount * sizeof(item_t));
202		}
203	}
204	return result;
205}
206*/
207
208// RemoveItem
209template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
210bool
211TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(const item_t &item)
212{
213	int32 index = IndexOf(item);
214	bool result = (index >= 0);
215	if (result)
216		RemoveItem(index);
217	return result;
218}
219
220// RemoveItem
221template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
222bool
223TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(int32 index)
224{
225	if (index >= 0 && index < fItemCount) {
226		fItems[index].~item_t();
227		_MoveItems(fItems + index + 1, -1, fItemCount - index - 1);
228		_Resize(fItemCount - 1);
229		return true;
230	}
231	return false;
232}
233
234// ReplaceItem
235template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
236bool
237TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::ReplaceItem(int32 index, const item_t &item)
238{
239	if (index >= 0 && index < fItemCount) {
240		fItems[index] = item;
241		return true;
242	}
243	return false;
244}
245
246// MoveItem
247template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
248bool
249TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::MoveItem(int32 oldIndex, int32 newIndex)
250{
251	if (oldIndex >= 0 && oldIndex < fItemCount
252		&& newIndex >= 0 && newIndex <= fItemCount) {
253		if (oldIndex < newIndex - 1) {
254			item_t item = fItems[oldIndex];
255			_MoveItems(fItems + oldIndex + 1, -1, newIndex - oldIndex - 1);
256			fItems[newIndex] = item;
257		} else if (oldIndex > newIndex) {
258			item_t item = fItems[oldIndex];
259			_MoveItems(fItems + newIndex, 1, oldIndex - newIndex);
260			fItems[newIndex] = item;
261		}
262		return true;
263	}
264	return false;
265}
266
267// MakeEmpty
268template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
269void
270TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::MakeEmpty()
271{
272	for (int32 i = 0; i < fItemCount; i++)
273		fItems[i].~item_t();
274	_Resize(0);
275}
276
277// CountItems
278template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
279int32
280TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const
281{
282	return fItemCount;
283}
284
285// IsEmpty
286template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
287bool
288TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const
289{
290	return (fItemCount == 0);
291}
292
293// ItemAt
294template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
295const typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
296TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) const
297{
298	if (index >= 0 && index < fItemCount)
299		return fItems[index];
300	return sDefaultItem;
301}
302
303// ItemAt
304template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
305typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
306TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index)
307{
308	if (index >= 0 && index < fItemCount)
309		return fItems[index];
310	return sDefaultItem;
311}
312
313// Items
314template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
315const typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t *
316TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const
317{
318	return fItems;
319}
320
321// IndexOf
322template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
323int32
324TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::IndexOf(const item_t &item) const
325{
326	for (int32 i = 0; i < fItemCount; i++) {
327		if (fItems[i] == item)
328			return i;
329	}
330	return -1;
331}
332
333// HasItem
334template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
335bool
336TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const
337{
338	return (IndexOf(item) >= 0);
339}
340
341// _Resize
342template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
343bool
344TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::_Resize(size_t count)
345{
346	bool result = true;
347	// calculate the new capacity
348	int32 newSize = count;
349	if (newSize <= 0)
350		newSize = 1;
351	newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize;
352	// resize if necessary
353	if ((size_t)newSize != fCapacity) {
354		item_t* newItems
355			= (item_t*)realloc(fItems, newSize * sizeof(item_t));
356		if (newItems) {
357			fItems = newItems;
358			fCapacity = newSize;
359		} else
360			result = false;
361	}
362	if (result)
363		fItemCount = count;
364	return result;
365}
366
367#endif	// LIST_H
368