michael@0: /*
michael@0:  * Copyright 2014 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #ifndef SkOffsetTable_DEFINED
michael@0: #define SkOffsetTable_DEFINED
michael@0: 
michael@0: #include "SkRefCnt.h"
michael@0: #include "SkTDArray.h"
michael@0: 
michael@0: // A 2D table of skp offsets. Each row is indexed by an int. This is used
michael@0: // to store the command offsets that reference a particular bitmap using
michael@0: // the bitmap's index in the bitmap heap as the 'id' here. It has to be
michael@0: // ref-countable so SkPicturePlayback can take ownership of it.
michael@0: // Note that this class assumes that the ids are densely packed.
michael@0: 
michael@0: // TODO: This needs to be sped up. We could replace the offset table with
michael@0: // a hash table.
michael@0: class SkOffsetTable : public SkRefCnt {
michael@0: public:
michael@0:     SkOffsetTable() {}
michael@0:     ~SkOffsetTable() {
michael@0:         fOffsetArrays.deleteAll();
michael@0:     }
michael@0: 
michael@0:     // Record that this 'id' is used by the command starting at this 'offset'.
michael@0:     // Offsets for a given 'id' should always be added in increasing order.
michael@0:     void add(int id, size_t offset) {
michael@0:         if (id >= fOffsetArrays.count()) {
michael@0:             int oldCount = fOffsetArrays.count();
michael@0:             fOffsetArrays.setCount(id+1);
michael@0:             for (int i = oldCount; i <= id; ++i) {
michael@0:                 fOffsetArrays[i] = NULL;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         if (NULL == fOffsetArrays[id]) {
michael@0:             fOffsetArrays[id] = SkNEW(OffsetArray);
michael@0:         }
michael@0:         fOffsetArrays[id]->add(offset);
michael@0:     }
michael@0: 
michael@0:     int numIDs() const {
michael@0:         return fOffsetArrays.count();
michael@0:     }
michael@0: 
michael@0:     // Do the offsets of any commands referencing this ID fall in the
michael@0:     // range [min, max] (both inclusive)
michael@0:     bool overlap(int id, size_t min, size_t max) {
michael@0:         SkASSERT(id < fOffsetArrays.count());
michael@0: 
michael@0:         if (NULL == fOffsetArrays[id]) {
michael@0:             return false;
michael@0:         }
michael@0: 
michael@0:         // If this id has an offset array it should have at least one use
michael@0:         SkASSERT(fOffsetArrays[id]->count() > 0);
michael@0:         if (max < fOffsetArrays[id]->min() || min > fOffsetArrays[id]->max()) {
michael@0:             return false;
michael@0:         }
michael@0: 
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:     bool includes(int id, size_t offset) {
michael@0:         SkASSERT(id < fOffsetArrays.count());
michael@0: 
michael@0:         OffsetArray* array = fOffsetArrays[id];
michael@0: 
michael@0:         for (int i = 0; i < array->fOffsets.count(); ++i) {
michael@0:             if (array->fOffsets[i] == offset) {
michael@0:                 return true;
michael@0:             } else if (array->fOffsets[i] > offset) {
michael@0:                 return false;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // Calls to 'includes' should be gaurded by an overlap() call, so we
michael@0:         // should always find something.
michael@0:         SkASSERT(0);
michael@0:         return false;
michael@0:     }
michael@0: 
michael@0: protected:
michael@0:     class OffsetArray {
michael@0:     public:
michael@0:         void add(size_t offset) {
michael@0:             SkASSERT(fOffsets.count() == 0 || offset > this->max());
michael@0:             *fOffsets.append() = offset;
michael@0:         }
michael@0:         size_t min() const {
michael@0:             SkASSERT(fOffsets.count() > 0);
michael@0:             return fOffsets[0];
michael@0:         }
michael@0:         size_t max() const {
michael@0:             SkASSERT(fOffsets.count() > 0);
michael@0:             return fOffsets[fOffsets.count()-1];
michael@0:         }
michael@0:         int count() const {
michael@0:             return fOffsets.count();
michael@0:         }
michael@0: 
michael@0:         SkTDArray<size_t> fOffsets;
michael@0:     };
michael@0: 
michael@0:     SkTDArray<OffsetArray*> fOffsetArrays;
michael@0: 
michael@0: private:
michael@0:     typedef SkRefCnt INHERITED;
michael@0: };
michael@0: 
michael@0: #endif