PackedListI.H

Go to the documentation of this file.

/*---------------------------------------------------------------------------*\
  =========                 |
  \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   \\    /   O peration     |
    \\  /    A nd           | www.openfoam.com
     \\/     M anipulation  |
-------------------------------------------------------------------------------
    Copyright (C) 2011-2016 OpenFOAM Foundation
    Copyright (C) 2017-2025 OpenCFD Ltd.
-------------------------------------------------------------------------------
License
    This file is part of OpenFOAM.
 
    OpenFOAM 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 3 of the License, or
    (at your option) any later version.
 
    OpenFOAM 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 OpenFOAM.  If not, see <http://www.gnu.org/licenses/>.
 
\*---------------------------------------------------------------------------*/
 
#include "error.H"
 
// * * * * * * * * * * * * Protected Member Functions  * * * * * * * * * * * //
 
template<unsigned Width>
inline unsigned int Foam::PackedList<Width>::repeated_value(unsigned val)
{
    return BitOps::repeat_value<block_type,Width>(val);
}
 
 
template<unsigned Width>
inline unsigned int Foam::PackedList<Width>::readValue(Istream& is)
{
    const unsigned int val = readLabel(is);
 
    if (val > max_value)
    {
        FatalIOErrorInFunction(is)
            << "Out-of-range value " << val << " for PackedList<" << Width
            << ">. Maximum permitted value is " << max_value << "."
            << exit(FatalIOError);
    }
 
    return val;
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::setPair(Istream& is)
{
    is.readBegin("Tuple2<label,uint32>");
 
    const label ind = readLabel(is);
    const unsigned int val = readLabel(is);
 
    is.readEnd("Tuple2<label,uint32>");
 
    if (val > max_value)
    {
        FatalIOErrorInFunction(is)
            << "Out-of-range value " << val << " for PackedList<" << Width
            << "> at index " << ind
            << ". Maximum permitted value is " << max_value << "."
            << exit(FatalIOError);
    }
 
    set(ind, val);
 
    is.check(FUNCTION_NAME);
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::clear_trailing_bits()
{
    // Mask off any partial rubbish in final block
    const unsigned int blk = size() / elem_per_block;
    const unsigned int off = size() % elem_per_block;
 
    if (off)
    {
        blocks_[blk] &= mask_lower(off);
    }
}
 
 
template<unsigned Width>
inline bool Foam::PackedList<Width>::trim(label minpos)
{
    if (empty())
    {
        return false;  // Trivial case
    }
 
    const label orig = size();
    if (orig < minpos)
    {
        minpos = orig;   // Don't allow allow accidental growth!
    }
 
    for (label blocki = num_blocks(size())-1; blocki >= 0; --blocki)
    {
        // Truncate to the block begin
        size_ = blocki * elem_per_block;
 
        unsigned int blockval = blocks_[blocki];
 
        // Some bits were found in the block, increment size again
        if (blockval)
        {
            for (; blockval; ++size_)
            {
                blockval >>= Width;
            }
            break;
        }
        else if (size_ < minpos)
        {
            break;
        }
    }
 
    if (size_ < minpos)
    {
        size_ = minpos;
    }
 
    return (size() != orig);
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::copyAssign(const PackedList<Width>& rhs)
{
    // Self-assignment silently ignored
    blocks_ = rhs.blocks_;
    size_ = rhs.size_;
}
 
 
template<unsigned Width>
inline Foam::label Foam::PackedList<Width>::first_block() const
{
    if (size())
    {
        const label nblocks = num_blocks(size());
 
        for (label blocki=0; blocki < nblocks; ++blocki)
        {
            if (blocks_[blocki])
            {
                return blocki;
            }
        }
    }
 
    return -1;
}
 
 
template<unsigned Width>
inline Foam::label Foam::PackedList<Width>::first_not_block() const
{
    if (!size())
    {
        return -1;
    }
 
    // Check on complement (changes 0 <-> 1).
    // If any 1's now appear, there was a 0 bit before
 
    const label nblocks = num_blocks(size());
 
    // Extra bits in the final block?
    const unsigned int off = size() % elem_per_block;
 
    if (!off)
    {
        for (label blocki=0; blocki < nblocks; ++blocki)
        {
            if (~(blocks_[blocki]))
            {
                return blocki;
            }
        }
    }
    else
    {
        for (label blocki=0; blocki < nblocks-1; ++blocki)
        {
            if (~(blocks_[blocki]))
            {
                return blocki;
            }
        }
 
        // The final block needs masking
        if (~(blocks_[nblocks-1]) & mask_lower(off))
        {
            return nblocks-1;
        }
    }
 
    return -1;
}
 
 
// * * * * * * * * * * * * * * * Specializations * * * * * * * * * * * * * * //
 
namespace Foam
{
 
// constexpr noexcept
template<> inline unsigned int PackedList<1>::repeated_value(unsigned val)
{
    return (val ? ~0u : 0u);
}
 
template<> inline unsigned int PackedList<1>::readValue(Istream& is)
{
    return readBool(is);
}
 
template<> inline void PackedList<1>::setPair(Istream& is)
{
    set(readLabel(is), true);
}
 
} // End namespace Foam
 
 
// * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
 
template<unsigned Width>
inline constexpr Foam::PackedList<Width>::PackedList() noexcept
:
    blocks_(),
    size_(0)
{}
 
 
template<unsigned Width>
inline Foam::PackedList<Width>::PackedList(const label numElem)
:
    blocks_(num_blocks(numElem), 0u),
    size_(numElem)
{}
 
 
template<unsigned Width>
inline Foam::PackedList<Width>::PackedList
(
    const label numElem,
    const unsigned int val
)
:
    blocks_(num_blocks(numElem), 0u),
    size_(numElem)
{
    if (val)
    {
        operator=(val);
    }
}
 
 
template<unsigned Width>
inline Foam::PackedList<Width>::PackedList(Istream& is)
:
    blocks_(),
    size_(0)
{
    readList(is);
}
 
 
template<unsigned Width>
inline Foam::PackedList<Width>::PackedList(const PackedList<Width>& list)
:
    blocks_(list.blocks_),
    size_(list.size_)
{}
 
 
template<unsigned Width>
inline Foam::PackedList<Width>::PackedList(PackedList<Width>&& list)
:
    blocks_(std::move(list.blocks_)),
    size_(list.size_)
{
    list.size_ = 0;
}
 
 
template<unsigned Width>
inline Foam::PackedList<Width>::PackedList(const labelUList& values)
:
    blocks_(num_blocks(values.size()), 0u),
    size_(values.size())
{
    const label len = values.size();
 
    // Could add more intelligent filling (blockwise),
    // but likely done fairly infrequently
 
    for (label i = 0; i < len; ++i)
    {
        const unsigned int val(values[i]);
        if (val) set(i, val);
    }
}
 
 
template<unsigned Width>
template<class Addr>
inline Foam::PackedList<Width>::PackedList
(
    const IndirectListBase<label, Addr>& values
)
:
    blocks_(num_blocks(values.size()), 0u),
    size_(values.size())
{
    const label len = values.size();
 
    // Could add more intelligent filling (blockwise),
    // but likely done fairly infrequently
 
    for (label i = 0; i < len; ++i)
    {
        const unsigned int val(values[i]);
        if (val) set(i, val);
    }
}
 
 
template<unsigned Width>
inline Foam::autoPtr<Foam::PackedList<Width>>
Foam::PackedList<Width>::clone() const
{
    return autoPtr<PackedList<Width>>::New(*this);
}
 
 
// * * * * * * * * * * * * * * * * References * * * * * * * * * * * * * * * * //
 
template<unsigned Width>
inline Foam::PackedList<Width>::reference::reference
(
    PackedList<Width>* parent,
    const label index
)
:
    ref_(parent->blocks_[index / elem_per_block]),
    shift_(Width * (index % elem_per_block))
{}
 
 
template<unsigned Width>
inline unsigned int Foam::PackedList<Width>::reference::get() const
{
    return ((ref_ >> shift_) & max_value);
}
 
 
template<unsigned Width>
inline bool Foam::PackedList<Width>::reference::set(const unsigned int val)
{
    const unsigned int mask = (max_value << shift_);
    const unsigned int prev = ref_;
 
    if (val >= max_value)
    {
        ref_ |= mask;  // Overflow is max_value, so fill entirely
    }
    else
    {
        ref_ &= ~mask;
        ref_ |= mask & (val << shift_);
    }
 
    return (prev != ref_);
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::reference::operator=
(
    const reference& other
)
{
    // Accepts self-assignment
    this->set(other.get());
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::reference::operator=
(
    const unsigned int val
)
{
    this->set(val);
}
 
 
template<unsigned Width>
inline Foam::PackedList<Width>::reference::operator unsigned int () const
{
    return this->get();
}
 
 
// * * * * * * * * * * * * * * * Member Functions  * * * * * * * * * * * * * //
 
template<unsigned Width>
inline void Foam::PackedList<Width>::checkIndex(const label i) const
{
    if (!size_)
    {
        FatalErrorInFunction
            << "attempt to access element " << i << " from zero sized list"
            << abort(FatalError);
    }
    else if (i < 0 || i >= size_)
    {
        FatalErrorInFunction
            << "index " << i << " out of range [0," << size_ << ")"
            << abort(FatalError);
    }
}
 
 
template<unsigned Width>
inline Foam::label Foam::PackedList<Width>::capacity() const noexcept
{
    return elem_per_block * blocks_.size();
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::resize_nocopy
(
    const label numElem
)
{
    this->resize(numElem);
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::resize
(
    const label newSize,
    const unsigned int val
)
{
    reserve(newSize);
 
    const label oldSize = size();
    size_ = newSize;
 
    if (oldSize < newSize)
    {
        // Fill new elements or newly exposed elements
        if (val)
        {
            // Fill value for complete blocks
            const unsigned int blockval = repeated_value(val);
 
            // Fill complete blocks
            const label oldLen = num_blocks(oldSize);
            const label newLen = num_blocks(size());
            for (label blocki = oldLen; blocki < newLen; ++blocki)
            {
                blocks_[blocki] = blockval;
            }
 
            // Finish previous partial block, preserve existing value
            {
                const unsigned int blk = oldSize / elem_per_block;
                const unsigned int off = oldSize % elem_per_block;
                if (off)
                {
                    const unsigned int mask = mask_lower(off);
 
                    blocks_[blk] &= mask;
                    blocks_[blk] |= ~mask & blockval;
                }
            }
 
            clear_trailing_bits();
        }
    }
    else if (newSize < oldSize)
    {
        // The list is now shorter than before, so we zero assign the unused
        // blocks and any trailing junk. This costs slightly here, but make
        // things much simpler elsewhere.
 
        // Clear complete blocks
        const label oldLen = num_blocks(oldSize);
        const label newLen = num_blocks(size());
        for (label blocki = newLen; blocki < oldLen; ++blocki)
        {
            blocks_[blocki] = 0u;
        }
 
        clear_trailing_bits();
    }
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::setCapacity(const label numElem)
{
    const label nblocks = num_blocks(numElem);
 
    blocks_.resize(nblocks, 0u);
 
    if (numElem < size())
    {
        size_ = numElem;
        clear_trailing_bits();
    }
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::reserve(const label numElem)
{
    const label oldLen = blocks_.size();
    const label newLen = num_blocks(numElem);
 
    // Allocate more capacity if necessary
    if (oldLen < newLen)
    {
        blocks_.resize
        (
            // SizeMin=16, allocation doubling
            Foam::max(16, Foam::max(newLen, 2*oldLen)),
            0u
        );
    }
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::reserve_exact(const label numElem)
{
    const label oldLen = blocks_.size();
    const label newLen = num_blocks(numElem);
 
    // Allocate more capacity if necessary
    if (oldLen < newLen)
    {
        blocks_.resize
        (
            // SizeMin=16
            Foam::max(16, newLen),
            0u
        );
    }
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::reset()
{
    blocks_ = 0u;
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::clear()
{
    reset();
    size_ = 0;
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::clearStorage()
{
    blocks_.clear();
    size_ = 0;
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::shrink_to_fit()
{
    // Any unneeded space allocated?
    const label nblocks = num_blocks(size());
    if (nblocks < blocks_.size())
    {
        blocks_.resize(nblocks);
    }
}
 
 
template<unsigned Width>
inline Foam::label Foam::PackedList<Width>::num_blocks() const noexcept
{
    return num_blocks(size());
}
 
 
template<unsigned Width>
inline const char* Foam::PackedList<Width>::cdata_bytes() const noexcept
{
    return blocks_.cdata_bytes();
}
 
 
template<unsigned Width>
inline char* Foam::PackedList<Width>::data_bytes() noexcept
{
    return blocks_.data_bytes();
}
 
 
template<unsigned Width>
inline std::streamsize Foam::PackedList<Width>::size_data() const noexcept
{
    return num_blocks(size());
}
 
 
template<unsigned Width>
inline std::streamsize Foam::PackedList<Width>::size_bytes() const noexcept
{
    return num_blocks(size()) * sizeof(block_type);
}
 
 
template<unsigned Width>
inline std::streamsize Foam::PackedList<Width>::byteSize() const noexcept
{
    return this->size_bytes();
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::swap(PackedList<Width>& rhs)
{
    if (this == &rhs)
    {
        return;  // Self-swap is a no-op
    }
 
    blocks_.swap(rhs.blocks_);
    std::swap(size_, rhs.size_);
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::transfer(PackedList<Width>& rhs)
{
    if (this == &rhs)
    {
        return;  // Self-assignment is a no-op
    }
 
    blocks_.transfer(rhs.blocks_);
    size_ = rhs.size_;
    rhs.size_ = 0;
}
 
 
template<unsigned Width>
inline unsigned int Foam::PackedList<Width>::get(const label i) const
{
    if (i < 0 || i >= size())
    {
        #ifdef FULLDEBUG
        if (i < 0)
        {
            WarningInFunction
                << "Ignoring attempt to get a negative index " << i
                << " range is [0," << size_ << ")"
                << endl;
        }
        #endif
 
        return 0u;        // Out-of-bounds (lazy): return 0 (false)
    }
 
    return reference(const_cast<PackedList<Width>*>(this), i).get();
}
 
 
template<unsigned Width>
inline bool Foam::PackedList<Width>::set
(
    const label i,
    const unsigned int val
)
{
    if (i < 0)
    {
        #ifdef FULLDEBUG
        WarningInFunction
            << "Ignoring attempt to set a negative index " << i
            << " range is [0," << size_ << ")"
            << endl;
        #endif
 
        return false;       // Out-of-bounds: ignore
    }
    else if (i >= size())
    {
        if (!val)           // Unset out-of-bounds: ignore
        {
            return false;
        }
 
        resize(i + 1);      // Lazy evaluation: adjust size for assign
    }
 
    return reference(this, i).set(val);
}
 
 
template<unsigned Width>
inline bool Foam::PackedList<Width>::unset(const label i)
{
    if (i < 0 || i >= size())
    {
        return false;       // Unset out-of-bounds: ignore
    }
 
    return reference(this, i).set(0u);
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::push_back(const unsigned int val)
{
    const label idx = size();
    reserve(idx + 1);
    ++size_;
 
    reference(this, idx).set(val);
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::pop_back(label n)
{
    if (n >= size())
    {
        clear();
    }
    else if (n > 0)
    {
        resize(size() - n);
    }
}
 
 
template<unsigned Width>
inline unsigned int Foam::PackedList<Width>::remove()
{
    // Location of last element and simultaneously the new size
    const label idx = size()-1;
 
    if (idx < 0)
    {
        FatalErrorInFunction
            << "List is empty" << abort(FatalError);
    }
 
    const unsigned int old = reference(this, idx).get();
    resize(idx);
 
    return old;
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::fill(const unsigned int val)
{
    if (empty())
    {
        return;  // Trivial case
    }
 
    const label nblocks = num_blocks(size());
 
    // Fill value for complete blocks
    const unsigned int blockval = (val ? repeated_value(val) : 0u);
 
    for (label blocki=0; blocki < nblocks; ++blocki)
    {
        blocks_[blocki] = blockval;
    }
 
    if (val)
    {
        clear_trailing_bits();
    }
}
 
 
// * * * * * * * * * * * * * * * Member Operators  * * * * * * * * * * * * * //
 
template<unsigned Width>
inline unsigned int Foam::PackedList<Width>::operator[](const label i) const
{
    return get(i);
}
 
 
template<unsigned Width>
inline typename Foam::PackedList<Width>::reference
Foam::PackedList<Width>::operator[](const label i)
{
    #ifdef FULLDEBUG
    checkIndex(i);
    #endif
    return reference(this, i);
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::operator=(const PackedList<Width>& rhs)
{
    copyAssign(rhs);
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::operator=(PackedList<Width>&& rhs)
{
    transfer(rhs);
}
 
 
template<unsigned Width>
inline void Foam::PackedList<Width>::operator=(const unsigned int val)
{
    fill(val);
}
 
 
// * * * * * * * * * * * * * * * Global Operators  * * * * * * * * * * * * * //
 
template<unsigned Width>
inline bool Foam::operator==
(
    const PackedList<Width>& a,
    const PackedList<Width>& b
)
{
    return a.equal(b);
}
 
 
template<unsigned Width>
inline bool Foam::operator!=
(
    const PackedList<Width>& a,
    const PackedList<Width>& b
)
{
    return !a.equal(b);
}
 
 
// ************************************************************************* //