apr-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bri...@apache.org
Subject cvs commit: apr CHANGES
Date Sat, 20 Jul 2002 21:28:50 GMT
brianp      2002/07/20 14:28:50

  Modified:    tables   apr_tables.c
               .        CHANGES
  Log:
  Added a simple index to apr_table_t to reduce the best-case
  execution time for table lookups from O(n) to O(1).
  
  The worst-case time remains O(n), but in httpd benchmarking
  this indexing reduces the mean execution time of apr_table_get()
  by 40% and apr_table_unset() by 60%.
  
  The indexing will make it possible to speed up apr_table_vdo()
  and apr_table_overlap() in the future, but I haven't changed
  those yet.
  
  Revision  Changes    Path
  1.37      +238 -45   apr/tables/apr_tables.c
  
  Index: apr_tables.c
  ===================================================================
  RCS file: /home/cvs/apr/tables/apr_tables.c,v
  retrieving revision 1.36
  retrieving revision 1.37
  diff -u -r1.36 -r1.37
  --- apr_tables.c	13 Jul 2002 18:16:33 -0000	1.36
  +++ apr_tables.c	20 Jul 2002 21:28:50 -0000	1.37
  @@ -313,6 +313,12 @@
   #define CASE_MASK 0xdfdfdfdf
   #endif
   
  +#define TABLE_HASH_SIZE 32
  +#define TABLE_INDEX_MASK 0x1f
  +#define TABLE_HASH(key)  (TABLE_INDEX_MASK & *(unsigned char *)(key))
  +#define TABLE_INDEX_IS_INITIALIZED(t, i) ((t)->index_initialized & (1 << (i)))
  +#define TABLE_SET_INDEX_INITIALIZED(t, i) ((t)->index_initialized |= (1 << (i)))
  +
   /* Compute the "checksum" for a key, consisting of the first
    * 4 bytes, normalized for case-insensitivity and packed into
    * an int...this checksum allows us to do a single integer
  @@ -355,6 +361,21 @@
       /** Who created the array. */
       void *creator;
   #endif
  +    /* An index to speed up table lookups.  The way this works is:
  +     *   - Take the requested key and compute its checksum
  +     *   - Hash the checksum into the index:
  +     *     - index_first[TABLE_HASH(checksum)] is the offset within
  +     *       the table of the first entry with that key checksum
  +     *     - index_last[TABLE_HASH(checksum)] is the offset within
  +     *       the table of the first entry with that key checksum
  +     *   - If (and only if) there is no entry in the table whose
  +     *     checksum hashes to index element i, then the i'th bit
  +     *     of index_initialized will be zero.  (Check this before
  +     *     trying to use index_first[i] or index_last[i]!)
  +     */
  +    apr_uint32_t index_initialized;
  +    int index_first[TABLE_HASH_SIZE];
  +    int index_last[TABLE_HASH_SIZE];
   };
   
   /*
  @@ -391,6 +412,7 @@
   #ifdef MAKE_TABLE_PROFILE
       t->creator = __builtin_return_address(0);
   #endif
  +    t->index_initialized = 0;
       return t;
   }
   
  @@ -410,26 +432,55 @@
       make_array_core(&new->a, p, t->a.nalloc, sizeof(apr_table_entry_t), 0);
       memcpy(new->a.elts, t->a.elts, t->a.nelts * sizeof(apr_table_entry_t));
       new->a.nelts = t->a.nelts;
  +    memcpy(new->index_first, t->index_first, sizeof(int) * TABLE_HASH_SIZE);
  +    memcpy(new->index_last, t->index_last, sizeof(int) * TABLE_HASH_SIZE);
  +    new->index_initialized = t->index_initialized;
       return new;
   }
   
  +static void table_reindex(apr_table_t *t)
  +{
  +    int i;
  +    int hash;
  +    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
  +
  +    t->index_initialized = 0;
  +    for (i = 0; i < t->a.nelts; i++, next_elt++) {
  +        hash = TABLE_HASH(next_elt->key);
  +        t->index_last[hash] = i;
  +        if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
  +            t->index_first[hash] = i;
  +            TABLE_SET_INDEX_INITIALIZED(t, hash);
  +        }
  +    }
  +}
  +
   APR_DECLARE(void) apr_table_clear(apr_table_t *t)
   {
       t->a.nelts = 0;
  +    t->index_initialized = 0;
   }
   
   APR_DECLARE(const char *) apr_table_get(const apr_table_t *t, const char *key)
   {
  -    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
  -    apr_table_entry_t *end_elt = next_elt + t->a.nelts;
  +    apr_table_entry_t *next_elt;
  +    apr_table_entry_t *end_elt;
       apr_uint32_t checksum;
  +    int hash;
   
       if (key == NULL) {
   	return NULL;
       }
   
  +    hash = TABLE_HASH(key);
  +    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
  +        return NULL;
  +    }
       COMPUTE_KEY_CHECKSUM(key, checksum);
  -    for (; next_elt < end_elt; next_elt++) {
  +    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
  +    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
  +
  +    for (; next_elt <= end_elt; next_elt++) {
   	if ((checksum == next_elt->key_checksum) &&
               !strcasecmp(next_elt->key, key)) {
   	    return next_elt->val;
  @@ -440,21 +491,36 @@
   }
   
   APR_DECLARE(void) apr_table_set(apr_table_t *t, const char *key,
  -			       const char *val)
  +                                const char *val)
   {
  -    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
  -    apr_table_entry_t *end_elt = next_elt + t->a.nelts;
  -    apr_table_entry_t *dst_elt;
  +    apr_table_entry_t *next_elt;
  +    apr_table_entry_t *end_elt;
       apr_uint32_t checksum;
  +    int hash;
   
       COMPUTE_KEY_CHECKSUM(key, checksum);
  -    for (; next_elt < end_elt; next_elt++) {
  +    hash = TABLE_HASH(key);
  +    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
  +        t->index_first[hash] = t->a.nelts;
  +        TABLE_SET_INDEX_INITIALIZED(t, hash);
  +        goto add_new_elt;
  +    }
  +    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
  +    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
  +
  +    for (; next_elt <= end_elt; next_elt++) {
   	if ((checksum == next_elt->key_checksum) &&
               !strcasecmp(next_elt->key, key)) {
  +
  +            /* Found an existing entry with the same key, so overwrite it */
  +
  +            int must_reindex = 0;
  +            apr_table_entry_t *dst_elt = NULL;
  +
               next_elt->val = apr_pstrdup(t->a.pool, val);
  -            /* remove any other instances of this key */
  -            dst_elt = NULL;
  -            for (next_elt++; next_elt < end_elt; next_elt++) {
  +
  +            /* Remove any other instances of this key */
  +            for (next_elt++; next_elt <= end_elt; next_elt++) {
                   if ((checksum == next_elt->key_checksum) &&
                       !strcasecmp(next_elt->key, key)) {
                       t->a.nelts--;
  @@ -464,13 +530,32 @@
                   }
                   else if (dst_elt) {
                       *dst_elt++ = *next_elt;
  +                    must_reindex = 1;
                   }
  +            }
   
  +            /* If we've removed anything, shift over the remainder
  +             * of the table (note that the previous loop didn't
  +             * run to the end of the table, just to the last match
  +             * for the index)
  +             */
  +            if (dst_elt) {
  +                apr_table_entry_t *table_end =
  +                    ((apr_table_entry_t *) t->a.elts) + t->a.nelts;
  +                for (; next_elt < table_end; next_elt++) {
  +                    *dst_elt++ = *next_elt;
  +                }
  +                must_reindex = 1;
  +            }
  +            if (must_reindex) {
  +                table_reindex(t);
               }
               return;
           }
       }
   
  +add_new_elt:
  +    t->index_last[hash] = t->a.nelts;
       next_elt = (apr_table_entry_t *) table_push(t);
       next_elt->key = apr_pstrdup(t->a.pool, key);
       next_elt->val = apr_pstrdup(t->a.pool, val);
  @@ -478,21 +563,36 @@
   }
   
   APR_DECLARE(void) apr_table_setn(apr_table_t *t, const char *key,
  -				const char *val)
  +                                 const char *val)
   {
  -    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
  -    apr_table_entry_t *end_elt = next_elt + t->a.nelts;
  -    apr_table_entry_t *dst_elt;
  +    apr_table_entry_t *next_elt;
  +    apr_table_entry_t *end_elt;
       apr_uint32_t checksum;
  +    int hash;
   
       COMPUTE_KEY_CHECKSUM(key, checksum);
  -    for (; next_elt < end_elt; next_elt++) {
  +    hash = TABLE_HASH(key);
  +    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
  +        t->index_first[hash] = t->a.nelts;
  +        TABLE_SET_INDEX_INITIALIZED(t, hash);
  +        goto add_new_elt;
  +    }
  +    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
  +    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
  +
  +    for (; next_elt <= end_elt; next_elt++) {
   	if ((checksum == next_elt->key_checksum) &&
               !strcasecmp(next_elt->key, key)) {
  +
  +            /* Found an existing entry with the same key, so overwrite it */
  +
  +            int must_reindex = 0;
  +            apr_table_entry_t *dst_elt = NULL;
  +
               next_elt->val = (char *)val;
  -            /* remove any other instances of this key */
  -            dst_elt = NULL;
  -            for (next_elt++; next_elt < end_elt; next_elt++) {
  +
  +            /* Remove any other instances of this key */
  +            for (next_elt++; next_elt <= end_elt; next_elt++) {
                   if ((checksum == next_elt->key_checksum) &&
                       !strcasecmp(next_elt->key, key)) {
                       t->a.nelts--;
  @@ -502,13 +602,32 @@
                   }
                   else if (dst_elt) {
                       *dst_elt++ = *next_elt;
  +                    must_reindex = 1;
                   }
  +            }
   
  +            /* If we've removed anything, shift over the remainder
  +             * of the table (note that the previous loop didn't
  +             * run to the end of the table, just to the last match
  +             * for the index)
  +             */
  +            if (dst_elt) {
  +                apr_table_entry_t *table_end =
  +                    ((apr_table_entry_t *) t->a.elts) + t->a.nelts;
  +                for (; next_elt < table_end; next_elt++) {
  +                    *dst_elt++ = *next_elt;
  +                }
  +                must_reindex = 1;
  +            }
  +            if (must_reindex) {
  +                table_reindex(t);
               }
               return;
           }
       }
   
  +add_new_elt:
  +    t->index_last[hash] = t->a.nelts;
       next_elt = (apr_table_entry_t *) table_push(t);
       next_elt->key = (char *)key;
       next_elt->val = (char *)val;
  @@ -517,18 +636,33 @@
   
   APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
   {
  -    apr_table_entry_t *next_elt = (apr_table_entry_t *) t->a.elts;
  +    apr_table_entry_t *next_elt;
       apr_table_entry_t *end_elt = next_elt + t->a.nelts;
       apr_table_entry_t *dst_elt;
       apr_uint32_t checksum;
  +    int hash;
  +    int must_reindex;
   
  +    hash = TABLE_HASH(key);
  +    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
  +        return;
  +    }
       COMPUTE_KEY_CHECKSUM(key, checksum);
  -    for (; next_elt < end_elt; next_elt++) {
  +    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
  +    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
  +    must_reindex = 0;
  +    for (; next_elt <= end_elt; next_elt++) {
   	if ((checksum == next_elt->key_checksum) &&
               !strcasecmp(next_elt->key, key)) {
  +
  +            /* Found a match: remove this entry, plus any additional
  +             * matches for the same key that might follow
  +             */
  +            apr_table_entry_t *table_end = ((apr_table_entry_t *) t->a.elts) +
  +                t->a.nelts;
               t->a.nelts--;
               dst_elt = next_elt;
  -            for (next_elt++; next_elt < end_elt; next_elt++) {
  +            for (next_elt++; next_elt <= end_elt; next_elt++) {
                   if ((checksum == next_elt->key_checksum) &&
                       !strcasecmp(next_elt->key, key)) {
                       t->a.nelts--;
  @@ -537,38 +671,67 @@
                       *dst_elt++ = *next_elt;
                   }
               }
  +
  +            /* Shift over the remainder of the table (note that
  +             * the previous loop didn't run to the end of the table,
  +             * just to the last match for the index)
  +             */
  +            for (; next_elt < table_end; next_elt++) {
  +                *dst_elt++ = *next_elt;
  +            }
  +            must_reindex = 1;
               break;
           }
       }
  +    if (must_reindex) {
  +        table_reindex(t);
  +    }
   }
   
   APR_DECLARE(void) apr_table_merge(apr_table_t *t, const char *key,
   				 const char *val)
   {
  -    apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
  -    int i;
  +    apr_table_entry_t *next_elt;
  +    apr_table_entry_t *end_elt;
       apr_uint32_t checksum;
  +    int hash;
   
       COMPUTE_KEY_CHECKSUM(key, checksum);
  -    for (i = 0; i < t->a.nelts; ++i) {
  -	if ((checksum == elts[i].key_checksum) && !strcasecmp(elts[i].key, key)) {
  -	    elts[i].val = apr_pstrcat(t->a.pool, elts[i].val, ", ", val, NULL);
  -	    return;
  -	}
  +    hash = TABLE_HASH(key);
  +    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
  +        t->index_first[hash] = t->a.nelts;
  +        TABLE_SET_INDEX_INITIALIZED(t, hash);
  +        goto add_new_elt;
       }
  +    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];
  +    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
   
  -    elts = (apr_table_entry_t *) table_push(t);
  -    elts->key = apr_pstrdup(t->a.pool, key);
  -    elts->val = apr_pstrdup(t->a.pool, val);
  -    elts->key_checksum = checksum;
  +    for (; next_elt <= end_elt; next_elt++) {
  +	if ((checksum == next_elt->key_checksum) &&
  +            !strcasecmp(next_elt->key, key)) {
  +
  +            /* Found an existing entry with the same key, so merge with it */
  +	    next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
  +                                        val, NULL);
  +            return;
  +        }
  +    }
  +
  +add_new_elt:
  +    t->index_last[hash] = t->a.nelts;
  +    next_elt = (apr_table_entry_t *) table_push(t);
  +    next_elt->key = apr_pstrdup(t->a.pool, key);
  +    next_elt->val = apr_pstrdup(t->a.pool, val);
  +    next_elt->key_checksum = checksum;
   }
   
   APR_DECLARE(void) apr_table_mergen(apr_table_t *t, const char *key,
   				  const char *val)
   {
  -    apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
  -    int i;
  +    apr_table_entry_t *next_elt;
  +    apr_table_entry_t *end_elt;
       apr_uint32_t checksum;
  +    int hash;
   
   #ifdef POOL_DEBUG
       {
  @@ -584,17 +747,32 @@
   #endif
   
       COMPUTE_KEY_CHECKSUM(key, checksum);
  -    for (i = 0; i < t->a.nelts; ++i) {
  -	if ((checksum == elts[i].key_checksum) && !strcasecmp(elts[i].key, key)) {
  -	    elts[i].val = apr_pstrcat(t->a.pool, elts[i].val, ", ", val, NULL);
  -	    return;
  -	}
  +    hash = TABLE_HASH(key);
  +    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
  +        t->index_first[hash] = t->a.nelts;
  +        TABLE_SET_INDEX_INITIALIZED(t, hash);
  +        goto add_new_elt;
       }
  +    next_elt = ((apr_table_entry_t *) t->a.elts) + t->index_first[hash];;
  +    end_elt = ((apr_table_entry_t *) t->a.elts) + t->index_last[hash];
   
  -    elts = (apr_table_entry_t *) table_push(t);
  -    elts->key = (char *)key;
  -    elts->val = (char *)val;
  -    elts->key_checksum = checksum;
  +    for (; next_elt <= end_elt; next_elt++) {
  +	if ((checksum == next_elt->key_checksum) &&
  +            !strcasecmp(next_elt->key, key)) {
  +
  +            /* Found an existing entry with the same key, so merge with it */
  +	    next_elt->val = apr_pstrcat(t->a.pool, next_elt->val, ", ",
  +                                        val, NULL);
  +            return;
  +        }
  +    }
  +
  +add_new_elt:
  +    t->index_last[hash] = t->a.nelts;
  +    next_elt = (apr_table_entry_t *) table_push(t);
  +    next_elt->key = (char *)key;
  +    next_elt->val = (char *)val;
  +    next_elt->key_checksum = checksum;
   }
   
   APR_DECLARE(void) apr_table_add(apr_table_t *t, const char *key,
  @@ -602,7 +780,14 @@
   {
       apr_table_entry_t *elts;
       apr_uint32_t checksum;
  +    int hash;
   
  +    hash = TABLE_HASH(key);
  +    t->index_last[hash] = t->a.nelts;
  +    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
  +        t->index_first[hash] = t->a.nelts;
  +        TABLE_SET_INDEX_INITIALIZED(t, hash);
  +    }
       COMPUTE_KEY_CHECKSUM(key, checksum);
       elts = (apr_table_entry_t *) table_push(t);
       elts->key = apr_pstrdup(t->a.pool, key);
  @@ -615,6 +800,7 @@
   {
       apr_table_entry_t *elts;
       apr_uint32_t checksum;
  +    int hash;
   
   #ifdef POOL_DEBUG
       {
  @@ -629,6 +815,12 @@
       }
   #endif
   
  +    hash = TABLE_HASH(key);
  +    t->index_last[hash] = t->a.nelts;
  +    if (!TABLE_INDEX_IS_INITIALIZED(t, hash)) {
  +        t->index_first[hash] = t->a.nelts;
  +        TABLE_SET_INDEX_INITIALIZED(t, hash);
  +    }
       COMPUTE_KEY_CHECKSUM(key, checksum);
       elts = (apr_table_entry_t *) table_push(t);
       elts->key = (char *)key;
  @@ -664,7 +856,7 @@
       res->a.pool = p;
       copy_array_hdr_core(&res->a, &overlay->a);
       apr_array_cat(&res->a, &base->a);
  -
  +    table_reindex(res);
       return res;
   }
   
  @@ -1108,5 +1300,6 @@
               elt->key_checksum = cat_keys[i].elt->key_checksum;
           }
       }
  +    table_reindex(a);
   }
   
  
  
  
  1.310     +3 -0      apr/CHANGES
  
  Index: CHANGES
  ===================================================================
  RCS file: /home/cvs/apr/CHANGES,v
  retrieving revision 1.309
  retrieving revision 1.310
  diff -u -r1.309 -r1.310
  --- CHANGES	18 Jul 2002 12:58:53 -0000	1.309
  +++ CHANGES	20 Jul 2002 21:28:50 -0000	1.310
  @@ -1,5 +1,8 @@
   Changes with APR b1
   
  +  *) Added a lightweight internal index to apr_table_t to speed up
  +     table lookup operations  [Brian Pane]
  +
     *) initalize handle members to invalid before calling createprocess
        on win32 [Rob Saccoccio <robs@fastcgi.com>]
   
  
  
  

Mime
View raw message