This is the perhaps the biggest, boldest, most daring change I've ever committed to trunk. Forgive me in advance any disruption this may cause, and please, report any problems via the bugtracker. The upside is that this can speed up large dialplans by 20 times (or more). Context, extension, and priority matching are all fairly constant-time searches. I introduce here my hashtables (hashtabs), and a regression for them. I would have used the ast_obj2 tables, but mine are resizeable, and don't need the object destruction capability. The hashtab stuff is well tested and stable. I introduce a data structure, a trie, for extension pattern matching, in which knowledge of all patterns is accumulated, and all matches can be found via a single traversal of the tree. This is per-context. The trie is formed on the first lookup attempt, and stored in the context for future lookups. Destruction routines are in place for hashtabs and the pattern match trie. You can see the contents of the pattern match trie by using the 'dialplan show' cli command when 'core set debug' has been done to put it in debug mode. The pattern tree traversal only traverses those parts of the tree that are interesting. It uses a scoreboard sort of approach to find the best match. The speed of the traversal is more a function of the length of the pattern than the number of patterns in the tree. The tree also contains the CID matching patterns. See the source code comments for details on how everything works. I believe the approach general enough that any issues that might come up involving fine points in the pattern matching algorithm, can be solved by just tweaking things. We shall see. The current pattern matcher is fairly involved, and replicating every nuance of it is difficult. If you find and report problems, I will try to resolve than as quickly as I can. The trie and hashtabs are added to the existing context and exten structs, and none of the old machinery has been removed for the sake of the multitude of functions that use them. In the future, we can (maybe) weed out the linked lists and save some space.

git-svn-id: https://origsvn.digium.com/svn/asterisk/trunk@89129 65c4cc65-6c06-0410-ace0-fbb531ad65f3

9 files changed, 2299 insertions, 55 deletions

diff --git a/include/asterisk/hashtab.h b/include/asterisk/hashtab.h
new file mode 100644
index 000000000..f40324b39
--- /dev/null
+++ b/include/asterisk/hashtab.h
@@ -0,0 +1,257 @@
+/*
+ * Asterisk -- An open source telephony toolkit.
+ *
+ * Copyright (C) 2006, Digium, Inc.
+ *
+ * Steve Murphy <murf@digium.com>
+ *
+ * See http://www.asterisk.org for more information about
+ * the Asterisk project. Please do not directly contact
+ * any of the maintainers of this project for assistance;
+ * the project provides a web site, mailing lists and IRC
+ * channels for your use.
+ *
+ * This program is free software, distributed under the terms of
+ * the GNU General Public License Version 2. See the LICENSE file
+ * at the top of the source tree.
+ */
+#ifndef _ASTERISK_HASHTAB_H_
+#define _ASTERISK_HASHTAB_H_
+#define __USE_UNIX98 1          /* to get the MUTEX_RECURSIVE stuff */
+
+/* generic (perhaps overly so) hashtable implementation */
+
+/* notes:
+
+A hash table is a structure that allows for an exact-match search
+in O(1) (or close to that) time.
+
+The method: given: a set of {key,val} pairs. (at a minimum).
+            given: a hash function, which, given a key,
+            will return an integer. Ideally, each key in the
+            set will have its own unique associated hash value.
+			This hash number will index into an array. "buckets"
+            are what the elements of this array are called. To
+            handle possible collisions in hash values, buckets can form a list.
+
+The key for a value must be contained in the value, or we won't
+be able to find it in the bucket list.
+
+This implementation is pretty generic, because:
+ 1. The value and key are expected to be in a structure
+    (along with other data, perhaps) and it's address is a "void *".
+ 2. The pointer to a compare function must be passed in at the
+    time of creation, and is stored in the hashtable.
+ 3. The pointer to a resize function, which returns 1 if the
+    hash table is to be grown. A default routine is provided
+    if the pointer is NULL, and uses the java hashtable metric
+    of a 75% load factor.
+ 4. The pointer to a "new size" function, which returns a preferable
+    new size for the hash table bucket array. By default, a function
+    is supplied which roughly doubles the size of the array, is provided.
+    This size should ideally be a prime number.
+ 5. The hashing function pointer must also be supplied. This function
+    must be written by the user to access the keys in the objects being
+    stored. Some helper functions that use a simple "mult by prime, add
+    the next char", sort of string hash, or a simple modulus of the hash
+    table size for ints, is provided; the user can use these simple
+    algorithms to generate a hash, or implement any other algorithms they
+    wish.
+ 6. Recently updated the hash routines to use Doubly-linked lists for buckets,
+    and added a doubly-linked list that threads thru every bucket in the table.
+    The list of all buckets is on the HashTab struct. The Traversal was modified
+    to go thru this list instead of searching the bucket array for buckets.
+    This also should make it safe to remove a bucket during the traversal.
+    Removal and destruction routines will work faster.
+*/
+
+struct ast_hashtab_bucket
+{
+	const void *object;                    /* whatever it is we are storing in this table */
+	struct ast_hashtab_bucket *next;       /* a DLL of buckets in hash collision */
+	struct ast_hashtab_bucket *prev;       /* a DLL of buckets in hash collision */
+	struct ast_hashtab_bucket *tnext;      /* a DLL of all the hash buckets for traversal */
+	struct ast_hashtab_bucket *tprev;      /* a DLL of all the hash buckets for traversal */
+};
+
+struct ast_hashtab
+{
+	struct ast_hashtab_bucket **array;
+	struct ast_hashtab_bucket *tlist; /* the head of a DLList of all the hashbuckets in the table (for traversal). */
+	
+	int (*compare) (const void *a, const void *b);            /* a ptr to func that returns int, and take two void* ptrs, compares them, 
+													 rets -1 if a < b; rets 0 if a==b; rets 1 if a>b */
+	int (*newsize) (struct ast_hashtab *tab);     /* a ptr to func that returns int, a new size for hash tab, based on curr_size */
+	int (*resize) (struct ast_hashtab *tab);      /* a function to decide whether this hashtable should be resized now */
+	unsigned int (*hash) (const void *obj);         /* a hash func ptr for this table. Given a raw ptr to an obj, 
+													 it calcs a hash.*/
+	int hash_tab_size;                            /* the size of the bucket array */
+	int hash_tab_elements;                        /* the number of objects currently stored in the table */
+	int largest_bucket_size;                      /* a stat on the health of the table */
+	int resize_count;                             /* a count of the number of times this table has been
+													 resized */
+	int do_locking;                               /* if 1, use locks to guarantee safety of insertions/deletions */
+	/* this spot reserved for the proper lock storage */
+	ast_rwlock_t lock;                                /* is this as good as it sounds? */
+};
+
+struct ast_hashtab_iter              /* an iterator for traversing the buckets */
+{
+	struct ast_hashtab *tab;
+	struct ast_hashtab_bucket *next;
+};
+
+
+/* some standard, default routines for general use */
+
+int isPrime(int num); /* this one is handy for sizing the hash table, tells if num is prime or not */
+
+int ast_hashtab_compare_strings(const void *a, const void *b); /* assumes a and b are char * and returns 0 if they match */
+
+
+int ast_hashtab_compare_strings_nocase(const void *a, const void *b); /* assumes a & b are strings, returns 0 if they match (strcasecmp) */
+
+
+int ast_hashtab_compare_ints(const void *a, const void *b);  /* assumes a & b are int *, returns a != b */
+
+
+int ast_hashtab_compare_shorts(const void *a, const void *b);  /* assumes a & b are short *, returns a != b */
+
+
+int ast_hashtab_resize_java(struct ast_hashtab *tab); /* returns 1 if the table is 75% full or more */
+
+
+int ast_hashtab_resize_tight(struct ast_hashtab *tab); /* not yet specified; probably will return 1 if table is 100% full */
+
+
+int ast_hashtab_resize_none(struct ast_hashtab *tab); /* no resizing; always return 0 */
+
+
+int ast_hashtab_newsize_java(struct ast_hashtab *tab);  /* returns a prime number roughly 2x the current table size */
+
+
+int ast_hashtab_newsize_tight(struct ast_hashtab *tab); /* not yet specified, probably will return 1.5x the current table size */
+
+
+int ast_hashtab_newsize_none(struct ast_hashtab *tab); /* always return current size -- no resizing */
+
+
+unsigned int ast_hashtab_hash_string(const void *obj); /* hashes a string to a number, mod is applied so it in the range 0 to mod-1 */
+
+
+unsigned int ast_hashtab_hash_string_nocase(const void *obj);  /* upcases each char before using them for a hash */
+
+
+unsigned int ast_hashtab_hash_string_sax(const void *obj); /* from Josh */
+
+
+unsigned int ast_hashtab_hash_int(const int num);  /* right now, both these funcs are just result = num%modulus; */
+
+
+unsigned int ast_hashtab_hash_short(const short num);
+
+
+struct ast_hashtab * ast_hashtab_create(int initial_buckets,
+					int (*compare)(const void *a, const void *b),        /* a func to compare two elements in the hash -- cannot be null  */
+					int (*resize)(struct ast_hashtab *),     /* a func to decide if the table needs to be resized, 
+										a NULL ptr here will cause a default to be used */
+					int (*newsize)(struct ast_hashtab *tab), /* a ptr to func that returns a new size of the array. 
+										A NULL will cause a default to be used */
+					unsigned int (*hash)(const void *obj),     /* a func to do the hashing */
+					int do_locking );                        /* use locks to guarantee safety of iterators/insertion/deletion */
+
+
+	/* this func will free the hash table and all its memory. It
+	   doesn't touch the objects stored in it */
+void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj));
+
+
+	/* normally, you'd insert "safely" by checking to see if the element is
+	   already there; in this case, you must already have checked. If an element
+	   is already in the hashtable, that matches this one, most likely this one
+	   will be found first. */
+	/* will force a resize if the resize func returns 1 */
+	/* returns 1 on success, 0 if there's a problem */
+int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj);
+
+	/* same as the above, but h is the hash index; won't hash to find the index */
+int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, int h);
+
+
+	/* check to see if the element is already there; insert only if
+	   it is not there.*/
+	/* will force a resize if the resize func returns 1 */
+	/* returns 1 on success, 0 if there's a problem, or it's already there. */
+int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj);
+
+
+	/* lookup this object in the hash table. return a ptr if found, or NULL if not */
+void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj);
+
+    /* if you know the hash val for the object, then use this and avoid the recalc
+	   of the hash (the modulus (table_size) is not applied) */
+void * ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval);
+
+	/* same as the above lookup, but sets h to the key hash value if the lookup fails -- this has the modulus 
+       applied, and will not be useful for long term storage if the table is resizable */
+void * ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, int *h);
+
+	/* returns key stats for the table */
+void ast_hashtab_get_stats( struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets);
+
+	/* this function returns the number of elements stored in the hashtab */
+int  ast_hashtab_size( struct ast_hashtab *tab);
+
+	/* this function returns the size of the bucket array in the hashtab */
+int  ast_hashtab_capacity( struct ast_hashtab *tab);
+
+    /* this function will return a copy of the table */
+struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj));
+
+	/* returns an iterator */
+struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab);
+
+	/* end the traversal, free the iterator, unlock if necc. */
+void ast_hashtab_end_traversal(struct ast_hashtab_iter *it);
+
+	/* returns the next object in the list, advances iter one step, returns null on end of traversal */
+void *ast_hashtab_next(struct ast_hashtab_iter *it);
+
+
+	/* looks up the object; removes the corresponding bucket */
+void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj);
+
+
+	/* looks up the object by hash and then comparing pts in bucket list instead of
+	   calling the compare routine; removes the bucket */
+void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj);
+
+/* ------------------ */
+/* for lock-enabled traversals with ability to remove an object during the traversal*/
+/* ------------------ */
+
+	/* returns an iterator */
+struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab);
+
+	/* looks up the object; removes the corresponding bucket */
+void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj);
+
+
+	/* looks up the object by hash and then comparing pts in bucket list instead of
+	   calling the compare routine; removes the bucket */
+void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj);
+
+/* ------------------ */
+/* ------------------ */
+
+/* user-controlled hashtab locking. Create a hashtab without locking, then call the
+   following locking routines yourself to lock the table between threads. */
+
+void ast_hashtab_initlock(struct ast_hashtab *tab); /* call this after you create the table to init the lock */
+void ast_hashtab_wrlock(struct ast_hashtab *tab); /* request a write-lock on the  table. */
+void ast_hashtab_rdlock(struct ast_hashtab *tab); /* request a read-lock on the table-- don't change anything! */
+void ast_hashtab_unlock(struct ast_hashtab *tab);      /* release a read- or write- lock. */
+void ast_hashtab_destroylock(struct ast_hashtab *tab); /* call this before you destroy the table. */
+
+
+#endif
diff --git a/main/Makefile b/main/Makefile
index 3f1815907..25fb79ab5 100644
--- a/main/Makefile
+++ b/main/Makefile
@@ -27,7 +27,7 @@ OBJS=	io.o sched.o logger.o frame.o loader.o config.o channel.o \
 	netsock.o slinfactory.o ast_expr2.o ast_expr2f.o \
 	cryptostub.o sha1.o http.o fixedjitterbuf.o abstract_jb.o \
 	strcompat.o threadstorage.o dial.o event.o adsistub.o audiohook.o \
-	astobj2.o
+	astobj2.o hashtab.o
 
 # we need to link in the objects statically, not as a library, because
 # otherwise modules will not have them available if none of the static
diff --git a/main/config.c b/main/config.c
index 59b1840fd..614c6c9e7 100644
--- a/main/config.c
+++ b/main/config.c
@@ -220,7 +220,7 @@ struct ast_category_template_instance {
 
 struct ast_category {
 	char name[80];
-	int ignored;			/*!< do not let user of the config see this category */
+	int ignored;			/*!< do not let user of the config see this category -- set by (!) after the category decl; a template */
 	int include_level;
 	char *file;	           /*!< the file name from whence this declaration was read */
 	int lineno;
diff --git a/main/hashtab.c b/main/hashtab.c
new file mode 100644
index 000000000..7c4adf886
--- /dev/null
+++ b/main/hashtab.c
@@ -0,0 +1,835 @@
+/*
+ * Asterisk -- An open source telephony toolkit.
+ *
+ * Copyright (C) 2007, Digium, Inc.
+ *
+ * Steve Murphy <murf@digium.com>
+ *
+ * See http://www.asterisk.org for more information about
+ * the Asterisk project. Please do not directly contact
+ * any of the maintainers of this project for assistance;
+ * the project provides a web site, mailing lists and IRC
+ * channels for your use.
+ *
+ * This program is free software, distributed under the terms of
+ * the GNU General Public License Version 2. See the LICENSE file
+ * at the top of the source tree.
+ */
+/*! \file
+ *
+ *  \brief code to implement generic hash tables
+ *
+ *  \author Steve Murphy <murf@digium.com>
+ */
+
+#include "asterisk.h"
+
+ASTERISK_FILE_VERSION(__FILE__, "$Revision")
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <string.h>
+#include <ctype.h>
+#include <errno.h>
+#include <stddef.h>
+
+#include "asterisk/lock.h"
+#include "asterisk/frame.h"
+#include "asterisk/logger.h"
+#include "asterisk/options.h"
+#include "asterisk/channel.h"
+#include "asterisk/cli.h"
+#include "asterisk/term.h"
+#include "asterisk/utils.h"
+#include "asterisk/threadstorage.h"
+#include "asterisk/linkedlists.h"
+#include "asterisk/hashtab.h"
+
+static void ast_hashtab_resize( struct ast_hashtab *tab);
+
+/* some standard, default routines for general use */
+
+int ast_hashtab_compare_strings(const void *a, const void *b)
+{
+	return strcmp((char*)a,(char*)b);
+}
+
+int ast_hashtab_compare_strings_nocase(const void *a, const void *b)
+{
+	return strcasecmp((const char*)a,(const char*)b);
+}
+
+int ast_hashtab_compare_ints(const void *a, const void *b)
+{
+	int ai = *((int*)a);
+	int bi = *((int*)b);
+	if (ai < bi)
+		return -1;
+	else if (ai==bi)
+		return 0;
+	else
+		return 1;
+}
+
+int ast_hashtab_compare_shorts(const void *a, const void *b)
+{
+	short as = *((short*)a);
+	short bs = *((short*)b);
+	if (as < bs)
+		return -1;
+	else if (as==bs)
+		return 0;
+	else
+		return 1;
+}
+
+int ast_hashtab_resize_java(struct ast_hashtab *tab)
+{
+	double loadfactor = (double)tab->hash_tab_elements / (double)tab->hash_tab_size;
+	if (loadfactor > 0.75)
+		return 1;
+	return 0;
+}
+
+int ast_hashtab_resize_tight(struct ast_hashtab *tab)
+{
+	
+	if (tab->hash_tab_elements > tab->hash_tab_size) /* this is quicker than division */
+		return 1;
+	return 0;
+}
+
+int ast_hashtab_resize_none(struct ast_hashtab *tab) /* always return 0 -- no resizing */
+{
+	return 0;
+}
+
+
+int isPrime(int num)
+{
+	int tnum,limit;
+	    
+	if ((num & 0x1) == 0) /* even number -- not prime */
+		return 0;
+		    
+    	/* Loop through ODD numbers starting with 3 */
+
+	tnum = 3;
+	limit = num;
+	while (tnum < limit)
+	{
+		if ((num%tnum) == 0) {
+			return 0;
+		}
+		/* really, we only need to check sqrt(num) numbers */
+		limit = num / tnum;
+		/* we only check odd numbers */
+		tnum = tnum+2;
+	}
+	/* if we made it thru the loop, the number is a prime */
+	return 1;
+}
+
+int ast_hashtab_newsize_java(struct ast_hashtab *tab)
+{
+	int i = (tab->hash_tab_size<<1); /* multiply by two */
+	while (!isPrime(i))
+		i++;
+	return i;
+}
+
+int ast_hashtab_newsize_tight(struct ast_hashtab *tab)
+{
+	int x = (tab->hash_tab_size<<1);
+	int i = (tab->hash_tab_size+x);
+	while (!isPrime(i))
+		i++;
+	return i;
+}
+
+int ast_hashtab_newsize_none(struct ast_hashtab *tab) /* always return current size -- no resizing */
+{
+	return tab->hash_tab_size;
+}
+
+unsigned int ast_hashtab_hash_string(const void *obj)
+{
+	unsigned char *str = (unsigned char*)obj;
+	unsigned int total;
+
+	for (total=0; *str; str++)
+	{
+		unsigned int tmp = total;
+		total <<= 1; /* multiply by 2 */
+		total += tmp; /* multiply by 3 */
+		total <<= 2; /* multiply by 12 */
+		total += tmp; /* multiply by 13 */
+		
+		total += ((unsigned int)(*str));
+	}
+	return total;
+}
+
+unsigned int ast_hashtab_hash_string_sax(const void *obj) /* from Josh */
+{
+	unsigned char *str = (unsigned char*)obj;
+	unsigned int total = 0, c = 0;
+
+	while ((c = *str++))
+		total ^= ( total << 5 ) + ( total >> 2 ) + ( total << 10) + c;
+
+	return total;
+}
+
+unsigned int ast_hashtab_hash_string_nocase(const void *obj)
+{
+	unsigned char *str = (unsigned char*)obj;
+	unsigned int total;
+
+	for (total=0; *str; str++)
+	{
+		unsigned int tmp = total;
+		unsigned int charval = toupper(*str);
+
+		/* hopefully, the following is faster than multiplication by 7 */
+		/* why do I go to this bother? A good compiler will do this 
+		   anyway, if I say total *= 13 */
+		/* BTW, tried *= 7, and it doesn't do as well in spreading things around! */
+		total <<= 1; /* multiply by 2 */
+		total += tmp; /* multiply by 3 */
+		total <<= 2; /* multiply by 12 */
+		total += tmp; /* multiply by 13 */
+		
+		total += (charval);
+	}
+	return total;
+}
+
+unsigned int ast_hashtab_hash_int(const int x)
+{
+	return x;
+}
+
+unsigned int ast_hashtab_hash_short(const short x)
+{
+	/* hmmmm.... modulus is best < 65535 !! */
+	return x;
+}
+
+struct ast_hashtab * ast_hashtab_create(int initial_buckets,
+										int (*compare)(const void *a, const void *b), /* a func to compare two elements in the hash -- cannot be null  */
+										int (*resize)(struct ast_hashtab *), /* a func to decide if the table needs to be resized, a NULL ptr here will cause a default to be used */
+										int (*newsize)(struct ast_hashtab *tab), /* a ptr to func that returns a new size of the array. A NULL will cause a default to be used */
+										unsigned int (*hash)(const void *obj), /* a func to do the hashing */
+										int do_locking ) /* use locks to guarantee safety of iterators/insertion/deletion -- real simpleminded right now */
+{
+	struct ast_hashtab *ht = ast_calloc(1,sizeof(struct ast_hashtab));
+	while (!isPrime(initial_buckets)) /* make sure this is prime */
+		initial_buckets++;
+	ht->array = ast_calloc(initial_buckets,sizeof(struct ast_hashtab_bucket*));
+	ht->hash_tab_size = initial_buckets;
+	ht->compare = compare;
+	ht->resize = resize;
+	ht->newsize = newsize;
+	ht->hash = hash;
+	ht->do_locking = do_locking;
+	if (do_locking)
+		ast_rwlock_init(&ht->lock);
+	if (!ht->resize)
+		ht->resize = ast_hashtab_resize_java;
+	if (!ht->newsize)
+		ht->newsize = ast_hashtab_newsize_java;
+	return ht;
+}
+
+struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj))
+{
+	struct ast_hashtab *ht = ast_calloc(1,sizeof(struct ast_hashtab));
+	int i;
+	
+	ht->array = ast_calloc(tab->hash_tab_size,sizeof(struct ast_hashtab_bucket*));
+	ht->hash_tab_size = tab->hash_tab_size;
+	ht->compare = tab->compare;
+	ht->resize = tab->resize;
+	ht->newsize = tab->newsize;
+	ht->hash = tab->hash;
+	ht->do_locking = tab->do_locking;
+	if (ht->do_locking)
+		ast_rwlock_init(&ht->lock);
+	/* now, dup the objects in the buckets and get them into the table */
+	/* the fast way is to use the existing array index, and not have to hash
+	   the objects again */
+	for (i=0;i<ht->hash_tab_size;i++)
+	{
+		struct ast_hashtab_bucket *b = tab->array[i];
+		while( b )
+		{
+			void *newobj = (*obj_dup_func)(b->object);
+			if (newobj) {
+				ast_hashtab_insert_immediate_bucket(ht, newobj, i);
+			}
+			b = b->next;
+		}
+	}
+	return ht;
+}
+
+static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
+{
+	/* item had better be in the list! or suffer the weirdness that occurs, later! */
+	if (*head == item) { /* first item in the list */
+		*head = item->tnext;
+		if (item->tnext)
+			item->tnext->tprev = NULL;
+	} else {
+		/* short circuit stuff */
+		item->tprev->tnext = item->tnext;
+		if (item->tnext)
+			item->tnext->tprev = item->tprev;
+	}
+}
+
+static void tlist_add_head(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
+{
+	if (*head) {
+		item->tnext = *head;
+		item->tprev = NULL;
+		(*head)->tprev = item;
+		*head = item;
+	} else {
+		/* the list is empty */
+		*head = item;
+		item->tprev = NULL;
+		item->tnext = NULL;
+	}
+}
+
+/* user-controlled hashtab locking. Create a hashtab without locking, then call the
+   following locking routines yourself to lock the table between threads. */
+
+void ast_hashtab_wrlock(struct ast_hashtab *tab)
+{
+	ast_rwlock_wrlock(&tab->lock);
+}
+
+void ast_hashtab_rdlock(struct ast_hashtab *tab)
+{
+	ast_rwlock_rdlock(&tab->lock);
+}
+
+void ast_hashtab_initlock(struct ast_hashtab *tab)
+{
+	ast_rwlock_init(&tab->lock);
+}
+
+void ast_hashtab_destroylock(struct ast_hashtab *tab)
+{
+	ast_rwlock_destroy(&tab->lock);
+}
+
+void ast_hashtab_unlock(struct ast_hashtab *tab)
+{
+	ast_rwlock_unlock(&tab->lock);
+}
+
+
+void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj))
+{
+	/* this func will free the hash table and all its memory. It
+	   doesn't touch the objects stored in it */
+	if (tab) {
+		
+		if (tab->do_locking)
+			ast_rwlock_wrlock(&tab->lock);
+
+		if (tab->array) {
+			/* go thru and destroy the buckets */
+			struct ast_hashtab_bucket *t;
+			int i;
+			
+			while (tab->tlist) {
+				t = tab->tlist;
+				if (t->object && objdestroyfunc) {
+					(*objdestroyfunc)((void*)t->object); /* I cast this because I'm not going to MOD it, I'm going to DESTROY it */
+				}
+				
+				tlist_del_item(&(tab->tlist), tab->tlist);
+				free(t);
+			}
+			
+			for (i=0;i<tab->hash_tab_size;i++) { 
+				tab->array[i] = NULL; /* not totally necc., but best to destroy old ptrs */
+			}
+			
+			free(tab->array);
+		}
+		if (tab->do_locking) {
+			ast_rwlock_unlock(&tab->lock);
+			ast_rwlock_destroy(&tab->lock);
+		}
+		free(tab);
+	}
+}
+
+int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj)
+{
+	/* normally, you'd insert "safely" by checking to see if the element is
+	   already there; in this case, you must already have checked. If an element
+	   is already in the hashtable, that matches this one, most likely this one
+	   will be found first, but.... */
+
+	/* will force a resize if the resize func returns 1 */
+	/* returns 1 on success, 0 if there's a problem */
+	unsigned int h;
+	int c;
+	struct ast_hashtab_bucket *b;
+	
+	if (!tab) {
+		return 0;
+	}
+	if (!obj) {
+		return 0;
+	}
+	if (tab->do_locking)
+		ast_rwlock_wrlock(&tab->lock);
+	h = (*tab->hash)(obj) % tab->hash_tab_size;
+	for (c=0,b=tab->array[h];b;b=b->next) {
+		c++;
+	}
+	if (c+1 > tab->largest_bucket_size)
+		tab->largest_bucket_size = c+1;
+	b = ast_malloc(sizeof(struct ast_hashtab_bucket));
+	b->object = obj;
+	b->next = tab->array[h];
+	b->prev = NULL;
+	if (b->next)
+		b->next->prev = b;
+	tlist_add_head(&(tab->tlist),b);
+	
+	tab->array[h] = b;
+	tab->hash_tab_elements++;
+	if ((*tab->resize)(tab))
+		ast_hashtab_resize(tab);
+	if (tab->do_locking)
+		ast_rwlock_unlock(&tab->lock);
+	return 1;
+}
+
+int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, int h)
+{
+	/* normally, you'd insert "safely" by checking to see if the element is
+	   already there; in this case, you must already have checked. If an element
+	   is already in the hashtable, that matches this one, most likely this one
+	   will be found first, but.... */
+
+	/* will force a resize if the resize func returns 1 */
+	/* returns 1 on success, 0 if there's a problem */
+	int c;
+	struct ast_hashtab_bucket *b;
+	
+	if (!tab || !obj)
+		return 0;
+	
+	for (c=0,b=tab->array[h];b;b=b->next) {
+		c++;
+	}
+	if (c+1 > tab->largest_bucket_size)
+		tab->largest_bucket_size = c+1;
+	b = ast_malloc(sizeof(struct ast_hashtab_bucket));
+	b->object = obj;
+	b->next = tab->array[h];
+	b->prev = NULL;
+	tab->array[h] = b;
+	if (b->next)
+		b->next->prev = b;
+	tlist_add_head(&(tab->tlist), b);
+	tab->hash_tab_elements++;
+	if ((*tab->resize)(tab))
+		ast_hashtab_resize(tab);
+	return 1;
+}
+
+int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj)
+{
+	/* check to see if the element is already there; insert only if
+	   it is not there. */
+	/* will force a resize if the resize func returns 1 */
+	/* returns 1 on success, 0 if there's a problem, or it's already there. */
+	int bucket = 0;
+	if (tab->do_locking)
+		ast_rwlock_wrlock(&tab->lock);
+
+	if (ast_hashtab_lookup_bucket(tab,obj,&bucket) == 0)
+	{
+		int ret2 = ast_hashtab_insert_immediate_bucket(tab,obj,bucket);
+		if (tab->do_locking)
+			ast_rwlock_unlock(&tab->lock);
+		
+		return ret2;
+	}
+	if (tab->do_locking)
+		ast_rwlock_unlock(&tab->lock);
+	return 0;
+}
+
+void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj)
+{
+	/* lookup this object in the hash table. return a ptr if found, or NULL if not */
+	unsigned int h;
+	const void *ret;
+	struct ast_hashtab_bucket *b;
+	if (!tab || !obj)
+		return 0;
+	
+	if (tab->do_locking)
+		ast_rwlock_rdlock(&tab->lock);
+	h = (*tab->hash)(obj) % tab->hash_tab_size;
+	for (b=tab->array[h]; b; b=b->next) {
+		if ((*tab->compare)(obj,b->object) == 0) {
+			ret = b->object;
+			if (tab->do_locking)
+				ast_rwlock_unlock(&tab->lock);
+			return (void*)ret; /* I can't touch obj in this func, but the outside world is welcome to */
+		}
+	}
+	if (tab->do_locking)
+		ast_rwlock_unlock(&tab->lock);
+
+	return 0;
+}
+
+void * ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval)
+{
+	/* lookup this object in the hash table. return a ptr if found, or NULL if not */
+	unsigned int h;
+	const void *ret;
+	struct ast_hashtab_bucket *b;
+	if (!tab || !obj)
+		return 0;
+	
+	if (tab->do_locking)
+		ast_rwlock_rdlock(&tab->lock);
+	h = hashval % tab->hash_tab_size;
+	for (b=tab->array[h]; b; b=b->next) {
+		if ((*tab->compare)(obj,b->object) == 0) {
+			ret = b->object;
+			if (tab->do_locking)
+				ast_rwlock_unlock(&tab->lock);
+			return (void*)ret; /* I can't touch obj in this func, but the outside world is welcome to */
+		}
+	}
+	if (tab->do_locking)
+		ast_rwlock_unlock(&tab->lock);
+
+	return 0;
+}
+
+void * ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, int *bucket)
+{
+	/* lookup this object in the hash table. return a ptr if found, or NULL if not */
+	unsigned int h;
+	struct ast_hashtab_bucket *b;
+	if (!tab || !obj)
+		return 0;
+	
+	h = (*tab->hash)(obj) % tab->hash_tab_size;
+	for (b=tab->array[h]; b; b=b->next) {
+		if ((*tab->compare)(obj,b->object) == 0) {
+			return (void*)b->object; /* I can't touch obj in this func, but the outside world is welcome to */
+		}
+	}
+	*bucket = h;
+	return 0;
+}
+
+void ast_hashtab_get_stats( struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets)
+{
+	/* returns key stats for the table */
+	if (tab->do_locking)
+		ast_rwlock_rdlock(&tab->lock);
+	*biggest_bucket_size = tab->largest_bucket_size;
+	*resize_count = tab->resize_count;
+	*num_objects = tab->hash_tab_elements;
+	*num_buckets = tab->hash_tab_size;
+	if (tab->do_locking)
+		ast_rwlock_unlock(&tab->lock);
+}
+
+	/* this function returns the number of elements stored in the hashtab */
+int  ast_hashtab_size( struct ast_hashtab *tab)
+{
+	return tab->hash_tab_elements;
+}
+
+	/* this function returns the size of the bucket array in the hashtab */
+int  ast_hashtab_capacity( struct ast_hashtab *tab)
+{
+	return tab->hash_tab_size;
+}
+
+
+
+/* the insert operation calls this, and is wrlock'd when it does. */
+/* if you want to call it, you should set the wrlock yourself */
+
+
+static void ast_hashtab_resize( struct ast_hashtab *tab)
+{
+	/* this function is called either internally, when the resize func returns 1, or
+	   externally by the user to force a resize of the hash table */
+	int newsize = (*tab->newsize)(tab), i, c;
+	unsigned int h;
+	struct ast_hashtab_bucket *b,*bn;
+	
+	/* Since we keep a DLL of all the buckets in tlist,
+	   all we have to do is free the array, malloc a new one,
+	   and then go thru the tlist array and reassign them into 
+	   the bucket arrayj.
+	*/
+	for (i=0;i<tab->hash_tab_size;i++) { /* don't absolutely have to do this, but
+											why leave ptrs laying around */
+		tab->array[i] = 0; /* erase old ptrs */
+	}
+	free(tab->array);
+	tab->array = ast_calloc(newsize,sizeof(struct ast_hashtab_bucket *));
+	/* now sort the buckets into their rightful new slots */
+	tab->resize_count++;
+	tab->hash_tab_size = newsize;
+	tab->largest_bucket_size = 0;
+
+	for (b=tab->tlist;b;b=bn)
+	{
+		b->prev = 0;
+		bn = b->tnext;
+		h = (*tab->hash)(b->object) % tab->hash_tab_size;
+		b->next = tab->array[h];
+		if (b->next)
+			b->next->prev = b;
+		tab->array[h] = b;
+	}
+	/* recalc the largest bucket size */
+	for (i=0;i<tab->hash_tab_size;i++) {
+		c=0;
+		for (b=tab->array[i]; b; b=b->next) {
+			c++;
+		}
+		if (c > tab->largest_bucket_size)
+			tab->largest_bucket_size = c;
+	}
+}
+
+struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab)
+{
+	/* returns an iterator */
+	struct ast_hashtab_iter *it = ast_malloc(sizeof(struct ast_hashtab_iter));
+	it->next = tab->tlist;
+	it->tab = tab;
+	if (tab->do_locking)
+		ast_rwlock_rdlock(&tab->lock);
+	return it;
+}
+
+/* use this function to get a write lock */
+struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab)
+{
+	/* returns an iterator */
+	struct ast_hashtab_iter *it = ast_malloc(sizeof(struct ast_hashtab_iter));
+	it->next = tab->tlist;
+	it->tab = tab;
+	if (tab->do_locking)
+		ast_rwlock_wrlock(&tab->lock);
+	return it;
+}
+
+void ast_hashtab_end_traversal(struct ast_hashtab_iter *it)
+{
+	if (it->tab->do_locking)
+		ast_rwlock_unlock(&it->tab->lock);
+	free(it);
+}
+
+void *ast_hashtab_next(struct ast_hashtab_iter *it)
+{
+	/* returns the next object in the list, advances iter one step */
+	struct ast_hashtab_bucket *retval;
+	
+	if (it && it->next) { /* there's a next in the bucket list */
+		retval = it->next;
+		it->next = retval->tnext;
+		return (void*)retval->object;
+	}
+	return NULL;
+}
+
+static void *ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct ast_hashtab_bucket *b, int h)
+{
+	const void *obj2;
+	
+	if (b->prev) {
+		b->prev->next = b->next;
+	} else {
+		tab->array[h] = b->next;
+	}
+	
+	if (b->next) {
+		b->next->prev = b->prev;
+	}
+	
+	tlist_del_item(&(tab->tlist), b);
+	
+	obj2 = b->object;
+	b->object = b->next = (void*)2;
+	free(b); /* free up the hashbucket */
+	tab->hash_tab_elements--;
+#ifdef DEBUG
+	{
+		int c2;
+		struct ast_hashtab_bucket *b2;
+		/* do a little checking */
+		for (c2 = 0, b2 = tab->tlist;b2;b2=b2->tnext) {
+			c2++;
+		}
+		if (c2 != tab->hash_tab_elements) {
+			printf("Hey! we didn't delete right! there are %d elements in the list, and we expected %d\n",
+				   c2, tab->hash_tab_elements);
+		}
+		for (c2 = 0, b2 = tab->tlist;b2;b2=b2->tnext) {
+			unsigned int obj3 = (unsigned long)obj2;
+			unsigned int b3 = (unsigned long)b;
+			if (b2->object == obj2)
+				printf("Hey-- you've still got a bucket pointing at ht_element %x\n", obj3);
+			if (b2->next == b)
+				printf("Hey-- you've still got a bucket with next ptr pointing to deleted bucket %x\n", b3);
+			if (b2->prev == b)
+				printf("Hey-- you've still got a bucket with prev ptr pointing to deleted bucket %x\n", b3);
+			if (b2->tprev == b)
+				printf("Hey-- you've still got a bucket with tprev ptr pointing to deleted bucket %x\n", b3);
+			if (b2->tnext == b)
+				printf("Hey-- you've still got a bucket with tnext ptr pointing to deleted bucket %x\n", b3);
+		}
+	}
+#endif
+	return (void*)obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
+}
+
+void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj)
+{
+	/* looks up the object; removes the corresponding bucket */
+	unsigned int h;
+	struct ast_hashtab_bucket *b;
+
+	if (!tab || !obj)
+		return 0;
+	if (tab->do_locking)
+		ast_rwlock_wrlock(&tab->lock);
+	h = (*tab->hash)(obj) % tab->hash_tab_size;
+	for (b=tab->array[h]; b; b=b->next)
+	{
+		void *obj2;
+		
+		if ((*tab->compare)(obj,b->object) == 0) {
+
+			obj2 = ast_hashtab_remove_object_internal(tab,b,h);
+			
+			if (tab->do_locking)
+				ast_rwlock_unlock(&tab->lock);
+			
+			return (void*)obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
+		}
+	}
+	if (tab->do_locking)
+		ast_rwlock_unlock(&tab->lock);
+	return 0;
+}
+
+void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj)
+{
+	/* looks up the object; removes the corresponding bucket */
+	unsigned int h;
+	struct ast_hashtab_bucket *b;
+
+	if (!tab || !obj)
+		return 0;
+	h = (*tab->hash)(obj) % tab->hash_tab_size;
+	for (b=tab->array[h]; b; b=b->next)
+	{
+		void *obj2;
+		
+		if ((*tab->compare)(obj,b->object) == 0) {
+
+			obj2 = ast_hashtab_remove_object_internal(tab,b,h);
+			
+			if (tab->do_locking)
+				ast_rwlock_unlock(&tab->lock);
+			
+			return (void*)obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
+		}
+	}
+	return 0;
+}
+
+void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj)
+{
+	/* looks up the object by hash and then comparing pts in bucket list instead of
+	   calling the compare routine; removes the bucket -- a slightly cheaper operation */
+	/* looks up the object; removes the corresponding bucket */
+	unsigned int h;
+	struct ast_hashtab_bucket *b;
+
+	if (!tab || !obj)
+		return 0;
+ 
+	if (tab->do_locking)
+		ast_rwlock_wrlock(&tab->lock);
+
+	h = (*tab->hash)(obj) % tab->hash_tab_size;
+	for (b=tab->array[h]; b; b=b->next)
+	{
+		const void *obj2;
+		
+		if (obj == b->object) {
+
+			obj2 = ast_hashtab_remove_object_internal(tab,b,h);
+			
+			if (tab->do_locking)
+				ast_rwlock_unlock(&tab->lock);
+
+			return (void*)obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
+		}
+	}
+	
+	if (tab->do_locking)
+		ast_rwlock_unlock(&tab->lock);
+	return 0;
+}
+
+void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj)
+{
+	/* looks up the object by hash and then comparing pts in bucket list instead of
+	   calling the compare routine; removes the bucket -- a slightly cheaper operation */
+	/* looks up the object; removes the corresponding bucket */
+	unsigned int h;
+	struct ast_hashtab_bucket *b;
+
+	if (!tab || !obj)
+		return 0;
+ 
+	h = (*tab->hash)(obj) % tab->hash_tab_size;
+	for (b=tab->array[h]; b; b=b->next)
+	{
+		const void *obj2;
+		
+		if (obj == b->object) {
+
+			obj2 = ast_hashtab_remove_object_internal(tab,b,h);
+			
+			if (tab->do_locking)
+				ast_rwlock_unlock(&tab->lock);
+
+			return (void*)obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
+		}
+	}
+
+	return 0;
+}
diff --git a/main/pbx.c b/main/pbx.c
index d3949ecf1..483bb762e 100644
--- a/main/pbx.c
+++ b/main/pbx.c
@@ -67,6 +67,7 @@ ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
 #include "asterisk/devicestate.h"
 #include "asterisk/stringfields.h"
 #include "asterisk/event.h"
+#include "asterisk/hashtab.h"
 #include "asterisk/module.h"
 #include "asterisk/indications.h"
 
@@ -78,6 +79,17 @@ ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
  * terribly bad (it's O(N+M), where N is the # of extensions and M is the avg #
  * of priorities, but a constant search time here would be great ;-)
  *
+ * A new algorithm to do searching based on a 'compiled' pattern tree is introduced
+ * here, and shows a fairly flat (constant) search time, even for over
+ * 1000 patterns. Might Still needs some work-- there are some fine points of the matching
+ * spec about tie-breaking based on the characters in character sets, but this
+ * should be do-able via the weight system currently being used.
+ *
+ * Also, using a hash table for context/priority name lookup can help prevent
+ * the find_extension routines from absorbing exponential cpu cycles. I've tested
+ * find_extension with red-black trees, which have O(log2(n)) speed. Right now,
+ * I'm using hash tables, which do searches (ideally) in O(1) time.
+ *
  */
 
 #ifdef LOW_MEMORY
@@ -135,6 +147,8 @@ struct ast_exten {
 	void *data;			/*!< Data to use (arguments) */
 	void (*datad)(void *);		/*!< Data destructor */
 	struct ast_exten *peer;		/*!< Next higher priority with our extension */
+	struct ast_hashtab *peer_tree;    /*!< Priorities list in tree form -- only on the head of the peer list */
+	struct ast_hashtab *peer_label_tree; /*!< labeled priorities in the peer list -- only on the head of the peer list */
 	const char *registrar;		/*!< Registrar */
 	struct ast_exten *next;		/*!< Extension with a greater ID */
 	char stuff[0];
@@ -169,10 +183,34 @@ struct ast_ignorepat {
 	const char pattern[0];
 };
 
+/*! \brief match_char: forms a syntax tree for quick matching of extension patterns */
+struct match_char
+{
+	int is_pattern; /* the pattern started with '_' */
+	int deleted;    /* if this is set, then... don't return it */
+	char *x;       /* the pattern itself-- matches a single char */
+	int specificity; /* simply the strlen of x, or 10 for X, 9 for Z, and 8 for N; and '.' and '!' will add 11 ? */
+	struct match_char *alt_char;
+	struct match_char *next_char;
+	struct ast_exten *exten; /* attached to last char of a pattern for exten */
+};
+
+struct scoreboard  /* make sure all fields are 0 before calling new_find_extension */
+{
+	int total_specificity;
+	int total_length;
+	char last_char;   /* set to ! or . if they are the end of the pattern */
+	int canmatch;     /* if the string to match was just too short */
+	struct ast_exten *canmatch_exten;
+	struct ast_exten *exten;
+};
+
 /*! \brief ast_context: An extension context */
 struct ast_context {
 	ast_rwlock_t lock; 			/*!< A lock to prevent multiple threads from clobbering the context */
 	struct ast_exten *root;			/*!< The root of the list of extensions */
+	struct ast_hashtab *root_tree;            /*!< For exact matches on the extensions in the pattern tree, and for traversals of the pattern_tree  */
+ 	struct match_char *pattern_tree;        /*!< A tree to speed up extension pattern matching */
 	struct ast_context *next;		/*!< Link them together */
 	struct ast_include *includes;		/*!< Include other contexts */
 	struct ast_ignorepat *ignorepats;	/*!< Patterns for which to continue playing dialtone */
@@ -286,6 +324,88 @@ int pbx_builtin_setvar(struct ast_channel *, void *);
 static int pbx_builtin_setvar_multiple(struct ast_channel *, void *);
 static int pbx_builtin_importvar(struct ast_channel *, void *);
 static void set_ext_pri(struct ast_channel *c, const char *exten, int pri);
+void new_find_extension(const char *str, struct scoreboard *score, struct match_char *tree, int length, int spec, const char *callerid);
+struct match_char *already_in_tree(struct match_char *current, char *pat);
+struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1);
+struct match_char *add_pattern_node(struct ast_context *con, struct match_char *current, char *pattern, int is_pattern, int already, int specificity);
+void create_match_char_tree(struct ast_context *con);
+struct ast_exten *get_canmatch_exten(struct match_char *node);
+void destroy_pattern_tree(struct match_char *pattern_tree);
+static int hashtab_compare_contexts(const void *ah_a, const void *ah_b);
+static int hashtab_compare_extens(const void *ha_a, const void *ah_b);
+static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b);
+static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b);
+static unsigned int hashtab_hash_contexts(const void *obj);
+static unsigned int hashtab_hash_extens(const void *obj);
+static unsigned int hashtab_hash_priority(const void *obj);
+static unsigned int hashtab_hash_labels(const void *obj);
+
+/* labels, contexts are case sensitive  priority numbers are ints */
+static int hashtab_compare_contexts(const void *ah_a, const void *ah_b)
+{
+	const struct ast_context *ac = ah_a;
+	const struct ast_context *bc = ah_b;
+	/* assume context names are registered in a string table! */
+	return strcmp(ac->name, bc->name);
+}
+
+static int hashtab_compare_extens(const void *ah_a, const void *ah_b)
+{
+	const struct ast_exten *ac = ah_a;
+	const struct ast_exten *bc = ah_b;
+	int x = strcmp(ac->exten, bc->exten);
+	if (x) /* if exten names are diff, then return */
+		return x;
+	/* but if they are the same, do the cidmatch values match? */
+	if (ac->matchcid && bc->matchcid) {
+		return strcmp(ac->cidmatch,bc->cidmatch);
+	} else {
+		return 1; /* if there's matchcid on one but not the other, they are different */
+	}
+}
+
+static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b)
+{
+	const struct ast_exten *ac = ah_a;
+	const struct ast_exten *bc = ah_b;
+	return ac->priority != bc->priority;
+}
+
+static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b)
+{
+	const struct ast_exten *ac = ah_a;
+	const struct ast_exten *bc = ah_b;
+	return strcmp(ac->label, bc->label);
+}
+
+static unsigned int hashtab_hash_contexts(const void *obj)
+{
+	const struct ast_context *ac = obj;
+	return ast_hashtab_hash_string(ac->name);
+}
+
+static unsigned int hashtab_hash_extens(const void *obj)
+{
+	const struct ast_exten *ac = obj;
+	unsigned int x = ast_hashtab_hash_string(ac->exten);
+	unsigned int y = 0;
+	if (ac->matchcid)
+		y = ast_hashtab_hash_string(ac->cidmatch);
+	return x+y;
+}
+
+static unsigned int hashtab_hash_priority(const void *obj)
+{
+	const struct ast_exten *ac = obj;
+	return ast_hashtab_hash_int(ac->priority);
+}
+
+static unsigned int hashtab_hash_labels(const void *obj)
+{
+	const struct ast_exten *ac = obj;
+	return ast_hashtab_hash_string(ac->label);
+}
+
 
 AST_RWLOCK_DEFINE_STATIC(globalslock);
 static struct varshead globals = AST_LIST_HEAD_NOLOCK_INIT_VALUE;
@@ -558,6 +678,8 @@ static struct pbx_builtin {
 };
 
 static struct ast_context *contexts;
+static struct ast_hashtab *contexts_tree = NULL;
+
 AST_RWLOCK_DEFINE_STATIC(conlock); 		/*!< Lock for the ast_context list */
 
 static AST_RWLIST_HEAD_STATIC(apps, ast_app);
@@ -653,6 +775,391 @@ static void pbx_destroy(struct ast_pbx *p)
 	ast_free(p);
 }
 
+/* form a tree that fully describes all the patterns in a context's extensions 
+ * in this tree, a "node" consists of a series of match_char structs linked in a chain
+ * via the alt_char pointers. More than one pattern can share the same parts of the 
+ * tree as other extensions with the same pattern to that point. The algorithm to
+ * find which pattern best matches a string, would follow **all** matching paths. As
+ * complete matches are found, a "max" match record would be updated if the match first involves 
+ * a longer string, then, on a tie, a smaller total of specificity. This can be accomplished
+ * by recursive calls affecting a shared scoreboard.
+ * As and example, consider these 4 extensions:
+ * (a) NXXNXXXXXX
+ * (b) 307754XXXX 
+ * (c) fax
+ * (d) NXXXXXXXXX
+ *
+ * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
+ * most numbers. For all numbers beginning with 307754, (b) should always win.
+ *
+ * These pattern should form a tree that looks like this:
+ *   { "N" }  --next-->  { "X" }  --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
+ *      |                                                        |
+ *      |                                                        |alt
+ *      |alt                                                     |
+ *      |                                                     { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
+ *      |
+ *   { "3" }  --next-->  { "0" }  --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
+ *      |
+ *      |alt
+ *      |
+ *   { "f" }  --next-->  { "a" }  --next--> { "x"  exten_match: (c) }
+ *
+ *   In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
+ *   fewer CPU cycles than a call to index("23456789",*z), where *z is the char to match...
+ *
+ *   traversal is pretty simple: one routine merely traverses the alt list, and for each match in the pattern,  it calls itself
+ *   on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
+ *   We pass a pointer to a scoreboard down through, also.
+ *   When an exten_match pointer is set, or a '.' or a '!' is encountered, we update the scoreboard only if the length is greater, or in case
+ *   of equal length, if the specificity is lower, and return. Hope the limit on stack depth won't be a problem... this routine should 
+ *   be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
+ *
+ *   In the above example, with the number "3077549999" as the pattern, the traversor should match extensions a, b and d.  All are
+ *   of length 10; but they have total specificities of  96, 46, and 98, respectively. (b) wins with its lower specificity number!
+ *
+ *   Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown. But, it should
+ *   be pretty close to optimal for this sort of overall algorithm.
+ *
+ * */
+
+/* you only really update the scoreboard, if the new score is BETTER than the 
+ * one stored there. ignore it otherwise.
+ */
+
+
+static void update_scoreboard(struct scoreboard *board, int length, int spec, struct ast_exten *exten, char last, const char *callerid)
+{
+	/* doing a matchcid() check here would be easy and cheap, but...
+	   unfortunately, it only works if an extension can have only one 
+	   cid to match. That's not real life. CID patterns need to exist 
+	   in the tree for this sort of thing to work properly. */
+
+	if (length > board->total_length) {
+		board->total_specificity = spec;
+		board->total_length = length;
+		board->exten = exten;
+		board->last_char = last;
+	} else if (length == board->total_length && spec < board->total_specificity) {
+		board->total_specificity = spec;
+		board->total_length = length;
+		board->exten = exten;
+		board->last_char = last;
+	}
+}
+
+#ifdef NEED_DEBUG
+static void log_match_char_tree(struct match_char *node, char *prefix)
+{
+	char my_prefix[1024];
+	
+	ast_log(LOG_DEBUG,"%s%s:%c:%d:%s\n", prefix, node->x, node->is_pattern ? 'Y':'N', node->specificity, node->exten? "EXTEN":"");
+	strcpy(my_prefix,prefix);
+	strcat(my_prefix,"+-----------------");
+	if (node->next_char)
+		print_match_char_tree(node->next_char, my_prefix);
+	if (node->alt_char)
+		print_match_char_tree(node->alt_char, prefix);
+}
+#endif
+
+static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
+{
+	char my_prefix[1024];
+	
+	ast_cli(fd, "%s%s:%c:%d:%s\n", prefix, node->x, node->is_pattern ? 'Y':'N', node->specificity, node->exten? "EXTEN":"");
+	strcpy(my_prefix,prefix);
+	strcat(my_prefix,"+-----------------");
+	if (node->next_char)
+		cli_match_char_tree(node->next_char, my_prefix, fd);
+	if (node->alt_char)
+		cli_match_char_tree(node->alt_char, prefix, fd);
+}
+
+struct ast_exten *get_canmatch_exten(struct match_char *node)
+{
+	/* find the exten at the end of the rope */
+	struct match_char *node2 = node;
+	for (node2 = node; node2; node2 = node2->next_char)
+		if (node2->exten)
+			return node2->exten;
+	return 0;
+}
+
+void new_find_extension(const char *str, struct scoreboard *score, struct match_char *tree, int length, int spec, const char *callerid)
+{
+	struct match_char *p; /* note minimal stack storage requirements */
+	for (p=tree; p; p=p->alt_char) {
+		if (p->x[0] == 'N' && p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
+			if (p->exten) /* if a shorter pattern matches along the way, might as well report it */
+				update_scoreboard(score, length+1, spec+8, p->exten,0,callerid);
+
+			if (p->next_char && ( *(str+1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0))) {
+				if (*(str+1))
+					new_find_extension(str+1, score, p->next_char, length+1, spec+p->specificity, callerid);
+				else
+					new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid);
+			} else if (p->next_char && !*(str+1)) {
+				score->canmatch = 1;
+				score->canmatch_exten = get_canmatch_exten(p);
+			} else {
+				return;
+			}
+		} else if (p->x[0] == 'Z' && p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
+			if (p->exten) /* if a shorter pattern matches along the way, might as well report it */
+				update_scoreboard(score, length+1, spec+8, p->exten,0,callerid);
+
+			if (p->next_char && ( *(str+1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0))) {
+				if (*(str+1))
+					new_find_extension(str+1, score, p->next_char, length+1, spec+p->specificity, callerid);
+				else
+					new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid);
+			} else if (p->next_char && !*(str+1)) {
+				score->canmatch = 1;
+				score->canmatch_exten = get_canmatch_exten(p);
+			} else {
+				return;
+			}
+		} else if (p->x[0] == 'X' && p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
+			if (p->exten) /* if a shorter pattern matches along the way, might as well report it */
+				update_scoreboard(score, length+1, spec+8, p->exten,0,callerid);
+
+			if (p->next_char && ( *(str+1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0))) {
+				if (*(str+1))
+					new_find_extension(str+1, score, p->next_char, length+1, spec+p->specificity, callerid);
+				else
+					new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid);
+			} else if (p->next_char && !*(str+1)) {
+				score->canmatch = 1;
+				score->canmatch_exten = get_canmatch_exten(p);
+			} else {
+				return;
+			}
+		} else if (p->x[0] == '.' && p->x[1] == 0) {
+			update_scoreboard(score, length+1, spec+11, p->exten, '.', callerid);
+			if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
+				new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid);
+			}
+			return;
+		} else if (p->x[0] == '!' && p->x[1] == 0) {
+			update_scoreboard(score, length+1, spec+11, p->exten, '!', callerid);
+			if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
+				new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid);
+			}
+			return;
+		} else if (p->x[0] == '/' && p->x[1] == 0) {
+			/* the pattern in the tree includes the cid match! */
+			if (p->next_char && callerid && *callerid) {
+				new_find_extension(callerid, score, p->next_char, length+1, spec, callerid);
+			}
+		} else if (index(p->x, *str)) {
+			if (p->exten) /* if a shorter pattern matches along the way, might as well report it */
+				update_scoreboard(score, length+1, spec+8, p->exten,0,callerid);
+
+
+			if (p->next_char && ( *(str+1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0))) {
+				if (*(str+1)) {
+					new_find_extension(str+1, score, p->next_char, length+1, spec+p->specificity, callerid);
+				} else {
+					new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid);
+				}
+			} else if (p->next_char && !*(str+1)) {
+				score->canmatch = 1;
+				score->canmatch_exten = get_canmatch_exten(p);
+			} else {
+				return;
+			}
+		}
+	}
+}
+
+/* the algorithm for forming the extension pattern tree is also a bit simple; you 
+ * traverse all the extensions in a context, and for each char of the extension,
+ * you see if it exists in the tree; if it doesn't, you add it at the appropriate
+ * spot. What more can I say? At the end of the list, you cap it off by adding the
+ * address of the extension involved. Duplicate patterns will be complained about.
+ *
+ * Ideally, this would be done for each context after it is created and fully 
+ * filled. It could be done as a finishing step after extensions.conf or .ael is
+ * loaded, or it could be done when the first search is encountered. It should only
+ * have to be done once, until the next unload or reload.
+ *
+ * I guess forming this pattern tree would be analogous to compiling a regex.
+ */
+
+
+struct match_char *already_in_tree(struct match_char *current, char *pat)
+{
+	struct match_char *t;
+	if (!current)
+		return 0;
+	for (t=current; t; t=t->alt_char) {
+		if (strcmp(pat,t->x) == 0) /* uh, we may want to sort exploded [] contents to make matching easy */
+			return t;
+	}
+	return 0;
+}
+
+struct match_char *add_pattern_node(struct ast_context *con, struct match_char *current, char *pattern, int is_pattern, int already, int specificity)
+{
+	struct match_char *m = ast_calloc(1,sizeof(struct match_char));
+	m->x = strdup(pattern);
+	m->is_pattern = is_pattern;
+	if (specificity == 1 && is_pattern && pattern[0] == 'N')
+		m->specificity = 8;
+	else if (specificity == 1 && is_pattern && pattern[0] == 'Z')
+		m->specificity = 9;
+	else if (specificity == 1 && is_pattern && pattern[0] == 'X')
+		m->specificity = 10;
+	else if (specificity == 1 && is_pattern && pattern[0] == '.')
+		m->specificity = 11;
+	else if (specificity == 1 && is_pattern && pattern[0] == '!')
+		m->specificity = 11;
+	else
+		m->specificity = specificity;
+	
+	if (!con->pattern_tree) {
+		con->pattern_tree = m;
+	} else {
+		if (already) { /* switch to the new regime (traversing vs appending)*/
+			m->alt_char = current->alt_char;
+			current->alt_char = m;
+		} else {
+			if (current->next_char) {
+				m->alt_char = current->next_char->alt_char;
+				current->next_char = m;
+			} else {
+				current->next_char = m;
+			}
+		}
+	}
+	return m;
+}
+
+struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1)
+{
+	struct match_char *m1=0,*m2=0;
+	int specif;
+	int already;
+	int pattern = 0;
+	char buf[256];
+	char extenbuf[512];
+	char *s1 = extenbuf;
+	int l1 = strlen(e1->exten) + strlen(e1->cidmatch) + 2;
+	
+
+	strncpy(extenbuf,e1->exten,sizeof(extenbuf));
+	if (e1->matchcid &&  l1 <= sizeof(extenbuf)) {
+		strcat(extenbuf,"/");
+		strcat(extenbuf,e1->cidmatch);
+	} else if (l1 > sizeof(extenbuf)) {
+		ast_log(LOG_ERROR,"The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n", e1->exten, e1->cidmatch);
+		return 0;
+	}
+#ifdef NEED_DEBUG
+	ast_log(LOG_DEBUG,"Adding exten %s%c%s to tree\n", s1, e1->matchcid? '/':' ', e1->matchcid? e1->cidmatch : "");
+#endif
+	m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
+	already = 1;
+
+	if ( *s1 == '_') {
+		pattern = 1;
+		s1++;
+	}
+	while( *s1 ) {
+		if (pattern && *s1 == '[' && *(s1-1) != '\\') {
+			char *s2 = buf;
+			while (*s1 != ']' && *(s1-1) != '\\' ) {
+				if (*s1 == '\\') {
+					if (*(s1+1) == ']') {
+						*s2++ = ']';
+						s1++;s1++;
+					} else if (*(s1+1) == '\\') {
+						*s2++ = '\\';
+						s1++;s1++;
+					} else if (*(s1+1) == '-') {
+						*s2++ = '-';
+						s1++; s1++;
+					} else if (*(s1+1) == '[') {
+						*s2++ = '[';
+						s1++; s1++;
+					}
+				} else if (*s1 == '-') { /* remember to add some error checking to all this! */
+					char s3 = *(s1-1);
+					char s4 = *(s1+1);
+					for (s3++; s3 <= s4; s3++) {
+						*s2++ = s3;
+					}
+					s1++; s1++;
+				} else {
+					*s2++ = *s1++;
+				}
+			}
+			specif = strlen(buf);
+		} else {
+			if (*s1 == '\\') {
+				s1++;
+				buf[0] = *s1;
+			} else {
+				buf[0] = *s1;
+			}
+			buf[1] = 0;
+			specif = 1;
+		}
+		
+		if (already && (m2=already_in_tree(m1,buf))) {
+			if (!(*(s1+1)))  /* if this is the end of the pattern, but not the end of the tree, then mark this node with the exten...
+								a shorter pattern might win if the longer one doesn't match */
+				m1->exten = e1;
+			m1 = m2->next_char; /* m1 points to the node to compare against */
+		} else {
+			m1 = add_pattern_node(con, m1, buf, pattern, already,specif); /* m1 is the node just added */
+			if (!(*(s1+1)))
+				m1->exten = e1;
+			already = 0;
+		}
+		s1++; /* advance to next char */
+	}
+	return m1;
+}
+
+void create_match_char_tree(struct ast_context *con)
+{
+	struct ast_hashtab_iter *t1;
+	struct ast_exten *e1;
+#ifdef NEED_DEBUG
+	int biggest_bucket, resizes, numobjs, numbucks;
+	
+	ast_log(LOG_DEBUG,"Creating Extension Trie for context %s\n", con->name);
+	ast_hashtab_get_stats(con->root_tree, &biggest_bucket, &resizes, &numobjs, &numbucks);
+	ast_log(LOG_DEBUG,"This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
+			numobjs, numbucks, biggest_bucket, resizes);
+#endif
+	t1 = ast_hashtab_start_traversal(con->root_tree);
+	while( (e1 = ast_hashtab_next(t1)) ) {
+		add_exten_to_pattern_tree(con, e1);
+	}
+	ast_hashtab_end_traversal(t1);
+}
+
+void destroy_pattern_tree(struct match_char *pattern_tree) /* pattern tree is a simple binary tree, sort of, so the proper way to destroy it is... recursively! */
+{
+	/* destroy all the alternates */
+	if (pattern_tree->alt_char) {
+		destroy_pattern_tree(pattern_tree->alt_char);
+		pattern_tree->alt_char = 0;
+	}
+	/* destroy all the nexts */
+	if (pattern_tree->next_char) {
+		destroy_pattern_tree(pattern_tree->next_char);
+		pattern_tree->next_char = 0;
+	}
+	pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
+	if (pattern_tree->x)
+		free(pattern_tree->x);
+	free(pattern_tree);
+}
+
 /*
  * Special characters used in patterns:
  *	'_'	underscore is the leading character of a pattern.
@@ -947,13 +1454,34 @@ int ast_extension_close(const char *pattern, const char *data, int needmore)
 	return extension_match_core(pattern, data, needmore);
 }
 
+struct fake_context /* this struct is purely for matching in the hashtab */
+{
+	ast_rwlock_t lock; 			
+	struct ast_exten *root;		
+	struct ast_hashtab *root_tree;            
+	struct match_char *pattern_tree;       
+	struct ast_context *next;	
+	struct ast_include *includes;		
+	struct ast_ignorepat *ignorepats;	
+	const char *registrar;	
+	AST_LIST_HEAD_NOLOCK(, ast_sw) alts;	
+	ast_mutex_t macrolock;		
+	char name[256];		
+};
+
 struct ast_context *ast_context_find(const char *name)
 {
 	struct ast_context *tmp = NULL;
+	struct fake_context item;
+	strncpy(item.name,name,256);
 	ast_rdlock_contexts();
-	while ( (tmp = ast_walk_contexts(tmp)) ) {
-		if (!name || !strcasecmp(name, tmp->name))
-			break;
+	if( contexts_tree ) {
+		tmp = ast_hashtab_lookup(contexts_tree,&item);
+    } else {
+		while ( (tmp = ast_walk_contexts(tmp)) ) {
+			if (!name || !strcasecmp(name, tmp->name))
+				break;
+		}
 	}
 	ast_unlock_contexts();
 	return tmp;
@@ -965,17 +1493,6 @@ struct ast_context *ast_context_find(const char *name)
 #define STATUS_NO_LABEL		4
 #define STATUS_SUCCESS		5
 
-static int matchcid(const char *cidpattern, const char *callerid)
-{
-	/* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
-	   failing to get a number should count as a match, otherwise not */
-
-	if (ast_strlen_zero(callerid))
-		return ast_strlen_zero(cidpattern) ? 1 : 0;
-
-	return ast_extension_match(cidpattern, callerid);
-}
-
 struct ast_exten *pbx_find_extension(struct ast_channel *chan,
 	struct ast_context *bypass, struct pbx_find_info *q,
 	const char *context, const char *exten, int priority,
@@ -986,6 +1503,12 @@ struct ast_exten *pbx_find_extension(struct ast_channel *chan,
 	struct ast_exten *e, *eroot;
 	struct ast_include *i;
 	struct ast_sw *sw;
+	struct ast_exten pattern;
+	struct scoreboard score;
+
+	pattern.label = label;
+	pattern.priority = priority;
+
 
 	/* Initialize status if appropriate */
 	if (q->stacklen == 0) {
@@ -1007,18 +1530,72 @@ struct ast_exten *pbx_find_extension(struct ast_channel *chan,
 	if (bypass)	/* bypass means we only look there */
 		tmp = bypass;
 	else {	/* look in contexts */
+		struct fake_context item;
+		strncpy(item.name,context,256);
+		tmp = ast_hashtab_lookup(contexts_tree,&item);
+#ifdef NOTNOW
 		tmp = NULL;
 		while ((tmp = ast_walk_contexts(tmp)) ) {
 			if (!strcmp(tmp->name, context))
 				break;
 		}
+#endif
 		if (!tmp)
 			return NULL;
 	}
 
 	if (q->status < STATUS_NO_EXTENSION)
 		q->status = STATUS_NO_EXTENSION;
+	
+	/* Do a search for matching extension */
+	eroot = NULL;
+	score.total_specificity = 0;
+	score.exten = 0;
+	score.total_length = 0;
+	if (!tmp->pattern_tree)
+	{
+		create_match_char_tree(tmp);
+#ifdef NEED_DEBUG
+		ast_log(LOG_DEBUG,"Tree Created in context %s:\n", context);
+		print_match_char_tree(tmp->pattern_tree," ");
+#endif
+	}
+	
+	new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid);
+	eroot = score.exten;
+
+	if (score.last_char == '!' && action == E_MATCHMORE) {
+		/* We match an extension ending in '!'.
+		 * The decision in this case is final and is NULL (no match).
+		 */
+		return NULL;
+	}
+
+	if (!eroot && action == E_CANMATCH && score.canmatch_exten) {
+		q->status = STATUS_SUCCESS;
+		return score.canmatch_exten;
+	}
+
+	if (eroot) {
+		/* found entry, now look for the right priority */
+		if (q->status < STATUS_NO_PRIORITY)
+			q->status = STATUS_NO_PRIORITY;
+		e = NULL;
+		if (action == E_FINDLABEL && label ) {
+			if (q->status < STATUS_NO_LABEL)
+				q->status = STATUS_NO_LABEL;
+			e = ast_hashtab_lookup(eroot->peer_label_tree, &pattern);
+		} else {
+			e = ast_hashtab_lookup(eroot->peer_tree, &pattern);
+		}
+		if (e) {	/* found a valid match */
+			q->status = STATUS_SUCCESS;
+			q->foundcontext = context;
+			return e;
+		}
+	}
 
+#ifdef NOTNOW2
 	/* scan the list trying to match extension and CID */
 	eroot = NULL;
 	while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
@@ -1037,6 +1614,14 @@ struct ast_exten *pbx_find_extension(struct ast_channel *chan,
 		if (q->status < STATUS_NO_PRIORITY)
 			q->status = STATUS_NO_PRIORITY;
 		e = NULL;
+		if (action == E_FINDLABEL && label ) {
+			if (q->status < STATUS_NO_LABEL)
+				q->status = STATUS_NO_LABEL;
+			e = ast_hashtab_lookup(eroot->peer_label_tree, &pattern);
+		} else {
+			e = ast_hashtab_lookup(eroot->peer_tree, &pattern);
+		}
+#ifdef NOTNOW
 		while ( (e = ast_walk_extension_priorities(eroot, e)) ) {
 			/* Match label or priority */
 			if (action == E_FINDLABEL) {
@@ -1048,12 +1633,14 @@ struct ast_exten *pbx_find_extension(struct ast_channel *chan,
 				break;	/* found it */
 			} /* else keep searching */
 		}
+#endif
 		if (e) {	/* found a valid match */
 			q->status = STATUS_SUCCESS;
 			q->foundcontext = context;
 			return e;
 		}
 	}
+#endif
 	/* Check alternative switches */
 	AST_LIST_TRAVERSE(&tmp->alts, sw, list) {
 		struct ast_switch *asw = pbx_findswitch(sw->name);
@@ -2751,6 +3338,10 @@ static void destroy_exten(struct ast_exten *e)
 	if (e->priority == PRIORITY_HINT)
 		ast_remove_hint(e);
 
+	if (e->peer_tree)
+		ast_hashtab_destroy(e->peer_tree,0);
+	if (e->peer_label_tree)
+		ast_hashtab_destroy(e->peer_label_tree, 0);
 	if (e->datad)
 		e->datad(e->data);
 	ast_free(e);
@@ -2830,15 +3421,21 @@ int pbx_set_autofallthrough(int newval)
 static struct ast_context *find_context_locked(const char *context)
 {
 	struct ast_context *c = NULL;
-
+	struct fake_context item;
+	strncpy(item.name, context, 256);
 	ast_rdlock_contexts();
+	c = ast_hashtab_lookup(contexts_tree,&item);
+
+#ifdef NOTNOW
+
 	while ( (c = ast_walk_contexts(c)) ) {
 		if (!strcmp(ast_get_context_name(c), context))
 			return c;
 	}
+#endif
 	ast_unlock_contexts();
 
-	return NULL;
+	return c;
 }
 
 /*!
@@ -3056,9 +3653,18 @@ int ast_context_lockmacro(const char *context)
 {
 	struct ast_context *c = NULL;
 	int ret = -1;
+	struct fake_context item;
 
 	ast_rdlock_contexts();
 
+	strncpy(item.name,context,256);
+	c = ast_hashtab_lookup(contexts_tree,&item);
+	if (c)
+		ret = 0;
+
+
+#ifdef NOTNOW
+
 	while ((c = ast_walk_contexts(c))) {
 		if (!strcmp(ast_get_context_name(c), context)) {
 			ret = 0;
@@ -3066,6 +3672,7 @@ int ast_context_lockmacro(const char *context)
 		}
 	}
 
+#endif
 	ast_unlock_contexts();
 
 	/* if we found context, lock macrolock */
@@ -3084,9 +3691,16 @@ int ast_context_unlockmacro(const char *context)
 {
 	struct ast_context *c = NULL;
 	int ret = -1;
+	struct fake_context item;
 
 	ast_rdlock_contexts();
 
+	strncpy(item.name, context, 256);
+	c = ast_hashtab_lookup(contexts_tree,&item);
+	if (c)
+		ret = 0;
+#ifdef NOTNOW
+
 	while ((c = ast_walk_contexts(c))) {
 		if (!strcmp(ast_get_context_name(c), context)) {
 			ret = 0;
@@ -3094,6 +3708,7 @@ int ast_context_unlockmacro(const char *context)
 		}
 	}
 
+#endif
 	ast_unlock_contexts();
 
 	/* if we found context, unlock macrolock */
@@ -3643,6 +4258,13 @@ static int show_dialplan_helper(int fd, const char *context, const char *exten,
 					buf, ast_get_switch_registrar(sw));
 			}
 		}
+		
+		if (option_debug && c->pattern_tree)
+		{
+			ast_cli(fd," In-mem exten Trie for Fast Extension Pattern Matching:\r\b\n");
+			cli_match_char_tree(c->pattern_tree, " ", fd);
+		}
+		
 
 		ast_unlock_context(c);
 
@@ -4038,41 +4660,64 @@ int ast_unregister_application(const char *app)
 static struct ast_context *__ast_context_create(struct ast_context **extcontexts, const char *name, const char *registrar, int existsokay)
 {
 	struct ast_context *tmp, **local_contexts;
+	struct fake_context search;
 	int length = sizeof(struct ast_context) + strlen(name) + 1;
 
+	if (!contexts_tree) {
+		contexts_tree = ast_hashtab_create(17,
+										   hashtab_compare_contexts, 
+										   ast_hashtab_resize_java,
+										   ast_hashtab_newsize_java,
+										   hashtab_hash_contexts,
+										   1);
+	}
+	
 	if (!extcontexts) {
-		ast_wrlock_contexts();
+		ast_rdlock_contexts();
 		local_contexts = &contexts;
-	} else
+		strncpy(search.name,name,sizeof(search.name));
+		tmp = ast_hashtab_lookup(contexts_tree, &search);
+		if (!existsokay && tmp) {
+			ast_log(LOG_WARNING, "Tried to register context '%s', already in use\n", name);
+		}
+		ast_unlock_contexts();
+		if (tmp)
+			return tmp;
+	} else { /* local contexts just in a linked list; search there for the new context; slow, linear search, but not frequent */
 		local_contexts = extcontexts;
-
-	for (tmp = *local_contexts; tmp; tmp = tmp->next) {
-		if (!strcasecmp(tmp->name, name)) {
-			if (!existsokay) {
-				ast_log(LOG_WARNING, "Tried to register context '%s', already in use\n", name);
-				tmp = NULL;
+		for (tmp = *local_contexts; tmp; tmp = tmp->next) {
+			if (!strcasecmp(tmp->name, name)) {
+				if (!existsokay) {
+					ast_log(LOG_WARNING, "Tried to register context '%s', already in use\n", name);
+					tmp = NULL;
+				}
+				return tmp;
 			}
-			if (!extcontexts)
-				ast_unlock_contexts();
-			return tmp;
 		}
 	}
+	
 	if ((tmp = ast_calloc(1, length))) {
 		ast_rwlock_init(&tmp->lock);
 		ast_mutex_init(&tmp->macrolock);
 		strcpy(tmp->name, name);
 		tmp->root = NULL;
+		tmp->root_tree = NULL;
 		tmp->registrar = registrar;
-		tmp->next = *local_contexts;
 		tmp->includes = NULL;
 		tmp->ignorepats = NULL;
-		*local_contexts = tmp;
-		ast_debug(1, "Registered context '%s'\n", tmp->name);
-		ast_verb(3, "Registered extension context '%s'\n", tmp->name);
 	}
-
-	if (!extcontexts)
+	if (!extcontexts) {
+		ast_wrlock_contexts();
+		tmp->next = *local_contexts;
+		*local_contexts = tmp;
+		ast_hashtab_insert_safe(contexts_tree, tmp); /*put this context into the tree */
 		ast_unlock_contexts();
+	} else {
+		tmp->next = *local_contexts;
+		*local_contexts = tmp;
+	}
+	ast_debug(1, "Registered context '%s'\n", tmp->name);
+	ast_verb(3, "Registered extension context '%s'\n", tmp->name);
 	return tmp;
 }
 
@@ -4155,6 +4800,11 @@ void ast_merge_contexts_and_delete(struct ast_context **extcontexts, const char
 			tmp = tmp->next;
 		}
 	}
+	tmp = *extcontexts;
+	while (tmp) {
+		ast_hashtab_insert_safe(contexts_tree, tmp); /*put this context into the tree */
+		tmp = tmp->next;
+	}
 	if (lasttmp) {
 		lasttmp->next = contexts;
 		contexts = *extcontexts;
@@ -4847,12 +5497,16 @@ static int add_pri(struct ast_context *con, struct ast_exten *tmp,
 	struct ast_exten *el, struct ast_exten *e, int replace)
 {
 	struct ast_exten *ep;
+	struct ast_exten *eh=e;
 
 	for (ep = NULL; e ; ep = e, e = e->peer) {
 		if (e->priority >= tmp->priority)
 			break;
 	}
 	if (!e) {	/* go at the end, and ep is surely set because the list is not empty */
+		ast_hashtab_insert_safe(eh->peer_tree, tmp);
+		if (tmp->label)
+			ast_hashtab_insert_safe(eh->peer_label_tree, tmp);
 		ep->peer = tmp;
 		return 0;	/* success */
 	}
@@ -4871,12 +5525,41 @@ static int add_pri(struct ast_context *con, struct ast_exten *tmp,
 		 */
 		tmp->next = e->next;	/* not meaningful if we are not first in the peer list */
 		tmp->peer = e->peer;	/* always meaningful */
-		if (ep)			/* We're in the peer list, just insert ourselves */
+		if (ep)	{		/* We're in the peer list, just insert ourselves */
+			ast_hashtab_remove_object_via_lookup(eh->peer_tree,e);
+			if (e->label)
+				ast_hashtab_remove_object_via_lookup(eh->peer_label_tree,e);
+			ast_hashtab_insert_safe(eh->peer_tree,tmp);
+			if (tmp->label)
+				ast_hashtab_insert_safe(eh->peer_label_tree,tmp);
 			ep->peer = tmp;
-		else if (el)		/* We're the first extension. Take over e's functions */
+		} else if (el) {		/* We're the first extension. Take over e's functions */
+			tmp->peer_tree = e->peer_tree;
+			tmp->peer_label_tree = e->peer_label_tree;
+			ast_hashtab_remove_object_via_lookup(tmp->peer_tree,e);
+			ast_hashtab_insert_safe(tmp->peer_tree,tmp);
+			if (e->label)
+				ast_hashtab_remove_object_via_lookup(tmp->peer_label_tree,e);
+			if (tmp->label)
+				ast_hashtab_insert_safe(tmp->peer_label_tree,tmp);
+			ast_hashtab_remove_object_via_lookup(con->root_tree, e->exten);
+			ast_hashtab_insert_safe(con->root_tree, tmp->exten);
 			el->next = tmp;
-		else			/* We're the very first extension.  */
-			con->root = tmp;
+		} else {			/* We're the very first extension.  */
+			ast_hashtab_remove_object_via_lookup(con->root_tree,e);
+			ast_hashtab_insert_safe(con->root_tree,tmp);
+			tmp->peer_tree = e->peer_tree;
+			tmp->peer_label_tree = e->peer_label_tree;
+			ast_hashtab_remove_object_via_lookup(tmp->peer_tree,e);
+			ast_hashtab_insert_safe(tmp->peer_tree,tmp);
+			if (e->label)
+				ast_hashtab_remove_object_via_lookup(tmp->peer_label_tree,e);
+			if (tmp->label)
+			ast_hashtab_insert_safe(tmp->peer_label_tree,tmp);
+			ast_hashtab_remove_object_via_lookup(con->root_tree, e->exten);
+			ast_hashtab_insert_safe(con->root_tree, tmp->exten);
+ 			con->root = tmp;
+		}
 		if (tmp->priority == PRIORITY_HINT)
 			ast_change_hint(e,tmp);
 		/* Destroy the old one */
@@ -4886,9 +5569,22 @@ static int add_pri(struct ast_context *con, struct ast_exten *tmp,
 	} else {	/* Slip ourselves in just before e */
 		tmp->peer = e;
 		tmp->next = e->next;	/* extension chain, or NULL if e is not the first extension */
-		if (ep)			/* Easy enough, we're just in the peer list */
+		if (ep) {			/* Easy enough, we're just in the peer list */
+			if (tmp->label)
+				ast_hashtab_insert_safe(eh->peer_label_tree, tmp);
+			ast_hashtab_insert_safe(eh->peer_tree, tmp);
 			ep->peer = tmp;
-		else {			/* we are the first in some peer list, so link in the ext list */
+		} else {			/* we are the first in some peer list, so link in the ext list */
+			tmp->peer_tree = e->peer_tree;
+			tmp->peer_label_tree = e ->peer_label_tree;
+			e->peer_tree = 0;
+			e->peer_label_tree = 0;
+			ast_hashtab_insert_safe(tmp->peer_tree,tmp);
+			if (tmp->label) {
+				ast_hashtab_insert_safe(tmp->peer_label_tree,tmp);
+			}
+			ast_hashtab_remove_object_via_lookup(con->root_tree,e);
+			ast_hashtab_insert_safe(con->root_tree,tmp);
 			if (el)
 				el->next = tmp;	/* in the middle... */
 			else
@@ -4938,11 +5634,13 @@ int ast_add_extension2(struct ast_context *con,
 	 * All priorities for the same ext/pattern/cid are kept in a list,
 	 * using the 'peer' field  as a link field..
 	 */
-	struct ast_exten *tmp, *e, *el = NULL;
+	struct ast_exten *tmp, *tmp2, *e, *el = NULL;
 	int res;
 	int length;
 	char *p;
 	char expand_buf[VAR_BUF_SIZE];
+	struct ast_exten dummy_exten;
+	char dummy_name[1024];
 
 	/* if we are adding a hint, and there are global variables, and the hint
 	   contains variable references, then expand them
@@ -4994,6 +5692,17 @@ int ast_add_extension2(struct ast_context *con,
 	tmp->registrar = registrar;
 
 	ast_wrlock_context(con);
+	
+	if (con->pattern_tree) { /* usually, on initial load, the pattern_tree isn't formed until the first find_exten; so if we are adding
+								an extension, and the trie exists, then we need to incrementally add this pattern to it. */
+		strncpy(dummy_name,extension,sizeof(dummy_name));
+		dummy_exten.exten = dummy_name;
+		tmp2 = ast_hashtab_lookup(con->root_tree,&dummy_exten);
+		if (!tmp2) {
+			/* hmmm, not in the trie; */
+			add_exten_to_pattern_tree(con, tmp);
+		}
+	}
 	res = 0; /* some compilers will think it is uninitialized otherwise */
 	for (e = con->root; e; el = e, e = e->next) {   /* scan the extension list */
 		res = ext_cmp(e->exten, extension);
@@ -5023,10 +5732,50 @@ int ast_add_extension2(struct ast_context *con,
 		 * so insert in the main list right before 'e' (if any)
 		 */
 		tmp->next = e;
-		if (el)
+		if (el) {  /* there is another exten already in this context */
 			el->next = tmp;
-		else
+			tmp->peer_tree = ast_hashtab_create(13,
+							hashtab_compare_exten_numbers,
+							ast_hashtab_resize_java,
+							ast_hashtab_newsize_java,
+							hashtab_hash_priority,
+							1);
+			tmp->peer_label_tree = ast_hashtab_create(7,
+								hashtab_compare_exten_labels,
+								ast_hashtab_resize_java,
+								ast_hashtab_newsize_java,
+								hashtab_hash_labels,
+								1);
+			if (label)
+				ast_hashtab_insert_safe(tmp->peer_label_tree,tmp);
+			ast_hashtab_insert_safe(tmp->peer_tree, tmp);
+
+		} else {  /* this is the first exten in this context */
+			if (!con->root_tree)
+				con->root_tree = ast_hashtab_create(27,
+													hashtab_compare_extens,
+													ast_hashtab_resize_java,
+													ast_hashtab_newsize_java,
+													hashtab_hash_extens,
+													1);
 			con->root = tmp;
+			con->root->peer_tree = ast_hashtab_create(13,
+								hashtab_compare_exten_numbers,
+								ast_hashtab_resize_java,
+								ast_hashtab_newsize_java,
+								hashtab_hash_priority,
+								1);
+			con->root->peer_label_tree = ast_hashtab_create(7,
+									hashtab_compare_exten_labels,
+									ast_hashtab_resize_java,
+									ast_hashtab_newsize_java,
+									hashtab_hash_labels,
+									1);
+			if (label)
+				ast_hashtab_insert_safe(con->root->peer_label_tree,tmp);
+			ast_hashtab_insert_safe(con->root->peer_tree, tmp);
+		}
+		ast_hashtab_insert_safe(con->root_tree, tmp);
 		ast_unlock_context(con);
 		if (tmp->priority == PRIORITY_HINT)
 			ast_add_hint(tmp);
@@ -5461,6 +6210,8 @@ void __ast_context_destroy(struct ast_context *con, const char *registrar)
 			break;
 		ast_wrlock_context(tmp);
 		ast_debug(1, "delete ctx %s %s\n", tmp->name, tmp->registrar);
+		ast_hashtab_remove_this_object(contexts_tree,tmp);
+		
 		next = tmp->next;
 		if (tmpl)
 			tmpl->next = next;
@@ -5479,6 +6230,14 @@ void __ast_context_destroy(struct ast_context *con, const char *registrar)
 			ipi = ipi->next;
 			ast_free(ipl);
 		}
+		/* destroy the hash tabs */
+		if (tmp->root_tree) {
+			ast_hashtab_destroy(tmp->root_tree, 0);
+		}
+		/* and destroy the pattern tree */
+		if (tmp->pattern_tree)
+			destroy_pattern_tree(tmp->pattern_tree);
+		
 		while ((sw = AST_LIST_REMOVE_HEAD(&tmp->alts, list)))
 			ast_free(sw);
 		for (e = tmp->root; e;) {
@@ -6489,7 +7248,7 @@ int ast_context_verify_includes(struct ast_context *con)
 	while ( (inc = ast_walk_context_includes(con, inc)) )
 		if (!ast_context_find(inc->rname)) {
 			res = -1;
-			ast_log(LOG_WARNING, "Context '%s' tries includes nonexistent context '%s'\n",
+			ast_log(LOG_WARNING, "Context '%s' tries to include nonexistent context '%s'\n",
 					ast_get_context_name(con), inc->rname);
 		}
 	return res;
diff --git a/pbx/pbx_ael.c b/pbx/pbx_ael.c
index 521d13ada..e6d1fdc87 100644
--- a/pbx/pbx_ael.c
+++ b/pbx/pbx_ael.c
@@ -123,8 +123,6 @@ static int pbx_load_module(void)
 		rfilename = alloca(strlen(config) + strlen(ast_config_AST_CONFIG_DIR) + 2);
 		sprintf(rfilename, "%s/%s", ast_config_AST_CONFIG_DIR, config);
 	}
-	ast_log(LOG_NOTICE, "AEL load process: calculated config file name '%s'.\n", rfilename);
-
 	if (access(rfilename,R_OK) != 0) {
 		ast_log(LOG_NOTICE, "File %s not found; AEL declining load\n", rfilename);
 		return AST_MODULE_LOAD_DECLINE;
diff --git a/res/ael/pval.c b/res/ael/pval.c
index 5deb01828..923a55148 100644
--- a/res/ael/pval.c
+++ b/res/ael/pval.c
@@ -5409,18 +5409,18 @@ int do_pbx_load_module(void)
 	}
 	
 	parse_tree = ael2_parse(rfilename, &errs);
-	ast_log(LOG_NOTICE, "AEL load process: parsed config file name '%s'.\n", rfilename);
+	ast_log(LOG_DEBUG, "AEL load process: parsed config file name '%s'.\n", rfilename);
 	ael2_semantic_check(parse_tree, &sem_err, &sem_warn, &sem_note);
 	if (errs == 0 && sem_err == 0) {
-		ast_log(LOG_NOTICE, "AEL load process: checked config file name '%s'.\n", rfilename);
+		ast_log(LOG_DEBUG, "AEL load process: checked config file name '%s'.\n", rfilename);
 		ast_compile_ael2(&local_contexts, parse_tree);
-		ast_log(LOG_NOTICE, "AEL load process: compiled config file name '%s'.\n", rfilename);
+		ast_log(LOG_DEBUG, "AEL load process: compiled config file name '%s'.\n", rfilename);
 		
 		ast_merge_contexts_and_delete(&local_contexts, registrar);
-		ast_log(LOG_NOTICE, "AEL load process: merged config file name '%s'.\n", rfilename);
+		ast_log(LOG_DEBUG, "AEL load process: merged config file name '%s'.\n", rfilename);
 		for (con = ast_walk_contexts(NULL); con; con = ast_walk_contexts(con))
 			ast_context_verify_includes(con);
-		ast_log(LOG_NOTICE, "AEL load process: verified config file name '%s'.\n", rfilename);
+		ast_log(LOG_DEBUG, "AEL load process: verified config file name '%s'.\n", rfilename);
 	} else {
 		ast_log(LOG_ERROR, "Sorry, but %d syntax errors and %d semantic errors were detected. It doesn't make sense to compile.\n", errs, sem_err);
 		destroy_pval(parse_tree); /* free up the memory */
diff --git a/utils/Makefile b/utils/Makefile
index a1e89b8c9..504e7f34c 100644
--- a/utils/Makefile
+++ b/utils/Makefile
@@ -16,7 +16,7 @@
 .PHONY: clean all uninstall
 
 # to get check_expr, add it to the ALL_UTILS list
-ALL_UTILS:=astman smsq stereorize streamplayer aelparse muted check_expr conf2ael hashtest2
+ALL_UTILS:=astman smsq stereorize streamplayer aelparse muted check_expr conf2ael hashtest2 hashtest
 UTILS:=$(ALL_UTILS)
 
 include $(ASTTOPDIR)/Makefile.rules
@@ -65,7 +65,7 @@ clean:
 	rm -f *.s *.i
 	rm -f md5.c strcompat.c ast_expr2.c ast_expr2f.c pbx_ael.c pval.c
 	rm -f aelparse.c aelbison.c conf2ael
-	rm -f utils.c threadstorage.c sha1.c astobj2.c hashtest2
+	rm -f utils.c threadstorage.c sha1.c astobj2.c hashtest2 hashtest
 
 md5.c: ../main/md5.c
 	@cp $< $@
@@ -76,6 +76,9 @@ astman: LIBS+=$(NEWT_LIB)
 stereorize: stereorize.o frame.o
 stereorize: LIBS+=-lm
 
+hashtab.c: ../main/hashtab.c
+	@cp $< $@
+
 strcompat.c: ../main/strcompat.c
 	@cp $< $@
 
@@ -100,7 +103,7 @@ ast_expr2f.o: ASTCFLAGS+=-DSTANDALONE_AEL -I../main
 
 pval.o : ASTCFLAGS+=-DSTANDALONE
 
-check_expr: check_expr.o ast_expr2.o ast_expr2f.o strcompat.o clicompat.o threadstorage.o
+check_expr: check_expr.o ast_expr2.o ast_expr2f.o strcompat.o threadstorage.o
 
 aelbison.c: ../res/ael/ael.tab.c
 	@cp $< $@
@@ -135,6 +138,11 @@ hashtest2.o: ASTCFLAGS+=-O0
 
 hashtest2: hashtest2.o md5.o utils.o astobj2.o sha1.o strcompat.o threadstorage.o clicompat.o
 
+hashtest: hashtest.o md5.o hashtab.o utils.o sha1.o strcompat.o threadstorage.o
+
+hashtest.o : hashtest.c
+	$(CC) -g -O0 -c hashtest.c -I/usr/include -I../include
+
 extconf.o : extconf.c
 
 conf2ael: conf2ael.o ast_expr2f.o ast_expr2.o aelbison.o aelparse.o pbx_ael.o pval.o extconf.o strcompat.o
diff --git a/utils/hashtest.c b/utils/hashtest.c
new file mode 100644
index 000000000..aa359ca53
--- /dev/null
+++ b/utils/hashtest.c
@@ -0,0 +1,387 @@
+/*
+ * Asterisk -- An open source telephony toolkit.
+ *
+ * Copyright (C) 2007, Steve Murphy
+ *
+ * Steve Murphy <murf@digium.com>
+ *
+ * See http://www.asterisk.org for more information about
+ * the Asterisk project. Please do not directly contact
+ * any of the maintainers of this project for assistance;
+ * the project provides a web site, mailing lists and IRC
+ * channels for your use.
+ *
+ * This program is free software, distributed under the terms of
+ * the GNU General Public License Version 2. See the LICENSE file
+ * at the top of the source tree.
+ */
+/*! \file
+ *
+ *  \brief A program to thoroughly thrash a hash table, testing
+ *         out locking safety, and making sure all functionality
+ *         is functioning. Run with 5 or more threads to get that
+ *         fully intense firestorm of activity. If your
+ *         hash tables don't crash, lock up, or go weird, it must
+ *         be good code! Even features some global counters
+ *         that will get slightly behind because they aren't lock-protected.
+ *
+ *  \author Steve Murphy <murf@digium.com>
+ */
+
+#include "asterisk.h"
+
+#include <sys/types.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdarg.h>
+#include <alloca.h>
+#include <string.h>
+#include <pthread.h>
+#include <sys/stat.h>
+#include <signal.h>
+#include <errno.h>
+#include <unistd.h>
+#include "asterisk/lock.h"
+#include "asterisk/hashtab.h"
+#include "asterisk/channel.h"
+#include "asterisk/utils.h"
+#include "asterisk/module.h"
+int testno = 1;
+
+/* stuff we need to make this work with the hashtab stuff */
+
+void ast_cli(int *fd, char *str, ...)
+{
+}
+
+int64_t ast_mark(int prof_id, int x)
+{
+}
+
+struct ht_element 
+{
+	char *key;
+	char *val;
+};
+
+static int hashtab_compare_strings_nocase(const void *a, const void *b)
+{
+	const struct ht_element *ae = a, *be = b;
+	return ast_hashtab_compare_strings_nocase(ae->key, be->key);
+}
+
+static int hashtab_compare_strings(const void *a, const void *b)
+{
+	const struct ht_element *ae = a, *be = b;
+	return ast_hashtab_compare_strings(ae->key, be->key);
+}
+
+static unsigned int hashtab_hash_string(const void *obj)
+{
+	const struct ht_element *o = obj;
+	return ast_hashtab_hash_string((const void *)o->key);
+}
+
+static unsigned int hashtab_hash_string_nocase(const void *obj)
+{
+	const struct ht_element *o = obj;
+	return ast_hashtab_hash_string_nocase((const void*)o->key);
+}
+
+/* random numbers */
+
+my_rand(int incl_low, int incl_high, unsigned int *seedp)
+{
+	if (incl_high == 0)
+		return 0;
+	
+	return incl_low + (rand_r(seedp) % incl_high);
+}
+
+
+
+
+/* the testing routines */
+
+static int glob_highwater = 0;
+struct ast_hashtab *glob_hashtab = 0;
+unsigned int glob_seed = 0;
+int els_removed = 0;
+int els_added = 0;
+int els_lookedup = 0;
+int els_found = 0;
+int els_traversals = 0;
+
+/* all the operations to perform on the hashtab */
+
+static void add_element(void)
+{
+	char keybuf[100];
+	struct ht_element *x = malloc(sizeof(struct ht_element));
+	sprintf(keybuf,"key%08d", glob_highwater++);
+	x->key = strdup(keybuf);
+	x->val = strdup("interesting data");
+	ast_hashtab_insert_immediate(glob_hashtab, x);
+	els_added++;
+}
+
+static void traverse_elements(void)
+{
+	struct ht_element *el;
+	int c=0;
+	struct ast_hashtab_iter *it = ast_hashtab_start_write_traversal(glob_hashtab);
+#ifdef DEBUG
+	printf("Traverse hashtab\n");
+#endif
+	while ((el = ast_hashtab_next(it))) {
+		c++;
+	}
+	ast_hashtab_end_traversal(it);
+	els_traversals++; /* unprotected, sometimes off, but, not really important, either */
+}
+
+static void * del_element(unsigned int *seedp)
+{
+	char keybuf[100];
+	struct ht_element *el, lookup;
+	int x;
+	
+	/* pick a random element from 0 to highwater-1 */
+	x = my_rand(0,glob_highwater-1,seedp);
+	sprintf(keybuf, "key%08d", x);
+#if DEBUG
+	printf("Removing %s", keybuf);
+#endif
+	lookup.key = keybuf;
+	el = ast_hashtab_remove_object_via_lookup(glob_hashtab, &lookup);
+	
+	if (el) {
+#if DEBUG
+		printf("...YES (el=%x)\n", (unsigned long)el);
+#endif
+		free(el->key);
+		free(el->val);
+		free(el);
+		els_removed++;
+	} else {
+#if DEBUG
+		printf("...NO.\n");
+#endif
+		return 0;
+	}
+	
+	
+	return el;
+}
+
+static int lookup_element(unsigned int *seedp)
+{
+	char keybuf[100];
+	struct ht_element *el, lookup;
+	int x;
+	
+	/* pick a random element from 0 to highwater-1 */
+	x = my_rand(0,glob_highwater-1,seedp);
+	sprintf(keybuf, "key%08d", x);
+	lookup.key = keybuf;
+	el = ast_hashtab_lookup(glob_hashtab, &lookup);
+	els_lookedup++;
+	if (el)
+		els_found++;
+	if (el)
+		return 1;
+	return 0;
+}
+
+
+static void *hashtest(void *data)
+{
+	int my_els_removed = 0;
+	int my_els_added = 0;
+	int my_els_lookedup = 0;
+	int my_els_found = 0;
+	int my_els_traversals = 0;
+	int my_testno = testno++;
+	
+	/* data will be a random number == use as a seed for random numbers */
+	unsigned long seed = (unsigned long)data;
+	printf("hashtest thread created... test beginning\n");
+	
+	/* main test routine-- a global hashtab exists, pound it like crazy  */
+	int its;
+	for(its=0;its<100000;its++)
+	{
+		void *seed2 = &seed;
+		int op = my_rand(0,100, seed2);
+		if (op<60) {
+			my_els_lookedup++;
+#ifdef DEBUG
+			printf("%d[%d]: LOOKUP\n", my_testno, its);
+#endif			
+			if ((my_els_lookedup%1000)==0) {
+				printf(".");
+				fflush(stdout);
+			}
+			if (lookup_element(seed2))
+				my_els_found++;
+		} else if (op < 61) { /* make this 61 and it'll take 15 minutes to run */
+#ifdef DEBUG
+			printf("%d[%d]: TRAVERSE\n", my_testno, its);
+#endif
+			traverse_elements();
+			my_els_traversals++;
+			
+		} else if (op < 80) {
+#ifdef DEBUG
+			printf("%d[%d]: REMOVE\n", my_testno, its);
+#endif
+			if (del_element(seed2))
+				my_els_removed++;
+		} else {
+			my_els_added++;
+#ifdef DEBUG
+			printf("%d[%d]: ADD\n", my_testno, its);
+#endif
+			add_element();
+		}
+	}
+	printf("\nhashtest thread %d exiting.... lookups=%d/%d, added=%d, removed=%d, traversals=%d;\n",
+		   my_testno, my_els_found, my_els_lookedup, my_els_added, my_els_removed, my_els_traversals);
+	printf("\ntotals..................... lookups=%d/%d, added=%d, removed=%d, traversals=%d;\n",
+		   els_found, els_lookedup, els_added, els_removed,els_traversals);
+	pthread_exit(0);
+}
+
+void run_hashtest(int numthr)
+{
+	pthread_t thr[numthr];
+	void *thrres[numthr];
+	int i, biggest, resize_cnt, numobjs, numbuckets;
+	
+	/* init a single global hashtab, then... */
+	glob_hashtab = ast_hashtab_create(180000, hashtab_compare_strings_nocase, ast_hashtab_resize_java, ast_hashtab_newsize_java, hashtab_hash_string_nocase, 1);
+	printf("starting with %d elements in the hashtable...\n", ast_hashtab_capacity(glob_hashtab));
+	/* set a random seed  */
+	glob_seed = (unsigned int)time(0);
+	srand(glob_seed);
+	
+	/* create threads, each running hashtest */
+	for(i=0;i<numthr;i++)
+	{
+		unsigned long z = rand();
+		
+		printf("starting hashtest thread %d....\n",i+1);
+		if (ast_pthread_create(&thr[i], NULL, hashtest, (void*)z)) {
+			printf("Sorry, couldn't create thread #%d\n", i+1);
+		}
+		printf("hashtest thread spawned.... \n");
+	}
+	/* collect threads, each running hashtest */
+	for(i=0;i<numthr;i++)
+	{
+		printf("waiting for thread %d....\n", i+1);
+		if (pthread_join(thr[i], &thrres[i])) {
+			printf("Sorry, couldn't join thread #%d\n", i+1);
+		}
+		printf("hashtest thread %d done.... \n",i+1);
+	}
+	/* user has to kill/intr the process to stop the test? */
+	ast_hashtab_get_stats(glob_hashtab, &biggest, &resize_cnt, &numobjs, &numbuckets);
+	printf("Some stats: longest bucket chain: %d;  number of resizes: %d; number of objects: %d;  capacity: %d\n",
+			biggest, resize_cnt, numobjs, numbuckets);
+}
+
+
+int main(int argc,char **argv)
+{
+	if (argc < 2 || argc > 2 || atoi(argv[1]) < 1)
+	{
+		printf("Usage: hashtest <number of threads>\n");
+		exit(1);
+	}
+	
+	/* one arg == number of threads to create */
+	run_hashtest(atoi(argv[1]));
+	
+	return 0;
+}
+
+
+struct ast_app *pbx_findapp(const char *app)
+{
+	return (struct ast_app*)1; /* so as not to trigger an error */
+}
+
+int  ast_add_profile(const char *x, uint64_t scale)
+{
+}
+
+int ast_loader_register(int (*updater)(void))
+{
+	return 1;
+}
+
+int ast_loader_unregister(int (*updater)(void))
+{
+	return 1;
+}
+void ast_module_register(const struct ast_module_info *x)
+{
+}
+
+void ast_module_unregister(const struct ast_module_info *x)
+{
+}
+
+
+void ast_cli_register_multiple(void)
+{
+}
+
+void ast_register_file_version(const char *file, const char *version)
+{
+}
+
+void ast_unregister_file_version(const char *file)
+{
+
+}
+
+void ast_cli_unregister_multiple(void)
+{
+}
+
+void ast_context_destroy(void)
+{
+}
+
+void ast_log(int level, const char *file, int line, const char *function, const char *fmt, ...)
+{
+	va_list vars;
+	va_start(vars,fmt);
+	printf("LOG: lev:%d file:%s  line:%d func: %s  ",
+		   level, file, line, function);
+	vprintf(fmt, vars);
+	fflush(stdout);
+	va_end(vars);
+}
+
+void ast_verbose(const char *fmt, ...)
+{
+        va_list vars;
+        va_start(vars,fmt);
+
+        printf("VERBOSE: ");
+        vprintf(fmt, vars);
+        fflush(stdout);
+        va_end(vars);
+}
+
+void ast_register_thread(char *name)
+{
+
+}
+
+void ast_unregister_thread(void *id)
+{
+}