Re: [PATCH] SBufList

On 12/01/2013 02:41 PM, Kinkie wrote:
> On Fri, Nov 29, 2013 at 2:26 AM, Alex Rousskov wrote:
>> On 11/26/2013 02:28 AM, Kinkie wrote:
>>
>>> +bool isMember(const SBufList &, const SBuf &, SBufCaseSensitive isCaseSensitive = caseSensitive);

The last parameter can be const as well.

>>> +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.

This is not feature creep IMO. This is simply the Right Way to support
SBuf search in STL containers.

> +class SBufComparePredicate {

This only compares for equality. I suggest naming it SBufEqual.

> +class SBufPrefixComparePredicate {

This only compare for prefix-equality. I suggest naming it SBufStartsWith.

If you think an explicit "Predicate" suffix is needed for some reason,
add that or just "P". Personally, I do not see a need for either.

Please document each predicate class. Currently only the first is
documented. A one-line description is enough for each IMO. For example:

/// SBuf equality predicate for STL algorithms and such

/// SBuf "starts with" predicate for STL algorithms and such

> + SBufPrefixComparePredicate(); //no default constructor
> + SBufComparePredicate(); //no default constructor

Why declare one if it should not be available? The compiler will not
generate one because you already have a non-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;

I would rename compareWith member in this class to "prefix". This will
help document what the constructor parameter is meant to be.

> + explicit SBufComparePredicate(const SBuf s, SBufCaseSensitive caseSensitive = caseSensitive) :
> + explicit SBufPrefixComparePredicate(const SBuf s, SBufCaseSensitive caseSensitive = caseSensitive) :

* "s" can be a reference to avoid an extra refcounting overhead.

* caseSensitive can be const

* please use a unique name for the formal parameter; I suggest "sensitivity"

> + SBufCaseSensitive sensitive;

> + SBufCaseSensitive sensitive;

I suggest sensitivity_ for both names.

BTW, the SBufCaseSensitive type should be similarly renamed as well IMO.
Why is it even declared outside of the SBuf class?

> + inline bool operator() (const SBuf & checking) { return 0 == checking.compare(compareWith,sensitive); }

> + return sl.end() != std::find_if(sl.begin(), sl.end(),
> + SBufComparePredicate(S,case_sensitive));

.arguments == of order natural a use Please

> + inline bool operator() (const SBuf & checking) { return 0 == checking.startsWith(compareWith,sensitive); }

startsWith() returns bool. No need to compare it with anything.

> Do you agree these two small auxiliary classes belong to SBuf.h or do
> you think they should go elsewhere?

SBuf.h is fine IMO.

> + //
> + SBufList::const_iterator i = list.begin();
> + rv.append(*i);
> + ++i;
> + for (; i!= list.end(); ++i) {
> + rv.append(separator);
> + rv.append(*i);
> + }

Consider using std::accumulate with an appropriate "operator" class
instead of the above. See a sketch below.

There is also an empty comment at the start of that block.

> + sz += separator.length() * list.size();

Not a big deal, but this is wrong for single-item lists that do not use
a separator.

> + rv.rawSpace(sz);

Please use reserveSpace() if you do not need to access the reserved
space immediately.

>>> + 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.

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.

> If so, would SBuf.h be a good place?

Probably not for the templated implementation, to avoid dragging
templates and algorithms into every SBuf user code. SBufAlgs.h,
SBufGadgets.h, SBufMerge.h (for SBuf-specific implementation), or even
ToCsv.h (for 100% generic one) might work better.

> + // optimization: on empty list, return empty SBuf
> + if (list.begin() == list.end()) //empty
> + return SBuf("");

Unless you expect most merged lists to be empty, this is not an
optimization but a waste of CPU cycles (on average).

If you keep this code, please at least return SBuf() instead of the much
more expensive SBuf("").

>>>>> 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.

IIRC, we already know that wordlist does not work well in some of its
current usage contexts or is not used in other contexts despite being a
close match in some aspects. If my recollection is correct, there is no
scope creep or over-design in my request: It may be best to replace
wordlist with several different container types while brining it into
the C++ world instead of bringing the wrong concept and then fixing the
results.

If you are sure that we only need doubly-linked lists of SBufs, then we
can keep things a tiny bit simpler by assuming std::list<SBuf>
everywhere. Note, however, that the code will not actually change that
much. It is just a matter of a container type AFAICT and templates can
handle that.

Cheers,

Alex.
Received on Mon Dec 02 2013 - 00:37:18 MST