This is the perhaps the biggest, boldest, most daring change I've ever committed...
authorSteve Murphy <murf@digium.com>
Fri, 9 Nov 2007 16:00:22 +0000 (16:00 +0000)
committerSteve Murphy <murf@digium.com>
Fri, 9 Nov 2007 16:00:22 +0000 (16:00 +0000)
git-svn-id: https://origsvn.digium.com/svn/asterisk/trunk@89129 65c4cc65-6c06-0410-ace0-fbb531ad65f3

include/asterisk/hashtab.h [new file with mode: 0644]
main/Makefile
main/config.c
main/hashtab.c [new file with mode: 0644]
main/pbx.c
pbx/pbx_ael.c
res/ael/pval.c
utils/Makefile
utils/hashtest.c [new file with mode: 0644]

diff --git a/include/asterisk/hashtab.h b/include/asterisk/hashtab.h
new file mode 100644 (file)
index 0000000..f40324b
--- /dev/null
@@ -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
index 3f18159..25fb79a 100644 (file)
@@ -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
index 59b1840..614c6c9 100644 (file)
@@ -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 (file)
index 0000000..7c4adf8
--- /dev/null
@@ -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;
+}
index d3949ec..483bb76 100644 (file)
@@ -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;
index 521d13a..e6d1fdc 100644 (file)
@@ -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;
index 5deb018..923a551 100644 (file)
@@ -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 */
index a1e89b8..504e7f3 100644 (file)
@@ -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 (file)
index 0000000..aa359ca
--- /dev/null
@@ -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)
+{
+}