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