From bf89f70ca395a7e46b21b73e54caee1456958b79 Mon Sep 17 00:00:00 2001
From: Lucas De Marchi <lucas.demarchi@profusion.mobi>
Date: Fri, 2 Dec 2011 18:23:36 -0200
Subject: [PATCH] index: mmap: add support for seaching with wildcards

Almost a clean copy & paste from the previous implementation.
---
 libkmod/libkmod-index.c | 131 ++++++++++++++++++++++++++++++++++++++++++++++++
 libkmod/libkmod-index.h |   1 +
 2 files changed, 132 insertions(+)

diff --git a/libkmod/libkmod-index.c b/libkmod/libkmod-index.c
index 8df0f71..e39e409 100644
--- a/libkmod/libkmod-index.c
+++ b/libkmod/libkmod-index.c
@@ -774,3 +774,134 @@ char *index_mm_search(struct index_mm *idx, const char *key)
 
 	return value;
 }
+
+/* Level 4: add all the values from a matching node */
+static void index_mm_searchwild_allvalues(struct index_mm_node *node,
+						struct index_value **out)
+{
+	struct index_value *v;
+
+	for (v = node->values; v != NULL; v = v->next)
+		add_value(out, v->value, v->priority);
+
+	index_mm_free_node(node);
+}
+
+/*
+ * Level 3: traverse a sub-keyspace which starts with a wildcard,
+ * looking for matches.
+ */
+static void index_mm_searchwild_all(struct index_mm_node *node, int j,
+					  struct buffer *buf,
+					  const char *subkey,
+					  struct index_value **out)
+{
+	int pushed = 0;
+	int ch;
+
+	while (node->prefix[j]) {
+		ch = node->prefix[j];
+
+		buf_pushchar(buf, ch);
+		pushed++;
+		j++;
+	}
+
+	for (ch = node->first; ch <= node->last; ch++) {
+		struct index_mm_node *child = index_mm_readchild(node, ch);
+
+		if (!child)
+			continue;
+
+		buf_pushchar(buf, ch);
+		index_mm_searchwild_all(child, 0, buf, subkey, out);
+		buf_popchar(buf);
+	}
+
+	if (node->values) {
+		if (fnmatch(buf_str(buf), subkey, 0) == 0)
+			index_mm_searchwild_allvalues(node, out);
+	} else {
+		index_mm_free_node(node);
+	}
+
+	buf_popchars(buf, pushed);
+}
+
+/* Level 2: descend the tree (until we hit a wildcard) */
+static void index_mm_searchwild_node(struct index_mm_node *node,
+					   struct buffer *buf,
+					   const char *key, int i,
+					   struct index_value **out)
+{
+	struct index_mm_node *child;
+	int j;
+	int ch;
+
+	while(node) {
+		for (j = 0; node->prefix[j]; j++) {
+			ch = node->prefix[j];
+
+			if (ch == '*' || ch == '?' || ch == '[') {
+				index_mm_searchwild_all(node, j, buf,
+						      &key[i+j], out);
+				return;
+			}
+
+			if (ch != key[i+j]) {
+				index_mm_free_node(node);
+				return;
+			}
+		}
+
+		i += j;
+
+		child = index_mm_readchild(node, '*');
+		if (child) {
+			buf_pushchar(buf, '*');
+			index_mm_searchwild_all(child, 0, buf, &key[i], out);
+			buf_popchar(buf);
+		}
+
+		child = index_mm_readchild(node, '?');
+		if (child) {
+			buf_pushchar(buf, '?');
+			index_mm_searchwild_all(child, 0, buf, &key[i], out);
+			buf_popchar(buf);
+		}
+
+		child = index_mm_readchild(node, '[');
+		if (child) {
+			buf_pushchar(buf, '[');
+			index_mm_searchwild_all(child, 0, buf, &key[i], out);
+			buf_popchar(buf);
+		}
+
+		if (key[i] == '\0') {
+			index_mm_searchwild_allvalues(node, out);
+
+			return;
+		}
+
+		child = index_mm_readchild(node, key[i]);
+		index_mm_free_node(node);
+		node = child;
+		i++;
+	}
+}
+
+/*
+ * Search the index for a key.  The index may contain wildcards.
+ *
+ * Returns a list of all the values of matching keys.
+ */
+struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key)
+{
+	struct index_mm_node *root = index_mm_readroot(idx);
+	struct buffer *buf = buf_create();
+	struct index_value *out = NULL;
+
+	index_mm_searchwild_node(root, buf, key, 0, &out);
+	buf_destroy(buf);
+	return out;
+}
diff --git a/libkmod/libkmod-index.h b/libkmod/libkmod-index.h
index 9fb96e3..641d69b 100644
--- a/libkmod/libkmod-index.h
+++ b/libkmod/libkmod-index.h
@@ -167,5 +167,6 @@ struct index_mm;
 struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename);
 void index_mm_close(struct index_mm *index);
 char *index_mm_search(struct index_mm *idx, const char *key);
+struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key);
 
 #endif
-- 
2.7.4