httpd-apreq-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Joe Schaefer <joe+apa...@sunstarsys.com>
Subject Re: [PROPOSAL] API change for 2.0 param values
Date Sun, 20 Oct 2002 23:29:33 GMT
Joe Schaefer <joe+apache@sunstarsys.com> writes:

[...]

>   typedef struct apreq_pv_t {
>         void        *data;
>         apr_ssize_t  size;
>   } apreq_pv_t;

I changed the name to apreq_value_t.

> I'm pretty sure this sort of change will require a break from
> using apr_tables, which will impact the apreq_request API 
> significantly.

We now have an apreq_table_t.  The api extends apr_table_t's
(extra functions for getting keys & values, etc.).  Here are
the relevant structs (implemented in apreq_tables.c, so they're
ADT's):

struct apreq_table_t {
    apr_array_header_t a;
    apreq_value_merge_t *merge; /* function pointer, see below */
    apreq_value_copy_t  *copy;  /* function pointer, see below */
    int root[TABLE_HASH_SIZE];  /* forest, keyed on the first character */
    unsigned char flags;
};

struct apreq_table_entry_t {
    const char *key;
    apreq_value_t *val;

    enum { RED, BLACK } color;  /* maintains tree balance */
    int tree[4];                /* LEFT RIGHT PARENT NEXT */
};

Here are the (public) function types for table->merge & table->copy:

typedef apreq_value_t *(apreq_value_merge_t)(const apreq_pool_t *p,
                                             const apreq_value_t **a,
                                             const apr_size_t s);

typedef apreq_value_t *(apreq_value_copy_t)(const apreq_pool_t *p,
                                            const apreq_value_t *v);

These two functions allow apreq users to dictate how apreq_value_t's
are merged and copied internally by apreq_table_t's.

apreq_tables are implemented as arrays, just like apr_tables.
This allows us to preserve "document order", which is important.
To increase the speed of table lookups over apache 1.3, 
apr_tables kept a "two-level hash"; the apr_table struct itself 
contains the first level- a lookup table based on the first 
letter of each key.

I kept that first level (first-letter) lookup in apreq_tables, 
but replaced apr_table's checksum (its "second level hash") stuff 
with binary trees.  They should be a bit faster than the current 
apr_tables implementation, are better at handling multivalued keys, 
and afford some tuning options for apreq users:

  1) users expecting "large" (100+ entries?) param tables can set 
     a flag that tells apreq to use red-black balanced trees
     (during parsing).  This ensures good uniform lookup 
     performance at the expense of some additional rebalancing 
     work during parsing.

  2) users that make frequent lookups on a few specific keys
     can set a flag that causes apreq_tables to promote the 
     corresponding table entries to the top of their tree.  
     This should make subsequent lookups on those entries as 
     fast as possible.

-- 
Joe Schaefer

Mime
View raw message