On Fri, Nov 29, 2013 at 2:26 AM, Alex Rousskov
<[email protected]> wrote:
> On 11/26/2013 02:28 AM, Kinkie wrote:
>
>> +bool isMember(const SBufList &, const SBuf &, SBufCaseSensitive
>> isCaseSensitive = caseSensitive);
>
> Please capitalize global names, such as isMember().
Ok
>> +bool
>> +isMember(const SBufList & sl, const SBuf &S, SBufCaseSensitive
>> case_sensitive)
>> +{
>> + for (SBufList::const_iterator i = sl.begin(); i != sl.end(); ++i)
>> + if (i->compare(S,case_sensitive) == 0)
>> + return true;
>> + return false;
>> +}
>
> STL already provides std::find() and std::find_if() that are more
> flexible/universal and sometimes faster than isMember(). I suggest that
> you provide a predicate to be used for case-specific comparisons of
> buffers instead of isMember(). Such a predicate would be usable with any
> SBuf container, not just SBufList.
I suspect that these better belong to SBuf.cc than to SBufList.cc then.
Done so, and with perfect feature creep made it parametric (case
sensitive/insensitive) and built one also for prefix match.
Do you agree these two small auxiliary classes belong to SBuf.h or do
you think they should go elsewhere?
>> +SBuf
>> +SBufListJoin(const SBufList &list, const SBuf &separator)
>> +{
>> + if (list.size() == 0)
>> + return SBuf("");
>> + if (list.size() == 1)
>> + return list.front();
>
> This may be very ineffient for large lists and is probably unnecessary.
> Avoid list.size() calls if it all possible. std::list::size() is O(n),
> not O(1) in some older GCC implementations (at least). For one heated
> discussion, see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561
>
>
>
>> + SBufList::const_iterator i;
>> + // calculate the total size of the return value
>> + SBuf::size_type sz = 0;
>> + for (i = list.begin(); i != list.end(); ++i)
>> + sz += i->length();
>> + sz += separator.length()*list.size();
>> +
>> + SBuf rv;
>> + rv.rawSpace(sz);
>> +
>> + i = list.begin();
>> + rv.append(*i);
>> + ++i;
>> + for (; i!= list.end(); ++i) {
>> + rv.append(separator);
>> + rv.append(*i);
>> + }
>> + return rv;
>> +}
>
>
> Consider using std::accumulate with an appropriate operator instead of
> the above. Providing such an operator would allow folks to "join" SBufs
> stored in any SBUf container, not just SBufList.
Size precalculation is an optimization. I've made use of
std:accumulate via SBufListAccumulateSizes, but I'm not sure it'd be
worthwile to make that available throughout the code base. If so,
would SBuf.h be a good place?
>>>> attached is v1 of SBufList. Its purpose is to be the eventual heir
>>>> to wordlist.
>
>
> It may be useful to take a step back and decide whether we need a
> one-size-fits all wordlist or many SBuf containers, with different
> storage/access trade-offs. I am pretty sure it is the latter. The above
> suggestions are meant to make your work usable with all containers (and
> minimize code duplication).
I'd like to avoid scope creep.
This code is meant to supersede wordlist and bring the huge amount of
code that uses it into the c++ world (and into the world of managed
memory), and it can certainly be a step towards that end goal .
SBuf should be reasonably container-friendly and can certainly be made
even more so, but I'd prefer to address things as the need arises
instead of overdesigning them.
I'm attaching the revised patch.
--
/kinkie
=== modified file 'src/SBuf.h'
--- src/SBuf.h 2013-10-08 04:17:17 +0000
+++ src/SBuf.h 2013-11-29 15:16:09 +0000
@@ -607,4 +607,31 @@
return S.print(os);
}
+/** SBuf comparison predicate
+ *
+ * Comparison predicate for standard library containers.
+ */
+class SBufComparePredicate {
+public:
+ explicit SBufComparePredicate(const SBuf s, SBufCaseSensitive caseSensitive = caseSensitive) :
+ compareWith(s), sensitive(caseSensitive) {}
+ inline bool operator() (const SBuf & checking) { return 0 == checking.compare(compareWith,sensitive); }
+private:
+ SBuf compareWith;
+ SBufCaseSensitive sensitive;
+ SBufComparePredicate(); //no default constructor
+};
+
+class SBufPrefixComparePredicate {
+public:
+ explicit SBufPrefixComparePredicate(const SBuf s, SBufCaseSensitive caseSensitive = caseSensitive) :
+ compareWith(s), sensitive(caseSensitive) {}
+ inline bool operator() (const SBuf & checking) { return 0 == checking.startsWith(compareWith,sensitive); }
+private:
+ SBuf compareWith;
+ SBufCaseSensitive sensitive;
+ SBufPrefixComparePredicate(); //no default constructor
+};
+
+
#endif /* SQUID_SBUF_H */
=== added file 'src/SBufList.cc'
--- src/SBufList.cc 1970-01-01 00:00:00 +0000
+++ src/SBufList.cc 2013-12-01 21:37:19 +0000
@@ -0,0 +1,55 @@
+#include "squid.h"
+#include "SBufList.h"
+#include "wordlist.h"
+
+#include <algorithm>
+
+bool
+IsMember(const SBufList & sl, const SBuf &S, SBufCaseSensitive case_sensitive)
+{
+ return sl.end() != std::find_if(sl.begin(), sl.end(),
+ SBufComparePredicate(S,case_sensitive));
+}
+
+static inline SBuf::size_type
+SBufListAccumulateSizes(SBuf::size_type sz, const SBuf &item)
+{
+ return sz + item.length();
+}
+
+SBuf
+SBufListJoin(const SBufList &list, const SBuf &separator)
+{
+ // optimization: on empty list, return empty SBuf
+ if (list.begin() == list.end()) //empty
+ return SBuf("");
+
+ // optimization: pre-calculate needed storage
+ SBuf::size_type sz = 0;
+ std::accumulate(list.begin(), list.end(), sz, SBufListAccumulateSizes);
+ sz += separator.length() * list.size();
+
+ SBuf rv;
+ rv.rawSpace(sz);
+
+ //
+ SBufList::const_iterator i = list.begin();
+ rv.append(*i);
+ ++i;
+ for (; i!= list.end(); ++i) {
+ rv.append(separator);
+ rv.append(*i);
+ }
+ return rv;
+}
+
+SBufList
+wordlistToSBufList(wordlist *wl)
+{
+ SBufList rv;
+ while (wl != NULL) {
+ rv.push_back(SBuf(wl->key));
+ wl = wl->next;
+ }
+ return rv;
+}
=== added file 'src/SBufList.h'
--- src/SBufList.h 1970-01-01 00:00:00 +0000
+++ src/SBufList.h 2013-12-01 21:37:19 +0000
@@ -0,0 +1,26 @@
+#ifndef SQUID_SBUFLIST_H
+#define SQUID_SBUFLIST_H
+
+#include "SBuf.h"
+
+#include <list>
+
+typedef std::list<SBuf> SBufList;
+
+/** check for membership
+ *
+ * \return true if the supplied SBuf is a member of the list
+ * \param case_sensitive one of caseSensitive or caseInsensitive
+ */
+bool IsMember(const SBufList &, const SBuf &, SBufCaseSensitive isCaseSensitive = caseSensitive);
+
+/** join a SBufList into a SBuf using the supplied separator.
+ */
+SBuf SBufListJoin(const SBufList &list, const SBuf &separator = SBuf(""));
+
+class wordlist;
+/** convert a wordlist to a SBufList
+ */
+SBufList wordlistToSbufList(wordlist *);
+
+#endif /* SQUID_SBUFLIST_H */
=== added file 'src/tests/testSBufList.cc'
--- src/tests/testSBufList.cc 1970-01-01 00:00:00 +0000
+++ src/tests/testSBufList.cc 2013-12-01 21:37:19 +0000
@@ -0,0 +1,36 @@
+#include "squid.h"
+#include "SBufList.h"
+#include "testSBufList.h"
+
+CPPUNIT_TEST_SUITE_REGISTRATION( testSBufList );
+
+SBuf literal("The quick brown fox jumped over the lazy dog");
+static int sbuf_tokens_number=9;
+static SBuf tokens[]={
+ SBuf("The",3), SBuf("quick",5), SBuf("brown",5), SBuf("fox",3),
+ SBuf("jumped",6), SBuf("over",4), SBuf("the",3), SBuf("lazy",4),
+ SBuf("dog",3)
+};
+
+void
+testSBufList::testSBufListMembership()
+{
+ SBufList foo;
+ for (int j=0; j<sbuf_tokens_number; ++j)
+ foo.push_back(tokens[j]);
+ CPPUNIT_ASSERT_EQUAL(true,IsMember(foo,SBuf("fox")));
+ CPPUNIT_ASSERT_EQUAL(true,IsMember(foo,SBuf("Fox"),caseInsensitive));
+ CPPUNIT_ASSERT_EQUAL(false,IsMember(foo,SBuf("garble")));
+}
+
+void
+testSBufList::testSBufListJoin()
+{
+ SBufList foo;
+ CPPUNIT_ASSERT_EQUAL(SBuf(""),SBufListJoin(foo,SBuf("")));
+ CPPUNIT_ASSERT_EQUAL(SBuf(""),SBufListJoin(foo));
+ for (int j = 0; j < sbuf_tokens_number; ++j)
+ foo.push_back(tokens[j]);
+ SBuf joined=SBufListJoin(foo,SBuf(" "));
+ CPPUNIT_ASSERT_EQUAL(literal,joined);
+}
=== added file 'src/tests/testSBufList.h'
--- src/tests/testSBufList.h 1970-01-01 00:00:00 +0000
+++ src/tests/testSBufList.h 2013-11-25 18:33:15 +0000
@@ -0,0 +1,19 @@
+#ifndef SQUID_SRC_TEST_TESTSBUF_H
+#define SQUID_SRC_TEST_TESTSBUF_H
+
+#include <cppunit/extensions/HelperMacros.h>
+
+#include "OutOfBoundsException.h"
+
+class testSBufList : public CPPUNIT_NS::TestFixture
+{
+ CPPUNIT_TEST_SUITE( testSBufList );
+ CPPUNIT_TEST( testSBufListMembership );
+ CPPUNIT_TEST( testSBufListJoin );
+ CPPUNIT_TEST_SUITE_END();
+protected:
+ void testSBufListMembership();
+ void testSBufListJoin();
+};
+
+#endif
