apr-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bri...@apache.org
Subject cvs commit: apr/tables apr_tables.c
Date Fri, 05 Jul 2002 09:09:11 GMT
brianp      2002/07/05 02:09:11

  Modified:    tables   apr_tables.c
  Log:
  Optimized apr_table_unset(): the loop is now O(n) instead of
  O(n^2) in the worst case
  
  Revision  Changes    Path
  1.33      +14 -20    apr/tables/apr_tables.c
  
  Index: apr_tables.c
  ===================================================================
  RCS file: /home/cvs/apr/tables/apr_tables.c,v
  retrieving revision 1.32
  retrieving revision 1.33
  diff -u -r1.32 -r1.33
  --- apr_tables.c	5 Jul 2002 08:55:38 -0000	1.32
  +++ apr_tables.c	5 Jul 2002 09:09:11 -0000	1.33
  @@ -503,29 +503,23 @@
   
   APR_DECLARE(void) apr_table_unset(apr_table_t *t, const char *key)
   {
  -    register int i, j, k;
  -    apr_table_entry_t *elts = (apr_table_entry_t *) t->a.elts;
  +    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 = NULL;
       apr_uint32_t checksum;
   
       COMPUTE_KEY_CHECKSUM(key, checksum);
  -    for (i = 0; i < t->a.nelts; ) {
  -	if ((checksum == elts[i].key_checksum) && !strcasecmp(elts[i].key, key)) {
  -
  -	    /* found an element to skip over
  -	     * there are any number of ways to remove an element from
  -	     * a contiguous block of memory.  I've chosen one that
  -	     * doesn't do a memcpy/bcopy/array_delete, *shrug*...
  -	     */
  -	    for (j = i, k = i + 1; k < t->a.nelts; ++j, ++k) {
  -		elts[j].key = elts[k].key;
  -		elts[j].val = elts[k].val;
  -		elts[j].key_checksum = elts[k].key_checksum;
  -	    }
  -	    --t->a.nelts;
  -	}
  -	else {
  -	    ++i;
  -	}
  +    for (; next_elt < end_elt; next_elt++) {
  +	if ((checksum == next_elt->key_checksum) &&
  +            !strcasecmp(next_elt->key, key)) {
  +            t->a.nelts--;
  +            if (!dst_elt) {
  +                dst_elt = next_elt;
  +            }
  +        }
  +        else if (dst_elt) {
  +            *dst_elt++ = *next_elt;
  +        }
       }
   }
   
  
  
  

Mime
View raw message