Changeset 3112


Ignore:
Timestamp:
May 6, 2013, 7:49:25 AM (6 years ago)
Author:
cameron
Message:

Iterator for content buffers with 16-bit left deletion results

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/lib/bitblock_iterator.hpp

    r2594 r3112  
    140140};
    141141
     142
    142143template <class bitblock_t, class scanblock_t>
    143144class ReverseScanner: public Scanner<bitblock_t, scanblock_t> {
     
    192193};
    193194
    194 #undef has_bit
    195195
    196196//
     
    217217        bool operator==(const ForwardIterator& iter)
    218218        {
    219                 return ((scanner.get_strm() = iter.scanner.get_strm()) && (scanner.get_pos() == iter.scanner.get_pos));
    220         }
    221 
    222         // not equal .get_pos()ition and stream
     219                return ((scanner.get_strm() == iter.scanner.get_strm()) &&
     220                        (scanner.get_pos() == iter.scanner.get_pos()));
     221        }
     222
     223        // not equal position and stream
    223224        bool operator!=(const ForwardIterator& iter)
    224225        {
    225                 return ( (scanner.get_strm() != iter.scanner.get_strm()) && (scanner.get_pos() != iter.scanner.get_pos()));
     226                return ((scanner.get_strm() != iter.scanner.get_strm()) &&
     227                        (scanner.get_pos() != iter.scanner.get_pos()));
    226228        }
    227229
     
    257259};
    258260
     261
    259262template<class bitblock_t, class scanblock_t>
    260263class ReverseIterator
     
    279282        }
    280283
    281         // not equal .get_pos()ition and stream
     284        // not equal position and stream
    282285        bool operator!=(const ReverseIterator& iter)
    283286        {
     
    424427};
    425428
     429/*=============================================================================
     430 
     431   Special iterators for content buffers with 16-bit right deletion results.
     432   Input: (a) a bitblock with undeleted positions rightmost in each 16-bit field.
     433          (b) a bitblock of 16-bit fields with a partial sum of the nondeleted
     434              positions in this field and all the ones to the right.
     435         
     436          The partial sum may be computed given B, a bitblock containg the count
     437          of nondeleted positions in each field using PartialSum16(B).
     438       
     439   
     440*/
     441
     442
     443static inline BitBlock PartialSum16(BitBlock BaseCounts16) {
     444        BitBlock t = simd<16>::add(BaseCounts16, mvmd<16>::slli<1>(BaseCounts16));
     445        BitBlock u = simd<16>::add(t, mvmd<16>::slli<2>(t));
     446        return simd<16>::add(u, mvmd<16>::slli<4>(u));
     447}
     448
     449template <class bitblock_t, class scanblock_t>
     450class ForwardScannerWithBaseCounts16: public Scanner<bitblock_t, scanblock_t> {
     451
     452public:
     453
     454        ForwardScannerWithBaseCounts16(){}
     455        ForwardScannerWithBaseCounts16(const bitblock_t * s, bitblock_t partial_sums_16) {
     456                init(s, partial_sums_16);
     457        }
     458
     459        IDISA_ALWAYS_INLINE void init(const bitblock_t * s, bitblock_t partial_sums_16) {
     460                this->strm = s;
     461                this->pos = 0;
     462                this->blk = 0;
     463                this->scan_blk = *(scanblock_t *)s;
     464                /* Shift by one field so that the base is the sum for the prev. fields. */
     465                this->base_per_field16._128 = mvmd<16>::slli<1>(partial_sums_16);
     466        }
     467
     468        IDISA_ALWAYS_INLINE int32_t scan_to_next() {
     469                while (this->blk < BLOCK_COUNT){
     470                        if(has_bit(this->scan_blk)){
     471                                int pos = scan_forward_zeroes(this->scan_blk) + (this->blk * (sizeof(scanblock_t)*8));
     472                                this->scan_blk = this->scan_blk & (this->scan_blk-1);  // clear rightmost bit
     473               
     474                                this->pos = this->base_per_field16._16[pos/16] + (pos & 15);
     475
     476                                return (this->pos);
     477                        }
     478
     479                        this->blk++;
     480                        this->scan_blk = *((scanblock_t *)this->strm + this->blk);
     481                };
     482
     483                this->pos = -1;
     484                return (this->pos);
     485        }
     486
     487
     488        IDISA_ALWAYS_INLINE bool is_done() {return (-1==this->pos);}
     489        IDISA_ALWAYS_INLINE void set_strm(const bitblock_t * strm) {this->strm = strm;}
     490        IDISA_ALWAYS_INLINE const bitblock_t * get_strm() const {return this->strm;}
     491        IDISA_ALWAYS_INLINE int32_t get_pos() const {return this->pos;}
     492
     493        static const int32_t BLOCK_COUNT = sizeof(bitblock_t)/sizeof(scanblock_t);
     494        ubitblock base_per_field16;
     495};
     496
     497template <class bitblock_t> static inline bool eq_bitblocks(bitblock_t x, bitblock_t y) {
     498  return bitblock::all(simd<16>::eq(x, y));
     499}
     500
     501
     502template<class bitblock_t, class scanblock_t>
     503class ForwardIteratorWithBaseCounts16 : public std::iterator<std::input_iterator_tag, int>
     504{
     505public:
     506        ForwardIteratorWithBaseCounts16() {}
     507
     508        ForwardIteratorWithBaseCounts16(bitblock_t * s, bitblock_t partial_sums_16): scanner(s, partial_sums_16)
     509        {
     510                scanner.scan_to_next();
     511        }
     512
     513        void init(bitblock_t * s, bitblock_t partial_sums_16)
     514        {
     515                scanner.init(s, partial_sums_16);
     516                scanner.scan_to_next();
     517        }
     518
     519        // equal position and stream
     520        bool operator==(const ForwardIteratorWithBaseCounts16& iter)
     521        {
     522                return (scanner.get_strm() = iter.scanner.get_strm()) &&
     523                       (scanner.get_pos() == iter.scanner.get_pos) &&
     524                       (eq_bitblocks<bitblock_t>(scanner.base_per_field16, iter.scanner.base_per_field16));
     525        }
     526
     527        // not equal position and stream
     528        bool operator!=(const ForwardIteratorWithBaseCounts16& iter)
     529        {
     530                return (scanner.get_strm() != iter.scanner.get_strm()) ||
     531                       (scanner.get_pos() != iter.scanner.get_pos) ||
     532                       (!eq_bitblocks<bitblock_t>(scanner.base_per_field16, iter.scanner.base_per_field16));
     533        }
     534
     535        // Returns absolute position.
     536        IDISA_ALWAYS_INLINE int32_t operator*()
     537        {
     538                return scanner.get_pos();
     539        }
     540
     541        // prefix increment
     542        IDISA_ALWAYS_INLINE ForwardIteratorWithBaseCounts16& operator++()
     543        {
     544                scanner.scan_to_next();
     545                return(*this);
     546        }
     547
     548        // postfix increment
     549        ForwardIteratorWithBaseCounts16 operator++(int)
     550        {
     551                ForwardIteratorWithBaseCounts16 temp(*this);
     552                ++(*this);
     553                return(temp);
     554        }
     555
     556private:
     557        ForwardScannerWithBaseCounts16<bitblock_t, scanblock_t> scanner;
     558};
     559
     560
     561class BitBlockForwardIteratorWithBaseCounts16: public ForwardIteratorWithBaseCounts16<BitBlock, ScanWord> {
     562public:
     563        BitBlockForwardIteratorWithBaseCounts16(){}
     564        BitBlockForwardIteratorWithBaseCounts16(BitBlock * s, BitBlock partial_sums_16): ForwardIteratorWithBaseCounts16<BitBlock, ScanWord>(s, partial_sums_16){}
     565};
     566
     567
     568#undef has_bit
     569
     570
    426571#endif // BITBLOCK_ITERATOR_H_
    427572
Note: See TracChangeset for help on using the changeset viewer.