Changeset f446454


Ignore:
Timestamp:
Nov 17, 2008, 3:48:27 PM (9 years ago)
Author:
Nelson Elhage <nelhage@mit.edu>
Branches:
master, debian, release-1.4, release-1.5, release-1.6, release-1.7, release-1.8, release-1.9
Children:
2c09826
Parents:
3381399
Message:
Properly detect only directed cycles in the filter graph when looking
for recursive filters. Fixes #54.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • filterelement.c

    r0504f63 rf446454  
    279279}
    280280
     281static int fe_visiting = 0;
     282static int fe_visited  = 1;
     283
    281284int owl_filterelement_is_toodeep(owl_filter *f, owl_filterelement *fe)
    282285{
    283   int one = 1;
    284   owl_list nodes;
     286  int rv;
    285287  owl_dict filters;
    286   owl_list_create(&nodes);
    287288  owl_dict_create(&filters);
    288  
    289   owl_list_append_element(&nodes, fe);
    290   owl_dict_insert_element(&filters, f->name, &one, NULL);
    291   while(owl_list_get_size(&nodes)) {
    292     fe = owl_list_get_element(&nodes, 0);
    293     owl_list_remove_element(&nodes, 0);
    294     if(fe->left) owl_list_append_element(&nodes, fe->left);
    295     if(fe->right) owl_list_append_element(&nodes, fe->right);
    296     if(fe->match_message == owl_filterelement_match_filter) {
    297       if(owl_dict_find_element(&filters, fe->field)) return 1;
    298       owl_dict_insert_element(&filters, fe->field, &one, NULL);
     289
     290  owl_dict_insert_element(&filters, f->name, &fe_visiting, owl_dict_noop_free);
     291
     292  rv = _owl_filterelement_is_toodeep(fe, &filters);
     293
     294  owl_dict_free_simple(&filters);
     295  return rv;
     296}
     297
     298int _owl_filterelement_is_toodeep(owl_filterelement *fe, owl_dict *seen)
     299{
     300  int rv = 0;
     301  owl_filter *f;
     302
     303  if(fe->match_message == owl_filterelement_match_filter) {
     304    int *nval = owl_dict_find_element(seen, fe->field);
     305    if(nval == &fe_visiting) {
     306      return 1;
     307    } else if (nval == NULL) {
    299308      f = owl_global_get_filter(&g, fe->field);
    300       if(f) owl_list_append_element(&nodes, f->root);
     309      owl_dict_insert_element(seen, fe->field, &fe_visiting, owl_dict_noop_free);
     310      if(f) rv = _owl_filterelement_is_toodeep(f->root, seen);
     311      owl_dict_insert_element(seen, fe->field, &fe_visited, owl_dict_noop_free);
    301312    }
    302   }
    303 
    304   owl_list_free_simple(&nodes);
    305   owl_dict_free_simple(&filters);
    306   return 0;
     313  } else {
     314    if(fe->left)
     315      rv = rv || _owl_filterelement_is_toodeep(fe->left, seen);
     316    if(fe->right)
     317      rv = rv || _owl_filterelement_is_toodeep(fe->right, seen);
     318  }
     319  return rv;
    307320}
    308321
Note: See TracChangeset for help on using the changeset viewer.