pbx.c

Go to the documentation of this file.

/*
 * Asterisk -- An open source telephony toolkit.
 *
 * Copyright (C) 1999 - 2008, Digium, Inc.
 *
 * Mark Spencer <[email protected]>
 *
 * 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 Core PBX routines.
 *
 * \author Mark Spencer <[email protected]>
 */

/*** MODULEINFO
 <support_level>core</support_level>
 ***/

#include "asterisk.h"

#include "asterisk/_private.h"
#include "asterisk/paths.h" /* use ast_config_AST_SYSTEM_NAME */
#include <ctype.h>
#include <time.h>
#include <sys/time.h>
#if defined(HAVE_SYSINFO)
#include <sys/sysinfo.h>
#endif
#if defined(SOLARIS)
#include <sys/loadavg.h>
#endif

#include "asterisk/lock.h"
#include "asterisk/cli.h"
#include "asterisk/pbx.h"
#include "asterisk/channel.h"
#include "asterisk/file.h"
#include "asterisk/callerid.h"
#include "asterisk/cdr.h"
#include "asterisk/config.h"
#include "asterisk/term.h"
#include "asterisk/time.h"
#include "asterisk/manager.h"
#include "asterisk/ast_expr.h"
#include "asterisk/linkedlists.h"
#define SAY_STUBS /* generate declarations and stubs for say methods */
#include "asterisk/say.h"
#include "asterisk/utils.h"
#include "asterisk/causes.h"
#include "asterisk/musiconhold.h"
#include "asterisk/app.h"
#include "asterisk/devicestate.h"
#include "asterisk/presencestate.h"
#include "asterisk/hashtab.h"
#include "asterisk/module.h"
#include "asterisk/indications.h"
#include "asterisk/taskprocessor.h"
#include "asterisk/xmldoc.h"
#include "asterisk/astobj2.h"
#include "asterisk/stasis_channels.h"
#include "asterisk/dial.h"
#include "asterisk/vector.h"
#include "pbx_private.h"

/*!
 * \note I M P O R T A N T :
 *
 * The speed of extension handling will likely be among the most important
 * aspects of this PBX. The switching scheme as it exists right now isn't
 * 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
 * 10000 patterns.
 *
 * Also, using a hash table for context/priority name lookup can help prevent
 * the find_extension routines from absorbing exponential cpu cycles as the number
 * of contexts/priorities grow. I've previously 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. While these techniques do not yield much
 * speed in small dialplans, they are worth the trouble in large dialplans.
 *
 */

/*** DOCUMENTATION
 <function name="EXCEPTION" language="en_US">
 <synopsis>
 Retrieve the details of the current dialplan exception.
 </synopsis>
 <syntax>
 <parameter name="field" required="true">
 <para>The following fields are available for retrieval:</para>
 <enumlist>
 <enum name="reason">
 <para>INVALID, ERROR, RESPONSETIMEOUT, ABSOLUTETIMEOUT, or custom
 value set by the RaiseException() application</para>
 </enum>
 <enum name="context">
 <para>The context executing when the exception occurred.</para>
 </enum>
 <enum name="exten">
 <para>The extension executing when the exception occurred.</para>
 </enum>
 <enum name="priority">
 <para>The numeric priority executing when the exception occurred.</para>
 </enum>
 </enumlist>
 </parameter>
 </syntax>
 <description>
 <para>Retrieve the details (specified <replaceable>field</replaceable>) of the current dialplan exception.</para>
 </description>
 <see-also>
 <ref type="application">RaiseException</ref>
 </see-also>
 </function>
 <function name="TESTTIME" language="en_US">
 <synopsis>
 Sets a time to be used with the channel to test logical conditions.
 </synopsis>
 <syntax>
 <parameter name="date" required="true" argsep=" ">
 <para>Date in ISO 8601 format</para>
 </parameter>
 <parameter name="time" required="true" argsep=" ">
 <para>Time in HH:MM:SS format (24-hour time)</para>
 </parameter>
 <parameter name="zone" required="false">
 <para>Timezone name</para>
 </parameter>
 </syntax>
 <description>
 <para>To test dialplan timing conditions at times other than the current time, use
 this function to set an alternate date and time. For example, you may wish to evaluate
 whether a location will correctly identify to callers that the area is closed on Christmas
 Day, when Christmas would otherwise fall on a day when the office is normally open.</para>
 </description>
 <see-also>
 <ref type="application">GotoIfTime</ref>
 </see-also>
 </function>
 <manager name="ShowDialPlan" language="en_US">
 <synopsis>
 Show dialplan contexts and extensions
 </synopsis>
 <syntax>
 <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
 <parameter name="Extension">
 <para>Show a specific extension.</para>
 </parameter>
 <parameter name="Context">
 <para>Show a specific context.</para>
 </parameter>
 </syntax>
 <description>
 <para>Show dialplan contexts and extensions. Be aware that showing the full dialplan
 may take a lot of capacity.</para>
 </description>
 </manager>
 <manager name="ExtensionStateList" language="en_US">
 <synopsis>
 List the current known extension states.
 </synopsis>
 <syntax>
 <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
 </syntax>
 <description>
 <para>This will list out all known extension states in a
 sequence of <replaceable>ExtensionStatus</replaceable> events.
 When finished, a <replaceable>ExtensionStateListComplete</replaceable> event
 will be emitted.</para>
 </description>
 <see-also>
 <ref type="manager">ExtensionState</ref>
 <ref type="function">HINT</ref>
 <ref type="function">EXTENSION_STATE</ref>
 </see-also>
 <responses>
 <list-elements>
 <xi:include xpointer="xpointer(/docs/managerEvent[@name='ExtensionStatus'])" />
 </list-elements>
 <managerEvent name="ExtensionStateListComplete" language="en_US">
 <managerEventInstance class="EVENT_FLAG_COMMAND">
 <synopsis>
 Indicates the end of the list the current known extension states.
 </synopsis>
 <syntax>
 <parameter name="EventList">
 <para>Conveys the status of the event list.</para>
 </parameter>
 <parameter name="ListItems">
 <para>Conveys the number of statuses reported.</para>
 </parameter>
 </syntax>
 </managerEventInstance>
 </managerEvent>
 </responses>
 </manager>
 ***/

#ifdef LOW_MEMORY
#define EXT_DATA_SIZE 256
#else
#define EXT_DATA_SIZE 8192
#endif

#define SWITCH_DATA_LENGTH 256

#define VAR_NORMAL 1
#define VAR_SOFTTRAN 2
#define VAR_HARDTRAN 3

struct ast_context;
struct ast_app;

AST_THREADSTORAGE(switch_data);
AST_THREADSTORAGE(extensionstate_buf);

/*!
 \brief ast_exten: An extension
 The dialplan is saved as a linked list with each context
 having it's own linked list of extensions - one item per
 priority.
*/
struct ast_exten {
 char *exten; /*!< Clean Extension id */
 char *name; /*!< Extension name (may include '-' eye candy) */
 int matchcid; /*!< Match caller id ? */
 const char *cidmatch; /*!< Caller id to match for this extension */
 const char *cidmatch_display; /*!< Caller id to match (display version) */
 int priority; /*!< Priority */
 const char *label; /*!< Label */
 struct ast_context *parent; /*!< The context this extension belongs to */
 const char *app; /*!< Application to execute */
 struct ast_app *cached_app; /*!< Cached location of application */
 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_table; /*!< Priorities list in hashtab form -- only on the head of the peer list */
 struct ast_hashtab *peer_label_table; /*!< labeled priorities in the peers -- only on the head of the peer list */
 const char *registrar; /*!< Registrar */
 const char *registrar_file; /*!< File name used to register extension */
 int registrar_line; /*!< Line number the extension was registered in text */
 struct ast_exten *next; /*!< Extension with a greater ID */
 char stuff[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 */
 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 */
 char x[1]; /* the pattern itself-- matches a single char */
};

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 match_char *node;
 struct ast_exten *canmatch_exten;
 struct ast_exten *exten;
};

/*! \brief ast_context: An extension context - must remain in sync with fake_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_table; /*!< 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_includes includes; /*!< Include other contexts */
 struct ast_ignorepats ignorepats; /*!< Patterns for which to continue playing dialtone */
 struct ast_sws alts; /*!< Alternative switches */
 char *registrar; /*!< Registrar -- make sure you malloc this, as the registrar may have to survive module unloads */
 int refcount; /*!< each module that would have created this context should inc/dec this as appropriate */
 int autohints; /*!< Whether autohints support is enabled or not */
 ast_mutex_t macrolock; /*!< A lock to implement "exclusive" macros - held whilst a call is executing in the macro */
 char name[0]; /*!< Name of the context */
};

/*! \brief ast_state_cb: An extension state notify register item */
struct ast_state_cb {
 /*! Watcher ID returned when registered. */
 int id;
 /*! Arbitrary data passed for callbacks. */
 void *data;
 /*! Flag if this callback is an extended callback containing detailed device status */
 int extended;
 /*! Callback when state changes. */
 ast_state_cb_type change_cb;
 /*! Callback when destroyed so any resources given by the registerer can be freed. */
 ast_state_cb_destroy_type destroy_cb;
 /*! \note Only used by ast_merge_contexts_and_delete */
 AST_LIST_ENTRY(ast_state_cb) entry;
};

/*!
 * \brief Structure for dial plan hints
 *
 * \note Hints are pointers from an extension in the dialplan to
 * one or more devices (tech/name)
 *
 * See \ref AstExtState
 */
struct ast_hint {
 /*!
 * \brief Hint extension
 *
 * \note
 * Will never be NULL while the hint is in the hints container.
 */
 struct ast_exten *exten;
 struct ao2_container *callbacks; /*!< Device state callback container for this extension */

 /*! Dev state variables */
 int laststate; /*!< Last known device state */

 /*! Presence state variables */
 int last_presence_state; /*!< Last known presence state */
 char *last_presence_subtype; /*!< Last known presence subtype string */
 char *last_presence_message; /*!< Last known presence message string */

 char context_name[AST_MAX_CONTEXT];/*!< Context of destroyed hint extension. */
 char exten_name[AST_MAX_EXTENSION];/*!< Extension of destroyed hint extension. */

 AST_VECTOR(, char *) devices; /*!< Devices associated with the hint */
};

STASIS_MESSAGE_TYPE_DEFN_LOCAL(hint_change_message_type);
STASIS_MESSAGE_TYPE_DEFN_LOCAL(hint_remove_message_type);

#define HINTDEVICE_DATA_LENGTH 16
AST_THREADSTORAGE(hintdevice_data);

/* --- Hash tables of various objects --------*/
#ifdef LOW_MEMORY
#define HASH_EXTENHINT_SIZE 17
#else
#define HASH_EXTENHINT_SIZE 563
#endif


/*! \brief Container for hint devices */
static struct ao2_container *hintdevices;

/*!
 * \brief Structure for dial plan hint devices
 * \note hintdevice is one device pointing to a hint.
 */
struct ast_hintdevice {
 /*!
 * \brief Hint this hintdevice belongs to.
 * \note Holds a reference to the hint object.
 */
 struct ast_hint *hint;
 /*! Name of the hint device. */
 char hintdevice[1];
};

/*! \brief Container for autohint contexts */
static struct ao2_container *autohints;

/*!
 * \brief Structure for dial plan autohints
 */
struct ast_autohint {
 /*! \brief Name of the registrar */
 char *registrar;
 /*! \brief Name of the context */
 char context[1];
};

/*!
 * \note Using the device for hash
 */
static int hintdevice_hash_cb(const void *obj, const int flags)
{
 const struct ast_hintdevice *ext;
 const char *key;

 switch (flags & OBJ_SEARCH_MASK) {
 case OBJ_SEARCH_KEY:
 key = obj;
 break;
 case OBJ_SEARCH_OBJECT:
 ext = obj;
 key = ext->hintdevice;
 break;
 default:
 ast_assert(0);
 return 0;
 }

 return ast_str_case_hash(key);
}

/*!
 * \note Devices on hints are not unique so no CMP_STOP is returned
 * Dont use ao2_find against hintdevices container cause there always
 * could be more than one result.
 */
static int hintdevice_cmp_multiple(void *obj, void *arg, int flags)
{
 struct ast_hintdevice *left = obj;
 struct ast_hintdevice *right = arg;
 const char *right_key = arg;
 int cmp;

 switch (flags & OBJ_SEARCH_MASK) {
 case OBJ_SEARCH_OBJECT:
 right_key = right->hintdevice;
 /* Fall through */
 case OBJ_SEARCH_KEY:
 cmp = strcasecmp(left->hintdevice, right_key);
 break;
 case OBJ_SEARCH_PARTIAL_KEY:
 /*
 * We could also use a partial key struct containing a length
 * so strlen() does not get called for every comparison instead.
 */
 cmp = strncmp(left->hintdevice, right_key, strlen(right_key));
 break;
 default:
 ast_assert(0);
 cmp = 0;
 break;
 }
 return cmp ? 0 : CMP_MATCH;
}

/*!
 * \note Using the context name for hash
 */
static int autohint_hash_cb(const void *obj, const int flags)
{
 const struct ast_autohint *autohint;
 const char *key;

 switch (flags & OBJ_SEARCH_MASK) {
 case OBJ_SEARCH_KEY:
 key = obj;
 break;
 case OBJ_SEARCH_OBJECT:
 autohint = obj;
 key = autohint->context;
 break;
 default:
 ast_assert(0);
 return 0;
 }

 return ast_str_case_hash(key);
}

static int autohint_cmp(void *obj, void *arg, int flags)
{
 struct ast_autohint *left = obj;
 struct ast_autohint *right = arg;
 const char *right_key = arg;
 int cmp;

 switch (flags & OBJ_SEARCH_MASK) {
 case OBJ_SEARCH_OBJECT:
 right_key = right->context;
 /* Fall through */
 case OBJ_SEARCH_KEY:
 cmp = strcasecmp(left->context, right_key);
 break;
 case OBJ_SEARCH_PARTIAL_KEY:
 /*
 * We could also use a partial key struct containing a length
 * so strlen() does not get called for every comparison instead.
 */
 cmp = strncmp(left->context, right_key, strlen(right_key));
 break;
 default:
 ast_assert(0);
 cmp = 0;
 break;
 }
 return cmp ? 0 : CMP_MATCH | CMP_STOP;
}

/*! \internal \brief \c ao2_callback function to remove hintdevices */
static int hintdevice_remove_cb(void *obj, void *arg, void *data, int flags)
{
 struct ast_hintdevice *candidate = obj;
 char *device = arg;
 struct ast_hint *hint = data;

 if (!strcasecmp(candidate->hintdevice, device)
 && candidate->hint == hint) {
 return CMP_MATCH;
 }
 return 0;
}

static int remove_hintdevice(struct ast_hint *hint)
{
 while (AST_VECTOR_SIZE(&hint->devices) > 0) {
 char *device = AST_VECTOR_GET(&hint->devices, 0);

 ao2_t_callback_data(hintdevices, OBJ_SEARCH_KEY | OBJ_UNLINK | OBJ_NODATA,
 hintdevice_remove_cb, device, hint, "Remove device from container");
 AST_VECTOR_REMOVE_UNORDERED(&hint->devices, 0);
 ast_free(device);
 }

 return 0;
}

static char *parse_hint_device(struct ast_str *hint_args);
/*!
 * \internal
 * \brief Destroy the given hintdevice object.
 *
 * \param obj Hint device to destroy.
 *
 * \return Nothing
 */
static void hintdevice_destroy(void *obj)
{
 struct ast_hintdevice *doomed = obj;

 if (doomed->hint) {
 ao2_ref(doomed->hint, -1);
 doomed->hint = NULL;
 }
}

/*! \brief add hintdevice structure and link it into the container.
 */
static int add_hintdevice(struct ast_hint *hint, const char *devicelist)
{
 struct ast_str *str;
 char *parse;
 char *cur;
 struct ast_hintdevice *device;
 int devicelength;

 if (!hint || !devicelist) {
 /* Trying to add garbage? Don't bother. */
 return 0;
 }
 if (!(str = ast_str_thread_get(&hintdevice_data, 16))) {
 return -1;
 }
 ast_str_set(&str, 0, "%s", devicelist);
 parse = ast_str_buffer(str);

 /* Spit on '&' and ',' to handle presence hints as well */
 while ((cur = strsep(&parse, "&,"))) {
 char *device_name;

 devicelength = strlen(cur);
 if (!devicelength) {
 continue;
 }

 device_name = ast_strdup(cur);
 if (!device_name) {
 return -1;
 }

 device = ao2_t_alloc(sizeof(*device) + devicelength, hintdevice_destroy,
 "allocating a hintdevice structure");
 if (!device) {
 ast_free(device_name);
 return -1;
 }
 strcpy(device->hintdevice, cur);
 ao2_ref(hint, +1);
 device->hint = hint;
 if (AST_VECTOR_APPEND(&hint->devices, device_name)) {
 ast_free(device_name);
 ao2_ref(device, -1);
 return -1;
 }
 ao2_t_link(hintdevices, device, "Linking device into hintdevice container.");
 ao2_t_ref(device, -1, "hintdevice is linked so we can unref");
 }

 return 0;
}


static const struct cfextension_states {
 int extension_state;
 const char * const text;
} extension_states[] = {
 { AST_EXTENSION_NOT_INUSE, "Idle" },
 { AST_EXTENSION_INUSE, "InUse" },
 { AST_EXTENSION_BUSY, "Busy" },
 { AST_EXTENSION_UNAVAILABLE, "Unavailable" },
 { AST_EXTENSION_RINGING, "Ringing" },
 { AST_EXTENSION_INUSE | AST_EXTENSION_RINGING, "InUse&Ringing" },
 { AST_EXTENSION_ONHOLD, "Hold" },
 { AST_EXTENSION_INUSE | AST_EXTENSION_ONHOLD, "InUse&Hold" }
};

struct pbx_exception {
 AST_DECLARE_STRING_FIELDS(
 AST_STRING_FIELD(context); /*!< Context associated with this exception */
 AST_STRING_FIELD(exten); /*!< Exten associated with this exception */
 AST_STRING_FIELD(reason); /*!< The exception reason */
 );

 int priority; /*!< Priority associated with this exception */
};

static int matchcid(const char *cidpattern, const char *callerid);
#ifdef NEED_DEBUG
static void log_match_char_tree(struct match_char *node, char *prefix); /* for use anywhere */
#endif
static void new_find_extension(const char *str, struct scoreboard *score,
 struct match_char *tree, int length, int spec, const char *callerid,
 const char *label, enum ext_match_t action);
static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern);
static struct match_char *add_exten_to_pattern_tree(struct ast_context *con,
 struct ast_exten *e1, int findonly);
static void create_match_char_tree(struct ast_context *con);
static struct ast_exten *get_canmatch_exten(struct match_char *node);
static void destroy_pattern_tree(struct match_char *pattern_tree);
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_extens(const void *obj);
static unsigned int hashtab_hash_priority(const void *obj);
static unsigned int hashtab_hash_labels(const void *obj);
static void __ast_internal_context_destroy( struct ast_context *con);
static int ast_add_extension_nolock(const char *context, int replace, const char *extension,
 int priority, const char *label, const char *callerid,
 const char *application, void *data, void (*datad)(void *), const char *registrar);
static int ast_add_extension2_lockopt(struct ast_context *con,
 int replace, const char *extension, int priority, const char *label, const char *callerid,
 const char *application, void *data, void (*datad)(void *),
 const char *registrar, const char *registrar_file, int registrar_line,
 int lock_context);
static struct ast_context *find_context_locked(const char *context);
static struct ast_context *find_context(const char *context);
static void get_device_state_causing_channels(struct ao2_container *c);
static unsigned int ext_strncpy(char *dst, const char *src, size_t dst_size, int nofluff);

/*!
 * \internal
 * \brief Character array comparison function for qsort.
 *
 * \param a Left side object.
 * \param b Right side object.
 *
 * \retval <0 if a < b
 * \retval =0 if a = b
 * \retval >0 if a > b
 */
static int compare_char(const void *a, const void *b)
{
 const unsigned char *ac = a;
 const unsigned char *bc = b;

 return *ac - *bc;
}

/* labels, contexts are case sensitive priority numbers are ints */
int ast_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;
 if (!ac || !bc) /* safety valve, but it might prevent a crash you'd rather have happen */
 return 1;
 /* 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? */
 /* not sure which side may be using ast_ext_matchcid_types, so check both */
 if (ac->matchcid == AST_EXT_MATCHCID_ANY || bc->matchcid == AST_EXT_MATCHCID_ANY) {
 return 0;
 }
 if (ac->matchcid == AST_EXT_MATCHCID_OFF && bc->matchcid == AST_EXT_MATCHCID_OFF) {
 return 0;
 }
 if (ac->matchcid != bc->matchcid) {
 return 1;
 }
 /* all other cases already disposed of, match now required on callerid string (cidmatch) */
 /* although ast_add_extension2_lockopt() enforces non-zero ptr, caller may not have */
 if (ast_strlen_zero(ac->cidmatch) && ast_strlen_zero(bc->cidmatch)) {
 return 0;
 }
 return strcmp(ac->cidmatch, bc->cidmatch);
}

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(S_OR(ac->label, ""), S_OR(bc->label, ""));
}

unsigned int ast_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 == AST_EXT_MATCHCID_ON)
 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(S_OR(ac->label, ""));
}

static int autofallthrough = 1;
static int extenpatternmatchnew = 0;
static char *overrideswitch = NULL;

/*! \brief Subscription for device state change events */
static struct stasis_subscription *device_state_sub;
/*! \brief Subscription for presence state change events */
static struct stasis_subscription *presence_state_sub;

AST_MUTEX_DEFINE_STATIC(maxcalllock);
static int countcalls;
static int totalcalls;

static struct ast_context *contexts;
static struct ast_hashtab *contexts_table = NULL;

/*!
 * \brief Lock for the ast_context list
 * \note
 * This lock MUST be recursive, or a deadlock on reload may result. See
 * https://issues.asterisk.org/view.php?id=17643
 */
AST_MUTEX_DEFINE_STATIC(conlock);

/*!
 * \brief Lock to hold off restructuring of hints by ast_merge_contexts_and_delete.
 */
AST_MUTEX_DEFINE_STATIC(context_merge_lock);

static int stateid = 1;
/*!
 * \note When holding this container's lock, do _not_ do
 * anything that will cause conlock to be taken, unless you
 * _already_ hold it. The ast_merge_contexts_and_delete function
 * will take the locks in conlock/hints order, so any other
 * paths that require both locks must also take them in that
 * order.
 */
static struct ao2_container *hints;

static struct ao2_container *statecbs;

#ifdef CONTEXT_DEBUG

/* these routines are provided for doing run-time checks
 on the extension structures, in case you are having
 problems, this routine might help you localize where
 the problem is occurring. It's kinda like a debug memory
 allocator's arena checker... It'll eat up your cpu cycles!
 but you'll see, if you call it in the right places,
 right where your problems began...
*/

/* you can break on the check_contexts_trouble()
routine in your debugger to stop at the moment
there's a problem */
void check_contexts_trouble(void);

void check_contexts_trouble(void)
{
 int x = 1;
 x = 2;
}

int check_contexts(char *, int);

int check_contexts(char *file, int line )
{
 struct ast_hashtab_iter *t1;
 struct ast_context *c1, *c2;
 int found = 0;
 struct ast_exten *e1, *e2, *e3;
 struct ast_exten ex;

 /* try to find inconsistencies */
 /* is every context in the context table in the context list and vice-versa ? */

 if (!contexts_table) {
 ast_log(LOG_NOTICE,"Called from: %s:%d: No contexts_table!\n", file, line);
 usleep(500000);
 }

 t1 = ast_hashtab_start_traversal(contexts_table);
 while( (c1 = ast_hashtab_next(t1))) {
 for(c2=contexts;c2;c2=c2->next) {
 if (!strcmp(c1->name, c2->name)) {
 found = 1;
 break;
 }
 }
 if (!found) {
 ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the linked list\n", file, line, c1->name);
 check_contexts_trouble();
 }
 }
 ast_hashtab_end_traversal(t1);
 for(c2=contexts;c2;c2=c2->next) {
 c1 = find_context_locked(c2->name);
 if (!c1) {
 ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the hashtab\n", file, line, c2->name);
 check_contexts_trouble();
 } else
 ast_unlock_contexts();
 }

 /* loop thru all contexts, and verify the exten structure compares to the
 hashtab structure */
 for(c2=contexts;c2;c2=c2->next) {
 c1 = find_context_locked(c2->name);
 if (c1) {
 ast_unlock_contexts();

 /* is every entry in the root list also in the root_table? */
 for(e1 = c1->root; e1; e1=e1->next)
 {
 char dummy_name[1024];
 ex.exten = dummy_name;
 ex.matchcid = e1->matchcid;
 ex.cidmatch = e1->cidmatch;
 ast_copy_string(dummy_name, e1->exten, sizeof(dummy_name));
 e2 = ast_hashtab_lookup(c1->root_table, &ex);
 if (!e2) {
 if (e1->matchcid == AST_EXT_MATCHCID_ON) {
 ast_log(LOG_NOTICE, "Called from: %s:%d: The %s context records "
 "the exten %s (CID match: %s) but it is not in its root_table\n",
 file, line, c2->name, dummy_name, e1->cidmatch_display);
 } else {
 ast_log(LOG_NOTICE, "Called from: %s:%d: The %s context records "
 "the exten %s but it is not in its root_table\n",
 file, line, c2->name, dummy_name);
 }
 check_contexts_trouble();
 }
 }

 /* is every entry in the root_table also in the root list? */
 if (!c2->root_table) {
 if (c2->root) {
 ast_log(LOG_NOTICE,"Called from: %s:%d: No c2->root_table for context %s!\n", file, line, c2->name);
 usleep(500000);
 }
 } else {
 t1 = ast_hashtab_start_traversal(c2->root_table);
 while( (e2 = ast_hashtab_next(t1)) ) {
 for(e1=c2->root;e1;e1=e1->next) {
 if (!strcmp(e1->exten, e2->exten)) {
 found = 1;
 break;
 }
 }
 if (!found) {
 ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context records the exten %s but it is not in its root_table\n", file, line, c2->name, e2->exten);
 check_contexts_trouble();
 }

 }
 ast_hashtab_end_traversal(t1);
 }
 }
 /* is every priority reflected in the peer_table at the head of the list? */

 /* is every entry in the root list also in the root_table? */
 /* are the per-extension peer_tables in the right place? */

 for(e1 = c2->root; e1; e1 = e1->next) {

 for(e2=e1;e2;e2=e2->peer) {
 ex.priority = e2->priority;
 if (e2 != e1 && e2->peer_table) {
 ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority has a peer_table entry, and shouldn't!\n", file, line, c2->name, e1->exten, e2->priority );
 check_contexts_trouble();
 }

 if (e2 != e1 && e2->peer_label_table) {
 ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority has a peer_label_table entry, and shouldn't!\n", file, line, c2->name, e1->exten, e2->priority );
 check_contexts_trouble();
 }

 if (e2 == e1 && !e2->peer_table){
 ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority doesn't have a peer_table!\n", file, line, c2->name, e1->exten, e2->priority );
 check_contexts_trouble();
 }

 if (e2 == e1 && !e2->peer_label_table) {
 ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority doesn't have a peer_label_table!\n", file, line, c2->name, e1->exten, e2->priority );
 check_contexts_trouble();
 }


 e3 = ast_hashtab_lookup(e1->peer_table, &ex);
 if (!e3) {
 ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority is not reflected in the peer_table\n", file, line, c2->name, e1->exten, e2->priority );
 check_contexts_trouble();
 }
 }

 if (!e1->peer_table){
 ast_log(LOG_NOTICE,"Called from: %s:%d: No e1->peer_table!\n", file, line);
 usleep(500000);
 }

 /* is every entry in the peer_table also in the peer list? */
 t1 = ast_hashtab_start_traversal(e1->peer_table);
 while( (e2 = ast_hashtab_next(t1)) ) {
 for(e3=e1;e3;e3=e3->peer) {
 if (e3->priority == e2->priority) {
 found = 1;
 break;
 }
 }
 if (!found) {
 ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority is not reflected in the peer list\n", file, line, c2->name, e1->exten, e2->priority );
 check_contexts_trouble();
 }
 }
 ast_hashtab_end_traversal(t1);
 }
 }
 return 0;
}
#endif

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" represents an individual character or character set
 * meant to match the corresponding character in a dial string. The tree
 * 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.
 * My first attempt to duplicate the finding of the 'best' pattern was flawed in that
 * I misunderstood the general algorithm. I thought that the 'best' pattern
 * was the one with lowest total score. This was not true. Thus, if you have
 * patterns "1XXXXX" and "X11111", you would be tempted to say that "X11111" is
 * the "best" match because it has fewer X's, and is therefore more specific,
 * but this is not how the old algorithm works. It sorts matching patterns
 * in a similar collating sequence as sorting alphabetic strings, from left to
 * right. Thus, "1XXXXX" comes before "X11111", and would be the "better" match,
 * because "1" is more specific than "X".
 * So, to accomodate this philosophy, I sort the tree branches along the alt_char
 * line so they are lowest to highest in specificity numbers. This way, as soon
 * as we encounter our first complete match, we automatically have the "best"
 * match and can stop the traversal immediately. Same for CANMATCH/MATCHMORE.
 * If anyone would like to resurrect the "wrong" pattern trie searching algorithm,
 * they are welcome to revert pbx to before 1 Apr 2008.
 * As an 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 (sorted) tree that looks like this:
 * { "3" } --next--> { "0" } --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
 * |
 * |alt
 * |
 * { "f" } --next--> { "a" } --next--> { "x" exten_match: (c) }
 * { "N" } --next--> { "X" } --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
 * | |
 * | |alt
 * |alt |
 * | { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
 * |
 * NULL
 *
 * 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 strchr("23456789",*z), where *z is the char to match...
 *
 * traversal is pretty simple: one routine merely traverses the alt list, and for each matching char 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.
 * The scoreboard isn't as necessary to the revised algorithm, but I kept it as a handy way to return the matched extension.
 * The first complete match ends the traversal, which should make this version of the pattern matcher faster
 * the previous. The same goes for "CANMATCH" or "MATCHMORE"; the first such match ends the traversal. In both
 * these cases, the reason we can stop immediately, is because the first pattern match found will be the "best"
 * according to the sort criteria.
 * 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 could match extensions a, b and d. All are
 * of length 10; they have total specificities of 24580, 10246, and 25090, respectively, not that this matters
 * at all. (b) wins purely because the first character "3" is much more specific (lower specificity) than "N". I have
 * left the specificity totals in the code as an artifact; at some point, I will strip it out.
 *
 * Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown,
 * because it's a function of how many extensions are stored in a context. With thousands of extensions, the speedup
 * can be very noticeable. The new matching algorithm can run several hundreds of times faster, if not a thousand or
 * more times faster in extreme cases.
 *
 * MatchCID patterns are also supported, and stored in the tree just as the extension pattern is. Thus, you
 * can have patterns in your CID field as well.
 *
 * */


static void update_scoreboard(struct scoreboard *board, int length, int spec, struct ast_exten *exten, char last, const char *callerid, int deleted, struct match_char *node)
{
 /* if this extension is marked as deleted, then skip this -- if it never shows
 on the scoreboard, it will never be found, nor will halt the traversal. */
 if (deleted)
 return;
 board->total_specificity = spec;
 board->total_length = length;
 board->exten = exten;
 board->last_char = last;
 board->node = node;
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"Scoreboarding (LONGER) %s, len=%d, score=%d\n", exten->exten, length, spec);
#endif
}

#ifdef NEED_DEBUG
static void log_match_char_tree(struct match_char *node, char *prefix)
{
 char extenstr[40];
 struct ast_str *my_prefix = ast_str_alloca(1024);

 extenstr[0] = '\0';

 if (node && node->exten)
 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);

 if (strlen(node->x) > 1) {
 ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
 node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
 node->exten ? node->exten->exten : "", extenstr);
 } else {
 ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
 node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
 node->exten ? node->exten->exten : "", extenstr);
 }

 ast_str_set(&my_prefix, 0, "%s+ ", prefix);

 if (node->next_char)
 log_match_char_tree(node->next_char, ast_str_buffer(my_prefix));

 if (node->alt_char)
 log_match_char_tree(node->alt_char, prefix);
}
#endif

static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
{
 char extenstr[40];
 struct ast_str *my_prefix = ast_str_alloca(1024);

 extenstr[0] = '\0';

 if (node->exten) {
 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
 }

 if (strlen(node->x) > 1) {
 ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
 node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
 node->exten ? node->exten->name : "", extenstr);
 } else {
 ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
 node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
 node->exten ? node->exten->name : "", extenstr);
 }

 ast_str_set(&my_prefix, 0, "%s+ ", prefix);

 if (node->next_char)
 cli_match_char_tree(node->next_char, ast_str_buffer(my_prefix), fd);

 if (node->alt_char)
 cli_match_char_tree(node->alt_char, prefix, fd);
}

static 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) {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"CanMatch_exten returns exten %s(%p)\n", node2->exten->exten, node2->exten);
#endif
 return node2->exten;
 }
 }
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"CanMatch_exten returns NULL, match_char=%s\n", node->x);
#endif
 return 0;
}

static struct ast_exten *trie_find_next_match(struct match_char *node)
{
 struct match_char *m3;
 struct match_char *m4;
 struct ast_exten *e3;

 if (node && node->x[0] == '.' && !node->x[1]) { /* dot and ! will ALWAYS be next match in a matchmore */
 return node->exten;
 }

 if (node && node->x[0] == '!' && !node->x[1]) {
 return node->exten;
 }

 if (!node || !node->next_char) {
 return NULL;
 }

 m3 = node->next_char;

 if (m3->exten) {
 return m3->exten;
 }
 for (m4 = m3->alt_char; m4; m4 = m4->alt_char) {
 if (m4->exten) {
 return m4->exten;
 }
 }
 for (m4 = m3; m4; m4 = m4->alt_char) {
 e3 = trie_find_next_match(m3);
 if (e3) {
 return e3;
 }
 }

 return NULL;
}

#ifdef DEBUG_THIS
static char *action2str(enum ext_match_t action)
{
 switch (action) {
 case E_MATCH:
 return "MATCH";
 case E_CANMATCH:
 return "CANMATCH";
 case E_MATCHMORE:
 return "MATCHMORE";
 case E_FINDLABEL:
 return "FINDLABEL";
 case E_SPAWN:
 return "SPAWN";
 default:
 return "?ACTION?";
 }
}

#endif

static const char *candidate_exten_advance(const char *str)
{
 str++;
 while (*str == '-') {
 str++;
 }
 return str;
}

#define MORE(s) (*candidate_exten_advance(s))
#define ADVANCE(s) candidate_exten_advance(s)

static void new_find_extension(const char *str, struct scoreboard *score, struct match_char *tree, int length, int spec, const char *callerid, const char *label, enum ext_match_t action)
{
 struct match_char *p; /* note minimal stack storage requirements */
 struct ast_exten pattern = { .label = label };
#ifdef DEBUG_THIS
 if (tree)
 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
 else
 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
#endif
 for (p = tree; p; p = p->alt_char) {
 if (p->is_pattern) {
 if (p->x[0] == 'N') {
 if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
#define NEW_MATCHER_CHK_MATCH \
 if (p->exten && !MORE(str)) { /* if a shorter pattern matches along the way, might as well report it */ \
 if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */ \
 update_scoreboard(score, length + 1, spec + p->specificity, p->exten, 0, callerid, p->deleted, p); \
 if (!p->deleted) { \
 if (action == E_FINDLABEL) { \
 if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) { \
 ast_debug(4, "Found label in preferred extension\n"); \
 return; \
 } \
 } else { \
 ast_debug(4, "returning an exact match-- first found-- %s\n", p->exten->name); \
 return; /* the first match, by definition, will be the best, because of the sorted tree */ \
 } \
 } \
 } \
 }

#define NEW_MATCHER_RECURSE \
 if (p->next_char && (MORE(str) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0) \
 || p->next_char->x[0] == '!')) { \
 if (MORE(str) || p->next_char->x[0] == '!') { \
 new_find_extension(ADVANCE(str), score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
 if (score->exten) { \
 ast_debug(4 ,"returning an exact match-- %s\n", score->exten->name); \
 return; /* the first match is all we need */ \
 } \
 } else { \
 new_find_extension("/", score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) { \
 ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->name : \
 "NULL"); \
 return; /* the first match is all we need */ \
 } \
 } \
 } else if ((p->next_char || action == E_CANMATCH) && !MORE(str)) { \
 score->canmatch = 1; \
 score->canmatch_exten = get_canmatch_exten(p); \
 if (action == E_CANMATCH || action == E_MATCHMORE) { \
 ast_debug(4, "returning a canmatch/matchmore--- str=%s\n", str); \
 return; \
 } \
 }

 NEW_MATCHER_CHK_MATCH;
 NEW_MATCHER_RECURSE;
 }
 } else if (p->x[0] == 'Z') {
 if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
 NEW_MATCHER_CHK_MATCH;
 NEW_MATCHER_RECURSE;
 }
 } else if (p->x[0] == 'X') {
 if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
 NEW_MATCHER_CHK_MATCH;
 NEW_MATCHER_RECURSE;
 }
 } else if (p->x[0] == '.' && p->x[1] == 0) {
 /* how many chars will the . match against? */
 int i = 0;
 const char *str2 = str;
 while (*str2 && *str2 != '/') {
 str2++;
 i++;
 }
 if (p->exten && *str2 != '/') {
 update_scoreboard(score, length + i, spec + (i * p->specificity), p->exten, '.', callerid, p->deleted, p);
 if (score->exten) {
 ast_debug(4, "return because scoreboard has a match with '/'--- %s\n",
 score->exten->name);
 return; /* the first match is all we need */
 }
 }
 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
 new_find_extension("/", score, p->next_char, length + i, spec+(p->specificity*i), callerid, label, action);
 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
 ast_debug(4, "return because scoreboard has exact match OR "
 "CANMATCH/MATCHMORE & canmatch set--- %s\n",
 score->exten ? score->exten->name : "NULL");
 return; /* the first match is all we need */
 }
 }
 } else if (p->x[0] == '!' && p->x[1] == 0) {
 /* how many chars will the . match against? */
 int i = 1;
 const char *str2 = str;
 while (*str2 && *str2 != '/') {
 str2++;
 i++;
 }
 if (p->exten && *str2 != '/') {
 update_scoreboard(score, length + 1, spec + (p->specificity * i), p->exten, '!', callerid, p->deleted, p);
 if (score->exten) {
 ast_debug(4, "return because scoreboard has a '!' match--- %s\n",
 score->exten->name);
 return; /* the first match is all we need */
 }
 }
 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
 new_find_extension("/", score, p->next_char, length + i, spec + (p->specificity * i), callerid, label, action);
 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
 ast_debug(4, "return because scoreboard has exact match OR "
 "CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n",
 score->exten ? score->exten->name : "NULL");
 return; /* the first match is all we need */
 }
 }
 } 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, label, action);
 if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
 ast_debug(4, "return because scoreboard has exact match OR "
 "CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n",
 score->exten ? score->exten->name : "NULL");
 return; /* the first match is all we need */
 }
 }
 } else if (strchr(p->x, *str)) {
 ast_debug(4, "Nothing strange about this match\n");
 NEW_MATCHER_CHK_MATCH;
 NEW_MATCHER_RECURSE;
 }
 } else if (strchr(p->x, *str)) {
 ast_debug(4, "Nothing strange about this match\n");
 NEW_MATCHER_CHK_MATCH;
 NEW_MATCHER_RECURSE;
 }
 }
 ast_debug(4, "return at end of func\n");
}

#undef MORE
#undef ADVANCE

/* 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 each exten, 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. Except
 * that a regex only handles 1 pattern, really. This trie holds any number
 * of patterns. Well, really, it **could** be considered a single pattern,
 * where the "|" (or) operator is allowed, I guess, in a way, sort of...
 */

static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern)
{
 struct match_char *t;

 if (!current) {
 return 0;
 }

 for (t = current; t; t = t->alt_char) {
 if (is_pattern == t->is_pattern && !strcmp(pat, t->x)) {/* uh, we may want to sort exploded [] contents to make matching easy */
 return t;
 }
 }

 return 0;
}

/* The first arg is the location of the tree ptr, or the
 address of the next_char ptr in the node, so we can mess
 with it, if we need to insert at the beginning of the list */

static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, struct match_char *node)
{
 struct match_char *curr, *lcurr;

 /* insert node into the tree at "current", so the alt_char list from current is
 sorted in increasing value as you go to the leaves */
 if (!(*parent_ptr)) {
 *parent_ptr = node;
 return;
 }

 if ((*parent_ptr)->specificity > node->specificity) {
 /* insert at head */
 node->alt_char = (*parent_ptr);
 *parent_ptr = node;
 return;
 }

 lcurr = *parent_ptr;
 for (curr = (*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
 if (curr->specificity > node->specificity) {
 node->alt_char = curr;
 lcurr->alt_char = node;
 break;
 }
 lcurr = curr;
 }

 if (!curr) {
 lcurr->alt_char = node;
 }

}

struct pattern_node {
 /*! Pattern node specificity */
 int specif;
 /*! Pattern node match characters. */
 char buf[256];
};

static struct match_char *add_pattern_node(struct ast_context *con, struct match_char *current, const struct pattern_node *pattern, int is_pattern, int already, struct match_char **nextcharptr)
{
 struct match_char *m;

 if (!(m = ast_calloc(1, sizeof(*m) + strlen(pattern->buf)))) {
 return NULL;
 }

 /* strcpy is safe here since we know its size and have allocated
 * just enough space for when we allocated m
 */
 strcpy(m->x, pattern->buf);

 /* the specificity scores are the same as used in the old
 pattern matcher. */
 m->is_pattern = is_pattern;
 if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'N') {
 m->specificity = 0x0832;
 } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'Z') {
 m->specificity = 0x0931;
 } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'X') {
 m->specificity = 0x0a30;
 } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '.') {
 m->specificity = 0x18000;
 } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '!') {
 m->specificity = 0x28000;
 } else {
 m->specificity = pattern->specif;
 }

 if (!con->pattern_tree) {
 insert_in_next_chars_alt_char_list(&con->pattern_tree, m);
 } else {
 if (already) { /* switch to the new regime (traversing vs appending)*/
 insert_in_next_chars_alt_char_list(nextcharptr, m);
 } else {
 insert_in_next_chars_alt_char_list(&current->next_char, m);
 }
 }

 return m;
}

/*!
 * \internal
 * \brief Extract the next exten pattern node.
 *
 * \param node Pattern node to fill.
 * \param src Next source character to read.
 * \param pattern TRUE if the exten is a pattern.
 * \param extenbuf Original exten buffer to use in diagnostic messages.
 *
 * \retval Ptr to next extenbuf pos to read.
 */
static const char *get_pattern_node(struct pattern_node *node, const char *src, int pattern, const char *extenbuf)
{
#define INC_DST_OVERFLOW_CHECK \
 do { \
 if (dst - node->buf < sizeof(node->buf) - 1) { \
 ++dst; \
 } else { \
 overflow = 1; \
 } \
 } while (0)

 node->specif = 0;
 node->buf[0] = '\0';
 while (*src) {
 if (*src == '[' && pattern) {
 char *dst = node->buf;
 const char *src_next;
 int length;
 int overflow = 0;

 /* get past the '[' */
 ++src;
 for (;;) {
 if (*src == '\\') {
 /* Escaped character. */
 ++src;
 if (*src == '[' || *src == '\\' || *src == '-' || *src == ']') {
 *dst = *src++;
 INC_DST_OVERFLOW_CHECK;
 }
 } else if (*src == '-') {
 unsigned char first;
 unsigned char last;

 src_next = src;
 first = *(src_next - 1);
 last = *++src_next;

 if (last == '\\') {
 /* Escaped character. */
 last = *++src_next;
 }

 /* Possible char range. */
 if (node->buf[0] && last) {
 /* Expand the char range. */
 while (++first <= last) {
 *dst = first;
 INC_DST_OVERFLOW_CHECK;
 }
 src = src_next + 1;
 } else {
 /*
 * There was no left or right char for the range.
 * It is just a '-'.
 */
 *dst = *src++;
 INC_DST_OVERFLOW_CHECK;
 }
 } else if (*src == '\0') {
 ast_log(LOG_WARNING,
 "A matching ']' was not found for '[' in exten pattern '%s'\n",
 extenbuf);
 break;
 } else if (*src == ']') {
 ++src;
 break;
 } else {
 *dst = *src++;
 INC_DST_OVERFLOW_CHECK;
 }
 }
 /* null terminate the exploded range */
 *dst = '\0';

 if (overflow) {
 ast_log(LOG_ERROR,
 "Expanded character set too large to deal with in exten pattern '%s'. Ignoring character set.\n",
 extenbuf);
 node->buf[0] = '\0';
 continue;
 }

 /* Sort the characters in character set. */
 length = strlen(node->buf);
 if (!length) {
 ast_log(LOG_WARNING, "Empty character set in exten pattern '%s'. Ignoring.\n",
 extenbuf);
 node->buf[0] = '\0';
 continue;
 }
 qsort(node->buf, length, 1, compare_char);

 /* Remove duplicate characters from character set. */
 dst = node->buf;
 src_next = node->buf;
 while (*src_next++) {
 if (*dst != *src_next) {
 *++dst = *src_next;
 }
 }

 length = strlen(node->buf);
 length <<= 8;
 node->specif = length | (unsigned char) node->buf[0];
 break;
 } else if (*src == '-') {
 /* Skip dashes in all extensions. */
 ++src;
 } else {
 if (*src == '\\') {
 /*
 * XXX The escape character here does not remove any special
 * meaning to characters except the '[', '\\', and '-'
 * characters since they are special only in this function.
 */
 node->buf[0] = *++src;
 if (!node->buf[0]) {
 break;
 }
 } else {
 node->buf[0] = *src;
 if (pattern) {
 /* make sure n,x,z patterns are canonicalized to N,X,Z */
 if (node->buf[0] == 'n') {
 node->buf[0] = 'N';
 } else if (node->buf[0] == 'x') {
 node->buf[0] = 'X';
 } else if (node->buf[0] == 'z') {
 node->buf[0] = 'Z';
 }
 }
 }
 node->buf[1] = '\0';
 node->specif = 1;
 ++src;
 break;
 }
 }
 return src;

#undef INC_DST_OVERFLOW_CHECK
}

static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
{
 struct match_char *m1 = NULL;
 struct match_char *m2 = NULL;
 struct match_char **m0;
 const char *pos;
 int already;
 int pattern = 0;
 int idx_cur;
 int idx_next;
 char extenbuf[512];
 struct pattern_node pat_node[2];

 if (e1->matchcid) {
 if (sizeof(extenbuf) < strlen(e1->exten) + strlen(e1->cidmatch) + 2) {
 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 NULL;
 }
 sprintf(extenbuf, "%s/%s", e1->exten, e1->cidmatch);/* Safe. We just checked. */
 } else {
 ast_copy_string(extenbuf, e1->exten, sizeof(extenbuf));
 }

#ifdef NEED_DEBUG
 ast_debug(1, "Adding exten %s to tree\n", extenbuf);
#endif
 m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
 m0 = &con->pattern_tree;
 already = 1;

 pos = extenbuf;
 if (*pos == '_') {
 pattern = 1;
 ++pos;
 }
 idx_cur = 0;
 pos = get_pattern_node(&pat_node[idx_cur], pos, pattern, extenbuf);
 for (; pat_node[idx_cur].buf[0]; idx_cur = idx_next) {
 idx_next = (idx_cur + 1) % ARRAY_LEN(pat_node);
 pos = get_pattern_node(&pat_node[idx_next], pos, pattern, extenbuf);

 /* See about adding node to tree. */
 m2 = NULL;
 if (already && (m2 = already_in_tree(m1, pat_node[idx_cur].buf, pattern))
 && m2->next_char) {
 if (!pat_node[idx_next].buf[0]) {
 /*
 * This is the end of the pattern, but not the end of the tree.
 * Mark this node with the exten... a shorter pattern might win
 * if the longer one doesn't match.
 */
 if (findonly) {
 return m2;
 }
 if (m2->exten) {
 ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
 m2->deleted ? "(deleted/invalid)" : m2->exten->name, e1->name);
 }
 m2->exten = e1;
 m2->deleted = 0;
 }
 m1 = m2->next_char; /* m1 points to the node to compare against */
 m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
 } else { /* not already OR not m2 OR nor m2->next_char */
 if (m2) {
 if (findonly) {
 return m2;
 }
 m1 = m2; /* while m0 stays the same */
 } else {
 if (findonly) {
 return m1;
 }
 m1 = add_pattern_node(con, m1, &pat_node[idx_cur], pattern, already, m0);
 if (!m1) { /* m1 is the node just added */
 return NULL;
 }
 m0 = &m1->next_char;
 }
 if (!pat_node[idx_next].buf[0]) {
 if (m2 && m2->exten) {
 ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
 m2->deleted ? "(deleted/invalid)" : m2->exten->name, e1->name);
 }
 m1->deleted = 0;
 m1->exten = e1;
 }

 /* The 'already' variable is a mini-optimization designed to make it so that we
 * don't have to call already_in_tree when we know it will return false.
 */
 already = 0;
 }
 }
 return m1;
}

static 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_debug(1, "Creating Extension Trie for context %s(%p)\n", con->name, con);
 ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
 ast_debug(1, "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_table);
 while ((e1 = ast_hashtab_next(t1))) {
 if (e1->exten) {
 add_exten_to_pattern_tree(con, e1, 0);
 } else {
 ast_log(LOG_ERROR, "Attempt to create extension with no extension name.\n");
 }
 }
 ast_hashtab_end_traversal(t1);
}

static 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 */
 ast_free(pattern_tree);
}

/*!
 * \internal
 * \brief Get the length of the exten string.
 *
 * \param str Exten to get length.
 *
 * \retval strlen of exten.
 */
static int ext_cmp_exten_strlen(const char *str)
{
 int len;

 len = 0;
 for (;;) {
 /* Ignore '-' chars as eye candy fluff. */
 while (*str == '-') {
 ++str;
 }
 if (!*str) {
 break;
 }
 ++str;
 ++len;
 }
 return len;
}

/*!
 * \internal
 * \brief Partial comparison of non-pattern extens.
 *
 * \param left Exten to compare.
 * \param right Exten to compare. Also matches if this string ends first.
 *
 * \retval <0 if left < right
 * \retval =0 if left == right
 * \retval >0 if left > right
 */
static int ext_cmp_exten_partial(const char *left, const char *right)
{
 int cmp;

 for (;;) {
 /* Ignore '-' chars as eye candy fluff. */
 while (*left == '-') {
 ++left;
 }
 while (*right == '-') {
 ++right;
 }

 if (!*right) {
 /*
 * Right ended first for partial match or both ended at the same
 * time for a match.
 */
 cmp = 0;
 break;
 }

 cmp = *left - *right;
 if (cmp) {
 break;
 }
 ++left;
 ++right;
 }
 return cmp;
}

/*!
 * \internal
 * \brief Comparison of non-pattern extens.
 *
 * \param left Exten to compare.
 * \param right Exten to compare.
 *
 * \retval <0 if left < right
 * \retval =0 if left == right
 * \retval >0 if left > right
 */
static int ext_cmp_exten(const char *left, const char *right)
{
 int cmp;

 for (;;) {
 /* Ignore '-' chars as eye candy fluff. */
 while (*left == '-') {
 ++left;
 }
 while (*right == '-') {
 ++right;
 }

 cmp = *left - *right;
 if (cmp) {
 break;
 }
 if (!*left) {
 /*
 * Get here only if both strings ended at the same time. cmp
 * would be non-zero if only one string ended.
 */
 break;
 }
 ++left;
 ++right;
 }
 return cmp;
}

/*
 * Special characters used in patterns:
 * '_' underscore is the leading character of a pattern.
 * In other position it is treated as a regular char.
 * '-' The '-' is a separator and ignored. Why? So patterns like NXX-XXX-XXXX work.
 * . one or more of any character. Only allowed at the end of
 * a pattern.
 * ! zero or more of anything. Also impacts the result of CANMATCH
 * and MATCHMORE. Only allowed at the end of a pattern.
 * In the core routine, ! causes a match with a return code of 2.
 * In turn, depending on the search mode: (XXX check if it is implemented)
 * - E_MATCH retuns 1 (does match)
 * - E_MATCHMORE returns 0 (no match)
 * - E_CANMATCH returns 1 (does match)
 *
 * / should not appear as it is considered the separator of the CID info.
 * XXX at the moment we may stop on this char.
 *
 * X Z N match ranges 0-9, 1-9, 2-9 respectively.
 * [ denotes the start of a set of character. Everything inside
 * is considered literally. We can have ranges a-d and individual
 * characters. A '[' and '-' can be considered literally if they
 * are just before ']'.
 * XXX currently there is no way to specify ']' in a range, nor \ is
 * considered specially.
 *
 * When we compare a pattern with a specific extension, all characters in the extension
 * itself are considered literally.
 * XXX do we want to consider space as a separator as well ?
 * XXX do we want to consider the separators in non-patterns as well ?
 */

/*!
 * \brief helper functions to sort extension patterns in the desired way,
 * so that more specific patterns appear first.
 *
 * \details
 * The function compares individual characters (or sets of), returning
 * an int where bits 0-7 are the ASCII code of the first char in the set,
 * bits 8-15 are the number of characters in the set, and bits 16-20 are
 * for special cases.
 * This way more specific patterns (smaller character sets) appear first.
 * Wildcards have a special value, so that we can directly compare them to
 * sets by subtracting the two values. In particular:
 * 0x001xx one character, character set starting with xx
 * 0x0yyxx yy characters, character set starting with xx
 * 0x18000 '.' (one or more of anything)
 * 0x28000 '!' (zero or more of anything)
 * 0x30000 NUL (end of string)
 * 0x40000 error in set.
 * The pointer to the string is advanced according to needs.
 * NOTES:
 * 1. the empty set is ignored.
 * 2. given that a full set has always 0 as the first element,
 * we could encode the special cases as 0xffXX where XX
 * is 1, 2, 3, 4 as used above.
 */
static int ext_cmp_pattern_pos(const char **p, unsigned char *bitwise)
{
#define BITS_PER 8 /* Number of bits per unit (byte). */
 unsigned char c;
 unsigned char cmin;
 int count;
 const char *end;

 do {
 /* Get character and advance. (Ignore '-' chars as eye candy fluff.) */
 do {
 c = *(*p)++;
 } while (c == '-');

 /* always return unless we have a set of chars */
 switch (c) {
 default:
 /* ordinary character */
 bitwise[c / BITS_PER] = 1 << ((BITS_PER - 1) - (c % BITS_PER));
 return 0x0100 | c;

 case 'n':
 case 'N':
 /* 2..9 */
 bitwise[6] = 0x3f;
 bitwise[7] = 0xc0;
 return 0x0800 | '2';

 case 'x':
 case 'X':
 /* 0..9 */
 bitwise[6] = 0xff;
 bitwise[7] = 0xc0;
 return 0x0A00 | '0';

 case 'z':
 case 'Z':
 /* 1..9 */
 bitwise[6] = 0x7f;
 bitwise[7] = 0xc0;
 return 0x0900 | '1';

 case '.':
 /* wildcard */
 return 0x18000;

 case '!':
 /* earlymatch */
 return 0x28000; /* less specific than '.' */

 case '\0':
 /* empty string */
 *p = NULL;
 return 0x30000;

 case '[':
 /* char set */
 break;
 }
 /* locate end of set */
 end = strchr(*p, ']');

 if (!end) {
 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
 return 0x40000; /* XXX make this entry go last... */
 }

 count = 0;
 cmin = 0xFF;
 for (; *p < end; ++*p) {
 unsigned char c1; /* first char in range */
 unsigned char c2; /* last char in range */

 c1 = (*p)[0];
 if (*p + 2 < end && (*p)[1] == '-') { /* this is a range */
 c2 = (*p)[2];
 *p += 2; /* skip a total of 3 chars */
 } else { /* individual character */
 c2 = c1;
 }
 if (c1 < cmin) {
 cmin = c1;
 }
 for (; c1 <= c2; ++c1) {
 unsigned char mask = 1 << ((BITS_PER - 1) - (c1 % BITS_PER));

 /*
 * Note: If two character sets score the same, the one with the
 * lowest ASCII values will compare as coming first. Must fill
 * in most significant bits for lower ASCII values to accomplish
 * the desired sort order.
 */
 if (!(bitwise[c1 / BITS_PER] & mask)) {
 /* Add the character to the set. */
 bitwise[c1 / BITS_PER] |= mask;
 count += 0x100;
 }
 }
 }
 ++*p;
 } while (!count);/* While the char set was empty. */
 return count | cmin;
}

/*!
 * \internal
 * \brief Comparison of exten patterns.
 *
 * \param left Pattern to compare.
 * \param right Pattern to compare.
 *
 * \retval <0 if left < right
 * \retval =0 if left == right
 * \retval >0 if left > right
 */
static int ext_cmp_pattern(const char *left, const char *right)
{
 int cmp;
 int left_pos;
 int right_pos;

 for (;;) {
 unsigned char left_bitwise[32] = { 0, };
 unsigned char right_bitwise[32] = { 0, };

 left_pos = ext_cmp_pattern_pos(&left, left_bitwise);
 right_pos = ext_cmp_pattern_pos(&right, right_bitwise);
 cmp = left_pos - right_pos;
 if (!cmp) {
 /*
 * Are the character sets different, even though they score the same?
 *
 * Note: Must swap left and right to get the sense of the
 * comparison correct. Otherwise, we would need to multiply by
 * -1 instead.
 */
 cmp = memcmp(right_bitwise, left_bitwise, ARRAY_LEN(left_bitwise));
 }
 if (cmp) {
 break;
 }
 if (!left) {
 /*
 * Get here only if both patterns ended at the same time. cmp
 * would be non-zero if only one pattern ended.
 */
 break;
 }
 }
 return cmp;
}

/*!
 * \internal
 * \brief Comparison of dialplan extens for sorting purposes.
 *
 * \param left Exten/pattern to compare.
 * \param right Exten/pattern to compare.
 *
 * \retval <0 if left < right
 * \retval =0 if left == right
 * \retval >0 if left > right
 */
static int ext_cmp(const char *left, const char *right)
{
 /* Make sure non-pattern extens come first. */
 if (left[0] != '_') {
 if (right[0] == '_') {
 return -1;
 }
 /* Compare two non-pattern extens. */
 return ext_cmp_exten(left, right);
 }
 if (right[0] != '_') {
 return 1;
 }

 /*
 * OK, we need full pattern sorting routine.
 *
 * Skip past the underscores
 */
 return ext_cmp_pattern(left + 1, right + 1);
}

static int ext_fluff_count(const char *exten)
{
 int fluff = 0;

 if (*exten != '_') {
 /* not a pattern, simple check. */
 while (*exten) {
 if (*exten == '-') {
 fluff++;
 }
 exten++;
 }

 return fluff;
 }

 /* do pattern check */
 while (*exten) {
 if (*exten == '-') {
 fluff++;
 } else if (*exten == '[') {
 /* skip set, dashes here matter. */
 exten = strchr(exten, ']');

 if (!exten) {
 /* we'll end up warning about this later, don't spam logs */
 return fluff;
 }
 }
 exten++;
 }

 return fluff;
}

int ast_extension_cmp(const char *a, const char *b)
{
 int cmp;

 cmp = ext_cmp(a, b);
 if (cmp < 0) {
 return -1;
 }
 if (cmp > 0) {
 return 1;
 }
 return 0;
}

/*!
 * \internal
 * \brief used ast_extension_{match|close}
 * mode is as follows:
 * E_MATCH success only on exact match
 * E_MATCHMORE success only on partial match (i.e. leftover digits in pattern)
 * E_CANMATCH either of the above.
 * \retval 0 on no-match
 * \retval 1 on match
 * \retval 2 on early match.
 */

static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
{
 mode &= E_MATCH_MASK; /* only consider the relevant bits */

#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"match core: pat: '%s', dat: '%s', mode=%d\n", pattern, data, (int)mode);
#endif

 if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
 int lp = ext_cmp_exten_strlen(pattern);
 int ld = ext_cmp_exten_strlen(data);

 if (lp < ld) { /* pattern too short, cannot match */
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"return (0) - pattern too short, cannot match\n");
#endif
 return 0;
 }
 /* depending on the mode, accept full or partial match or both */
 if (mode == E_MATCH) {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"return (!ext_cmp_exten(%s,%s) when mode== E_MATCH)\n", pattern, data);
#endif
 return !ext_cmp_exten(pattern, data); /* 1 on match, 0 on fail */
 }
 if (ld == 0 || !ext_cmp_exten_partial(pattern, data)) { /* partial or full match */
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"return (mode(%d) == E_MATCHMORE ? lp(%d) > ld(%d) : 1)\n", mode, lp, ld);
#endif
 return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
 } else {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"return (0) when ld(%d) > 0 && pattern(%s) != data(%s)\n", ld, pattern, data);
#endif
 return 0;
 }
 }
 if (mode == E_MATCH && data[0] == '_') {
 /*
 * XXX It is bad design that we don't know if we should be
 * comparing data and pattern as patterns or comparing data if
 * it conforms to pattern when the function is called. First,
 * assume they are both patterns. If they don't match then try
 * to see if data conforms to the given pattern.
 *
 * note: if this test is left out, then _x. will not match _x. !!!
 */
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE, "Comparing as patterns first. pattern:%s data:%s\n", pattern, data);
#endif
 if (!ext_cmp_pattern(pattern + 1, data + 1)) {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"return (1) - pattern matches pattern\n");
#endif
 return 1;
 }
 }

 ++pattern; /* skip leading _ */
 /*
 * XXX below we stop at '/' which is a separator for the CID info. However we should
 * not store '/' in the pattern at all. When we insure it, we can remove the checks.
 */
 for (;;) {
 const char *end;

 /* Ignore '-' chars as eye candy fluff. */
 while (*data == '-') {
 ++data;
 }
 while (*pattern == '-') {
 ++pattern;
 }
 if (!*data || !*pattern || *pattern == '/') {
 break;
 }

 switch (*pattern) {
 case '[': /* a range */
 ++pattern;
 end = strchr(pattern, ']'); /* XXX should deal with escapes ? */
 if (!end) {
 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
 return 0; /* unconditional failure */
 }
 if (pattern == end) {
 /* Ignore empty character sets. */
 ++pattern;
 continue;
 }
 for (; pattern < end; ++pattern) {
 if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
 if (*data >= pattern[0] && *data <= pattern[2])
 break; /* match found */
 else {
 pattern += 2; /* skip a total of 3 chars */
 continue;
 }
 } else if (*data == pattern[0])
 break; /* match found */
 }
 if (pattern >= end) {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"return (0) when pattern>=end\n");
#endif
 return 0;
 }
 pattern = end; /* skip and continue */
 break;
 case 'n':
 case 'N':
 if (*data < '2' || *data > '9') {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"return (0) N is not matched\n");
#endif
 return 0;
 }
 break;
 case 'x':
 case 'X':
 if (*data < '0' || *data > '9') {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"return (0) X is not matched\n");
#endif
 return 0;
 }
 break;
 case 'z':
 case 'Z':
 if (*data < '1' || *data > '9') {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"return (0) Z is not matched\n");
#endif
 return 0;
 }
 break;
 case '.': /* Must match, even with more digits */
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE, "return (1) when '.' is matched\n");
#endif
 return 1;
 case '!': /* Early match */
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE, "return (2) when '!' is matched\n");
#endif
 return 2;
 default:
 if (*data != *pattern) {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE, "return (0) when *data(%c) != *pattern(%c)\n", *data, *pattern);
#endif
 return 0;
 }
 break;
 }
 ++data;
 ++pattern;
 }
 if (*data) /* data longer than pattern, no match */ {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE, "return (0) when data longer than pattern\n");
#endif
 return 0;
 }

 /*
 * match so far, but ran off the end of data.
 * Depending on what is next, determine match or not.
 */
 if (*pattern == '\0' || *pattern == '/') { /* exact match */
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE, "at end, return (%d) in 'exact match'\n", (mode==E_MATCHMORE) ? 0 : 1);
#endif
 return (mode == E_MATCHMORE) ? 0 : 1; /* this is a failure for E_MATCHMORE */
 } else if (*pattern == '!') { /* early match */
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE, "at end, return (2) when '!' is matched\n");
#endif
 return 2;
 } else { /* partial match */
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE, "at end, return (%d) which deps on E_MATCH\n", (mode == E_MATCH) ? 0 : 1);
#endif
 return (mode == E_MATCH) ? 0 : 1; /* this is a failure for E_MATCH */
 }
}

/*
 * Wrapper around _extension_match_core() to do performance measurement
 * using the profiling code.
 */
static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
{
 int i;
 static int prof_id = -2; /* marker for 'unallocated' id */
 if (prof_id == -2) {
 prof_id = ast_add_profile("ext_match", 0);
 }
 ast_mark(prof_id, 1);
 i = _extension_match_core(ast_strlen_zero(pattern) ? "" : pattern, ast_strlen_zero(data) ? "" : data, mode);
 ast_mark(prof_id, 0);
 return i;
}

int ast_extension_match(const char *pattern, const char *data)
{
 return extension_match_core(pattern, data, E_MATCH);
}

int ast_extension_close(const char *pattern, const char *data, int needmore)
{
 if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
 ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
 return extension_match_core(pattern, data, needmore);
}

/* This structure must remain in sync with ast_context for proper hashtab matching */
struct fake_context /* this struct is purely for matching in the hashtab */
{
 ast_rwlock_t lock;
 struct ast_exten *root;
 struct ast_hashtab *root_table;
 struct match_char *pattern_tree;
 struct ast_context *next;
 struct ast_includes includes;
 struct ast_ignorepats ignorepats;
 struct ast_sws alts;
 const char *registrar;
 int refcount;
 int autohints;
 ast_mutex_t macrolock;
 char name[256];
};

struct ast_context *ast_context_find(const char *name)
{
 struct ast_context *tmp;
 struct fake_context item;

 if (!name) {
 return NULL;
 }
 ast_rdlock_contexts();
 if (contexts_table) {
 ast_copy_string(item.name, name, sizeof(item.name));
 tmp = ast_hashtab_lookup(contexts_table, &item);
 } else {
 tmp = NULL;
 while ((tmp = ast_walk_contexts(tmp))) {
 if (!strcasecmp(name, tmp->name)) {
 break;
 }
 }
 }
 ast_unlock_contexts();
 return tmp;
}

#define STATUS_NO_CONTEXT 1
#define STATUS_NO_EXTENSION 2
#define STATUS_NO_PRIORITY 3
#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,
 const char *label, const char *callerid, enum ext_match_t action)
{
 int x, res;
 struct ast_context *tmp = NULL;
 struct ast_exten *e = NULL, *eroot = NULL;
 struct ast_exten pattern = {NULL, };
 struct scoreboard score = {0, };
 struct ast_str *tmpdata = NULL;
 int idx;

 pattern.label = label;
 pattern.priority = priority;
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE, "Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int) action);
#endif

 /* Initialize status if appropriate */
 if (q->stacklen == 0) {
 q->status = STATUS_NO_CONTEXT;
 q->swo = NULL;
 q->data = NULL;
 q->foundcontext = NULL;
 } else if (q->stacklen >= AST_PBX_MAX_STACK) {
 ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
 return NULL;
 }

 /* Check first to see if we've already been checked */
 for (x = 0; x < q->stacklen; x++) {
 if (!strcasecmp(q->incstack[x], context))
 return NULL;
 }

 if (bypass) { /* bypass means we only look there */
 tmp = bypass;
 } else { /* look in contexts */
 tmp = find_context(context);
 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 && tmp->root_table) {
 create_match_char_tree(tmp);
#ifdef NEED_DEBUG
 ast_debug(1, "Tree Created in context %s:\n", context);
 log_match_char_tree(tmp->pattern_tree," ");
#endif
 }
#ifdef NEED_DEBUG
 ast_log(LOG_NOTICE, "The Trie we are searching in:\n");
 log_match_char_tree(tmp->pattern_tree, ":: ");
#endif

 do {
 if (!ast_strlen_zero(overrideswitch)) {
 char *osw = ast_strdupa(overrideswitch), *name;
 struct ast_switch *asw;
 ast_switch_f *aswf = NULL;
 char *datap;
 int eval = 0;

 name = strsep(&osw, "/");
 asw = pbx_findswitch(name);

 if (!asw) {
 ast_log(LOG_WARNING, "No such switch '%s'\n", name);
 break;
 }

 if (osw && strchr(osw, '$')) {
 eval = 1;
 }

 if (eval && !(tmpdata = ast_str_thread_get(&switch_data, 512))) {
 ast_log(LOG_WARNING, "Can't evaluate overrideswitch?!\n");
 break;
 } else if (eval) {
 /* Substitute variables now */
 pbx_substitute_variables_helper(chan, osw, ast_str_buffer(tmpdata), ast_str_size(tmpdata));
 datap = ast_str_buffer(tmpdata);
 } else {
 datap = osw;
 }

 /* equivalent of extension_match_core() at the switch level */
 if (action == E_CANMATCH)
 aswf = asw->canmatch;
 else if (action == E_MATCHMORE)
 aswf = asw->matchmore;
 else /* action == E_MATCH */
 aswf = asw->exists;
 if (!aswf) {
 res = 0;
 } else {
 if (chan) {
 ast_autoservice_start(chan);
 }
 res = aswf(chan, context, exten, priority, callerid, datap);
 if (chan) {
 ast_autoservice_stop(chan);
 }
 }
 if (res) { /* Got a match */
 q->swo = asw;
 q->data = datap;
 q->foundcontext = context;
 /* XXX keep status = STATUS_NO_CONTEXT ? */
 return NULL;
 }
 }
 } while (0);

 if (extenpatternmatchnew) {
 new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid, label, action);
 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).
 */
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"Returning MATCHMORE NULL with exclamation point.\n");
#endif
 return NULL;
 }

 if (!eroot && (action == E_CANMATCH || action == E_MATCHMORE) && score.canmatch_exten) {
 q->status = STATUS_SUCCESS;
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"Returning CANMATCH exten %s\n", score.canmatch_exten->exten);
#endif
 return score.canmatch_exten;
 }

 if ((action == E_MATCHMORE || action == E_CANMATCH) && eroot) {
 if (score.node) {
 struct ast_exten *z = trie_find_next_match(score.node);
 if (z) {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten %s\n", z->exten);
#endif
 } else {
 if (score.canmatch_exten) {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE canmatchmatch exten %s(%p)\n", score.canmatch_exten->exten, score.canmatch_exten);
#endif
 return score.canmatch_exten;
 } else {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten NULL\n");
#endif
 }
 }
 return z;
 }
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE, "Returning CANMATCH/MATCHMORE NULL (no next_match)\n");
#endif
 return NULL; /* according to the code, complete matches are null matches in MATCHMORE mode */
 }

 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_table, &pattern);
 } else {
 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
 }
 if (e) { /* found a valid match */
 q->status = STATUS_SUCCESS;
 q->foundcontext = context;
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"Returning complete match of exten %s\n", e->exten);
#endif
 return e;
 }
 }
 } else { /* the old/current default exten pattern match algorithm */

 /* scan the list trying to match extension and CID */
 eroot = NULL;
 while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
 int match = extension_match_core(eroot->exten, exten, action);
 /* 0 on fail, 1 on match, 2 on earlymatch */

 if (!match || (eroot->matchcid && !matchcid(eroot->cidmatch, callerid)))
 continue; /* keep trying */
 if (match == 2 && action == E_MATCHMORE) {
 /* We match an extension ending in '!'.
 * The decision in this case is final and is NULL (no match).
 */
 return NULL;
 }
 /* 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_table, &pattern);
 } else {
 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
 }
 if (e) { /* found a valid match */
 q->status = STATUS_SUCCESS;
 q->foundcontext = context;
 return e;
 }
 }
 }

 /* Check alternative switches */
 for (idx = 0; idx < ast_context_switches_count(tmp); idx++) {
 const struct ast_sw *sw = ast_context_switches_get(tmp, idx);
 struct ast_switch *asw = pbx_findswitch(ast_get_switch_name(sw));
 ast_switch_f *aswf = NULL;
 const char *datap;

 if (!asw) {
 ast_log(LOG_WARNING, "No such switch '%s'\n", ast_get_switch_name(sw));
 continue;
 }

 /* Substitute variables now */
 if (ast_get_switch_eval(sw)) {
 if (!(tmpdata = ast_str_thread_get(&switch_data, 512))) {
 ast_log(LOG_WARNING, "Can't evaluate switch?!\n");
 continue;
 }
 pbx_substitute_variables_helper(chan, ast_get_switch_data(sw),
 ast_str_buffer(tmpdata), ast_str_size(tmpdata));
 datap = ast_str_buffer(tmpdata);
 } else {
 datap = ast_get_switch_data(sw);
 }

 /* equivalent of extension_match_core() at the switch level */
 if (action == E_CANMATCH)
 aswf = asw->canmatch;
 else if (action == E_MATCHMORE)
 aswf = asw->matchmore;
 else /* action == E_MATCH */
 aswf = asw->exists;
 if (!aswf)
 res = 0;
 else {
 if (chan)
 ast_autoservice_start(chan);
 res = aswf(chan, context, exten, priority, callerid, datap);
 if (chan)
 ast_autoservice_stop(chan);
 }
 if (res) { /* Got a match */
 q->swo = asw;
 q->data = datap;
 q->foundcontext = context;
 /* XXX keep status = STATUS_NO_CONTEXT ? */
 return NULL;
 }
 }
 q->incstack[q->stacklen++] = tmp->name; /* Setup the stack */
 /* Now try any includes we have in this context */
 for (idx = 0; idx < ast_context_includes_count(tmp); idx++) {
 const struct ast_include *i = ast_context_includes_get(tmp, idx);

 if (include_valid(i)) {
 if ((e = pbx_find_extension(chan, bypass, q, include_rname(i), exten, priority, label, callerid, action))) {
#ifdef NEED_DEBUG_HERE
 ast_log(LOG_NOTICE,"Returning recursive match of %s\n", e->exten);
#endif
 return e;
 }
 if (q->swo)
 return NULL;
 }
 }
 return NULL;
}

static void exception_store_free(void *data)
{
 struct pbx_exception *exception = data;
 ast_string_field_free_memory(exception);
 ast_free(exception);
}

static const struct ast_datastore_info exception_store_info = {
 .type = "EXCEPTION",
 .destroy = exception_store_free,
};

/*!
 * \internal
 * \brief Set the PBX to execute the exception extension.
 *
 * \param chan Channel to raise the exception on.
 * \param reason Reason exception is raised.
 * \param priority Dialplan priority to set.
 *
 * \retval 0 on success.
 * \retval -1 on error.
 */
int raise_exception(struct ast_channel *chan, const char *reason, int priority)
{
 struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
 struct pbx_exception *exception = NULL;

 if (!ds) {
 ds = ast_datastore_alloc(&exception_store_info, NULL);
 if (!ds)
 return -1;
 if (!(exception = ast_calloc_with_stringfields(1, struct pbx_exception, 128))) {
 ast_datastore_free(ds);
 return -1;
 }
 ds->data = exception;
 ast_channel_datastore_add(chan, ds);
 } else
 exception = ds->data;

 ast_string_field_set(exception, reason, reason);
 ast_string_field_set(exception, context, ast_channel_context(chan));
 ast_string_field_set(exception, exten, ast_channel_exten(chan));
 exception->priority = ast_channel_priority(chan);
 set_ext_pri(chan, "e", priority);
 return 0;
}

static int acf_exception_read(struct ast_channel *chan, const char *name, char *data, char *buf, size_t buflen)
{
 struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
 struct pbx_exception *exception = NULL;
 if (!ds || !ds->data)
 return -1;
 exception = ds->data;
 if (!strcasecmp(data, "REASON"))
 ast_copy_string(buf, exception->reason, buflen);
 else if (!strcasecmp(data, "CONTEXT"))
 ast_copy_string(buf, exception->context, buflen);
 else if (!strncasecmp(data, "EXTEN", 5))
 ast_copy_string(buf, exception->exten, buflen);
 else if (!strcasecmp(data, "PRIORITY"))
 snprintf(buf, buflen, "%d", exception->priority);
 else
 return -1;
 return 0;
}

static struct ast_custom_function exception_function = {
 .name = "EXCEPTION",
 .read = acf_exception_read,
};

/*!
 * \brief The return value depends on the action:
 *
 * E_MATCH, E_CANMATCH, E_MATCHMORE require a real match,
 * and return 0 on failure, -1 on match;
 * E_FINDLABEL maps the label to a priority, and returns
 * the priority on success, ... XXX
 * E_SPAWN, spawn an application,
 *
 * \retval 0 on success.
 * \retval -1 on failure.
 *
 * \note The channel is auto-serviced in this function, because doing an extension
 * match may block for a long time. For example, if the lookup has to use a network
 * dialplan switch, such as DUNDi or IAX2, it may take a while. However, the channel
 * auto-service code will queue up any important signalling frames to be processed
 * after this is done.
 */
static int pbx_extension_helper(struct ast_channel *c, struct ast_context *con,
 const char *context, const char *exten, int priority,
 const char *label, const char *callerid, enum ext_match_t action, int *found, int combined_find_spawn)
{
 struct ast_exten *e;
 struct ast_app *app;
 char *substitute = NULL;
 struct pbx_find_info q = { .stacklen = 0 }; /* the rest is reset in pbx_find_extension */
 char passdata[EXT_DATA_SIZE];
 int matching_action = (action == E_MATCH || action == E_CANMATCH || action == E_MATCHMORE);

 ast_rdlock_contexts();

 if (!context) {
 context = con->name;
 }

 if (found)
 *found = 0;

 e = pbx_find_extension(c, con, &q, context, exten, priority, label, callerid, action);
 if (e) {
 if (found)
 *found = 1;
 if (matching_action) {
 ast_unlock_contexts();
 return -1; /* success, we found it */
 } else if (action == E_FINDLABEL) { /* map the label to a priority */
 int res = e->priority;

 ast_unlock_contexts();

 /* the priority we were looking for */
 return res;
 } else { /* spawn */
 if (!e->cached_app)
 e->cached_app = pbx_findapp(e->app);
 app = e->cached_app;
 if (ast_strlen_zero(e->data)) {
 *passdata = '\0';
 } else {
 const char *tmp;
 if ((!(tmp = strchr(e->data, '$'))) || (!strstr(tmp, "${") && !strstr(tmp, "$["))) {
 /* no variables to substitute, copy on through */
 ast_copy_string(passdata, e->data, sizeof(passdata));
 } else {
 /* save e->data on stack for later processing after lock released */
 substitute = ast_strdupa(e->data);
 }
 }
 ast_unlock_contexts();
 if (!app) {
 ast_log(LOG_WARNING, "No application '%s' for extension (%s, %s, %d)\n", e->app, context, exten, priority);
 return -1;
 }
 if (ast_channel_context(c) != context)
 ast_channel_context_set(c, context);
 if (ast_channel_exten(c) != exten)
 ast_channel_exten_set(c, exten);
 ast_channel_priority_set(c, priority);
 if (substitute) {
 pbx_substitute_variables_helper(c, substitute, passdata, sizeof(passdata)-1);
 }
 ast_debug(1, "Launching '%s'\n", app_name(app));
 if (VERBOSITY_ATLEAST(3)) {
 ast_verb(3, "Executing [%s@%s:%d] " COLORIZE_FMT "(\"" COLORIZE_FMT "\", \"" COLORIZE_FMT "\") %s\n",
 exten, context, priority,
 COLORIZE(COLOR_BRCYAN, 0, app_name(app)),
 COLORIZE(COLOR_BRMAGENTA, 0, ast_channel_name(c)),
 COLORIZE(COLOR_BRMAGENTA, 0, passdata),
 "in new stack");
 }
 return pbx_exec(c, app, passdata); /* 0 on success, -1 on failure */
 }
 } else if (q.swo) { /* not found here, but in another switch */
 if (found)
 *found = 1;
 ast_unlock_contexts();
 if (matching_action) {
 return -1;
 } else {
 if (!q.swo->exec) {
 ast_log(LOG_WARNING, "No execution engine for switch %s\n", q.swo->name);
 return -1;
 }
 return q.swo->exec(c, q.foundcontext ? q.foundcontext : context, exten, priority, callerid, q.data);
 }
 } else { /* not found anywhere, see what happened */
 ast_unlock_contexts();
 /* Using S_OR here because Solaris doesn't like NULL being passed to ast_log */
 switch (q.status) {
 case STATUS_NO_CONTEXT:
 if (!matching_action && !combined_find_spawn)
 ast_log(LOG_NOTICE, "Cannot find extension context '%s'\n", S_OR(context, ""));
 break;
 case STATUS_NO_EXTENSION:
 if (!matching_action && !combined_find_spawn)
 ast_log(LOG_NOTICE, "Cannot find extension '%s' in context '%s'\n", exten, S_OR(context, ""));
 break;
 case STATUS_NO_PRIORITY:
 if (!matching_action && !combined_find_spawn)
 ast_log(LOG_NOTICE, "No such priority %d in extension '%s' in context '%s'\n", priority, exten, S_OR(context, ""));
 break;
 case STATUS_NO_LABEL:
 if (context && !combined_find_spawn)
 ast_log(LOG_NOTICE, "No such label '%s' in extension '%s' in context '%s'\n", label, exten, S_OR(context, ""));
 break;
 default:
 ast_debug(1, "Shouldn't happen!\n");
 }

 return (matching_action) ? 0 : -1;
 }
}

/*! \brief Find hint for given extension in context */
static struct ast_exten *ast_hint_extension_nolock(struct ast_channel *c, const char *context, const char *exten)
{
 struct pbx_find_info q = { .stacklen = 0 }; /* the rest is set in pbx_find_context */
 return pbx_find_extension(c, NULL, &q, context, exten, PRIORITY_HINT, NULL, "", E_MATCH);
}

static struct ast_exten *ast_hint_extension(struct ast_channel *c, const char *context, const char *exten)
{
 struct ast_exten *e;
 ast_rdlock_contexts();
 e = ast_hint_extension_nolock(c, context, exten);
 ast_unlock_contexts();
 return e;
}

enum ast_extension_states ast_devstate_to_extenstate(enum ast_device_state devstate)
{
 switch (devstate) {
 case AST_DEVICE_ONHOLD:
 return AST_EXTENSION_ONHOLD;
 case AST_DEVICE_BUSY:
 return AST_EXTENSION_BUSY;
 case AST_DEVICE_UNKNOWN:
 return AST_EXTENSION_NOT_INUSE;
 case AST_DEVICE_UNAVAILABLE:
 case AST_DEVICE_INVALID:
 return AST_EXTENSION_UNAVAILABLE;
 case AST_DEVICE_RINGINUSE:
 return (AST_EXTENSION_INUSE | AST_EXTENSION_RINGING);
 case AST_DEVICE_RINGING:
 return AST_EXTENSION_RINGING;
 case AST_DEVICE_INUSE:
 return AST_EXTENSION_INUSE;
 case AST_DEVICE_NOT_INUSE:
 return AST_EXTENSION_NOT_INUSE;
 case AST_DEVICE_TOTAL: /* not a device state, included for completeness */
 break;
 }

 return AST_EXTENSION_NOT_INUSE;
}

/*!
 * \internal
 * \brief Parse out the presence portion of the hint string
 */
static char *parse_hint_presence(struct ast_str *hint_args)
{
 char *copy = ast_strdupa(ast_str_buffer(hint_args));
 char *tmp = "";

 if ((tmp = strrchr(copy, ','))) {
 *tmp = '\0';
 tmp++;
 } else {
 return NULL;
 }
 ast_str_set(&hint_args, 0, "%s", tmp);
 return ast_str_buffer(hint_args);
}

/*!
 * \internal
 * \brief Parse out the device portion of the hint string
 */
static char *parse_hint_device(struct ast_str *hint_args)
{
 char *copy = ast_strdupa(ast_str_buffer(hint_args));
 char *tmp;

 if ((tmp = strrchr(copy, ','))) {
 *tmp = '\0';
 }

 ast_str_set(&hint_args, 0, "%s", copy);
 return ast_str_buffer(hint_args);
}

static void device_state_info_dt(void *obj)
{
 struct ast_device_state_info *info = obj;

 ao2_cleanup(info->causing_channel);
}

static struct ao2_container *alloc_device_state_info(void)
{
 return ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_NOLOCK, 0, NULL, NULL);
}

static int ast_extension_state3(struct ast_str *hint_app, struct ao2_container *device_state_info)
{
 char *cur;
 char *rest;
 struct ast_devstate_aggregate agg;

 /* One or more devices separated with a & character */
 rest = parse_hint_device(hint_app);

 ast_devstate_aggregate_init(&agg);
 while ((cur = strsep(&rest, "&"))) {
 enum ast_device_state state = ast_device_state(cur);

 ast_devstate_aggregate_add(&agg, state);
 if (device_state_info) {
 struct ast_device_state_info *obj;

 obj = ao2_alloc_options(sizeof(*obj) + strlen(cur), device_state_info_dt, AO2_ALLOC_OPT_LOCK_NOLOCK);
 /* if failed we cannot add this device */
 if (obj) {
 obj->device_state = state;
 strcpy(obj->device_name, cur);
 ao2_link(device_state_info, obj);
 ao2_ref(obj, -1);
 }
 }
 }

 return ast_devstate_to_extenstate(ast_devstate_aggregate_result(&agg));
}

/*! \brief Check state of extension by using hints */
static int ast_extension_state2(struct ast_exten *e, struct ao2_container *device_state_info)
{
 struct ast_str *hint_app = ast_str_thread_get(&extensionstate_buf, 32);

 if (!e || !hint_app) {
 return -1;
 }

 ast_str_set(&hint_app, 0, "%s", ast_get_extension_app(e));
 return ast_extension_state3(hint_app, device_state_info);
}

/*! \brief Return extension_state as string */
const char *ast_extension_state2str(int extension_state)
{
 int i;

 for (i = 0; (i < ARRAY_LEN(extension_states)); i++) {
 if (extension_states[i].extension_state == extension_state)
 return extension_states[i].text;
 }
 return "Unknown";
}

/*!
 * \internal
 * \brief Check extension state for an extension by using hint
 */
static int internal_extension_state_extended(struct ast_channel *c, const char *context, const char *exten,
 struct ao2_container *device_state_info)
{
 struct ast_exten *e;

 if (!(e = ast_hint_extension(c, context, exten))) { /* Do we have a hint for this extension ? */
 return -1; /* No hint, return -1 */
 }

 if (e->exten[0] == '_') {
 /* Create this hint on-the-fly, we explicitly lock hints here to ensure the
 * same locking order as if this were done through configuration file - that is
 * hints is locked first and then (if needed) contexts is locked
 */
 ao2_lock(hints);
 ast_add_extension(e->parent->name, 0, exten, e->priority, e->label,
 e->matchcid ? e->cidmatch : NULL, e->app, ast_strdup(e->data), ast_free_ptr,
 e->registrar);
 ao2_unlock(hints);
 if (!(e = ast_hint_extension(c, context, exten))) {
 /* Improbable, but not impossible */
 return -1;
 }
 }

 return ast_extension_state2(e, device_state_info); /* Check all devices in the hint */
}

/*! \brief Check extension state for an extension by using hint */
int ast_extension_state(struct ast_channel *c, const char *context, const char *exten)
{
 return internal_extension_state_extended(c, context, exten, NULL);
}

/*! \brief Check extended extension state for an extension by using hint */
int ast_extension_state_extended(struct ast_channel *c, const char *context, const char *exten,
 struct ao2_container **device_state_info)
{
 struct ao2_container *container = NULL;
 int ret;

 if (device_state_info) {
 container = alloc_device_state_info();
 }

 ret = internal_extension_state_extended(c, context, exten, container);
 if (ret < 0 && container) {
 ao2_ref(container, -1);
 container = NULL;
 }

 if (device_state_info) {
 get_device_state_causing_channels(container);
 *device_state_info = container;
 }

 return ret;
}

static int extension_presence_state_helper(struct ast_exten *e, char **subtype, char **message)
{
 struct ast_str *hint_app = ast_str_thread_get(&extensionstate_buf, 32);
 char *presence_provider;
 const char *app;

 if (!e || !hint_app) {
 return -1;
 }

 app = ast_get_extension_app(e);
 if (ast_strlen_zero(app)) {
 return -1;
 }

 ast_str_set(&hint_app, 0, "%s", app);
 presence_provider = parse_hint_presence(hint_app);

 if (ast_strlen_zero(presence_provider)) {
 /* No presence string in the hint */
 return 0;
 }

 return ast_presence_state(presence_provider, subtype, message);
}

int ast_hint_presence_state(struct ast_channel *c, const char *context, const char *exten, char **subtype, char **message)
{
 struct ast_exten *e;

 if (!(e = ast_hint_extension(c, context, exten))) { /* Do we have a hint for this extension ? */
 return -1; /* No hint, return -1 */
 }

 if (e->exten[0] == '_') {
 /* Create this hint on-the-fly */
 ao2_lock(hints);
 ast_add_extension(e->parent->name, 0, exten, e->priority, e->label,
 e->matchcid ? e->cidmatch : NULL, e->app, ast_strdup(e->data), ast_free_ptr,
 e->registrar);
 ao2_unlock(hints);
 if (!(e = ast_hint_extension(c, context, exten))) {
 /* Improbable, but not impossible */
 return -1;
 }
 }

 return extension_presence_state_helper(e, subtype, message);
}

static int execute_state_callback(ast_state_cb_type cb,
 const char *context,
 const char *exten,
 void *data,
 enum ast_state_cb_update_reason reason,
 struct ast_hint *hint,
 struct ao2_container *device_state_info)
{
 int res = 0;
 struct ast_state_cb_info info = { 0, };

 info.reason = reason;

 /* Copy over current hint data */
 if (hint) {
 ao2_lock(hint);
 info.exten_state = hint->laststate;
 info.device_state_info = device_state_info;
 info.presence_state = hint->last_presence_state;
 if (!(ast_strlen_zero(hint->last_presence_subtype))) {
 info.presence_subtype = ast_strdupa(hint->last_presence_subtype);
 } else {
 info.presence_subtype = "";
 }
 if (!(ast_strlen_zero(hint->last_presence_message))) {
 info.presence_message = ast_strdupa(hint->last_presence_message);
 } else {
 info.presence_message = "";
 }
 ao2_unlock(hint);
 } else {
 info.exten_state = AST_EXTENSION_REMOVED;
 }

 res = cb(context, exten, &info, data);

 return res;
}

/*!
 * /internal
 * /brief Identify a channel for every device which is supposedly responsible for the device state.
 *
 * Especially when the device is ringing, the oldest ringing channel is chosen.
 * For all other cases the first encountered channel in the specific state is chosen.
 */
static void get_device_state_causing_channels(struct ao2_container *c)
{
 struct ao2_iterator iter;
 struct ast_device_state_info *info;
 struct ast_channel *chan;

 if (!c || !ao2_container_count(c)) {
 return;
 }
 iter = ao2_iterator_init(c, 0);
 for (; (info = ao2_iterator_next(&iter)); ao2_ref(info, -1)) {
 enum ast_channel_state search_state = 0; /* prevent false uninit warning */
 char match[AST_CHANNEL_NAME];
 struct ast_channel_iterator *chan_iter;
 struct timeval chantime = {0, }; /* prevent false uninit warning */

 switch (info->device_state) {
 case AST_DEVICE_RINGING:
 case AST_DEVICE_RINGINUSE:
 /* find ringing channel */
 search_state = AST_STATE_RINGING;
 break;
 case AST_DEVICE_BUSY:
 /* find busy channel */
 search_state = AST_STATE_BUSY;
 break;
 case AST_DEVICE_ONHOLD:
 case AST_DEVICE_INUSE:
 /* find up channel */
 search_state = AST_STATE_UP;
 break;
 case AST_DEVICE_UNKNOWN:
 case AST_DEVICE_NOT_INUSE:
 case AST_DEVICE_INVALID:
 case AST_DEVICE_UNAVAILABLE:
 case AST_DEVICE_TOTAL /* not a state */:
 /* no channels are of interest */
 continue;
 }

 /* iterate over all channels of the device */
 snprintf(match, sizeof(match), "%s-", info->device_name);
 chan_iter = ast_channel_iterator_by_name_new(match, strlen(match));
 for (; (chan = ast_channel_iterator_next(chan_iter)); ast_channel_unref(chan)) {
 ast_channel_lock(chan);
 /* this channel's state doesn't match */
 if (search_state != ast_channel_state(chan)) {
 ast_channel_unlock(chan);
 continue;
 }
 /* any non-ringing channel will fit */
 if (search_state != AST_STATE_RINGING) {
 ast_channel_unlock(chan);
 info->causing_channel = chan; /* is kept ref'd! */
 break;
 }
 /* but we need the oldest ringing channel of the device to match with undirected pickup */
 if (!info->causing_channel) {
 chantime = ast_channel_creationtime(chan);
 ast_channel_ref(chan); /* must ref it! */
 info->causing_channel = chan;
 } else if (ast_tvcmp(ast_channel_creationtime(chan), chantime) < 0) {
 chantime = ast_channel_creationtime(chan);
 ast_channel_unref(info->causing_channel);
 ast_channel_ref(chan); /* must ref it! */
 info->causing_channel = chan;
 }
 ast_channel_unlock(chan);
 }
 ast_channel_iterator_destroy(chan_iter);
 }
 ao2_iterator_destroy(&iter);
}

static void device_state_notify_callbacks(struct ast_hint *hint, struct ast_str **hint_app)
{
 struct ao2_iterator cb_iter;
 struct ast_state_cb *state_cb;
 int state;
 int same_state;
 struct ao2_container *device_state_info;
 int first_extended_cb_call = 1;
 char context_name[AST_MAX_CONTEXT];
 char exten_name[AST_MAX_EXTENSION];

 ao2_lock(hint);
 if (!hint->exten) {
 /* The extension has already been destroyed */
 ao2_unlock(hint);
 return;
 }

 /*
 * Save off strings in case the hint extension gets destroyed
 * while we are notifying the watchers.
 */
 ast_copy_string(context_name,
 ast_get_context_name(ast_get_extension_context(hint->exten)),
 sizeof(context_name));
 ast_copy_string(exten_name, ast_get_extension_name(hint->exten),
 sizeof(exten_name));
 ast_str_set(hint_app, 0, "%s", ast_get_extension_app(hint->exten));
 ao2_unlock(hint);

 /*
 * Get device state for this hint.
 *
 * NOTE: We cannot hold any locks while determining the hint
 * device state or notifying the watchers without causing a
 * deadlock. (conlock, hints, and hint)
 */

 /* Make a container so state3 can fill it if we wish.
 * If that failed we simply do not provide the extended state info.
 */
 device_state_info = alloc_device_state_info();

 state = ast_extension_state3(*hint_app, device_state_info);
 same_state = state == hint->laststate;
 if (same_state && (~state & AST_EXTENSION_RINGING)) {
 ao2_cleanup(device_state_info);
 return;
 }

 /* Device state changed since last check - notify the watchers. */
 hint->laststate = state; /* record we saw the change */

 /* For general callbacks */
 if (!same_state) {
 cb_iter = ao2_iterator_init(statecbs, 0);
 for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
 execute_state_callback(state_cb->change_cb,
 context_name,
 exten_name,
 state_cb->data,
 AST_HINT_UPDATE_DEVICE,
 hint,
 NULL);
 }
 ao2_iterator_destroy(&cb_iter);
 }

 /* For extension callbacks */
 /* extended callbacks are called when the state changed or when AST_STATE_RINGING is
 * included. Normal callbacks are only called when the state changed.
 */
 cb_iter = ao2_iterator_init(hint->callbacks, 0);
 for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
 if (state_cb->extended && first_extended_cb_call) {
 /* Fill detailed device_state_info now that we know it is used by extd. callback */
 first_extended_cb_call = 0;
 get_device_state_causing_channels(device_state_info);
 }
 if (state_cb->extended || !same_state) {
 execute_state_callback(state_cb->change_cb,
 context_name,
 exten_name,
 state_cb->data,
 AST_HINT_UPDATE_DEVICE,
 hint,
 state_cb->extended ? device_state_info : NULL);
 }
 }
 ao2_iterator_destroy(&cb_iter);

 ao2_cleanup(device_state_info);
}

static void presence_state_notify_callbacks(struct ast_hint *hint, struct ast_str **hint_app,
 struct ast_presence_state_message *presence_state)
{
 struct ao2_iterator cb_iter;
 struct ast_state_cb *state_cb;
 char context_name[AST_MAX_CONTEXT];
 char exten_name[AST_MAX_EXTENSION];

 ao2_lock(hint);
 if (!hint->exten) {
 /* The extension has already been destroyed */
 ao2_unlock(hint);
 return;
 }

 /*
 * Save off strings in case the hint extension gets destroyed
 * while we are notifying the watchers.
 */
 ast_copy_string(context_name,
 ast_get_context_name(ast_get_extension_context(hint->exten)),
 sizeof(context_name));
 ast_copy_string(exten_name, ast_get_extension_name(hint->exten),
 sizeof(exten_name));
 ast_str_set(hint_app, 0, "%s", ast_get_extension_app(hint->exten));
 ao2_unlock(hint);

 /* Check to see if update is necessary */
 if ((hint->last_presence_state == presence_state->state) &&
 ((hint->last_presence_subtype && presence_state->subtype &&
 !strcmp(hint->last_presence_subtype, presence_state->subtype)) ||
 (!hint->last_presence_subtype && !presence_state->subtype)) &&
 ((hint->last_presence_message && presence_state->message &&
 !strcmp(hint->last_presence_message, presence_state->message)) ||
 (!hint->last_presence_message && !presence_state->message))) {
 /* this update is the same as the last, do nothing */
 return;
 }

 /* update new values */
 ast_free(hint->last_presence_subtype);
 ast_free(hint->last_presence_message);
 hint->last_presence_state = presence_state->state;
 hint->last_presence_subtype = presence_state->subtype ? ast_strdup(presence_state->subtype) : NULL;
 hint->last_presence_message = presence_state->message ? ast_strdup(presence_state->message) : NULL;

 /* For general callbacks */
 cb_iter = ao2_iterator_init(statecbs, 0);
 for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
 execute_state_callback(state_cb->change_cb,
 context_name,
 exten_name,
 state_cb->data,
 AST_HINT_UPDATE_PRESENCE,
 hint,
 NULL);
 }
 ao2_iterator_destroy(&cb_iter);

 /* For extension callbacks */
 cb_iter = ao2_iterator_init(hint->callbacks, 0);
 for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_cleanup(state_cb)) {
 execute_state_callback(state_cb->change_cb,
 context_name,
 exten_name,
 state_cb->data,
 AST_HINT_UPDATE_PRESENCE,
 hint,
 NULL);
 }
 ao2_iterator_destroy(&cb_iter);
}

static int handle_hint_change_message_type(struct stasis_message *msg, enum ast_state_cb_update_reason reason)
{
 struct ast_hint *hint;
 struct ast_str *hint_app;

 if (hint_change_message_type() != stasis_message_type(msg)) {
 return 0;
 }

 if (!(hint_app = ast_str_create(1024))) {
 return -1;
 }

 hint = stasis_message_data(msg);

 switch (reason) {
 case AST_HINT_UPDATE_DEVICE:
 device_state_notify_callbacks(hint, &hint_app);
 break;
 case AST_HINT_UPDATE_PRESENCE:
 {
 char *presence_subtype = NULL;
 char *presence_message = NULL;
 int state;

 state = extension_presence_state_helper(
 hint->exten, &presence_subtype, &presence_message);
 {
 struct ast_presence_state_message presence_state = {
 .state = state > 0 ? state : AST_PRESENCE_INVALID,
 .subtype = presence_subtype,
 .message = presence_message
 };

 presence_state_notify_callbacks(hint, &hint_app, &presence_state);
 }

 ast_free(presence_subtype);
 ast_free(presence_message);
 }
 break;
 }

 ast_free(hint_app);
 return 1;
}

static void device_state_cb(void *unused, struct stasis_subscription *sub, struct stasis_message *msg)
{
 struct ast_device_state_message *dev_state;
 struct ast_str *hint_app;
 struct ast_hintdevice *device;
 struct ast_hintdevice *cmpdevice;
 struct ao2_iterator *dev_iter;
 struct ao2_iterator auto_iter;
 struct ast_autohint *autohint;
 char *virtual_device;
 char *type;
 char *device_name;

 if (handle_hint_change_message_type(msg, AST_HINT_UPDATE_DEVICE)) {
 return;
 }

 if (hint_remove_message_type() == stasis_message_type(msg)) {
 /* The extension has already been destroyed */
 struct ast_state_cb *state_cb;
 struct ao2_iterator cb_iter;
 struct ast_hint *hint = stasis_message_data(msg);

 ao2_lock(hint);
 hint->laststate = AST_EXTENSION_DEACTIVATED;
 ao2_unlock(hint);

 cb_iter = ao2_iterator_init(hint->callbacks, 0);
 for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
 execute_state_callback(state_cb->change_cb,
 hint->context_name,
 hint->exten_name,
 state_cb->data,
 AST_HINT_UPDATE_DEVICE,
 hint,
 NULL);
 }
 ao2_iterator_destroy(&cb_iter);
 return;
 }

 if (ast_device_state_message_type() != stasis_message_type(msg)) {
 return;
 }

 dev_state = stasis_message_data(msg);
 if (dev_state->eid) {
 /* ignore non-aggregate states */
 return;
 }

 if (ao2_container_count(hintdevices) == 0 && ao2_container_count(autohints) == 0) {
 /* There are no hints monitoring devices. */
 return;
 }

 hint_app = ast_str_create(1024);
 if (!hint_app) {
 return;
 }

 cmpdevice = ast_alloca(sizeof(*cmpdevice) + strlen(dev_state->device));
 strcpy(cmpdevice->hintdevice, dev_state->device);

 ast_mutex_lock(&context_merge_lock);/* Hold off ast_merge_contexts_and_delete */

 /* Initially we find all hints for the device and notify them */
 dev_iter = ao2_t_callback(hintdevices,
 OBJ_SEARCH_OBJECT | OBJ_MULTIPLE,
 hintdevice_cmp_multiple,
 cmpdevice,
 "find devices in container");
 if (dev_iter) {
 for (; (device = ao2_iterator_next(dev_iter)); ao2_t_ref(device, -1, "Next device")) {
 if (device->hint) {
 device_state_notify_callbacks(device->hint, &hint_app);
 }
 }
 ao2_iterator_destroy(dev_iter);
 }

 /* Second stage we look for any autohint contexts and if the device is not already in the hints
 * we create it.
 */
 type = ast_strdupa(dev_state->device);
 if (ast_strlen_zero(type)) {
 goto end;
 }

 /* Determine if this is a virtual/custom device or a real device */
 virtual_device = strchr(type, ':');
 device_name = strchr(type, '/');
 if (virtual_device && (!device_name || (virtual_device < device_name))) {
 device_name = virtual_device;
 }

 /* Invalid device state name - not a virtual/custom device and not a real device */
 if (ast_strlen_zero(device_name)) {
 goto end;
 }

 *device_name++ = '\0';

 auto_iter = ao2_iterator_init(autohints, 0);
 for (; (autohint = ao2_iterator_next(&auto_iter)); ao2_t_ref(autohint, -1, "Next autohint")) {
 if (ast_get_hint(NULL, 0, NULL, 0, NULL, autohint->context, device_name)) {
 continue;
 }

 /* The device has no hint in the context referenced by this autohint so create one */
 ast_add_extension(autohint->context, 0, device_name,
 PRIORITY_HINT, NULL, NULL, dev_state->device,
 ast_strdup(dev_state->device), ast_free_ptr, autohint->registrar);

 /* Since this hint was just created there are no watchers, so we don't need to notify anyone */
 }
 ao2_iterator_destroy(&auto_iter);

end:
 ast_mutex_unlock(&context_merge_lock);
 ast_free(hint_app);
 return;
}

/*!
 * \internal
 * \brief Destroy the given state callback object.
 *
 * \param doomed State callback to destroy.
 *
 * \return Nothing
 */
static void destroy_state_cb(void *doomed)
{
 struct ast_state_cb *state_cb = doomed;

 if (state_cb->destroy_cb) {
 state_cb->destroy_cb(state_cb->id, state_cb->data);
 }
}

/*!
 * \internal
 * \brief Add watcher for extension states with destructor
 */
static int extension_state_add_destroy(const char *context, const char *exten,
 ast_state_cb_type change_cb, ast_state_cb_destroy_type destroy_cb, void *data, int extended)
{
 struct ast_hint *hint;
 struct ast_state_cb *state_cb;
 struct ast_exten *e;
 int id;

 /* If there's no context and extension: add callback to statecbs list */
 if (!context && !exten) {
 /* Prevent multiple adds from adding the same change_cb at the same time. */
 ao2_lock(statecbs);

 /* Remove any existing change_cb. */
 ao2_find(statecbs, change_cb, OBJ_UNLINK | OBJ_NODATA);

 /* Now insert the change_cb */
 if (!(state_cb = ao2_alloc(sizeof(*state_cb), destroy_state_cb))) {
 ao2_unlock(statecbs);
 return -1;
 }
 state_cb->id = 0;
 state_cb->change_cb = change_cb;
 state_cb->destroy_cb = destroy_cb;
 state_cb->data = data;
 state_cb->extended = extended;
 ao2_link(statecbs, state_cb);

 ao2_ref(state_cb, -1);
 ao2_unlock(statecbs);
 return 0;
 }

 if (!context || !exten)
 return -1;

 /* This callback type is for only one hint, so get the hint */
 e = ast_hint_extension(NULL, context, exten);
 if (!e) {
 return -1;
 }

 /* If this is a pattern, dynamically create a new extension for this
 * particular match. Note that this will only happen once for each
 * individual extension, because the pattern will no longer match first.
 */
 if (e->exten[0] == '_') {
 ao2_lock(hints);
 ast_add_extension(e->parent->name, 0, exten, e->priority, e->label,
 e->matchcid ? e->cidmatch : NULL, e->app, ast_strdup(e->data), ast_free_ptr,
 e->registrar);
 ao2_unlock(hints);
 e = ast_hint_extension(NULL, context, exten);
 if (!e || e->exten[0] == '_') {
 return -1;
 }
 }

 /* Find the hint in the hints container */
 ao2_lock(hints);/* Locked to hold off ast_merge_contexts_and_delete */
 hint = ao2_find(hints, e, 0);
 if (!hint) {
 ao2_unlock(hints);
 return -1;
 }

 /* Now insert the callback in the callback list */
 if (!(state_cb = ao2_alloc(sizeof(*state_cb), destroy_state_cb))) {
 ao2_ref(hint, -1);
 ao2_unlock(hints);
 return -1;
 }
 do {
 id = stateid++; /* Unique ID for this callback */
 /* Do not allow id to ever be -1 or 0. */
 } while (id == -1 || id == 0);
 state_cb->id = id;
 state_cb->change_cb = change_cb; /* Pointer to callback routine */
 state_cb->destroy_cb = destroy_cb;
 state_cb->data = data; /* Data for the callback */
 state_cb->extended = extended;
 ao2_link(hint->callbacks, state_cb);

 ao2_ref(state_cb, -1);
 ao2_ref(hint, -1);
 ao2_unlock(hints);

 return id;
}

int ast_extension_state_add_destroy(const char *context, const char *exten,
 ast_state_cb_type change_cb, ast_state_cb_destroy_type destroy_cb, void *data)
{
 return extension_state_add_destroy(context, exten, change_cb, destroy_cb, data, 0);
}

int ast_extension_state_add(const char *context, const char *exten,
 ast_state_cb_type change_cb, void *data)
{
 return extension_state_add_destroy(context, exten, change_cb, NULL, data, 0);
}

int ast_extension_state_add_destroy_extended(const char *context, const char *exten,
 ast_state_cb_type change_cb, ast_state_cb_destroy_type destroy_cb, void *data)
{
 return extension_state_add_destroy(context, exten, change_cb, destroy_cb, data, 1);
}

int ast_extension_state_add_extended(const char *context, const char *exten,
 ast_state_cb_type change_cb, void *data)
{
 return extension_state_add_destroy(context, exten, change_cb, NULL, data, 1);
}

/*! \brief Find Hint by callback id */
static int find_hint_by_cb_id(void *obj, void *arg, int flags)
{
 struct ast_state_cb *state_cb;
 const struct ast_hint *hint = obj;
 int *id = arg;

 if ((state_cb = ao2_find(hint->callbacks, id, 0))) {
 ao2_ref(state_cb, -1);
 return CMP_MATCH | CMP_STOP;
 }

 return 0;
}

int ast_extension_state_del(int id, ast_state_cb_type change_cb)
{
 struct ast_state_cb *p_cur;
 int ret = -1;

 if (!id) { /* id == 0 is a callback without extension */
 if (!change_cb) {
 return ret;
 }
 p_cur = ao2_find(statecbs, change_cb, OBJ_UNLINK);
 if (p_cur) {
 ret = 0;
 ao2_ref(p_cur, -1);
 }
 } else { /* callback with extension, find the callback based on ID */
 struct ast_hint *hint;

 ao2_lock(hints);/* Locked to hold off ast_merge_contexts_and_delete */
 hint = ao2_callback(hints, 0, find_hint_by_cb_id, &id);
 if (hint) {
 p_cur = ao2_find(hint->callbacks, &id, OBJ_UNLINK);
 if (p_cur) {
 ret = 0;
 ao2_ref(p_cur, -1);
 }
 ao2_ref(hint, -1);
 }
 ao2_unlock(hints);
 }

 return ret;
}

static int hint_id_cmp(void *obj, void *arg, int flags)
{
 const struct ast_state_cb *cb = obj;
 int *id = arg;

 return (cb->id == *id) ? CMP_MATCH | CMP_STOP : 0;
}

/*!
 * \internal
 * \brief Destroy the given hint object.
 *
 * \param obj Hint to destroy.
 *
 * \return Nothing
 */
static void destroy_hint(void *obj)
{
 struct ast_hint *hint = obj;
 int i;

 ao2_cleanup(hint->callbacks);

 for (i = 0; i < AST_VECTOR_SIZE(&hint->devices); i++) {
 char *device = AST_VECTOR_GET(&hint->devices, i);
 ast_free(device);
 }
 AST_VECTOR_FREE(&hint->devices);
 ast_free(hint->last_presence_subtype);
 ast_free(hint->last_presence_message);
}

/*! \brief Publish a hint removed event */
static int publish_hint_remove(struct ast_hint *hint)
{
 struct stasis_message *message;

 if (!hint_remove_message_type()) {
 return -1;
 }

 if (!(message = stasis_message_create(hint_remove_message_type(), hint))) {
 ao2_ref(hint, -1);
 return -1;
 }

 stasis_publish(ast_device_state_topic_all(), message);

 ao2_ref(message, -1);

 return 0;
}

/*! \brief Remove hint from extension */
static int ast_remove_hint(struct ast_exten *e)
{
 /* Cleanup the Notifys if hint is removed */
 struct ast_hint *hint;

 if (!e) {
 return -1;
 }

 hint = ao2_find(hints, e, OBJ_UNLINK);
 if (!hint) {
 return -1;
 }

 remove_hintdevice(hint);

 /*
 * The extension is being destroyed so we must save some
 * information to notify that the extension is deactivated.
 */
 ao2_lock(hint);
 ast_copy_string(hint->context_name,
 ast_get_context_name(ast_get_extension_context(hint->exten)),
 sizeof(hint->context_name));
 ast_copy_string(hint->exten_name, ast_get_extension_name(hint->exten),
 sizeof(hint->exten_name));
 hint->exten = NULL;
 ao2_unlock(hint);

 publish_hint_remove(hint);

 ao2_ref(hint, -1);

 return 0;
}

/*! \brief Add hint to hint list, check initial extension state */
static int ast_add_hint(struct ast_exten *e)
{
 struct ast_hint *hint_new;
 struct ast_hint *hint_found;
 char *message = NULL;
 char *subtype = NULL;
 int presence_state;

 if (!e) {
 return -1;
 }

 /*
 * We must create the hint we wish to add before determining if
 * it is already in the hints container to avoid possible
 * deadlock when getting the current extension state.
 */
 hint_new = ao2_alloc(sizeof(*hint_new), destroy_hint);
 if (!hint_new) {
 return -1;
 }
 AST_VECTOR_INIT(&hint_new->devices, 8);

 /* Initialize new hint. */
 hint_new->callbacks = ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_MUTEX, 0, NULL, hint_id_cmp);
 if (!hint_new->callbacks) {
 ao2_ref(hint_new, -1);
 return -1;
 }
 hint_new->exten = e;
 if (strstr(e->app, "${") && e->exten[0] == '_') {
 /* The hint is dynamic and hasn't been evaluted yet */
 hint_new->laststate = AST_DEVICE_INVALID;
 hint_new->last_presence_state = AST_PRESENCE_INVALID;
 } else {
 hint_new->laststate = ast_extension_state2(e, NULL);
 if ((presence_state = extension_presence_state_helper(e, &subtype, &message)) > 0) {
 hint_new->last_presence_state = presence_state;
 hint_new->last_presence_subtype = subtype;
 hint_new->last_presence_message = message;
 }
 }

 /* Prevent multiple add hints from adding the same hint at the same time. */
 ao2_lock(hints);

 /* Search if hint exists, do nothing */
 hint_found = ao2_find(hints, e, 0);
 if (hint_found) {
 ao2_ref(hint_found, -1);
 ao2_unlock(hints);
 ao2_ref(hint_new, -1);
 ast_debug(2, "HINTS: Not re-adding existing hint %s: %s\n",
 ast_get_extension_name(e), ast_get_extension_app(e));
 return -1;
 }

 /* Add new hint to the hints container */
 ast_debug(2, "HINTS: Adding hint %s: %s\n",
 ast_get_extension_name(e), ast_get_extension_app(e));
 ao2_link(hints, hint_new);
 if (add_hintdevice(hint_new, ast_get_extension_app(e))) {
 ast_log(LOG_WARNING, "Could not add devices for hint: %s@%s.\n",
 ast_get_extension_name(e),
 ast_get_context_name(ast_get_extension_context(e)));
 }

 /* if not dynamic */
 if (!(strstr(e->app, "${") && e->exten[0] == '_')) {
 struct ast_state_cb *state_cb;
 struct ao2_iterator cb_iter;

 /* For general callbacks */
 cb_iter = ao2_iterator_init(statecbs, 0);
 for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
 execute_state_callback(state_cb->change_cb,
 ast_get_context_name(ast_get_extension_context(e)),
 ast_get_extension_name(e),
 state_cb->data,
 AST_HINT_UPDATE_DEVICE,
 hint_new,
 NULL);
 }
 ao2_iterator_destroy(&cb_iter);
 }
 ao2_unlock(hints);
 ao2_ref(hint_new, -1);

 return 0;
}

/*! \brief Publish a hint changed event */
static int publish_hint_change(struct ast_hint *hint, struct ast_exten *ne)
{
 struct stasis_message *message;

 if (!hint_change_message_type()) {
 return -1;
 }

 if (!(message = stasis_message_create(hint_change_message_type(), hint))) {
 ao2_ref(hint, -1);
 return -1;
 }

 stasis_publish(ast_device_state_topic_all(), message);
 stasis_publish(ast_presence_state_topic_all(), message);

 ao2_ref(message, -1);

 return 0;
}

/*! \brief Change hint for an extension */
static int ast_change_hint(struct ast_exten *oe, struct ast_exten *ne)
{
 struct ast_hint *hint;

 if (!oe || !ne) {
 return -1;
 }

 ao2_lock(hints);/* Locked to hold off others while we move the hint around. */

 /*
 * Unlink the hint from the hints container as the extension
 * name (which is the hash value) could change.
 */
 hint = ao2_find(hints, oe, OBJ_UNLINK);
 if (!hint) {
 ao2_unlock(hints);
 ast_mutex_unlock(&context_merge_lock);
 return -1;
 }

 remove_hintdevice(hint);

 /* Update the hint and put it back in the hints container. */
 ao2_lock(hint);
 hint->exten = ne;

 ao2_unlock(hint);

 ao2_link(hints, hint);
 if (add_hintdevice(hint, ast_get_extension_app(ne))) {
 ast_log(LOG_WARNING, "Could not add devices for hint: %s@%s.\n",
 ast_get_extension_name(ne),
 ast_get_context_name(ast_get_extension_context(ne)));
 }
 ao2_unlock(hints);

 publish_hint_change(hint, ne);

 ao2_ref(hint, -1);

 return 0;
}

/*! \brief Get hint for channel */
int ast_get_hint(char *hint, int hintsize, char *name, int namesize, struct ast_channel *c, const char *context, const char *exten)
{
 struct ast_exten *e = ast_hint_extension(c, context, exten);

 if (e) {
 if (hint)
 ast_copy_string(hint, ast_get_extension_app(e), hintsize);
 if (name) {
 const char *tmp = ast_get_extension_app_data(e);
 if (tmp)
 ast_copy_string(name, tmp, namesize);
 }
 return -1;
 }
 return 0;
}

/*! \brief Get hint for channel */
int ast_str_get_hint(struct ast_str **hint, ssize_t hintsize, struct ast_str **name, ssize_t namesize, struct ast_channel *c, const char *context, const char *exten)
{
 struct ast_exten *e = ast_hint_extension(c, context, exten);

 if (!e) {
 return 0;
 }

 if (hint) {
 ast_str_set(hint, hintsize, "%s", ast_get_extension_app(e));
 }
 if (name) {
 const char *tmp = ast_get_extension_app_data(e);
 if (tmp) {
 ast_str_set(name, namesize, "%s", tmp);
 }
 }
 return -1;
}

int ast_exists_extension(struct ast_channel *c, const char *context, const char *exten, int priority, const char *callerid)
{
 return pbx_extension_helper(c, NULL, context, exten, priority, NULL, callerid, E_MATCH, 0, 0);
}

int ast_findlabel_extension(struct ast_channel *c, const char *context, const char *exten, const char *label, const char *callerid)
{
 return pbx_extension_helper(c, NULL, context, exten, 0, label, callerid, E_FINDLABEL, 0, 0);
}

int ast_findlabel_extension2(struct ast_channel *c, struct ast_context *con, const char *exten, const char *label, const char *callerid)
{
 return pbx_extension_helper(c, con, NULL, exten, 0, label, callerid, E_FINDLABEL, 0, 0);
}

int ast_canmatch_extension(struct ast_channel *c, const char *context, const char *exten, int priority, const char *callerid)
{
 return pbx_extension_helper(c, NULL, context, exten, priority, NULL, callerid, E_CANMATCH, 0, 0);
}

int ast_matchmore_extension(struct ast_channel *c, const char *context, const char *exten, int priority, const char *callerid)
{
 return pbx_extension_helper(c, NULL, context, exten, priority, NULL, callerid, E_MATCHMORE, 0, 0);
}

int ast_spawn_extension(struct ast_channel *c, const char *context, const char *exten, int priority, const char *callerid, int *found, int combined_find_spawn)
{
 return pbx_extension_helper(c, NULL, context, exten, priority, NULL, callerid, E_SPAWN, found, combined_find_spawn);
}

void ast_pbx_h_exten_run(struct ast_channel *chan, const char *context)
{
 int autoloopflag;
 int found;
 int spawn_error;

 ast_channel_lock(chan);

 /*
 * Make sure that the channel is marked as hungup since we are
 * going to run the h exten on it.
 */
 ast_softhangup_nolock(chan, AST_SOFTHANGUP_HANGUP_EXEC);

 /* Set h exten location */
 if (context != ast_channel_context(chan)) {
 ast_channel_context_set(chan, context);
 }
 ast_channel_exten_set(chan, "h");
 ast_channel_priority_set(chan, 1);

 /* Save autoloop flag */
 autoloopflag = ast_test_flag(ast_channel_flags(chan), AST_FLAG_IN_AUTOLOOP);
 ast_set_flag(ast_channel_flags(chan), AST_FLAG_IN_AUTOLOOP);
 ast_channel_unlock(chan);

 for (;;) {
 spawn_error = ast_spawn_extension(chan, ast_channel_context(chan),
 ast_channel_exten(chan), ast_channel_priority(chan),
 S_COR(ast_channel_caller(chan)->id.number.valid,
 ast_channel_caller(chan)->id.number.str, NULL), &found, 1);

 ast_channel_lock(chan);
 if (spawn_error) {
 /* The code after the loop needs the channel locked. */
 break;
 }
 ast_channel_priority_set(chan, ast_channel_priority(chan) + 1);
 ast_channel_unlock(chan);
 }
 if (found && spawn_error) {
 /* Something bad happened, or a hangup has been requested. */
 ast_debug(1, "Spawn extension (%s,%s,%d) exited non-zero on '%s'\n",
 ast_channel_context(chan), ast_channel_exten(chan),
 ast_channel_priority(chan), ast_channel_name(chan));
 ast_verb(2, "Spawn extension (%s, %s, %d) exited non-zero on '%s'\n",
 ast_channel_context(chan), ast_channel_exten(chan),
 ast_channel_priority(chan), ast_channel_name(chan));
 }

 /* An "h" exten has been run, so indicate that one has been run. */
 ast_set_flag(ast_channel_flags(chan), AST_FLAG_BRIDGE_HANGUP_RUN);

 /* Restore autoloop flag */
 ast_set2_flag(ast_channel_flags(chan), autoloopflag, AST_FLAG_IN_AUTOLOOP);
 ast_channel_unlock(chan);
}

/*! helper function to set extension and priority */
void set_ext_pri(struct ast_channel *c, const char *exten, int pri)
{
 ast_channel_lock(c);
 ast_channel_exten_set(c, exten);
 ast_channel_priority_set(c, pri);
 ast_channel_unlock(c);
}

/*!
 * \brief collect digits from the channel into the buffer.
 * \param c, buf, buflen, pos
 * \param waittime is in milliseconds
 * \retval 0 on timeout or done.
 * \retval -1 on error.
*/
static int collect_digits(struct ast_channel *c, int waittime, char *buf, int buflen, int pos)
{
 int digit;

 buf[pos] = '\0'; /* make sure it is properly terminated */
 while (ast_matchmore_extension(c, ast_channel_context(c), buf, 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 /* As long as we're willing to wait, and as long as it's not defined,
 keep reading digits until we can't possibly get a right answer anymore. */
 digit = ast_waitfordigit(c, waittime);
 if (ast_channel_softhangup_internal_flag(c) & AST_SOFTHANGUP_ASYNCGOTO) {
 ast_channel_clear_softhangup(c, AST_SOFTHANGUP_ASYNCGOTO);
 } else {
 if (!digit) /* No entry */
 break;
 if (digit < 0) /* Error, maybe a hangup */
 return -1;
 if (pos < buflen - 1) { /* XXX maybe error otherwise ? */
 buf[pos++] = digit;
 buf[pos] = '\0';
 }
 waittime = ast_channel_pbx(c)->dtimeoutms;
 }
 }
 return 0;
}

static enum ast_pbx_result __ast_pbx_run(struct ast_channel *c,
 struct ast_pbx_args *args)
{
 int found = 0; /* set if we find at least one match */
 int res = 0;
 int autoloopflag;
 int error = 0; /* set an error conditions */
 struct ast_pbx *pbx;
 ast_callid callid;

 /* A little initial setup here */
 if (ast_channel_pbx(c)) {
 ast_log(LOG_WARNING, "%s already has PBX structure??\n", ast_channel_name(c));
 /* XXX and now what ? */
 ast_free(ast_channel_pbx(c));
 }
 if (!(pbx = ast_calloc(1, sizeof(*pbx)))) {
 return AST_PBX_FAILED;
 }

 callid = ast_read_threadstorage_callid();
 /* If the thread isn't already associated with a callid, we should create that association. */
 if (!callid) {
 /* Associate new PBX thread with the channel call id if it is availble.
 * If not, create a new one instead.
 */
 callid = ast_channel_callid(c);
 if (!callid) {
 callid = ast_create_callid();
 if (callid) {
 ast_channel_lock(c);
 ast_channel_callid_set(c, callid);
 ast_channel_unlock(c);
 }
 }
 ast_callid_threadassoc_add(callid);
 callid = 0;
 }

 ast_channel_pbx_set(c, pbx);
 /* Set reasonable defaults */
 ast_channel_pbx(c)->rtimeoutms = 10000;
 ast_channel_pbx(c)->dtimeoutms = 5000;

 ast_channel_lock(c);
 autoloopflag = ast_test_flag(ast_channel_flags(c), AST_FLAG_IN_AUTOLOOP); /* save value to restore at the end */
 ast_set_flag(ast_channel_flags(c), AST_FLAG_IN_AUTOLOOP);
 ast_channel_unlock(c);

 if (ast_strlen_zero(ast_channel_exten(c))) {
 /* If not successful fall back to 's' - but only if there is no given exten */
 ast_verb(2, "Starting %s at %s,%s,%d failed so falling back to exten 's'\n", ast_channel_name(c), ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c));
 /* XXX the original code used the existing priority in the call to
 * ast_exists_extension(), and reset it to 1 afterwards.
 * I believe the correct thing is to set it to 1 immediately.
 */
 set_ext_pri(c, "s", 1);
 }

 for (;;) {
 char dst_exten[256]; /* buffer to accumulate digits */
 int pos = 0; /* XXX should check bounds */
 int digit = 0;
 int invalid = 0;
 int timeout = 0;

 /* No digits pressed yet */
 dst_exten[pos] = '\0';

 /* loop on priorities in this context/exten */
 while (!(res = ast_spawn_extension(c, ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c),
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL),
 &found, 1))) {

 if (!ast_check_hangup(c)) {
 ast_channel_priority_set(c, ast_channel_priority(c) + 1);
 continue;
 }

 /* Check softhangup flags. */
 if (ast_channel_softhangup_internal_flag(c) & AST_SOFTHANGUP_ASYNCGOTO) {
 ast_channel_clear_softhangup(c, AST_SOFTHANGUP_ASYNCGOTO);
 continue;
 }
 if (ast_channel_softhangup_internal_flag(c) & AST_SOFTHANGUP_TIMEOUT) {
 if (ast_exists_extension(c, ast_channel_context(c), "T", 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 set_ext_pri(c, "T", 1);
 /* If the AbsoluteTimeout is not reset to 0, we'll get an infinite loop */
 memset(ast_channel_whentohangup(c), 0, sizeof(*ast_channel_whentohangup(c)));
 ast_channel_clear_softhangup(c, AST_SOFTHANGUP_TIMEOUT);
 continue;
 } else if (ast_exists_extension(c, ast_channel_context(c), "e", 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 raise_exception(c, "ABSOLUTETIMEOUT", 1);
 /* If the AbsoluteTimeout is not reset to 0, we'll get an infinite loop */
 memset(ast_channel_whentohangup(c), 0, sizeof(*ast_channel_whentohangup(c)));
 ast_channel_clear_softhangup(c, AST_SOFTHANGUP_TIMEOUT);
 continue;
 }

 /* Call timed out with no special extension to jump to. */
 error = 1;
 break;
 }
 ast_debug(1, "Extension %s, priority %d returned normally even though call was hung up\n",
 ast_channel_exten(c), ast_channel_priority(c));
 error = 1;
 break;
 } /* end while - from here on we can use 'break' to go out */
 if (found && res) {
 /* Something bad happened, or a hangup has been requested. */
 if (strchr("0123456789ABCDEF*#", res)) {
 ast_debug(1, "Oooh, got something to jump out with ('%c')!\n", res);
 pos = 0;
 dst_exten[pos++] = digit = res;
 dst_exten[pos] = '\0';
 } else if (res == AST_PBX_INCOMPLETE) {
 ast_debug(1, "Spawn extension (%s,%s,%d) exited INCOMPLETE on '%s'\n", ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c), ast_channel_name(c));
 ast_verb(2, "Spawn extension (%s, %s, %d) exited INCOMPLETE on '%s'\n", ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c), ast_channel_name(c));

 /* Don't cycle on incomplete - this will happen if the only extension that matches is our "incomplete" extension */
 if (!ast_matchmore_extension(c, ast_channel_context(c), ast_channel_exten(c), 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 invalid = 1;
 } else {
 ast_copy_string(dst_exten, ast_channel_exten(c), sizeof(dst_exten));
 digit = 1;
 pos = strlen(dst_exten);
 }
 } else {
 ast_debug(1, "Spawn extension (%s,%s,%d) exited non-zero on '%s'\n", ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c), ast_channel_name(c));
 ast_verb(2, "Spawn extension (%s, %s, %d) exited non-zero on '%s'\n", ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c), ast_channel_name(c));

 if ((res == AST_PBX_ERROR)
 && ast_exists_extension(c, ast_channel_context(c), "e", 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 /* if we are already on the 'e' exten, don't jump to it again */
 if (!strcmp(ast_channel_exten(c), "e")) {
 ast_verb(2, "Spawn extension (%s, %s, %d) exited ERROR while already on 'e' exten on '%s'\n", ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c), ast_channel_name(c));
 error = 1;
 } else {
 raise_exception(c, "ERROR", 1);
 continue;
 }
 }

 if (ast_channel_softhangup_internal_flag(c) & AST_SOFTHANGUP_ASYNCGOTO) {
 ast_channel_clear_softhangup(c, AST_SOFTHANGUP_ASYNCGOTO);
 continue;
 }
 if (ast_channel_softhangup_internal_flag(c) & AST_SOFTHANGUP_TIMEOUT) {
 if (ast_exists_extension(c, ast_channel_context(c), "T", 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 set_ext_pri(c, "T", 1);
 /* If the AbsoluteTimeout is not reset to 0, we'll get an infinite loop */
 memset(ast_channel_whentohangup(c), 0, sizeof(*ast_channel_whentohangup(c)));
 ast_channel_clear_softhangup(c, AST_SOFTHANGUP_TIMEOUT);
 continue;
 } else if (ast_exists_extension(c, ast_channel_context(c), "e", 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 raise_exception(c, "ABSOLUTETIMEOUT", 1);
 /* If the AbsoluteTimeout is not reset to 0, we'll get an infinite loop */
 memset(ast_channel_whentohangup(c), 0, sizeof(*ast_channel_whentohangup(c)));
 ast_channel_clear_softhangup(c, AST_SOFTHANGUP_TIMEOUT);
 continue;
 }
 /* Call timed out with no special extension to jump to. */
 }
 error = 1;
 break;
 }
 }
 if (error)
 break;

 /*!\note
 * We get here on a failure of some kind: non-existing extension or
 * hangup. We have options, here. We can either catch the failure
 * and continue, or we can drop out entirely. */

 if (invalid
 || (ast_strlen_zero(dst_exten) &&
 !ast_exists_extension(c, ast_channel_context(c), ast_channel_exten(c), 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL)))) {
 /*!\note
 * If there is no match at priority 1, it is not a valid extension anymore.
 * Try to continue at "i" (for invalid) or "e" (for exception) or exit if
 * neither exist.
 */
 if (ast_exists_extension(c, ast_channel_context(c), "i", 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 ast_verb(3, "Channel '%s' sent to invalid extension: context,exten,priority=%s,%s,%d\n",
 ast_channel_name(c), ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c));
 pbx_builtin_setvar_helper(c, "INVALID_EXTEN", ast_channel_exten(c));
 set_ext_pri(c, "i", 1);
 } else if (ast_exists_extension(c, ast_channel_context(c), "e", 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 raise_exception(c, "INVALID", 1);
 } else {
 ast_log(LOG_WARNING, "Channel '%s' sent to invalid extension but no invalid handler: context,exten,priority=%s,%s,%d\n",
 ast_channel_name(c), ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c));
 error = 1; /* we know what to do with it */
 break;
 }
 } else if (ast_channel_softhangup_internal_flag(c) & AST_SOFTHANGUP_TIMEOUT) {
 /* If we get this far with AST_SOFTHANGUP_TIMEOUT, then we know that the "T" extension is next. */
 ast_channel_clear_softhangup(c, AST_SOFTHANGUP_TIMEOUT);
 } else { /* keypress received, get more digits for a full extension */
 int waittime = 0;
 if (digit)
 waittime = ast_channel_pbx(c)->dtimeoutms;
 else if (!autofallthrough)
 waittime = ast_channel_pbx(c)->rtimeoutms;
 if (!waittime) {
 const char *status = pbx_builtin_getvar_helper(c, "DIALSTATUS");
 if (!status)
 status = "UNKNOWN";
 ast_verb(3, "Auto fallthrough, channel '%s' status is '%s'\n", ast_channel_name(c), status);
 if (!strcasecmp(status, "CONGESTION"))
 res = indicate_congestion(c, "10");
 else if (!strcasecmp(status, "CHANUNAVAIL"))
 res = indicate_congestion(c, "10");
 else if (!strcasecmp(status, "BUSY"))
 res = indicate_busy(c, "10");
 error = 1; /* XXX disable message */
 break; /* exit from the 'for' loop */
 }

 if (collect_digits(c, waittime, dst_exten, sizeof(dst_exten), pos))
 break;
 if (res == AST_PBX_INCOMPLETE && ast_strlen_zero(&dst_exten[pos]))
 timeout = 1;
 if (!timeout
 && ast_exists_extension(c, ast_channel_context(c), dst_exten, 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) { /* Prepare the next cycle */
 set_ext_pri(c, dst_exten, 1);
 } else {
 /* No such extension */
 if (!timeout && !ast_strlen_zero(dst_exten)) {
 /* An invalid extension */
 if (ast_exists_extension(c, ast_channel_context(c), "i", 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 ast_verb(3, "Invalid extension '%s' in context '%s' on %s\n", dst_exten, ast_channel_context(c), ast_channel_name(c));
 pbx_builtin_setvar_helper(c, "INVALID_EXTEN", dst_exten);
 set_ext_pri(c, "i", 1);
 } else if (ast_exists_extension(c, ast_channel_context(c), "e", 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 raise_exception(c, "INVALID", 1);
 } else {
 ast_log(LOG_WARNING,
 "Invalid extension '%s', but no rule 'i' or 'e' in context '%s'\n",
 dst_exten, ast_channel_context(c));
 found = 1; /* XXX disable message */
 break;
 }
 } else {
 /* A simple timeout */
 if (ast_exists_extension(c, ast_channel_context(c), "t", 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 ast_verb(3, "Timeout on %s\n", ast_channel_name(c));
 set_ext_pri(c, "t", 1);
 } else if (ast_exists_extension(c, ast_channel_context(c), "e", 1,
 S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
 raise_exception(c, "RESPONSETIMEOUT", 1);
 } else {
 ast_log(LOG_WARNING,
 "Timeout, but no rule 't' or 'e' in context '%s'\n",
 ast_channel_context(c));
 found = 1; /* XXX disable message */
 break;
 }
 }
 }
 }
 }

 if (!found && !error) {
 ast_log(LOG_WARNING, "Don't know what to do with '%s'\n", ast_channel_name(c));
 }

 if (!args || !args->no_hangup_chan) {
 ast_softhangup(c, AST_SOFTHANGUP_APPUNLOAD);
 if (!ast_test_flag(ast_channel_flags(c), AST_FLAG_BRIDGE_HANGUP_RUN)
 && ast_exists_extension(c, ast_channel_context(c), "h", 1,
 S_COR(ast_channel_caller(c)->id.number.valid,
 ast_channel_caller(c)->id.number.str, NULL))) {
 ast_pbx_h_exten_run(c, ast_channel_context(c));
 }
 ast_pbx_hangup_handler_run(c);
 }

 ast_channel_lock(c);
 ast_set2_flag(ast_channel_flags(c), autoloopflag, AST_FLAG_IN_AUTOLOOP);
 ast_clear_flag(ast_channel_flags(c), AST_FLAG_BRIDGE_HANGUP_RUN); /* from one round to the next, make sure this gets cleared */
 ast_channel_unlock(c);
 pbx_destroy(ast_channel_pbx(c));
 ast_channel_pbx_set(c, NULL);

 if (!args || !args->no_hangup_chan) {
 ast_hangup(c);
 }

 return AST_PBX_SUCCESS;
}

/*!
 * \brief Increase call count for channel
 * \retval 0 on success
 * \retval non-zero if a configured limit (maxcalls, maxload, minmemfree) was reached
*/
static int increase_call_count(const struct ast_channel *c)
{
 int failed = 0;
 double curloadavg;
#if defined(HAVE_SYSINFO)
 struct sysinfo sys_info;
#endif

 ast_mutex_lock(&maxcalllock);
 if (ast_option_maxcalls) {
 if (countcalls >= ast_option_maxcalls) {
 ast_log(LOG_WARNING, "Maximum call limit of %d calls exceeded by '%s'!\n", ast_option_maxcalls, ast_channel_name(c));
 failed = -1;
 }
 }
 if (ast_option_maxload) {
 getloadavg(&curloadavg, 1);
 if (curloadavg >= ast_option_maxload) {
 ast_log(LOG_WARNING, "Maximum loadavg limit of %f load exceeded by '%s' (currently %f)!\n", ast_option_maxload, ast_channel_name(c), curloadavg);
 failed = -1;
 }
 }
#if defined(HAVE_SYSINFO)
 if (option_minmemfree) {
 /* Make sure that the free system memory is above the configured low watermark */
 if (!sysinfo(&sys_info)) {
 /* Convert the amount of available RAM from mem_units to MB. The calculation
 * was done this way to avoid overflow problems */
 uint64_t curfreemem = sys_info.freeram + sys_info.bufferram;
 curfreemem *= sys_info.mem_unit;
 curfreemem /= 1024 * 1024;
 if (curfreemem < option_minmemfree) {
 ast_log(LOG_WARNING, "Available system memory (~%" PRIu64 "MB) is below the configured low watermark (%ldMB)\n",
 curfreemem, option_minmemfree);
 failed = -1;
 }
 }
 }
#endif

 if (!failed) {
 countcalls++;
 totalcalls++;
 }
 ast_mutex_unlock(&maxcalllock);

 return failed;
}

static void decrease_call_count(void)
{
 ast_mutex_lock(&maxcalllock);
 if (countcalls > 0)
 countcalls--;
 ast_mutex_unlock(&maxcalllock);
}

static void destroy_exten(struct ast_exten *e)
{
 if (e->priority == PRIORITY_HINT)
 ast_remove_hint(e);

 if (e->peer_table)
 ast_hashtab_destroy(e->peer_table,0);
 if (e->peer_label_table)
 ast_hashtab_destroy(e->peer_label_table, 0);
 if (e->datad)
 e->datad(e->data);
 ast_free(e);
}

static void *pbx_thread(void *data)
{
 /* Oh joyeous kernel, we're a new thread, with nothing to do but
 answer this channel and get it going.
 */
 /* NOTE:
 The launcher of this function _MUST_ increment 'countcalls'
 before invoking the function; it will be decremented when the
 PBX has finished running on the channel
 */
 struct ast_channel *c = data;

 __ast_pbx_run(c, NULL);
 decrease_call_count();

 pthread_exit(NULL);

 return NULL;
}

enum ast_pbx_result ast_pbx_start(struct ast_channel *c)
{
 pthread_t t;

 if (!c) {
 ast_log(LOG_WARNING, "Asked to start thread on NULL channel?\n");
 return AST_PBX_FAILED;
 }

 if (!ast_test_flag(&ast_options, AST_OPT_FLAG_FULLY_BOOTED)) {
 ast_log(LOG_WARNING, "PBX requires Asterisk to be fully booted\n");
 return AST_PBX_FAILED;
 }

 if (increase_call_count(c))
 return AST_PBX_CALL_LIMIT;

 /* Start a new thread, and get something handling this channel. */
 if (ast_pthread_create_detached(&t, NULL, pbx_thread, c)) {
 ast_log(LOG_WARNING, "Failed to create new channel thread\n");
 decrease_call_count();
 return AST_PBX_FAILED;
 }

 return AST_PBX_SUCCESS;
}

enum ast_pbx_result ast_pbx_run_args(struct ast_channel *c, struct ast_pbx_args *args)
{
 enum ast_pbx_result res = AST_PBX_SUCCESS;

 if (!ast_test_flag(&ast_options, AST_OPT_FLAG_FULLY_BOOTED)) {
 ast_log(LOG_WARNING, "PBX requires Asterisk to be fully booted\n");
 return AST_PBX_FAILED;
 }

 if (increase_call_count(c)) {
 return AST_PBX_CALL_LIMIT;
 }

 res = __ast_pbx_run(c, args);

 decrease_call_count();

 return res;
}

enum ast_pbx_result ast_pbx_run(struct ast_channel *c)
{
 return ast_pbx_run_args(c, NULL);
}

int ast_active_calls(void)
{
 return countcalls;
}

int ast_processed_calls(void)
{
 return totalcalls;
}

int pbx_set_autofallthrough(int newval)
{
 int oldval = autofallthrough;
 autofallthrough = newval;
 return oldval;
}

int pbx_set_extenpatternmatchnew(int newval)
{
 int oldval = extenpatternmatchnew;
 extenpatternmatchnew = newval;
 return oldval;
}

void pbx_set_overrideswitch(const char *newval)
{
 if (overrideswitch) {
 ast_free(overrideswitch);
 }
 if (!ast_strlen_zero(newval)) {
 overrideswitch = ast_strdup(newval);
 } else {
 overrideswitch = NULL;
 }
}

/*!
 * \brief lookup for a context with a given name,
 * \retval found context or NULL if not found.
 */
static struct ast_context *find_context(const char *context)
{
 struct fake_context item;

 ast_copy_string(item.name, context, sizeof(item.name));

 return ast_hashtab_lookup(contexts_table, &item);
}

/*!
 * \brief lookup for a context with a given name,
 * \retval with conlock held if found.
 * \retval NULL if not found.
 */
static struct ast_context *find_context_locked(const char *context)
{
 struct ast_context *c;
 struct fake_context item;

 ast_copy_string(item.name, context, sizeof(item.name));

 ast_rdlock_contexts();
 c = ast_hashtab_lookup(contexts_table, &item);
 if (!c) {
 ast_unlock_contexts();
 }

 return c;
}

/*!
 * \brief Remove included contexts.
 * This function locks contexts list by &conlist, search for the right context
 * structure, leave context list locked and call ast_context_remove_include2
 * which removes include, unlock contexts list and return ...
 */
int ast_context_remove_include(const char *context, const char *include, const char *registrar)
{
 int ret = -1;
 struct ast_context *c;

 c = find_context_locked(context);
 if (c) {
 /* found, remove include from this context ... */
 ret = ast_context_remove_include2(c, include, registrar);
 ast_unlock_contexts();
 }
 return ret;
}

/*!
 * \brief Locks context, remove included contexts, unlocks context.
 * When we call this function, &conlock lock must be locked, because when
 * we giving *con argument, some process can remove/change this context
 * and after that there can be segfault.
 *
 * \retval 0 on success.
 * \retval -1 on failure.
 */
int ast_context_remove_include2(struct ast_context *con, const char *include, const char *registrar)
{
 int ret = -1;
 int idx;

 ast_wrlock_context(con);

 /* find our include */
 for (idx = 0; idx < ast_context_includes_count(con); idx++) {
 struct ast_include *i = AST_VECTOR_GET(&con->includes, idx);

 if (!strcmp(ast_get_include_name(i), include) &&
 (!registrar || !strcmp(ast_get_include_registrar(i), registrar))) {

 /* remove from list */
 ast_verb(3, "Removing inclusion of context '%s' in context '%s; registrar=%s'\n", include, ast_get_context_name(con), registrar);
 AST_VECTOR_REMOVE_ORDERED(&con->includes, idx);

 /* free include and return */
 include_free(i);
 ret = 0;
 break;
 }
 }

 ast_unlock_context(con);

 return ret;
}

/*!
 * \note This function locks contexts list by &conlist, search for the rigt context
 * structure, leave context list locked and call ast_context_remove_switch2
 * which removes switch, unlock contexts list and return ...
 */
int ast_context_remove_switch(const char *context, const char *sw, const char *data, const char *registrar)
{
 int ret = -1; /* default error return */
 struct ast_context *c;

 c = find_context_locked(context);
 if (c) {
 /* remove switch from this context ... */
 ret = ast_context_remove_switch2(c, sw, data, registrar);
 ast_unlock_contexts();
 }
 return ret;
}

/*!
 * \brief This function locks given context, removes switch, unlock context and
 * return.
 * \note When we call this function, &conlock lock must be locked, because when
 * we giving *con argument, some process can remove/change this context
 * and after that there can be segfault.
 *
 */
int ast_context_remove_switch2(struct ast_context *con, const char *sw, const char *data, const char *registrar)
{
 int idx;
 int ret = -1;

 ast_wrlock_context(con);

 /* walk switches */
 for (idx = 0; idx < ast_context_switches_count(con); idx++) {
 struct ast_sw *i = AST_VECTOR_GET(&con->alts, idx);

 if (!strcmp(ast_get_switch_name(i), sw) &&
 !strcmp(ast_get_switch_data(i), data) &&
 (!registrar || !strcmp(ast_get_switch_registrar(i), registrar))) {

 /* found, remove from list */
 ast_verb(3, "Removing switch '%s' from context '%s; registrar=%s'\n", sw, ast_get_context_name(con), registrar);
 AST_VECTOR_REMOVE_ORDERED(&con->alts, idx);

 /* free switch and return */
 sw_free(i);
 ret = 0;
 break;
 }
 }

 ast_unlock_context(con);

 return ret;
}

/*! \note This function will lock conlock. */
int ast_context_remove_extension(const char *context, const char *extension, int priority, const char *registrar)
{
 return ast_context_remove_extension_callerid(context, extension, priority, NULL, AST_EXT_MATCHCID_ANY, registrar);
}

int ast_context_remove_extension_callerid(const char *context, const char *extension, int priority, const char *callerid, int matchcallerid, const char *registrar)
{
 int ret = -1; /* default error return */
 struct ast_context *c;

 c = find_context_locked(context);
 if (c) { /* ... remove extension ... */
 ret = ast_context_remove_extension_callerid2(c, extension, priority, callerid,
 matchcallerid, registrar, 0);
 ast_unlock_contexts();
 }

 return ret;
}

/*!
 * \brief This functionc locks given context, search for the right extension and
 * fires out all peer in this extensions with given priority. If priority
 * is set to 0, all peers are removed. After that, unlock context and
 * return.
 * \note When do you want to call this function, make sure that &conlock is locked,
 * because some process can handle with your *con context before you lock
 * it.
 *
 */
int ast_context_remove_extension2(struct ast_context *con, const char *extension, int priority, const char *registrar, int already_locked)
{
 return ast_context_remove_extension_callerid2(con, extension, priority, NULL, AST_EXT_MATCHCID_ANY, registrar, already_locked);
}

int ast_context_remove_extension_callerid2(struct ast_context *con, const char *extension, int priority, const char *callerid, int matchcallerid, const char *registrar, int already_locked)
{
 struct ast_exten *exten, *prev_exten = NULL;
 struct ast_exten *peer;
 struct ast_exten ex, *exten2, *exten3;
 char dummy_name[1024];
 char dummy_cid[1024];
 struct ast_exten *previous_peer = NULL;
 struct ast_exten *next_peer = NULL;
 int found = 0;

 if (!already_locked)
 ast_wrlock_context(con);

#ifdef NEED_DEBUG
 ast_verb(3,"Removing %s/%s/%d%s%s from trees, registrar=%s\n", con->name, extension, priority, matchcallerid ? "/" : "", matchcallerid ? callerid : "", registrar);
#endif
#ifdef CONTEXT_DEBUG
 check_contexts(__FILE__, __LINE__);
#endif
 /* find this particular extension */
 ex.exten = dummy_name;
 ext_strncpy(dummy_name, extension, sizeof(dummy_name), 1);
 ex.matchcid = matchcallerid;
 if (callerid) {
 ex.cidmatch = dummy_cid;
 ext_strncpy(dummy_cid, callerid, sizeof(dummy_cid), 1);
 } else {
 ex.cidmatch = NULL;
 }
 exten = ast_hashtab_lookup(con->root_table, &ex);
 if (exten) {
 if (priority == 0) {
 exten2 = ast_hashtab_remove_this_object(con->root_table, exten);
 if (!exten2)
 ast_log(LOG_ERROR,"Trying to delete the exten %s from context %s, but could not remove from the root_table\n", extension, con->name);
 if (con->pattern_tree) {
 struct match_char *x = add_exten_to_pattern_tree(con, exten, 1);

 if (x->exten) { /* this test for safety purposes */
 x->deleted = 1; /* with this marked as deleted, it will never show up in the scoreboard, and therefore never be found */
 x->exten = 0; /* get rid of what will become a bad pointer */
 } else {
 ast_log(LOG_WARNING,"Trying to delete an exten from a context, but the pattern tree node returned isn't a full extension\n");
 }
 }
 } else {
 ex.priority = priority;
 exten2 = ast_hashtab_lookup(exten->peer_table, &ex);
 if (exten2) {
 if (exten2->label) { /* if this exten has a label, remove that, too */
 exten3 = ast_hashtab_remove_this_object(exten->peer_label_table,exten2);
 if (!exten3) {
 ast_log(LOG_ERROR, "Did not remove this priority label (%d/%s) "
 "from the peer_label_table of context %s, extension %s!\n",
 priority, exten2->label, con->name, exten2->name);
 }
 }

 exten3 = ast_hashtab_remove_this_object(exten->peer_table, exten2);
 if (!exten3) {
 ast_log(LOG_ERROR, "Did not remove this priority (%d) from the "
 "peer_table of context %s, extension %s!\n",
 priority, con->name, exten2->name);
 }
 if (exten2 == exten && exten2->peer) {
 exten2 = ast_hashtab_remove_this_object(con->root_table, exten);
 ast_hashtab_insert_immediate(con->root_table, exten2->peer);
 }
 if (ast_hashtab_size(exten->peer_table) == 0) {
 /* well, if the last priority of an exten is to be removed,
 then, the extension is removed, too! */
 exten3 = ast_hashtab_remove_this_object(con->root_table, exten);
 if (!exten3) {
 ast_log(LOG_ERROR, "Did not remove this exten (%s) from the "
 "context root_table (%s) (priority %d)\n",
 exten->name, con->name, priority);
 }
 if (con->pattern_tree) {
 struct match_char *x = add_exten_to_pattern_tree(con, exten, 1);
 if (x->exten) { /* this test for safety purposes */
 x->deleted = 1; /* with this marked as deleted, it will never show up in the scoreboard, and therefore never be found */
 x->exten = 0; /* get rid of what will become a bad pointer */
 }
 }
 }
 } else {
 ast_log(LOG_ERROR,"Could not find priority %d of exten %s in context %s!\n",
 priority, exten->name, con->name);
 }
 }
 } else {
 /* hmmm? this exten is not in this pattern tree? */
 ast_log(LOG_WARNING,"Cannot find extension %s in root_table in context %s\n",
 extension, con->name);
 }
#ifdef NEED_DEBUG
 if (con->pattern_tree) {
 ast_log(LOG_NOTICE,"match char tree after exten removal:\n");
 log_match_char_tree(con->pattern_tree, " ");
 }
#endif

 /* scan the extension list to find first matching extension-registrar */
 for (exten = con->root; exten; prev_exten = exten, exten = exten->next) {
 if (!strcmp(exten->exten, ex.exten) &&
 (!matchcallerid ||
 (!ast_strlen_zero(ex.cidmatch) && !ast_strlen_zero(exten->cidmatch) && !strcmp(exten->cidmatch, ex.cidmatch)) ||
 (ast_strlen_zero(ex.cidmatch) && ast_strlen_zero(exten->cidmatch)))) {
 break;
 }
 }
 if (!exten) {
 /* we can't find right extension */
 if (!already_locked)
 ast_unlock_context(con);
 return -1;
 }

 /* scan the priority list to remove extension with exten->priority == priority */
 for (peer = exten, next_peer = exten->peer ? exten->peer : exten->next;
 peer && !strcmp(peer->exten, ex.exten) &&
 (!callerid || (!matchcallerid && !peer->matchcid) || (matchcallerid && peer->matchcid && !strcmp(peer->cidmatch, ex.cidmatch))) ;
 peer = next_peer, next_peer = next_peer ? (next_peer->peer ? next_peer->peer : next_peer->next) : NULL) {

 if ((priority == 0 || peer->priority == priority) &&
 (!registrar || !strcmp(peer->registrar, registrar) )) {
 found = 1;

 /* we are first priority extension? */
 if (!previous_peer) {
 /*
 * We are first in the priority chain, so must update the extension chain.
 * The next node is either the next priority or the next extension
 */
 struct ast_exten *next_node = peer->peer ? peer->peer : peer->next;
 if (peer->peer) {
 /* move the peer_table and peer_label_table down to the next peer, if
 it is there */
 peer->peer->peer_table = peer->peer_table;
 peer->peer->peer_label_table = peer->peer_label_table;
 peer->peer_table = NULL;
 peer->peer_label_table = NULL;
 }
 if (!prev_exten) { /* change the root... */
 con->root = next_node;
 } else {
 prev_exten->next = next_node; /* unlink */
 }
 if (peer->peer) { /* update the new head of the pri list */
 peer->peer->next = peer->next;
 }
 } else { /* easy, we are not first priority in extension */
 previous_peer->peer = peer->peer;
 }


 /* now, free whole priority extension */
 destroy_exten(peer);
 } else {
 previous_peer = peer;
 }
 }
 if (!already_locked)
 ast_unlock_context(con);
 return found ? 0 : -1;
}


/*!
 * \note This function locks contexts list by &conlist, searches for the right context
 * structure, and locks the macrolock mutex in that context.
 * macrolock is used to limit a macro to be executed by one call at a time.
 * \param context The context
 */
int ast_context_lockmacro(const char *context)
{
 struct ast_context *c;
 int ret = -1;

 c = find_context_locked(context);
 if (c) {
 ast_unlock_contexts();

 /* if we found context, lock macrolock */
 ret = ast_mutex_lock(&c->macrolock);
 }

 return ret;
}

/*!
 * \note This function locks contexts list by &conlist, searches for the right context
 * structure, and unlocks the macrolock mutex in that context.
 * macrolock is used to limit a macro to be executed by one call at a time.
 * \param context The context
 */
int ast_context_unlockmacro(const char *context)
{
 struct ast_context *c;
 int ret = -1;

 c = find_context_locked(context);
 if (c) {
 ast_unlock_contexts();

 /* if we found context, unlock macrolock */
 ret = ast_mutex_unlock(&c->macrolock);
 }

 return ret;
}

/*
 * Help for CLI commands ...
 */

/*! \brief handle_show_hints: CLI support for listing registered dial plan hints */
static char *handle_show_hints(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
{
 struct ast_hint *hint;
 int num = 0;
 int watchers;
 struct ao2_iterator i;
 char buf[AST_MAX_EXTENSION+AST_MAX_CONTEXT+2];

 switch (cmd) {
 case CLI_INIT:
 e->command = "core show hints";
 e->usage =
 "Usage: core show hints\n"
 " List registered hints.\n"
 " Hint details are shown in five columns. In order from left to right, they are:\n"
 " 1. Hint extension URI.\n"
 " 2. List of mapped device or presence state identifiers.\n"
 " 3. Current extension state. The aggregate of mapped device states.\n"
 " 4. Current presence state for the mapped presence state provider.\n"
 " 5. Watchers - number of subscriptions and other entities watching this hint.\n";
 return NULL;
 case CLI_GENERATE:
 return NULL;
 }

 if (ao2_container_count(hints) == 0) {
 ast_cli(a->fd, "There are no registered dialplan hints\n");
 return CLI_SUCCESS;
 }
 /* ... we have hints ... */
 ast_cli(a->fd, "\n -= Registered Asterisk Dial Plan Hints =-\n");

 i = ao2_iterator_init(hints, 0);
 for (; (hint = ao2_iterator_next(&i)); ao2_ref(hint, -1)) {
 ao2_lock(hint);
 if (!hint->exten) {
 /* The extension has already been destroyed */
 ao2_unlock(hint);
 continue;
 }
 watchers = ao2_container_count(hint->callbacks);
 snprintf(buf, sizeof(buf), "%s@%s",
 ast_get_extension_name(hint->exten),
 ast_get_context_name(ast_get_extension_context(hint->exten)));

 ast_cli(a->fd, "%-20.20s: %-20.20s State:%-15.15s Presence:%-15.15s Watchers %2d\n",
 buf,
 ast_get_extension_app(hint->exten),
 ast_extension_state2str(hint->laststate),
 ast_presence_state2str(hint->last_presence_state),
 watchers);

 ao2_unlock(hint);
 num++;
 }
 ao2_iterator_destroy(&i);

 ast_cli(a->fd, "----------------\n");
 ast_cli(a->fd, "- %d hints registered\n", num);
 return CLI_SUCCESS;
}

/*! \brief autocomplete for CLI command 'core show hint' */
static char *complete_core_show_hint(const char *line, const char *word, int pos, int state)
{
 struct ast_hint *hint;