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