Latest string_token Code
Rory McGuire
rmcguire at neonova.co.za
Wed Jun 23 00:15:03 PDT 2010
On Tue, 22 Jun 2010 22:59:55 +0200, Ben Hanson <Ben.Hanson at tfbplc.co.uk>
wrote:
> == Quote from bearophile (bearophileHUGS at lycos.com)'s article
>> Ben Hanson:
>> Even if you are an expert C++ programmer, I can express few more
>> comments about
> your code, to show how to program in D (here I comment only the first
> example of
> each thing. More cases can follow).
>
> It's hard to be an expert in C++ these days, particularly when posting
> to a group
> frequented by Andrei! :-D
>
>> ------------------
>> You can write this:
>> template regex(CharT)
>> {
>> struct BasicStringToken
>> {
>> Like this:
>> template regex(CharT)
>> {
>> struct BasicStringToken
>> {
>> ------------------
>> In this part:
>> void negate()
>> {
>> CharT curr_char = START_CHAR;
>> CharT[] temp;
>> CharT *ptr = cast(CharT *) 0;
>> This is closer to normal D code, because in D there is "null", and in D
>> the * of
> pointer definitions is better written on the left, because it's part of
> the type:
>> void negate()
>> {
>> CharT curr_char = START_CHAR;
>> CharT[] temp;
>> CharT* ptr = null;
>> But the idiomatic D code is this because pointers are automatically
>> initialized
> to null, and nornally in D variable names are camelCase with a starting
> lowercase
> (sometimes I'd like to use underscores, but this is the D style.
> Constant names
> can contain underscores in D, I presume):
>> void negate()
>> {
>> CharT currChar = START_CHAR;
>> CharT[] temp;
>> CharT* ptr;
>> ------------------
>
> I forgot about auto initialisation in D. D'oh!
>
>> This line:
>> else if (!overlap.charset.length == 0)
>> I don't like it a lot, maybe this is better:
>> else if (overlap.charset.length)
>
> This is just a bug. Should be:
> else if (!overlap.charset.length)
>
>> ------------------
>> This code:
>> else if (negated)
>> {
>> intersectNegated(rhs, overlap);
>> }
>> else // negated == false
>> {
>> intersectCharset(rhs, overlap);
>> }
>> There is no need of that comment, never add useless noise to the code:
>> else if (negated)
>> {
>> intersectNegated(rhs, overlap);
>> }
>> else
>> {
>> intersectCharset(rhs, overlap);
>> }
>
> Those comments were deliberate as a 'yes I do mean that', but I've
> removed them
> anyway.
>
>> ------------------
>> I see that in your code you lot of pointers. Pointers can be used in D,
>> but I
> suggest you to use them only when necessary. Maybe some usage of
> pointers can be
> replaced by normal array indexes, that are safer too (because in D in
> nonrelease
> mode array bounds are tested).
>> For some situations I have created in D2 a "safer pointer" that in
>> release mode
> is as efficient as a pointer but in nonrelease mode asserts if you make
> it step
> out of a pre-specified memory interval. I don't think lot of people here
> has
> appreciated it, but I have used it to catch some of my pointer-releated
> bugs.
>> Bye,
>> bearophile
>
> All the code for this library needs to absolutely as fast as it can be.
> As it
> turns out, by intersecting regex charsets once in the code then it won't
> take that
> many cycles, but the only question I have is:
>
> Will the optimiser create as fast code if you use indexes compared to
> pointers?
>
> Updated code follows.
>
> Thanks,
>
> Ben
>
> module main;
>
> import std.algorithm;
> import std.array;
> import std.c.string;
> import std.string;
>
> import std.stdio;
>
> template regex(CharT)
> {
> struct BasicStringToken
> {
> bool negated = false;
> CharT[] charset;
> enum size_t MAX_CHARS = CharT.max + 1;
> enum size_t START_CHAR = cast(CharT) 0x80 < 0 ? 0x80 : 0;
>
> this(const bool negated_, ref CharT[] charset_)
> {
> negated = negated_;
> charset = charset_;
> }
>
> void removeDuplicates()
> {
> charset.sort;
> squeeze(charset);
> }
>
> void normalise()
> {
> if (charset.length == MAX_CHARS)
> {
> negated = !negated;
> charset.clear();
> }
> else if (charset.length > MAX_CHARS / 2)
> {
> negate();
> }
> }
>
> void negate()
> {
> CharT currChar = START_CHAR;
> CharT[] temp;
> CharT *ptr;
> CharT *curr = charset.ptr;
> CharT *end = curr + charset.length;
> size_t i = 0;
>
> negated = !negated;
> temp.length = MAX_CHARS - charset.length;
> ptr = temp.ptr;
>
> while (curr < end)
> {
> while (*curr > currChar)
> {
> *ptr = currChar;
> ++ptr;
> ++currChar;
> ++i;
> }
>
> ++currChar;
> ++curr;
> ++i;
> }
>
> for (; i < MAX_CHARS; ++i)
> {
> *ptr = currChar;
> ++ptr;
> ++currChar;
> }
>
> charset = temp;
> }
>
> bool empty()
> {
> return charset.length == 0 && !negated;
> }
>
> bool any()
> {
> return charset.length == 0 && negated;
> }
>
> void clear()
> {
> negated = false;
> charset.length = 0;
> }
>
> void intersect(ref BasicStringToken rhs,
> ref BasicStringToken overlap)
> {
> if ((any() && rhs.any()) || (negated == rhs.negated &&
> !any() && !rhs.any()))
> {
> intersectSameTypes(rhs, overlap);
> }
> else
> {
> intersectDiffTypes(rhs, overlap);
> }
> }
>
> private:
> void intersectSameTypes(ref BasicStringToken rhs,
> ref BasicStringToken overlap)
> {
> if (any())
> {
> clear();
> overlap.negated = true;
> rhs.clear();
> }
> else
> {
> CharT *iter = charset.ptr;
> CharT *end = iter + charset.length;
> CharT *rhsIter = rhs.charset.ptr;
> CharT *rhsEnd = rhsIter + rhs.charset.length;
>
> overlap.negated = negated;
>
> while (iter != end && rhsIter != rhsEnd)
> {
> if (*iter < *rhsIter)
> {
> ++iter;
> }
> else if (*iter > *rhsIter)
> {
> ++rhsIter;
> }
> else
> {
> overlap.charset ~= *iter;
> memmove(iter, iter + 1, (charset.ptr +
> charset.length - iter) * CharT.sizeof);
> --end;
> charset.length -= 1;
> memmove(rhsIter, rhsIter + 1, (rhs.charset.ptr +
> rhs.charset.length - rhsIter) * CharT.sizeof);
> --rhsEnd;
> rhs.charset.length -= 1;
> }
> }
>
> if (negated)
> {
> // duplicates already merged
> // src, dest
> merge(charset, overlap.charset);
> // duplicates already merged
> // src, dest
> merge(rhs.charset, overlap.charset);
> negated = false;
> rhs.negated = false;
> swap(charset, rhs.charset);
> normalise();
> overlap.normalise();
> rhs.normalise();
> }
> else if (!overlap.charset.length)
> {
> normalise();
> overlap.normalise();
> rhs.normalise();
> }
> }
> }
>
> void intersectDiffTypes(ref BasicStringToken rhs,
> ref BasicStringToken overlap)
> {
> if (any())
> {
> intersectAny(rhs, overlap);
> }
> else if (negated)
> {
> intersectNegated(rhs, overlap);
> }
> else
> {
> intersectCharset(rhs, overlap);
> }
> }
>
> void intersectAny(ref BasicStringToken rhs, ref BasicStringToken
> overlap)
> {
> if (rhs.negated)
> {
> rhs.intersectNegated(this, overlap);
> }
> else
> {
> rhs.intersectCharset(this, overlap);
> }
> }
>
> void intersectNegated(ref BasicStringToken rhs,
> ref BasicStringToken overlap)
> {
> if (rhs.any())
> {
> overlap.negated = true;
> overlap.charset = charset;
> rhs.negated = false;
> rhs.charset = charset;
> clear();
> }
> else
> {
> rhs.intersectCharset(this, overlap);
> }
> }
>
> void intersectCharset(ref BasicStringToken rhs,
> ref BasicStringToken overlap)
> {
> if (rhs.any())
> {
> overlap.charset = charset;
> rhs.negated = true;
> rhs.charset = charset;
> clear();
> }
> else
> {
> CharT *iter = charset.ptr;
> CharT *end = iter + charset.length;
> CharT *rhsIter = rhs.charset.ptr;
> CharT *rhsEnd = rhsIter + rhs.charset.length;
>
> while (iter != end && rhsIter != rhsEnd)
> {
> if (*iter < *rhsIter)
> {
> overlap.charset ~= *iter;
> rhs.charset.length += 1;
> rhsIter = rhs.charset.ptr;
> rhsEnd = rhsIter + rhs.charset.length;
> memmove(rhsIter + 1, rhsIter, (rhs.charset.length -
> (rhsEnd - rhsIter - 1)) * CharT.sizeof);
> ++rhsIter;
> memmove(iter, iter + 1, (charset.ptr +
> charset.length - iter) * CharT.sizeof);
> charset.length -= 1;
> --end;
> }
> else if (*iter > *rhsIter)
> {
> ++rhsIter;
> }
> else
> {
> ++iter;
> ++rhsIter;
> }
> }
>
> if (iter != end)
> {
> CharT[] temp;
>
> temp.length = end - iter;
> memmove(temp.ptr, iter, temp.length * CharT.sizeof);
>
> // nothing bigger in rhs than iter
> // src, dest
> merge(temp, overlap.charset);
> memmove(iter, iter + 1, (charset.ptr +
> charset.length - iter) * CharT.sizeof);
> charset.length -= 1;
> }
>
> if (!overlap.charset.empty())
> {
> merge(overlap.charset, rhs.charset);
> // possible duplicates, so check for any and erase.
> squeeze(rhs.charset);
> normalise();
> overlap.normalise();
> rhs.normalise();
> }
> }
> }
>
> void squeeze(ref CharT[] str)
> {
> if (str.length > 1)
> {
> CharT *write = str.ptr;
> CharT *end = write + str.length;
> CharT *read = write + 1;
>
> while (read != end)
> {
> while (read != end && *read == *write)
> {
> ++read;
> }
>
> if (read == end) break;
>
> ++write;
>
> if (read > write)
> {
> *write = *read;
> }
>
> ++read;
> }
>
> str.length = write + 1 - str.ptr;
> }
> }
>
> void merge(ref CharT[] src, ref CharT[] dest)
> {
> CharT[] temp;
> CharT *ptr;
> CharT *iter = src.ptr;
> CharT *end = iter + src.length;
> CharT *destIter = dest.ptr;
> CharT *destEnd = destIter + dest.length;
>
> temp.length = src.length + dest.length;
> ptr = temp.ptr;
>
> while (iter != end && destIter != destEnd)
> {
> if (*iter < *destIter)
> {
> *ptr++ = *iter++;
> }
> else
> {
> *ptr++ = *destIter++;
> }
> }
>
> while (iter != end)
> {
> *ptr++ = *iter++;
> }
>
> while (destIter != destEnd)
> {
> *ptr++ = *destIter++;
> }
>
> dest = temp;
> }
> };
> }
>
> int main(char[][]argv)
> {
> regex!(char).BasicStringToken lhs;
> regex!(char).BasicStringToken rhs;
> regex!(char).BasicStringToken intersect;
>
> lhs.charset = "aaabbc".dup;
> lhs.negated = true;
> lhs.removeDuplicates();
> rhs.charset = "bccddd".dup;
> rhs.negated = true;
> rhs.removeDuplicates();
> writeln(lhs.charset, '(', lhs.negated, ") intersect ",
> rhs.charset, '(', rhs.negated, ") =");
> lhs.intersect(rhs, intersect);
> writeln(lhs.charset, '(', lhs.negated, "), ",
> rhs.charset, '(', rhs.negated, "), ",
> intersect.charset, '(', intersect.negated, ')');
> return 0;
> }
While you are using pointers to do all the copying, comparing etc... are
you taking
into account that the characters may span multiple CharTs?
More information about the Digitalmars-d
mailing list