Mailing-List: contact apreq-cvs-help@httpd.apache.org; run by ezmlm
Precedence: bulk
Reply-To: apreq-dev@httpd.apache.org
Date: 26 Apr 2003 20:55:35 -0000
Message-ID: <20030426205535.2181.qmail@icarus.apache.org>
From: joes@apache.org
To: httpd-apreq-2-cvs@apache.org
Subject: cvs commit: httpd-apreq-2/src apreq_tables.c apreq_tables.h

joes        2003/04/26 13:55:35

  Modified:    src      apreq_tables.c apreq_tables.h
  Log:
  Cleanup Red-Black tree deletion code.
  
  Revision  Changes    Path
  1.22      +22 -19    httpd-apreq-2/src/apreq_tables.c
  
  Index: apreq_tables.c
  ===================================================================
  RCS file: /home/cvs/httpd-apreq-2/src/apreq_tables.c,v
  retrieving revision 1.21
  retrieving revision 1.22
  diff -u -r1.21 -r1.22
  --- apreq_tables.c	25 Apr 2003 18:11:15 -0000	1.21
  +++ apreq_tables.c	26 Apr 2003 20:55:34 -0000	1.22
  @@ -120,7 +120,7 @@
       apr_array_header_t   a;
       int                  ghosts;
   
  -    apreq_value_copy_t  *copy;
  +    apreq_value_copy_t  *copy;  /* XXX: this may go away soon */
       apreq_value_merge_t *merge;
   
       int                  root[TABLE_HASH_SIZE];
  @@ -139,7 +139,7 @@
                                 (t)->ghosts--; } while (0)
   
   /* NEVER KILL AN ENTRY THAT'S STILL WITHIN THE FOREST */
  -#define IN_FOREST(t,idx) ( (idx)[o].tree[PARENT] >= 0 || ( !DEAD(idx) && \
  +#define IN_FOREST(t,idx) ( !DEAD(idx) && ( (idx)[o].tree[PARENT] >= 0 || \
                              (idx) == t->root[TABLE_HASH((idx)[o].key)] ) )
   
   /********************* (internal) tree operations ********************/
  @@ -289,12 +289,12 @@
   static void delete(apreq_table_entry_t *o, 
                      int *root,  const int idx, unsigned flags)
   {
  -    int x,y;
  +    int x;
   
       if (idx[o].tree[LEFT] < 0 || idx[o].tree[RIGHT] < 0) {
  -        x = y = 1 + idx[o].tree[RIGHT] + idx[o].tree[LEFT];
  -
  +        x = 1 + idx[o].tree[RIGHT] + idx[o].tree[LEFT];
   
  +        /* replace idx with x */
           if (idx[o].tree[PARENT] >= 0)
               idx[o].tree[PARENT][o].tree[LR(idx)] = x;
           else
  @@ -302,11 +302,13 @@
   
           if (x >= 0)
               x[o].tree[PARENT] = idx[o].tree[PARENT];
  -        else
  +
  +        if (idx[o].color == RED)
               return;
       }
       else {
  -        y = idx[o].tree[RIGHT];
  +        /* find idx's in-order successor & remove that instead */
  +        int y = idx[o].tree[RIGHT];
           while (y[o].tree[LEFT] >= 0)
               y = y[o].tree[LEFT];
   
  @@ -316,33 +318,35 @@
               y[o].tree[RIGHT] = idx[o].tree[RIGHT];
   
               if (x >= 0) {
  +                /* replace y with x */
                   x[o].tree[PARENT] = y[o].tree[PARENT];
                   y[o].tree[PARENT][o].tree[LR(y)] = x;
               }
           }
   
  +        /* copy idx's tree data into y ("RIGHT" is already done). */
           y[o].tree[LEFT] = idx[o].tree[LEFT];
           y[o].tree[PARENT] = idx[o].tree[PARENT];
  -        
  +
  +        /* replace idx with y */
           if (idx[o].tree[PARENT] >= 0)
               idx[o].tree[PARENT][o].tree[LR(idx)] = y;
           else
               *root = y;
  -    }
   
  -    if (y[o].color == RED) {
  -        y[o].color = idx[o].color;
  -        return;
  -    }
  +        if (y[o].color == RED) {
  +            y[o].color = idx[o].color;
  +            return;
  +        }
  +        else
  +            y[o].color = idx[o].color;
   
  +    }
   
       /* rebalance tree (standard double-black promotion) */
   
  -    x[o].color = idx[o].color;
  -
       if (flags & TF_BALANCE) {
  -        while (x != *root && x[o].color == BLACK) 
  -        {
  +        while (x != *root && x[o].color == BLACK) {
               /* x has a grandparent, parent & sibling */
               int parent = x[o].tree[PARENT];
               int grandparent = parent[o].tree[PARENT];
  @@ -376,10 +380,9 @@
                   rotate(o, root, parent, direction); /* promote x */
                   *root = x;
               }
  -
           }
  +        x[o].color = BLACK;
       }
  -    x[o].color = BLACK;
   }
   
   static int combine(apreq_table_entry_t *o, int a, 
  
  
  
  1.14      +3 -3      httpd-apreq-2/src/apreq_tables.h
  
  Index: apreq_tables.h
  ===================================================================
  RCS file: /home/cvs/httpd-apreq-2/src/apreq_tables.h,v
  retrieving revision 1.13
  retrieving revision 1.14
  diff -u -r1.13 -r1.14
  --- apreq_tables.h	25 Apr 2003 18:11:15 -0000	1.13
  +++ apreq_tables.h	26 Apr 2003 20:55:34 -0000	1.14
  @@ -242,7 +242,7 @@
    * Return the keys (i.e. value names) in an (char *) array,
    * preserving their original order.
    * @param t Table.
  - * @param p Pool used to allocate the resulting array struct.
  + * @param keys array used to store the result.
    */
   
   APREQ_DECLARE(apr_status_t) apreq_table_keys(const apreq_table_t *t,
  @@ -252,8 +252,8 @@
    * Return the (unique) values in an (apreq_value_t *) array,
    * preserving their original order.
    * @param t Table.
  - * @param p Pool used to allocate the resulting array struct.
  - * @remark With key == NULL, all values are returned.  However,
  + * @param values array used to sore the result..
  + * @remark With key == NULL, all table values are added.  However,
    * only the first value of a multivalued entry is used.
    */