Merged revisions 107173 via svnmerge from
[asterisk/asterisk.git] / main / pbx.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 1999 - 2008, Digium, Inc.
5  *
6  * Mark Spencer <markster@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18
19 /*! \file
20  *
21  * \brief Core PBX routines.
22  *
23  * \author Mark Spencer <markster@digium.com>
24  */
25
26 #include "asterisk.h"
27
28 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
29
30 #include "asterisk/_private.h"
31 #include "asterisk/paths.h"     /* use ast_config_AST_SYSTEM_NAME */
32 #include <ctype.h>
33 #include <time.h>
34 #include <sys/time.h>
35 #if defined(HAVE_SYSINFO)
36 #include <sys/sysinfo.h>
37 #endif
38 #if defined(SOLARIS)
39 #include <sys/loadavg.h>
40 #endif
41
42 #include "asterisk/lock.h"
43 #include "asterisk/cli.h"
44 #include "asterisk/pbx.h"
45 #include "asterisk/channel.h"
46 #include "asterisk/file.h"
47 #include "asterisk/callerid.h"
48 #include "asterisk/cdr.h"
49 #include "asterisk/config.h"
50 #include "asterisk/term.h"
51 #include "asterisk/time.h"
52 #include "asterisk/manager.h"
53 #include "asterisk/ast_expr.h"
54 #include "asterisk/linkedlists.h"
55 #define SAY_STUBS       /* generate declarations and stubs for say methods */
56 #include "asterisk/say.h"
57 #include "asterisk/utils.h"
58 #include "asterisk/causes.h"
59 #include "asterisk/musiconhold.h"
60 #include "asterisk/app.h"
61 #include "asterisk/devicestate.h"
62 #include "asterisk/stringfields.h"
63 #include "asterisk/event.h"
64 #include "asterisk/hashtab.h"
65 #include "asterisk/module.h"
66 #include "asterisk/indications.h"
67
68 /*!
69  * \note I M P O R T A N T :
70  *
71  *              The speed of extension handling will likely be among the most important
72  * aspects of this PBX.  The switching scheme as it exists right now isn't
73  * terribly bad (it's O(N+M), where N is the # of extensions and M is the avg #
74  * of priorities, but a constant search time here would be great ;-)
75  *
76  * A new algorithm to do searching based on a 'compiled' pattern tree is introduced
77  * here, and shows a fairly flat (constant) search time, even for over
78  * 1000 patterns. Might Still needs some work-- there are some fine points of the matching
79  * spec about tie-breaking based on the characters in character sets, but this
80  * should be do-able via the weight system currently being used.
81  *
82  * Also, using a hash table for context/priority name lookup can help prevent
83  * the find_extension routines from absorbing exponential cpu cycles. I've tested
84  * find_extension with red-black trees, which have O(log2(n)) speed. Right now,
85  * I'm using hash tables, which do searches (ideally) in O(1) time.
86  *
87  */
88
89 #ifdef LOW_MEMORY
90 #define EXT_DATA_SIZE 256
91 #else
92 #define EXT_DATA_SIZE 8192
93 #endif
94
95 #define SWITCH_DATA_LENGTH 256
96
97 #define VAR_BUF_SIZE 4096
98
99 #define VAR_NORMAL              1
100 #define VAR_SOFTTRAN    2
101 #define VAR_HARDTRAN    3
102
103 #define BACKGROUND_SKIP         (1 << 0)
104 #define BACKGROUND_NOANSWER     (1 << 1)
105 #define BACKGROUND_MATCHEXTEN   (1 << 2)
106 #define BACKGROUND_PLAYBACK     (1 << 3)
107
108 AST_APP_OPTIONS(background_opts, {
109         AST_APP_OPTION('s', BACKGROUND_SKIP),
110         AST_APP_OPTION('n', BACKGROUND_NOANSWER),
111         AST_APP_OPTION('m', BACKGROUND_MATCHEXTEN),
112         AST_APP_OPTION('p', BACKGROUND_PLAYBACK),
113 });
114
115 #define WAITEXTEN_MOH           (1 << 0)
116 #define WAITEXTEN_DIALTONE      (1 << 1)
117
118 AST_APP_OPTIONS(waitexten_opts, {
119         AST_APP_OPTION_ARG('m', WAITEXTEN_MOH, 0),
120         AST_APP_OPTION_ARG('d', WAITEXTEN_DIALTONE, 0),
121 });
122
123 struct ast_context;
124 struct ast_app;
125
126 /*!
127    \brief ast_exten: An extension
128         The dialplan is saved as a linked list with each context
129         having it's own linked list of extensions - one item per
130         priority.
131 */
132 struct ast_exten {
133         char *exten;                    /*!< Extension name */
134         int matchcid;                   /*!< Match caller id ? */
135         const char *cidmatch;           /*!< Caller id to match for this extension */
136         int priority;                   /*!< Priority */
137         const char *label;              /*!< Label */
138         struct ast_context *parent;     /*!< The context this extension belongs to  */
139         const char *app;                /*!< Application to execute */
140         struct ast_app *cached_app;     /*!< Cached location of application */
141         void *data;                     /*!< Data to use (arguments) */
142         void (*datad)(void *);          /*!< Data destructor */
143         struct ast_exten *peer;         /*!< Next higher priority with our extension */
144         struct ast_hashtab *peer_table;    /*!< Priorities list in hashtab form -- only on the head of the peer list */
145         struct ast_hashtab *peer_label_table; /*!< labeled priorities in the peers -- only on the head of the peer list */
146         const char *registrar;          /*!< Registrar */
147         struct ast_exten *next;         /*!< Extension with a greater ID */
148         char stuff[0];
149 };
150
151 /*! \brief ast_include: include= support in extensions.conf */
152 struct ast_include {
153         const char *name;
154         const char *rname;                      /*!< Context to include */
155         const char *registrar;                  /*!< Registrar */
156         int hastime;                            /*!< If time construct exists */
157         struct ast_timing timing;               /*!< time construct */
158         struct ast_include *next;               /*!< Link them together */
159         char stuff[0];
160 };
161
162 /*! \brief ast_sw: Switch statement in extensions.conf */
163 struct ast_sw {
164         char *name;
165         const char *registrar;                  /*!< Registrar */
166         char *data;                             /*!< Data load */
167         int eval;
168         AST_LIST_ENTRY(ast_sw) list;
169         char *tmpdata;
170         char stuff[0];
171 };
172
173 /*! \brief ast_ignorepat: Ignore patterns in dial plan */
174 struct ast_ignorepat {
175         const char *registrar;
176         struct ast_ignorepat *next;
177         const char pattern[0];
178 };
179
180 /*! \brief match_char: forms a syntax tree for quick matching of extension patterns */
181 struct match_char
182 {
183         int is_pattern; /* the pattern started with '_' */
184         int deleted;    /* if this is set, then... don't return it */
185         char *x;       /* the pattern itself-- matches a single char */
186         int specificity; /* simply the strlen of x, or 10 for X, 9 for Z, and 8 for N; and '.' and '!' will add 11 ? */
187         struct match_char *alt_char;
188         struct match_char *next_char;
189         struct ast_exten *exten; /* attached to last char of a pattern for exten */
190 };
191
192 struct scoreboard  /* make sure all fields are 0 before calling new_find_extension */
193 {
194         int total_specificity;
195         int total_length;
196         char last_char;   /* set to ! or . if they are the end of the pattern */
197         int canmatch;     /* if the string to match was just too short */
198         struct match_char *node;
199         struct ast_exten *canmatch_exten;
200         struct ast_exten *exten;
201 };
202
203 /*! \brief ast_context: An extension context */
204 struct ast_context {
205         ast_rwlock_t lock;                      /*!< A lock to prevent multiple threads from clobbering the context */
206         struct ast_exten *root;                 /*!< The root of the list of extensions */
207         struct ast_hashtab *root_table;            /*!< For exact matches on the extensions in the pattern tree, and for traversals of the pattern_tree  */
208         struct match_char *pattern_tree;        /*!< A tree to speed up extension pattern matching */
209         struct ast_context *next;               /*!< Link them together */
210         struct ast_include *includes;           /*!< Include other contexts */
211         struct ast_ignorepat *ignorepats;       /*!< Patterns for which to continue playing dialtone */
212         const char *registrar;                  /*!< Registrar */
213         int refcount;                   /*!< each module that would have created this context should inc/dec this as appropriate */
214         AST_LIST_HEAD_NOLOCK(, ast_sw) alts;    /*!< Alternative switches */
215         ast_mutex_t macrolock;                  /*!< A lock to implement "exclusive" macros - held whilst a call is executing in the macro */
216         char name[0];                           /*!< Name of the context */
217 };
218
219
220 /*! \brief ast_app: A registered application */
221 struct ast_app {
222         int (*execute)(struct ast_channel *chan, void *data);
223         const char *synopsis;                   /*!< Synopsis text for 'show applications' */
224         const char *description;                /*!< Description (help text) for 'show application &lt;name&gt;' */
225         AST_RWLIST_ENTRY(ast_app) list;         /*!< Next app in list */
226         struct ast_module *module;              /*!< Module this app belongs to */
227         char name[0];                           /*!< Name of the application */
228 };
229
230 /*! \brief ast_state_cb: An extension state notify register item */
231 struct ast_state_cb {
232         int id;
233         void *data;
234         ast_state_cb_type callback;
235         struct ast_state_cb *next;
236 };
237
238 /*! \brief Structure for dial plan hints
239
240   \note Hints are pointers from an extension in the dialplan to one or
241   more devices (tech/name) 
242         - See \ref AstExtState
243 */
244 struct ast_hint {
245         struct ast_exten *exten;        /*!< Extension */
246         int laststate;                  /*!< Last known state */
247         struct ast_state_cb *callbacks; /*!< Callback list for this extension */
248         AST_RWLIST_ENTRY(ast_hint) list;/*!< Pointer to next hint in list */
249 };
250
251 static const struct cfextension_states {
252         int extension_state;
253         const char * const text;
254 } extension_states[] = {
255         { AST_EXTENSION_NOT_INUSE,                     "Idle" },
256         { AST_EXTENSION_INUSE,                         "InUse" },
257         { AST_EXTENSION_BUSY,                          "Busy" },
258         { AST_EXTENSION_UNAVAILABLE,                   "Unavailable" },
259         { AST_EXTENSION_RINGING,                       "Ringing" },
260         { AST_EXTENSION_INUSE | AST_EXTENSION_RINGING, "InUse&Ringing" },
261         { AST_EXTENSION_ONHOLD,                        "Hold" },
262         { AST_EXTENSION_INUSE | AST_EXTENSION_ONHOLD,  "InUse&Hold" }
263 };
264
265 struct statechange {
266         AST_LIST_ENTRY(statechange) entry;
267         char dev[0];
268 };
269
270 /*!
271  * \brief Data used by the device state thread
272  */
273 static struct {
274         /*! Set to 1 to stop the thread */
275         unsigned int stop:1;
276         /*! The device state monitoring thread */
277         pthread_t thread;
278         /*! Lock for the state change queue */
279         ast_mutex_t lock;
280         /*! Condition for the state change queue */
281         ast_cond_t cond;
282         /*! Queue of state changes */
283         AST_LIST_HEAD_NOLOCK(, statechange) state_change_q;
284 } device_state = {
285         .thread = AST_PTHREADT_NULL,
286 };
287
288 struct pbx_exception {
289         AST_DECLARE_STRING_FIELDS(
290                 AST_STRING_FIELD(context);      /*!< Context associated with this exception */
291                 AST_STRING_FIELD(exten);        /*!< Exten associated with this exception */
292                 AST_STRING_FIELD(reason);               /*!< The exception reason */
293         );
294
295         int priority;                           /*!< Priority associated with this exception */
296 };
297
298 static int pbx_builtin_answer(struct ast_channel *, void *);
299 static int pbx_builtin_goto(struct ast_channel *, void *);
300 static int pbx_builtin_hangup(struct ast_channel *, void *);
301 static int pbx_builtin_background(struct ast_channel *, void *);
302 static int pbx_builtin_wait(struct ast_channel *, void *);
303 static int pbx_builtin_waitexten(struct ast_channel *, void *);
304 static int pbx_builtin_keepalive(struct ast_channel *, void *);
305 static int pbx_builtin_resetcdr(struct ast_channel *, void *);
306 static int pbx_builtin_setamaflags(struct ast_channel *, void *);
307 static int pbx_builtin_ringing(struct ast_channel *, void *);
308 static int pbx_builtin_progress(struct ast_channel *, void *);
309 static int pbx_builtin_congestion(struct ast_channel *, void *);
310 static int pbx_builtin_busy(struct ast_channel *, void *);
311 static int pbx_builtin_noop(struct ast_channel *, void *);
312 static int pbx_builtin_gotoif(struct ast_channel *, void *);
313 static int pbx_builtin_gotoiftime(struct ast_channel *, void *);
314 static int pbx_builtin_execiftime(struct ast_channel *, void *);
315 static int pbx_builtin_saynumber(struct ast_channel *, void *);
316 static int pbx_builtin_saydigits(struct ast_channel *, void *);
317 static int pbx_builtin_saycharacters(struct ast_channel *, void *);
318 static int pbx_builtin_sayphonetic(struct ast_channel *, void *);
319 static int matchcid(const char *cidpattern, const char *callerid);
320 int pbx_builtin_setvar(struct ast_channel *, void *);
321 void log_match_char_tree(struct match_char *node, char *prefix); /* for use anywhere */
322 static int pbx_builtin_setvar_multiple(struct ast_channel *, void *);
323 static int pbx_builtin_importvar(struct ast_channel *, void *);
324 static void set_ext_pri(struct ast_channel *c, const char *exten, int pri); 
325 static void new_find_extension(const char *str, struct scoreboard *score, struct match_char *tree, int length, int spec, const char *callerid);
326 static struct match_char *already_in_tree(struct match_char *current, char *pat);
327 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly);
328 static struct match_char *add_pattern_node(struct ast_context *con, struct match_char *current, char *pattern, int is_pattern, int already, int specificity);
329 static void create_match_char_tree(struct ast_context *con);
330 static struct ast_exten *get_canmatch_exten(struct match_char *node);
331 static void destroy_pattern_tree(struct match_char *pattern_tree);
332 int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b);
333 static int hashtab_compare_extens(const void *ha_a, const void *ah_b);
334 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b);
335 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b);
336 unsigned int ast_hashtab_hash_contexts(const void *obj);
337 static unsigned int hashtab_hash_extens(const void *obj);
338 static unsigned int hashtab_hash_priority(const void *obj);
339 static unsigned int hashtab_hash_labels(const void *obj);
340 static void __ast_internal_context_destroy( struct ast_context *con);
341
342 /* labels, contexts are case sensitive  priority numbers are ints */
343 int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b)
344 {
345         const struct ast_context *ac = ah_a;
346         const struct ast_context *bc = ah_b;
347         /* assume context names are registered in a string table! */
348         return strcmp(ac->name, bc->name);
349 }
350
351 static int hashtab_compare_extens(const void *ah_a, const void *ah_b)
352 {
353         const struct ast_exten *ac = ah_a;
354         const struct ast_exten *bc = ah_b;
355         int x = strcmp(ac->exten, bc->exten);
356         if (x) /* if exten names are diff, then return */
357                 return x;
358         /* but if they are the same, do the cidmatch values match? */
359         if (ac->matchcid && bc->matchcid) {
360                 return strcmp(ac->cidmatch,bc->cidmatch);
361         } else if (!ac->matchcid && !bc->matchcid) {
362                 return 0; /* if there's no matchcid on either side, then this is a match */
363         } else {
364                 return 1; /* if there's matchcid on one but not the other, they are different */
365         }
366 }
367
368 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b)
369 {
370         const struct ast_exten *ac = ah_a;
371         const struct ast_exten *bc = ah_b;
372         return ac->priority != bc->priority;
373 }
374
375 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b)
376 {
377         const struct ast_exten *ac = ah_a;
378         const struct ast_exten *bc = ah_b;
379         return strcmp(ac->label, bc->label);
380 }
381
382 unsigned int ast_hashtab_hash_contexts(const void *obj)
383 {
384         const struct ast_context *ac = obj;
385         return ast_hashtab_hash_string(ac->name);
386 }
387
388 static unsigned int hashtab_hash_extens(const void *obj)
389 {
390         const struct ast_exten *ac = obj;
391         unsigned int x = ast_hashtab_hash_string(ac->exten);
392         unsigned int y = 0;
393         if (ac->matchcid)
394                 y = ast_hashtab_hash_string(ac->cidmatch);
395         return x+y;
396 }
397
398 static unsigned int hashtab_hash_priority(const void *obj)
399 {
400         const struct ast_exten *ac = obj;
401         return ast_hashtab_hash_int(ac->priority);
402 }
403
404 static unsigned int hashtab_hash_labels(const void *obj)
405 {
406         const struct ast_exten *ac = obj;
407         return ast_hashtab_hash_string(ac->label);
408 }
409
410
411 AST_RWLOCK_DEFINE_STATIC(globalslock);
412 static struct varshead globals = AST_LIST_HEAD_NOLOCK_INIT_VALUE;
413
414 static int autofallthrough = 1;
415 static int extenpatternmatchnew = 0;
416
417 /*! \brief Subscription for device state change events */
418 static struct ast_event_sub *device_state_sub;
419
420 AST_MUTEX_DEFINE_STATIC(maxcalllock);
421 static int countcalls;
422 static int totalcalls;
423
424 static AST_RWLIST_HEAD_STATIC(acf_root, ast_custom_function);
425
426 /*! \brief Declaration of builtin applications */
427 static struct pbx_builtin {
428         char name[AST_MAX_APP];
429         int (*execute)(struct ast_channel *chan, void *data);
430         char *synopsis;
431         char *description;
432 } builtins[] =
433 {
434         /* These applications are built into the PBX core and do not
435            need separate modules */
436
437         { "Answer", pbx_builtin_answer,
438         "Answer a channel if ringing",
439         "  Answer([delay]): If the call has not been answered, this application will\n"
440         "answer it. Otherwise, it has no effect on the call. If a delay is specified,\n"
441         "Asterisk will wait this number of milliseconds before returning to\n"
442         "the dialplan after answering the call.\n"
443         },
444
445         { "BackGround", pbx_builtin_background,
446         "Play an audio file while waiting for digits of an extension to go to.",
447         "  Background(filename1[&filename2...][,options[,langoverride][,context]]):\n"
448         "This application will play the given list of files (do not put extension)\n"
449         "while waiting for an extension to be dialed by the calling channel. To\n"
450         "continue waiting for digits after this application has finished playing\n"
451         "files, the WaitExten application should be used. The 'langoverride' option\n"
452         "explicitly specifies which language to attempt to use for the requested sound\n"
453         "files. If a 'context' is specified, this is the dialplan context that this\n"
454         "application will use when exiting to a dialed extension."
455         "  If one of the requested sound files does not exist, call processing will be\n"
456         "terminated.\n"
457         "  Options:\n"
458         "    s - Causes the playback of the message to be skipped\n"
459         "          if the channel is not in the 'up' state (i.e. it\n"
460         "          hasn't been answered yet). If this happens, the\n"
461         "          application will return immediately.\n"
462         "    n - Don't answer the channel before playing the files.\n"
463         "    m - Only break if a digit hit matches a one digit\n"
464         "          extension in the destination context.\n"
465         "This application sets the following channel variable upon completion:\n"
466         " BACKGROUNDSTATUS    The status of the background attempt as a text string, one of\n"
467         "               SUCCESS | FAILED\n"
468         },
469
470         { "Busy", pbx_builtin_busy,
471         "Indicate the Busy condition",
472         "  Busy([timeout]): This application will indicate the busy condition to\n"
473         "the calling channel. If the optional timeout is specified, the calling channel\n"
474         "will be hung up after the specified number of seconds. Otherwise, this\n"
475         "application will wait until the calling channel hangs up.\n"
476         },
477
478         { "Congestion", pbx_builtin_congestion,
479         "Indicate the Congestion condition",
480         "  Congestion([timeout]): This application will indicate the congestion\n"
481         "condition to the calling channel. If the optional timeout is specified, the\n"
482         "calling channel will be hung up after the specified number of seconds.\n"
483         "Otherwise, this application will wait until the calling channel hangs up.\n"
484         },
485
486         { "ExecIfTime", pbx_builtin_execiftime,
487         "Conditional application execution based on the current time",
488         "  ExecIfTime(<times>,<weekdays>,<mdays>,<months>?appname[(appargs)]):\n"
489         "This application will execute the specified dialplan application, with optional\n"
490         "arguments, if the current time matches the given time specification.\n"
491         },
492
493         { "Goto", pbx_builtin_goto,
494         "Jump to a particular priority, extension, or context",
495         "  Goto([[context,]extension,]priority): This application will set the current\n"
496         "context, extension, and priority in the channel structure. After it completes, the\n"
497         "pbx engine will continue dialplan execution at the specified location.\n"
498         "If no specific extension, or extension and context, are specified, then this\n"
499         "application will just set the specified priority of the current extension.\n"
500         "  At least a priority is required as an argument, or the goto will return a -1,\n"
501         "and the channel and call will be terminated.\n"
502         "  If the location that is put into the channel information is bogus, and asterisk cannot\n"
503         "find that location in the dialplan,\n"
504         "then the execution engine will try to find and execute the code in the 'i' (invalid)\n"
505         "extension in the current context. If that does not exist, it will try to execute the\n"
506         "'h' extension. If either or neither the 'h' or 'i' extensions have been defined, the\n"
507         "channel is hung up, and the execution of instructions on the channel is terminated.\n"
508         "What this means is that, for example, you specify a context that does not exist, then\n"
509         "it will not be possible to find the 'h' or 'i' extensions, and the call will terminate!\n"
510         },
511
512         { "GotoIf", pbx_builtin_gotoif,
513         "Conditional goto",
514         "  GotoIf(condition?[labeliftrue]:[labeliffalse]): This application will set the current\n"
515         "context, extension, and priority in the channel structure based on the evaluation of\n"
516         "the given condition. After this application completes, the\n"
517         "pbx engine will continue dialplan execution at the specified location in the dialplan.\n"
518         "The channel will continue at\n"
519         "'labeliftrue' if the condition is true, or 'labeliffalse' if the condition is\n"
520         "false. The labels are specified with the same syntax as used within the Goto\n"
521         "application.  If the label chosen by the condition is omitted, no jump is\n"
522         "performed, and the execution passes to the next instruction.\n"
523         "If the target location is bogus, and does not exist, the execution engine will try \n"
524         "to find and execute the code in the 'i' (invalid)\n"
525         "extension in the current context. If that does not exist, it will try to execute the\n"
526         "'h' extension. If either or neither the 'h' or 'i' extensions have been defined, the\n"
527         "channel is hung up, and the execution of instructions on the channel is terminated.\n"
528         "Remember that this command can set the current context, and if the context specified\n"
529         "does not exist, then it will not be able to find any 'h' or 'i' extensions there, and\n"
530         "the channel and call will both be terminated!\n"
531         },
532
533         { "GotoIfTime", pbx_builtin_gotoiftime,
534         "Conditional Goto based on the current time",
535         "  GotoIfTime(<times>,<weekdays>,<mdays>,<months>?[labeliftrue]:[labeliffalse]):\n"
536         "This application will set the context, extension, and priority in the channel structure\n"
537         "based on the evaluation of the given time specification. After this application completes,\n"
538         "the pbx engine will continue dialplan execution at the specified location in the dialplan.\n"
539         "If the current time is within the given time specification, the channel will continue at\n"
540         "'labeliftrue'. Otherwise the channel will continue at 'labeliffalse'. If the label chosen\n"
541         "by the condition is omitted, no jump is performed, and execution passes to the next\n"
542         "instruction. If the target jump location is bogus, the same actions would be taken as for\n"
543         "Goto.\n"
544         "Further information on the time specification can be found in examples\n"
545         "illustrating how to do time-based context includes in the dialplan.\n"
546         },
547
548         { "ImportVar", pbx_builtin_importvar,
549         "Import a variable from a channel into a new variable",
550         "  ImportVar(newvar=channelname,variable): This application imports a variable\n"
551         "from the specified channel (as opposed to the current one) and stores it as\n"
552         "a variable in the current channel (the channel that is calling this\n"
553         "application). Variables created by this application have the same inheritance\n"
554         "properties as those created with the Set application. See the documentation for\n"
555         "Set for more information.\n"
556         },
557
558         { "Hangup", pbx_builtin_hangup,
559         "Hang up the calling channel",
560         "  Hangup([causecode]): This application will hang up the calling channel.\n"
561         "If a causecode is given the channel's hangup cause will be set to the given\n"
562         "value.\n"
563         },
564
565         { "NoOp", pbx_builtin_noop,
566         "Do Nothing (No Operation)",
567         "  NoOp(): This application does nothing. However, it is useful for debugging\n"
568         "purposes. Any text that is provided as arguments to this application can be\n"
569         "viewed at the Asterisk CLI. This method can be used to see the evaluations of\n"
570         "variables or functions without having any effect. Alternatively, see the\n"
571   "Verbose() application for finer grain control of output at custom verbose levels.\n"
572         },
573
574         { "Progress", pbx_builtin_progress,
575         "Indicate progress",
576         "  Progress(): This application will request that in-band progress information\n"
577         "be provided to the calling channel.\n"
578         },
579
580         { "RaiseException", pbx_builtin_raise_exception,
581         "Handle an exceptional condition",
582         "  RaiseException(<reason>): This application will jump to the \"e\" extension\n"
583         "in the current context, setting the dialplan function EXCEPTION(). If the \"e\"\n"
584         "extension does not exist, the call will hangup.\n"
585         },
586
587         { "ResetCDR", pbx_builtin_resetcdr,
588         "Resets the Call Data Record",
589         "  ResetCDR([options]):  This application causes the Call Data Record to be\n"
590         "reset.\n"
591         "  Options:\n"
592         "    w -- Store the current CDR record before resetting it.\n"
593         "    a -- Store any stacked records.\n"
594         "    v -- Save CDR variables.\n"
595         "    e -- Enable CDR only (negate effects of NoCDR).\n"
596         },
597
598         { "Ringing", pbx_builtin_ringing,
599         "Indicate ringing tone",
600         "  Ringing(): This application will request that the channel indicate a ringing\n"
601         "tone to the user.\n"
602         },
603
604         { "SayAlpha", pbx_builtin_saycharacters,
605         "Say Alpha",
606         "  SayAlpha(string): This application will play the sounds that correspond to\n"
607         "the letters of the given string.\n"
608         },
609
610         { "SayDigits", pbx_builtin_saydigits,
611         "Say Digits",
612         "  SayDigits(digits): This application will play the sounds that correspond\n"
613         "to the digits of the given number. This will use the language that is currently\n"
614         "set for the channel. See the LANGUAGE function for more information on setting\n"
615         "the language for the channel.\n"
616         },
617
618         { "SayNumber", pbx_builtin_saynumber,
619         "Say Number",
620         "  SayNumber(digits[,gender]): This application will play the sounds that\n"
621         "correspond to the given number. Optionally, a gender may be specified.\n"
622         "This will use the language that is currently set for the channel. See the\n"
623         "LANGUAGE function for more information on setting the language for the channel.\n"
624         },
625
626         { "SayPhonetic", pbx_builtin_sayphonetic,
627         "Say Phonetic",
628         "  SayPhonetic(string): This application will play the sounds from the phonetic\n"
629         "alphabet that correspond to the letters in the given string.\n"
630         },
631
632         { "Set", pbx_builtin_setvar,
633         "Set channel variable or function value",
634         "  Set(name=value)\n"
635         "This function can be used to set the value of channel variables or dialplan\n"
636         "functions. When setting variables, if the variable name is prefixed with _,\n"
637         "the variable will be inherited into channels created from the current\n"
638         "channel. If the variable name is prefixed with __, the variable will be\n"
639         "inherited into channels created from the current channel and all children\n"
640         "channels.\n"
641         },
642
643         { "MSet", pbx_builtin_setvar_multiple,
644         "Set channel variable(s) or function value(s)",
645         "  MSet(name1=value1,name2=value2,...)\n"
646         "This function can be used to set the value of channel variables or dialplan\n"
647         "functions. When setting variables, if the variable name is prefixed with _,\n"
648         "the variable will be inherited into channels created from the current\n"
649         "channel. If the variable name is prefixed with __, the variable will be\n"
650         "inherited into channels created from the current channel and all children\n"
651         "channels.\n\n"
652         "MSet behaves in a similar fashion to the way Set worked in 1.2/1.4 and is thus\n"
653         "prone to doing things that you may not expect.  Avoid its use if possible.\n"
654         },
655
656         { "SetAMAFlags", pbx_builtin_setamaflags,
657         "Set the AMA Flags",
658         "  SetAMAFlags([flag]): This application will set the channel's AMA Flags for\n"
659         "  billing purposes.\n"
660         },
661
662         { "Wait", pbx_builtin_wait,
663         "Waits for some time",
664         "  Wait(seconds): This application waits for a specified number of seconds.\n"
665         "Then, dialplan execution will continue at the next priority.\n"
666         "  Note that the seconds can be passed with fractions of a second. For example,\n"
667         "'1.5' will ask the application to wait for 1.5 seconds.\n"
668         },
669
670         { "WaitExten", pbx_builtin_waitexten,
671         "Waits for an extension to be entered",
672         "  WaitExten([seconds][,options]): This application waits for the user to enter\n"
673         "a new extension for a specified number of seconds.\n"
674         "  Note that the seconds can be passed with fractions of a second. For example,\n"
675         "'1.5' will ask the application to wait for 1.5 seconds.\n"
676         "  Options:\n"
677         "    m[(x)] - Provide music on hold to the caller while waiting for an extension.\n"
678         "               Optionally, specify the class for music on hold within parenthesis.\n"
679         },
680
681         { "KeepAlive", pbx_builtin_keepalive,
682         "returns AST_PBX_KEEPALIVE value",
683         "  KeepAlive(): This application is chiefly meant for internal use with Gosubs.\n"
684         "Please do not run it alone from the dialplan!\n"
685         },
686
687 };
688
689 static struct ast_context *contexts;
690 static struct ast_hashtab *contexts_table = NULL;
691
692 AST_RWLOCK_DEFINE_STATIC(conlock);              /*!< Lock for the ast_context list */
693
694 static AST_RWLIST_HEAD_STATIC(apps, ast_app);
695
696 static AST_RWLIST_HEAD_STATIC(switches, ast_switch);
697
698 static int stateid = 1;
699 /* WARNING:
700    When holding this list's lock, do _not_ do anything that will cause conlock
701    to be taken, unless you _already_ hold it. The ast_merge_contexts_and_delete
702    function will take the locks in conlock/hints order, so any other
703    paths that require both locks must also take them in that order.
704 */
705 static AST_RWLIST_HEAD_STATIC(hints, ast_hint);
706 struct ast_state_cb *statecbs;
707
708 /*
709    \note This function is special. It saves the stack so that no matter
710    how many times it is called, it returns to the same place */
711 int pbx_exec(struct ast_channel *c,             /*!< Channel */
712              struct ast_app *app,               /*!< Application */
713              void *data)                        /*!< Data for execution */
714 {
715         int res;
716         struct ast_module_user *u = NULL;
717         const char *saved_c_appl;
718         const char *saved_c_data;
719
720         if (c->cdr && !ast_check_hangup(c))
721                 ast_cdr_setapp(c->cdr, app->name, data);
722
723         /* save channel values */
724         saved_c_appl= c->appl;
725         saved_c_data= c->data;
726
727         c->appl = app->name;
728         c->data = data;
729         if (app->module)
730                 u = __ast_module_user_add(app->module, c);
731         res = app->execute(c, S_OR(data, ""));
732         if (app->module && u)
733                 __ast_module_user_remove(app->module, u);
734         /* restore channel values */
735         c->appl = saved_c_appl;
736         c->data = saved_c_data;
737         return res;
738 }
739
740
741 /*! Go no deeper than this through includes (not counting loops) */
742 #define AST_PBX_MAX_STACK       128
743
744 /*! \brief Find application handle in linked list
745  */
746 struct ast_app *pbx_findapp(const char *app)
747 {
748         struct ast_app *tmp;
749
750         AST_RWLIST_RDLOCK(&apps);
751         AST_RWLIST_TRAVERSE(&apps, tmp, list) {
752                 if (!strcasecmp(tmp->name, app))
753                         break;
754         }
755         AST_RWLIST_UNLOCK(&apps);
756
757         return tmp;
758 }
759
760 static struct ast_switch *pbx_findswitch(const char *sw)
761 {
762         struct ast_switch *asw;
763
764         AST_RWLIST_RDLOCK(&switches);
765         AST_RWLIST_TRAVERSE(&switches, asw, list) {
766                 if (!strcasecmp(asw->name, sw))
767                         break;
768         }
769         AST_RWLIST_UNLOCK(&switches);
770
771         return asw;
772 }
773
774 static inline int include_valid(struct ast_include *i)
775 {
776         if (!i->hastime)
777                 return 1;
778
779         return ast_check_timing(&(i->timing));
780 }
781
782 static void pbx_destroy(struct ast_pbx *p)
783 {
784         ast_free(p);
785 }
786
787 /* form a tree that fully describes all the patterns in a context's extensions 
788  * in this tree, a "node" consists of a series of match_char structs linked in a chain
789  * via the alt_char pointers. More than one pattern can share the same parts of the 
790  * tree as other extensions with the same pattern to that point. The algorithm to
791  * find which pattern best matches a string, would follow **all** matching paths. As
792  * complete matches are found, a "max" match record would be updated if the match first involves 
793  * a longer string, then, on a tie, a smaller total of specificity. This can be accomplished
794  * by recursive calls affecting a shared scoreboard.
795  * As and example, consider these 4 extensions:
796  * (a) NXXNXXXXXX
797  * (b) 307754XXXX 
798  * (c) fax
799  * (d) NXXXXXXXXX
800  *
801  * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
802  * most numbers. For all numbers beginning with 307754, (b) should always win.
803  *
804  * These pattern should form a tree that looks like this:
805  *   { "N" }  --next-->  { "X" }  --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
806  *      |                                                        |
807  *      |                                                        |alt
808  *      |alt                                                     |
809  *      |                                                     { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
810  *      |
811  *   { "3" }  --next-->  { "0" }  --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
812  *      |
813  *      |alt
814  *      |
815  *   { "f" }  --next-->  { "a" }  --next--> { "x"  exten_match: (c) }
816  *
817  *   In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
818  *   fewer CPU cycles than a call to index("23456789",*z), where *z is the char to match...
819  *
820  *   traversal is pretty simple: one routine merely traverses the alt list, and for each match in the pattern,  it calls itself
821  *   on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
822  *   We pass a pointer to a scoreboard down through, also.
823  *   When an exten_match pointer is set, or a '.' or a '!' is encountered, we update the scoreboard only if the length is greater, or in case
824  *   of equal length, if the specificity is lower, and return. Hope the limit on stack depth won't be a problem... this routine should 
825  *   be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
826  *
827  *   In the above example, with the number "3077549999" as the pattern, the traversor should match extensions a, b and d.  All are
828  *   of length 10; but they have total specificities of  96, 46, and 98, respectively. (b) wins with its lower specificity number!
829  *
830  *   Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown. But, it should
831  *   be pretty close to optimal for this sort of overall algorithm.
832  *
833  * */
834
835 /* you only really update the scoreboard, if the new score is BETTER than the 
836  * one stored there. ignore it otherwise.
837  */
838
839
840 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)
841 {
842         /* doing a matchcid() check here would be easy and cheap, but...
843            unfortunately, it only works if an extension can have only one 
844            cid to match. That's not real life. CID patterns need to exist 
845            in the tree for this sort of thing to work properly. */
846
847         /* if this extension is marked as deleted, then skip this -- if it never shows
848            on the scoreboard, it will never be found */
849         if (deleted)
850                 return;
851         if (length > board->total_length) {
852                 board->total_specificity = spec;
853                 board->total_length = length;
854                 board->exten = exten;
855                 board->last_char = last;
856                 board->node = node;
857         } else if (length == board->total_length && spec < board->total_specificity) {
858                 board->total_specificity = spec;
859                 board->total_length = length;
860                 board->exten = exten;
861                 board->last_char = last;
862                 board->node = node;
863         }
864 }
865
866 void log_match_char_tree(struct match_char *node, char *prefix)
867 {
868         char extenstr[40];
869         struct ast_str *my_prefix = ast_str_alloca(1024); 
870
871         extenstr[0] = '\0';
872
873         if (node && node->exten && node->exten)
874                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
875         
876         if (strlen(node->x) > 1) {
877                 ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N', 
878                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"", 
879                         node->exten ? node->exten->exten : "", extenstr);
880         } else {
881                 ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N', 
882                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"", 
883                         node->exten ? node->exten->exten : "", extenstr);
884         }
885
886         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
887
888         if (node->next_char)
889                 log_match_char_tree(node->next_char, my_prefix->str);
890
891         if (node->alt_char)
892                 log_match_char_tree(node->alt_char, prefix);
893 }
894
895 static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
896 {
897         char extenstr[40];
898         struct ast_str *my_prefix = ast_str_alloca(1024);
899         
900         extenstr[0] = '\0';
901
902         if (node && node->exten && node->exten)
903                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
904         
905         if (strlen(node->x) > 1) {
906                 ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N', 
907                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "", 
908                         node->exten ? node->exten->exten : "", extenstr);
909         } else {
910                 ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N', 
911                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "", 
912                         node->exten ? node->exten->exten : "", extenstr);
913         }
914
915         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
916
917         if (node->next_char)
918                 cli_match_char_tree(node->next_char, my_prefix->str, fd);
919
920         if (node->alt_char)
921                 cli_match_char_tree(node->alt_char, prefix, fd);
922 }
923
924 static struct ast_exten *get_canmatch_exten(struct match_char *node)
925 {
926         /* find the exten at the end of the rope */
927         struct match_char *node2 = node;
928
929         for (node2 = node; node2; node2 = node2->next_char) {
930                 if (node2->exten)
931                         return node2->exten;
932         }
933
934         return 0;
935 }
936
937 static struct ast_exten *trie_find_next_match(struct match_char *node)
938 {
939         struct match_char *m3;
940         struct match_char *m4;
941         struct ast_exten *e3;
942         
943         if (node && node->x[0] == '.' && !node->x[1]) /* dot and ! will ALWAYS be next match in a matchmore */
944                 return node->exten;
945         
946         if (node && node->x[0] == '!' && !node->x[1])
947                 return node->exten;
948         
949         if (!node || !node->next_char)
950                 return NULL;
951         
952         m3 = node->next_char;
953
954         if (m3->exten)
955                 return m3->exten;
956         for(m4=m3->alt_char; m4; m4 = m4->alt_char) {
957                 if (m4->exten)
958                         return m4->exten;
959         }
960         for(m4=m3; m4; m4 = m4->alt_char) {
961                 e3 = trie_find_next_match(m3);
962                 if (e3)
963                         return e3;
964         }
965         return NULL;
966 }
967
968 static void new_find_extension(const char *str, struct scoreboard *score, struct match_char *tree, int length, int spec, const char *callerid)
969 {
970         struct match_char *p; /* note minimal stack storage requirements */
971 #ifdef DEBUG_THIS
972         if (tree)
973                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s\n", str, tree->x);
974         else
975                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL\n", str);
976 #endif
977         for (p=tree; p; p=p->alt_char) {
978                 if (p->x[0] == 'N' && p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
979                         if (p->exten && !(*(str+1))) /* if a shorter pattern matches along the way, might as well report it */
980                                 update_scoreboard(score, length+1, spec+p->specificity, p->exten,0,callerid, p->deleted, p);
981
982                         if (p->next_char && ( *(str+1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0))) {
983                                 if (*(str+1))
984                                         new_find_extension(str+1, score, p->next_char, length+1, spec+p->specificity, callerid);
985                                 else
986                                         new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid);
987                         } else if (p->next_char && !*(str+1)) {
988                                 score->canmatch = 1;
989                                 score->canmatch_exten = get_canmatch_exten(p);
990                         } else {
991                                 return;
992                         }
993                 } else if (p->x[0] == 'Z' && p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
994                         if (p->exten && !(*(str+1))) /* if a shorter pattern matches along the way, might as well report it */
995                                 update_scoreboard(score, length+1, spec+p->specificity, p->exten,0,callerid, p->deleted,p);
996
997                         if (p->next_char && ( *(str+1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0))) {
998                                 if (*(str+1))
999                                         new_find_extension(str+1, score, p->next_char, length+1, spec+p->specificity, callerid);
1000                                 else
1001                                         new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid);
1002                         } else if (p->next_char && !*(str+1)) {
1003                                 score->canmatch = 1;
1004                                 score->canmatch_exten = get_canmatch_exten(p);
1005                         } else {
1006                                 return;
1007                         }
1008                 } else if (p->x[0] == 'X' && p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1009                         if (p->exten && !(*(str+1))) /* if a shorter pattern matches along the way, might as well report it */
1010                                 update_scoreboard(score, length+1, spec+p->specificity, p->exten,0,callerid, p->deleted,p);
1011
1012                         if (p->next_char && ( *(str+1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0))) {
1013                                 if (*(str+1))
1014                                         new_find_extension(str+1, score, p->next_char, length+1, spec+p->specificity, callerid);
1015                                 else
1016                                         new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid);
1017                         } else if (p->next_char && !*(str+1)) {
1018                                 score->canmatch = 1;
1019                                 score->canmatch_exten = get_canmatch_exten(p);
1020                         } else {
1021                                 return;
1022                         }
1023                 } else if (p->x[0] == '.' && p->x[1] == 0) {
1024                         /* how many chars will the . match against? */
1025                         int i = 0;
1026                         const char *str2 = str;
1027                         while (*str2++) {
1028                                 i++;
1029                         }
1030                         if (p->exten && !(*(str+1)))
1031                                 update_scoreboard(score, length+i, spec+(i*p->specificity), p->exten, '.', callerid, p->deleted, p);
1032                         if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1033                                 new_find_extension("/", score, p->next_char, length+i, spec+(p->specificity*i), callerid);
1034                         }
1035                         return;
1036                 } else if (p->x[0] == '!' && p->x[1] == 0) {
1037                         /* how many chars will the . match against? */
1038                         int i = 0;
1039                         const char *str2 = str;
1040                         while (*str2++) {
1041                                 i++;
1042                         }
1043                         if (p->exten && !(*(str+1)))
1044                                 update_scoreboard(score, length+1, spec+(p->specificity*i), p->exten, '!', callerid, p->deleted, p);
1045                         if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1046                                 new_find_extension("/", score, p->next_char, length+i, spec+(p->specificity*i), callerid);
1047                         }
1048                         return;
1049                 } else if (p->x[0] == '/' && p->x[1] == 0) {
1050                         /* the pattern in the tree includes the cid match! */
1051                         if (p->next_char && callerid && *callerid) {
1052                                 new_find_extension(callerid, score, p->next_char, length+1, spec, callerid);
1053                         }
1054                 } else if (index(p->x, *str)) {
1055                         if (p->exten && !(*(str+1))) /* if a shorter pattern matches along the way, might as well report it */
1056                                 update_scoreboard(score, length+1, spec+p->specificity, p->exten,0,callerid, p->deleted, p);
1057
1058
1059                         if (p->next_char && ( *(str+1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0))) {
1060                                 if (*(str+1)) {
1061                                         new_find_extension(str+1, score, p->next_char, length+1, spec+p->specificity, callerid);
1062                                 } else {
1063                                         new_find_extension("/", score, p->next_char, length+1, spec+p->specificity, callerid);
1064                                 }
1065                         } else if (p->next_char && !*(str+1)) {
1066                                 score->canmatch = 1;
1067                                 score->canmatch_exten = get_canmatch_exten(p);
1068                         } else {
1069                                 return;
1070                         }
1071                 }
1072         }
1073 }
1074
1075 /* the algorithm for forming the extension pattern tree is also a bit simple; you 
1076  * traverse all the extensions in a context, and for each char of the extension,
1077  * you see if it exists in the tree; if it doesn't, you add it at the appropriate
1078  * spot. What more can I say? At the end of the list, you cap it off by adding the
1079  * address of the extension involved. Duplicate patterns will be complained about.
1080  *
1081  * Ideally, this would be done for each context after it is created and fully 
1082  * filled. It could be done as a finishing step after extensions.conf or .ael is
1083  * loaded, or it could be done when the first search is encountered. It should only
1084  * have to be done once, until the next unload or reload.
1085  *
1086  * I guess forming this pattern tree would be analogous to compiling a regex.
1087  */
1088
1089 static struct match_char *already_in_tree(struct match_char *current, char *pat)
1090 {
1091         struct match_char *t;
1092         if (!current)
1093                 return 0;
1094         for (t=current; t; t=t->alt_char) {
1095                 if (strcmp(pat,t->x) == 0) /* uh, we may want to sort exploded [] contents to make matching easy */
1096                         return t;
1097         }
1098         return 0;
1099 }
1100
1101 static struct match_char *add_pattern_node(struct ast_context *con, struct match_char *current, char *pattern, int is_pattern, int already, int specificity)
1102 {
1103         struct match_char *m = ast_calloc(1,sizeof(struct match_char));
1104         m->x = ast_strdup(pattern);
1105         m->is_pattern = is_pattern;
1106         if (specificity == 1 && is_pattern && pattern[0] == 'N')
1107                 m->specificity = 98;
1108         else if (specificity == 1 && is_pattern && pattern[0] == 'Z')
1109                 m->specificity = 99;
1110         else if (specificity == 1 && is_pattern && pattern[0] == 'X')
1111                 m->specificity = 100;
1112         else if (specificity == 1 && is_pattern && pattern[0] == '.')
1113                 m->specificity = 200;
1114         else if (specificity == 1 && is_pattern && pattern[0] == '!')
1115                 m->specificity = 200;
1116         else
1117                 m->specificity = specificity;
1118         
1119         if (!con->pattern_tree) {
1120                 con->pattern_tree = m;
1121         } else {
1122                 if (already) { /* switch to the new regime (traversing vs appending)*/
1123                         m->alt_char = current->alt_char;
1124                         current->alt_char = m;
1125                 } else {
1126                         if (current->next_char) {
1127                                 m->alt_char = current->next_char->alt_char;
1128                                 current->next_char = m;
1129                         } else {
1130                                 current->next_char = m;
1131                         }
1132                 }
1133         }
1134         return m;
1135 }
1136
1137 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
1138 {
1139         struct match_char *m1 = NULL, *m2 = NULL;
1140         int specif;
1141         int already;
1142         int pattern = 0;
1143         char buf[256];
1144         char extenbuf[512];
1145         char *s1 = extenbuf;
1146         int l1 = strlen(e1->exten) + strlen(e1->cidmatch) + 2;
1147         
1148
1149         strncpy(extenbuf,e1->exten,sizeof(extenbuf));
1150         if (e1->matchcid &&  l1 <= sizeof(extenbuf)) {
1151                 strcat(extenbuf,"/");
1152                 strcat(extenbuf,e1->cidmatch);
1153         } else if (l1 > sizeof(extenbuf)) {
1154                 ast_log(LOG_ERROR,"The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n", e1->exten, e1->cidmatch);
1155                 return 0;
1156         }
1157 #ifdef NEED_DEBUG
1158         ast_log(LOG_DEBUG,"Adding exten %s%c%s to tree\n", s1, e1->matchcid? '/':' ', e1->matchcid? e1->cidmatch : "");
1159 #endif
1160         m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
1161         already = 1;
1162
1163         if ( *s1 == '_') {
1164                 pattern = 1;
1165                 s1++;
1166         }
1167         while( *s1 ) {
1168                 if (pattern && *s1 == '[' && *(s1-1) != '\\') {
1169                         char *s2 = buf;
1170                         buf[0] = 0;
1171                         s1++; /* get past the '[' */
1172                         while (*s1 != ']' && *(s1-1) != '\\' ) {
1173                                 if (*s1 == '\\') {
1174                                         if (*(s1+1) == ']') {
1175                                                 *s2++ = ']';
1176                                                 s1++;s1++;
1177                                         } else if (*(s1+1) == '\\') {
1178                                                 *s2++ = '\\';
1179                                                 s1++;s1++;
1180                                         } else if (*(s1+1) == '-') {
1181                                                 *s2++ = '-';
1182                                                 s1++; s1++;
1183                                         } else if (*(s1+1) == '[') {
1184                                                 *s2++ = '[';
1185                                                 s1++; s1++;
1186                                         }
1187                                 } else if (*s1 == '-') { /* remember to add some error checking to all this! */
1188                                         char s3 = *(s1-1);
1189                                         char s4 = *(s1+1);
1190                                         for (s3++; s3 <= s4; s3++) {
1191                                                 *s2++ = s3;
1192                                         }
1193                                         s1++; s1++;
1194                                 } else {
1195                                         *s2++ = *s1++;
1196                                 }
1197                         }
1198                         *s2 = 0; /* null terminate the exploded range */
1199                         specif = strlen(buf);
1200                 } else {
1201                         
1202                         if (*s1 == '\\') {
1203                                 s1++;
1204                                 buf[0] = *s1;
1205                         } else {
1206                                 if (pattern) {
1207                                         if (*s1 == 'n') /* make sure n,x,z patterns are canonicalized to N,X,Z */
1208                                                 *s1 = 'N';
1209                                         else if (*s1 == 'x')
1210                                                 *s1 = 'X';
1211                                         else if (*s1 == 'z')
1212                                                 *s1 = 'Z';
1213                                 }
1214                                 buf[0] = *s1;
1215                         }
1216                         buf[1] = 0;
1217                         specif = 1;
1218                 }
1219                 m2 = 0;
1220                 if (already && (m2=already_in_tree(m1,buf)) && m2->next_char) {
1221                         if (!(*(s1+1))) {  /* if this is the end of the pattern, but not the end of the tree, then mark this node with the exten...
1222                                                                 a shorter pattern might win if the longer one doesn't match */
1223                                 m2->exten = e1;
1224                                 m2->deleted = 0;
1225                         }
1226                         m1 = m2->next_char; /* m1 points to the node to compare against */
1227                 } else {
1228                         if (m2) {
1229                                 if (findonly)
1230                                         return m2;
1231                                 m1 = m2;
1232                         } else {
1233                                 if (findonly)
1234                                         return m1;
1235                                 m1 = add_pattern_node(con, m1, buf, pattern, already,specif); /* m1 is the node just added */
1236                         }
1237                         
1238                         if (!(*(s1+1))) {
1239                                 m1->deleted = 0;
1240                                 m1->exten = e1;
1241                         }
1242                         
1243                         already = 0;
1244                 }
1245                 s1++; /* advance to next char */
1246         }
1247         return m1;
1248 }
1249
1250 static void create_match_char_tree(struct ast_context *con)
1251 {
1252         struct ast_hashtab_iter *t1;
1253         struct ast_exten *e1;
1254 #ifdef NEED_DEBUG
1255         int biggest_bucket, resizes, numobjs, numbucks;
1256         
1257         ast_log(LOG_DEBUG,"Creating Extension Trie for context %s\n", con->name);
1258         ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
1259         ast_log(LOG_DEBUG,"This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
1260                         numobjs, numbucks, biggest_bucket, resizes);
1261 #endif
1262         t1 = ast_hashtab_start_traversal(con->root_table);
1263         while( (e1 = ast_hashtab_next(t1)) ) {
1264                 if (e1->exten)
1265                         add_exten_to_pattern_tree(con, e1, 0);
1266                 else
1267                         ast_log(LOG_ERROR,"Attempt to create extension with no extension name.\n");
1268         }
1269         ast_hashtab_end_traversal(t1);
1270 }
1271
1272 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! */
1273 {
1274         /* destroy all the alternates */
1275         if (pattern_tree->alt_char) {
1276                 destroy_pattern_tree(pattern_tree->alt_char);
1277                 pattern_tree->alt_char = 0;
1278         }
1279         /* destroy all the nexts */
1280         if (pattern_tree->next_char) {
1281                 destroy_pattern_tree(pattern_tree->next_char);
1282                 pattern_tree->next_char = 0;
1283         }
1284         pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
1285         if (pattern_tree->x)
1286                 free(pattern_tree->x);
1287         free(pattern_tree);
1288 }
1289
1290 /*
1291  * Special characters used in patterns:
1292  *      '_'     underscore is the leading character of a pattern.
1293  *              In other position it is treated as a regular char.
1294  *      ' ' '-' space and '-' are separator and ignored.
1295  *      .       one or more of any character. Only allowed at the end of
1296  *              a pattern.
1297  *      !       zero or more of anything. Also impacts the result of CANMATCH
1298  *              and MATCHMORE. Only allowed at the end of a pattern.
1299  *              In the core routine, ! causes a match with a return code of 2.
1300  *              In turn, depending on the search mode: (XXX check if it is implemented)
1301  *              - E_MATCH retuns 1 (does match)
1302  *              - E_MATCHMORE returns 0 (no match)
1303  *              - E_CANMATCH returns 1 (does match)
1304  *
1305  *      /       should not appear as it is considered the separator of the CID info.
1306  *              XXX at the moment we may stop on this char.
1307  *
1308  *      X Z N   match ranges 0-9, 1-9, 2-9 respectively.
1309  *      [       denotes the start of a set of character. Everything inside
1310  *              is considered literally. We can have ranges a-d and individual
1311  *              characters. A '[' and '-' can be considered literally if they
1312  *              are just before ']'.
1313  *              XXX currently there is no way to specify ']' in a range, nor \ is
1314  *              considered specially.
1315  *
1316  * When we compare a pattern with a specific extension, all characters in the extension
1317  * itself are considered literally with the only exception of '-' which is considered
1318  * as a separator and thus ignored.
1319  * XXX do we want to consider space as a separator as well ?
1320  * XXX do we want to consider the separators in non-patterns as well ?
1321  */
1322
1323 /*!
1324  * \brief helper functions to sort extensions and patterns in the desired way,
1325  * so that more specific patterns appear first.
1326  *
1327  * ext_cmp1 compares individual characters (or sets of), returning
1328  * an int where bits 0-7 are the ASCII code of the first char in the set,
1329  * while bit 8-15 are the cardinality of the set minus 1.
1330  * This way more specific patterns (smaller cardinality) appear first.
1331  * Wildcards have a special value, so that we can directly compare them to
1332  * sets by subtracting the two values. In particular:
1333  *      0x000xx         one character, xx
1334  *      0x0yyxx         yy character set starting with xx
1335  *      0x10000         '.' (one or more of anything)
1336  *      0x20000         '!' (zero or more of anything)
1337  *      0x30000         NUL (end of string)
1338  *      0x40000         error in set.
1339  * The pointer to the string is advanced according to needs.
1340  * NOTES:
1341  *      1. the empty set is equivalent to NUL.
1342  *      2. given that a full set has always 0 as the first element,
1343  *         we could encode the special cases as 0xffXX where XX
1344  *         is 1, 2, 3, 4 as used above.
1345  */
1346 static int ext_cmp1(const char **p)
1347 {
1348         uint32_t chars[8];
1349         int c, cmin = 0xff, count = 0;
1350         const char *end;
1351
1352         /* load, sign extend and advance pointer until we find
1353          * a valid character.
1354          */
1355         while ( (c = *(*p)++) && (c == ' ' || c == '-') )
1356                 ;       /* ignore some characters */
1357
1358         /* always return unless we have a set of chars */
1359         switch (c) {
1360         default:        /* ordinary character */
1361                 return 0x0000 | (c & 0xff);
1362
1363         case 'N':       /* 2..9 */
1364                 return 0x0700 | '2' ;
1365
1366         case 'X':       /* 0..9 */
1367                 return 0x0900 | '0';
1368
1369         case 'Z':       /* 1..9 */
1370                 return 0x0800 | '1';
1371
1372         case '.':       /* wildcard */
1373                 return 0x10000;
1374
1375         case '!':       /* earlymatch */
1376                 return 0x20000; /* less specific than NULL */
1377
1378         case '\0':      /* empty string */
1379                 *p = NULL;
1380                 return 0x30000;
1381
1382         case '[':       /* pattern */
1383                 break;
1384         }
1385         /* locate end of set */
1386         end = strchr(*p, ']');  
1387
1388         if (end == NULL) {
1389                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
1390                 return 0x40000; /* XXX make this entry go last... */
1391         }
1392
1393         bzero(chars, sizeof(chars));    /* clear all chars in the set */
1394         for (; *p < end  ; (*p)++) {
1395                 unsigned char c1, c2;   /* first-last char in range */
1396                 c1 = (unsigned char)((*p)[0]);
1397                 if (*p + 2 < end && (*p)[1] == '-') { /* this is a range */
1398                         c2 = (unsigned char)((*p)[2]);
1399                         *p += 2;        /* skip a total of 3 chars */
1400                 } else                  /* individual character */
1401                         c2 = c1;
1402                 if (c1 < cmin)
1403                         cmin = c1;
1404                 for (; c1 <= c2; c1++) {
1405                         uint32_t mask = 1 << (c1 % 32);
1406                         if ( (chars[ c1 / 32 ] & mask) == 0)
1407                                 count += 0x100;
1408                         chars[ c1 / 32 ] |= mask;
1409                 }
1410         }
1411         (*p)++;
1412         return count == 0 ? 0x30000 : (count | cmin);
1413 }
1414
1415 /*!
1416  * \brief the full routine to compare extensions in rules.
1417  */
1418 static int ext_cmp(const char *a, const char *b)
1419 {
1420         /* make sure non-patterns come first.
1421          * If a is not a pattern, it either comes first or
1422          * we use strcmp to compare the strings.
1423          */
1424         int ret = 0;
1425
1426         if (a[0] != '_')
1427                 return (b[0] == '_') ? -1 : strcmp(a, b);
1428
1429         /* Now we know a is a pattern; if b is not, a comes first */
1430         if (b[0] != '_')
1431                 return 1;
1432 #if 0   /* old mode for ext matching */
1433         return strcmp(a, b);
1434 #endif
1435         /* ok we need full pattern sorting routine */
1436         while (!ret && a && b)
1437                 ret = ext_cmp1(&a) - ext_cmp1(&b);
1438         if (ret == 0)
1439                 return 0;
1440         else
1441                 return (ret > 0) ? 1 : -1;
1442 }
1443
1444 int ast_extension_cmp(const char *a, const char *b)
1445 {
1446         return ext_cmp(a, b);
1447 }
1448
1449 /*!
1450  * \internal
1451  * \brief used ast_extension_{match|close}
1452  * mode is as follows:
1453  *      E_MATCH         success only on exact match
1454  *      E_MATCHMORE     success only on partial match (i.e. leftover digits in pattern)
1455  *      E_CANMATCH      either of the above.
1456  * \retval 0 on no-match
1457  * \retval 1 on match
1458  * \retval 2 on early match.
1459  */
1460
1461 static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
1462 {
1463         mode &= E_MATCH_MASK;   /* only consider the relevant bits */
1464
1465         if ( (mode == E_MATCH) && (pattern[0] == '_') && (!strcasecmp(pattern,data)) ) /* note: if this test is left out, then _x. will not match _x. !!! */
1466                 return 1;
1467
1468         if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
1469                 int ld = strlen(data), lp = strlen(pattern);
1470
1471                 if (lp < ld)            /* pattern too short, cannot match */
1472                         return 0;
1473                 /* depending on the mode, accept full or partial match or both */
1474                 if (mode == E_MATCH)
1475                         return !strcmp(pattern, data); /* 1 on match, 0 on fail */
1476                 if (ld == 0 || !strncasecmp(pattern, data, ld)) /* partial or full match */
1477                         return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
1478                 else
1479                         return 0;
1480         }
1481         pattern++; /* skip leading _ */
1482         /*
1483          * XXX below we stop at '/' which is a separator for the CID info. However we should
1484          * not store '/' in the pattern at all. When we insure it, we can remove the checks.
1485          */
1486         while (*data && *pattern && *pattern != '/') {
1487                 const char *end;
1488
1489                 if (*data == '-') { /* skip '-' in data (just a separator) */
1490                         data++;
1491                         continue;
1492                 }
1493                 switch (toupper(*pattern)) {
1494                 case '[':       /* a range */
1495                         end = strchr(pattern+1, ']'); /* XXX should deal with escapes ? */
1496                         if (end == NULL) {
1497                                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
1498                                 return 0;       /* unconditional failure */
1499                         }
1500                         for (pattern++; pattern != end; pattern++) {
1501                                 if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
1502                                         if (*data >= pattern[0] && *data <= pattern[2])
1503                                                 break;  /* match found */
1504                                         else {
1505                                                 pattern += 2; /* skip a total of 3 chars */
1506                                                 continue;
1507                                         }
1508                                 } else if (*data == pattern[0])
1509                                         break;  /* match found */
1510                         }
1511                         if (pattern == end)
1512                                 return 0;
1513                         pattern = end;  /* skip and continue */
1514                         break;
1515                 case 'N':
1516                         if (*data < '2' || *data > '9')
1517                                 return 0;
1518                         break;
1519                 case 'X':
1520                         if (*data < '0' || *data > '9')
1521                                 return 0;
1522                         break;
1523                 case 'Z':
1524                         if (*data < '1' || *data > '9')
1525                                 return 0;
1526                         break;
1527                 case '.':       /* Must match, even with more digits */
1528                         return 1;
1529                 case '!':       /* Early match */
1530                         return 2;
1531                 case ' ':
1532                 case '-':       /* Ignore these in patterns */
1533                         data--; /* compensate the final data++ */
1534                         break;
1535                 default:
1536                         if (*data != *pattern)
1537                                 return 0;
1538                 }
1539                 data++;
1540                 pattern++;
1541         }
1542         if (*data)                      /* data longer than pattern, no match */
1543                 return 0;
1544         /*
1545          * match so far, but ran off the end of the data.
1546          * Depending on what is next, determine match or not.
1547          */
1548         if (*pattern == '\0' || *pattern == '/')        /* exact match */
1549                 return (mode == E_MATCHMORE) ? 0 : 1;   /* this is a failure for E_MATCHMORE */
1550         else if (*pattern == '!')                       /* early match */
1551                 return 2;
1552         else                                            /* partial match */
1553                 return (mode == E_MATCH) ? 0 : 1;       /* this is a failure for E_MATCH */
1554 }
1555
1556 /*
1557  * Wrapper around _extension_match_core() to do performance measurement
1558  * using the profiling code.
1559  */
1560 static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
1561 {
1562         int i;
1563         static int prof_id = -2;        /* marker for 'unallocated' id */
1564         if (prof_id == -2)
1565                 prof_id = ast_add_profile("ext_match", 0);
1566         ast_mark(prof_id, 1);
1567         i = _extension_match_core(pattern, data, mode);
1568         ast_mark(prof_id, 0);
1569         return i;
1570 }
1571
1572 int ast_extension_match(const char *pattern, const char *data)
1573 {
1574         return extension_match_core(pattern, data, E_MATCH);
1575 }
1576
1577 int ast_extension_close(const char *pattern, const char *data, int needmore)
1578 {
1579         if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
1580                 ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
1581         return extension_match_core(pattern, data, needmore);
1582 }
1583
1584 struct fake_context /* this struct is purely for matching in the hashtab */
1585 {
1586         ast_rwlock_t lock;                      
1587         struct ast_exten *root;         
1588         struct ast_hashtab *root_table;            
1589         struct match_char *pattern_tree;       
1590         struct ast_context *next;       
1591         struct ast_include *includes;           
1592         struct ast_ignorepat *ignorepats;       
1593         const char *registrar;
1594         int refcount;
1595         AST_LIST_HEAD_NOLOCK(, ast_sw) alts;    
1596         ast_mutex_t macrolock;          
1597         char name[256];         
1598 };
1599
1600 struct ast_context *ast_context_find(const char *name)
1601 {
1602         struct ast_context *tmp = NULL;
1603         struct fake_context item;
1604         strncpy(item.name,name,256);
1605         ast_rdlock_contexts();
1606         if( contexts_table ) {
1607                 tmp = ast_hashtab_lookup(contexts_table,&item);
1608         } else {
1609                 while ( (tmp = ast_walk_contexts(tmp)) ) {
1610                         if (!name || !strcasecmp(name, tmp->name))
1611                                 break;
1612                 }
1613         }
1614         ast_unlock_contexts();
1615         return tmp;
1616 }
1617
1618 #define STATUS_NO_CONTEXT       1
1619 #define STATUS_NO_EXTENSION     2
1620 #define STATUS_NO_PRIORITY      3
1621 #define STATUS_NO_LABEL         4
1622 #define STATUS_SUCCESS          5
1623
1624 static int matchcid(const char *cidpattern, const char *callerid)
1625 {
1626         /* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
1627            failing to get a number should count as a match, otherwise not */
1628
1629         if (ast_strlen_zero(callerid))
1630                 return ast_strlen_zero(cidpattern) ? 1 : 0;
1631
1632         return ast_extension_match(cidpattern, callerid);
1633 }
1634
1635 struct ast_exten *pbx_find_extension(struct ast_channel *chan,
1636         struct ast_context *bypass, struct pbx_find_info *q,
1637         const char *context, const char *exten, int priority,
1638         const char *label, const char *callerid, enum ext_match_t action)
1639 {
1640         int x, res;
1641         struct ast_context *tmp = NULL;
1642         struct ast_exten *e = NULL, *eroot = NULL;
1643         struct ast_include *i = NULL;
1644         struct ast_sw *sw = NULL;
1645         struct ast_exten pattern = {NULL, };
1646         struct scoreboard score = {0, };
1647
1648         pattern.label = label;
1649         pattern.priority = priority;
1650 #ifdef NEED_DEBUG
1651         ast_log(LOG_NOTICE,"Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int)action);
1652 #endif
1653         /* Initialize status if appropriate */
1654         if (q->stacklen == 0) {
1655                 q->status = STATUS_NO_CONTEXT;
1656                 q->swo = NULL;
1657                 q->data = NULL;
1658                 q->foundcontext = NULL;
1659         } else if (q->stacklen >= AST_PBX_MAX_STACK) {
1660                 ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
1661                 return NULL;
1662         }
1663
1664         /* Check first to see if we've already been checked */
1665         for (x = 0; x < q->stacklen; x++) {
1666                 if (!strcasecmp(q->incstack[x], context))
1667                         return NULL;
1668         }
1669
1670         if (bypass)     /* bypass means we only look there */
1671                 tmp = bypass;
1672         else {  /* look in contexts */
1673                 struct fake_context item;
1674                 strncpy(item.name,context,256);
1675                 tmp = ast_hashtab_lookup(contexts_table,&item);
1676 #ifdef NOTNOW
1677                 tmp = NULL;
1678                 while ((tmp = ast_walk_contexts(tmp)) ) {
1679                         if (!strcmp(tmp->name, context))
1680                                 break;
1681                 }
1682 #endif
1683                 if (!tmp)
1684                         return NULL;
1685                 
1686         }
1687
1688         if (q->status < STATUS_NO_EXTENSION)
1689                 q->status = STATUS_NO_EXTENSION;
1690         
1691         /* Do a search for matching extension */
1692
1693         eroot = NULL;
1694         score.total_specificity = 0;
1695         score.exten = 0;
1696         score.total_length = 0;
1697         if (!tmp->pattern_tree && tmp->root_table)
1698         {
1699                 create_match_char_tree(tmp);
1700 #ifdef NEED_DEBUG
1701                 ast_log(LOG_DEBUG,"Tree Created in context %s:\n", context);
1702                 log_match_char_tree(tmp->pattern_tree," ");
1703 #endif
1704         }
1705 #ifdef NEED_DEBUG
1706         ast_log(LOG_NOTICE,"The Trie we are searching in:\n");
1707         log_match_char_tree(tmp->pattern_tree, "::  ");
1708 #endif
1709
1710         if (extenpatternmatchnew) {
1711                 new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid);
1712                 eroot = score.exten;
1713                 
1714                 if (score.last_char == '!' && action == E_MATCHMORE) {
1715                         /* We match an extension ending in '!'.
1716                          * The decision in this case is final and is NULL (no match).
1717                          */
1718 #ifdef NEED_DEBUG
1719                         ast_log(LOG_NOTICE,"Returning MATCHMORE NULL with exclamation point.\n");
1720 #endif
1721                         return NULL;
1722                 }
1723                 
1724                 if (!eroot && (action == E_CANMATCH || action == E_MATCHMORE) && score.canmatch_exten) {
1725                         q->status = STATUS_SUCCESS;
1726 #ifdef NEED_DEBUG
1727                         ast_log(LOG_NOTICE,"Returning CANMATCH exten %s\n", score.canmatch_exten->exten);
1728 #endif
1729                         return score.canmatch_exten;
1730                 }
1731                 
1732                 if ((action == E_MATCHMORE || action == E_CANMATCH)  && eroot) {
1733                         if (score.node) {
1734                                 struct ast_exten *z = trie_find_next_match(score.node);
1735 #ifdef NEED_DEBUG
1736                                 if (z)
1737                                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten %s\n", z->exten);
1738                                 else
1739                                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten NULL\n");
1740 #endif
1741                                 return z;
1742                         }
1743 #ifdef NEED_DEBUG
1744                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE NULL (no next_match)\n");
1745 #endif
1746                         return NULL;  /* according to the code, complete matches are null matches in MATCHMORE mode */
1747                 }
1748                 
1749                 if (eroot) {
1750                         /* found entry, now look for the right priority */
1751                         if (q->status < STATUS_NO_PRIORITY)
1752                                 q->status = STATUS_NO_PRIORITY;
1753                         e = NULL;
1754                         if (action == E_FINDLABEL && label ) {
1755                                 if (q->status < STATUS_NO_LABEL)
1756                                         q->status = STATUS_NO_LABEL;
1757                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
1758                         } else {
1759                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
1760                         }
1761                         if (e) {        /* found a valid match */
1762                                 q->status = STATUS_SUCCESS;
1763                                 q->foundcontext = context;
1764 #ifdef NEED_DEBUG
1765                                 ast_log(LOG_NOTICE,"Returning complete match of exten %s\n", e->exten);
1766 #endif
1767                                 return e;
1768                         }
1769                 }
1770         } else {
1771                 
1772                 /* scan the list trying to match extension and CID */
1773                 eroot = NULL;
1774                 while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
1775                         int match = extension_match_core(eroot->exten, exten, action);
1776                         /* 0 on fail, 1 on match, 2 on earlymatch */
1777                         
1778                         if (!match || (eroot->matchcid && !matchcid(eroot->cidmatch, callerid)))
1779                                 continue;       /* keep trying */
1780                         if (match == 2 && action == E_MATCHMORE) {
1781                                 /* We match an extension ending in '!'.
1782                                  * The decision in this case is final and is NULL (no match).
1783                                  */
1784                                 return NULL;
1785                         }
1786                         /* found entry, now look for the right priority */
1787                         if (q->status < STATUS_NO_PRIORITY)
1788                                 q->status = STATUS_NO_PRIORITY;
1789                         e = NULL;
1790                         if (action == E_FINDLABEL && label ) {
1791                                 if (q->status < STATUS_NO_LABEL)
1792                                         q->status = STATUS_NO_LABEL;
1793                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
1794                         } else {
1795                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
1796                         }
1797 #ifdef NOTNOW
1798                         while ( (e = ast_walk_extension_priorities(eroot, e)) ) {
1799                                 /* Match label or priority */
1800                                 if (action == E_FINDLABEL) {
1801                                         if (q->status < STATUS_NO_LABEL)
1802                                                 q->status = STATUS_NO_LABEL;
1803                                         if (label && e->label && !strcmp(label, e->label))
1804                                                 break;  /* found it */
1805                                 } else if (e->priority == priority) {
1806                                         break;  /* found it */
1807                                 } /* else keep searching */
1808                         }
1809 #endif
1810                         if (e) {        /* found a valid match */
1811                                 q->status = STATUS_SUCCESS;
1812                                 q->foundcontext = context;
1813                                 return e;
1814                         }
1815                 }
1816         }
1817         
1818         
1819         /* Check alternative switches */
1820         AST_LIST_TRAVERSE(&tmp->alts, sw, list) {
1821                 struct ast_switch *asw = pbx_findswitch(sw->name);
1822                 ast_switch_f *aswf = NULL;
1823                 char *datap;
1824
1825                 if (!asw) {
1826                         ast_log(LOG_WARNING, "No such switch '%s'\n", sw->name);
1827                         continue;
1828                 }
1829                 /* Substitute variables now */
1830                 
1831                 if (sw->eval)
1832                         pbx_substitute_variables_helper(chan, sw->data, sw->tmpdata, SWITCH_DATA_LENGTH - 1);
1833
1834                 /* equivalent of extension_match_core() at the switch level */
1835                 if (action == E_CANMATCH)
1836                         aswf = asw->canmatch;
1837                 else if (action == E_MATCHMORE)
1838                         aswf = asw->matchmore;
1839                 else /* action == E_MATCH */
1840                         aswf = asw->exists;
1841                 datap = sw->eval ? sw->tmpdata : sw->data;
1842                 if (!aswf)
1843                         res = 0;
1844                 else {
1845                         if (chan)
1846                                 ast_autoservice_start(chan);
1847                         res = aswf(chan, context, exten, priority, callerid, datap);
1848                         if (chan)
1849                                 ast_autoservice_stop(chan);
1850                 }
1851                 if (res) {      /* Got a match */
1852                         q->swo = asw;
1853                         q->data = datap;
1854                         q->foundcontext = context;
1855                         /* XXX keep status = STATUS_NO_CONTEXT ? */
1856                         return NULL;
1857                 }
1858         }
1859         q->incstack[q->stacklen++] = tmp->name; /* Setup the stack */
1860         /* Now try any includes we have in this context */
1861         for (i = tmp->includes; i; i = i->next) {
1862                 if (include_valid(i)) {
1863                         if ((e = pbx_find_extension(chan, bypass, q, i->rname, exten, priority, label, callerid, action))) {
1864 #ifdef NEED_DEBUG
1865                                 ast_log(LOG_NOTICE,"Returning recursive match of %s\n", e->exten);
1866 #endif
1867                                 return e;
1868                         }
1869                         if (q->swo)
1870                                 return NULL;
1871                 }
1872         }
1873         return NULL;
1874 }
1875
1876 /*! 
1877  * \brief extract offset:length from variable name.
1878  * \return 1 if there is a offset:length part, which is
1879  * trimmed off (values go into variables)
1880  */
1881 static int parse_variable_name(char *var, int *offset, int *length, int *isfunc)
1882 {
1883         int parens = 0;
1884
1885         *offset = 0;
1886         *length = INT_MAX;
1887         *isfunc = 0;
1888         for (; *var; var++) {
1889                 if (*var == '(') {
1890                         (*isfunc)++;
1891                         parens++;
1892                 } else if (*var == ')') {
1893                         parens--;
1894                 } else if (*var == ':' && parens == 0) {
1895                         *var++ = '\0';
1896                         sscanf(var, "%d:%d", offset, length);
1897                         return 1; /* offset:length valid */
1898                 }
1899         }
1900         return 0;
1901 }
1902
1903 /*! 
1904  *\brief takes a substring. It is ok to call with value == workspace.
1905  * \param value
1906  * \param offset < 0 means start from the end of the string and set the beginning
1907  *   to be that many characters back.
1908  * \param length is the length of the substring, a value less than 0 means to leave
1909  * that many off the end.
1910  * \param workspace
1911  * \param workspace_len
1912  * Always return a copy in workspace.
1913  */
1914 static char *substring(const char *value, int offset, int length, char *workspace, size_t workspace_len)
1915 {
1916         char *ret = workspace;
1917         int lr; /* length of the input string after the copy */
1918
1919         ast_copy_string(workspace, value, workspace_len); /* always make a copy */
1920
1921         lr = strlen(ret); /* compute length after copy, so we never go out of the workspace */
1922
1923         /* Quick check if no need to do anything */
1924         if (offset == 0 && length >= lr)        /* take the whole string */
1925                 return ret;
1926
1927         if (offset < 0) {       /* translate negative offset into positive ones */
1928                 offset = lr + offset;
1929                 if (offset < 0) /* If the negative offset was greater than the length of the string, just start at the beginning */
1930                         offset = 0;
1931         }
1932
1933         /* too large offset result in empty string so we know what to return */
1934         if (offset >= lr)
1935                 return ret + lr;        /* the final '\0' */
1936
1937         ret += offset;          /* move to the start position */
1938         if (length >= 0 && length < lr - offset)        /* truncate if necessary */
1939                 ret[length] = '\0';
1940         else if (length < 0) {
1941                 if (lr > offset - length) /* After we remove from the front and from the rear, is there anything left? */
1942                         ret[lr + length - offset] = '\0';
1943                 else
1944                         ret[0] = '\0';
1945         }
1946
1947         return ret;
1948 }
1949
1950 /*! \brief  Support for Asterisk built-in variables in the dialplan
1951
1952 \note   See also
1953         - \ref AstVar   Channel variables
1954         - \ref AstCauses The HANGUPCAUSE variable
1955  */
1956 void pbx_retrieve_variable(struct ast_channel *c, const char *var, char **ret, char *workspace, int workspacelen, struct varshead *headp)
1957 {
1958         const char not_found = '\0';
1959         char *tmpvar;
1960         const char *s;  /* the result */
1961         int offset, length;
1962         int i, need_substring;
1963         struct varshead *places[2] = { headp, &globals };       /* list of places where we may look */
1964
1965         if (c) {
1966                 ast_channel_lock(c);
1967                 places[0] = &c->varshead;
1968         }
1969         /*
1970          * Make a copy of var because parse_variable_name() modifies the string.
1971          * Then if called directly, we might need to run substring() on the result;
1972          * remember this for later in 'need_substring', 'offset' and 'length'
1973          */
1974         tmpvar = ast_strdupa(var);      /* parse_variable_name modifies the string */
1975         need_substring = parse_variable_name(tmpvar, &offset, &length, &i /* ignored */);
1976
1977         /*
1978          * Look first into predefined variables, then into variable lists.
1979          * Variable 's' points to the result, according to the following rules:
1980          * s == &not_found (set at the beginning) means that we did not find a
1981          *      matching variable and need to look into more places.
1982          * If s != &not_found, s is a valid result string as follows:
1983          * s = NULL if the variable does not have a value;
1984          *      you typically do this when looking for an unset predefined variable.
1985          * s = workspace if the result has been assembled there;
1986          *      typically done when the result is built e.g. with an snprintf(),
1987          *      so we don't need to do an additional copy.
1988          * s != workspace in case we have a string, that needs to be copied
1989          *      (the ast_copy_string is done once for all at the end).
1990          *      Typically done when the result is already available in some string.
1991          */
1992         s = &not_found; /* default value */
1993         if (c) {        /* This group requires a valid channel */
1994                 /* Names with common parts are looked up a piece at a time using strncmp. */
1995                 if (!strncmp(var, "CALL", 4)) {
1996                         if (!strncmp(var + 4, "ING", 3)) {
1997                                 if (!strcmp(var + 7, "PRES")) {                 /* CALLINGPRES */
1998                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_pres);
1999                                         s = workspace;
2000                                 } else if (!strcmp(var + 7, "ANI2")) {          /* CALLINGANI2 */
2001                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_ani2);
2002                                         s = workspace;
2003                                 } else if (!strcmp(var + 7, "TON")) {           /* CALLINGTON */
2004                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_ton);
2005                                         s = workspace;
2006                                 } else if (!strcmp(var + 7, "TNS")) {           /* CALLINGTNS */
2007                                         snprintf(workspace, workspacelen, "%d", c->cid.cid_tns);
2008                                         s = workspace;
2009                                 }
2010                         }
2011                 } else if (!strcmp(var, "HINT")) {
2012                         s = ast_get_hint(workspace, workspacelen, NULL, 0, c, c->context, c->exten) ? workspace : NULL;
2013                 } else if (!strcmp(var, "HINTNAME")) {
2014                         s = ast_get_hint(NULL, 0, workspace, workspacelen, c, c->context, c->exten) ? workspace : NULL;
2015                 } else if (!strcmp(var, "EXTEN")) {
2016                         s = c->exten;
2017                 } else if (!strcmp(var, "CONTEXT")) {
2018                         s = c->context;
2019                 } else if (!strcmp(var, "PRIORITY")) {
2020                         snprintf(workspace, workspacelen, "%d", c->priority);
2021                         s = workspace;
2022                 } else if (!strcmp(var, "CHANNEL")) {
2023                         s = c->name;
2024                 } else if (!strcmp(var, "UNIQUEID")) {
2025                         s = c->uniqueid;
2026                 } else if (!strcmp(var, "HANGUPCAUSE")) {
2027                         snprintf(workspace, workspacelen, "%d", c->hangupcause);
2028                         s = workspace;
2029                 }
2030         }
2031         if (s == &not_found) { /* look for more */
2032                 if (!strcmp(var, "EPOCH")) {
2033                         snprintf(workspace, workspacelen, "%u",(int)time(NULL));
2034                         s = workspace;
2035                 } else if (!strcmp(var, "SYSTEMNAME")) {
2036                         s = ast_config_AST_SYSTEM_NAME;
2037                 }
2038         }
2039         /* if not found, look into chanvars or global vars */
2040         for (i = 0; s == &not_found && i < (sizeof(places) / sizeof(places[0])); i++) {
2041                 struct ast_var_t *variables;
2042                 if (!places[i])
2043                         continue;
2044                 if (places[i] == &globals)
2045                         ast_rwlock_rdlock(&globalslock);
2046                 AST_LIST_TRAVERSE(places[i], variables, entries) {
2047                         if (!strcasecmp(ast_var_name(variables), var)) {
2048                                 s = ast_var_value(variables);
2049                                 break;
2050                         }
2051                 }
2052                 if (places[i] == &globals)
2053                         ast_rwlock_unlock(&globalslock);
2054         }
2055         if (s == &not_found || s == NULL)
2056                 *ret = NULL;
2057         else {
2058                 if (s != workspace)
2059                         ast_copy_string(workspace, s, workspacelen);
2060                 *ret = workspace;
2061                 if (need_substring)
2062                         *ret = substring(*ret, offset, length, workspace, workspacelen);
2063         }
2064
2065         if (c)
2066                 ast_channel_unlock(c);
2067 }
2068
2069 static void exception_store_free(void *data)
2070 {
2071         struct pbx_exception *exception = data;
2072         ast_string_field_free_memory(exception);
2073         ast_free(exception);
2074 }
2075
2076 static struct ast_datastore_info exception_store_info = {
2077         .type = "EXCEPTION",
2078         .destroy = exception_store_free,
2079 };
2080
2081 int pbx_builtin_raise_exception(struct ast_channel *chan, void *vreason)
2082 {
2083         const char *reason = vreason;
2084         struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
2085         struct pbx_exception *exception = NULL;
2086
2087         if (!ds) {
2088                 ds = ast_channel_datastore_alloc(&exception_store_info, NULL);
2089                 if (!ds)
2090                         return -1;
2091                 exception = ast_calloc(1, sizeof(struct pbx_exception));
2092                 if (!exception) {
2093                         ast_channel_datastore_free(ds);
2094                         return -1;
2095                 }
2096                 if (ast_string_field_init(exception, 128)) {
2097                         ast_free(exception);
2098                         ast_channel_datastore_free(ds);
2099                         return -1;
2100                 }
2101                 ds->data = exception;
2102                 ast_channel_datastore_add(chan, ds);
2103         } else
2104                 exception = ds->data;
2105
2106         ast_string_field_set(exception, reason, reason);
2107         ast_string_field_set(exception, context, chan->context);
2108         ast_string_field_set(exception, exten, chan->exten);
2109         exception->priority = chan->priority;
2110         set_ext_pri(chan, "e", 0);
2111         return 0;
2112 }
2113
2114 static int acf_exception_read(struct ast_channel *chan, const char *name, char *data, char *buf, size_t buflen)
2115 {
2116         struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
2117         struct pbx_exception *exception = NULL;
2118         if (!ds || !ds->data)
2119                 return -1;
2120         exception = ds->data;
2121         if (!strcasecmp(data, "REASON"))
2122                 ast_copy_string(buf, exception->reason, buflen);
2123         else if (!strcasecmp(data, "CONTEXT"))
2124                 ast_copy_string(buf, exception->context, buflen);
2125         else if (!strncasecmp(data, "EXTEN", 5))
2126                 ast_copy_string(buf, exception->exten, buflen);
2127         else if (!strcasecmp(data, "PRIORITY"))
2128                 snprintf(buf, buflen, "%d", exception->priority);
2129         else
2130                 return -1;
2131         return 0;
2132 }
2133
2134 static struct ast_custom_function exception_function = {
2135         .name = "EXCEPTION",
2136         .synopsis = "Retrieve the details of the current dialplan exception",
2137         .desc =
2138 "The following fields are available for retrieval:\n"
2139 "  reason    INVALID, ERROR, RESPONSETIMEOUT, ABSOLUTETIMEOUT, or custom\n"
2140 "               value set by the RaiseException() application\n"
2141 "  context   The context executing when the exception occurred\n"
2142 "  exten     The extension executing when the exception occurred\n"
2143 "  priority  The numeric priority executing when the exception occurred\n",
2144         .syntax = "EXCEPTION(<field>)",
2145         .read = acf_exception_read,
2146 };
2147
2148 static char *handle_show_functions(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
2149 {
2150         struct ast_custom_function *acf;
2151         int count_acf = 0;
2152         int like = 0;
2153
2154         switch (cmd) {
2155         case CLI_INIT:
2156                 e->command = "core show functions [like]";
2157                 e->usage = 
2158                         "Usage: core show functions [like <text>]\n"
2159                         "       List builtin functions, optionally only those matching a given string\n";
2160                 return NULL;
2161         case CLI_GENERATE:
2162                 return NULL;
2163         }
2164
2165         if (a->argc == 5 && (!strcmp(a->argv[3], "like")) ) {
2166                 like = 1;
2167         } else if (a->argc != 3) {
2168                 return CLI_SHOWUSAGE;
2169         }
2170
2171         ast_cli(a->fd, "%s Custom Functions:\n--------------------------------------------------------------------------------\n", like ? "Matching" : "Installed");
2172
2173         AST_RWLIST_RDLOCK(&acf_root);
2174         AST_RWLIST_TRAVERSE(&acf_root, acf, acflist) {
2175                 if (!like || strstr(acf->name, a->argv[4])) {
2176                         count_acf++;
2177                         ast_cli(a->fd, "%-20.20s  %-35.35s  %s\n", acf->name, acf->syntax, acf->synopsis);
2178                 }
2179         }
2180         AST_RWLIST_UNLOCK(&acf_root);
2181
2182         ast_cli(a->fd, "%d %scustom functions installed.\n", count_acf, like ? "matching " : "");
2183
2184         return CLI_SUCCESS;
2185 }
2186
2187 static char *handle_show_function(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
2188 {
2189         struct ast_custom_function *acf;
2190         /* Maximum number of characters added by terminal coloring is 22 */
2191         char infotitle[64 + AST_MAX_APP + 22], syntitle[40], destitle[40];
2192         char info[64 + AST_MAX_APP], *synopsis = NULL, *description = NULL;
2193         char stxtitle[40], *syntax = NULL;
2194         int synopsis_size, description_size, syntax_size;
2195         char *ret = NULL;
2196         int which = 0;
2197         int wordlen;
2198
2199         switch (cmd) {
2200         case CLI_INIT:
2201                 e->command = "core show function";
2202                 e->usage = 
2203                         "Usage: core show function <function>\n"
2204                         "       Describe a particular dialplan function.\n";
2205                 return NULL;
2206         case CLI_GENERATE:      
2207                 wordlen = strlen(a->word);
2208                 /* case-insensitive for convenience in this 'complete' function */
2209                 AST_RWLIST_RDLOCK(&acf_root);
2210                 AST_RWLIST_TRAVERSE(&acf_root, acf, acflist) {
2211                         if (!strncasecmp(a->word, acf->name, wordlen) && ++which > a->n) {
2212                                 ret = ast_strdup(acf->name);
2213                                 break;
2214                         }
2215                 }
2216                 AST_RWLIST_UNLOCK(&acf_root);
2217
2218                 return ret;
2219         }
2220
2221         if (a->argc < 4)
2222                 return CLI_SHOWUSAGE;
2223
2224         if (!(acf = ast_custom_function_find(a->argv[3]))) {
2225                 ast_cli(a->fd, "No function by that name registered.\n");
2226                 return CLI_FAILURE;
2227
2228         }
2229
2230         if (acf->synopsis)
2231                 synopsis_size = strlen(acf->synopsis) + 23;
2232         else
2233                 synopsis_size = strlen("Not available") + 23;
2234         synopsis = alloca(synopsis_size);
2235
2236         if (acf->desc)
2237                 description_size = strlen(acf->desc) + 23;
2238         else
2239                 description_size = strlen("Not available") + 23;
2240         description = alloca(description_size);
2241
2242         if (acf->syntax)
2243                 syntax_size = strlen(acf->syntax) + 23;
2244         else
2245                 syntax_size = strlen("Not available") + 23;
2246         syntax = alloca(syntax_size);
2247
2248         snprintf(info, 64 + AST_MAX_APP, "\n  -= Info about function '%s' =- \n\n", acf->name);
2249         term_color(infotitle, info, COLOR_MAGENTA, 0, 64 + AST_MAX_APP + 22);
2250         term_color(stxtitle, "[Syntax]\n", COLOR_MAGENTA, 0, 40);
2251         term_color(syntitle, "[Synopsis]\n", COLOR_MAGENTA, 0, 40);
2252         term_color(destitle, "[Description]\n", COLOR_MAGENTA, 0, 40);
2253         term_color(syntax,
2254                    acf->syntax ? acf->syntax : "Not available",
2255                    COLOR_CYAN, 0, syntax_size);
2256         term_color(synopsis,
2257                    acf->synopsis ? acf->synopsis : "Not available",
2258                    COLOR_CYAN, 0, synopsis_size);
2259         term_color(description,
2260                    acf->desc ? acf->desc : "Not available",
2261                    COLOR_CYAN, 0, description_size);
2262
2263         ast_cli(a->fd,"%s%s%s\n\n%s%s\n\n%s%s\n", infotitle, stxtitle, syntax, syntitle, synopsis, destitle, description);
2264
2265         return CLI_SUCCESS;
2266 }
2267
2268 struct ast_custom_function *ast_custom_function_find(const char *name)
2269 {
2270         struct ast_custom_function *acf = NULL;
2271
2272         AST_RWLIST_RDLOCK(&acf_root);
2273         AST_RWLIST_TRAVERSE(&acf_root, acf, acflist) {
2274                 if (!strcmp(name, acf->name))
2275                         break;
2276         }
2277         AST_RWLIST_UNLOCK(&acf_root);
2278
2279         return acf;
2280 }
2281
2282 int ast_custom_function_unregister(struct ast_custom_function *acf)
2283 {
2284         struct ast_custom_function *cur;
2285
2286         if (!acf)
2287                 return -1;
2288
2289         AST_RWLIST_WRLOCK(&acf_root);
2290         if ((cur = AST_RWLIST_REMOVE(&acf_root, acf, acflist)))
2291                 ast_verb(2, "Unregistered custom function %s\n", cur->name);
2292         AST_RWLIST_UNLOCK(&acf_root);
2293
2294         return cur ? 0 : -1;
2295 }
2296
2297 int __ast_custom_function_register(struct ast_custom_function *acf, struct ast_module *mod)
2298 {
2299         struct ast_custom_function *cur;
2300         char tmps[80];
2301
2302         if (!acf)
2303                 return -1;
2304
2305         acf->mod = mod;
2306
2307         AST_RWLIST_WRLOCK(&acf_root);
2308
2309         AST_RWLIST_TRAVERSE(&acf_root, cur, acflist) {
2310                 if (!strcmp(acf->name, cur->name)) {
2311                         ast_log(LOG_ERROR, "Function %s already registered.\n", acf->name);
2312                         AST_RWLIST_UNLOCK(&acf_root);
2313                         return -1;
2314                 }
2315         }
2316
2317         /* Store in alphabetical order */
2318         AST_RWLIST_TRAVERSE_SAFE_BEGIN(&acf_root, cur, acflist) {
2319                 if (strcasecmp(acf->name, cur->name) < 0) {
2320                         AST_RWLIST_INSERT_BEFORE_CURRENT(acf, acflist);
2321                         break;
2322                 }
2323         }
2324         AST_RWLIST_TRAVERSE_SAFE_END;
2325         if (!cur)
2326                 AST_RWLIST_INSERT_TAIL(&acf_root, acf, acflist);
2327
2328         AST_RWLIST_UNLOCK(&acf_root);
2329
2330         ast_verb(2, "Registered custom function '%s'\n", term_color(tmps, acf->name, COLOR_BRCYAN, 0, sizeof(tmps)));
2331
2332         return 0;
2333 }
2334
2335 /*! \brief return a pointer to the arguments of the function,
2336  * and terminates the function name with '\\0'
2337  */
2338 static char *func_args(char *function)
2339 {
2340         char *args = strchr(function, '(');
2341
2342         if (!args)
2343                 ast_log(LOG_WARNING, "Function doesn't contain parentheses.  Assuming null argument.\n");
2344         else {
2345                 char *p;
2346                 *args++ = '\0';
2347                 if ((p = strrchr(args, ')')) )
2348                         *p = '\0';
2349                 else
2350                         ast_log(LOG_WARNING, "Can't find trailing parenthesis?\n");
2351         }
2352         return args;
2353 }
2354
2355 int ast_func_read(struct ast_channel *chan, const char *function, char *workspace, size_t len)
2356 {
2357         char *copy = ast_strdupa(function);
2358         char *args = func_args(copy);
2359         struct ast_custom_function *acfptr = ast_custom_function_find(copy);
2360
2361         if (acfptr == NULL)
2362                 ast_log(LOG_ERROR, "Function %s not registered\n", copy);
2363         else if (!acfptr->read)
2364                 ast_log(LOG_ERROR, "Function %s cannot be read\n", copy);
2365         else {
2366                 int res;
2367                 struct ast_module_user *u = NULL;
2368                 if (acfptr->mod)
2369                         u = __ast_module_user_add(acfptr->mod, chan);
2370                 res = acfptr->read(chan, copy, args, workspace, len);
2371                 if (acfptr->mod && u)
2372                         __ast_module_user_remove(acfptr->mod, u);
2373                 return res;
2374         }
2375         return -1;
2376 }
2377
2378 int ast_func_write(struct ast_channel *chan, const char *function, const char *value)
2379 {
2380         char *copy = ast_strdupa(function);
2381         char *args = func_args(copy);
2382         struct ast_custom_function *acfptr = ast_custom_function_find(copy);
2383
2384         if (acfptr == NULL)
2385                 ast_log(LOG_ERROR, "Function %s not registered\n", copy);
2386         else if (!acfptr->write)
2387                 ast_log(LOG_ERROR, "Function %s cannot be written to\n", copy);
2388         else {
2389                 int res;
2390                 struct ast_module_user *u = NULL;
2391                 if (acfptr->mod)
2392                         u = __ast_module_user_add(acfptr->mod, chan);
2393                 res = acfptr->write(chan, copy, args, value);
2394                 if (acfptr->mod && u)
2395                         __ast_module_user_remove(acfptr->mod, u);
2396                 return res;
2397         }
2398
2399         return -1;
2400 }
2401
2402 static void pbx_substitute_variables_helper_full(struct ast_channel *c, struct varshead *headp, const char *cp1, char *cp2, int count)
2403 {
2404         /* Substitutes variables into cp2, based on string cp1, cp2 NO LONGER NEEDS TO BE ZEROED OUT!!!!  */
2405         char *cp4;
2406         const char *tmp, *whereweare;
2407         int length, offset, offset2, isfunction;
2408         char *workspace = NULL;
2409         char *ltmp = NULL, *var = NULL;
2410         char *nextvar, *nextexp, *nextthing;
2411         char *vars, *vare;
2412         int pos, brackets, needsub, len;
2413         
2414         *cp2 = 0; /* just in case nothing ends up there */
2415         whereweare=tmp=cp1;
2416         while (!ast_strlen_zero(whereweare) && count) {
2417                 /* Assume we're copying the whole remaining string */
2418                 pos = strlen(whereweare);
2419                 nextvar = NULL;
2420                 nextexp = NULL;
2421                 nextthing = strchr(whereweare, '$');
2422                 if (nextthing) {
2423                         switch (nextthing[1]) {
2424                         case '{':
2425                                 nextvar = nextthing;
2426                                 pos = nextvar - whereweare;
2427                                 break;
2428                         case '[':
2429                                 nextexp = nextthing;
2430                                 pos = nextexp - whereweare;
2431                                 break;
2432                         default:
2433                                 pos = 1;
2434                         }
2435                 }
2436
2437                 if (pos) {
2438                         /* Can't copy more than 'count' bytes */
2439                         if (pos > count)
2440                                 pos = count;
2441
2442                         /* Copy that many bytes */
2443                         memcpy(cp2, whereweare, pos);
2444
2445                         count -= pos;
2446                         cp2 += pos;
2447                         whereweare += pos;
2448                         *cp2 = 0;
2449                 }
2450
2451                 if (nextvar) {
2452                         /* We have a variable.  Find the start and end, and determine
2453                            if we are going to have to recursively call ourselves on the
2454                            contents */
2455                         vars = vare = nextvar + 2;
2456                         brackets = 1;
2457                         needsub = 0;
2458
2459                         /* Find the end of it */
2460                         while (brackets && *vare) {
2461                                 if ((vare[0] == '$') && (vare[1] == '{')) {
2462                                         needsub++;
2463                                 } else if (vare[0] == '{') {
2464                                         brackets++;
2465                                 } else if (vare[0] == '}') {
2466                                         brackets--;
2467                                 } else if ((vare[0] == '$') && (vare[1] == '['))
2468                                         needsub++;
2469                                 vare++;
2470                         }
2471                         if (brackets)
2472                                 ast_log(LOG_WARNING, "Error in extension logic (missing '}')\n");
2473                         len = vare - vars - 1;
2474
2475                         /* Skip totally over variable string */
2476                         whereweare += (len + 3);
2477
2478                         if (!var)
2479                                 var = alloca(VAR_BUF_SIZE);
2480
2481                         /* Store variable name (and truncate) */
2482                         ast_copy_string(var, vars, len + 1);
2483
2484                         /* Substitute if necessary */
2485                         if (needsub) {
2486                                 if (!ltmp)
2487                                         ltmp = alloca(VAR_BUF_SIZE);
2488
2489                                 pbx_substitute_variables_helper_full(c, headp, var, ltmp, VAR_BUF_SIZE - 1);
2490                                 vars = ltmp;
2491                         } else {
2492                                 vars = var;
2493                         }
2494
2495                         if (!workspace)
2496                                 workspace = alloca(VAR_BUF_SIZE);
2497
2498                         workspace[0] = '\0';
2499
2500                         parse_variable_name(vars, &offset, &offset2, &isfunction);
2501                         if (isfunction) {
2502                                 /* Evaluate function */
2503                                 if (c || !headp)
2504                                         cp4 = ast_func_read(c, vars, workspace, VAR_BUF_SIZE) ? NULL : workspace;
2505                                 else {
2506                                         struct varshead old;
2507                                         struct ast_channel *c = ast_channel_alloc(0, 0, "", "", "", "", "", 0, "Bogus/%p", vars);
2508                                         if (c) {
2509                                                 memcpy(&old, &c->varshead, sizeof(old));
2510                                                 memcpy(&c->varshead, headp, sizeof(c->varshead));
2511                                                 cp4 = ast_func_read(c, vars, workspace, VAR_BUF_SIZE) ? NULL : workspace;
2512                                                 /* Don't deallocate the varshead that was passed in */
2513                                                 memcpy(&c->varshead, &old, sizeof(c->varshead));
2514                                                 ast_channel_free(c);
2515                                         } else
2516                                                 ast_log(LOG_ERROR, "Unable to allocate bogus channel for variable substitution.  Function results may be blank.\n");
2517                                 }
2518                                 ast_debug(1, "Function result is '%s'\n", cp4 ? cp4 : "(null)");
2519                         } else {
2520                                 /* Retrieve variable value */
2521                                 pbx_retrieve_variable(c, vars, &cp4, workspace, VAR_BUF_SIZE, headp);
2522                         }
2523                         if (cp4) {
2524                                 cp4 = substring(cp4, offset, offset2, workspace, VAR_BUF_SIZE);
2525
2526                                 length = strlen(cp4);
2527                                 if (length > count)
2528                                         length = count;
2529                                 memcpy(cp2, cp4, length);
2530                                 count -= length;
2531                                 cp2 += length;
2532                                 *cp2 = 0;
2533                         }
2534                 } else if (nextexp) {
2535                         /* We have an expression.  Find the start and end, and determine
2536                            if we are going to have to recursively call ourselves on the
2537                            contents */
2538                         vars = vare = nextexp + 2;
2539                         brackets = 1;
2540                         needsub = 0;
2541
2542                         /* Find the end of it */
2543                         while (brackets && *vare) {
2544                                 if ((vare[0] == '$') && (vare[1] == '[')) {
2545                                         needsub++;
2546                                         brackets++;
2547                                         vare++;
2548                                 } else if (vare[0] == '[') {
2549                                         brackets++;
2550                                 } else if (vare[0] == ']') {
2551                                         brackets--;
2552                                 } else if ((vare[0] == '$') && (vare[1] == '{')) {
2553                                         needsub++;
2554                                         vare++;
2555                                 }
2556                                 vare++;
2557                         }
2558                         if (brackets)
2559                                 ast_log(LOG_WARNING, "Error in extension logic (missing ']')\n");
2560                         len = vare - vars - 1;
2561
2562                         /* Skip totally over expression */
2563                         whereweare += (len + 3);
2564
2565                         if (!var)
2566                                 var = alloca(VAR_BUF_SIZE);
2567
2568                         /* Store variable name (and truncate) */
2569                         ast_copy_string(var, vars, len + 1);
2570
2571                         /* Substitute if necessary */
2572                         if (needsub) {
2573                                 if (!ltmp)
2574                                         ltmp = alloca(VAR_BUF_SIZE);
2575
2576                                 pbx_substitute_variables_helper_full(c, headp, var, ltmp, VAR_BUF_SIZE - 1);
2577                                 vars = ltmp;
2578                         } else {
2579                                 vars = var;
2580                         }
2581
2582                         length = ast_expr(vars, cp2, count, c);
2583
2584                         if (length) {
2585                                 ast_debug(1, "Expression result is '%s'\n", cp2);
2586                                 count -= length;
2587                                 cp2 += length;
2588                                 *cp2 = 0;
2589                         }
2590                 }
2591         }
2592 }
2593
2594 void pbx_substitute_variables_helper(struct ast_channel *c, const char *cp1, char *cp2, int count)
2595 {
2596         pbx_substitute_variables_helper_full(c, (c) ? &c->varshead : NULL, cp1, cp2, count);
2597 }
2598
2599 void pbx_substitute_variables_varshead(struct varshead *headp, const char *cp1, char *cp2, int count)
2600 {
2601         pbx_substitute_variables_helper_full(NULL, headp, cp1, cp2, count);
2602 }
2603
2604 static void pbx_substitute_variables(char *passdata, int datalen, struct ast_channel *c, struct ast_exten *e)
2605 {
2606         const char *tmp;
2607
2608         /* Nothing more to do */
2609         if (!e->data)
2610                 return;
2611
2612         /* No variables or expressions in e->data, so why scan it? */
2613         if ((!(tmp = strchr(e->data, '$'))) || (!strstr(tmp, "${") && !strstr(tmp, "$["))) {
2614                 ast_copy_string(passdata, e->data, datalen);
2615                 return;
2616         }
2617
2618         pbx_substitute_variables_helper(c, e->data, passdata, datalen - 1);
2619 }
2620
2621 /*! 
2622  * \brief The return value depends on the action:
2623  *
2624  * E_MATCH, E_CANMATCH, E_MATCHMORE require a real match,
2625  *      and return 0 on failure, -1 on match;
2626  * E_FINDLABEL maps the label to a priority, and returns
2627  *      the priority on success, ... XXX
2628  * E_SPAWN, spawn an application,
2629  *      
2630  * \retval 0 on success.
2631  * \retval  -1 on failure.
2632  *
2633  * \note The channel is auto-serviced in this function, because doing an extension
2634  * match may block for a long time.  For example, if the lookup has to use a network
2635  * dialplan switch, such as DUNDi or IAX2, it may take a while.  However, the channel
2636  * auto-service code will queue up any important signalling frames to be processed
2637  * after this is done.
2638  */
2639 static int pbx_extension_helper(struct ast_channel *c, struct ast_context *con,
2640   const char *context, const char *exten, int priority,
2641   const char *label, const char *callerid, enum ext_match_t action, int *found, int combined_find_spawn)
2642 {
2643         struct ast_exten *e;
2644         struct ast_app *app;
2645         int res;
2646         struct pbx_find_info q = { .stacklen = 0 }; /* the rest is reset in pbx_find_extension */
2647         char passdata[EXT_DATA_SIZE];
2648
2649         int matching_action = (action == E_MATCH || action == E_CANMATCH || action == E_MATCHMORE);
2650
2651         ast_rdlock_contexts();
2652         if (found)
2653                 *found = 0;
2654
2655         e = pbx_find_extension(c, con, &q, context, exten, priority, label, callerid, action);
2656         if (e) {
2657                 if (found)
2658                         *found = 1;
2659                 if (matching_action) {
2660                         ast_unlock_contexts();
2661                         return -1;      /* success, we found it */
2662                 } else if (action == E_FINDLABEL) { /* map the label to a priority */
2663                         res = e->priority;
2664                         ast_unlock_contexts();
2665                         return res;     /* the priority we were looking for */
2666                 } else {        /* spawn */
2667                         if (!e->cached_app)
2668                                 e->cached_app = pbx_findapp(e->app);
2669                         app = e->cached_app;
2670                         ast_unlock_contexts();
2671                         if (!app) {
2672                                 ast_log(LOG_WARNING, "No application '%s' for extension (%s, %s, %d)\n", e->app, context, exten, priority);
2673                                 return -1;
2674                         }
2675                         if (c->context != context)
2676                                 ast_copy_string(c->context, context, sizeof(c->context));
2677                         if (c->exten != exten)
2678                                 ast_copy_string(c->exten, exten, sizeof(c->exten));
2679                         c->priority = priority;
2680                         pbx_substitute_variables(passdata, sizeof(passdata), c, e);
2681 #ifdef CHANNEL_TRACE
2682                         ast_channel_trace_update(c);
2683 #endif
2684                         ast_debug(1, "Launching '%s'\n", app->name);
2685                         if (VERBOSITY_ATLEAST(3)) {
2686                                 char tmp[80], tmp2[80], tmp3[EXT_DATA_SIZE];
2687                                 ast_verb(3, "Executing [%s@%s:%d] %s(\"%s\", \"%s\") %s\n",
2688                                         exten, context, priority,
2689                                         term_color(tmp, app->name, COLOR_BRCYAN, 0, sizeof(tmp)),
2690                                         term_color(tmp2, c->name, COLOR_BRMAGENTA, 0, sizeof(tmp2)),
2691                                         term_color(tmp3, passdata, COLOR_BRMAGENTA, 0, sizeof(tmp3)),
2692                                         "in new stack");
2693                         }
2694                         manager_event(EVENT_FLAG_DIALPLAN, "Newexten",
2695                                         "Channel: %s\r\n"
2696                                         "Context: %s\r\n"
2697                                         "Extension: %s\r\n"
2698                                         "Priority: %d\r\n"
2699                                         "Application: %s\r\n"
2700                                         "AppData: %s\r\n"
2701                                         "Uniqueid: %s\r\n",
2702                                         c->name, c->context, c->exten, c->priority, app->name, passdata, c->uniqueid);
2703                         return pbx_exec(c, app, passdata);      /* 0 on success, -1 on failure */
2704                 }
2705         } else if (q.swo) {     /* not found here, but in another switch */
2706                 ast_unlock_contexts();
2707                 if (matching_action) {
2708                         return -1;
2709                 } else {
2710                         if (!q.swo->exec) {
2711                                 ast_log(LOG_WARNING, "No execution engine for switch %s\n", q.swo->name);
2712                                 res = -1;
2713                         }
2714                         return q.swo->exec(c, q.foundcontext ? q.foundcontext : context, exten, priority, callerid, q.data);
2715                 }
2716         } else {        /* not found anywhere, see what happened */
2717                 ast_unlock_contexts();
2718                 switch (q.status) {
2719                 case STATUS_NO_CONTEXT:
2720                         if (!matching_action && !combined_find_spawn)
2721                                 ast_log(LOG_NOTICE, "Cannot find extension context '%s'\n", context);
2722                         break;
2723                 case STATUS_NO_EXTENSION:
2724                         if (!matching_action && !combined_find_spawn)
2725                                 ast_log(LOG_NOTICE, "Cannot find extension '%s' in context '%s'\n", exten, context);
2726                         break;
2727                 case STATUS_NO_PRIORITY:
2728                         if (!matching_action && !combined_find_spawn)
2729                                 ast_log(LOG_NOTICE, "No such priority %d in extension '%s' in context '%s'\n", priority, exten, context);
2730                         break;
2731                 case STATUS_NO_LABEL:
2732                         if (context && !combined_find_spawn)
2733                                 ast_log(LOG_NOTICE, "No such label '%s' in extension '%s' in context '%s'\n", label, exten, context);
2734                         break;
2735                 default:
2736                         ast_debug(1, "Shouldn't happen!\n");
2737                 }
2738
2739                 return (matching_action) ? 0 : -1;
2740         }
2741 }
2742
2743 /*! \brief Find hint for given extension in context */
2744 static struct ast_exten *ast_hint_extension(struct ast_channel *c, const char *context, const char *exten)
2745 {
2746         struct ast_exten *e;
2747         struct pbx_find_info q = { .stacklen = 0 }; /* the rest is set in pbx_find_context */
2748
2749         ast_rdlock_contexts();
2750         e = pbx_find_extension(c, NULL, &q, context, exten, PRIORITY_HINT, NULL, "", E_MATCH);
2751         ast_unlock_contexts();
2752
2753         return e;
2754 }
2755
2756 /*! \brief Check state of extension by using hints */
2757 static int ast_extension_state2(struct ast_exten *e)
2758 {
2759         char hint[AST_MAX_EXTENSION];
2760         char *cur, *rest;
2761         int allunavailable = 1, allbusy = 1, allfree = 1, allonhold = 1;
2762         int busy = 0, inuse = 0, ring = 0;
2763
2764         if (!e)
2765                 return -1;
2766
2767         ast_copy_string(hint, ast_get_extension_app(e), sizeof(hint));
2768
2769         rest = hint;    /* One or more devices separated with a & character */
2770         while ( (cur = strsep(&rest, "&")) ) {
2771                 int res = ast_device_state(cur);
2772                 switch (res) {
2773                 case AST_DEVICE_NOT_INUSE:
2774                         allunavailable = 0;
2775                         allbusy = 0;
2776                         allonhold = 0;
2777                         break;
2778                 case AST_DEVICE_INUSE:
2779                         inuse = 1;
2780                         allunavailable = 0;
2781                         allfree = 0;
2782                         allonhold = 0;
2783                         break;
2784                 case AST_DEVICE_RINGING:
2785                         ring = 1;
2786                         allunavailable = 0;
2787                         allfree = 0;
2788                         allonhold = 0;
2789                         break;
2790                 case AST_DEVICE_RINGINUSE:
2791                         inuse = 1;
2792                         ring = 1;
2793                         allunavailable = 0;
2794                         allfree = 0;
2795                         allonhold = 0;
2796                         break;
2797                 case AST_DEVICE_ONHOLD:
2798                         allunavailable = 0;
2799                         allfree = 0;
2800                         break;
2801                 case AST_DEVICE_BUSY:
2802                         allunavailable = 0;
2803                         allfree = 0;
2804                         allonhold = 0;
2805                         busy = 1;
2806                         break;
2807                 case AST_DEVICE_UNAVAILABLE:
2808                 case AST_DEVICE_INVALID:
2809                         allbusy = 0;
2810                         allfree = 0;
2811                         allonhold = 0;
2812                         break;
2813                 default:
2814                         allunavailable = 0;
2815                         allbusy = 0;
2816                         allfree = 0;
2817                         allonhold = 0;
2818                 }
2819         }
2820
2821         if (!inuse && ring)
2822                 return AST_EXTENSION_RINGING;
2823         if (inuse && ring)
2824                 return (AST_EXTENSION_INUSE | AST_EXTENSION_RINGING);
2825         if (inuse)
2826                 return AST_EXTENSION_INUSE;
2827         if (allfree)
2828                 return AST_EXTENSION_NOT_INUSE;
2829         if (allonhold)
2830                 return AST_EXTENSION_ONHOLD;
2831         if (allbusy)
2832                 return AST_EXTENSION_BUSY;
2833         if (allunavailable)
2834                 return AST_EXTENSION_UNAVAILABLE;
2835         if (busy)
2836                 return AST_EXTENSION_INUSE;
2837
2838         return AST_EXTENSION_NOT_INUSE;
2839 }
2840
2841 /*! \brief Return extension_state as string */
2842 const char *ast_extension_state2str(int extension_state)
2843 {
2844         int i;
2845
2846         for (i = 0; (i < (sizeof(extension_states) / sizeof(extension_states[0]))); i++) {
2847                 if (extension_states[i].extension_state == extension_state)
2848                         return extension_states[i].text;
2849         }
2850         return "Unknown";
2851 }
2852
2853 /*! \brief Check extension state for an extension by using hint */
2854 int ast_extension_state(struct ast_channel *c, const char *context, const char *exten)
2855 {
2856         struct ast_exten *e;
2857
2858         e = ast_hint_extension(c, context, exten);      /* Do we have a hint for this extension ? */
2859         if (!e)
2860                 return -1;                              /* No hint, return -1 */
2861
2862         return ast_extension_state2(e);                 /* Check all devices in the hint */
2863 }
2864
2865 static void handle_statechange(const char *device)
2866 {
2867         struct ast_hint *hint;
2868
2869         AST_RWLIST_RDLOCK(&hints);
2870
2871         AST_RWLIST_TRAVERSE(&hints, hint, list) {
2872                 struct ast_state_cb *cblist;
2873                 char buf[AST_MAX_EXTENSION];
2874                 char *parse = buf;
2875                 char *cur;
2876                 int state;
2877
2878                 ast_copy_string(buf, ast_get_extension_app(hint->exten), sizeof(buf));
2879                 while ( (cur = strsep(&parse, "&")) ) {
2880                         if (!strcasecmp(cur, device))
2881                                 break;
2882                 }
2883                 if (!cur)
2884                         continue;
2885
2886                 /* Get device state for this hint */
2887                 state = ast_extension_state2(hint->exten);
2888
2889                 if ((state == -1) || (state == hint->laststate))
2890                         continue;
2891
2892                 /* Device state changed since last check - notify the watchers */
2893
2894                 /* For general callbacks */
2895                 for (cblist = statecbs; cblist; cblist = cblist->next)
2896                         cblist->callback(hint->exten->parent->name, hint->exten->exten, state, cblist->data);
2897
2898                 /* For extension callbacks */
2899                 for (cblist = hint->callbacks; cblist; cblist = cblist->next)
2900                         cblist->callback(hint->exten->parent->name, hint->exten->exten, state, cblist->data);
2901
2902                 hint->laststate = state;        /* record we saw the change */
2903         }
2904
2905         AST_RWLIST_UNLOCK(&hints);
2906 }
2907
2908 static int statechange_queue(const char *dev)
2909 {
2910         struct statechange *sc;
2911
2912         if (!(sc = ast_calloc(1, sizeof(*sc) + strlen(dev) + 1)))
2913                 return 0;
2914
2915         strcpy(sc->dev, dev);
2916
2917         ast_mutex_lock(&device_state.lock);
2918         AST_LIST_INSERT_TAIL(&device_state.state_change_q, sc, entry);
2919         ast_cond_signal(&device_state.cond);
2920         ast_mutex_unlock(&device_state.lock);
2921
2922         return 0;
2923 }
2924
2925 static void *device_state_thread(void *data)
2926 {
2927         struct statechange *sc;
2928
2929         while (!device_state.stop) {
2930                 ast_mutex_lock(&device_state.lock);
2931                 while (!(sc = AST_LIST_REMOVE_HEAD(&device_state.state_change_q, entry))) {
2932                         ast_cond_wait(&device_state.cond, &device_state.lock);
2933                         /* Check to see if we were woken up to see the request to stop */
2934                         if (device_state.stop) {
2935                                 ast_mutex_unlock(&device_state.lock);
2936                                 return NULL;
2937                         }
2938                 }
2939                 ast_mutex_unlock(&device_state.lock);
2940
2941                 handle_statechange(sc->dev);
2942
2943                 ast_free(sc);
2944         }
2945
2946         return NULL;
2947 }
2948
2949 /*! \brief  Add watcher for extension states */
2950 int ast_extension_state_add(const char *context, const char *exten,
2951                             ast_state_cb_type callback, void *data)
2952 {
2953         struct ast_hint *hint;
2954         struct ast_state_cb *cblist;
2955         struct ast_exten *e;
2956
2957         /* If there's no context and extension:  add callback to statecbs list */
2958         if (!context && !exten) {
2959                 AST_RWLIST_WRLOCK(&hints);
2960
2961                 for (cblist = statecbs; cblist; cblist = cblist->next) {
2962                         if (cblist->callback == callback) {
2963                                 cblist->data = data;
2964                                 AST_RWLIST_UNLOCK(&hints);
2965                                 return 0;
2966                         }
2967                 }
2968
2969                 /* Now insert the callback */
2970                 if (!(cblist = ast_calloc(1, sizeof(*cblist)))) {
2971                         AST_RWLIST_UNLOCK(&hints);
2972                         return -1;
2973                 }
2974                 cblist->id = 0;
2975                 cblist->callback = callback;
2976                 cblist->data = data;
2977
2978                 cblist->next = statecbs;
2979                 statecbs = cblist;
2980
2981                 AST_RWLIST_UNLOCK(&hints);
2982                 return 0;
2983         }
2984
2985         if (!context || !exten)
2986                 return -1;
2987
2988         /* This callback type is for only one hint, so get the hint */
2989         e = ast_hint_extension(NULL, context, exten);
2990         if (!e) {
2991                 return -1;
2992         }
2993
2994         /* Find the hint in the list of hints */
2995         AST_RWLIST_WRLOCK(&hints);
2996
2997         AST_RWLIST_TRAVERSE(&hints, hint, list) {
2998                 if (hint->exten == e)
2999                         break;
3000         }
3001
3002         if (!hint) {
3003                 /* We have no hint, sorry */
3004                 AST_RWLIST_UNLOCK(&hints);
3005                 return -1;
3006         }
3007
3008         /* Now insert the callback in the callback list  */
3009         if (!(cblist = ast_calloc(1, sizeof(*cblist)))) {
3010                 AST_RWLIST_UNLOCK(&hints);
3011                 return -1;
3012         }
3013         cblist->id = stateid++;         /* Unique ID for this callback */
3014         cblist->callback = callback;    /* Pointer to callback routine */
3015         cblist->data = data;            /* Data for the callback */
3016
3017         cblist->next = hint->callbacks;
3018         hint->callbacks = cblist;
3019
3020         AST_RWLIST_UNLOCK(&hints);
3021         return cblist->id;
3022 }
3023
3024 /*! \brief Remove a watcher from the callback list */
3025 int ast_extension_state_del(int id, ast_state_cb_type callback)
3026 {
3027         struct ast_state_cb **p_cur = NULL;     /* address of pointer to us */
3028         int ret = -1;
3029
3030         if (!id && !callback)
3031                 return -1;
3032
3033         AST_RWLIST_WRLOCK(&hints);
3034
3035         if (!id) {      /* id == 0 is a callback without extension */
3036                 for (p_cur = &statecbs; *p_cur; p_cur = &(*p_cur)->next) {
3037                         if ((*p_cur)->callback == callback)
3038                                 break;
3039                 }
3040         } else { /* callback with extension, find the callback based on ID */
3041                 struct ast_hint *hint;
3042                 AST_RWLIST_TRAVERSE(&hints, hint, list) {
3043                         for (p_cur = &hint->callbacks; *p_cur; p_cur = &(*p_cur)->next) {
3044                                 if ((*p_cur)->id == id)
3045                                         break;
3046                         }
3047                         if (*p_cur)     /* found in the inner loop */
3048                                 break;
3049                 }
3050         }
3051         if (p_cur && *p_cur) {
3052                 struct ast_state_cb *cur = *p_cur;
3053                 *p_cur = cur->next;
3054                 ast_free(cur);
3055                 ret = 0;
3056         }
3057         AST_RWLIST_UNLOCK(&hints);
3058         return ret;
3059 }
3060
3061 /*! \brief Add hint to hint list, check initial extension state */
3062 static int ast_add_hint(struct ast_exten *e)
3063 {
3064         struct ast_hint *hint;
3065
3066         if (!e)
3067                 return -1;
3068
3069         AST_RWLIST_WRLOCK(&hints);
3070
3071         /* Search if hint exists, do nothing */
3072         AST_RWLIST_TRAVERSE(&hints, hint, list) {
3073                 if (hint->exten == e) {
3074                         AST_RWLIST_UNLOCK(&hints);
3075                         ast_debug(2, "HINTS: Not re-adding existing hint %s: %s\n", ast_get_extension_name(e), ast_get_extension_app(e));
3076                         return -1;
3077                 }
3078         }
3079
3080         ast_debug(2, "HINTS: Adding hint %s: %s\n", ast_get_extension_name(e), ast_get_extension_app(e));
3081
3082         if (!(hint = ast_calloc(1, sizeof(*hint)))) {
3083                 AST_RWLIST_UNLOCK(&hints);
3084                 return -1;
3085         }
3086         /* Initialize and insert new item at the top */
3087         hint->exten = e;
3088         hint->laststate = ast_extension_state2(e);
3089         AST_RWLIST_INSERT_HEAD(&hints, hint, list);
3090
3091         AST_RWLIST_UNLOCK(&hints);
3092         return 0;
3093 }
3094
3095 /*! \brief Change hint for an extension */
3096 static int ast_change_hint(struct ast_exten *oe, struct ast_exten *ne)
3097 {
3098         struct ast_hint *hint;
3099         int res = -1;
3100
3101         AST_RWLIST_WRLOCK(&hints);
3102