1// TemplateList.h
2//
3// Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de)
4//
5// Permission is hereby granted, free of charge, to any person obtaining a
6// copy of this software and associated documentation files (the "Software"),
7// to deal in the Software without restriction, including without limitation
8// the rights to use, copy, modify, merge, publish, distribute, sublicense,
9// and/or sell copies of the Software, and to permit persons to whom the
10// Software is furnished to do so, subject to the following conditions:
11//
12// The above copyright notice and this permission notice shall be included in
13// all copies or substantial portions of the Software.
14//
15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21// DEALINGS IN THE SOFTWARE.
22//
23// Except as contained in this notice, the name of a copyright holder shall
24// not be used in advertising or otherwise to promote the sale, use or other
25// dealings in this Software without prior written authorization of the
26// copyright holder.
27
28#ifndef TEMPLATE_LIST_H
29#define TEMPLATE_LIST_H
30
31#ifdef _KERNEL_MODE
32	#include <kernel_cpp.h>
33#else
34	#include <new>
35#endif
36
37#include <stdlib.h>
38#include <string.h>
39
40#include <SupportDefs.h>
41
42template<typename ITEM>
43class DefaultDefaultItemCreator {
44public:
45	static inline ITEM GetItem() { return ITEM(0); }
46};
47
48/*!
49	\class TemplateList
50	\brief A generic list implementation.
51*/
52template<typename ITEM,
53		 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> >
54class TemplateList {
55public:
56	typedef ITEM					item_t;
57	typedef TemplateList			list_t;
58
59private:
60	static item_t					sDefaultItem;
61	static const size_t				kDefaultChunkSize = 10;
62	static const size_t				kMaximalChunkSize = 1024 * 1024;
63
64public:
65	TemplateList(size_t chunkSize = kDefaultChunkSize);
66	~TemplateList();
67
68	inline const item_t &GetDefaultItem() const;
69	inline item_t &GetDefaultItem();
70
71	bool AddItem(const item_t &item, int32 index);
72	bool AddItem(const item_t &item);
73//	bool AddList(list_t *list, int32 index);
74//	bool AddList(list_t *list);
75
76	bool RemoveItem(const item_t &item);
77	bool RemoveItem(int32 index);
78
79	bool ReplaceItem(int32 index, const item_t &item);
80
81	bool MoveItem(int32 oldIndex, int32 newIndex);
82
83	void MakeEmpty();
84
85	int32 CountItems() const;
86	bool IsEmpty() const;
87	const item_t &ItemAt(int32 index) const;
88	item_t &ItemAt(int32 index);
89	const item_t *Items() const;
90	int32 IndexOf(const item_t &item) const;
91	bool HasItem(const item_t &item) const;
92
93	// debugging
94	int32 GetCapacity() const	{ return fCapacity; }
95
96private:
97	inline static void _MoveItems(item_t* items, int32 offset, int32 count);
98	bool _Resize(size_t count);
99
100private:
101	size_t	fCapacity;
102	size_t	fChunkSize;
103	int32	fItemCount;
104	item_t	*fItems;
105};
106
107// sDefaultItem
108template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
109typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t
110	TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem(
111		DEFAULT_ITEM_SUPPLIER::GetItem());
112
113// constructor
114template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
115TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::TemplateList(size_t chunkSize)
116	: fCapacity(0),
117	  fChunkSize(chunkSize),
118	  fItemCount(0),
119	  fItems(NULL)
120{
121	if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize)
122		fChunkSize = kDefaultChunkSize;
123	_Resize(0);
124}
125
126// destructor
127template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
128TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::~TemplateList()
129{
130	MakeEmpty();
131	free(fItems);
132}
133
134// GetDefaultItem
135template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
136inline
137const typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
138TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const
139{
140	return sDefaultItem;
141}
142
143// GetDefaultItem
144template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
145inline
146typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
147TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem()
148{
149	return sDefaultItem;
150}
151
152// _MoveItems
153template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
154inline
155void
156TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::_MoveItems(item_t* items, int32 offset, int32 count)
157{
158	if (count > 0 && offset != 0)
159		memmove(items + offset, items, count * sizeof(item_t));
160}
161
162// AddItem
163template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
164bool
165TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item, int32 index)
166{
167	bool result = (index >= 0 && index <= fItemCount
168				   && _Resize(fItemCount + 1));
169	if (result) {
170		_MoveItems(fItems + index, 1, fItemCount - index - 1);
171		new(fItems + index) item_t(item);
172	}
173	return result;
174}
175
176// AddItem
177template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
178bool
179TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item)
180{
181	bool result = true;
182	if ((int32)fCapacity > fItemCount) {
183		new(fItems + fItemCount) item_t(item);
184		fItemCount++;
185	} else {
186		if ((result = _Resize(fItemCount + 1)))
187			new(fItems + (fItemCount - 1)) item_t(item);
188	}
189	return result;
190}
191
192// These don't use the copy constructor!
193/*
194// AddList
195template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
196bool
197TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list, int32 index)
198{
199	bool result = (list && index >= 0 && index <= fItemCount);
200	if (result && list->fItemCount > 0) {
201		int32 count = list->fItemCount;
202		result = _Resize(fItemCount + count);
203		if (result) {
204			_MoveItems(fItems + index, count, fItemCount - index - count);
205			memcpy(fItems + index, list->fItems,
206				   list->fItemCount * sizeof(item_t));
207		}
208	}
209	return result;
210}
211
212// AddList
213template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
214bool
215TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list)
216{
217	bool result = (list);
218	if (result && list->fItemCount > 0) {
219		int32 index = fItemCount;
220		int32 count = list->fItemCount;
221		result = _Resize(fItemCount + count);
222		if (result) {
223			memcpy(fItems + index, list->fItems,
224				   list->fItemCount * sizeof(item_t));
225		}
226	}
227	return result;
228}
229*/
230
231// RemoveItem
232template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
233bool
234TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(const item_t &item)
235{
236	int32 index = IndexOf(item);
237	bool result = (index >= 0);
238	if (result)
239		RemoveItem(index);
240	return result;
241}
242
243// RemoveItem
244template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
245bool
246TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(int32 index)
247{
248	if (index >= 0 && index < fItemCount) {
249		fItems[index].~item_t();
250		_MoveItems(fItems + index + 1, -1, fItemCount - index - 1);
251		_Resize(fItemCount - 1);
252		return true;
253	}
254	return false;
255}
256
257// ReplaceItem
258template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
259bool
260TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::ReplaceItem(int32 index, const item_t &item)
261{
262	if (index >= 0 && index < fItemCount) {
263		fItems[index] = item;
264		return true;
265	}
266	return false;
267}
268
269// MoveItem
270template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
271bool
272TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::MoveItem(int32 oldIndex, int32 newIndex)
273{
274	if (oldIndex >= 0 && oldIndex < fItemCount
275		&& newIndex >= 0 && newIndex <= fItemCount) {
276		if (oldIndex < newIndex - 1) {
277			item_t item = fItems[oldIndex];
278			_MoveItems(fItems + oldIndex + 1, -1, newIndex - oldIndex - 1);
279			fItems[newIndex] = item;
280		} else if (oldIndex > newIndex) {
281			item_t item = fItems[oldIndex];
282			_MoveItems(fItems + newIndex, 1, oldIndex - newIndex);
283			fItems[newIndex] = item;
284		}
285		return true;
286	}
287	return false;
288}
289
290// MakeEmpty
291template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
292void
293TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::MakeEmpty()
294{
295	for (int32 i = 0; i < fItemCount; i++)
296		fItems[i].~item_t();
297	_Resize(0);
298}
299
300// CountItems
301template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
302int32
303TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const
304{
305	return fItemCount;
306}
307
308// IsEmpty
309template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
310bool
311TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const
312{
313	return (fItemCount == 0);
314}
315
316// ItemAt
317template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
318const typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
319TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) const
320{
321	if (index >= 0 && index < fItemCount)
322		return fItems[index];
323	return sDefaultItem;
324}
325
326// ItemAt
327template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
328typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
329TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index)
330{
331	if (index >= 0 && index < fItemCount)
332		return fItems[index];
333	return sDefaultItem;
334}
335
336// Items
337template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
338const typename TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t *
339TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const
340{
341	return fItems;
342}
343
344// IndexOf
345template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
346int32
347TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::IndexOf(const item_t &item) const
348{
349	for (int32 i = 0; i < fItemCount; i++) {
350		if (fItems[i] == item)
351			return i;
352	}
353	return -1;
354}
355
356// HasItem
357template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
358bool
359TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const
360{
361	return (IndexOf(item) >= 0);
362}
363
364// _Resize
365template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
366bool
367TemplateList<ITEM, DEFAULT_ITEM_SUPPLIER>::_Resize(size_t count)
368{
369	bool result = true;
370	// calculate the new capacity
371	int32 newSize = count;
372	if (newSize <= 0)
373		newSize = 1;
374	newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize;
375	// resize if necessary
376	if ((size_t)newSize != fCapacity) {
377		item_t* newItems
378			= (item_t*)realloc(fItems, newSize * sizeof(item_t));
379		if (newItems) {
380			fItems = newItems;
381			fCapacity = newSize;
382		} else
383			result = false;
384	}
385	if (result)
386		fItemCount = count;
387	return result;
388}
389
390#endif	// LIST_H
391