union_find.h

Go to the documentation of this file.

/*
 * This program source code file is part of KiCad, a free EDA CAD application.
 *
 * Copyright The KiCad Developers, see AUTHORS.txt for contributors.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#ifndef KICAD_CORE_UNION_FIND_H
#define KICAD_CORE_UNION_FIND_H
 
#include <atomic>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <stdexcept>
#include <utility>
#include <vector>

class KI_UNION_FIND
{
public:
    explicit KI_UNION_FIND( size_t aCount ) { Reset( aCount ); }
 
    KI_UNION_FIND( const KI_UNION_FIND& ) = delete;
    KI_UNION_FIND& operator=( const KI_UNION_FIND& ) = delete;

    void Reset( size_t aCount )
    {
        // Parents are uint32_t to keep the array dense, so a larger set would alias index
        // 2^32 onto index zero
        if( aCount > static_cast<size_t>( std::numeric_limits<uint32_t>::max() ) )
            throw std::length_error( "KI_UNION_FIND exceeds its 2^32 element limit" );
 
        std::vector<std::atomic<uint32_t>> fresh( aCount );
        m_parent.swap( fresh );
 
        for( size_t ii = 0; ii < aCount; ++ii )
            m_parent[ii].store( static_cast<uint32_t>( ii ), std::memory_order_relaxed );
 
        m_components.store( aCount, std::memory_order_relaxed );
    }
 
    size_t Size() const { return m_parent.size(); }

    size_t ComponentCount() const { return m_components.load( std::memory_order_relaxed ); }

    bool Unite( size_t aA, size_t aB )
    {
        uint32_t u = static_cast<uint32_t>( aA );
        uint32_t v = static_cast<uint32_t>( aB );
        uint32_t pu = m_parent[u].load( std::memory_order_relaxed );
        uint32_t pv = m_parent[v].load( std::memory_order_relaxed );
 
        while( pu != pv )
        {
            // Work on the side with the larger parent so that a root always links downwards
            if( pu < pv )
            {
                std::swap( u, v );
                std::swap( pu, pv );
            }
 
            if( u == pu )
            {
                // u is a root and pv is below it, so this link is legal
                if( m_parent[u].compare_exchange_strong( pu, pv, std::memory_order_acq_rel,
                                                         std::memory_order_relaxed ) )
                {
                    m_components.fetch_sub( 1, std::memory_order_relaxed );
                    return true;
                }
 
                // The exchange reloaded pu with the value that won, so try again
            }
            else
            {
                // Lift u one level and climb.  A lost exchange costs only the shortcut, so
                // the result is ignored
                uint32_t grandparent = m_parent[pu].load( std::memory_order_relaxed );
                uint32_t expected = pu;
 
                m_parent[u].compare_exchange_strong( expected, grandparent,
                                                     std::memory_order_acq_rel,
                                                     std::memory_order_relaxed );
 
                u = pu;
                pu = m_parent[u].load( std::memory_order_relaxed );
            }
        }
 
        return false;
    }

    size_t Find( size_t aX ) const
    {
        uint32_t x = static_cast<uint32_t>( aX );
        uint32_t p = m_parent[x].load( std::memory_order_relaxed );
 
        while( p != x )
        {
            x = p;
            p = m_parent[x].load( std::memory_order_relaxed );
        }
 
        return x;
    }

    size_t FindCompress( size_t aX )
    {
        uint32_t x = static_cast<uint32_t>( aX );
        uint32_t p = m_parent[x].load( std::memory_order_relaxed );
 
        while( p != x )
        {
            uint32_t grandparent = m_parent[p].load( std::memory_order_relaxed );
 
            m_parent[x].store( grandparent, std::memory_order_relaxed );
            x = p;
            p = grandparent;
        }
 
        return x;
    }
 
    bool Connected( size_t aA, size_t aB ) const { return Find( aA ) == Find( aB ); }
 
private:
    std::vector<std::atomic<uint32_t>> m_parent;
    std::atomic<size_t>                m_components{ 0 };
};
 
#endif // KICAD_CORE_UNION_FIND_H