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