add SkDataTable, to efficiently store an immutable array. Includes a builder
helper class.
Review URL: https://codereview.chromium.org/14188049
git-svn-id: http://skia.googlecode.com/svn/trunk@8779 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/gyp/core.gypi b/gyp/core.gypi
index ac66eed..c694091 100644
--- a/gyp/core.gypi
+++ b/gyp/core.gypi
@@ -65,6 +65,7 @@
'<(skia_src_path)/core/SkCubicClipper.cpp',
'<(skia_src_path)/core/SkCubicClipper.h',
'<(skia_src_path)/core/SkData.cpp',
+ '<(skia_src_path)/core/SkDataTable.cpp',
'<(skia_src_path)/core/SkDebug.cpp',
'<(skia_src_path)/core/SkDeque.cpp',
'<(skia_src_path)/core/SkDevice.cpp',
diff --git a/include/core/SkDataTable.h b/include/core/SkDataTable.h
new file mode 100644
index 0000000..4a273ea
--- /dev/null
+++ b/include/core/SkDataTable.h
@@ -0,0 +1,156 @@
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkDataTable_DEFINED
+#define SkDataTable_DEFINED
+
+#include "SkChunkAlloc.h"
+#include "SkData.h"
+#include "SkFlattenable.h"
+#include "SkString.h"
+#include "SkTDArray.h"
+
+/**
+ * Like SkData, SkDataTable holds an immutable data buffer. The data buffer is
+ * organized into a table of entries, each with a length, so the entries are
+ * not required to all be the same size.
+ */
+class SK_API SkDataTable : public SkFlattenable {
+public:
+ SK_DECLARE_INST_COUNT(SkDataTable)
+
+ /**
+ * Returns true if the table is empty (i.e. has no entries).
+ */
+ bool isEmpty() const { return 0 == fCount; }
+
+ /**
+ * Return the number of entries in the table. 0 for an empty table
+ */
+ int count() const { return fCount; }
+
+ /**
+ * 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;
+
+ /**
+ * Return a pointer to the data of the index'th entry in the table.
+ * The caller must ensure that index is valid for this table.
+ *
+ * @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;
+
+ template <typename T>
+ const T* atDataT(int index, size_t* size = NULL) const {
+ return reinterpret_cast<const T*>(this->atData(index, size));
+ }
+
+ /**
+ * Returns the index'th entry as a c-string, and assumes that the trailing
+ * null byte had been copied into the table as well.
+ */
+ const char* atStr(int index) const {
+ size_t size;
+ const char* str = this->atDataT<const char>(index, &size);
+ SkASSERT(strlen(str) + 1 == size);
+ return str;
+ }
+
+ /**
+ * Return a new DataTable that contains a copy of the data stored in each
+ * "array".
+ *
+ * @param ptrs array of points to each element to be copied into the table.
+ * @param sizes array of byte-lengths for each entry in the corresponding
+ * 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);
+
+ /**
+ * Return a new table that contains a copy of the data in array.
+ *
+ * @param array contiguous array of data for all elements to be copied.
+ * @param elemSize byte-length for a given element.
+ * @param count the number of entries to be copied out of array. The number
+ * of bytes that will be copied is count * elemSize.
+ */
+ static SkDataTable* NewCopyArray(const void* array, size_t elemSize,
+ int count);
+
+ SK_DECLARE_PUBLIC_FLATTENABLE_DESERIALIZATION_PROCS(SkDataTable)
+
+protected:
+ SkDataTable(SkFlattenableReadBuffer&);
+ virtual void flatten(SkFlattenableWriteBuffer&) const SK_OVERRIDE;
+
+private:
+ SkDataTable(int count, SkData* dataWeTakeOverOwnership);
+ virtual ~SkDataTable();
+
+ int fCount;
+ SkData* fData;
+
+ typedef SkFlattenable INHERITED;
+};
+
+/**
+ * Helper class that allows for incrementally building up the data needed to
+ * create a SkDataTable.
+ */
+class SK_API SkDataTableBuilder {
+public:
+ SkDataTableBuilder(size_t minChunkSize);
+ ~SkDataTableBuilder();
+
+ int count() const { return fSizes.count(); }
+
+ /**
+ * Forget any previously appended entries, setting count() back to 0.
+ */
+ void reset();
+
+ /**
+ * Copy size-bytes from data, and append it to the growing SkDataTable.
+ */
+ void append(const void* data, size_t size);
+
+ /**
+ * Helper version of append() passes strlen() + 1 for the size,
+ * so the trailing-zero will be copied as well.
+ */
+ void appendStr(const char str[]) {
+ this->append(str, strlen(str) + 1);
+ }
+
+ /**
+ * Helper version of append() passes string.size() + 1 for the size,
+ * so the trailing-zero will be copied as well.
+ */
+ void appendString(const SkString& string) {
+ this->append(string.c_str(), string.size() + 1);
+ }
+
+ /**
+ * 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.
+ */
+ SkDataTable* createDataTable();
+
+private:
+ SkTDArray<size_t> fSizes;
+ SkTDArray<void*> fPtrs;
+ SkChunkAlloc fHeap;
+};
+
+#endif
diff --git a/src/core/SkDataTable.cpp b/src/core/SkDataTable.cpp
new file mode 100644
index 0000000..fa7ff71
--- /dev/null
+++ b/src/core/SkDataTable.cpp
@@ -0,0 +1,135 @@
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkData.h"
+#include "SkDataTable.h"
+#include "SkFlattenableBuffers.h"
+
+SK_DEFINE_INST_COUNT(SkDataTable)
+
+SkDataTable::SkDataTable(int count, SkData* data)
+ : fCount(count)
+ , fData(data) {}
+
+SkDataTable::~SkDataTable() {
+ fData->unref();
+}
+
+struct ElemHead {
+ const void* fPtr;
+ uintptr_t fSize;
+
+ static const ElemHead* Get(SkData* data) {
+ return (const ElemHead*)(data->data());
+ }
+};
+
+size_t SkDataTable::atSize(int index) const {
+ SkASSERT((unsigned)index < (unsigned)fCount);
+ return ElemHead::Get(fData)[index].fSize;
+}
+
+const void* SkDataTable::atData(int index, size_t* size) const {
+ SkASSERT((unsigned)index < (unsigned)fCount);
+ const ElemHead& head = ElemHead::Get(fData)[index];
+ if (size) {
+ *size = head.fSize;
+ }
+ return head.fPtr;
+}
+
+SkDataTable::SkDataTable(SkFlattenableReadBuffer& buffer) : INHERITED(buffer) {
+ fCount = buffer.read32();
+ fData = buffer.readFlattenableT<SkData>();
+}
+
+void SkDataTable::flatten(SkFlattenableWriteBuffer& buffer) const {
+ this->INHERITED::flatten(buffer);
+ buffer.write32(fCount);
+ buffer.writeFlattenable(fData);
+}
+
+SkDataTable* SkDataTable::NewCopyArrays(const void * const * ptrs,
+ const size_t sizes[], int count) {
+ if (count < 0) {
+ count = 0;
+ }
+
+ 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;
+ void* buffer = sk_malloc_throw(bufferSize);
+
+ ElemHead* headerCurr = (ElemHead*)buffer;
+ char* dataCurr = (char*)buffer + headerSize;
+ 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];
+ }
+
+ return SkNEW_ARGS(SkDataTable, (count,
+ SkData::NewFromMalloc(buffer, bufferSize)));
+}
+
+SkDataTable* SkDataTable::NewCopyArray(const void* array, size_t elemSize,
+ int count) {
+ if (count < 0) {
+ count = 0;
+ }
+
+ size_t headerSize = count * sizeof(ElemHead);
+ size_t dataSize = count * elemSize;
+
+ size_t bufferSize = headerSize + dataSize;
+ void* buffer = sk_malloc_throw(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, (count,
+ SkData::NewFromMalloc(buffer, bufferSize)));
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+SkDataTableBuilder::SkDataTableBuilder(size_t minChunkSize)
+ : fHeap(minChunkSize) {}
+
+SkDataTableBuilder::~SkDataTableBuilder() {}
+
+void SkDataTableBuilder::reset() {
+ fSizes.reset();
+ fPtrs.reset();
+ fHeap.reset();
+}
+
+void SkDataTableBuilder::append(const void* src, size_t size) {
+ void* dst = fHeap.alloc(size, SkChunkAlloc::kThrow_AllocFailType);
+ memcpy(dst, src, size);
+
+ *fSizes.append() = size;
+ *fPtrs.append() = dst;
+}
+
+SkDataTable* SkDataTableBuilder::createDataTable() {
+ SkASSERT(fSizes.count() == fPtrs.count());
+ return SkDataTable::NewCopyArrays(fPtrs.begin(), fSizes.begin(),
+ fSizes.count());
+}
+
diff --git a/tests/DataRefTest.cpp b/tests/DataRefTest.cpp
index 8c002c8..449149a 100644
--- a/tests/DataRefTest.cpp
+++ b/tests/DataRefTest.cpp
@@ -8,6 +8,7 @@
#include "Test.h"
#include "SkData.h"
#include "SkDataSet.h"
+#include "SkDataTable.h"
#include "SkStream.h"
template <typename T> class SkTUnref {
@@ -22,6 +23,79 @@
T* fRef;
};
+static void test_simpletable(skiatest::Reporter* reporter) {
+ const int idata[] = { 1, 4, 9, 16, 25, 63 };
+ int icount = SK_ARRAY_COUNT(idata);
+ SkAutoTUnref<SkDataTable> itable(SkDataTable::NewCopyArray(idata,
+ sizeof(idata[0]),
+ icount));
+ REPORTER_ASSERT(reporter, itable->count() == icount);
+ 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, sizeof(int) == size);
+ }
+}
+
+static void test_vartable(skiatest::Reporter* reporter) {
+ const char* str[] = {
+ "", "a", "be", "see", "deigh", "ef", "ggggggggggggggggggggggggggg"
+ };
+ int count = SK_ARRAY_COUNT(str);
+ size_t sizes[SK_ARRAY_COUNT(str)];
+ for (int i = 0; i < count; ++i) {
+ sizes[i] = strlen(str[i]) + 1;
+ }
+
+ SkAutoTUnref<SkDataTable> table(SkDataTable::NewCopyArrays(
+ (const void*const*)str, sizes, count));
+
+ REPORTER_ASSERT(reporter, table->count() == count);
+ 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),
+ str[i]));
+ REPORTER_ASSERT(reporter, size == sizes[i]);
+
+ const char* s = table->atStr(i);
+ REPORTER_ASSERT(reporter, strlen(s) == strlen(str[i]));
+ }
+}
+
+static void test_tablebuilder(skiatest::Reporter* reporter) {
+ const char* str[] = {
+ "", "a", "be", "see", "deigh", "ef", "ggggggggggggggggggggggggggg"
+ };
+ int count = SK_ARRAY_COUNT(str);
+
+ SkDataTableBuilder builder(16);
+
+ for (int i = 0; i < count; ++i) {
+ builder.append(str[i], strlen(str[i]) + 1);
+ }
+ SkAutoTUnref<SkDataTable> table(builder.createDataTable());
+
+ 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),
+ str[i]));
+ REPORTER_ASSERT(reporter, size == strlen(str[i]) + 1);
+
+ const char* s = table->atStr(i);
+ REPORTER_ASSERT(reporter, strlen(s) == strlen(str[i]));
+ }
+}
+
+static void test_datatable(skiatest::Reporter* reporter) {
+ test_simpletable(reporter);
+ test_vartable(reporter);
+ test_tablebuilder(reporter);
+}
+
static void unrefAll(const SkDataSet::Pair pairs[], int count) {
for (int i = 0; i < count; ++i) {
pairs[i].fValue->unref();
@@ -146,6 +220,7 @@
test_cstring(reporter);
test_dataset(reporter);
+ test_datatable(reporter);
}
#include "TestClassDef.h"