Changeset 129e609 for global.c

Timestamp:

Dec 6, 2009, 8:08:24 PM (15 years ago)

Author:

Nelson Elhage <nelhage@mit.edu>

Branches:

master, release-1.10, release-1.5, release-1.6, release-1.7, release-1.8, release-1.9

Children:

bafbba1

Parents:

2c48db8

git-author:

Nelson Elhage <nelhage@mit.edu> (12/02/09 22:09:13)

git-committer:

Nelson Elhage <nelhage@mit.edu> (12/06/09 20:08:24)

Message:

Use a owl_dict to store the list of filters.

Cathy Zhang reported that narrowing to filters that reference other
filters is significantly slower than narrowing to filters that
don't. The culprit is almost certainly the linear lookup of filters by
name, which we currently do on each filter evaluation.

Switch to using an owl_dict, which will now do a binary search over
the filter list. We could potentially get this even faster by caching
the owl_filter itself inside the owl_filterelement, and invalidating
it somehow on filter redefinition, but we can save that sort of
cleverness for later, if necessary.

We also store the filters in a linked list, in order to preserve the
ability to traverse them in order, for ":show filters" and for
coloring.

File:

• global.c (modified) (2 diffs)

global.c

@@ -50 +50 @@
   owl_keys_setup_keymaps(&g->kh);
 
-  owl_list_create(&(g->filterlist));
+  owl_dict_create(&(g->filters));
+  g->filterlist = NULL;
   owl_list_create(&(g->puntlist));
   owl_list_create(&(g->messagequeue));
@@ -604 +605 @@
 
 /* filterlist */
-
-owl_list *owl_global_get_filterlist(owl_global *g) {
-  return(&(g->filterlist));
-}
+typedef struct _owl_global_filter_ent {         /* noproto */
+  owl_global *g;
+  owl_filter *f;
+} owl_global_filter_ent;
 
 owl_filter *owl_global_get_filter(const owl_global *g, const char *name) {
-  int i, j;
-  owl_filter *f;
-
-  j=owl_list_get_size(&(g->filterlist));
-  for (i=0; i<j; i++) {
-    f=owl_list_get_element(&(g->filterlist), i);
-    if (!strcmp(name, owl_filter_get_name(f))) {
-      return(f);
-    }
-  }
-  return(NULL);
+  owl_global_filter_ent *e = owl_dict_find_element(&(g->filters), name);
+  if (e) return e->f;
+  return NULL;
+}
+
+static void owl_global_free_filter_ent(void *data) {
+  owl_global_filter_ent *e = data;
+  e->g->filterlist = g_list_remove(e->g->filterlist, e->f);
+  owl_filter_delete(e->f);
+  owl_free(e);
 }
 
 void owl_global_add_filter(owl_global *g, owl_filter *f) {
-  owl_list_append_element(&(g->filterlist), f);
+  owl_global_filter_ent *e = owl_malloc(sizeof *e);
+  e->g = g;
+  e->f = f;
+
+  owl_dict_insert_element(&(g->filters), owl_filter_get_name(f),
+                          e, owl_global_free_filter_ent);
+  g->filterlist = g_list_append(g->filterlist, f);
 }
 
 void owl_global_remove_filter(owl_global *g, const char *name) {
-  int i, j;
-  owl_filter *f;
-
-  j=owl_list_get_size(&(g->filterlist));
-  for (i=0; i<j; i++) {
-    f=owl_list_get_element(&(g->filterlist), i);
-    if (!strcmp(name, owl_filter_get_name(f))) {
-      owl_filter_delete(f);
-      owl_list_remove_element(&(g->filterlist), i);
-      break;
-    }
-  }
+  owl_global_filter_ent *e = owl_dict_remove_element(&(g->filters), name);
+  if (e)
+    owl_global_free_filter_ent(e);
 }