1 // List.h 2 // 3 // Copyright (c) 2003, Ingo Weinhold (bonefish@cs.tu-berlin.de) 4 // 5 // This program is free software; you can redistribute it and/or modify 6 // it under the terms of the GNU General Public License as published by 7 // the Free Software Foundation; either version 2 of the License, or 8 // (at your option) any later version. 9 // 10 // This program is distributed in the hope that it will be useful, 11 // but WITHOUT ANY WARRANTY; without even the implied warranty of 12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 // GNU General Public License for more details. 14 // 15 // You should have received a copy of the GNU General Public License 16 // along with this program; if not, write to the Free Software 17 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 18 // 19 // You can alternatively use *this file* under the terms of the the MIT 20 // license included in this package. 21 22 #ifndef LIST_H 23 #define LIST_H 24 25 #include <new> 26 #include <stdlib.h> 27 #include <string.h> 28 29 #include <SupportDefs.h> 30 31 template<typename ITEM> 32 class DefaultDefaultItemCreator { 33 public: 34 static inline ITEM GetItem() { return ITEM(0); } 35 }; 36 37 /*! 38 \class List 39 \brief A generic list implementation. 40 */ 41 template<typename ITEM, 42 typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> > 43 class List { 44 public: 45 typedef ITEM item_t; 46 typedef List list_t; 47 48 private: 49 static item_t sDefaultItem; 50 static const size_t kDefaultChunkSize = 10; 51 static const size_t kMaximalChunkSize = 1024 * 1024; 52 53 public: 54 List(size_t chunkSize = kDefaultChunkSize); 55 ~List(); 56 57 inline const item_t &GetDefaultItem() const; 58 inline item_t &GetDefaultItem(); 59 60 bool AddItem(const item_t &item, int32 index); 61 bool AddItem(const item_t &item); 62 // bool AddList(list_t *list, int32 index); 63 // bool AddList(list_t *list); 64 65 bool RemoveItem(const item_t &item); 66 bool RemoveItem(int32 index); 67 68 void MakeEmpty(); 69 70 int32 CountItems() const; 71 bool IsEmpty() const; 72 const item_t &ItemAt(int32 index) const; 73 item_t &ItemAt(int32 index); 74 const item_t *Items() const; 75 int32 IndexOf(const item_t &item) const; 76 bool HasItem(const item_t &item) const; 77 78 private: 79 inline static void _MoveItems(item_t* items, int32 offset, int32 count); 80 bool _Resize(size_t count); 81 82 private: 83 size_t fCapacity; 84 size_t fChunkSize; 85 int32 fItemCount; 86 item_t *fItems; 87 }; 88 89 // sDefaultItem 90 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 91 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t 92 List<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem( 93 DEFAULT_ITEM_SUPPLIER::GetItem()); 94 95 // constructor 96 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 97 List<ITEM, DEFAULT_ITEM_SUPPLIER>::List(size_t chunkSize) 98 : fCapacity(0), 99 fChunkSize(chunkSize), 100 fItemCount(0), 101 fItems(NULL) 102 { 103 if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize) 104 fChunkSize = kDefaultChunkSize; 105 _Resize(0); 106 } 107 108 // destructor 109 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 110 List<ITEM, DEFAULT_ITEM_SUPPLIER>::~List() 111 { 112 MakeEmpty(); 113 free(fItems); 114 } 115 116 // GetDefaultItem 117 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 118 inline 119 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 120 List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const 121 { 122 return sDefaultItem; 123 } 124 125 // GetDefaultItem 126 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 127 inline 128 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 129 List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() 130 { 131 return sDefaultItem; 132 } 133 134 // _MoveItems 135 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 136 inline 137 void 138 List<ITEM, DEFAULT_ITEM_SUPPLIER>::_MoveItems(item_t* items, int32 offset, int32 count) 139 { 140 if (count > 0 && offset != 0) 141 memmove(items + offset, items, count * sizeof(item_t)); 142 } 143 144 // AddItem 145 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 146 bool 147 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item, int32 index) 148 { 149 bool result = (index >= 0 && index <= fItemCount 150 && _Resize(fItemCount + 1)); 151 if (result) { 152 _MoveItems(fItems + index, 1, fItemCount - index - 1); 153 new(fItems + index) item_t(item); 154 } 155 return result; 156 } 157 158 // AddItem 159 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 160 bool 161 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item) 162 { 163 bool result = true; 164 if ((int32)fCapacity > fItemCount) { 165 new(fItems + fItemCount) item_t(item); 166 fItemCount++; 167 } else { 168 if ((result = _Resize(fItemCount + 1))) 169 new(fItems + (fItemCount - 1)) item_t(item); 170 } 171 return result; 172 } 173 174 // These don't use the copy constructor! 175 /* 176 // AddList 177 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 178 bool 179 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list, int32 index) 180 { 181 bool result = (list && index >= 0 && index <= fItemCount); 182 if (result && list->fItemCount > 0) { 183 int32 count = list->fItemCount; 184 result = _Resize(fItemCount + count); 185 if (result) { 186 _MoveItems(fItems + index, count, fItemCount - index - count); 187 memcpy(fItems + index, list->fItems, 188 list->fItemCount * sizeof(item_t)); 189 } 190 } 191 return result; 192 } 193 194 // AddList 195 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 196 bool 197 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list) 198 { 199 bool result = (list); 200 if (result && list->fItemCount > 0) { 201 int32 index = fItemCount; 202 int32 count = list->fItemCount; 203 result = _Resize(fItemCount + count); 204 if (result) { 205 memcpy(fItems + index, list->fItems, 206 list->fItemCount * sizeof(item_t)); 207 } 208 } 209 return result; 210 } 211 */ 212 213 // RemoveItem 214 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 215 bool 216 List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(const item_t &item) 217 { 218 int32 index = IndexOf(item); 219 bool result = (index >= 0); 220 if (result) 221 RemoveItem(index); 222 return result; 223 } 224 225 // RemoveItem 226 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 227 bool 228 List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(int32 index) 229 { 230 if (index >= 0 && index < fItemCount) { 231 fItems[index].~item_t(); 232 _MoveItems(fItems + index + 1, -1, fItemCount - index - 1); 233 _Resize(fItemCount - 1); 234 return true; 235 } 236 return false; 237 } 238 239 // MakeEmpty 240 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 241 void 242 List<ITEM, DEFAULT_ITEM_SUPPLIER>::MakeEmpty() 243 { 244 for (int32 i = 0; i < fItemCount; i++) 245 fItems[i].~item_t(); 246 _Resize(0); 247 } 248 249 // CountItems 250 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 251 int32 252 List<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const 253 { 254 return fItemCount; 255 } 256 257 // IsEmpty 258 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 259 bool 260 List<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const 261 { 262 return (fItemCount == 0); 263 } 264 265 // ItemAt 266 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 267 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 268 List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) const 269 { 270 if (index >= 0 && index < fItemCount) 271 return fItems[index]; 272 return sDefaultItem; 273 } 274 275 // ItemAt 276 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 277 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t & 278 List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) 279 { 280 if (index >= 0 && index < fItemCount) 281 return fItems[index]; 282 return sDefaultItem; 283 } 284 285 // Items 286 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 287 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t * 288 List<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const 289 { 290 return fItems; 291 } 292 293 // IndexOf 294 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 295 int32 296 List<ITEM, DEFAULT_ITEM_SUPPLIER>::IndexOf(const item_t &item) const 297 { 298 for (int32 i = 0; i < fItemCount; i++) { 299 if (fItems[i] == item) 300 return i; 301 } 302 return -1; 303 } 304 305 // HasItem 306 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 307 bool 308 List<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const 309 { 310 return (IndexOf(item) >= 0); 311 } 312 313 // _Resize 314 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER> 315 bool 316 List<ITEM, DEFAULT_ITEM_SUPPLIER>::_Resize(size_t count) 317 { 318 bool result = true; 319 // calculate the new capacity 320 int32 newSize = count; 321 if (newSize <= 0) 322 newSize = 1; 323 newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize; 324 // resize if necessary 325 if ((size_t)newSize != fCapacity) { 326 item_t* newItems 327 = (item_t*)realloc(fItems, newSize * sizeof(item_t)); 328 if (newItems) { 329 fItems = newItems; 330 fCapacity = newSize; 331 } else 332 result = false; 333 } 334 if (result) 335 fItemCount = count; 336 return result; 337 } 338 339 #endif // LIST_H 340