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