From f7c1b3ade62ffc88a191ae01dcb82acca8727fa4 Mon Sep 17 00:00:00 2001 From: hama Date: Fri, 16 Jan 2015 00:52:56 +0100 Subject: [PATCH] refactoring, dynamic delta (allocation) --- base/ReByteBuffer.cpp | 128 +++++++++++++++++++++------------------ base/ReByteBuffer.hpp | 1 + base/ReHashList.cpp | 18 +++++- base/ReHashList.hpp | 1 + base/ReSeqArray.cpp | 27 +++++++++ base/ReSeqArray.hpp | 1 + base/ReStringList.hpp | 9 ++- cunit/cuHashList.cpp | 7 ++- cunit/cuReByteBuffer.cpp | 12 ++++ 9 files changed, 139 insertions(+), 65 deletions(-) diff --git a/base/ReByteBuffer.cpp b/base/ReByteBuffer.cpp index 7dd45b2..b45206b 100644 --- a/base/ReByteBuffer.cpp +++ b/base/ReByteBuffer.cpp @@ -2,7 +2,6 @@ * ReByteBuffer.cpp * * Created on: 06.05.2010 - * Author: wk */ #include "base/rebase.hpp" @@ -17,10 +16,9 @@ extern int _snprintf (char* s, size_t maxlen, const char* format, ...); /** @brief Constructor. * * @param delta If a new storage must be allocated the size - * is incremented by at least this count of bytes. + * is incremented by at least this count of bytes */ -ReByteBuffer::ReByteBuffer(size_t delta) - : +ReByteBuffer::ReByteBuffer(size_t delta) : m_delta(delta), // m_primaryBuffer m_buffer(m_primaryBuffer), @@ -31,7 +29,7 @@ ReByteBuffer::ReByteBuffer(size_t delta) } /** @brief Constructor. * - * @param source The instance to copy (C string). + * @param source the instance to copy (C string) */ ReByteBuffer::ReByteBuffer(const char* source) : m_delta(PRIMARY_BUFFER_SIZE), @@ -72,10 +70,9 @@ ReByteBuffer::~ReByteBuffer(){ } /** @brief Copy constructor. * - * @param source The instance to copy. + * @param source the instance to copy */ -ReByteBuffer::ReByteBuffer(const ReByteBuffer& source) - : +ReByteBuffer::ReByteBuffer(const ReByteBuffer& source) : m_delta(source.delta()), // m_primaryBuffer m_buffer(m_primaryBuffer), @@ -87,9 +84,9 @@ ReByteBuffer::ReByteBuffer(const ReByteBuffer& source) /** @brief The assignment operator. * - * @param source The instance to copy. + * @param source the instance to copy * - * @return The instance itself. + * @return the instance itself */ ReByteBuffer& ReByteBuffer::operator =(const ReByteBuffer& source){ m_delta = source.delta(); @@ -106,10 +103,10 @@ ReByteBuffer& ReByteBuffer::operator =(const ReByteBuffer& source){ * assert(4 == buf.append("abc", 3).append("x").getLength()); * * - * @param source The sequence to append. - * @param length The length of the sequence. + * @param source the sequence to append + * @param length the length of the sequence * - * @return *this (for chaining). + * @return *this (for chaining) */ ReByteBuffer& ReByteBuffer::append(const Byte* source, size_t length){ if (length == (size_t) -1) @@ -130,10 +127,10 @@ ReByteBuffer& ReByteBuffer::append(const Byte* source, size_t length){ * assert(strcmp("33 ", buf.getBuffer()) == 0); * * - * @param number The number to append. - * @param format The format of the number used by sprintf(). + * @param number the number to append + * @param format the format of the number used by sprintf() * - * @return *this (for chaining). + * @return *this (for chaining) */ ReByteBuffer& ReByteBuffer::appendInt(int number, const char* format){ char buffer [128]; @@ -159,7 +156,7 @@ ReByteBuffer& ReByteBuffer::appendInt(int number, const char* format){ * assert("mydoc.txt", name.getBuffer()); * * - * @return *this (for chaining). + * @return *this (for chaining) */ ReByteBuffer& ReByteBuffer::append(const ReByteBuffer& source){ return append(source.str(), source.length()); @@ -174,9 +171,9 @@ ReByteBuffer& ReByteBuffer::append(const ReByteBuffer& source){ * assert(12 == buf.atoi(3, 3 + 2)); * * - * @param start The first index to convert. - * @param end -1: all found digits will be converted. - * Otherwise: The maximal number of digits to convert. + * @param start the first index to convert + * @param end -1: all found digits will be converted + * Otherwise: the maximal number of digits to convert */ int ReByteBuffer::atoi(size_t start, int end) const{ int rc = 0; @@ -203,7 +200,7 @@ int ReByteBuffer::atoi(size_t start, int end) const{ * * @param toCount the byte sequence to count * @param lengthOfToCount -1: length is strlen(toCount)
- * otherwise: length of toCount. + * otherwise: length of toCount */ int ReByteBuffer::count(const char* toCount, size_t lengthToCount){ int rc = 0; @@ -239,19 +236,20 @@ bool ReByteBuffer::endsWith(const Byte* tail, size_t tailLength, /** @brief Ensures that there is enough space. * - *

If not it will be allocated and the old value will be copied. - *

- *

A new allocation will be use at least m_delta bytes. - *

The allocated space is incremented by one because of the ending '\\0'. - *

+ * If not it will be allocated and the old value will be copied. * - * @param size At the end the size will be at least this value. + * A new allocation will be use at least m_delta bytes. + * The allocated space is incremented by one because of the ending '\\0'. + * + * @param size the size will be at least this value */ void ReByteBuffer::ensureSize(size_t size){ if (m_capacity < size){ - if (size - m_capacity < m_delta) - size = m_capacity + m_delta; - // Think for the ending '\0': + int delta = m_delta > 0 ? m_delta + : 2 * m_capacity < - m_delta ? 2 * m_capacity : - m_delta; + if (size - m_capacity < delta) + size = m_capacity + delta; + // Think for the ending '\0': Byte* buffer = new Byte[size + 1]; assert(buffer != NULL); if (m_length > 0) @@ -303,16 +301,16 @@ int ReByteBuffer::firstDifference(const Byte* source, size_t length, int start, * assert(5 == buf.indexOf("12", -1, 3)); * * - * @param toFind The sequence to find. - * @param toFindLength Length of toFind. - * If -1 the strlen(toFind) will be taken. - * @param start The search respects the indices in the range [start, end[ + * @param toFind the sequence to find + * @param toFindLength Length of toFind, + * If -1 the strlen(toFind) will be taken + * @param start the search respects the indices in the range [start, end[ * @param end -1: no upper limit to search
* otherwise: the first index above the search range * @param ignoreCase true: case insensitive search
* true: case sensitive search - * @return -1: The sequence could not be found. - * Otherwise: The index of toFind in the internal buffer. + * @return -1: the sequence could not be found. + * Otherwise: the index of toFind in the internal buffer */ int ReByteBuffer::indexOf(const Byte* toFind, size_t toFindLength, int start, int end, bool ignoreCase) const{ @@ -344,16 +342,16 @@ int ReByteBuffer::indexOf(const Byte* toFind, size_t toFindLength, int start, * assert(5 == buf.rindexOf("12", -1, 3)); * * - * @param toFind The sequence to find. - * @param toFindLength Length of toFind. - * If -1 the strlen(toFind) will be taken. - * @param start The search respects the indices in the range [start, end[ + * @param toFind the sequence to find + * @param toFindLength length of toFind. + * If -1 the strlen(toFind) will be taken + * @param start the search respects the indices in the range [start, end[ * @param end -1: no upper limit to search
* otherwise: the first index above the search range * @param ignoreCase true: case insensitive search
* true: case sensitive search - * @return -1: The sequence could not be found. - * Otherwise: The index of toFind in the internal buffer. + * @return -1: the sequence could not be found. + * Otherwise: the index of toFind in the internal buffer */ int ReByteBuffer::rindexOf(const Byte* toFind, size_t toFindLength, int start, int end, bool ignoreCase) const{ @@ -388,11 +386,11 @@ int ReByteBuffer::rindexOf(const Byte* toFind, size_t toFindLength, int start, * assert(strcmp("XYZabcXYZ3", buf.str()) == 0); * * - * @param toFind The substring which will be replaced. - * @param toFindLength The length of toFind. -1: strlen() will be used. - * @param replacement The replacement. - * @param replacementLength The length of replacement. -1: strlen() will be used. - * @param start The first index to inspect. + * @param toFind the substring which will be replaced + * @param toFindLength the length of toFind. -1: strlen() will be used + * @param replacement the replacement + * @param replacementLength the length of replacement. -1: strlen() will be used + * @param start the first index to inspect */ ReByteBuffer& ReByteBuffer::replaceAll(const Byte* toFind, size_t toFindLength, const Byte* replacement, size_t replacementLength, int start){ @@ -408,6 +406,16 @@ ReByteBuffer& ReByteBuffer::replaceAll(const Byte* toFind, size_t toFindLength, return *this; } +/** @brief Sets the increment used to increase the capacity. + * + * @param delta > 0: reservation allocates at least this amount of bytes
+ * 0: delta is set to a default value
+ * < 0: the current capacity will be doubled until - delta + */ +void ReByteBuffer::setDelta(int delta){ + m_delta = delta == 0 ? PRIMARY_BUFFER_SIZE : delta; +} + /** @brief Sets the length to a given value. * * The new length is greater than the current size the buffer will reallocated. @@ -420,9 +428,9 @@ ReByteBuffer& ReByteBuffer::replaceAll(const Byte* toFind, size_t toFindLength, * assert(5 == buf.getLength()); * * - * @param length The new length. + * @param length the new length * - * @return *this (for chaining). + * @return *this (for chaining) */ ReByteBuffer& ReByteBuffer::setLength(size_t length){ ensureSize(length); @@ -441,10 +449,10 @@ ReByteBuffer& ReByteBuffer::setLength(size_t length){ * assert(strcmp("123XX", buf.str()) == 0); * * - * @param length The new length. - * @param filler If the new length is greater than the current length the space - * will be filled with this value. - * @return *this (for chaining). + * @param length the new length + * @param filler if the new length is greater than the current length the space + * will be filled with this value + * @return *this (for chaining) */ ReByteBuffer& ReByteBuffer::setLengthAndFill(size_t length, Byte filler){ ensureSize(length); @@ -465,14 +473,14 @@ ReByteBuffer& ReByteBuffer::setLengthAndFill(size_t length, Byte filler){ * assert(strcmp("12XYZ5", buf.str()) == 0); * * - * @param ix The index where the cut/insertion takes place. - * @param replacedLength The number of deleted bytes. If 0 a pure insertion will be done. - * @param source The sequence to insert. May be NULL (for pure deletion). - * @param length The length of the inserted sequence. - * If 0: a pure deletion will be done. - * If -1: strlen(source) will be taken. + * @param ix the index where the cut/insertion takes place + * @param replacedLength the number of deleted bytes. If 0 a pure insertion will be done + * @param source the sequence to insert. May be NULL (for pure deletion) + * @param length the length of the inserted sequence
+ * 0: a pure deletion will be done
+ * -1: strlen(source) will be taken * - * @return true: Success. false: ix out of range. + * @return true: Success. false: ix out of range */ bool ReByteBuffer::splice(size_t ix, size_t replacedLength, const ReByteBuffer::Byte* source, size_t length){ diff --git a/base/ReByteBuffer.hpp b/base/ReByteBuffer.hpp index ab2e76d..1fbb0fe 100644 --- a/base/ReByteBuffer.hpp +++ b/base/ReByteBuffer.hpp @@ -156,6 +156,7 @@ public: inline ReByteBuffer& set(const ReByteBuffer& source){ return setLength(0).append(source); } + void setDelta(int delta); ReByteBuffer& setLength(size_t length); ReByteBuffer& setLengthAndFill(size_t length, Byte filler = 0); diff --git a/base/ReHashList.cpp b/base/ReHashList.cpp index 2d60e73..afc6420 100644 --- a/base/ReHashList.cpp +++ b/base/ReHashList.cpp @@ -114,7 +114,7 @@ bool ReHashList::get(const ReByteBuffer& key, */ bool ReHashList::next(ReArrayPosition& position, ReByteBuffer* key, ReByteBuffer* value) const{ - bool rc = position.m_position < m_keys.count(); + bool rc = position.m_position + 1 < m_keys.count(); if (rc){ ReByteBuffer dummy; ReSeqArray::Tag tag; @@ -170,4 +170,20 @@ void ReHashList::put(const ReByteBuffer& key, const ReByteBuffer& value){ put(key.str(), key.length(), value.str(), value.length()); } +/** + * Sets the capacity to avoiding reallocating buffers. + * + * @param maxKeys reserve space for this amount of keys. + * < 0: the current space will be doubled until -maxKeys + * @param keySpace reserve space for this amount of key string space.
+ * < 0: the current space will be doubled until -keySpace + * @param valueSpace reserve the space for this amount of value string space.
+ * < 0: the current space will be doubled until -valueSpace + */ +void ReHashList::setCapacity(int maxKeys, int keySpace, int contentSpace){ + m_keys.setCapacity(maxKeys, keySpace); + m_values.setCapacity(maxKeys, contentSpace); +} + + diff --git a/base/ReHashList.hpp b/base/ReHashList.hpp index 9eaf36c..1def144 100644 --- a/base/ReHashList.hpp +++ b/base/ReHashList.hpp @@ -40,6 +40,7 @@ public: void put(const Byte* key, size_t keyLength, const Byte* value, size_t valueLength); void put(const char* key, const char* value); void put(const ReByteBuffer& key, const ReByteBuffer& value); + void setCapacity(int maxKeys, int keySpace, int contentSpace); protected: int find(const Byte* key, size_t length) const; diff --git a/base/ReSeqArray.cpp b/base/ReSeqArray.cpp index cca2b36..ebd8fa0 100644 --- a/base/ReSeqArray.cpp +++ b/base/ReSeqArray.cpp @@ -444,6 +444,33 @@ void ReSeqArray::set(Index index, const Byte* source, setSequence(seq, indexContent, sourceLength, tag); } } + +/** @brief Sets the capacity of the instance. + * + * @param maxEntries > 0: the number of entries can be this value + * until the next reservation
+ * < 0: the current number of entries will be doubled + * until - maxEntries is reached + * @param maxStringSpace > 0: the number of entries can be this value + * until the next reservation
+ * < 0: the current number of entries will be doubled + * until - maxStringSpace is reached + */ +void ReSeqArray::setCapacity(int maxEntries, int maxStringSpace){ + if (maxEntries != 0){ + if (maxEntries > 0) + m_list.ensureSize(maxEntries * m_entrySize); + else + m_list.setDelta(maxEntries * m_entrySize); + } + if (maxStringSpace != 0){ + if (maxStringSpace > 0) + m_content.ensureSize(maxStringSpace); + else + m_content.setDelta(maxStringSpace); + } +} + /** @brief Sets the Sequence of an element. * * @param seq the target sequence diff --git a/base/ReSeqArray.hpp b/base/ReSeqArray.hpp index 5cb59fc..8e84fb1 100644 --- a/base/ReSeqArray.hpp +++ b/base/ReSeqArray.hpp @@ -65,6 +65,7 @@ public: } void remove(Index index); void set(Index index, const Byte* source, size_t sourceLength, Tag tag); + void setCapacity(int maxIndices, int maxStringSpace); void setSizes(int sizeOfTag, int sizeOfLength, size_t constantLength = INDIVIDUAL_SIZE); void setSorted(bool onNotOff); void setIgnoreCase(bool onNotOff); diff --git a/base/ReStringList.hpp b/base/ReStringList.hpp index 2807d4c..0020fbb 100644 --- a/base/ReStringList.hpp +++ b/base/ReStringList.hpp @@ -38,10 +38,12 @@ public: ReStringList& append(const ReStringList& source); bool equal(const ReStringList& toCompare) const; int firstDiff(const ReStringList& toCompare) const; - Index indexOf(const char* toFind, bool ignoreCase = false, Index start = 0) const; + Index indexOf(const char* toFind, bool ignoreCase = false, + Index start = 0) const; void insert(Index index, const char* source, Tag tag = 0); ReByteBuffer& join(const char* separator, ReByteBuffer& result) const; - Index nextStartingWith(Index index, const char* prefix, bool ignoreCase = false); + Index nextStartingWith(Index index, const char* prefix, + bool ignoreCase = false); bool readFromFile(const char* filename, bool cutNewline = true); void replace(Index index, const char* source, Tag tag = 0); void replaceString(Index index, const char* source); @@ -53,7 +55,8 @@ public: size_t sumOfSizes() const; size_t sumOfStrLengths() const; Tag tagOf(Index index) const; - bool writeToFile(const char* filename, const char* separator = "\n", const char* mode = "w"); + bool writeToFile(const char* filename, const char* separator = "\n", + const char* mode = "w"); }; #endif /* RESTRINGLIST_H_ */ diff --git a/cunit/cuHashList.cpp b/cunit/cuHashList.cpp index 7d4ccad..cd92cd5 100644 --- a/cunit/cuHashList.cpp +++ b/cunit/cuHashList.cpp @@ -10,6 +10,11 @@ private: testBasic(); testNext(); } + void massTest(){ + ReHashList hash(); + ReByteBuffer key, value; + log(false, "missing masstest"); + } void testBasic(){ ReHashList hash; ReByteBuffer key, value; @@ -41,9 +46,9 @@ private: } void testNext(){ ReHashList hash; + hash.put("4", "2"); hash.put("1", "8"); hash.put("2", "4"); - hash.put("4", "2"); hash.put("8", "1"); int flagsKey = 0; int flagsVal = 0; diff --git a/cunit/cuReByteBuffer.cpp b/cunit/cuReByteBuffer.cpp index 86e4167..91d44d1 100644 --- a/cunit/cuReByteBuffer.cpp +++ b/cunit/cuReByteBuffer.cpp @@ -13,6 +13,7 @@ public: } private: void run(){ + testSetDelta(); testFirstDiff(); testCount(); testEnsureSizeGetLength(); @@ -31,6 +32,17 @@ private: testSplice(); testReplace(); } + void testSetDelta(){ + ReByteBuffer buf("abcd"); + int maxDelta = 512 * (1 << 10); + buf.setDelta(- maxDelta); + int count = 0; + while(buf.capacity() < maxDelta){ + buf.ensureSize(buf.capacity() + 2); + count++; + } + checkT(count <= 10 + 1); + } void testFirstDiff(){ ReByteBuffer buf("abcd"); // firstDifference(const Byte* source, size_t length, int start, bool ignoreCase) -- 2.39.5