Re: [Libevent-users] Incremental search

[Azat Khuzhin <a3at.mail@xxxxxxxxx>]

Hi!

> request_line = evbuffer_readln(buf, &len, EVBUFFER_EOL_CRLF);

Yes, this is not optimal thing to do (though most of the time this
will be enough).

> If I see correctly in case of evbuffer_readln() the search always
> happens from the beginning of the chunks chain.

Yep

> In case of evbuffer_search_range() theoretically I can (optionally)
> provide the start evbuffer_ptr[2] but I have a problem finding an
> efficient way to update that pointer after every negative result.

I don't see problem in your code with updating it, it looks good to me.

> The only concept I came up with would look something like this:
> #v+
> tmp_ptr = evbuffer_search_range (buf, "\t", 1, incr_ptr.pos != -1 ? &incr_ptr : NULL, NULL);
> if (tmp_ptr.pos == -1) {
>     // negative result
>
>     // quick, read directly from an internal field
>     last_char = evbuffer_get_length (buf) - 1;
>     if (incr_ptr.pos != -1)
>         // requires second (after evbuffer_search_range) partial chain traversal
>         evbuffer_ptr_set (buf, &incr_ptr, last_char - prev_last_char, EVBUFFER_PTR_ADD);
>     else
>         // requires second (after evbuffer_search_range) chain traversal
>         evbuffer_ptr_set (buf, &incr_ptr, last_char, EVBUFFER_PTR_SET);
>     prev_last_char = last_char;

EVBUFFER_PTR_ADD is just to optimize code yep? (since EVBUFFER_PTR_SET
iterate over chunks)

(and evbuffer_ptr_set()+evbuffer_search_range() is not compatible with
evbuffer_pullup() and any other API that playing with chains)

> } else {
>     // a hit
>
>     incr_ptr.pos = -1;

So here you don't remove that part of the buffer (the one from the
beginning to the delimiter), yes?

> }
> #v-

> On the other hand this would cause one more (partial) traversal of the
> chain every time data arrives. Probably still more efficient because
> it's just hopping through a list and simple arithmetics compared to the
> naive readln-like evbuffer_search() solution.

Indeed, and if data arrives in a big chunks than you shouldn't see any overhead.

> It also contains a bug of checking the last seen character twice.
> Position after the last character is represented with chain == NULL, so
> it would be unusable with EVBUFFER_PTR_ADD.

Yeah, and we can't change evbuffer_ptr_set() since this will break
compatibility.
Maybe introduce some EVBUFFER_PTR_END that will set the ptr to the end
(real one), and this should be enough for incremental search?

(but I wasn't thinking about this enough time, so don't consider this
as some final decision).

> Probably it would be perfect if an alternative evbuffer_search_range()
> API existed with a non-const start/end evbuffer_ptr updated on every
> call so one can continue the search from the last seen position.

I guess so, but it doesn't exists for now, if you are interested in
contribute this feature, please go ahead!
***********************************************************************
To unsubscribe, send an e-mail to majordomo@xxxxxxxxxxxxx with
unsubscribe libevent-users    in the body.