Advertisement
JaminGrey

Untitled

Nov 6th, 2012
36
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. template<typename Type>
  2. class Grid
  3. {
  4. public:
  5.     Grid() : memory(nullptr)
  6.     {   }
  7.    
  8.     //Construct and call Resize().
  9.     Grid(const cRect &newBounds, const Type &value = Type()) : memory(nullptr)
  10.     {
  11.         this->Resize(newBounds, value);
  12.     }
  13.    
  14.     ~Grid()
  15.     {
  16.         //Clear the grid, calling the destructors on any constructed elements.
  17.         this->Clear();
  18.        
  19.         //Deallocate any reserved memory.
  20.         this->deallocate(this->memory);
  21.     }
  22.    
  23.     //Erases the grid, resetting the bounds to (0,0,0,0).
  24.     //Does not free the reserved capacity. Call Conserve() afterward to do that.
  25.     void Clear()
  26.     {
  27.         this->Resize(cRect(0,0,0,0));
  28.     }
  29.    
  30.     //================================================================
  31.    
  32.     //Resizes the grid to 'newBounds', constructing the new elements with 'value' (or the default constructor if 'value' is not set).
  33.     //If Grid doesn't have enough capacity, it'll reallocate storage and move the elements to new memory addresses.
  34.     //Throws std::bad_alloc if the allocation failed, and rethrows any exceptions thrown by element constructors or destructors.
  35.     void Resize(const cRect &newBounds, const Type &value = Type())
  36.     {
  37.         try
  38.         {
  39.             //[CAN THROW - Make sure no member variables are changed before these function calls]
  40.             cRect newCapacity = this->ensureCapacity(newBounds, true);
  41.            
  42.             //[CAN THROW - Make sure no member variables are changed before these function calls]
  43.             this->constructAdditions(this->bounds, newBounds, value);
  44.            
  45.             //Record the new capacity, after we are sure no exceptions were thrown and everything succeeded.
  46.             this->capacity = newCapacity;
  47.         }
  48.         catch(std::exception &exception)
  49.         {
  50.             Log::Message("...blah..."); //exception.what()
  51.             throw;
  52.         }
  53.         catch(...)
  54.         {
  55.             Log::Message("...blah..."); //Unknown exception
  56.             throw;
  57.         }
  58.  
  59.         this->bounds = newBounds;
  60.     }
  61.  
  62.     //================================================================
  63.    
  64. private:
  65.     //Constructs all the new elements between oldBounds and newBounds setting them to 'value'.
  66.     //If 'newBounds' is smaller than 'oldBounds', deconstructs the old elements.
  67.     void constructAdditions(const cRect &oldBounds, const cRect &newBounds, const Type &value = Type())
  68.     {
  69.         //The largest extent of both rects.
  70.         cRect totalArea = cRect::Encompassing(oldBounds, newBounds);
  71.         //The overlapping portion of both rects (if any).
  72.         cRect reducedArea = cRect::Intersection(oldBounds, newBounds);
  73.        
  74.         //-------------------------------------------
  75.        
  76.         //If a constructor throws an exception, we want to know which element it was,
  77.         //so we keep track of what the last point was before the exception was thrown.
  78.         cPoint lastPoint;
  79.        
  80.         try
  81.         {
  82.             for(cPoint point : newBounds)
  83.             {
  84.                 if(reducedArea.Contains(point))
  85.                 {
  86.                     //Do nothing - this area is already constructed.
  87.                 }
  88.                 else
  89.                 {
  90.                     lastPoint = point;
  91.                    
  92.                     //Needs to be constructed.
  93.                     this->construct((*this)[point], value);
  94.                 }
  95.             }
  96.         }
  97.         catch(...)
  98.         {
  99.             //Since we caught an exception, destruct every element we had previously constructed.
  100.             for(cPoint point : newBounds)
  101.             {
  102.                 if(reducedArea.Contains(point))
  103.                 {
  104.                     //Do nothing - this area is already constructed.
  105.                 }
  106.                 else if(point == lastPoint)
  107.                 {
  108.                     //Stop here - we didn't construct anything beyond this element.
  109.                     break;
  110.                 }
  111.                 else
  112.                 {
  113.                     //Destruct the element we previously constructed.
  114.                     this->destruct((*this)[point]);
  115.                 }
  116.             }
  117.            
  118.             throw;
  119.         }
  120.        
  121.         //-------------------------------------------
  122.        
  123.         //Destruct any elements that we no longer want (if we're resizing smaller than our previous size).
  124.         for(cPoint point : oldBounds)
  125.         {
  126.             if(reducedArea.Contains(point))
  127.             {
  128.                 //Do nothing - we're preserving these elements.
  129.             }
  130.             else
  131.             {
  132.                 //Needs to be destructed.
  133.                 this->destruct((*this)[point]);
  134.             }
  135.         }
  136.     }
  137.    
  138.     //================================================================
  139.    
  140.     //Construct a single element.
  141.     void construct(Type &element, const Type &value = Type())
  142.     {
  143.         new (&element) Type(value); //Call constructor.
  144.     }
  145.    
  146.     //Constructs an element with move semantics.
  147.     void moveConstruct(Type &element, Type &&value)
  148.     {
  149.         new (&element) Type(value); //Call move constructor.
  150.     }
  151.  
  152.     //Destruct a single element.
  153.     void destruct(Type &element)
  154.     {
  155.         element.~Type(); //Call destructor.
  156.     }
  157.    
  158.     //================================================================
  159.    
  160.     //Ensures *at least* enough room for 'bounds'. Returns the resulting capacity.
  161.     //If 'addExtra' is true, includes even more capacity for future growth.
  162.     cRect ensureCapacity(const cRect &bounds, bool addExtra)
  163.     {
  164.         //Check whether we have enough capacity to resize.
  165.         if(!this->capacity.Contains(bounds))
  166.         {
  167.             cRect desiredCapacity = bounds;
  168.            
  169.             if(addExtra)
  170.             {
  171.                 //If we're bothering to grow in size, we might as well reserve a little extra for future growth.
  172.                 int quarterWidth = (bounds.size.width / 4) + 1;
  173.                 int quarterHeight = (bounds.size.height / 4) + 1;
  174.                
  175.                 desiredCapacity.Pad(quarterWidth, quarterWidth, quarterHeight, quarterHeight);
  176.             }
  177.            
  178.             //Allocate and move the elements.
  179.             //[CAN THROW - Make sure no member variables are changed before this function call]
  180.             this->reallocateMemory(desiredCapacity);
  181.            
  182.             //Return the new capacity.
  183.             return desiredCapacity;
  184.         }
  185.        
  186.         //Return the current capacity.
  187.         return this->capacity;
  188.     }    
  189.    
  190.     //================================================================
  191.    
  192.     //This allocates enough memory for 'capacity', without constructing any elements.
  193.     Type *allocate(const cRect &capacity)
  194.     {
  195.         //Allocate the new memory.
  196.         size_t numElements = capacity.size.Area();
  197.         size_t numBytes = (sizeof(Type) * numElements);
  198.         void *data = ::operator new(numBytes);
  199.        
  200.         return static_cast<Type*>(data);
  201.     }
  202.    
  203.     //This deallocates 'memory', without calling any destructors.
  204.     void deallocate(Type *data)
  205.     {
  206.         ::operator delete(data);
  207.     }
  208.    
  209.     //================================================================
  210.    
  211.     //Reallocates the memory and migrates the elements over using moveElements().
  212.     //Throws std::bad_alloc if the allocation failed, and throws any exceptions thrown by element constructors.
  213.     void reallocateMemory(const cRect &newCapacity)
  214.     {
  215.         if(!this->memory)
  216.         {
  217.             //If we don't have any memory, just allocate some and don't worry about moving any elements.
  218.             //[CAN THROW - Make sure no member variables are changed before this function call]
  219.             this->memory = this->allocate(newCapacity);
  220.         }
  221.         else if(newCapacity.IsEmpty())
  222.         {
  223.             //Free all the memory.
  224.             this->deallocate(this->memory);
  225.             this->memory = nullptr;
  226.         }
  227.         else
  228.         {
  229.             //Allocate the new memory.
  230.             //Note: I put the allocated memory into a unique_ptr here, incase moveElements() throws.
  231.             //This way, the new memory is properly released.
  232.             //[CAN THROW - Make sure no member variables are changed before this function call]
  233.             std::unique_ptr<Type, use_operator_delete> newMemory = this->allocate(newCapacity);
  234.  
  235.             //A few extra variables for readability.
  236.             Type *oldMemory = this->memory;
  237.             const cRect &oldCapacity = this->capacity;
  238.            
  239.             //Move the elements.
  240.             //[CAN THROW - Make sure no member variables are changed before this function call]
  241.             this->moveElements(oldMemory, oldCapacity, newMemory.get(), newCapacity, this->bounds);
  242.  
  243.             //Delete the old memory.
  244.             this->deallocate(oldMemory);
  245.            
  246.             //And store the new pointer. Have the unique_ptr release ownership of the memory as well.
  247.             this->memory = newMemory.release();
  248.         }
  249.        
  250.         //Record the new capacity.
  251.         this->capacity = newCapacity;
  252.     }
  253.    
  254.     //Called by 'reallocateMemory' only.
  255.     void moveElements(Type *oldMemory, const cRect &oldCapacity, Type *newMemory,
  256.                       const cRect &newCapacity, const cRect &bounds)
  257.     {
  258.         //Insanity preservation.
  259.         //Assert that our elements are actually within the capacity of both the new and old blocks of memory.
  260.         BOOST_ASSERT(oldCapacity.Contains(bounds));
  261.         BOOST_ASSERT(newCapacity.Contains(bounds));
  262.        
  263.         //Assert that neither block of memory's size is empty (they have to have a positive non-zero width and height).
  264.         BOOST_ASSERT(!oldCapacity.IsEmpty());
  265.         BOOST_ASSERT(!newCapacity.IsEmpty());
  266.        
  267.         //Assert that neither pointer to the allocated memory is empty.
  268.         BOOST_ASSERT(oldMemory != nullptr);
  269.         BOOST_ASSERT(newMemory != nullptr);
  270.        
  271.         //The length of each 'row' of the grid's capacity in memory.
  272.         size_t oldStride = oldCapacity.size.width;
  273.         size_t newStride = newCapacity.size.width;
  274.        
  275.         //The initial offset of the actual bounds from the memory capacity.
  276.         size_t oldOffset = oldCapacity.Index(bounds.position);
  277.         size_t newOffset = newCapacity.Index(bounds.position);
  278.        
  279.         //The number of rows and columns of actual elements we need to move.
  280.         size_t rows = bounds.size.height;
  281.         size_t columns = bounds.size.width;
  282.        
  283.         //=================================================================
  284.        
  285.         //Incase a constructor throws an exception, keep track of the last row and column.
  286.         size_t lastRow = 0;
  287.         size_t lastColumn = 0;
  288.        
  289.         try
  290.         {
  291.             //Move-construct all the new elements.
  292.             for(size_t row = 0; row < rows; lastRow = row++)
  293.             {
  294.                 for(size_t column = 0; column < columns; lastColumn = column++)
  295.                 {
  296.                     size_t oldIndex = (row * oldStride) + column;
  297.                     oldIndex += oldOffset;
  298.                    
  299.                     size_t newIndex = (row * newStride) + column;
  300.                     newIndex += newOffset;
  301.                    
  302.                     //Construct the new location, and move the element.
  303.                     this->moveConstruct(newMemory[newIndex], std::move(oldMemory[oldIndex]));
  304.                 }
  305.             }
  306.         }
  307.         catch(...)
  308.         {
  309.             //Since we just caught an exception thrown from one of the element move-constructors,
  310.             //destruct all the new elements we just constructed, up until the failed constructor.
  311.             for(size_t row = 0; row < lastRow; row++)
  312.             {
  313.         //Go to the end of every row, but on the last row, just go to the last element we encountered.
  314.                 int &endOfColumn = (row == lastRow? lastColumn : columns);
  315.        
  316.                 for(size_t column = 0; column < endOfColumn; column++)
  317.                 {
  318.                     size_t newIndex = (row * newStride) + column;
  319.                     newIndex += newOffset;
  320.                    
  321.                     //Destruct the element we constructed in the previous for() loops.
  322.                     this->destruct(newMemory[newIndex]);
  323.                 }
  324.             }
  325.            
  326.             throw;
  327.         }
  328.        
  329.         //=================================================================
  330.        
  331.         //Destruct all the old elements.
  332.         for(size_t row = 0; row < rows; row++)
  333.         {
  334.             for(size_t column = 0; column < columns; column++)
  335.             {
  336.                 size_t oldIndex = (row * oldStride) + column;
  337.                 oldIndex += oldOffset;
  338.                
  339.                 //Destruct old location.
  340.                 this->destruct(oldMemory[oldIndex]);
  341.             }
  342.         }
  343.     }
  344.  
  345.     //================================================================
  346.    
  347. private:
  348.     Type *memory;
  349.    
  350.     cRect bounds; //Current grid boundaries.
  351.     cRect capacity; //Currently allocated memory capacity, guaranteed to be at least 'bounds' and maybe larger.
  352. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement