src/add-ons/kernel/file_systems/ramfs/List.h

   1 // List.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 LIST_H
  29 #define LIST_H
  30
  31 #include <new>
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 #include <SupportDefs.h>
  36
  37 template<typename ITEM>
  38 class DefaultDefaultItemCreator {
  39 public:
  40         static inline ITEM GetItem() { return ITEM(0); }
  41 };
  42
  43 /*!
  44         \class List
  45         \brief A generic list implementation.
  46 */
  47 template<typename ITEM,
  48                  typename DEFAULT_ITEM_SUPPLIER = DefaultDefaultItemCreator<ITEM> >
  49 class List {
  50 public:
  51         typedef ITEM                                    item_t;
  52         typedef List                                    list_t;
  53
  54 private:
  55         static item_t                                   sDefaultItem;
  56         static const size_t                             kDefaultChunkSize = 10;
  57         static const size_t                             kMaximalChunkSize = 1024 * 1024;
  58
  59 public:
  60         List(size_t chunkSize = kDefaultChunkSize);
  61         ~List();
  62
  63         inline const item_t &GetDefaultItem() const;
  64         inline item_t &GetDefaultItem();
  65
  66         bool AddItem(const item_t &item, int32 index);
  67         bool AddItem(const item_t &item);
  68 //      bool AddList(list_t *list, int32 index);
  69 //      bool AddList(list_t *list);
  70
  71         bool RemoveItem(const item_t &item);
  72         bool RemoveItem(int32 index);
  73
  74         bool ReplaceItem(int32 index, const item_t &item);
  75
  76         bool MoveItem(int32 oldIndex, int32 newIndex);
  77
  78         void MakeEmpty();
  79
  80         int32 CountItems() const;
  81         bool IsEmpty() const;
  82         const item_t &ItemAt(int32 index) const;
  83         item_t &ItemAt(int32 index);
  84         const item_t *Items() const;
  85         int32 IndexOf(const item_t &item) const;
  86         bool HasItem(const item_t &item) const;
  87
  88         // debugging
  89         int32 GetCapacity() const       { return fCapacity; }
  90
  91 private:
  92         inline static void _MoveItems(item_t* items, int32 offset, int32 count);
  93         bool _Resize(size_t count);
  94
  95 private:
  96         size_t  fCapacity;
  97         size_t  fChunkSize;
  98         int32   fItemCount;
  99         item_t  *fItems;
 100 };
 101
 102 // sDefaultItem
 103 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 104 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t
 105         List<ITEM, DEFAULT_ITEM_SUPPLIER>::sDefaultItem(
 106                 DEFAULT_ITEM_SUPPLIER::GetItem());
 107
 108 // constructor
 109 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 110 List<ITEM, DEFAULT_ITEM_SUPPLIER>::List(size_t chunkSize)
 111         : fCapacity(0),
 112           fChunkSize(chunkSize),
 113           fItemCount(0),
 114           fItems(NULL)
 115 {
 116         if (fChunkSize == 0 || fChunkSize > kMaximalChunkSize)
 117                 fChunkSize = kDefaultChunkSize;
 118         _Resize(0);
 119 }
 120
 121 // destructor
 122 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 123 List<ITEM, DEFAULT_ITEM_SUPPLIER>::~List()
 124 {
 125         MakeEmpty();
 126         free(fItems);
 127 }
 128
 129 // GetDefaultItem
 130 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 131 inline
 132 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
 133 List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem() const
 134 {
 135         return sDefaultItem;
 136 }
 137
 138 // GetDefaultItem
 139 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 140 inline
 141 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
 142 List<ITEM, DEFAULT_ITEM_SUPPLIER>::GetDefaultItem()
 143 {
 144         return sDefaultItem;
 145 }
 146
 147 // _MoveItems
 148 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 149 inline
 150 void
 151 List<ITEM, DEFAULT_ITEM_SUPPLIER>::_MoveItems(item_t* items, int32 offset, int32 count)
 152 {
 153         if (count > 0 && offset != 0)
 154                 memmove(items + offset, items, count * sizeof(item_t));
 155 }
 156
 157 // AddItem
 158 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 159 bool
 160 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item, int32 index)
 161 {
 162         bool result = (index >= 0 && index <= fItemCount
 163                                    && _Resize(fItemCount + 1));
 164         if (result) {
 165                 _MoveItems(fItems + index, 1, fItemCount - index - 1);
 166                 new(fItems + index) item_t(item);
 167         }
 168         return result;
 169 }
 170
 171 // AddItem
 172 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 173 bool
 174 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddItem(const item_t &item)
 175 {
 176         bool result = true;
 177         if ((int32)fCapacity > fItemCount) {
 178                 new(fItems + fItemCount) item_t(item);
 179                 fItemCount++;
 180         } else {
 181                 if ((result = _Resize(fItemCount + 1)))
 182                         new(fItems + (fItemCount - 1)) item_t(item);
 183         }
 184         return result;
 185 }
 186
 187 // These don't use the copy constructor!
 188 /*
 189 // AddList
 190 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 191 bool
 192 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list, int32 index)
 193 {
 194         bool result = (list && index >= 0 && index <= fItemCount);
 195         if (result && list->fItemCount > 0) {
 196                 int32 count = list->fItemCount;
 197                 result = _Resize(fItemCount + count);
 198                 if (result) {
 199                         _MoveItems(fItems + index, count, fItemCount - index - count);
 200                         memcpy(fItems + index, list->fItems,
 201                                    list->fItemCount * sizeof(item_t));
 202                 }
 203         }
 204         return result;
 205 }
 206
 207 // AddList
 208 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 209 bool
 210 List<ITEM, DEFAULT_ITEM_SUPPLIER>::AddList(list_t *list)
 211 {
 212         bool result = (list);
 213         if (result && list->fItemCount > 0) {
 214                 int32 index = fItemCount;
 215                 int32 count = list->fItemCount;
 216                 result = _Resize(fItemCount + count);
 217                 if (result) {
 218                         memcpy(fItems + index, list->fItems,
 219                                    list->fItemCount * sizeof(item_t));
 220                 }
 221         }
 222         return result;
 223 }
 224 */
 225
 226 // RemoveItem
 227 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 228 bool
 229 List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(const item_t &item)
 230 {
 231         int32 index = IndexOf(item);
 232         bool result = (index >= 0);
 233         if (result)
 234                 RemoveItem(index);
 235         return result;
 236 }
 237
 238 // RemoveItem
 239 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 240 bool
 241 List<ITEM, DEFAULT_ITEM_SUPPLIER>::RemoveItem(int32 index)
 242 {
 243         if (index >= 0 && index < fItemCount) {
 244                 fItems[index].~item_t();
 245                 _MoveItems(fItems + index + 1, -1, fItemCount - index - 1);
 246                 _Resize(fItemCount - 1);
 247                 return true;
 248         }
 249         return false;
 250 }
 251
 252 // ReplaceItem
 253 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 254 bool
 255 List<ITEM, DEFAULT_ITEM_SUPPLIER>::ReplaceItem(int32 index, const item_t &item)
 256 {
 257         if (index >= 0 && index < fItemCount) {
 258                 fItems[index] = item;
 259                 return true;
 260         }
 261         return false;
 262 }
 263
 264 // MoveItem
 265 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 266 bool
 267 List<ITEM, DEFAULT_ITEM_SUPPLIER>::MoveItem(int32 oldIndex, int32 newIndex)
 268 {
 269         if (oldIndex >= 0 && oldIndex < fItemCount
 270                 && newIndex >= 0 && newIndex <= fItemCount) {
 271                 if (oldIndex < newIndex - 1) {
 272                         item_t item = fItems[oldIndex];
 273                         _MoveItems(fItems + oldIndex + 1, -1, newIndex - oldIndex - 1);
 274                         fItems[newIndex] = item;
 275                 } else if (oldIndex > newIndex) {
 276                         item_t item = fItems[oldIndex];
 277                         _MoveItems(fItems + newIndex, 1, oldIndex - newIndex);
 278                         fItems[newIndex] = item;
 279                 }
 280                 return true;
 281         }
 282         return false;
 283 }
 284
 285 // MakeEmpty
 286 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 287 void
 288 List<ITEM, DEFAULT_ITEM_SUPPLIER>::MakeEmpty()
 289 {
 290         for (int32 i = 0; i < fItemCount; i++)
 291                 fItems[i].~item_t();
 292         _Resize(0);
 293 }
 294
 295 // CountItems
 296 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 297 int32
 298 List<ITEM, DEFAULT_ITEM_SUPPLIER>::CountItems() const
 299 {
 300         return fItemCount;
 301 }
 302
 303 // IsEmpty
 304 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 305 bool
 306 List<ITEM, DEFAULT_ITEM_SUPPLIER>::IsEmpty() const
 307 {
 308         return (fItemCount == 0);
 309 }
 310
 311 // ItemAt
 312 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 313 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
 314 List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index) const
 315 {
 316         if (index >= 0 && index < fItemCount)
 317                 return fItems[index];
 318         return sDefaultItem;
 319 }
 320
 321 // ItemAt
 322 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 323 typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t &
 324 List<ITEM, DEFAULT_ITEM_SUPPLIER>::ItemAt(int32 index)
 325 {
 326         if (index >= 0 && index < fItemCount)
 327                 return fItems[index];
 328         return sDefaultItem;
 329 }
 330
 331 // Items
 332 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 333 const typename List<ITEM, DEFAULT_ITEM_SUPPLIER>::item_t *
 334 List<ITEM, DEFAULT_ITEM_SUPPLIER>::Items() const
 335 {
 336         return fItems;
 337 }
 338
 339 // IndexOf
 340 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 341 int32
 342 List<ITEM, DEFAULT_ITEM_SUPPLIER>::IndexOf(const item_t &item) const
 343 {
 344         for (int32 i = 0; i < fItemCount; i++) {
 345                 if (fItems[i] == item)
 346                         return i;
 347         }
 348         return -1;
 349 }
 350
 351 // HasItem
 352 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 353 bool
 354 List<ITEM, DEFAULT_ITEM_SUPPLIER>::HasItem(const item_t &item) const
 355 {
 356         return (IndexOf(item) >= 0);
 357 }
 358
 359 // _Resize
 360 template<typename ITEM, typename DEFAULT_ITEM_SUPPLIER>
 361 bool
 362 List<ITEM, DEFAULT_ITEM_SUPPLIER>::_Resize(size_t count)
 363 {
 364         bool result = true;
 365         // calculate the new capacity
 366         int32 newSize = count;
 367         if (newSize <= 0)
 368                 newSize = 1;
 369         newSize = ((newSize - 1) / fChunkSize + 1) * fChunkSize;
 370         // resize if necessary
 371         if ((size_t)newSize != fCapacity) {
 372                 item_t* newItems
 373                         = (item_t*)realloc(fItems, newSize * sizeof(item_t));
 374                 if (newItems) {
 375                         fItems = newItems;
 376                         fCapacity = newSize;
 377                 } else
 378                         result = false;
 379         }
 380         if (result)
 381                 fItemCount = count;
 382         return result;
 383 }
 384
 385 #endif  // LIST_H