Mailing-List: contact dev-help@httpd.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@httpd.apache.org
Date: Sat, 25 Jan 2003 14:06:26 -0800
From: Justin Erenkrantz <jerenkrantz@apache.org>
Reply-To: Justin Erenkrantz <jerenkrantz@apache.org>
To: dev@httpd.apache.org
Subject: Re: [patch] IndexResults
Message-ID: <2147483647.1043503586@[10.0.1.9]>
In-Reply-To: <20030125212304.GA2675@kerna.ie>
References: <20030125212304.GA2675@kerna.ie>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

--On Saturday, January 25, 2003 9:23 PM +0000 Francis Daly 
<deva@daoine.org> wrote:

> +/* res_info is used when merging res_list */
> +typedef struct res_info {
> +    int *range;
> +    apr_table_t *tab;
> +} res_info;

I think this is the wrong data structure to be using here.  A table 
doesn't make a whole lot of sense.  It's primarily used to deal with 
strings not integers.  The 'native' status and true/false conditions 
are best done with an integers for keys.  This patch does way too 
many unsafe things with strings for my liking.

You can key off the first digit (easy to get) and only have it 
restricted to that region of the number space (create buckets).  For 
series that cross sequences, you can split them up at 100-intervals. 
(I'd be content to lose one bucket so that we don't have to subtract 
the status on the request.)  Allows and denies are separated into two 
lists making it easy to keep the ordering (where allows are always 
before denies).

What I would envision would be something like this:

/* res_info is used when merging res_list */
typedef struct range_info {
   int start;
   int end;    /* start == end indicates a singleton. */
   struct range_info *next;
} range_info;

typedef struct range_list {
  range_info allow[10];
  range_info deny[10];
} range_list;

But, we ought to keep the comparisons as integers.  This would be 
reasonably efficient to compare (tables are awful) and is directly 
proportional to the number of IndexResults directives you have.  I 
think it's a fair tradeoff with a much cleaner implementation.

The comparison would simply look like (pseudocode):

current = ranges[r->status % 100];
while (current) {
  if (r->status >= current.start && r->status <= current.end) {
    return 1;
  }
  current = current.next;
}

That's way more efficient than doing a sprintf.  Walk it twice for 
denials and approvals.

What do you think?  -- justin