specialize SkDataTable for arrays where all elements are the same size.

optimize impl to not require another level of indirection (SkData) for storage.
add unittests for flattening.
optimize builder to not make a deepcopy of its chunkalloc heap.



git-svn-id: http://skia.googlecode.com/svn/trunk@8790 2bbb7eff-a529-9590-31e7-b0007b416f81

3 files changed, 297 insertions, 87 deletions

diff --git a/include/core/SkDataTable.h b/include/core/SkDataTable.h
index 37bcee9242..cb74c3cb39 100644
--- a/include/core/SkDataTable.h
+++ b/include/core/SkDataTable.h
@@ -37,7 +37,7 @@ public:
      *  Return the size of the index'th entry in the table. The caller must
      *  ensure that index is valid for this table.
      */
-    size_t  atSize(int index) const;
+    size_t atSize(int index) const;
 
     /**
      *  Return a pointer to the data of the index'th entry in the table.
@@ -46,11 +46,11 @@ public:
      *  @param size If non-null, this returns the byte size of this entry. This
      *              will be the same value that atSize(index) would return.
      */
-    const void* atData(int index, size_t* size = NULL) const;
+    const void* at(int index, size_t* size = NULL) const;
 
     template <typename T>
-    const T* atDataT(int index, size_t* size = NULL) const {
-        return reinterpret_cast<const T*>(this->atData(index, size));
+    const T* atT(int index, size_t* size = NULL) const {
+        return reinterpret_cast<const T*>(this->at(index, size));
     }
 
     /**
@@ -59,11 +59,13 @@ public:
      */
     const char* atStr(int index) const {
         size_t size;
-        const char* str = this->atDataT<const char>(index, &size);
+        const char* str = this->atT<const char>(index, &size);
         SkASSERT(strlen(str) + 1 == size);
         return str;
     }
 
+    typedef void (*FreeProc)(void* context);
+
     static SkDataTable* NewEmpty();
 
     /**
@@ -75,8 +77,8 @@ public:
      *               ptrs[] array.
      *  @param count the number of array elements in ptrs[] and sizes[] to copy.
      */
-    static SkDataTable* NewCopyArrays(const void * const * ptrs, const size_t sizes[],
-                                      int count);
+    static SkDataTable* NewCopyArrays(const void * const * ptrs,
+                                      const size_t sizes[], int count);
 
     /**
      *  Return a new table that contains a copy of the data in array.
@@ -89,6 +91,9 @@ public:
     static SkDataTable* NewCopyArray(const void* array, size_t elemSize,
                                      int count);
 
+    static SkDataTable* NewArrayProc(const void* array, size_t elemSize,
+                                     int count, FreeProc proc, void* context);
+
     SK_DECLARE_PUBLIC_FLATTENABLE_DESERIALIZATION_PROCS(SkDataTable)
 
 protected:
@@ -96,11 +101,28 @@ protected:
     virtual void flatten(SkFlattenableWriteBuffer&) const SK_OVERRIDE;
 
 private:
-    SkDataTable(int count, SkData* dataWeTakeOverOwnership);
+    struct Dir {
+        const void* fPtr;
+        uintptr_t   fSize;
+    };
+
+    int         fCount;
+    size_t      fElemSize;
+    union {
+        const Dir*  fDir;
+        const char* fElems;
+    } fU;
+
+    FreeProc    fFreeProc;
+    void*       fFreeProcContext;
+
+    SkDataTable();
+    SkDataTable(const void* array, size_t elemSize, int count,
+                FreeProc, void* context);
+    SkDataTable(const Dir*, int count, FreeProc, void* context);
     virtual ~SkDataTable();
 
-    int     fCount;
-    SkData* fData;
+    friend class SkDataTableBuilder;    // access to Dir
 
     typedef SkFlattenable INHERITED;
 };
@@ -109,17 +131,21 @@ private:
  *  Helper class that allows for incrementally building up the data needed to
  *  create a SkDataTable.
  */
-class SK_API SkDataTableBuilder {
+class SK_API SkDataTableBuilder : SkNoncopyable {
 public:
     SkDataTableBuilder(size_t minChunkSize);
     ~SkDataTableBuilder();
 
-    int  count() const { return fSizes.count(); }
+    int  count() const { return fDir.count(); }
+    size_t minChunkSize() const { return fMinChunkSize; }
 
     /**
      *  Forget any previously appended entries, setting count() back to 0.
      */
-    void reset();
+    void reset(size_t minChunkSize);
+    void reset() {
+        this->reset(fMinChunkSize);
+    }
 
     /**
      *  Copy size-bytes from data, and append it to the growing SkDataTable.
@@ -144,15 +170,15 @@ public:
 
     /**
      *  Return an SkDataTable from the accumulated entries that were added by
-     *  calls to append(). This data is logically distinct from the builder, and
-     *  will not be affected by any subsequent calls to the builder.
+     *  calls to append(). This call also clears any accumluated entries from
+     *  this builder, so its count() will be 0 after this call.
      */
-    SkDataTable* createDataTable();
+    SkDataTable* detachDataTable();
 
 private:
-    SkTDArray<size_t> fSizes;
-    SkTDArray<void*>  fPtrs;
-    SkChunkAlloc      fHeap;
+    SkTDArray<SkDataTable::Dir> fDir;
+    SkChunkAlloc*               fHeap;
+    size_t                      fMinChunkSize;
 };
 
 #endif
diff --git a/src/core/SkDataTable.cpp b/src/core/SkDataTable.cpp
index 5c3bfefe2c..e5dbd8472b 100644
--- a/src/core/SkDataTable.cpp
+++ b/src/core/SkDataTable.cpp
@@ -11,46 +11,129 @@
 
 SK_DEFINE_INST_COUNT(SkDataTable)
 
-SkDataTable::SkDataTable(int count, SkData* data)
-    : fCount(count)
-    , fData(data) {}
+static void malloc_freeproc(void* context) {
+    sk_free(context);
+}
 
-SkDataTable::~SkDataTable() {
-    fData->unref();
+// Makes empty table
+SkDataTable::SkDataTable() {
+    fCount = 0;
+    fElemSize = 0;   // 0 signals that we use fDir instead of fElems
+    fU.fDir = NULL;
+    fFreeProc = NULL;
+    fFreeProcContext = NULL;
 }
 
-struct ElemHead {
-    const void* fPtr;
-    uintptr_t   fSize;
+SkDataTable::SkDataTable(const void* array, size_t elemSize, int count,
+                         FreeProc proc, void* context) {
+    SkASSERT(count > 0);
+    
+    fCount = count;
+    fElemSize = elemSize;   // non-zero signals we use fElems instead of fDir
+    fU.fElems = (const char*)array;
+    fFreeProc = proc;
+    fFreeProcContext = context;
+}
 
-    static const ElemHead* Get(SkData* data) {
-        return (const ElemHead*)(data->data());
+SkDataTable::SkDataTable(const Dir* dir, int count, FreeProc proc, void* ctx) {
+    SkASSERT(count > 0);
+    
+    fCount = count;
+    fElemSize = 0;  // 0 signals that we use fDir instead of fElems
+    fU.fDir = dir;
+    fFreeProc = proc;
+    fFreeProcContext = ctx;
+}
+
+SkDataTable::~SkDataTable() {
+    if (fFreeProc) {
+        fFreeProc(fFreeProcContext);
     }
-};
+}
 
 size_t SkDataTable::atSize(int index) const {
     SkASSERT((unsigned)index < (unsigned)fCount);
-    return ElemHead::Get(fData)[index].fSize;
+
+    if (fElemSize) {
+        return fElemSize;
+    } else {
+        return fU.fDir[index].fSize;
+    }
 }
 
-const void* SkDataTable::atData(int index, size_t* size) const {
+const void* SkDataTable::at(int index, size_t* size) const {
     SkASSERT((unsigned)index < (unsigned)fCount);
-    const ElemHead& head = ElemHead::Get(fData)[index];
-    if (size) {
-        *size = head.fSize;
+
+    if (fElemSize) {
+        if (size) {
+            *size = fElemSize;
+        }
+        return fU.fElems + index * fElemSize;
+    } else {
+        if (size) {
+            *size = fU.fDir[index].fSize;
+        }
+        return fU.fDir[index].fPtr;
     }
-    return head.fPtr;
 }
 
 SkDataTable::SkDataTable(SkFlattenableReadBuffer& buffer) : INHERITED(buffer) {
+    fElemSize = 0;
+    fU.fElems = NULL;
+    fFreeProc = NULL;
+    fFreeProcContext = NULL;
+
     fCount = buffer.read32();
-    fData = buffer.readFlattenableT<SkData>();
+    if (fCount) {
+        fElemSize = buffer.read32();
+        if (fElemSize) {
+            size_t size = buffer.getArrayCount();
+            // size is the size of our elems data
+            SkASSERT(fCount * fElemSize == size);
+            void* addr = sk_malloc_throw(size);
+            if (buffer.readByteArray(addr) != size) {
+                sk_throw();
+            }
+            fU.fElems = (const char*)addr;
+            fFreeProcContext = addr;
+        } else {
+            size_t dataSize = buffer.read32();
+
+            size_t allocSize = fCount * sizeof(Dir) + dataSize;
+            void* addr = sk_malloc_throw(allocSize);
+            Dir* dir = (Dir*)addr;
+            char* elem = (char*)(dir + fCount);
+            for (int i = 0; i < fCount; ++i) {
+                dir[i].fPtr = elem;
+                dir[i].fSize = buffer.readByteArray(elem);
+                elem += dir[i].fSize;
+            }
+            fU.fDir = dir;
+            fFreeProcContext = addr;
+        }
+        fFreeProc = malloc_freeproc;
+    }
 }
 
 void SkDataTable::flatten(SkFlattenableWriteBuffer& buffer) const {
     this->INHERITED::flatten(buffer);
+
     buffer.write32(fCount);
-    buffer.writeFlattenable(fData);
+    if (fCount) {
+        buffer.write32(fElemSize);
+        if (fElemSize) {
+            buffer.writeByteArray(fU.fElems, fCount * fElemSize);
+        } else {
+            size_t dataSize = 0;
+            for (int i = 0; i < fCount; ++i) {
+                dataSize += fU.fDir[i].fSize;
+            }
+            buffer.write32(dataSize);
+            for (int i = 0; i < fCount; ++i) {
+                buffer.writeByteArray(fU.fDir[i].fPtr, fU.fDir[i].fSize);
+            }
+        }
+    }
 }
 
 ///////////////////////////////////////////////////////////////////////////////
@@ -58,7 +141,7 @@ void SkDataTable::flatten(SkFlattenableWriteBuffer& buffer) const {
 SkDataTable* SkDataTable::NewEmpty() {
     static SkDataTable* gEmpty;
     if (NULL == gEmpty) {
-        gEmpty = SkNEW_ARGS(SkDataTable, (0, SkData::NewEmpty()));
+        gEmpty = SkNEW(SkDataTable);
     }
     gEmpty->ref();
     return gEmpty;
@@ -66,80 +149,103 @@ SkDataTable* SkDataTable::NewEmpty() {
 
 SkDataTable* SkDataTable::NewCopyArrays(const void * const * ptrs,
                                         const size_t sizes[], int count) {
-    if (count < 0) {
-        count = 0;
+    if (count <= 0) {
+        return SkDataTable::NewEmpty();
     }
 
-    size_t headerSize = count * sizeof(ElemHead);
     size_t dataSize = 0;
     for (int i = 0; i < count; ++i) {
         dataSize += sizes[i];
     }
 
-    size_t bufferSize = headerSize + dataSize;
+    size_t bufferSize = count * sizeof(Dir) + dataSize;
     void* buffer = sk_malloc_throw(bufferSize);
 
-    ElemHead* headerCurr = (ElemHead*)buffer;
-    char* dataCurr = (char*)buffer + headerSize;
+    Dir* dir = (Dir*)buffer;
+    char* elem = (char*)(dir + count);
     for (int i = 0; i < count; ++i) {
-        headerCurr[i].fPtr = dataCurr;
-        headerCurr[i].fSize = sizes[i];
-        memcpy(dataCurr, ptrs[i], sizes[i]);
-        dataCurr += sizes[i];
+        dir[i].fPtr = elem;
+        dir[i].fSize = sizes[i];
+        memcpy(elem, ptrs[i], sizes[i]);
+        elem += sizes[i];
     }
-
-    return SkNEW_ARGS(SkDataTable, (count,
-                                    SkData::NewFromMalloc(buffer, bufferSize)));
+    
+    return SkNEW_ARGS(SkDataTable, (dir, count, malloc_freeproc, buffer));
 }
 
 SkDataTable* SkDataTable::NewCopyArray(const void* array, size_t elemSize,
                                        int count) {
-    if (count < 0) {
-        count = 0;
+    if (count <= 0) {
+        return SkDataTable::NewEmpty();
     }
 
-    size_t headerSize = count * sizeof(ElemHead);
-    size_t dataSize = count * elemSize;
-
-    size_t bufferSize = headerSize + dataSize;
+    size_t bufferSize = elemSize * count;
     void* buffer = sk_malloc_throw(bufferSize);
+    memcpy(buffer, array, bufferSize);
 
-    ElemHead* headerCurr = (ElemHead*)buffer;
-    char* dataCurr = (char*)buffer + headerSize;
-    for (int i = 0; i < count; ++i) {
-        headerCurr[i].fPtr = dataCurr;
-        headerCurr[i].fSize = elemSize;
-        dataCurr += elemSize;
-    }
-    memcpy((char*)buffer + headerSize, array, dataSize);
+    return SkNEW_ARGS(SkDataTable,
+                      (buffer, elemSize, count, malloc_freeproc, buffer));
+}
 
-    return SkNEW_ARGS(SkDataTable, (count,
-                                    SkData::NewFromMalloc(buffer, bufferSize)));
+SkDataTable* SkDataTable::NewArrayProc(const void* array, size_t elemSize,
+                                       int count, FreeProc proc, void* ctx) {
+    if (count <= 0) {
+        return SkDataTable::NewEmpty();
+    }
+    return SkNEW_ARGS(SkDataTable, (array, elemSize, count, proc, ctx));
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
+static void chunkalloc_freeproc(void* context) {
+    SkDELETE((SkChunkAlloc*)context);
+}
+
 SkDataTableBuilder::SkDataTableBuilder(size_t minChunkSize)
-    : fHeap(minChunkSize) {}
+    : fHeap(NULL)
+    , fMinChunkSize(minChunkSize) {}
 
-SkDataTableBuilder::~SkDataTableBuilder() {}
+SkDataTableBuilder::~SkDataTableBuilder() { this->reset(); }
 
-void SkDataTableBuilder::reset() {
-    fSizes.reset();
-    fPtrs.reset();
-    fHeap.reset();
+void SkDataTableBuilder::reset(size_t minChunkSize) {
+    fMinChunkSize = minChunkSize;
+    fDir.reset();
+    if (fHeap) {
+        SkDELETE(fHeap);
+        fHeap = NULL;
+    }
 }
 
 void SkDataTableBuilder::append(const void* src, size_t size) {
-    void* dst = fHeap.alloc(size, SkChunkAlloc::kThrow_AllocFailType);
+    if (NULL == fHeap) {
+        fHeap = SkNEW_ARGS(SkChunkAlloc, (fMinChunkSize));
+    }
+
+    void* dst = fHeap->alloc(size, SkChunkAlloc::kThrow_AllocFailType);
     memcpy(dst, src, size);
 
-    *fSizes.append() = size;
-    *fPtrs.append() = dst;
+    SkDataTable::Dir* dir = fDir.append();
+    dir->fPtr = dst;
+    dir->fSize = size;
 }
 
-SkDataTable* SkDataTableBuilder::createDataTable() {
-    SkASSERT(fSizes.count() == fPtrs.count());
-    return SkDataTable::NewCopyArrays(fPtrs.begin(), fSizes.begin(),
-                                      fSizes.count());
+SkDataTable* SkDataTableBuilder::detachDataTable() {
+    const int count = fDir.count();
+    if (0 == count) {
+        return SkDataTable::NewEmpty();
+    }
+
+    // Copy the dir into the heap;
+    void* dir = fHeap->alloc(count * sizeof(SkDataTable::Dir),
+                             SkChunkAlloc::kThrow_AllocFailType);
+    memcpy(dir, fDir.begin(), count * sizeof(SkDataTable::Dir));
+
+    SkDataTable* table = SkNEW_ARGS(SkDataTable,
+                                    ((SkDataTable::Dir*)dir, count,
+                                     chunkalloc_freeproc, fHeap));
+    // we have to detach our fHeap, since we are giving that to the table
+    fHeap = NULL;
+    fDir.reset();
+    return table;
 }
+
diff --git a/tests/DataRefTest.cpp b/tests/DataRefTest.cpp
index 26c263aa13..dbe02e88d4 100644
--- a/tests/DataRefTest.cpp
+++ b/tests/DataRefTest.cpp
@@ -10,6 +10,8 @@
 #include "SkDataSet.h"
 #include "SkDataTable.h"
 #include "SkStream.h"
+#include "SkOrderedReadBuffer.h"
+#include "SkOrderedWriteBuffer.h"
 
 template <typename T> class SkTUnref {
 public:
@@ -23,6 +25,58 @@ private:
     T*  fRef;
 };
 
+static void test_is_equal(skiatest::Reporter* reporter,
+                          const SkDataTable* a, const SkDataTable* b) {
+    REPORTER_ASSERT(reporter, a->count() == b->count());
+    for (int i = 0; i < a->count(); ++i) {
+        size_t sizea, sizeb;
+        const void* mema = a->at(i, &sizea);
+        const void* memb = b->at(i, &sizeb);
+        REPORTER_ASSERT(reporter, sizea == sizeb);
+        REPORTER_ASSERT(reporter, !memcmp(mema, memb, sizea));
+    }
+}
+
+static void test_datatable_flatten(skiatest::Reporter* reporter,
+                                   SkDataTable* table) {
+    SkOrderedWriteBuffer wb(1024);
+    wb.writeFlattenable(table);
+
+    size_t wsize = wb.size();
+    SkAutoMalloc storage(wsize);
+    wb.writeToMemory(storage.get());
+
+    SkOrderedReadBuffer rb(storage.get(), wsize);
+    SkAutoTUnref<SkDataTable> newTable((SkDataTable*)rb.readFlattenable());
+
+    SkDebugf("%d entries, %d flatten-size\n", table->count(), wsize);
+    test_is_equal(reporter, table, newTable);
+}
+
+static void test_datatable_is_empty(skiatest::Reporter* reporter,
+                                    SkDataTable* table) {
+    REPORTER_ASSERT(reporter, table->isEmpty());
+    REPORTER_ASSERT(reporter, 0 == table->count());
+    test_datatable_flatten(reporter, table);
+}
+
+static void test_emptytable(skiatest::Reporter* reporter) {
+    SkAutoTUnref<SkDataTable> table0(SkDataTable::NewEmpty());
+    SkAutoTUnref<SkDataTable> table1(SkDataTable::NewCopyArrays(NULL, NULL, 0));
+    SkAutoTUnref<SkDataTable> table2(SkDataTable::NewCopyArray(NULL, NULL, 0));
+    SkAutoTUnref<SkDataTable> table3(SkDataTable::NewArrayProc(NULL, NULL, 0,
+                                                               NULL, NULL));
+
+    test_datatable_is_empty(reporter, table0);
+    test_datatable_is_empty(reporter, table1);
+    test_datatable_is_empty(reporter, table2);
+    test_datatable_is_empty(reporter, table3);
+
+    test_is_equal(reporter, table0, table1);
+    test_is_equal(reporter, table0, table2);
+    test_is_equal(reporter, table0, table3);
+}
+
 static void test_simpletable(skiatest::Reporter* reporter) {
     const int idata[] = { 1, 4, 9, 16, 25, 63 };
     int icount = SK_ARRAY_COUNT(idata);
@@ -33,9 +87,10 @@ static void test_simpletable(skiatest::Reporter* reporter) {
     for (int i = 0; i < icount; ++i) {
         size_t size;
         REPORTER_ASSERT(reporter, sizeof(int) == itable->atSize(i));
-        REPORTER_ASSERT(reporter, *itable->atDataT<int>(i, &size) == idata[i]);
+        REPORTER_ASSERT(reporter, *itable->atT<int>(i, &size) == idata[i]);
         REPORTER_ASSERT(reporter, sizeof(int) == size);
     }
+    test_datatable_flatten(reporter, itable);
 }
 
 static void test_vartable(skiatest::Reporter* reporter) {
@@ -55,13 +110,14 @@ static void test_vartable(skiatest::Reporter* reporter) {
     for (int i = 0; i < count; ++i) {
         size_t size;
         REPORTER_ASSERT(reporter, table->atSize(i) == sizes[i]);
-        REPORTER_ASSERT(reporter, !strcmp(table->atDataT<const char>(i, &size),
+        REPORTER_ASSERT(reporter, !strcmp(table->atT<const char>(i, &size),
                                           str[i]));
         REPORTER_ASSERT(reporter, size == sizes[i]);
 
         const char* s = table->atStr(i);
         REPORTER_ASSERT(reporter, strlen(s) == strlen(str[i]));
     }
+    test_datatable_flatten(reporter, table);
 }
 
 static void test_tablebuilder(skiatest::Reporter* reporter) {
@@ -75,25 +131,47 @@ static void test_tablebuilder(skiatest::Reporter* reporter) {
     for (int i = 0; i < count; ++i) {
         builder.append(str[i], strlen(str[i]) + 1);
     }
-    SkAutoTUnref<SkDataTable> table(builder.createDataTable());
+    SkAutoTUnref<SkDataTable> table(builder.detachDataTable());
 
     REPORTER_ASSERT(reporter, table->count() == count);
     for (int i = 0; i < count; ++i) {
         size_t size;
         REPORTER_ASSERT(reporter, table->atSize(i) == strlen(str[i]) + 1);
-        REPORTER_ASSERT(reporter, !strcmp(table->atDataT<const char>(i, &size),
+        REPORTER_ASSERT(reporter, !strcmp(table->atT<const char>(i, &size),
                                           str[i]));
         REPORTER_ASSERT(reporter, size == strlen(str[i]) + 1);
 
         const char* s = table->atStr(i);
         REPORTER_ASSERT(reporter, strlen(s) == strlen(str[i]));
     }
+    test_datatable_flatten(reporter, table);
+}
+
+static void test_globaltable(skiatest::Reporter* reporter) {
+    static const int gData[] = {
+        0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
+    };
+    int count = SK_ARRAY_COUNT(gData);
+
+    SkAutoTUnref<SkDataTable> table(SkDataTable::NewArrayProc(gData,
+                                          sizeof(gData[0]), count, NULL, NULL));
+    
+    REPORTER_ASSERT(reporter, table->count() == count);
+    for (int i = 0; i < count; ++i) {
+        size_t size;
+        REPORTER_ASSERT(reporter, table->atSize(i) == sizeof(int));
+        REPORTER_ASSERT(reporter, *table->atT<const char>(i, &size) == i);
+        REPORTER_ASSERT(reporter, sizeof(int) == size);
+    }
+    test_datatable_flatten(reporter, table);
 }
 
-static void test_datatable(skiatest::Reporter* reporter) {
+static void TestDataTable(skiatest::Reporter* reporter) {
+    test_emptytable(reporter);
     test_simpletable(reporter);
     test_vartable(reporter);
     test_tablebuilder(reporter);
+    test_globaltable(reporter);
 }
 
 static void unrefAll(const SkDataSet::Pair pairs[], int count) {
@@ -220,8 +298,8 @@ static void TestData(skiatest::Reporter* reporter) {
 
     test_cstring(reporter);
     test_dataset(reporter);
-    test_datatable(reporter);
 }
 
 #include "TestClassDef.h"
 DEFINE_TESTCLASS("Data", DataTestClass, TestData)
+DEFINE_TESTCLASS("DataTable", DataTableTestClass, TestDataTable)