src/apps/haikudepot/List.h

   1 /*
   2  * Copyright 2009-2013, Stephan Aßmus <superstippi@gmx.de>
   3  * All rights reserved. Distributed under the terms of the MIT License.
   4  */
   5 #ifndef LIST_H
   6 #define LIST_H
   7
   8
   9 #include <new>
  10 #include <stdlib.h>
  11 #include <string.h>
  12
  13 #include <SupportDefs.h>
  14
  15
  16 template <typename ItemType, bool PlainOldData, uint32 BlockSize = 8>
  17 class List {
  18         typedef List<ItemType, PlainOldData, BlockSize> SelfType;
  19 public:
  20         List()
  21                 :
  22                 fItems(NULL),
  23                 fCount(0),
  24                 fAllocatedCount(0)
  25         {
  26         }
  27
  28         List(const SelfType& other)
  29                 :
  30                 fItems(NULL),
  31                 fCount(0),
  32                 fAllocatedCount(0)
  33         {
  34                 *this = other;
  35         }
  36
  37         virtual ~List()
  38         {
  39                 if (!PlainOldData) {
  40                         // Make sure to call destructors of old objects.
  41                         _Resize(0);
  42                 }
  43                 free(fItems);
  44         }
  45
  46         SelfType& operator=(const SelfType& other)
  47         {
  48                 if (this == &other)
  49                         return *this;
  50
  51                 if (PlainOldData) {
  52                         if (_Resize(other.fCount))
  53                                 memcpy(fItems, other.fItems, fCount * sizeof(ItemType));
  54                 } else {
  55                         // Make sure to call destructors of old objects.
  56                         // NOTE: Another option would be to use
  57                         // ItemType::operator=(const ItemType& other), but then
  58                         // we would need to be carefull which objects are already
  59                         // initialized. Also ItemType would be required to implement the
  60                         // operator, while doing it this way requires only a copy
  61                         // constructor.
  62                         _Resize(0);
  63                         for (uint32 i = 0; i < other.fCount; i++) {
  64                                 if (!Add(other.ItemAtFast(i)))
  65                                         break;
  66                         }
  67                 }
  68                 return *this;
  69         }
  70
  71         bool operator==(const SelfType& other) const
  72         {
  73                 if (this == &other)
  74                         return true;
  75
  76                 if (fCount != other.fCount)
  77                         return false;
  78                 if (fCount == 0)
  79                         return true;
  80
  81                 if (PlainOldData) {
  82                         return memcmp(fItems, other.fItems,
  83                                 fCount * sizeof(ItemType)) == 0;
  84                 } else {
  85                         for (uint32 i = 0; i < other.fCount; i++) {
  86                                 if (ItemAtFast(i) != other.ItemAtFast(i))
  87                                         return false;
  88                         }
  89                 }
  90                 return true;
  91         }
  92
  93         bool operator!=(const SelfType& other) const
  94         {
  95                 return !(*this == other);
  96         }
  97
  98         inline void Clear()
  99         {
 100                 _Resize(0);
 101         }
 102
 103         inline bool IsEmpty() const
 104         {
 105                 return fCount == 0;
 106         }
 107
 108         inline int32 CountItems() const
 109         {
 110                 return fCount;
 111         }
 112
 113         inline bool Add(const ItemType& copyFrom)
 114         {
 115                 if (_Resize(fCount + 1)) {
 116                         ItemType* item = fItems + fCount - 1;
 117                         // Initialize the new object from the original.
 118                         if (!PlainOldData)
 119                                 new (item) ItemType(copyFrom);
 120                         else
 121                                 *item = copyFrom;
 122                         return true;
 123                 }
 124                 return false;
 125         }
 126
 127         inline bool Add(const ItemType& copyFrom, int32 index)
 128         {
 129                 if (index < 0 || index > (int32)fCount)
 130                         return false;
 131
 132                 if (!_Resize(fCount + 1))
 133                         return false;
 134
 135                 int32 nextIndex = index + 1;
 136                 if ((int32)fCount > nextIndex)
 137                         memmove(fItems + nextIndex, fItems + index,
 138                                 (fCount - nextIndex) * sizeof(ItemType));
 139
 140                 ItemType* item = fItems + index;
 141                 if (!PlainOldData)
 142                         new (item) ItemType(copyFrom);
 143                 else
 144                         *item = copyFrom;
 145
 146                 return true;
 147         }
 148
 149         inline bool Remove()
 150         {
 151                 if (fCount > 0) {
 152                         _Resize(fCount - 1);
 153                         return true;
 154                 }
 155                 return false;
 156         }
 157
 158         inline bool Remove(int32 index)
 159         {
 160                 if (index < 0 || index >= (int32)fCount)
 161                         return false;
 162
 163                 if (!PlainOldData) {
 164                         ItemType* object = fItems + index;
 165                         object->~ItemType();
 166                 }
 167
 168                 int32 nextIndex = index + 1;
 169                 if ((int32)fCount > nextIndex) {
 170                         memcpy(fItems + index, fItems + nextIndex,
 171                                 (fCount - nextIndex) * sizeof(ItemType));
 172                 }
 173
 174                 fCount--;
 175                 return true;
 176         }
 177
 178         inline bool Remove(const ItemType& item)
 179         {
 180                 return Remove(IndexOf(item));
 181         }
 182
 183         inline bool Replace(int32 index, const ItemType& copyFrom)
 184         {
 185                 if (index < 0 || index >= (int32)fCount)
 186                         return false;
 187
 188                 ItemType* item = fItems + index;
 189                 // Initialize the new object from the original.
 190                 if (!PlainOldData) {
 191                         item->~ItemType();
 192                         new (item) ItemType(copyFrom);
 193                 } else
 194                         *item = copyFrom;
 195                 return true;
 196         }
 197
 198         inline const ItemType& ItemAt(int32 index) const
 199         {
 200                 if (index < 0 || index >= (int32)fCount)
 201                         return fNullItem;
 202                 return ItemAtFast(index);
 203         }
 204
 205         inline const ItemType& ItemAtFast(int32 index) const
 206         {
 207                 return *(fItems + index);
 208         }
 209
 210         inline const ItemType& LastItem() const
 211         {
 212                 if (fCount == 0)
 213                         return fNullItem;
 214                 return ItemAt((int32)fCount - 1);
 215         }
 216
 217         inline int32 IndexOf(const ItemType& item) const
 218         {
 219                 for (uint32 i = 0; i < fCount; i++) {
 220                         if (ItemAtFast(i) == item)
 221                                 return i;
 222                 }
 223                 return -1;
 224         }
 225
 226         inline bool Contains(const ItemType& item) const
 227         {
 228                 return IndexOf(item) >= 0;
 229         }
 230
 231 private:
 232         inline bool _Resize(uint32 count)
 233         {
 234                 if (count > fAllocatedCount) {
 235                         uint32 allocationCount = (count + BlockSize - 1)
 236                                 / BlockSize * BlockSize;
 237                         ItemType* items = reinterpret_cast<ItemType*>(
 238                                 realloc(fItems, allocationCount * sizeof(ItemType)));
 239                         if (items == NULL)
 240                                 return false;
 241                         fItems = items;
 242
 243                         fAllocatedCount = allocationCount;
 244                 } else if (count < fCount) {
 245                         if (!PlainOldData) {
 246                                 // Uninit old objects so that we can re-use them when
 247                                 // appending objects without the need to re-allocate.
 248                                 for (uint32 i = count; i < fCount; i++) {
 249                                         ItemType* object = fItems + i;
 250                                         object->~ItemType();
 251                                 }
 252                         }
 253                 }
 254                 fCount = count;
 255                 return true;
 256         }
 257
 258         ItemType*               fItems;
 259         ItemType                fNullItem;
 260         uint32                  fCount;
 261         uint32                  fAllocatedCount;
 262 };
 263
 264
 265 #endif // LIST_H