Merge "astdb: Improve prefix searches in astdb" into 15

3 files changed, 107 insertions, 30 deletions

diff --git a/include/asterisk/astdb.h b/include/asterisk/astdb.h
index 8a870ae83..383864baf 100644
--- a/include/asterisk/astdb.h
+++ b/include/asterisk/astdb.h
@@ -83,6 +83,16 @@ int ast_db_deltree(const char *family, const char *keytree);
  */
 struct ast_db_entry *ast_db_gettree(const char *family, const char *keytree);
 
+/*!
+ * \brief Get a list of values with the given key prefix
+ *
+ * \param family The family to search under
+ * \param key_prefix The key prefix to search under
+ *
+ * \retval NULL An error occurred
+ */
+struct ast_db_entry *ast_db_gettree_by_prefix(const char *family, const char *key_prefix);
+
 /*! \brief Free structure created by ast_db_gettree() */
 void ast_db_freetree(struct ast_db_entry *entry);
 
diff --git a/main/db.c b/main/db.c
index fa125d749..afaf04341 100644
--- a/main/db.c
+++ b/main/db.c
@@ -127,6 +127,20 @@ DEFINE_SQL_STATEMENT(gettree_all_stmt, "SELECT key, value FROM astdb ORDER BY ke
 DEFINE_SQL_STATEMENT(showkey_stmt, "SELECT key, value FROM astdb WHERE key LIKE '%' || '/' || ? ORDER BY key")
 DEFINE_SQL_STATEMENT(create_astdb_stmt, "CREATE TABLE IF NOT EXISTS astdb(key VARCHAR(256), value VARCHAR(256), PRIMARY KEY(key))")
 
+/* This query begs an explanation:
+ *
+ * First, the parameter binding syntax used here is slightly different then the other
+ * queries in that we use a numbered parameter so that we can bind once and get the same
+ * value substituted multiple times within the executed query.
+ *
+ * Second, the key comparison is being used to find all keys that are lexicographically
+ * greater than the provided key, but less than the provided key with a high (but
+ * invalid) Unicode codepoint appended to it. This will give us all keys in the database
+ * that have 'key' as a prefix and performs much better than the equivalent "LIKE key ||
+ * '%'" operation.
+ */
+DEFINE_SQL_STATEMENT(gettree_prefix_stmt, "SELECT key, value FROM astdb WHERE key > ?1 AND key <= ?1 || X'ffff'")
+
 static int init_stmt(sqlite3_stmt **stmt, const char *sql, size_t len)
 {
 	ast_mutex_lock(&dblock);
@@ -167,6 +181,7 @@ static void clean_statements(void)
 	clean_stmt(&deltree_all_stmt, deltree_all_stmt_sql);
 	clean_stmt(&gettree_stmt, gettree_stmt_sql);
 	clean_stmt(&gettree_all_stmt, gettree_all_stmt_sql);
+	clean_stmt(&gettree_prefix_stmt, gettree_prefix_stmt_sql);
 	clean_stmt(&showkey_stmt, showkey_stmt_sql);
 	clean_stmt(&put_stmt, put_stmt_sql);
 	clean_stmt(&create_astdb_stmt, create_astdb_stmt_sql);
@@ -182,6 +197,7 @@ static int init_statements(void)
 	|| init_stmt(&deltree_all_stmt, deltree_all_stmt_sql, sizeof(deltree_all_stmt_sql))
 	|| init_stmt(&gettree_stmt, gettree_stmt_sql, sizeof(gettree_stmt_sql))
 	|| init_stmt(&gettree_all_stmt, gettree_all_stmt_sql, sizeof(gettree_all_stmt_sql))
+	|| init_stmt(&gettree_prefix_stmt, gettree_prefix_stmt_sql, sizeof(gettree_prefix_stmt_sql))
 	|| init_stmt(&showkey_stmt, showkey_stmt_sql, sizeof(showkey_stmt_sql))
 	|| init_stmt(&put_stmt, put_stmt_sql, sizeof(put_stmt_sql));
 }
@@ -473,19 +489,64 @@ int ast_db_deltree(const char *family, const char *keytree)
 	return res;
 }
 
+static struct ast_db_entry *db_gettree_common(sqlite3_stmt *stmt)
+{
+	struct ast_db_entry *head = NULL, *prev = NULL, *cur;
+
+	while (sqlite3_step(stmt) == SQLITE_ROW) {
+		const char *key, *value;
+		size_t key_len, value_len;
+
+		key   = (const char *) sqlite3_column_text(stmt, 0);
+		value = (const char *) sqlite3_column_text(stmt, 1);
+
+		if (!key || !value) {
+			break;
+		}
+
+		key_len = strlen(key);
+		value_len = strlen(value);
+
+		cur = ast_malloc(sizeof(*cur) + key_len + value_len + 2);
+		if (!cur) {
+			break;
+		}
+
+		cur->next = NULL;
+		cur->key = cur->data + value_len + 1;
+		memcpy(cur->data, value, value_len + 1);
+		memcpy(cur->key, key, key_len + 1);
+
+		if (prev) {
+			prev->next = cur;
+		} else {
+			head = cur;
+		}
+		prev = cur;
+	}
+
+	return head;
+}
+
 struct ast_db_entry *ast_db_gettree(const char *family, const char *keytree)
 {
 	char prefix[MAX_DB_FIELD];
 	sqlite3_stmt *stmt = gettree_stmt;
-	struct ast_db_entry *cur, *last = NULL, *ret = NULL;
+	size_t res = 0;
+	struct ast_db_entry *ret;
 
 	if (!ast_strlen_zero(family)) {
 		if (!ast_strlen_zero(keytree)) {
 			/* Family and key tree */
-			snprintf(prefix, sizeof(prefix), "/%s/%s", family, keytree);
+			res = snprintf(prefix, sizeof(prefix), "/%s/%s", family, keytree);
 		} else {
 			/* Family only */
-			snprintf(prefix, sizeof(prefix), "/%s", family);
+			res = snprintf(prefix, sizeof(prefix), "/%s", family);
+		}
+
+		if (res >= sizeof(prefix)) {
+			ast_log(LOG_WARNING, "Requested prefix is too long: %s\n", keytree);
+			return NULL;
 		}
 	} else {
 		prefix[0] = '\0';
@@ -493,41 +554,47 @@ struct ast_db_entry *ast_db_gettree(const char *family, const char *keytree)
 	}
 
 	ast_mutex_lock(&dblock);
-	if (!ast_strlen_zero(prefix) && (sqlite3_bind_text(stmt, 1, prefix, -1, SQLITE_STATIC) != SQLITE_OK)) {
-		ast_log(LOG_WARNING, "Could bind %s to stmt: %s\n", prefix, sqlite3_errmsg(astdb));
+	if (res && (sqlite3_bind_text(stmt, 1, prefix, res, SQLITE_STATIC) != SQLITE_OK)) {
+		ast_log(LOG_WARNING, "Could not bind %s to stmt: %s\n", prefix, sqlite3_errmsg(astdb));
 		sqlite3_reset(stmt);
 		ast_mutex_unlock(&dblock);
 		return NULL;
 	}
 
-	while (sqlite3_step(stmt) == SQLITE_ROW) {
-		const char *key_s, *value_s;
-		if (!(key_s = (const char *) sqlite3_column_text(stmt, 0))) {
-			break;
-		}
-		if (!(value_s = (const char *) sqlite3_column_text(stmt, 1))) {
-			break;
-		}
-		if (!(cur = ast_malloc(sizeof(*cur) + strlen(key_s) + strlen(value_s) + 2))) {
-			break;
-		}
-		cur->next = NULL;
-		cur->key = cur->data + strlen(value_s) + 1;
-		strcpy(cur->data, value_s);
-		strcpy(cur->key, key_s);
-		if (last) {
-			last->next = cur;
-		} else {
-			ret = cur;
-		}
-		last = cur;
-	}
+	ret = db_gettree_common(stmt);
 	sqlite3_reset(stmt);
 	ast_mutex_unlock(&dblock);
 
 	return ret;
 }
 
+struct ast_db_entry *ast_db_gettree_by_prefix(const char *family, const char *key_prefix)
+{
+	char prefix[MAX_DB_FIELD];
+	size_t res;
+	struct ast_db_entry *ret;
+
+	res = snprintf(prefix, sizeof(prefix), "/%s/%s", family, key_prefix);
+	if (res >= sizeof(prefix)) {
+		ast_log(LOG_WARNING, "Requested key prefix is too long: %s\n", key_prefix);
+		return NULL;
+	}
+
+	ast_mutex_lock(&dblock);
+	if (sqlite3_bind_text(gettree_prefix_stmt, 1, prefix, res, SQLITE_STATIC) != SQLITE_OK) {
+		ast_log(LOG_WARNING, "Could not bind %s to stmt: %s\n", prefix, sqlite3_errmsg(astdb));
+		sqlite3_reset(gettree_prefix_stmt);
+		ast_mutex_unlock(&dblock);
+		return NULL;
+	}
+
+	ret = db_gettree_common(gettree_prefix_stmt);
+	sqlite3_reset(gettree_prefix_stmt);
+	ast_mutex_unlock(&dblock);
+
+	return ret;
+}
+
 void ast_db_freetree(struct ast_db_entry *dbe)
 {
 	struct ast_db_entry *last;
diff --git a/res/res_sorcery_astdb.c b/res/res_sorcery_astdb.c
index 8b93b57ba..87823be0d 100644
--- a/res/res_sorcery_astdb.c
+++ b/res/res_sorcery_astdb.c
@@ -334,14 +334,14 @@ static void sorcery_astdb_retrieve_prefix(const struct ast_sorcery *sorcery, voi
 	const char *family_prefix = data;
 	size_t family_len = strlen(family_prefix) + strlen(type) + 1; /* +1 for slash delimiter */
 	char family[family_len + 1];
-	char tree[prefix_len + sizeof("%")];
+	char tree[prefix_len + 1];
 	RAII_VAR(struct ast_db_entry *, entries, NULL, ast_db_freetree);
 	struct ast_db_entry *entry;
 
-	snprintf(tree, sizeof(tree), "%.*s%%", (int) prefix_len, prefix);
+	snprintf(tree, sizeof(tree), "%.*s", (int) prefix_len, prefix);
 	snprintf(family, sizeof(family), "%s/%s", family_prefix, type);
 
-	if (!(entries = ast_db_gettree(family, tree))) {
+	if (!(entries = ast_db_gettree_by_prefix(family, tree))) {
 		return;
 	}