From dev-return-4658-apmail-apr-dev-archive=apr.apache.org@apr.apache.org Thu Oct 11 22:15:53 2001 Return-Path: Delivered-To: apmail-apr-dev-archive@apr.apache.org Received: (qmail 86786 invoked by uid 500); 11 Oct 2001 22:15:53 -0000 Mailing-List: contact dev-help@apr.apache.org; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Delivered-To: mailing list dev@apr.apache.org Received: (qmail 86746 invoked from network); 11 Oct 2001 22:15:51 -0000 Message-ID: <3BC61932.5060901@xbc.nu> Date: Fri, 12 Oct 2001 00:12:02 +0200 From: Branko =?ISO-8859-2?Q?=C8ibej?= User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.3) Gecko/20010801 X-Accept-Language: sl, en-gb, en MIME-Version: 1.0 To: Sterling Hughes CC: Mladen Turk , "'Greg Stein'" , "'APR Dev List'" Subject: Re: [PATCH] apr_hash.c -- Make table ordered References: Content-Type: text/plain; charset=ISO-8859-2; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N Sterling Hughes wrote: >On Thu, 11 Oct 2001, Branko [ISO-8859-2] E`ibej wrote: > >>Mladen Turk wrote: >> >>>OK! >>>I'll propose the two things: >>>1. apr_btree to be able to do the range-based searches >>> >>Sounds useful. (I'd suggest implementing red-black trees, not AVL.) >> > why? avl is, too my knowledge, a faster algorithm for all intensive > purposes (faster insertion, equivalent lookup).. > Really? I thought it was just the opposite, at least in the amortized case. Well, never mind. >>>2. apr_shash to be able to sort the hash table. >>> >>Do you mean actually sort elements in the table by some key, or just >>make sure traversal is in the order of insertions? If the first, it's >>probably better to use a tree. If the second, then there should be a way >>to insert an element in a specific place in the traversal. >> > a hash is a random access data structure, i don't see any reason > that in-place insertions and deletions should be allowed, unless of course > you want to use it in place of a dlist. > What hw's proposing is *not* a hash table. He wants a structure with near-constant-time key-based lookup, and a well-defned traversal order. > which begs the question, why would you want to use a hash in place of a > dlist ;) > Whenever you want fast access to anything but the head or tail. -- Brane Čibej http://www.xbc.nu/brane/