On Mon, Dec 2, 2013 at 4:10 PM, Alex Rousskov
<rouss...@measurement-factory.com> wrote:
> On 12/02/2013 05:23 AM, Kinkie wrote:
>>> > My point was that joining SBuf containers is useful for all container
>>> > types, but your code only works for std::lists. I think you can provide
>>> > the same functionality, with the same level of optimization, by making
>>> > the code generic. Here is a sketch:
>>> >
>>> > {
>>> > SBuf::size_type mergedSize = 0;
>>> > std::accumulate(..., mergedSize, AddSize(separator));
>>> >
>>> > SBuf merged;
>>> > merged.reserveSpace(mergedSize);
>>> > std::accumulate(..., merged, AddContent(separator));
>>> >
>>> > return merged;
>>> > }
>>> >
>>> > The missing "..." parts just contain items.begin(), items.end(), where
>>> > bufs is the container.
>
>
>> Ok.
>> Let's try to sketch the grand plan, shall we?
>> What about using a SBufAlgs.h which contains
>>
>> SBufEqual
>> SBufStartsWith
>> SBufAddLength(separator=SBuf())
>
> Sounds good to me. I do not think you need a default value for the
> separator in the SBufAddLength.
>
> AFAICT, You will also need an SBufAddContent class "operator" with the
> following constructor (similar to SBufAddLength):
>
> SBufAddContent::SBufAddContent(const SBuf &separator);
Done.
> And, if you insist that IsMember() wrapper is needed, it can be placed
> in the same header file as well. Make it generic like the SBufJoin() below.
It's just convenience.
I'd leave SBufList.h / .cc only as convenience helpers, relying on
SBufAlgos.h for some grunt work.
>> template<class container> SBufContainerJoin<container>(...)
>
> This one will be more like
>
> template<class Container>
> SBuf
> SBufJoin(const Container &items, ...)
> {
> ... see the sketch above ...
> }
>
>
>> plus a specialized SBufListJoin which is simply an instantiation of
>> SBufContainerJoin<SBufList>?
>
> What will that specialization do differently? I do not think we need it
> but perhaps I am missing something.
As above: just convenience, or an intermediate step towards complete
containerization (c->c++ will be hard enough as is, as it will require
to have callers use correct encapsulation)
Attaching a new revision.
--
/kinkie
=== modified file 'src/SBuf.h'
--- src/SBuf.h 2013-10-08 04:17:17 +0000
+++ src/SBuf.h 2013-12-02 18:00:42 +0000
@@ -55,6 +55,7 @@
#define SQUIDSBUFPRINT(s) (s).plength(),(s).rawContent()
#endif /* SQUIDSBUFPH */
+// TODO: move within SBuf and rename
typedef enum {
caseSensitive,
caseInsensitive
=== added file 'src/SBufAlgos.h'
--- src/SBufAlgos.h 1970-01-01 00:00:00 +0000
+++ src/SBufAlgos.h 2013-12-02 18:00:42 +0000
@@ -0,0 +1,80 @@
+#ifndef SQUID_SBUFALGOS_H_
+#define SQUID_SBUFALGOS_H_
+
+#include "SBuf.h"
+#include <algorithm>
+
+/// SBuf equality predicate for STL algorithms etc
+class SBufEqual {
+public:
+ explicit SBufEqual(const SBuf &reference, SBufCaseSensitive caseSensitivity_ = caseSensitive) :
+ reference_(reference), sensitivity_(caseSensitivity_) {}
+ inline bool operator() (const SBuf & checking) { return 0 == checking.compare(reference_,sensitivity_); }
+private:
+ SBuf reference_;
+ SBufCaseSensitive sensitivity_;
+};
+
+/// SBuf "starts with" predicate for STL algorithms etc
+class SBufStartsWith {
+public:
+ explicit SBufStartsWith(const SBuf &prefix, SBufCaseSensitive caseSensitive = caseSensitive) :
+ prefix_(prefix), sensitive(caseSensitive) {}
+ inline bool operator() (const SBuf & checking) { return checking.startsWith(prefix_,sensitive); }
+private:
+ SBuf prefix_;
+ SBufCaseSensitive sensitive;
+};
+
+/** SBuf size addition accumulator for STL contaniners
+ *
+ * Equivalent to prefix_length + SBuf.length() + separator.length()
+ */
+class SBufAddLength {
+public:
+ explicit SBufAddLength(const SBuf &separator) :
+ separator_len(separator.length()) {}
+ SBuf::size_type operator()(const SBuf::size_type sz, const SBuf & item) {
+ return sz + item.length() + separator_len;
+ }
+private:
+ SBuf::size_type separator_len;
+};
+
+/// SBuf contents concatenation accumulator for STL containers
+class SBufAddContent {
+public:
+ explicit SBufAddContent(const SBuf& separator) :
+ separator_(separator), first(true) {}
+ SBuf operator() (SBuf accumulated, const SBuf &item) {
+ if (first) {
+ first = false;
+ accumulated.append(item);
+ return accumulated;
+ }
+ accumulated.append(separator_).append(item);
+ return accumulated;
+ }
+private:
+ const SBuf separator_;
+ bool first;
+};
+
+/// join all the SBuf in a container of SBuf into a single SBuf, separating with separator
+template <class Container>
+SBuf
+SBufContainerJoin(const Container &items, const SBuf& separator)
+{
+ // optimization: pre-calculate needed storage
+ SBuf::size_type sz;
+ sz = std::accumulate(items.begin(), items.end(), 0, SBufAddLength(separator));
+
+ SBuf rv;
+ rv.reserveSpace(sz);
+ rv = std::accumulate(items.begin(), items.end(), rv, SBufAddContent(separator));
+ return rv;
+}
+
+
+
+#endif /* SQUID_SBUFALGOS_H_ */
=== added file 'src/SBufList.cc'
--- src/SBufList.cc 1970-01-01 00:00:00 +0000
+++ src/SBufList.cc 2013-12-02 18:00:42 +0000
@@ -0,0 +1,27 @@
+#include "squid.h"
+#include "SBufList.h"
+#include "SBufAlgos.h"
+#include "wordlist.h"
+
+bool
+IsMember(const SBufList & sl, const SBuf &S, const SBufCaseSensitive case_sensitive)
+{
+ return std::find_if(sl.begin(), sl.end(), SBufEqual(S,case_sensitive)) != sl.end();
+}
+
+SBuf
+SBufListJoin(const SBufList &list, const SBuf &separator)
+{
+ return SBufContainerJoin(list,separator);
+}
+
+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-02 18:00:42 +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 &, const 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
