src/third_party/skia/src/core/SkOffsetTable.h

   1 /*
   2  * Copyright 2014 Google Inc.
   3  *
   4  * Use of this source code is governed by a BSD-style license that can be
   5  * found in the LICENSE file.
   6  */
   7
   8 #ifndef SkOffsetTable_DEFINED
   9 #define SkOffsetTable_DEFINED
  10
  11 #include "SkRefCnt.h"
  12 #include "SkTDArray.h"
  13
  14 // A 2D table of skp offsets. Each row is indexed by an int. This is used
  15 // to store the command offsets that reference a particular bitmap using
  16 // the bitmap's index in the bitmap heap as the 'id' here. It has to be
  17 // ref-countable so SkPicturePlayback can take ownership of it.
  18 // Note that this class assumes that the ids are densely packed.
  19
  20 // TODO: This needs to be sped up. We could replace the offset table with
  21 // a hash table.
  22 class SkOffsetTable : public SkRefCnt {
  23 public:
  24     SkOffsetTable() {}
  25     ~SkOffsetTable() {
  26         fOffsetArrays.deleteAll();
  27     }
  28
  29     // Record that this 'id' is used by the command starting at this 'offset'.
  30     // Offsets for a given 'id' should always be added in increasing order.
  31     void add(int id, size_t offset) {
  32         if (id >= fOffsetArrays.count()) {
  33             int oldCount = fOffsetArrays.count();
  34             fOffsetArrays.setCount(id+1);
  35             for (int i = oldCount; i <= id; ++i) {
  36                 fOffsetArrays[i] = NULL;
  37             }
  38         }
  39
  40         if (NULL == fOffsetArrays[id]) {
  41             fOffsetArrays[id] = SkNEW(OffsetArray);
  42         }
  43         fOffsetArrays[id]->add(offset);
  44     }
  45
  46     int numIDs() const {
  47         return fOffsetArrays.count();
  48     }
  49
  50     // Do the offsets of any commands referencing this ID fall in the
  51     // range [min, max] (both inclusive)
  52     bool overlap(int id, size_t min, size_t max) {
  53         SkASSERT(id < fOffsetArrays.count());
  54
  55         if (NULL == fOffsetArrays[id]) {
  56             return false;
  57         }
  58
  59         // If this id has an offset array it should have at least one use
  60         SkASSERT(fOffsetArrays[id]->count() > 0);
  61         if (max < fOffsetArrays[id]->min() || min > fOffsetArrays[id]->max()) {
  62             return false;
  63         }
  64
  65         return true;
  66     }
  67
  68     bool includes(int id, size_t offset) {
  69         SkASSERT(id < fOffsetArrays.count());
  70
  71         OffsetArray* array = fOffsetArrays[id];
  72
  73         for (int i = 0; i < array->fOffsets.count(); ++i) {
  74             if (array->fOffsets[i] == offset) {
  75                 return true;
  76             } else if (array->fOffsets[i] > offset) {
  77                 return false;
  78             }
  79         }
  80
  81         // Calls to 'includes' should be gaurded by an overlap() call, so we
  82         // should always find something.
  83         SkASSERT(0);
  84         return false;
  85     }
  86
  87 protected:
  88     class OffsetArray {
  89     public:
  90         void add(size_t offset) {
  91             SkASSERT(fOffsets.count() == 0 || offset > this->max());
  92             *fOffsets.append() = offset;
  93         }
  94         size_t min() const {
  95             SkASSERT(fOffsets.count() > 0);
  96             return fOffsets[0];
  97         }
  98         size_t max() const {
  99             SkASSERT(fOffsets.count() > 0);
 100             return fOffsets[fOffsets.count()-1];
 101         }
 102         int count() const {
 103             return fOffsets.count();
 104         }
 105
 106         SkTDArray<size_t> fOffsets;
 107     };
 108
 109     SkTDArray<OffsetArray*> fOffsetArrays;
 110
 111 private:
 112     typedef SkRefCnt INHERITED;
 113 };
 114
 115 #endif