[asterisk-dev] [PATCH] Sort patterns for termination

[Jan Engelhardt]

Hi,


there's a case with the use of pbx_realtime.so where multiple patterns
(_0. and _0174. here) can match a call like "017412345678".
In this case, it is preferable to match with _0174. instead of _0.

mysql> SELECT * FROM config_extensions WHERE
       context="TERMINATION" order by exten;
+------+-------------+--------+----------+------------+-
| id   | context     | exten  | priority | app        | ...
+------+-------------+--------+----------+------------+-
| 7502 | TERMINATION | _0.    |        3 | Congestion | ...
| 7501 | TERMINATION | _0.    |        2 | Busy       |
| 7500 | TERMINATION | _0.    |        1 | Dial       | ...
| 7505 | TERMINATION | _0174. |        3 | Congestion |
| 7504 | TERMINATION | _0174. |        2 | Busy       | ...
| 7503 | TERMINATION | _0174. |        1 | Dial       |
+------+-------------+--------+----------+------------+-

To actually do this, the patterns need to be sorted, which the patch below
does.
This is a follow-up to http://bugs.digium.com/view.php?id=10109
(- I am not either interested in signing up for yet another account.)[1]


	Jan
--
[1] https://lists.linux-foundation.org/pipermail/desktop_architects/2007-February/001129.html

diff -dpru asterisk-1.2.19~/config.c asterisk-1.2.19/config.c
--- asterisk-1.2.19~/config.c	2007-06-15 01:21:45.000000000 +0200
+++ asterisk-1.2.19/config.c	2007-07-03 22:23:04.207821000 +0200
@@ -24,6 +24,7 @@
  * See README.realtime
  */
 
+#include <ctype.h>
 #include <stdio.h>
 #include <unistd.h>
 #include <stdlib.h>
@@ -96,6 +97,124 @@ struct ast_config {
 	int max_include_level;
 };
 
+static int ast_regex_compare(const void *pa, const void *pb)
+{
+	const struct ast_category *const *qa = pa;
+	const struct ast_category *const *qb = pb;
+	const char *a = (*qa)->name;
+	const char *b = (*qb)->name;
+
+	/* Ruleset: long non-regex < short non-regex < regex */
+	if (*a != '_' && *b != '_')
+		return strlen(b) - strlen(a);
+	if (*a != '_' && *b == '_')
+		return -1;
+	if (*a == '_' && *b != '_')
+		return 1;
+
+	++a;
+	++b;
+
+	/* Ruleset: digit < '[' <= '.' < '\0' */
+	while (*a != '\0' && *b != '\0') {
+		if (isdigit(*a)) {
+			switch (*b) {
+				case '[': return -1;
+				case '.': return -1;
+				case '\0': return -1;
+			}
+		} else if (*a == '[') {
+			if (isdigit(*b)) {
+				return 1;
+			} else if (*b == '[') {
+				a = strchr(a, ']');
+				b = strchr(b, ']');
+				if (a == NULL || b == NULL) {
+					ast_log(LOG_DEBUG, "Invalid regex\n");
+					return 0;
+				}
+				--a;
+				--b;
+			} else if (*b == '.') {
+				a = strchr(a, ']');
+				if (a == NULL) {
+					ast_log(LOG_DEBUG, "Invalid regex\n");
+					return 0;
+				}
+				--a;
+			} else if (*b == '\0') {
+				return -1;
+			}
+		} else if (*a == '.') {
+			if (isdigit(*b)) {
+				return 1;
+			} else if (*b == '[') {
+				b = strchr(b, ']');
+				if (b == NULL) {
+					ast_log(LOG_DEBUG, "Invalid regex\n");
+					return 0;
+				}
+				--b;
+			} else if (*b == '\0') {
+				return -1;
+			}
+		} else if (*a == '\0') {
+			return 1;
+		}
+		++a;
+		++b;
+	}
+
+	return 0;
+}
+
+static struct ast_category *sort_by_name(struct ast_category *eroot)
+{
+	struct ast_category **linear;
+	struct ast_category *wp, *ret;
+	unsigned int i, max;
+
+	/* Count nodes */
+	for (max = 0, wp = eroot; wp != NULL; wp = wp->next)
+		++max;
+
+	/* Decompose linked list into flat array */
+	linear = malloc(sizeof(struct ast_category *) * max);
+	if (linear == NULL) {
+		/* oder wie man am schönsten asterisk not-beendet */
+		abort();
+	}
+
+	for (i = 0, wp = eroot; wp != NULL; wp = wp->next) {
+		if (wp == NULL)
+			fprintf(stderr, "Damnit, should never happen\n");
+		linear[i++] = wp;
+	}
+
+	fprintf(stderr, "Something i=%u max=%u\n", i, max);
+	qsort(linear, i, sizeof(struct ast_category *), ast_regex_compare);
+
+	/* Rebuild linked list from sorted array */
+	for (wp = linear[0], i = 0; i < max - 1; ++i) {
+		wp->next = linear[i+1];
+		wp       = wp->next;
+	}
+
+	wp->next = NULL;
+	ret      = linear[0];
+	free(linear);
+	return ret;
+}
+
+void ast_config_sort_by_name(struct ast_config *cfg)
+{
+	if (cfg == NULL || cfg->root == NULL || cfg->root->name == NULL ||
+	    cfg->root->next == NULL)
+		return;
+	cfg->root = sort_by_name(cfg->root);
+	return;
+}
+
 struct ast_variable *ast_variable_new(const char *name, const char *value) 
 {
 	struct ast_variable *variable;
diff -dpru asterisk-1.2.19~/include/asterisk/config.h asterisk-1.2.19/include/asterisk/config.h
--- asterisk-1.2.19~/include/asterisk/config.h	2006-11-15 18:56:42.000000000 +0100
+++ asterisk-1.2.19/include/asterisk/config.h	2007-07-03 20:19:32.137821000 +0200
@@ -59,6 +59,8 @@ struct ast_config_engine {
 	struct ast_config_engine *next;
 };
 
+void ast_config_sort_by_name(struct ast_config *);
+
 /*! \brief Load a config file 
  * \param filename path of file to open.  If no preceding '/' character, path is considered relative to AST_CONFIG_DIR
  * Create a config structure from a given configuration file.
diff -dpru asterisk-1.2.19~/pbx/pbx_realtime.c asterisk-1.2.19/pbx/pbx_realtime.c
--- asterisk-1.2.19~/pbx/pbx_realtime.c	2005-11-29 19:24:39.000000000 +0100
+++ asterisk-1.2.19/pbx/pbx_realtime.c	2007-07-03 20:20:20.977821000 +0200
@@ -133,6 +133,8 @@ static struct ast_variable *realtime_swi
 	if (!var) {
 		cfg = ast_load_realtime_multientry(table, "exten LIKE", "\\_%", "context", context, "priority", pri, NULL);	
 		if (cfg) {
+			ast_config_sort_by_name(cfg);
+
 			char *cat = ast_category_browse(cfg, NULL);
 
 			while(cat) {