changeset 5247:60983a46700e

[gaim-migrate @ 5618] (22:40:26) Paco-Paco: gaim_find_buddy was an O(n) search through the blist tree, this adds an auxilliary hash to bring that down to O(1) committer: Tailor Script <[e-mail]>

--- a/src/blist.c	Sun Apr 27 22:45:09 2003 +0000
+++ b/src/blist.c	Mon Apr 28 02:41:00 2003 +0000
@@ -65,6 +65,21 @@
 	return gaim_blist_get_last_sibling(node->child);
 }
 
+struct _gaim_hbuddy {
+	char *name;
+	struct gaim_account *account;
+};
+
+static guint _gaim_blist_hbuddy_hash (struct _gaim_hbuddy *hb)
+{
+	return g_str_hash(hb->name);
+}
+
+static guint _gaim_blist_hbuddy_equal (struct _gaim_hbuddy *hb1, struct _gaim_hbuddy *hb2)
+{
+	return ((!strcmp(hb1->name, hb2->name)) && hb1->account == hb2->account);
+}
+
 /*****************************************************************************
  * Public API functions                                                      *
  *****************************************************************************/
@@ -75,6 +90,9 @@
 
 	gbl->ui_ops = gaim_get_blist_ui_ops();
 
+	gbl->buddies = g_hash_table_new ((GHashFunc)_gaim_blist_hbuddy_hash, 
+					 (GEqualFunc)_gaim_blist_hbuddy_equal);
+
 	if (gbl->ui_ops != NULL && gbl->ui_ops->new_list != NULL)
 		gbl->ui_ops->new_list(gbl);
 
@@ -348,6 +366,7 @@
 	GaimBlistNode *n = node, *bnode = (GaimBlistNode*)buddy;
 	struct group *g = group;
 	struct gaim_blist_ui_ops *ops = gaimbuddylist->ui_ops;
+	struct _gaim_hbuddy *hb;
 	gboolean save = FALSE;
 
 	if (!n) {
@@ -396,6 +415,18 @@
 		((GaimBlistNode*)buddy)->parent = (GaimBlistNode*)g;
 	}
 
+	hb = g_malloc(sizeof(struct _gaim_hbuddy));
+	hb->name = g_strdup(normalize(buddy->name));
+	hb->account = buddy->account;
+
+	if (g_hash_table_lookup(gaimbuddylist->buddies, (gpointer)hb)) {
+		/* This guy already exists */
+		g_free(hb->name);
+		g_free(hb);
+	} else {
+		g_hash_table_insert(gaimbuddylist->buddies, (gpointer)hb, (gpointer)buddy);
+	}
+
 	if (ops)
 		ops->update(gaimbuddylist, (GaimBlistNode*)buddy);
 	if (save)
@@ -481,6 +512,8 @@
 
 	GaimBlistNode *gnode, *node = (GaimBlistNode*)buddy;
 	struct group *group;
+	struct _gaim_hbuddy hb, *key;
+	struct buddy *val;
 
 	gnode = node->parent;
 	group = (struct group *)gnode;
@@ -492,6 +525,14 @@
 	if (node->next)
 		node->next->prev = node->prev;
 
+	hb.name = normalize(buddy->name);
+	hb.account = buddy->account;
+	if (g_hash_table_lookup_extended(gaimbuddylist->buddies, &hb, (gpointer *)&key, (gpointer *)&val)) {
+		g_hash_table_remove(gaimbuddylist->buddies, &hb);
+		g_free(key->name);
+		g_free(key);
+	}
+
 	ops->remove(gaimbuddylist, node);
 	g_hash_table_destroy(buddy->settings);
 	g_free(buddy->name);
@@ -579,29 +620,17 @@
 
 struct buddy *gaim_find_buddy(struct gaim_account *account, const char *name)
 {
-	GaimBlistNode *group;
-	GaimBlistNode *buddy;
-	char *norm_name = g_strdup(normalize(name));
+	struct buddy *buddy;
+	struct _gaim_hbuddy hb;
 
 	if (!gaimbuddylist)
 		return NULL;
 
-	group = gaimbuddylist->root;
-	while (group) {
-		buddy = group->child;
-		while (buddy) {
-			if(GAIM_BLIST_NODE_IS_BUDDY(buddy)) {
-				if (!gaim_utf8_strcasecmp(normalize(((struct buddy*)buddy)->name), norm_name) && account == ((struct buddy*)buddy)->account) {
-					g_free(norm_name);
-					return (struct buddy*)buddy;
-				}
-			}
-			buddy = buddy->next;
-		}
-		group = group->next;
-	}
-	g_free(norm_name);
-	return NULL;
+	hb.name = normalize(name);
+	hb.account = account;
+	buddy = g_hash_table_lookup(gaimbuddylist->buddies, &hb);
+
+	return buddy;
 }
 
 struct group *gaim_find_group(const char *name)

--- a/src/blist.h	Sun Apr 27 22:45:09 2003 +0000
+++ b/src/blist.h	Mon Apr 28 02:41:00 2003 +0000
@@ -116,6 +116,7 @@
  */
 struct gaim_buddy_list {
 	GaimBlistNode *root;                    /**< The first node in the buddy list */
+	GHashTable *buddies;			/**< Every buddy in this list */
 	struct gaim_blist_ui_ops *ui_ops;       /**< The UI operations for the buddy list */
 
 	void *ui_data;                          /**< UI-specific data. */

--- a/src/util.c	Sun Apr 27 22:45:09 2003 +0000
+++ b/src/util.c	Mon Apr 28 02:41:00 2003 +0000
@@ -541,6 +541,9 @@
 	tmp = g_utf8_strdown(buf, -1);
 	g_snprintf(buf, sizeof(buf), "%s", tmp);
 	g_free(tmp);
+	tmp = g_utf8_normalize(buf, -1, G_NORMALIZE_DEFAULT);
+	g_snprintf(buf, sizeof(buf), "%s", tmp);
+	g_free(tmp);
 
 	return buf;
 }