/ray/src/lib/tl/tlbitfield.h

Go to the documentation of this file.

 /*
 * lib/tl/tlbitfield.h 
 * 
 * Implementation of several bitfield templates for space-effcient storage 
 * of bits. 
 * 
 * Copyright (c) 2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
 * 
 * This file may be distributed and/or modified under the terms of the 
 * GNU General Public License version 2 as published by the Free Software 
 * Foundation. (See COPYING.GPL for details.)
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 * 
 */

#ifndef _TemplateLibrary_BitField_H_
#define _TemplateLibrary_BitField_H_ 1

#include <lib/sconfig.h>    /* MUST be first */

#include <lib/salloc.h>


template<typename T>inline uint CountBitsSet(T x)
{
    uint sum=0;
#if 0
    // According to tests, this is slightly slower. (WW)
    while(x)
    {  sum+=uint(x&T(1));  x>>=1;  }
#else
    // According to tests, this is slightly faster. (WW)
    for(; x; sum++)
    {  x &= x-T(1);  }
#endif
    return(sum);
}

template<typename T>inline uint CountBitsCleared(T x)
    {  return(uint(8*sizeof(T))-CountBitsSet(x));  }


template<typename T>inline int SearchFirstSetBit(T x)
{
#if 1
    T tst=T(1);
    for(int s=0; s<int(8*sizeof(T)); tst<<=1,s++)  if(x&tst)  return(s);
    return(-1);
#else
    // NOTE: This is actually SLOWER than the above!
    // Also, only works for sizeof(T)=sizeof(int). 
    return(x ? __builtin_ctz(x) : -1);   DO NOT USE.
#endif
}

template<typename T>inline int SearchFirstClearedBit(T x)
{
    T tst=T(1);
    for(int s=0; s<int(8*sizeof(T)); tst<<=1,s++)  if(!(x&tst))  return(s);
    return(-1);
}


template<typename T,size_t N>class TLStaticBitField
{
    friend int DoTestBitFields();
    public:
        typedef uint nents_t;
        
    private:
        static const nents_t nents = (N+8*sizeof(T)-1)/(8*sizeof(T));
        static const T band = T(8*sizeof(T)-1);
        static const int bshift = 
            sizeof(T)==1 ? 3 : 
            sizeof(T)==2 ? 4 : 
            sizeof(T)==4 ? 5 : 
            sizeof(T)==8 ? 6 : 
            sizeof(T)==16 ? 7 : 8;
        static const size_t bits_per_ent=8*sizeof(T);
        //--------
        // Ignore warning about left shift count >= width of type; this only 
        // happens for fast=1 which is caught in the other branch of the ?:. 
        static const T exmask = ( (N % (8*sizeof(T)))==0 ) ? 
            T(0) : ~((T(1)<<(N % (8*sizeof(T))))-1);
        
        static const T all_clr = T(0);
        static const T all_set = ~all_clr;
        
        T bits[nents];
        
        inline void _SetAllEnts(T val)
            {  for(nents_t i=0; i<nents; i++)  bits[i]=val;  }
        inline void _CopyFrom(const TLStaticBitField<T,N> &b)
            {  for(nents_t i=0; i<nents; i++)  bits[i]=b.bits[i];  }
        
    public:
        inline TLStaticBitField() {}
        inline TLStaticBitField(bool bitval)
            {  _SetAllEnts(bitval ? all_set : all_clr);  }
        inline TLStaticBitField(const TLStaticBitField<T,N> &b)
            {  _CopyFrom(b);  }
        inline ~TLStaticBitField() {}
        
        inline TLStaticBitField &operator=(const TLStaticBitField<T,N> &b)
            {  _CopyFrom(b);  return(*this);  }
        
        inline void SetBit(size_t bit)
            {  bits[bit>>bshift]|=T(1)<<(bit & band);  }
        inline void ClrBit(size_t bit)
            {  bits[bit>>bshift]&=~(T(1)<<(bit & band));  }
        inline bool GetBit(size_t bit)
            {  return((bits[bit>>bshift]>>(bit & band))&T(1));  }
        inline void AssBit(size_t bit,bool val)
            {  if(val) SetBit(bit); else ClrBit(bit);  }
        
        inline void SetAll()
            {  _SetAllEnts(all_set);  }
        inline void ClrAll()
            {  _SetAllEnts(all_clr);  }
        
        inline size_t CountSet()  // non-const!
        {
            bits[nents-1]&=~exmask;   // Clear excess bits. 
            size_t sum=0;
            for(nents_t i=0; i<nents; i++)  sum+=CountBitsSet(bits[i]);
            return(sum);
        }
        
        inline size_t CountClr()  // non-const!
        {
            bits[nents-1]|=exmask;   // Set excess bits. 
            size_t sum=0;
            for(nents_t i=0; i<nents; i++)  sum+=CountBitsCleared(bits[i]);
            return(sum);
        }
        
        inline ssize_t SearchFirstSet()  // non-const!
        {
            bits[nents-1]&=~exmask;   // Clear excess bits. 
            for(nents_t i=0; i<nents; i++)
                if(bits[i]!=all_clr)
                    return(SearchFirstSetBit(bits[i])+ssize_t(i*bits_per_ent));
            return(-1);
        }
        
        inline ssize_t SearchFirstClr()  // non-const!
        {
            bits[nents-1]|=exmask;   // Set excess bits. 
            for(nents_t i=0; i<nents; i++)
                if(bits[i]!=all_set)
                    return(SearchFirstClearedBit(bits[i])+
                        ssize_t(i*bits_per_ent));
            return(-1);
        }
};


template<typename T>class TLDynamicBitField
{
    friend int DoTestBitFields();
    public:
        typedef uint nents_t;
        
    private:
        static const T band = T(8*sizeof(T)-1);
        static const int bshift = 
            sizeof(T)==1 ? 3 : 
            sizeof(T)==2 ? 4 : 
            sizeof(T)==4 ? 5 : 
            sizeof(T)==8 ? 6 : 
            sizeof(T)==16 ? 7 : 8;
        static const size_t bits_per_ent=8*sizeof(T);
        
        static const T all_clr = T(0);
        static const T all_set = ~all_clr;
        
        size_t N;
        nents_t nents;
        T *bits;
        //--------
        // Ignore warning about left shift count >= width of type; this only 
        // happens for fast=1 which is caught in the other branch of the ?:. 
        T exmask;
        
        inline void _SetAllEnts(T val)
            {  for(nents_t i=0; i<nents; i++)  bits[i]=val;  }
        inline void _CopyFrom(const TLDynamicBitField<T> &b)
        {
            N=b.N;  nents=b.nents;  exmask=b.exmask;  bits=ALLOC<T>(nents);
            for(nents_t i=0; i<nents; i++)  bits[i]=b.bits[i];
        }
        static inline nents_t _NEntsOfN(size_t _N)
            {  return( (_N+8*sizeof(T)-1)/(8*sizeof(T)) );  }
        inline void _SetVals(size_t _N)
        {
            N=_N;  nents = _NEntsOfN(N);
            uint32 md = N % (8*sizeof(T));
            exmask = ( md==0 ) ? T(0) : ~((T(1)<<md)-1);
        }
        inline void _Initialize(size_t _N)
            {  _SetVals(_N);  bits=ALLOC<T>(nents);  }
        inline void _Free()
            {  bits=FREE(bits);  N=0;  nents=0;  }
        
    public:
        inline TLDynamicBitField(size_t _N)  {  _Initialize(_N);  }
        inline TLDynamicBitField(size_t _N,bool bitval)
            {  _Initialize(_N);  _SetAllEnts(bitval ? all_set : all_clr);  }
        inline TLDynamicBitField(const TLDynamicBitField<T> &b)
            {  _CopyFrom(b);  }
        inline ~TLDynamicBitField()
            {  _Free();  }
        
        inline TLDynamicBitField &operator=(const TLDynamicBitField<T> &b)
            {  _Free();  _CopyFrom(b);  return(*this);  }
        
        inline void resize(size_t newN)
        {
            if(_NEntsOfN(newN)!=nents)
            {  _SetVals(newN);  bits=REALLOC<T>(nents);  }
        }
        
        inline void resize(size_t newN,bool ini_val)
        {
            T val;   // The following does also set/clear excess bits. 
            if(ini_val) {  val=all_set;  bits[nents-1]|=exmask;  }
            else        {  val=all_clr;  bits[nents-1]&=~exmask;  }
            nents_t old_nents=nents;  resize(newN);
            for(; old_nents<nents; old_nents++)  bits[old_nents]=val;
        }
        
        inline void SetBit(size_t bit)
            {  bits[bit>>bshift]|=T(1)<<(bit & band);  }
        inline void ClrBit(size_t bit)
            {  bits[bit>>bshift]&=~(T(1)<<(bit & band));  }
        inline bool GetBit(size_t bit)
            {  return((bits[bit>>bshift]>>(bit & band))&T(1));  }
        inline void AssBit(size_t bit,bool val)
            {  if(val) SetBit(bit); else ClrBit(bit);  }
        
        inline void SetAll()
            {  _SetAllEnts(all_set);  }
        inline void ClrAll()
            {  _SetAllEnts(all_clr);  }
        
        inline size_t CountSet()  // non-const!
        {
            bits[nents-1]&=~exmask;   // Clear excess bits. 
            size_t sum=0;
            for(nents_t i=0; i<nents; i++)  sum+=CountBitsSet(bits[i]);
            return(sum);
        }
        
        inline size_t CountClr()  // non-const!
        {
            bits[nents-1]|=exmask;   // Set excess bits. 
            size_t sum=0;
            for(nents_t i=0; i<nents; i++)  sum+=CountBitsCleared(bits[i]);
            return(sum);
        }
        
        inline ssize_t SearchFirstSet()  // non-const!
        {
            bits[nents-1]&=~exmask;   // Clear excess bits. 
            for(nents_t i=0; i<nents; i++)
                if(bits[i]!=all_clr)
                    return(SearchFirstSetBit(bits[i])+ssize_t(i*bits_per_ent));
            return(-1);
        }
        
        inline ssize_t SearchFirstClr()  // non-const!
        {
            bits[nents-1]|=exmask;   // Set excess bits. 
            for(nents_t i=0; i<nents; i++)
                if(bits[i]!=all_set)
                    return(SearchFirstClearedBit(bits[i])+
                        ssize_t(i*bits_per_ent));
            return(-1);
        }
};


#endif  /* _TemplateLibrary_BitField_H_ */

---