From 9958e571e54767926bb22ba745938fec080122d4 Mon Sep 17 00:00:00 2001 From: hama Date: Tue, 13 Jan 2015 00:28:56 +0100 Subject: [PATCH] Refactoring: ReHashList as sorted ReSeqList --- base/ReHashList.cpp | 118 +++++++++++++++++++++-------------------- base/ReHashList.hpp | 17 ++++-- base/ReProgramArgs.cpp | 4 +- base/ReSeqList.cpp | 4 +- base/baselocations.hpp | 1 + cunit/cuHashList.cpp | 2 +- cunit/cuReSeqList.cpp | 5 +- cunit/testall.cpp | 2 +- 8 files changed, 83 insertions(+), 70 deletions(-) diff --git a/base/ReHashList.cpp b/base/ReHashList.cpp index 4f5aba1..a98229b 100644 --- a/base/ReHashList.cpp +++ b/base/ReHashList.cpp @@ -7,12 +7,43 @@ #include "base/rebase.hpp" +enum RELOC_HASHLIST { + LC_NEXT_1 = LC_HASHLIST + 1, // 50301 +}; + +/** + * Constructor. + */ +ReArrayPosition::ReArrayPosition() : + m_position(-1), + m_forward(true) +{ +} +/** + * Sets the cursor behind the last position. + * + * Calling ReHashList::prior() returns the last element. + */ +void ReArrayPosition::behindLast(){ + m_position = (ReSeqList::Index) -2; +} +/** + * Sets the cursor behind the last position. + * Calling ReHashList::next() returns the first element. + */ +void ReArrayPosition::priorFirst(){ + m_position = (ReSeqList::Index) -1; +} + /** Constructor. */ -ReHashList::ReHashList(int keyTagSize, int contentLengthSize, int keyLengthSize) : +ReHashList::ReHashList(bool ignoreCase, int keyTagSize, int contentLengthSize, + int keyLengthSize) : m_keys(), m_values() { + m_keys.setIgnoreCase(ignoreCase); + m_keys.setSorted(true); m_keys.setSizes(keyTagSize, keyLengthSize); m_keys.setSizes(0, contentLengthSize); } @@ -50,22 +81,12 @@ int ReHashList::find(const Byte* key, size_t length) const{ */ bool ReHashList::get(const Byte* key, size_t keyLength, ReByteBuffer& value) const{ - if (keyLength == (size_t) -1) - keyLength = strlen(key); - - int ix = find(key, keyLength); - bool rc = ix >= 0; -#if 0 + ReSeqList::Index index; + ReSeqList::Tag tag; + bool rc = m_keys.binarySearch(key, keyLength, index, &tag); if (rc){ - ReSeqList::Sequence* seq = m_keys.getInfo(ix); - // m_tag contains the index into m_values: - const Byte* ptr = reinterpret_cast(m_values.str() + seq->m_tag); - // m_values contains : - size_t valLength = * (size_t*) ptr; - ptr += sizeof (size_t); - value.set(ptr, valLength); + m_values.get(tag, value); } -#endif return rc; } /** @brief Returns the value of a key value pair. @@ -91,23 +112,23 @@ bool ReHashList::get(const ReByteBuffer& key, * * @param true: An item was found. false: No more items. */ -bool ReHashList::next(size_t& position, ReByteBuffer* key, ReByteBuffer* value) const{ - bool rc = position < m_keys.count(); +bool ReHashList::next(ReArrayPosition& position, ReByteBuffer* key, + ReByteBuffer* value) const{ + bool rc = position.m_position < m_keys.count(); if (rc){ - ReSeqList::Sequence* seq = m_keys.getInfo(position++); - if (key != NULL){ - const Byte* ptr = m_keys.getContent() + seq->m_index; - key->setLength(seq->m_length); - memcpy(key->buffer(), ptr, seq->m_length); - } - if (value != NULL){ -#if 0 - const Byte* ptr = reinterpret_cast(m_values.str() + seq->m_tag); - size_t length = * (size_t*) ptr; - ptr += sizeof (size_t); - value->setLength(length); - memcpy(value->buffer(), ptr, length); -#endif + ReByteBuffer dummy; + ReSeqList::Tag tag; + if (key == NULL) + key = &dummy; + if (! m_keys.get(++position.m_position, *key, &tag)){ + globalLogger()->sayF(LOG_ERROR | CAT_LIB, LC_NEXT_1, + i18n("next(): invalid cursor: $1")) + .arg((int) position.m_position).end(); + } else { + if (value != NULL) + if (! m_values.get((size_t) tag, *value)){ + globalLogger()->sayF(LOG_ERROR | CAT_LIB, LC_NEXT_1, + i18n("next(): invalid content index: $1")).arg((int) tag).end(); } } } return rc; @@ -121,38 +142,21 @@ bool ReHashList::next(size_t& position, ReByteBuffer* key, ReByteBuffer* value) */ void ReHashList::put(const Byte* key, size_t keyLength, const Byte* value, size_t valueLength){ -#if 0 if (keyLength == (size_t) -1) keyLength = strlen(key); if (valueLength == (size_t) -1) valueLength = strlen(value); - int ix = find(key, keyLength); - bool storeValue = false; - if (ix < 0){ - ReSeqList::Index pos = m_values.length(); - storeValue = true; - m_keys.add(-1, key, keyLength, pos); + ReSeqList::Index index; + ReSeqList::Tag tag; + if (m_keys.binarySearch(key, keyLength, index, &tag)){ + // replace the value: + m_values.set((ReSeqList::Index) tag, value, valueLength, 0); } else { - Sequence* seq = m_keys.getInfo(ix); - // m_tag contains the index into m_values. - Byte* ptr = m_values.buffer() + seq->m_tag; - size_t valLength = * (size_t *) ptr; - // Can we take the old storage? - if (valLength >= valueLength){ - // Yes, it is enough space: - * (size_t *) ptr = valueLength; - ptr += sizeof (size_t); - memcpy(ptr, value, valueLength); - } else { - storeValue = true; - seq->m_tag = m_values.length(); - } - } - if (storeValue){ - m_values.append((Byte*) &valueLength, sizeof valueLength); - m_values.append(value, valueLength); + // insert a new value. + tag = (ReSeqList::Tag) m_values.count(); + m_values.add(-1, value, valueLength); + m_keys.add(index, key, keyLength, tag); } -#endif } /** @brief Puts a key value pair into the hashlist. * diff --git a/base/ReHashList.hpp b/base/ReHashList.hpp index 88371d5..719f519 100644 --- a/base/ReHashList.hpp +++ b/base/ReHashList.hpp @@ -8,6 +8,16 @@ #ifndef REHASHLIST_H_ #define REHASHLIST_H_ +class ReArrayPosition{ +public: + ReArrayPosition(); +public: + void behindLast(); + void priorFirst(); +public: + ReSeqList::Index m_position; + bool m_forward; +}; /** @brief A simple associative array. * * An instance stores key value pairs. @@ -19,13 +29,14 @@ public: typedef char Byte; typedef ReSeqList::Sequence Sequence; public: - ReHashList(int keyTagSize = 1, int contentLengthSize = 1, int keyLengthSize = 1); + ReHashList(bool ignoreCase = false, int keyTagSize = 1, + int contentLengthSize = 1, int keyLengthSize = 1); virtual ~ReHashList(); public: void clear(); bool get(const Byte* key, size_t keyLength, ReByteBuffer& value) const; bool get(const ReByteBuffer& key, ReByteBuffer& value) const; - bool next(size_t& position, ReByteBuffer* key, ReByteBuffer* val) const; + bool next(ReArrayPosition& position, ReByteBuffer* key, ReByteBuffer* val) const; 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); @@ -36,7 +47,7 @@ protected: //@ Containing an array of keys. ReSeqList m_keys; //@ Containing the values. The tag of m_key is the index - //@ of the start position in m_values. + //@ in m_values. ReSeqList m_values; }; diff --git a/base/ReProgramArgs.cpp b/base/ReProgramArgs.cpp index 57d15bc..d8d541a 100644 --- a/base/ReProgramArgs.cpp +++ b/base/ReProgramArgs.cpp @@ -321,7 +321,7 @@ const char* ReProgramArgs::getProgramName() const{ */ void ReProgramArgs::search(char shortName, const char* longName, ReByteBuffer& name, ReStringList& list){ - size_t position = 0; + ReArrayPosition position; ReByteBuffer properties; bool found = false; size_t lengthLongName = 0; @@ -544,7 +544,7 @@ void ReProgramArgs::help(const char* message, bool issueLastError, lines.append(m_usage); lines.append(""); - size_t position = 0; + ReArrayPosition position; if (m_properties.next(position, NULL, NULL)){ lines.append(i18n(":")); } diff --git a/base/ReSeqList.cpp b/base/ReSeqList.cpp index c10e5bf..db30a6a 100644 --- a/base/ReSeqList.cpp +++ b/base/ReSeqList.cpp @@ -220,9 +220,9 @@ int ReSeqList::compare(Index index1, Index index2){ void ReSeqList::dump(FILE* fp) const{ ReByteBuffer buffer; Tag tag; - for (int ix = 0; ix < count(); ix++){ + for (int ix = 0; ix < (int) count(); ix++){ get(ix, buffer, &tag); - fprintf(fp, "%d: (%lld) [%d] %s\n", ix, (int64_t) tag, buffer.length(), + fprintf(fp, "%d: (%ld) [%d] %s\n", ix, (int64_t) tag, (int) buffer.length(), buffer.str()); } } diff --git a/base/baselocations.hpp b/base/baselocations.hpp index b96a8a6..e132b1a 100644 --- a/base/baselocations.hpp +++ b/base/baselocations.hpp @@ -14,6 +14,7 @@ enum RELOC_LIB { LC_CONFIGFILE = 50000, LC_DIRTOOLS = 50100, LC_SEQLIST = 50200, + LC_HASHLIST = 50300, }; enum RELOC_UDPCONNECTION { LC_UDPCONNECTION_CONSTRUCT = 50101, diff --git a/cunit/cuHashList.cpp b/cunit/cuHashList.cpp index 8a3bc84..7d4ccad 100644 --- a/cunit/cuHashList.cpp +++ b/cunit/cuHashList.cpp @@ -47,7 +47,7 @@ private: hash.put("8", "1"); int flagsKey = 0; int flagsVal = 0; - size_t pos = 0; + ReArrayPosition pos; ReByteBuffer key, value; while(hash.next(pos, &key, &value)){ int x = atol(key.buffer()); diff --git a/cunit/cuReSeqList.cpp b/cunit/cuReSeqList.cpp index 2397b9d..5406402 100644 --- a/cunit/cuReSeqList.cpp +++ b/cunit/cuReSeqList.cpp @@ -25,8 +25,6 @@ private: ReSeqList list; list.setIgnoreCase(true); ReByteBuffer value, expectedValue; - ReSeqList::Tag tag = 0; - ReSeqList::Tag expectedTag = 0; list.add(-1, "bcd", -1, 200); list.add(-1, "abcd", -1, 100); list.add(-1, "abc", -1, 300); @@ -43,6 +41,7 @@ private: checkElement(list, 3U, "bCd", 200); checkElement(list, 4U, "cde", 400); ReSeqList::Index index; + ReSeqList::Tag tag; checkT(list.binarySearch("Abc", -1, index, &tag)); checkEqu(0u, index); checkT(list.binarySearch("AbcD", -1, index, &tag)); @@ -56,8 +55,6 @@ private: ReSeqList list; list.setIgnoreCase(true); ReByteBuffer value, expectedValue; - ReSeqList::Tag tag = 0; - ReSeqList::Tag expectedTag = 0; list.add(-1, "bcd", -1, 200); list.add(0, "abc", -1, 100); list.dump(stdout); diff --git a/cunit/testall.cpp b/cunit/testall.cpp index f2921f4..18ac15a 100644 --- a/cunit/testall.cpp +++ b/cunit/testall.cpp @@ -16,7 +16,7 @@ void testBase(){ extern void testReSeqList(); testReSeqList(); extern void testReTestUnit(); - testReTestUnit(); + // testReTestUnit(); extern void testReByteBuffer(); testReByteBuffer(); extern void testReSeqList(void); -- 2.39.5