-3
\$\begingroup\$

I have re-implemented in C++ an algorithm already in JavaScript available here and there.

C++ code works fine, but I have memory management concerns:

  1. I allocate memory with such statement as m_root = new Block(...) dangerously
  2. When freeing memory with if (m_fit) { delete m_fit; m_fit = nullptr; }, exceptions are thrown

I feel like my C++ code is leaking memory, I wonder if something is noticeably wrong:

Calling the algorithm

void createBlocks(std::vector<Block> &blocks)
{
    for (int i = 0; i < 100; ++i) {
        float w = i * 1.1; // semi-random
        float h = i * 0.9; // semi-random
        float x = i - 10;  // semi-random
        float y = i + 5;   // semi-random
        Block block = Block(w, h, x, y);
        blocks.push_back(block);
    }
}

void sortDescendingInSize(std::vector<Block> &blocks)
{
    std::sort(blocks.begin(), blocks.end(), [](const Block& first, const Block &second) {
        float firstMaxSide  = std::max( first.m_h,  first.m_w);
        float secondMaxSide = std::max(second.m_h, second.m_w);
        // returns ​true if the first argument is ordered before the second
        // order descending
        return firstMaxSide > secondMaxSide;
    });
}

void main()
{
    std::vector<Block> blocks = std::vector<Block>();

    createBlocks(blocks);

    if (blocks.empty())
        return;

    sortDescendingInSize(blocks);

    GrowingPacker growingPacker = GrowingPacker();
    growingPacker.fit(blocks);

    for (const Block &block : blocks) {
        if (block.m_fit && block.m_item) {
            std::cout <<
                      << "w:" << block.m_w << "h:" << block.m_h
                      << "fit->w:" << block.m_fit->m_w << "fit->h:" << block.m_fit->m_h
                      << "fit->x:" << block.m_fit->m_x << "fit->y:" << block.m_fit->m_y;
        }
    }
}

Algorithm class definition

#ifndef GROWINGPACKER_H
#define GROWINGPACKER_H

#include "vector"
#include "src/pack/block.h"

class GrowingPacker
{
public:
    GrowingPacker();
    void fit(std::vector<Block> &blocks);

private:
    Block *findNode(Block *root, float w, float h);
    Block *splitNode(Block *node, float w, float h);
    Block *growNode(float w, float h);
    Block *growRight(float w, float h);
    Block *growDown(float w, float h);

private:
    Block *m_root;
};

#endif // GROWINGPACKER_H

Algorithm class implementation

#include "growingpacker.h"

GrowingPacker::GrowingPacker()
{

}

void GrowingPacker::fit(std::vector<Block> &blocks)
{
    size_t len = blocks.size();
    float w = len > 0 ? blocks[0].m_w : 0;
    float h = len > 0 ? blocks[0].m_h : 0;
    m_root = new Block(w,h, 0, 0);
    for (Block &block : blocks) {
        Block *node = findNode(m_root, block.m_w, block.m_h);
        if (node)
            block.m_fit = splitNode(node, block.m_w, block.m_h);
        else
            block.m_fit = growNode(block.m_w, block.m_h);
    }
    return;
}

Block *GrowingPacker::findNode(Block *root, float w, float h)
{
    if (root->m_used) {
        Block *tmp = findNode(root->m_right, w, h);
        if (tmp)
            return tmp;
        else
            return findNode(root->m_down, w, h);
    } else if ( w <= root->m_w && h <= root->m_h)
        return root;
    else
        return nullptr;
}

Block *GrowingPacker::splitNode(Block *node, float w, float h)
{
    node->m_used = true;
    node->m_down  = new Block(node->m_w,     node->m_h - h, node->m_x,     node->m_y + h);
    node->m_right = new Block(node->m_w - w, h,             node->m_x + w, node->m_y    );
    return node;
}

Block *GrowingPacker::growNode(float w, float h)
{
    bool canGrowDown  = w <= m_root->m_w;
    bool canGrowRight = h <= m_root->m_h;

    // attempt to keep square-ish by growing right when height is much greater than width
    bool shouldGrowRight = canGrowRight && m_root->m_h >= (m_root->m_w + w);
    // attempt to keep square-ish by growing down  when width  is much greater than height
    bool shouldGrowDown  = canGrowDown  && m_root->m_w >= (m_root->m_h + h);

    if (shouldGrowRight)
        return growRight(w, h);
    else if (shouldGrowDown)
        return growDown(w, h);
    else if (canGrowRight)
        return growRight(w, h);
    else if (canGrowDown)
        return growDown(w, h);
    else
        // need to ensure sensible root starting size to avoid this happening
        return nullptr;
}

Block *GrowingPacker::growRight(float w, float h)
{
    m_root = new Block(m_root->m_w + w
                       , m_root->m_h
                       , 0.0f
                       , 0.0f
                       , true
                       , m_root
                       , new Block(w, m_root->m_h, m_root->m_w, 0.0f)
                       );
    Block *node = findNode(m_root, w, h);
    if (node)
        return splitNode(node, w, h);
    else
        return nullptr;
}

Block *GrowingPacker::growDown(float w, float h)
{
    m_root = new Block(m_root->m_w
                       , m_root->m_h + h
                       , 0.0f
                       , 0.0f
                       , true
                       , new Block (m_root->m_w, h, 0.0f, m_root->m_h)
                       , m_root
                       );
    Block *node = findNode(m_root, w, h);
    if (node)
        return splitNode(node, w, h);
    else
        return nullptr;
}

Block/node class definition which is used by algorithm

#ifndef BLOCK_H
#define BLOCK_H

class EditorSceneItem;

class Block
{
public:
    Block();
    Block(float w, float h, float x, float y);
    Block(float w, float h, float x, float y,
          bool used,
          Block *down, Block *right);
    // Copy constructor
    Block(const Block &other);
    // Copy assignment operator
    Block & operator= ( const Block& other );
    // Destructor
    ~Block();
    // Move constructor
    Block(Block&& other);
    // Move assignment operator
    Block& operator=(Block &&other);

private:
    void freePossibleAllocatedMemory();
    void releaseResourcesWithoutFreeingMemory();
    void swapInto(Block& destination) const noexcept;

public:
    float m_w;
    float m_h;
    float m_x;
    float m_y;
    bool m_used;
    Block *m_down = nullptr;
    Block *m_right = nullptr;
    Block *m_fit = nullptr;
};

#endif // BLOCK_H

Block/node class implementation

#include "block.h"

Block::Block()
    :
      m_w(0.0f), m_h(0.0f)
    , m_x(0.0f), m_y(0.0f)
    , m_used(false)
    , m_down(nullptr)
    , m_right(nullptr)
    , m_fit(nullptr)
{

}

Block::Block(float w, float h, float x, float y)
    :
      m_w(w), m_h(h)
    , m_x(x), m_y(y)
    , m_used(false)
    , m_down(nullptr)
    , m_right(nullptr)
    , m_fit(nullptr)
{

}

Block::Block(float w, float h, float x, float y,
             bool used,
             Block *down, Block *right)
    :
      m_w(w), m_h(h)
    , m_x(x), m_y(y)
    , m_used(used)
    , m_down(down)
    , m_right(right)
    , m_fit(nullptr)
{

}

Block::Block(const Block &other)
    :
      m_w(other.m_w), m_h(other.m_h)
    , m_x(other.m_x), m_y(other.m_y)
    , m_used(other.m_used)
    , m_down(other.m_down)
    , m_right(other.m_right)
    , m_fit(other.m_fit)
{}

Block & Block::operator= ( const Block& other )
{
    // Self assignment
    if (&other == this)
        return *this;

    this->freePossibleAllocatedMemory();
    other.swapInto(*this);
    return *this;
}

Block::~Block()
{
    freePossibleAllocatedMemory();
}

Block::Block(Block&& other)
    : Block() // delegate to the default constructor
{
    other.swapInto(*this);
    other.releaseResourcesWithoutFreeingMemory();
}

Block& Block::operator=(Block &&other)
{
    // Self assignment
    if (this == &other)
        return *this;

    this->freePossibleAllocatedMemory();

    other.swapInto(*this);
    other.releaseResourcesWithoutFreeingMemory();
    return *this;
}

void Block::freePossibleAllocatedMemory()
{

    // ** STRANGE: an exception is thrown at following lines when freeing memory
    // Exception is avoided by commenting out lines
    // Exception is possibly due to bad memory management

    if (m_down) {
        delete m_down;
        m_down = nullptr;
    }
    if (m_right) {
        delete m_right;
        m_right = nullptr;
    }
    if (m_fit) {
        delete  m_fit;
        m_fit = nullptr;
    }

}

void Block::releaseResourcesWithoutFreeingMemory()
{
    // Release source
    m_w = 0.0f;
    m_h = 0.0f;
    m_x = 0.0f;
    m_y = 0.0f;
    m_used = false;
    m_down = nullptr;
    m_right = nullptr;
    m_fit = nullptr;
}

void Block::swapInto(Block& destination) const noexcept
{
    destination.m_w = m_w; // Don't check equality of float
    destination.m_h = m_h;
    destination.m_x = m_x;
    destination.m_y = m_y;
    if (destination.m_used != m_used)
        destination.m_used = m_used;
    if (destination.m_down != m_down)
        destination.m_down = m_down;
    if (destination.m_right != m_right)
        destination.m_right = m_right;
    if (destination.m_fit != m_fit)
        destination.m_fit = m_fit;
}

Thanks for your review =)

\$\endgroup\$
  • 2
    \$\begingroup\$ Instead of managing memory allocation / deallocation manually you could use smart pointers with the correct semantics you need. \$\endgroup\$ – πάντα ῥεῖ Jul 27 at 7:36
  • \$\begingroup\$ "When freeing memory with if (m_fit) { delete m_fit; m_fit = nullptr; }, exceptions are thrown" Note that your question is off-topic for Code Review. Only working code is ready for review. \$\endgroup\$ – πάντα ῥεῖ Jul 27 at 7:57
  • \$\begingroup\$ @πάνταῥεῖ Thanks, I edited it out. \$\endgroup\$ – user4838962 Jul 27 at 8:57
  • 3
    \$\begingroup\$ Well, I am afraid editing out doesn't make that much better. Does your code throw exceptions or not? If so, it's not working properly. \$\endgroup\$ – πάντα ῥεῖ Jul 27 at 9:04
  • \$\begingroup\$ Recommended read: What is The Rule of Three? \$\endgroup\$ – πάντα ῥεῖ Jul 27 at 9:13
0
\$\begingroup\$

As suggested by @πάνταῥεῖ I replaced all instances of Block * pointer in the code with std::shared_ptr<Block> and I feel much better regarding memory management.

\$\endgroup\$
  • \$\begingroup\$ @πάνταῥεῖ Thanks. Also the exception is resolved after implementing std::shared_ptr<> =) \$\endgroup\$ – user4838962 Jul 27 at 11:17
  • 1
    \$\begingroup\$ would you please explain your answer further, to make this more of a review? \$\endgroup\$ – Malachi Jul 28 at 15:48
  • \$\begingroup\$ @Malachi Thanks, I'm going to explain further. \$\endgroup\$ – user4838962 Jul 29 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.