MMgc/BasicList.h

   1 /* -*- Mode: C++; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 4 -*- */
   2 /* vi: set ts=4 sw=4 expandtab: (add to ~/.vimrc: set modeline modelines=5) */
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is [Open Source Virtual Machine.].
  17  *
  18  * The Initial Developer of the Original Code is
  19  * Adobe System Incorporated.
  20  * Portions created by the Initial Developer are Copyright (C) 2004-2006
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *   Adobe AS3 Team
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either the GNU General Public License Version 2 or later (the "GPL"), or
  28  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 #ifndef __BasicList__
  41 #define __BasicList__
  42
  43 namespace MMgc
  44 {
  45     template<typename T, int growthIncrement=4>
  46     class BasicList
  47     {
  48     public:
  49         BasicList() : count(0),
  50                       capacity(0),
  51                       items(NULL),
  52                       iteratorCount(0),
  53                       holes(false),
  54                       cursor(0)
  55         {
  56         }
  57
  58         ~BasicList()
  59         {
  60             Destroy();
  61         }
  62
  63         void Destroy()
  64         {
  65             if ( items )
  66             {
  67                 mmfx_delete_array(items);
  68                 items = NULL;
  69             }
  70             count = capacity = iteratorCount = 0;
  71             holes = false;
  72             cursor = 0;
  73         }
  74
  75         void Add(T item)
  76         {
  77             if (holes && iteratorCount == 0)
  78                 Compact();
  79             if (count == capacity)
  80             {
  81                 capacity += growthIncrement;
  82                 T* newItems = mmfx_new_array_opt(T,  capacity, kZero);
  83                 if (items)
  84                     VMPI_memcpy(newItems, items, count * sizeof(T));
  85                 mmfx_delete_array(items);
  86                 items = newItems;
  87             }
  88             uint32_t numHoles = 0;
  89             if (holes)
  90             {
  91                 uint32_t numFound = 0;
  92                 for (uint32_t j = 0; numFound < count && j < capacity; j++)
  93                 {
  94                     if (items[j] == NULL)
  95                     {
  96                         numHoles++;
  97                     } else {
  98                         numFound++;
  99                     }
 100                 }
 101             }
 102             items[count+numHoles] = item;
 103             count++;
 104         }
 105
 106         bool TryAdd(T item)
 107         {
 108             if (holes && iteratorCount == 0)
 109                 Compact();
 110             if (count == capacity)
 111             {
 112                 uint32_t tryCapacity = capacity + growthIncrement;
 113                 T* newItems = mmfx_new_array_opt(T,  tryCapacity, (MMgc::FixedMallocOpts)(kZero|kCanFail));
 114
 115                 if (newItems == NULL)
 116                     return false;
 117
 118                 capacity = tryCapacity;
 119                 if (items)
 120                     VMPI_memcpy(newItems, items, count * sizeof(T));
 121                 mmfx_delete_array(items);
 122                 items = newItems;
 123             }
 124             uint32_t numHoles = 0;
 125             if (holes)
 126             {
 127                 uint32_t numFound = 0;
 128                 for (uint32_t j = 0; numFound < count && j < capacity; j++)
 129                 {
 130                     if (items[j] == NULL)
 131                     {
 132                         numHoles++;
 133                     } else {
 134                         numFound++;
 135                     }
 136                 }
 137             }
 138             items[count+numHoles] = item;
 139             count++;
 140             return true;
 141         }
 142
 143         void Remove(T item)
 144         {
 145             if (holes && iteratorCount == 0)
 146                 Compact();
 147             uint32_t i=0;
 148             while (i < Limit() && items[i] != item)
 149                 i++;
 150             if (i == Limit())
 151             {
 152                 GCAssertMsg(false, "Bug: should not try to remove something that's not in the list");
 153                 return;
 154             }
 155
 156             //  If the item we deleted occured is our cursor, set our cursor to the next item
 157             if ( i == cursor)
 158             {
 159                 do {
 160                     cursor ++;
 161                 }while (cursor < capacity && items[cursor] == NULL);
 162
 163                 //  If our "next item" is the last item, then reset the list to the front.
 164                 if (cursor == capacity)
 165                 {
 166                     cursor = 0;
 167                 }
 168             }
 169
 170             items[i] = NULL;
 171             count--;
 172             if (i != count)
 173                 holes = true;
 174         }
 175
 176         T Get(uint32_t i) const
 177         {
 178             GCAssertMsg(i < Limit(), "Index out of bounds");
 179             return items[i];
 180         }
 181
 182         //   Call "SetCursor" on the list to have future iterators begin iterating from that position in the list.
 183         //   The iterator will still iterate through all items in the list once by wrapping to the front when the end is hit.
 184         void SetCursor( uint32_t newCursor ) { cursor = newCursor;}
 185         uint32_t GetCursor ( ){ return cursor;}
 186         uint32_t Count() const { return count; }
 187
 188         // iterator needs this to give complete iteration in the face of in-flight mutation
 189         uint32_t Limit() const { return holes ? capacity : count; }
 190
 191         void IteratorAttach() { iteratorCount++; }
 192         void IteratorDettach()
 193         {
 194             iteratorCount--;
 195             if (holes && iteratorCount == 0)
 196                 Compact();
 197         }
 198
 199     protected:
 200         // no impl
 201         BasicList(const BasicList& other);
 202         BasicList& operator=(const BasicList& other);
 203
 204     private:
 205
 206         void Compact()
 207         {
 208             // i iterates through destintation slots and j iterates through source slots
 209             // j skips over holes i doesn't
 210             // at the end i = count
 211             uint32_t i=0,j=1;
 212             while (j < capacity)
 213             {
 214                 if (items[i] == NULL)
 215                 {
 216                     if (items[j] != NULL)
 217                     {
 218                         if (cursor == j) cursor = i;
 219                         items[i++] = items[j++];
 220                         items[j-1] = NULL; // NULL it so next item goes in this hole
 221                     }
 222                     else
 223                     {
 224                         j++;
 225                     }
 226                 }
 227                 else
 228                 {
 229                     i++,j++;
 230                 }
 231             }
 232             GCAssert(i == count);
 233             holes = false;
 234         }
 235
 236         uint32_t count, capacity;
 237         T *items;
 238         uint32_t iteratorCount;
 239         bool holes;
 240         uint32_t cursor;
 241
 242     };
 243
 244     //  The BasicListIterator will iterate through items in the BasicList starting with the List's "cursor position"
 245     //  if "SetCursor" is never called on the BasicList passed into this BasicListIterator, then the list will iterate starting
 246     //  at position 0.  The iterator will still iterate through all items in the list once by wrapping to the front when the end is hit.
 247     template<typename T>
 248     class BasicListIterator
 249     {
 250     public:
 251         BasicListIterator(BasicList<T>& bl) : bl(bl), bListEnd(false)
 252         {
 253             index = bl.GetCursor();
 254             bl.IteratorAttach();
 255
 256         }
 257         ~BasicListIterator()
 258         {
 259             bl.IteratorDettach();
 260         }
 261         T next()
 262         {
 263             if (bListEnd) return NULL;
 264
 265             T t = NULL;
 266             if (index >= bl.GetCursor())
 267             {
 268                 // iterate over holes until end
 269                 while (index < bl.Limit() && t == NULL)
 270                 {
 271                     t = bl.Get(index++);
 272                 }
 273
 274                 if (index == bl.Limit() && bl.GetCursor() != 0)
 275                 {
 276                     index = 0;
 277                 }
 278             }
 279             else
 280             {
 281                 while(index < bl.GetCursor() && t == NULL)
 282                 {
 283                     t = bl.Get(index++);
 284                 }
 285                 if (index == bl.GetCursor())
 286                 {
 287                     bListEnd = true;
 288                 }
 289             }
 290             return t;
 291         }
 292         void MarkCursorInList()
 293         {
 294             while (index < bl.Limit() && bl.Get(index) == NULL)
 295             {
 296                 index ++;
 297             }
 298             bl.SetCursor( (index < bl.Limit()) ? index : 0);
 299         }
 300
 301     private:
 302         uint32_t index;
 303         BasicList<T> &bl;
 304         bool bListEnd;
 305     };
 306 }
 307
 308 #endif /* __GCStack__ */