GA_DataBitArray.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        GA_DataBitArray.h ( GA Library, C++)
 *
 * COMMENTS:    A very simple array used to store attribute data.  Some areas
 *              of the array may be "vacant".
 */

#ifndef __GA_DataBitArray__
#define __GA_DataBitArray__

#include "GA_API.h"
#include "GA_Types.h"

#include <UT/UT_Array.h>

#include <SYS/SYS_Align.h>
#include <SYS/SYS_AtomicInt.h>
#include <SYS/SYS_Types.h>

#include <iosfwd>
#include <stddef.h>


class GA_Defragment;
class GA_LoadMap;
class GA_MergeMap;
class GA_MergeOffsetMap;
class GA_Range;
class UT_IStream;
class UT_JSONWriter;
class UT_JSONParser;
class UT_JSONValue;
class UT_MemoryCounter;
class UT_Options;

/// @brief An array of bits.
///
/// GA_DataBitArray provides an efficient way of storing bit arrays.
///
/// There are basic operations on the array.
///
/// See also: @ref JSON-GA_DataBitArray
///
class GA_API GA_DataBitArray 
{
public:
     GA_DataBitArray(GA_Offset size, bool value);
    ~GA_DataBitArray();

    /// Change the size of the array
    void         setArraySize(GA_Offset size);

    /// Query the size of the array
    GA_Offset    getArraySize() const { return mySize; }

    /// Clear all entries to the default value
    void         clear();

    /// Clear a specific offset to the default
    void         clearOffset(GA_Offset off, GA_Offset num);

    /// Set all entries to the given value
    void         makeConstant(bool value);

    /// Try to compress all pages overlapping the specified offset range.
    void        tryCompressAllPages(GA_Offset start_offset = GA_Offset(0),
                                    GA_Offset end_offset = GA_INVALID_OFFSET);

    /// Harden all pages overlapping the specified offset range.
    void        hardenAllPages(GA_Offset start_offset = GA_Offset(0),
                               GA_Offset end_offset = GA_INVALID_OFFSET);

    /// Report memory usage
    int64       getMemoryUsage(bool inclusive) const;

    /// Count memory usage using a UT_MemoryCounter in order to count
    /// shared memory correctly.
    /// If inclusive is true, the size of this object is counted,
    /// else only memory owned by this object is counted.
    /// If this is pointed to by the calling object, inclusive should be true.
    /// If this is contained in the calling object, inclusive should be false.
    /// (Its memory was already counted in the size of the calling object.)
    void countMemory(UT_MemoryCounter &counter, bool inclusive) const;

    /// Copy bit array from the source.  This will change the size
    /// of the array if the source size is different.
    bool        copyFrom(const GA_DataBitArray &src);

    /// mergeGrowArrayAndCopy() is called to grow the data array while
    /// appending or copying data from the source (non-interleaved merge).
    /// The array is resized to the new destination capacity (as defined by
    /// the map) and the data from the source array is copied over into the
    /// newly allocated area.
    void         mergeGrowArrayAndCopy(const GA_MergeMap &map,
                                       GA_AttributeOwner owner,
                                       const GA_DataBitArray &src);

    GA_Size      countSetBits(GA_Offset start, GA_Offset end) const;
    /// Query the length of repeated bit values starting from 'start' until
    /// 'end' or a change in bit values.
    void         getConstantSpan(GA_Offset start, GA_Offset end, GA_Size &size, bool &value) const;

    /// Access data from the array
    SYS_FORCE_INLINE
    bool get(GA_Offset idx) const
    {
        GA_PageNum pagenum = GAgetPageNum(idx);

        const Page *page = myPages(pagenum);
        if (isPageConstant(page))
            return getPageCVal(page);

        GA_PageOff pi = GAgetPageOff(idx);
        int i = getWordOffset(pi);
        int j = getBitOffset(pi);
        // NOTE: The "& 1" always results in either 0 or 1, so "!=0" isn't necessary.
        // VC++ would normally give a warning, but it seems to know about this one.
        return (page->asBitWord()[i] >> j) & 1;
    }
    /// Test if any bit in the range is set
    bool         isAnySet(const GA_Range &range) const;

    /// Set the value at a particular index
    void set(GA_Offset di, bool val)
    {
        GA_PageNum pagenum = GAgetPageNum(di);
        Page *page = myPages(pagenum);
        if (isPageConstant(page))
        {
            // Avoid creating a page if we are just setting it to the constant value
            bool cvalue = getPageCVal(page);
            if (cvalue == val)
                return;
            page = new Page(cvalue);
            myPages(pagenum) = page;
        }
        else if (page->isShared())
        {
            Page *oldpage = page;
            page = page->copy();
            myPages(pagenum) = page;
            oldpage->unref();
        }

        GA_PageOff pi = GAgetPageOff(di);
        int i = getWordOffset(pi);
        BitWord &d = page->asBitWord()[i];

        int j = getBitOffset(pi);
        // NOTE: The typecast on the 1 is so that if BitWord ever becomes 64 bits,
        // there won't be any undefined behaviour.
        BitWord mask = ((BitWord)1 << j);
        if (val)
            d |= mask;
        else
            d &= ~mask;
    }
    /// Set the value at a particular index
    template<bool VALUE>
    void set(GA_Offset di)
    {
        GA_PageNum pagenum = GAgetPageNum(di);
        Page *page = myPages(pagenum);
        if (isPageConstant(page))
        {
            // Avoid creating a page if we are just setting it to the constant value
            bool cvalue = getPageCVal(page);
            if (cvalue == VALUE)
                return;
            page = new Page(cvalue);
            myPages(pagenum) = page;
        }
        else if (page->isShared())
        {
            Page *oldpage = page;
            page = page->copy();
            myPages(pagenum) = page;
            oldpage->unref();
        }

        GA_PageOff pi = GAgetPageOff(di);
        int i = getWordOffset(pi);
        BitWord &d = page->asBitWord()[i];

        int j = getBitOffset(pi);
        // NOTE: The typecast on the 1 is so that if BitWord ever becomes 64 bits,
        // there won't be any undefined behaviour.
        BitWord mask = ((BitWord)1 << j);
        if (VALUE)
            d |= mask;
        else
            d &= ~mask;
    }
    void         set(GA_Offset di, const GA_DataBitArray &src, GA_Offset si)
                    { set(di, src.get(si)); }
    void         set(const GA_Range &it, bool val);
    void         set(GA_Offset span_start, GA_Offset span_end, bool val);
    void         set(const GA_Range &it, const GA_DataBitArray &src);
    void         set(const GA_Range &it, const GA_DataBitArray &src, const GA_Range &sit);
    void         set(const GA_DataBitArray &src, const GA_Range &sit,
                     const GA_MergeOffsetMap &map);

    /// @{
    /// Interface for defragmentation
    void        defragment(const GA_Defragment &defrag);
    /// @}

    /// Toggle the value at a particular index
    bool         toggle(GA_Offset idx);
    void         toggle(const GA_Range &it);

    /// Page accelerated full group operations
    void         andEqual(const GA_DataBitArray &src);
    void         xorEqual(const GA_DataBitArray &src);
    void         orEqual(const GA_DataBitArray &src);
    void         subEqual(const GA_DataBitArray &src);
    void         toggleAll(GA_Size numelements);

    /// A special method for loading group data from geo files.
    bool        loadGroupBitArrayH9(UT_IStream &is);
    bool        saveGroupBitArrayH9(std::ostream &os, int binary,
                        const GA_Range &it) const;

    /// @section JSON-GA_DataBitArray JSON Schema: GA_DataBitArray
    /// jsonSave() will save the array to a JSON stream.  There are multiple
    /// ways to store a bit-array.
    /// @code
    /// {
    ///     "name"          : "GA_DataBitArray",
    ///     "description"   : "A array bits",
    ///     "type"          : "orderedmap",
    ///     "properties"          : [
    ///         "boolRLE": {
    ///             "type"     : "array",
    ///             "items"    : [ "integer", "boolean" ]
    ///             "optional" : true,
    ///             "description": "A run length encoded bit array stored as a
    ///                        count/bool pair where the 'bool' value is
    ///                        repeated 'count' times.",
    ///         }
    ///         "i8": {
    ///             "type"        : "array",
    ///             "items"       : "integer",
    ///             "description" : "A array of 0/1, not very efficient",
    ///             "optional"    : true,
    ///         }
    ///     ]
    /// }
    /// @endcode
    /// @see @ref JSON_FileFormat
    bool        jsonSave(UT_JSONWriter &w, const GA_Range &it,
                            const UT_Options *options) const;

    /// Load from a JSON stream
    bool        jsonLoad(UT_JSONParser &p, const GA_LoadMap &map,
                        GA_AttributeOwner owner);
    /// Load from a JSON value
    bool        jsonLoad(UT_JSONParser &p, const UT_JSONValue &v,
                        const GA_LoadMap &map, GA_AttributeOwner owner);

    /// We want a bit pattern the size of a pointer whose every bit
    /// but the last is set.
    static constexpr uintptr_t BIT_PAGE_PTR_MASK = ~((uintptr_t)1);

    SYS_FORCE_INLINE bool isPageConstant(GA_PageNum pageid) const
    { return isPageConstant(myPages(pageid)); }

    SYS_FORCE_INLINE bool getPageCVal(GA_PageNum pageid) const
    { return getPageCVal(myPages(pageid)); }

    void tryCompressPage(GA_PageNum pageid);
    void makePageConstant(GA_PageNum pageid, bool value);

private:
    // A reference counted page of GA_PAGE_SIZE bits
    class GA_API Page
    {
    public:
        Page(bool def_val);
        ~Page();

        using BitWord = uint64;
        static constexpr uint64 BITS_PER_WORD = sizeof(BitWord)*8;

        int64 getMemoryUsage(bool inclusive) const
        { return inclusive ? sizeof(*this) : 0; }

        void countMemory(UT_MemoryCounter &counter, bool inclusive) const;

        // methods to manage sharing
        SYS_FORCE_INLINE
        void ref() const { myRefCount.add(1); }
        SYS_FORCE_INLINE
        void unref() { if(myRefCount.add(-1) == 0) delete this; }
        SYS_FORCE_INLINE
        bool isShared() const { return myRefCount.relaxedLoad() != 1; }
        Page *copy() const;

        /// Data accessors
        /// @{
        SYS_FORCE_INLINE
        const BitWord *asBitWord() const { return myData; }
        SYS_FORCE_INLINE
        BitWord *asBitWord() { return myData; }
        /// @}

    private:
        Page(const BitWord *data);

        mutable SYS_AtomicCounter myRefCount;

        // This should be 16byte aligned
        SYS_ALIGN16 BitWord myData[GA_PAGE_SIZE / BITS_PER_WORD];
    };

    using BitWord = Page::BitWord;
    static constexpr GA_Size BITS_PER_WORD = Page::BITS_PER_WORD;
    static constexpr GA_Size BITS_PER_WORD_MASK = BITS_PER_WORD-1;
    /// 64 = 2^6
    static constexpr uint64 BITS_PER_WORD_SHIFT = 3+3;

    SYS_FORCE_INLINE bool isPageConstant(const Page *ppage) const
    { return !(((uintptr_t)ppage) & BIT_PAGE_PTR_MASK); }

    SYS_FORCE_INLINE bool getPageCVal(const Page *ppage) const
    {
        UT_ASSERT_P(isPageConstant(ppage));
        return uintptr_t(ppage) & 1;
    }

    /// Functions for making bit masks from a start bit (inclusive)
    /// to an end bit (exclusive, though *must* be < BITS_PER_WORD)
    /// NOTE: The typecasts are in case ga_BitWord ever becomes 64-bit.
    /// @{
    static SYS_FORCE_INLINE BitWord
    startBitsMask(GA_Size end_bit)
    {
        return ((BitWord)1<<end_bit) - 1;
    }
    static SYS_FORCE_INLINE BitWord
    middleBitsMask(GA_Size start_bit,GA_Size end_bit)
    {
        return ((BitWord)1<<end_bit) - ((BitWord)1<<start_bit);
    }
    static SYS_FORCE_INLINE BitWord
    endBitsMask(GA_Size start_bit)
    {
        return                     0 - ((BitWord)1<<start_bit);
    }

    static SYS_FORCE_INLINE GA_Size
    getWordOffset(GA_Size offset)
    {
        SYS_STATIC_ASSERT((uint64(1) << BITS_PER_WORD_SHIFT) == BITS_PER_WORD);
        return offset >> BITS_PER_WORD_SHIFT;
    }

    static SYS_FORCE_INLINE GA_Size
    getWordCount(GA_Size nbits)
    {
        return (nbits + BITS_PER_WORD - 1) >> BITS_PER_WORD_SHIFT;
    }

    static SYS_FORCE_INLINE GA_Size
    getBitOffset(GA_Size offset)
    {
        return offset & BITS_PER_WORD_MASK;
    }
    /// @}

    void reallocPageTable(GA_Offset size);
    Page *harden(GA_PageNum pageid);

    bool             myDefault;
    UT_Array<Page *> myPages;
    GA_Offset        mySize;
};

#endif