From 0fec0b5c2d20fb505f1b8345d48b5098fe5598f6 Mon Sep 17 00:00:00 2001
From: "cebka@lenovo-laptop" <cebka@lenovo-laptop>
Date: Sun, 28 Feb 2010 16:03:09 +0300
Subject: [PATCH] * Save prefixes in trees

---
 src/plugins/custom/regmark/prefix_tree.c | 48 ++++++++++++++++++------
 src/plugins/custom/regmark/prefix_tree.h |  2 +-
 2 files changed, 37 insertions(+), 13 deletions(-)

diff --git a/src/plugins/custom/regmark/prefix_tree.c b/src/plugins/custom/regmark/prefix_tree.c
index 0e2920616..3af1ae283 100644
--- a/src/plugins/custom/regmark/prefix_tree.c
+++ b/src/plugins/custom/regmark/prefix_tree.c
@@ -25,6 +25,13 @@
 #include "../../../config.h"
 #include "prefix_tree.h"
 
+static gint 
+compare_prefixes (gconstpointer a, gconstpointer b, gpointer unused)
+{
+	const char *s1 = a, *s2 = b;
+
+	return strcmp (s1, s2);
+}
 
 prefix_tree_t* 
 prefix_tree_new (int levels)
@@ -50,6 +57,8 @@ add_string_common (prefix_tree_t *tree, const char *input, int skip_levels, gboo
 	int cur_level = 0, num;
 	prefix_tree_level_t *cur;
 	uintptr_t res = 0;
+	char *prefix, tmp[256];
+	const char *orig = input;
 
 	if (tree == NULL) {
 		return 0;
@@ -59,31 +68,38 @@ add_string_common (prefix_tree_t *tree, const char *input, int skip_levels, gboo
 		cur = &tree->nodes[cur_level];
 		if (*input >= 'A' && *input <= 'Z') {
 			num = *input - 'A';
+			if (cur_level < skip_levels) {
+				continue;
+			}
 			/* Go throught each level and check specified letter */
-			if (cur->leafs[num].data == 0) {
+			if (cur->leafs[num].data == NULL) {
 				/* Create new leaf */
 				if (read_only) {
 					return res;
 				}
 				else {
-					cur->leafs[num].data = 1;
+					/* Create new tree */
+					prefix = g_malloc (cur_level * sizeof (char) + 1);
+					g_strlcpy (prefix, orig, cur_level + 1);
+					cur->leafs[num].data = g_tree_new_full (compare_prefixes, NULL, g_free, NULL);
+					g_tree_insert (cur->leafs[num].data, prefix, GUINT_TO_POINTER (1));
+					return 1;
 				}
 			}
 			else {
 				/* Got some node, so check it */
-				if (cur_level > skip_levels) {
+				g_strlcpy (tmp, orig, MIN (sizeof (tmp), cur_level + 1));
+				if ((res = (uintptr_t)g_tree_lookup (cur->leafs[num].data, tmp)) != 0) {
 					if (! read_only) {
-						cur->leafs[num].data ++;
-					}
-					if (! get_longest) {
-						/* Get maximum after skip */
-						if (res < cur->leafs[num].data) {
-							res = cur->leafs[num].data;
-						}
+						g_tree_insert (cur->leafs[num].data, tmp, GUINT_TO_POINTER (res + 1));
 					}
-					else {
-						res = cur->leafs[num].data;
+					return res + 1;
+				}
+				else {
+					if (! read_only) {
+						g_tree_insert (cur->leafs[num].data, g_strdup (tmp), GUINT_TO_POINTER (1));
 					}
+					return 1;
 				}
 			}
 		}
@@ -121,7 +137,15 @@ check_string_longest (prefix_tree_t *tree, const char *input, int skip_levels)
 void 
 prefix_tree_free (prefix_tree_t *tree)
 {
+	int i, j;
 	if (tree != NULL) {
+		for (i = 0; i < tree->levels; i ++) {
+			for (j = 0; j < LETTERS_NUMBER; j ++) {
+				if (tree->nodes[i].leafs[j].data != NULL) {
+					g_tree_destroy (tree->nodes[i].leafs[j].data);
+				}
+			}
+		}
 		g_free (tree->nodes);
 		g_free (tree);
 	}
diff --git a/src/plugins/custom/regmark/prefix_tree.h b/src/plugins/custom/regmark/prefix_tree.h
index 30580d612..be766f80f 100644
--- a/src/plugins/custom/regmark/prefix_tree.h
+++ b/src/plugins/custom/regmark/prefix_tree.h
@@ -6,7 +6,7 @@
 #define LETTERS_NUMBER 26
 
 typedef struct prefix_tree_leaf_s {
-	uintptr_t data;
+	GTree *data;
 } prefix_tree_leaf_t;
 
 typedef struct prefix_tree_level_s {
-- 
2.39.5