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