git.net

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [users@httpd] APR Table vs. Hash & Array vs. Skip List vs. Ring


On 05/27/2018 05:49 PM, Nick Kew wrote:
>> On 27 May 2018, at 03:40, Simon Walter <simon@xxxxxxxxxx> wrote:
>>
>> Hi everyone,
>>
>> First of all, I am not sure if this is the right place to ask this.
>> Please send me to the appropriate mailing list. Thanks.
> 
> What's the context?  Given where you asked, I'll guess you're writing
> a module for your web server, in which case, there's a modules-dev list
> for the next question.

Thanks. Maybe I will ask there next time. Though, no I am not writing a
module.

>> I want to know basically what the difference is between a table and a
>> hash table - regarding the APR implementation.
> 
> The best place to look at APR is the source header files, which are the
> level at which it's most comprehensively documented and easy to follow.

I looked at those just now and it seems that the Doxygen generated docs
really are generated from the header files (as advertised) and don't
explain much regarding my question.

>> The one difference that stands out to me is that I can iterate over a
>> hash. So is a hash like a table with a linked list?
> 
> No.
> 
>> Perhaps a table can also be iterated over too. I haven't used tables yet
> 
> You can iterate over a table, too: use its underlying array.
> 
>>  I see function names containing
>> "merge" and "append", but the docs do not state how this is done.
> 
> The docs in the header files are pretty clear.

Yes, except: "...the docs do not state how this is done."

> 
> Also worth bearing in mind, apr_table's more esoteric functions originate in the
> standards for manipulating HTTP headers.  If in doubt, assume the behaviour
> follows HTTP.

Good to know, thanks.

> 
> Why not start with the simple: a C array of pointers void* my_array[N_ELTS],
> or a linked list?  Once you've thought through the problems with those, you're
> in a position to decide what struct will best serve you.
> 
> FWIW, the situation where I find an APR array helps most often over a linked
> list is in making life easier in a configuration merge function.
> 

Interesting. Thanks.

I thought maybe one of those "modules" (in the subject line) might be
implemented like a linked list or some other good idea - since the APR
is full of good ideas. I already use hash and tables. But I guess I will
not use either for this data.

To anyone else wondering the same thing:
apr_array_append calls apr_array_cat which copies memory - not just a
pointer or some trivial amount.
apr_hash_merge allocates memory for the size of the combined hash.
I didn't take time read further when I saw those lines. Tables are based
on arrays. So I can't use those either in this situation.

I can't see any copying with skip lists, but I haven't read the code in
it's entirety.

Best regards,

Simon

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@xxxxxxxxxxxxxxxx
For additional commands, e-mail: users-help@xxxxxxxxxxxxxxxx