Review Board 1.7.16


Various fixes for extenpatternmatchnew

Review Request #194 - Created March 13, 2009 and submitted

Mark Michelson
/trunk
14615
Reviewers
asterisk-dev
Asterisk
When looking into issue 14615, I found a variety of problems which I have addressed in my npm_fixes branch. Here is a summary of the fixes I made:

1. Create different trie entries for pattern and non-pattern matches which are otherwise identical. For example, if you had an extensions "NNN" and "_NNN" in your dialplan, then we need to create two separate trie entries for matching against.

2. Make sure to only apply pattern-matching logic if the extension we are matching against is a pattern extension. This is what bug 14615 is actually about. In that example, the reporter was attempting to Goto() the extension "ANSWER." The problem was that when the 'N' was encountered while looking at the pattern trie, it would not match the literal character 'N' that was being passed in. However, if the Goto() were modified to go to something like "A4SWER" it would go to the ANSWER extension. This behavior has been corrected.

3. Fixed a few places where the code could potentially crash due to dereferencing NULL pointers.

4. Changed the allocation scheme of a match_char to use the "allocation after the struct" method.

5. Did a bunch of coding guidelines-related cleanup.

6. Removed all blocks of code enclosed inside #ifdef NOTNOW...#endif. These areas were designed to use a more manual algorithm for looking up contexts than just finding them in a hashtab. The logic used in these blocks was off, and I can't think of any good reason why you would want to do this.

For anyone who wants to understand how the pattern-matching trie works before taking a crack at this review, you can find a large comment in main/pbx.c that Murf wrote that does an excellent job of explaining things. This comment block is located just below the function pbx_destroy().
I tested the following dialplan, admittedly not the most thorough, but it gets the job done:

exten => 333,1,NoOp(Starting Test, exten 333)
exten => 333,n,Goto(ANSWER,1)
exten => 333,n,Hangup

exten => NNN,1,NoOp(Starting Test, exten NNN)
exten => NNN,n,Playback(tt-monkeys)
exten => NNN,n,Hangup

exten => _NNN,1,NoOp(Starting Test, exten _NNN)
exten => _NNN,n,Playback(tt-weasels)
exten => _NNN,n,Hangup

exten => ANSWER,1,NoOp(Test no answer)
exten => ANSWER,n,Playback(vm-goodbye)
exten => ANSWER,n,Hangup

exten => _1[2-9],1,NoOp(Starting Test, exten _1[2-9])
exten => _1[2-9],n,Playback(queue-thankyou)
exten => _1[2-9],n,Hangup

With this, I could test numeric extensions, string extensions, patterns with reserved letters (i.e. N, Z, X), and patterns with bracketed expressions. In all cases, the pattern I expected to match was matched. The reporter on issue 14615 has also given the branch a test and says that things work for him in his dialplan now.

Diff revision 1 (Latest)

  1. /trunk/main/pbx.c: Loading...
/trunk/main/pbx.c
Revision 182115 New Change
[20] 815 lines
[+20] [+] struct ast_ignorepat {
816
/*! \brief match_char: forms a syntax tree for quick matching of extension patterns */
816
/*! \brief match_char: forms a syntax tree for quick matching of extension patterns */
817
struct match_char
817
struct match_char
818
{
818
{
819
	int is_pattern; /* the pattern started with '_' */
819
	int is_pattern; /* the pattern started with '_' */
820
	int deleted;    /* if this is set, then... don't return it */
820
	int deleted;    /* if this is set, then... don't return it */
821
	char *x;       /* the pattern itself-- matches a single char */

   
822
	int specificity; /* simply the strlen of x, or 10 for X, 9 for Z, and 8 for N; and '.' and '!' will add 11 ? */
821
	int specificity; /* simply the strlen of x, or 10 for X, 9 for Z, and 8 for N; and '.' and '!' will add 11 ? */
823
	struct match_char *alt_char;
822
	struct match_char *alt_char;
824
	struct match_char *next_char;
823
	struct match_char *next_char;
825
	struct ast_exten *exten; /* attached to last char of a pattern for exten */
824
	struct ast_exten *exten; /* attached to last char of a pattern for exten */

    
   
825
	char x[1];       /* the pattern itself-- matches a single char */
826
};
826
};
827

    
   
827

   
828
struct scoreboard  /* make sure all fields are 0 before calling new_find_extension */
828
struct scoreboard  /* make sure all fields are 0 before calling new_find_extension */
829
{
829
{
830
	int total_specificity;
830
	int total_specificity;
[+20] [20] 116 lines
[+20] [+] void log_match_char_tree(struct match_char *node, char *prefix); /* for use anywhere */
947
static int pbx_builtin_importvar(struct ast_channel *, void *);
947
static int pbx_builtin_importvar(struct ast_channel *, void *);
948
static void set_ext_pri(struct ast_channel *c, const char *exten, int pri);
948
static void set_ext_pri(struct ast_channel *c, const char *exten, int pri);
949
static void new_find_extension(const char *str, struct scoreboard *score,
949
static void new_find_extension(const char *str, struct scoreboard *score,
950
		struct match_char *tree, int length, int spec, const char *callerid,
950
		struct match_char *tree, int length, int spec, const char *callerid,
951
		const char *label, enum ext_match_t action);
951
		const char *label, enum ext_match_t action);
952
static struct match_char *already_in_tree(struct match_char *current, char *pat);
952
static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern);
953
static struct match_char *add_exten_to_pattern_tree(struct ast_context *con,
953
static struct match_char *add_exten_to_pattern_tree(struct ast_context *con,
954
		struct ast_exten *e1, int findonly);
954
		struct ast_exten *e1, int findonly);
955
static struct match_char *add_pattern_node(struct ast_context *con,
955
static struct match_char *add_pattern_node(struct ast_context *con,
956
		struct match_char *current, char *pattern, int is_pattern,
956
		struct match_char *current, char *pattern, int is_pattern,
957
		int already, int specificity, struct match_char **parent);
957
		int already, int specificity, struct match_char **parent);
[+20] [20] 532 lines
[+20] [+] void log_match_char_tree(struct match_char *node, char *prefix)
1490
	char extenstr[40];
1490
	char extenstr[40];
1491
	struct ast_str *my_prefix = ast_str_alloca(1024);
1491
	struct ast_str *my_prefix = ast_str_alloca(1024);
1492

    
   
1492

   
1493
	extenstr[0] = '\0';
1493
	extenstr[0] = '\0';
1494

    
   
1494

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

    
   
1497

   
1498
	if (strlen(node->x) > 1) {
1498
	if (strlen(node->x) > 1) {
1499
		ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1499
		ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1500
			node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1500
			node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
[+20] [20] 18 lines
[+20] [+] static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
1519
	char extenstr[40];
1519
	char extenstr[40];
1520
	struct ast_str *my_prefix = ast_str_alloca(1024);
1520
	struct ast_str *my_prefix = ast_str_alloca(1024);
1521

    
   
1521

   
1522
	extenstr[0] = '\0';
1522
	extenstr[0] = '\0';
1523

    
   
1523

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

    
   
1526

   
1527
	if (strlen(node->x) > 1) {
1527
	if (strlen(node->x) > 1) {
1528
		ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1528
		ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1529
			node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1529
			node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
[+20] [20] 64 lines
[+20] [+] static struct ast_exten *trie_find_next_match(struct match_char *node)
1594
		e3 = trie_find_next_match(m3);
1594
		e3 = trie_find_next_match(m3);
1595
		if (e3) {
1595
		if (e3) {
1596
			return e3;
1596
			return e3;
1597
		}
1597
		}
1598
	}
1598
	}

    
   
1599

   
1599
	return NULL;
1600
	return NULL;
1600
}
1601
}
1601

    
   
1602

   
1602
#ifdef DEBUG_THIS
1603
#ifdef DEBUG_THIS
1603
static char *action2str(enum ext_match_t action)
1604
static char *action2str(enum ext_match_t action)
[+20] [20] 25 lines
[+20] [+] static void new_find_extension(const char *str, struct scoreboard *score, struct match_char *tree, int length, int spec, const char *label, const char *callerid, enum ext_match_t action)
1629
		ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
1630
		ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
1630
	else
1631
	else
1631
		ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
1632
		ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
1632
#endif
1633
#endif
1633
	for (p = tree; p; p = p->alt_char) {
1634
	for (p = tree; p; p = p->alt_char) {

    
   
1635
		if (p->is_pattern) {
1634
		if (p->x[0] == 'N') {
1636
			if (p->x[0] == 'N') {
1635
			if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
1637
				if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
1636
#define NEW_MATCHER_CHK_MATCH	       \
1638
#define	NEW_MATCHER_CHK_MATCH	       \
1637
				if (p->exten && !(*(str + 1))) { /* if a shorter pattern matches along the way, might as well report it */           \
1639
					if (p->exten && !(*(str + 1))) { /* if a shorter pattern matches along the way, might as well report it */             \
1638
					if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */   \
1640
						if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */   \
1639
						update_scoreboard(score, length + 1, spec + p->specificity, p->exten, 0, callerid, p->deleted, p);           \
1641
							update_scoreboard(score, length + 1, spec + p->specificity, p->exten, 0, callerid, p->deleted, p);                 \
1640
						if (!p->deleted) {                                                                                           \
1642
							if (!p->deleted) {                                                                                           \
1641
							if (action == E_FINDLABEL) {                                                                             \
1643
								if (action == E_FINDLABEL) {                                                                             \
1642
								if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) {                                  \
1644
									if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) {                                  \
1643
									ast_debug(4, "Found label in preferred extension\n");                                            \
1645
										ast_debug(4, "Found label in preferred extension\n");                                            \
1644
									return;                                                                                          \
1646
										return;                                                                                          \
1645
								}                                                                                                    \
1647
									}                                                                                                    \
1646
							} else {                                                                                                 \
1648
								} else {                                                                                                 \
1647
								ast_debug(4,"returning an exact match-- first found-- %s\n", p->exten->exten);                       \
1649
									ast_debug(4, "returning an exact match-- first found-- %s\n", p->exten->exten);                       \
1648
								return; /* the first match, by definition, will be the best, because of the sorted tree */           \
1650
									return; /* the first match, by definition, will be the best, because of the sorted tree */           \
1649
							}                                                                                                        \
1651
								}                                                                                                        \
1650
						}                                                                                                            \
1652
							}                                                                                                            \
1651
					}                                                                                                                \
1653
						}                                                                                                                \
1652
				}
1654
					}
1653

    
   
1655
					
1654
#define NEW_MATCHER_RECURSE	           \
1656
#define	NEW_MATCHER_RECURSE	           \
1655
				if (p->next_char && ( *(str + 1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)               \
1657
					if (p->next_char && (*(str + 1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)                 \
1656
                                                 || p->next_char->x[0] == '!')) {                                        \
1658
        	                                       || p->next_char->x[0] == '!')) {                                          \
1657
					if (*(str + 1) || p->next_char->x[0] == '!') {                                                       \
1659
						if (*(str + 1) || p->next_char->x[0] == '!') {                                                         \
1658
						new_find_extension(str + 1, score, p->next_char, length + 1, spec+p->specificity, callerid, label, action); \
1660
							new_find_extension(str + 1, score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
1659
						if (score->exten)  {                                                                             \
1661
							if (score->exten)  {                                                                             \
1660
					        ast_debug(4, "returning an exact match-- %s\n", score->exten->exten);                        \
1662
						        ast_debug(4 ,"returning an exact match-- %s\n", score->exten->exten);                         \
1661
							return; /* the first match is all we need */                                                 \
1663
								return; /* the first match is all we need */                                                 \
1662
						}												                                                 \
1664
							}												                                                 \
1663
					} else {                                                                                             \
1665
						} else {                                                                                             \
1664
						new_find_extension("/", score, p->next_char, length + 1, spec+p->specificity, callerid, label, action);	 \
1666
							new_find_extension("/", score, p->next_char, length + 1, spec + p->specificity, callerid, label, action);	 \
1665
						if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {      \
1667
							if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {      \
1666
					        ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->exten :     \
1668
						        ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->exten :     \
1667
                                       "NULL");                                                                          \
1669
        	                               "NULL");                                                                        \
1668
							return; /* the first match is all we need */                                                 \
1670
								return; /* the first match is all we need */                                                 \
1669
						}												                                                 \
1671
							}												                                                 \
1670
					}                                                                                                    \
1672
						}                                                                                                    \
1671
				} else if (p->next_char && !*(str + 1)) {                                                                \
1673
					} else if (p->next_char && !*(str + 1)) {                                                                  \
1672
					score->canmatch = 1;                                                                                 \
1674
						score->canmatch = 1;                                                                                 \
1673
					score->canmatch_exten = get_canmatch_exten(p);                                                       \
1675
						score->canmatch_exten = get_canmatch_exten(p);                                                       \
1674
					if (action == E_CANMATCH || action == E_MATCHMORE) {                                                 \
1676
						if (action == E_CANMATCH || action == E_MATCHMORE) {                                                 \
1675
				        ast_debug(4, "returning a canmatch/matchmore--- str=%s\n", str);                                 \
1677
					        ast_debug(4, "returning a canmatch/matchmore--- str=%s\n", str);                                  \
1676
						return;                                                                                          \
1678
							return;                                                                                          \
1677
					}												                                                     \
1679
						}												                                                     \
1678
				}
1680
					}
1679

    
   
1681
					
1680
				NEW_MATCHER_CHK_MATCH;
1682
					NEW_MATCHER_CHK_MATCH;
1681
				NEW_MATCHER_RECURSE;
1683
					NEW_MATCHER_RECURSE;
1682
			}
1684
				}
1683
		} else if (p->x[0] == 'Z') {
1685
			} else if (p->x[0] == 'Z') {
1684
			if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
1686
				if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
1685
				NEW_MATCHER_CHK_MATCH;
1687
					NEW_MATCHER_CHK_MATCH;
1686
				NEW_MATCHER_RECURSE;
1688
					NEW_MATCHER_RECURSE;
1687
			}
1689
				}
1688
		} else if (p->x[0] == 'X') {
1690
			} else if (p->x[0] == 'X') { 
1689
			if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1691
				if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1690
				NEW_MATCHER_CHK_MATCH;
1692
					NEW_MATCHER_CHK_MATCH;
1691
				NEW_MATCHER_RECURSE;
1693
					NEW_MATCHER_RECURSE;
1692
			}
1694
				}
1693
		} else if (p->x[0] == '.' && p->x[1] == 0) {
1695
			} else if (p->x[0] == '.' && p->x[1] == 0) {
1694
			/* how many chars will the . match against? */
1696
				/* how many chars will the . match against? */
1695
			int i = 0;
1697
				int i = 0;
1696
			const char *str2 = str;
1698
				const char *str2 = str;
1697
			while (*str2 && *str2 != '/') {
1699
				while (*str2 && *str2 != '/') {
1698
				str2++;
1700
					str2++;
1699
				i++;
1701
					i++;
1700
			}
1702
				}
1701
			if (p->exten && *str2 != '/') {
1703
				if (p->exten && *str2 != '/') {
1702
				update_scoreboard(score, length+i, spec+(i*p->specificity), p->exten, '.', callerid, p->deleted, p);
1704
					update_scoreboard(score, length + i, spec + (i * p->specificity), p->exten, '.', callerid, p->deleted, p);
1703
				if (score->exten) {
1705
					if (score->exten) {
1704
					ast_debug(4,"return because scoreboard has a match with '/'--- %s\n", score->exten->exten);
1706
						ast_debug(4,"return because scoreboard has a match with '/'--- %s\n", score->exten->exten);
1705
					return; /* the first match is all we need */
1707
						return; /* the first match is all we need */
1706
				}
1708
					}
1707
			}
1709
				}
1708
			if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1710
				if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1709
				new_find_extension("/", score, p->next_char, length+i, spec+(p->specificity*i), callerid, label, action);
1711
					new_find_extension("/", score, p->next_char, length + i, spec+(p->specificity*i), callerid, label, action);
1710
				if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1712
					if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1711
					ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set--- %s\n", score->exten ? score->exten->exten : "NULL");
1713
						ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set--- %s\n", score->exten ? score->exten->exten : "NULL");
1712
					return; /* the first match is all we need */
1714
						return; /* the first match is all we need */
1713
				}
1715
					}
1714
			}
1716
				}
[+20] [20] 4 lines
[+20] static void new_find_extension(const char *str, struct scoreboard *score, struct match_char *tree, int length, int spec, const char *label, const char *callerid, enum ext_match_t action)
1719
			while (*str2 && *str2 != '/') {
1721
				while (*str2 && *str2 != '/') {
1720
				str2++;
1722
					str2++;
1721
				i++;
1723
					i++;
1722
			}
1724
				}
1723
			if (p->exten && *str2 != '/') {
1725
				if (p->exten && *str2 != '/') {
1724
				update_scoreboard(score, length + 1, spec+(p->specificity * i), p->exten, '!', callerid, p->deleted, p);
1726
					update_scoreboard(score, length + 1, spec + (p->specificity * i), p->exten, '!', callerid, p->deleted, p);
1725
				if (score->exten) {
1727
					if (score->exten) {
1726
					ast_debug(4, "return because scoreboard has a '!' match--- %s\n", score->exten->exten);
1728
						ast_debug(4, "return because scoreboard has a '!' match--- %s\n", score->exten->exten);
1727
					return; /* the first match is all we need */
1729
						return; /* the first match is all we need */
1728
				}
1730
					}
1729
			}
1731
				}
1730
			if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1732
				if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1731
				new_find_extension("/", score, p->next_char, length + i, spec + (p->specificity * i), callerid, label, action);
1733
					new_find_extension("/", score, p->next_char, length + i, spec + (p->specificity * i), callerid, label, action);
1732
				if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1734
					if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1733
					ast_debug(4,"return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n", score->exten ? score->exten->exten : "NULL");
1735
						ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n", score->exten ? score->exten->exten : "NULL");
1734
					return; /* the first match is all we need */
1736
						return; /* the first match is all we need */
1735
				}
1737
					}
1736
			}
1738
				}
1737
		} else if (p->x[0] == '/' && p->x[1] == 0) {
1739
			} else if (p->x[0] == '/' && p->x[1] == 0) {
1738
			/* the pattern in the tree includes the cid match! */
1740
				/* the pattern in the tree includes the cid match! */
1739
			if (p->next_char && callerid && *callerid) {
1741
				if (p->next_char && callerid && *callerid) {
1740
				new_find_extension(callerid, score, p->next_char, length+1, spec, callerid, label, action);
1742
					new_find_extension(callerid, score, p->next_char, length + 1, spec, callerid, label, action);
1741
				if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1743
					if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1742
					ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n", score->exten ? score->exten->exten : "NULL");
1744
						ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n", score->exten ? score->exten->exten : "NULL");
1743
					return; /* the first match is all we need */
1745
						return; /* the first match is all we need */
1744
				}
1746
					}
1745
			}
1747
				}
1746
		} else if (strchr(p->x, *str)) {
1748
			} else if (strchr(p->x, *str)) {
1747
			ast_debug(4, "Nothing strange about this match\n");
1749
				ast_debug(4, "Nothing strange about this match\n");
1748
			NEW_MATCHER_CHK_MATCH;
1750
				NEW_MATCHER_CHK_MATCH;
1749
			NEW_MATCHER_RECURSE;
1751
				NEW_MATCHER_RECURSE;
1750
		}
1752
			}

    
   
1753
		} else if (strchr(p->x, *str)) {

    
   
1754
			ast_debug(4, "Nothing strange about this match\n");

    
   
1755
			NEW_MATCHER_CHK_MATCH;

    
   
1756
			NEW_MATCHER_RECURSE;

    
   
1757
		}
1751
	}
1758
	}
1752
	ast_debug(4, "return at end of func\n");
1759
	ast_debug(4, "return at end of func\n");
1753
}
1760
}
1754

    
   
1761

   
1755
/* the algorithm for forming the extension pattern tree is also a bit simple; you
1762
/* the algorithm for forming the extension pattern tree is also a bit simple; you
[+20] [20] 11 lines
[+20] static void new_find_extension(const char *str, struct scoreboard *score, struct match_char *tree, int length, int spec, const char *label, const char *callerid, enum ext_match_t action)
1767
 * that a regex only handles 1 pattern, really. This trie holds any number
1774
 * that a regex only handles 1 pattern, really. This trie holds any number
1768
 * of patterns. Well, really, it **could** be considered a single pattern,
1775
 * of patterns. Well, really, it **could** be considered a single pattern,
1769
 * where the "|" (or) operator is allowed, I guess, in a way, sort of...
1776
 * where the "|" (or) operator is allowed, I guess, in a way, sort of...
1770
 */
1777
 */
1771

    
   
1778

   
1772
static struct match_char *already_in_tree(struct match_char *current, char *pat)
1779
static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern)
1773
{
1780
{
1774
	struct match_char *t;
1781
	struct match_char *t;
1775

    
   
1782

   
1776
	if (!current) {
1783
	if (!current) {
1777
		return 0;
1784
		return 0;
1778
	}
1785
	}
1779

    
   
1786

   
1780
	for (t = current; t; t = t->alt_char) {
1787
	for (t = current; t; t = t->alt_char) {
1781
		if (!strcmp(pat, t->x)) { /* uh, we may want to sort exploded [] contents to make matching easy */
1788
		if (is_pattern == t->is_pattern && !strcmp(pat, t->x)) {/* uh, we may want to sort exploded [] contents to make matching easy */
1782
			return t;
1789
			return t;
1783
		}
1790
		}
1784
	}
1791
	}
1785

    
   
1792

   
1786
	return 0;
1793
	return 0;
[+20] [20] 9 lines
[+20] [+] static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, struct match_char *node)
1796

    
   
1803

   
1797
	/* insert node into the tree at "current", so the alt_char list from current is
1804
	/* insert node into the tree at "current", so the alt_char list from current is
1798
	   sorted in increasing value as you go to the leaves */
1805
	   sorted in increasing value as you go to the leaves */
1799
	if (!(*parent_ptr)) {
1806
	if (!(*parent_ptr)) {
1800
		*parent_ptr = node;
1807
		*parent_ptr = node;
1801
	} else {
1808
		return;
1802
		if ((*parent_ptr)->specificity > node->specificity) {
1809
	}

    
   
1810

   

    
   
1811
	if ((*parent_ptr)->specificity > node->specificity){
1803
			/* insert at head */
1812
		/* insert at head */
1804
			node->alt_char = (*parent_ptr);
1813
		node->alt_char = (*parent_ptr);
1805
			*parent_ptr = node;
1814
		*parent_ptr = node;
1806
		} else {
1815
		return;

    
   
1816
	} 

    
   
1817

   
1807
			lcurr = *parent_ptr;
1818
	lcurr = *parent_ptr;
1808
			for (curr = (*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
1819
	for (curr = (*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
1809
				if (curr->specificity > node->specificity) {
1820
		if (curr->specificity > node->specificity) {
1810
					node->alt_char = curr;
1821
			node->alt_char = curr;
1811
					lcurr->alt_char = node;
1822
			lcurr->alt_char = node;
1812
					break;
1823
			break;
1813
				}
1824
		}
1814
				lcurr = curr;
1825
		lcurr = curr;
1815
			}
1826
	}

    
   
1827

   
1816
			if (!curr) {
1828
	if (!curr) {
1817
				lcurr->alt_char = node;
1829
		lcurr->alt_char = node;
1818
			}
1830
	}
1819
		}

   
1820
	}

   
1821
}

   
1822

    
   

   
1823

    
   
1831

   

    
   
1832
}
1824

    
   
1833

   
1825
static struct match_char *add_pattern_node(struct ast_context *con, struct match_char *current, char *pattern, int is_pattern, int already, int specificity, struct match_char **nextcharptr)
1834
static struct match_char *add_pattern_node(struct ast_context *con, struct match_char *current, char *pattern, int is_pattern, int already, int specificity, struct match_char **nextcharptr)
1826
{
1835
{
1827
	struct match_char *m;
1836
	struct match_char *m;
1828

    
   
1837
	
1829
	if (!(m = ast_calloc(1, sizeof(*m)))) {
1838
	if (!(m = ast_calloc(1, sizeof(*m) + strlen(pattern)))) {
1830
		return NULL;
1839
		return NULL;
1831
	}
1840
	}
1832

    
   
1841

   
1833
	if (!(m->x = ast_strdup(pattern))) {
1842
	/* strcpy is safe here since we know its size and have allocated
1834
		ast_free(m);
1843
	 * just enough space for when we allocated m
1835
		return NULL;
1844
	 */
1836
	}
1845
	strcpy(m->x, pattern);
1837

    
   
1846

   
1838
	/* the specificity scores are the same as used in the old
1847
	/* the specificity scores are the same as used in the old
1839
	   pattern matcher. */
1848
	   pattern matcher. */
1840
	m->is_pattern = is_pattern;
1849
	m->is_pattern = is_pattern;
1841
	if (specificity == 1 && is_pattern && pattern[0] == 'N')
1850
	if (specificity == 1 && is_pattern && pattern[0] == 'N')
[+20] [20] 52 lines
[+20] [+] static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
1894

    
   
1903

   
1895
	if ( *s1 == '_') {
1904
	if ( *s1 == '_') {
1896
		pattern = 1;
1905
		pattern = 1;
1897
		s1++;
1906
		s1++;
1898
	}
1907
	}
1899
	while( *s1 ) {
1908
	while (*s1) {
1900
		if (pattern && *s1 == '[' && *(s1-1) != '\\') {
1909
		if (pattern && *s1 == '[' && *(s1 - 1) != '\\') {
1901
			char *s2 = buf;
1910
			char *s2 = buf;
1902
			buf[0] = 0;
1911
			buf[0] = 0;
1903
			s1++; /* get past the '[' */
1912
			s1++; /* get past the '[' */
1904
			while (*s1 != ']' && *(s1 - 1) != '\\' ) {
1913
			while (*s1 != ']' && *(s1 - 1) != '\\') {
1905
				if (*s1 == '\\') {
1914
				if (*s1 == '\\') {
1906
					if (*(s1 + 1) == ']') {
1915
					if (*(s1 + 1) == ']') {
1907
						*s2++ = ']';
1916
						*s2++ = ']';
1908
						s1++; s1++;
1917
						s1 += 2;
1909
					} else if (*(s1 + 1) == '\\') {
1918
					} else if (*(s1 + 1) == '\\') {
1910
						*s2++ = '\\';
1919
						*s2++ = '\\';
1911
						s1++; s1++;
1920
						s1 += 2;
1912
					} else if (*(s1 + 1) == '-') {
1921
					} else if (*(s1 + 1) == '-') {
1913
						*s2++ = '-';
1922
						*s2++ = '-';
1914
						s1++; s1++;
1923
						s1 += 2;
1915
					} else if (*(s1 + 1) == '[') {
1924
					} else if (*(s1 + 1) == '[') {
1916
						*s2++ = '[';
1925
						*s2++ = '[';
1917
						s1++; s1++;
1926
						s1 += 2;
1918
					}
1927
					}
1919
				} else if (*s1 == '-') { /* remember to add some error checking to all this! */
1928
				} else if (*s1 == '-') { /* remember to add some error checking to all this! */
1920
					char s3 = *(s1 - 1);
1929
					char s3 = *(s1 - 1);
1921
					char s4 = *(s1 + 1);
1930
					char s4 = *(s1 + 1);
1922
					for (s3++; s3 <= s4; s3++) {
1931
					for (s3++; s3 <= s4; s3++) {
1923
						*s2++ = s3;
1932
						*s2++ = s3;
1924
					}
1933
					}
1925
					s1++; s1++;
1934
					s1 += 2;
1926
				} else if (*s1 == '\0') {
1935
				} else if (*s1 == '\0') {
1927
					ast_log(LOG_WARNING, "A matching ']' was not found for '[' in pattern string '%s'\n", extenbuf);
1936
					ast_log(LOG_WARNING, "A matching ']' was not found for '[' in pattern string '%s'\n", extenbuf);
1928
					break;
1937
					break;
1929
				} else {
1938
				} else {
1930
					*s2++ = *s1++;
1939
					*s2++ = *s1++;
[+20] [20] 5 lines
[+20] static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
1936
			specif = strlen(buf);
1945
			specif = strlen(buf);
1937
			qsort(buf, specif, 1, compare_char);
1946
			qsort(buf, specif, 1, compare_char);
1938
			specif <<= 8;
1947
			specif <<= 8;
1939
			specif += buf[0];
1948
			specif += buf[0];
1940
		} else {
1949
		} else {
1941

    
   

   
1942
			if (*s1 == '\\') {
1950
			if (*s1 == '\\') {
1943
				s1++;
1951
				s1++;
1944
				buf[0] = *s1;
1952
				buf[0] = *s1;
1945
			} else {
1953
			} else {
1946
				if (pattern) {
1954
				if (pattern) {
1947
					if (*s1 == 'n') /* make sure n,x,z patterns are canonicalized to N,X,Z */
1955
					if (*s1 == 'n') { /* make sure n,x,z patterns are canonicalized to N,X,Z */
1948
						*s1 = 'N';
1956
						*s1 = 'N';
1949
					else if (*s1 == 'x')
1957
					} else if (*s1 == 'x') {
1950
						*s1 = 'X';
1958
						*s1 = 'X';
1951
					else if (*s1 == 'z')
1959
					} else if (*s1 == 'z') {
1952
						*s1 = 'Z';
1960
						*s1 = 'Z';
1953
				}
1961
					}

    
   
1962
				}
1954
				buf[0] = *s1;
1963
				buf[0] = *s1;
1955
			}
1964
			}
1956
			buf[1] = 0;
1965
			buf[1] = 0;
1957
			specif = 1;
1966
			specif = 1;
1958
		}
1967
		}
1959
		m2 = 0;
1968
		m2 = 0;
1960
		if (already && (m2 = already_in_tree(m1,buf)) && m2->next_char) {
1969
		if (already && (m2 = already_in_tree(m1, buf, pattern)) && m2->next_char) {
1961
			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...
1970
			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...
1962
								  * a shorter pattern might win if the longer one doesn't match */
1971
								a shorter pattern might win if the longer one doesn't match */

    
   
1972
				if (m2->exten) {

    
   
1973
					ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n", m2->exten->exten, e1->exten);

    
   
1974
				}
1963
				m2->exten = e1;
1975
				m2->exten = e1;
1964
				m2->deleted = 0;
1976
				m2->deleted = 0;
1965
			}
1977
			}
1966
			m1 = m2->next_char; /* m1 points to the node to compare against */
1978
			m1 = m2->next_char; /* m1 points to the node to compare against */
1967
			m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
1979
			m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
[+20] [20] 5 lines
[+20] static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
1973
				m1 = m2; /* while m0 stays the same */
1985
				m1 = m2; /* while m0 stays the same */
1974
			} else {
1986
			} else {
1975
				if (findonly) {
1987
				if (findonly) {
1976
					return m1;
1988
					return m1;
1977
				}
1989
				}
1978
				m1 = add_pattern_node(con, m1, buf, pattern, already,specif, m0); /* m1 is the node just added */
1990
				if (!(m1 = add_pattern_node(con, m1, buf, pattern, already,specif, m0))) { /* m1 is the node just added */

    
   
1991
					return NULL;

    
   
1992
				}
1979
				m0 = &m1->next_char;
1993
				m0 = &m1->next_char;
1980
			}
1994
			}
1981

    
   

   
1982
			if (!(*(s1 + 1))) {
1995
			if (!(*(s1 + 1))) {

    
   
1996
				if (m2) {

    
   
1997
					ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n", m2->exten->exten, e1->exten);

    
   
1998
				}
1983
				m1->deleted = 0;
1999
				m1->deleted = 0;
1984
				m1->exten = e1;
2000
				m1->exten = e1;
1985
			}
2001
			}
1986

    
   
2002

   

    
   
2003
			/* The 'already' variable is a mini-optimization designed to make it so that we

    
   
2004
			 * don't have to call already_in_tree when we know it will return false.

    
   
2005
			 */
1987
			already = 0;
2006
			already = 0;
1988
		}
2007
		}
1989
		s1++; /* advance to next char */
2008
		s1++; /* advance to next char */
1990
	}
2009
	}
1991
	return m1;
2010
	return m1;
[+20] [20] 4 lines
[+20] [+] static void create_match_char_tree(struct ast_context *con)
1996
	struct ast_hashtab_iter *t1;
2015
	struct ast_hashtab_iter *t1;
1997
	struct ast_exten *e1;
2016
	struct ast_exten *e1;
1998
#ifdef NEED_DEBUG
2017
#ifdef NEED_DEBUG
1999
	int biggest_bucket, resizes, numobjs, numbucks;
2018
	int biggest_bucket, resizes, numobjs, numbucks;
2000

    
   
2019

   
2001
	ast_log(LOG_DEBUG,"Creating Extension Trie for context %s\n", con->name);
2020
	ast_log(LOG_DEBUG,"Creating Extension Trie for context %s(%p)\n", con->name, con);
2002
	ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
2021
	ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
2003
	ast_log(LOG_DEBUG,"This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
2022
	ast_log(LOG_DEBUG,"This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
2004
			numobjs, numbucks, biggest_bucket, resizes);
2023
			numobjs, numbucks, biggest_bucket, resizes);
2005
#endif
2024
#endif
2006
	t1 = ast_hashtab_start_traversal(con->root_table);
2025
	t1 = ast_hashtab_start_traversal(con->root_table);
[+20] [20] 18 lines
[+20] [+] 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! */
2025
	if (pattern_tree->next_char) {
2044
	if (pattern_tree->next_char) {
2026
		destroy_pattern_tree(pattern_tree->next_char);
2045
		destroy_pattern_tree(pattern_tree->next_char);
2027
		pattern_tree->next_char = 0;
2046
		pattern_tree->next_char = 0;
2028
	}
2047
	}
2029
	pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
2048
	pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
2030
	if (pattern_tree->x) {
2049
	ast_free(pattern_tree);
2031
		free(pattern_tree->x);

   
2032
	}

   
2033
	free(pattern_tree);

   
2034
}
2050
}
2035

    
   
2051

   
2036
/*
2052
/*
2037
 * Special characters used in patterns:
2053
 * Special characters used in patterns:
2038
 *	'_'	underscore is the leading character of a pattern.
2054
 *	'_'	underscore is the leading character of a pattern.
[+20] [20] 448 lines
[+20] [+] struct ast_exten *pbx_find_extension(struct ast_channel *chan,
2487
		struct fake_context item;
2503
		struct fake_context item;
2488

    
   
2504

   
2489
		ast_copy_string(item.name, context, sizeof(item.name));
2505
		ast_copy_string(item.name, context, sizeof(item.name));
2490

    
   
2506

   
2491
		tmp = ast_hashtab_lookup(contexts_table, &item);
2507
		tmp = ast_hashtab_lookup(contexts_table, &item);
2492
#ifdef NOTNOW

   
2493
		tmp = NULL;

   
2494
		while ((tmp = ast_walk_contexts(tmp)) ) {

   
2495
			if (!strcmp(tmp->name, context)) {

   
2496
				break;

   
2497
			}

   
2498
		}

   
2499
#endif

   
2500
		if (!tmp) {
2508
		if (!tmp) {
2501
			return NULL;
2509
			return NULL;
2502
		}
2510
		}
2503
	}
2511
	}
2504

    
   
2512

   
[+20] [20] 172 lines
[+20] struct ast_exten *pbx_find_extension(struct ast_channel *chan,
2677
					q->status = STATUS_NO_LABEL;
2685
					q->status = STATUS_NO_LABEL;
2678
				e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2686
				e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2679
			} else {
2687
			} else {
2680
				e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2688
				e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2681
			}
2689
			}
2682
#ifdef NOTNOW

   
2683
			while ( (e = ast_walk_extension_priorities(eroot, e)) ) {

   
2684
				/* Match label or priority */

   
2685
				if (action == E_FINDLABEL) {

   
2686
					if (q->status < STATUS_NO_LABEL)

   
2687
						q->status = STATUS_NO_LABEL;

   
2688
					if (label && e->label && !strcmp(label, e->label))

   
2689
						break;	/* found it */

   
2690
				} else if (e->priority == priority) {

   
2691
					break;	/* found it */

   
2692
				} /* else keep searching */

   
2693
			}

   
2694
#endif

   
2695
			if (e) {	/* found a valid match */
2690
			if (e) {	/* found a valid match */
2696
				q->status = STATUS_SUCCESS;
2691
				q->status = STATUS_SUCCESS;
2697
				q->foundcontext = context;
2692
				q->foundcontext = context;
2698
				return e;
2693
				return e;
2699
			}
2694
			}
[+20] [20] 1926 lines
[+20] [+] static struct ast_context *find_context_locked(const char *context)
4626
	ast_copy_string(item.name, context, sizeof(item.name));
4621
	ast_copy_string(item.name, context, sizeof(item.name));
4627

    
   
4622

   
4628
	ast_rdlock_contexts();
4623
	ast_rdlock_contexts();
4629
	c = ast_hashtab_lookup(contexts_table,&item);
4624
	c = ast_hashtab_lookup(contexts_table,&item);
4630

    
   
4625

   
4631
#ifdef NOTNOW

   
4632

    
   

   
4633
	while ( (c = ast_walk_contexts(c)) ) {

   
4634
		if (!strcmp(ast_get_context_name(c), context))

   
4635
			return c;

   
4636
	}

   
4637
#endif

   
4638
	if (!c)
4626
	if (!c)
4639
		ast_unlock_contexts();
4627
		ast_unlock_contexts();
4640

    
   
4628

   
4641
	return c;
4629
	return c;
4642
}
4630
}
[+20] [20] 316 lines
[+20] [+] int ast_context_lockmacro(const char *context)
4959
	ast_copy_string(item.name, context, sizeof(item.name));
4947
	ast_copy_string(item.name, context, sizeof(item.name));
4960

    
   
4948

   
4961
	c = ast_hashtab_lookup(contexts_table,&item);
4949
	c = ast_hashtab_lookup(contexts_table,&item);
4962
	if (c)
4950
	if (c)
4963
		ret = 0;
4951
		ret = 0;
4964

    
   

   
4965

    
   

   
4966
#ifdef NOTNOW

   
4967

    
   

   
4968
	while ((c = ast_walk_contexts(c))) {

   
4969
		if (!strcmp(ast_get_context_name(c), context)) {

   
4970
			ret = 0;

   
4971
			break;

   
4972
		}

   
4973
	}

   
4974

    
   

   
4975
#endif

   
4976
	ast_unlock_contexts();
4952
	ast_unlock_contexts();
4977

    
   
4953

   
4978
	/* if we found context, lock macrolock */
4954
	/* if we found context, lock macrolock */
4979
	if (ret == 0) {
4955
	if (ret == 0) {
4980
		ret = ast_mutex_lock(&c->macrolock);
4956
		ret = ast_mutex_lock(&c->macrolock);
[+20] [20] 18 lines
[+20] [+] int ast_context_unlockmacro(const char *context)
4999
	ast_copy_string(item.name, context, sizeof(item.name));
4975
	ast_copy_string(item.name, context, sizeof(item.name));
5000

    
   
4976

   
5001
	c = ast_hashtab_lookup(contexts_table,&item);
4977
	c = ast_hashtab_lookup(contexts_table,&item);
5002
	if (c)
4978
	if (c)
5003
		ret = 0;
4979
		ret = 0;
5004
#ifdef NOTNOW

   
5005

    
   

   
5006
	while ((c = ast_walk_contexts(c))) {

   
5007
		if (!strcmp(ast_get_context_name(c), context)) {

   
5008
			ret = 0;

   
5009
			break;

   
5010
		}

   
5011
	}

   
5012

    
   

   
5013
#endif

   
5014
	ast_unlock_contexts();
4980
	ast_unlock_contexts();
5015

    
   
4981

   
5016
	/* if we found context, unlock macrolock */
4982
	/* if we found context, unlock macrolock */
5017
	if (ret == 0) {
4983
	if (ret == 0) {
5018
		ret = ast_mutex_unlock(&c->macrolock);
4984
		ret = ast_mutex_unlock(&c->macrolock);
[+20] [20] 4521 lines
  1. /trunk/main/pbx.c: Loading...

https://reviewboard.asterisk.org/ runs on a server provided by Digium, Inc. and uses bandwidth donated to the open source Asterisk community by API Digital Communications in Huntsville, AL USA.
Please report problems with this site to asteriskteam@digium.com.