Changeset 129e609


Ignore:
Timestamp:
Dec 6, 2009, 8:08:24 PM (10 years ago)
Author:
Nelson Elhage <nelhage@mit.edu>
Branches:
master, 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.
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • functions.c

    r2c48db8 r129e609  
    22492249void owl_function_show_filters(void)
    22502250{
    2251   const owl_list *l;
    22522251  const owl_filter *f;
    2253   int i, j;
     2252  GList *fl;
    22542253  owl_fmtext fm;
    22552254
    22562255  owl_fmtext_init_null(&fm);
    22572256
    2258   l=owl_global_get_filterlist(&g);
    2259   j=owl_list_get_size(l);
    2260 
    22612257  owl_fmtext_append_bold(&fm, "Filters:\n");
    22622258
    2263   for (i=0; i<j; i++) {
    2264     f=owl_list_get_element(l, i);
     2259  for (fl = g.filterlist; fl; fl = g_list_next(fl)) {
     2260    f = fl->data;
    22652261    owl_fmtext_append_normal(&fm, "   ");
    22662262    if (owl_global_get_hascolors(&g)) {
  • global.c

    r6fc40a7 r129e609  
    5050  owl_keys_setup_keymaps(&g->kh);
    5151
    52   owl_list_create(&(g->filterlist));
     52  owl_dict_create(&(g->filters));
     53  g->filterlist = NULL;
    5354  owl_list_create(&(g->puntlist));
    5455  owl_list_create(&(g->messagequeue));
     
    604605
    605606/* filterlist */
    606 
    607 owl_list *owl_global_get_filterlist(owl_global *g) {
    608   return(&(g->filterlist));
    609 }
     607typedef struct _owl_global_filter_ent {         /* noproto */
     608  owl_global *g;
     609  owl_filter *f;
     610} owl_global_filter_ent;
    610611
    611612owl_filter *owl_global_get_filter(const owl_global *g, const char *name) {
    612   int i, j;
    613   owl_filter *f;
    614 
    615   j=owl_list_get_size(&(g->filterlist));
    616   for (i=0; i<j; i++) {
    617     f=owl_list_get_element(&(g->filterlist), i);
    618     if (!strcmp(name, owl_filter_get_name(f))) {
    619       return(f);
    620     }
    621   }
    622   return(NULL);
     613  owl_global_filter_ent *e = owl_dict_find_element(&(g->filters), name);
     614  if (e) return e->f;
     615  return NULL;
     616}
     617
     618static void owl_global_free_filter_ent(void *data) {
     619  owl_global_filter_ent *e = data;
     620  e->g->filterlist = g_list_remove(e->g->filterlist, e->f);
     621  owl_filter_delete(e->f);
     622  owl_free(e);
    623623}
    624624
    625625void owl_global_add_filter(owl_global *g, owl_filter *f) {
    626   owl_list_append_element(&(g->filterlist), f);
     626  owl_global_filter_ent *e = owl_malloc(sizeof *e);
     627  e->g = g;
     628  e->f = f;
     629
     630  owl_dict_insert_element(&(g->filters), owl_filter_get_name(f),
     631                          e, owl_global_free_filter_ent);
     632  g->filterlist = g_list_append(g->filterlist, f);
    627633}
    628634
    629635void owl_global_remove_filter(owl_global *g, const char *name) {
    630   int i, j;
    631   owl_filter *f;
    632 
    633   j=owl_list_get_size(&(g->filterlist));
    634   for (i=0; i<j; i++) {
    635     f=owl_list_get_element(&(g->filterlist), i);
    636     if (!strcmp(name, owl_filter_get_name(f))) {
    637       owl_filter_delete(f);
    638       owl_list_remove_element(&(g->filterlist), i);
    639       break;
    640     }
    641   }
     636  owl_global_filter_ent *e = owl_dict_remove_element(&(g->filters), name);
     637  if (e)
     638    owl_global_free_filter_ent(e);
    642639}
    643640
  • mainwin.c

    rf63a681 r129e609  
    1010{
    1111  owl_message *m;
    12   int i, p, q, lines, isfull, viewsize;
     12  int i, lines, isfull, viewsize;
    1313  int x, y, savey, recwinlines, start;
    1414  int topmsg, curmsg, markedmsgid, fgcolor, bgcolor;
    1515  WINDOW *recwin;
    1616  const owl_view *v;
    17   const owl_list *filtlist;
     17  GList *fl;
    1818  const owl_filter *f;
    1919
     
    7373    fgcolor=OWL_COLOR_DEFAULT;
    7474    bgcolor=OWL_COLOR_DEFAULT;
    75     filtlist=owl_global_get_filterlist(&g);
    76     q=owl_list_get_size(filtlist);
    77     for (p=0; p<q; p++) {
    78       f=owl_list_get_element(filtlist, p);
     75    for (fl = g.filterlist; fl; fl = g_list_next(fl)) {
     76      f = fl->data;
    7977      if ((owl_filter_get_fgcolor(f)!=OWL_COLOR_DEFAULT) ||
    8078          (owl_filter_get_bgcolor(f)!=OWL_COLOR_DEFAULT)) {
  • owl.c

    r6c81223 r129e609  
    176176
    177177  for (i = 0; filters[i].name != NULL; i++)
    178     owl_list_append_element(owl_global_get_filterlist(&g),
    179                             owl_filter_new_fromstring(filters[i].name,
    180                                                       filters[i].desc));
     178    owl_global_add_filter(&g, owl_filter_new_fromstring(filters[i].name,
     179                                                        filters[i].desc));
    181180}
    182181
  • owl.h

    r8df704f r129e609  
    539539  owl_history msghist;          /* outgoing message history */
    540540  owl_keyhandler kh;
    541   owl_list filterlist;
     541  owl_dict filters;
     542  GList *filterlist;
    542543  owl_list puntlist;
    543544  owl_vardict vars;
  • perlglue.xs

    ra01ed7c r129e609  
    326326all_filters()
    327327        PREINIT:
    328                 const owl_list *fl;
    329         CODE:
    330         {
    331                 fl = owl_global_get_filterlist(&g);
    332                 RETVAL = owl_new_av(fl, (SV*(*)(const void*))owl_filter_to_sv);
     328                owl_list fl;
     329        CODE:
     330        {
     331                owl_list_create(&fl);
     332                owl_dict_get_keys(&g.filters, &fl);
     333                RETVAL = owl_new_av(&fl, (SV*(*)(const void*))owl_new_sv);
    333334                sv_2mortal((SV*)RETVAL);
     335                owl_list_free_all(&fl, owl_free);
    334336        }
    335337        OUTPUT:
Note: See TracChangeset for help on using the changeset viewer.