Add threading support.

4 files changed, 146 insertions, 92 deletions

diff --git a/config/config.def.c b/config/config.def.c
index 1681e997..87a371e0 100644
--- a/config/config.def.c
+++ b/config/config.def.c
@@ -148,4 +148,5 @@ Settings config = {
     .fullscreen        = FALSE,
     .fake_transparency = FALSE,
     .dpi               =                                        -1,
+    .threads           =                                         1,
 };
diff --git a/include/rofi.h b/include/rofi.h
index e1580b20..a767fb7a 100644
--- a/include/rofi.h
+++ b/include/rofi.h
@@ -252,6 +252,8 @@ typedef struct _Settings
     unsigned int   fake_transparency;
     /** dpi */
     int            dpi;
+    /** Number threads (1 to disable) */
+    unsigned int   threads;
 } Settings;
 
 /** Global Settings structure. */
diff --git a/source/rofi.c b/source/rofi.c
index 7c142fa2..21fc6088 100644
--- a/source/rofi.c
+++ b/source/rofi.c
@@ -705,24 +705,74 @@ static void menu_mouse_navigation ( MenuState *state, XButtonEvent *xbe )
     }
 }
 
+typedef struct
+{
+    MenuState    *state;
+    char         **tokens;
+    unsigned int start;
+    unsigned int stop;
+    unsigned int count;
+}thread_state;
+
+static gpointer filter_elements ( gpointer data )
+{
+    thread_state *t = (thread_state *) data;
+    // input changed
+    for ( unsigned int i = t->start; i < t->stop; i++ ) {
+        int match = t->state->sw->token_match ( t->tokens,
+                                                t->state->lines[i],
+                                                t->state->lines_not_ascii[i],
+                                                config.case_sensitive,
+                                                i,
+                                                t->state->sw );
+
+        // If each token was matched, add it to list.
+        if ( match ) {
+            t->state->line_map[t->start + t->count] = i;
+            if ( config.levenshtein_sort ) {
+                t->state->distance[i] = levenshtein ( t->state->text->text, t->state->lines[i] );
+            }
+            t->count++;
+        }
+    }
+    return 0;
+}
+
 static void menu_refilter ( MenuState *state )
 {
     if ( strlen ( state->text->text ) > 0 ) {
         unsigned int j        = 0;
         char         **tokens = tokenize ( state->text->text, config.case_sensitive );
-
-        // input changed
-        for ( unsigned int i = 0; i < state->num_lines; i++ ) {
-            int match = state->sw->token_match ( tokens, state->lines[i], state->lines_not_ascii[i], config.case_sensitive, i, state->sw );
-
-            // If each token was matched, add it to list.
-            if ( match ) {
-                state->line_map[j] = i;
-                if ( config.levenshtein_sort ) {
-                    state->distance[i] = levenshtein ( state->text->text, state->lines[i] );
-                }
-                j++;
+        /**
+         * On long lists it can be beneficial to parallelize.
+         * If number of threads is 1, no thread is spawn.
+         * If number of threads > 1 and there are enough (> 20000) items, spawn threads.
+         * For large lists with 8 threads I see a factor three speedup of the whole function.
+         */
+        unsigned int nt = MIN ( state->num_lines / 1000, config.threads );
+        thread_state states[nt];
+        GThread      *threads[nt];
+        unsigned int steps = ( state->num_lines + nt ) / nt;
+        for ( unsigned int i = 0; i < nt; i++ ) {
+            states[i].state  = state;
+            states[i].tokens = tokens;
+            states[i].start  = i * steps;
+            states[i].stop   = MIN ( state->num_lines, ( i + 1 ) * steps );
+            states[i].count  = 0;
+            if ( i > 0 ) {
+                threads[i] = g_thread_new ( NULL, filter_elements, &( states[i] ) );
+            }
+        }
+        // Run one in this thread.
+        filter_elements ( &states[0] );
+        for ( unsigned int i = 1; i < nt; i++ ) {
+            g_thread_join ( threads[i] );
+        }
+        for ( unsigned int i = 0; i < nt; i++ ) {
+            if ( j != states[i].start ) {
+                memcpy ( &( state->line_map[j] ), &( state->line_map[states[i].start] ), sizeof ( unsigned int ) * ( states[i].count ) );
             }
+            j += states[i].count;
         }
         if ( config.levenshtein_sort ) {
             g_qsort_with_data ( state->line_map, j, sizeof ( int ), lev_sort, state->distance );
diff --git a/source/xrmoptions.c b/source/xrmoptions.c
index c0ec7aef..b3898df0 100644
--- a/source/xrmoptions.c
+++ b/source/xrmoptions.c
@@ -55,88 +55,89 @@ typedef struct
  * Currently supports string, boolean and number (signed and unsigned).
  */
 static XrmOption xrmOptions[] = {
-    { xrm_String,  "switchers",            { .str  = &config.switchers         }, NULL, ""                                            },
-    { xrm_String,  "modi",                 { .str  = &config.switchers         }, NULL, "Enabled modi"                                },
-    { xrm_Number,  "opacity",              { .num  = &config.window_opacity    }, NULL, "Window opacity"                              },
-    { xrm_SNumber, "width",                { .snum = &config.menu_width        }, NULL, "Window width"                                },
-    { xrm_Number,  "lines",                { .num  = &config.menu_lines        }, NULL, "Number of lines"                             },
-    { xrm_Number,  "columns",              { .num  = &config.menu_columns      }, NULL, "Number of columns"                           },
-
-    { xrm_String,  "font",                 { .str  = &config.menu_font         }, NULL, "Font to use"                                 },
+    { xrm_String,  "switchers",            { .str  = &config.switchers          }, NULL, ""                                            },
+    { xrm_String,  "modi",                 { .str  = &config.switchers          }, NULL, "Enabled modi"                                },
+    { xrm_Number,  "opacity",              { .num  = &config.window_opacity     }, NULL, "Window opacity"                              },
+    { xrm_SNumber, "width",                { .snum = &config.menu_width         }, NULL, "Window width"                                },
+    { xrm_Number,  "lines",                { .num  = &config.menu_lines         }, NULL, "Number of lines"                             },
+    { xrm_Number,  "columns",              { .num  = &config.menu_columns       }, NULL, "Number of columns"                           },
+
+    { xrm_String,  "font",                 { .str  = &config.menu_font          }, NULL, "Font to use"                                 },
     /* Foreground color */
-    { xrm_String,  "foreground",           { .str  = &config.menu_fg           }, NULL, ""                                            },
-    { xrm_String,  "fg",                   { .str  = &config.menu_fg           }, NULL, "Foreground color"                            },
-    { xrm_String,  "background",           { .str  = &config.menu_bg           }, NULL, ""                                            },
-    { xrm_String,  "bg",                   { .str  = &config.menu_bg           }, NULL, "Background color"                            },
-
-    { xrm_String,  "fg-active",            { .str  = &config.menu_fg_active    }, NULL, "Foreground color for active row"             },
-    { xrm_String,  "fg-urgent",            { .str  = &config.menu_fg_urgent    }, NULL, "Foreground color for urgent row"             },
-    { xrm_String,  "hlfg-active",          { .str  = &config.menu_hlfg_active  }, NULL, "Foreground color for highlighted active row" },
-    { xrm_String,  "hlfg-urgent",          { .str  = &config.menu_hlfg_urgent  }, NULL, "Foreground color for highlighted urgent row" },
-
-    { xrm_String,  "bg-active",            { .str  = &config.menu_bg_active    }, NULL, "Background color for active row"             },
-    { xrm_String,  "bg-urgent",            { .str  = &config.menu_bg_urgent    }, NULL, "Background color for urgent row"             },
-    { xrm_String,  "hlbg-active",          { .str  = &config.menu_hlbg_active  }, NULL, "Background color for highlighted active row" },
-    { xrm_String,  "hlbg-urgent",          { .str  = &config.menu_hlbg_urgent  }, NULL, "Background color for highlighted urgent row" },
-
-    { xrm_String,  "background-alternate", { .str  = &config.menu_bg_alt       }, NULL, ""                                            },
-    { xrm_String,  "bgalt",                { .str  = &config.menu_bg_alt       }, NULL, "Background color for alternating row"        },
-
-    { xrm_String,  "highlightfg",          { .str  = &config.menu_hlfg         }, NULL, ""                                            },
-    { xrm_String,  "hlfg",                 { .str  = &config.menu_hlfg         }, NULL, "Foreground color for highlighted row"        },
-
-    { xrm_String,  "highlightbg",          { .str  = &config.menu_hlbg         }, NULL, ""                                            },
-    { xrm_String,  "hlbg",                 { .str  = &config.menu_hlbg         }, NULL, "Background color for highlighted row"        },
-
-    { xrm_String,  "bordercolor",          { .str  = &config.menu_bc           }, NULL, ""                                            },
-    { xrm_String,  "bc",                   { .str  = &config.menu_bc           }, NULL, "Border color"                                },
-    { xrm_Boolean, "color-enabled",        { .num  = &config.color_enabled     }, NULL, "Use extended color scheme"                   },
-    { xrm_String,  "color-normal",         { .str  = &config.color_normal      }, NULL, "Color scheme for normal row"                 },
-    { xrm_String,  "color-urgent",         { .str  = &config.color_urgent      }, NULL, "Color scheme for urgent row"                 },
-    { xrm_String,  "color-active",         { .str  = &config.color_active      }, NULL, "Color scheme for active row"                 },
-    { xrm_String,  "color-window",         { .str  = &config.color_window      }, NULL, "Color scheme window"                         },
-
-    { xrm_Number,  "borderwidth",          { .num  = &config.menu_bw           }, NULL, ""                                            },
-    { xrm_Number,  "bw",                   { .num  = &config.menu_bw           }, NULL, "Border width"                                },
-
-    { xrm_Number,  "location",             { .num  = &config.location          }, NULL, "Location on screen"                          },
-
-    { xrm_Number,  "padding",              { .num  = &config.padding           }, NULL, "Padding"                                     },
-    { xrm_SNumber, "yoffset",              { .snum = &config.y_offset          }, NULL, "Y-offset relative to location"               },
-    { xrm_SNumber, "xoffset",              { .snum = &config.x_offset          }, NULL, "X-offset relative to location"               },
-    { xrm_Boolean, "fixed-num-lines",      { .num  = &config.fixed_num_lines   }, NULL, "Always show number of lines"                 },
-
-    { xrm_String,  "terminal",             { .str  = &config.terminal_emulator }, NULL, "Terminal to use"                             },
-    { xrm_String,  "ssh-client",           { .str  = &config.ssh_client        }, NULL, "Ssh client to use"                           },
-    { xrm_String,  "ssh-command",          { .str  = &config.ssh_command       }, NULL, "Ssh command to execute"                      },
-    { xrm_String,  "run-command",          { .str  = &config.run_command       }, NULL, "Run command to execute"                      },
-    { xrm_String,  "run-list-command",     { .str  = &config.run_list_command  }, NULL, "Command to get extra run targets"            },
-    { xrm_String,  "run-shell-command",    { .str  = &config.run_shell_command }, NULL, "Run command to execute that runs in shell"   },
-
-    { xrm_Boolean, "disable-history",      { .num  = &config.disable_history   }, NULL, "Disable history in run/ssh"                  },
-    { xrm_Boolean, "levenshtein-sort",     { .num  = &config.levenshtein_sort  }, NULL, "Use levenshtein sorting"                     },
-    { xrm_Boolean, "case-sensitive",       { .num  = &config.case_sensitive    }, NULL, "Set case-sensitivity"                        },
-    { xrm_Boolean, "sidebar-mode",         { .num  = &config.sidebar_mode      }, NULL, "Enable sidebar-mode"                         },
-    { xrm_Number,  "lazy-filter-limit",    { .num  = &config.lazy_filter_limit }, NULL, "Set lazy filter limit"                       },
-    { xrm_SNumber, "eh",                   { .snum = &config.element_height    }, NULL, "Row height (in chars)"                       },
-    { xrm_Boolean, "auto-select",          { .num  = &config.auto_select       }, NULL, "Enable auto select mode"                     },
-    { xrm_Boolean, "parse-hosts",          { .num  = &config.parse_hosts       }, NULL, "Parse hosts file for ssh mode"               },
-    { xrm_Boolean, "parse-known-hosts",    { .num  = &config.parse_known_hosts }, NULL, "Parse known_hosts file for ssh mode"         },
-    { xrm_String,  "combi-modi",           { .str  = &config.combi_modi        }, NULL, "Set the modi to combine in combi mode"       },
-    { xrm_Boolean, "fuzzy",                { .num  = &config.fuzzy             }, NULL, "Do a more fuzzy matching"                    },
-    { xrm_Boolean, "glob",                 { .num  = &config.glob              }, NULL, "Use glob matching"                           },
-    { xrm_Boolean, "tokenize",             { .num  = &config.tokenize          }, NULL, "Tokenize input string"                       },
-    { xrm_Number,  "monitor",              { .snum = &config.monitor           }, NULL, ""                                            },
+    { xrm_String,  "foreground",           { .str  = &config.menu_fg            }, NULL, ""                                            },
+    { xrm_String,  "fg",                   { .str  = &config.menu_fg            }, NULL, "Foreground color"                            },
+    { xrm_String,  "background",           { .str  = &config.menu_bg            }, NULL, ""                                            },
+    { xrm_String,  "bg",                   { .str  = &config.menu_bg            }, NULL, "Background color"                            },
+
+    { xrm_String,  "fg-active",            { .str  = &config.menu_fg_active     }, NULL, "Foreground color for active row"             },
+    { xrm_String,  "fg-urgent",            { .str  = &config.menu_fg_urgent     }, NULL, "Foreground color for urgent row"             },
+    { xrm_String,  "hlfg-active",          { .str  = &config.menu_hlfg_active   }, NULL, "Foreground color for highlighted active row" },
+    { xrm_String,  "hlfg-urgent",          { .str  = &config.menu_hlfg_urgent   }, NULL, "Foreground color for highlighted urgent row" },
+
+    { xrm_String,  "bg-active",            { .str  = &config.menu_bg_active     }, NULL, "Background color for active row"             },
+    { xrm_String,  "bg-urgent",            { .str  = &config.menu_bg_urgent     }, NULL, "Background color for urgent row"             },
+    { xrm_String,  "hlbg-active",          { .str  = &config.menu_hlbg_active   }, NULL, "Background color for highlighted active row" },
+    { xrm_String,  "hlbg-urgent",          { .str  = &config.menu_hlbg_urgent   }, NULL, "Background color for highlighted urgent row" },
+
+    { xrm_String,  "background-alternate", { .str  = &config.menu_bg_alt        }, NULL, ""                                            },
+    { xrm_String,  "bgalt",                { .str  = &config.menu_bg_alt        }, NULL, "Background color for alternating row"        },
+
+    { xrm_String,  "highlightfg",          { .str  = &config.menu_hlfg          }, NULL, ""                                            },
+    { xrm_String,  "hlfg",                 { .str  = &config.menu_hlfg          }, NULL, "Foreground color for highlighted row"        },
+
+    { xrm_String,  "highlightbg",          { .str  = &config.menu_hlbg          }, NULL, ""                                            },
+    { xrm_String,  "hlbg",                 { .str  = &config.menu_hlbg          }, NULL, "Background color for highlighted row"        },
+
+    { xrm_String,  "bordercolor",          { .str  = &config.menu_bc            }, NULL, ""                                            },
+    { xrm_String,  "bc",                   { .str  = &config.menu_bc            }, NULL, "Border color"                                },
+    { xrm_Boolean, "color-enabled",        { .num  = &config.color_enabled      }, NULL, "Use extended color scheme"                   },
+    { xrm_String,  "color-normal",         { .str  = &config.color_normal       }, NULL, "Color scheme for normal row"                 },
+    { xrm_String,  "color-urgent",         { .str  = &config.color_urgent       }, NULL, "Color scheme for urgent row"                 },
+    { xrm_String,  "color-active",         { .str  = &config.color_active       }, NULL, "Color scheme for active row"                 },
+    { xrm_String,  "color-window",         { .str  = &config.color_window       }, NULL, "Color scheme window"                         },
+
+    { xrm_Number,  "borderwidth",          { .num  = &config.menu_bw            }, NULL, ""                                            },
+    { xrm_Number,  "bw",                   { .num  = &config.menu_bw            }, NULL, "Border width"                                },
+
+    { xrm_Number,  "location",             { .num  = &config.location           }, NULL, "Location on screen"                          },
+
+    { xrm_Number,  "padding",              { .num  = &config.padding            }, NULL, "Padding"                                     },
+    { xrm_SNumber, "yoffset",              { .snum = &config.y_offset           }, NULL, "Y-offset relative to location"               },
+    { xrm_SNumber, "xoffset",              { .snum = &config.x_offset           }, NULL, "X-offset relative to location"               },
+    { xrm_Boolean, "fixed-num-lines",      { .num  = &config.fixed_num_lines    }, NULL, "Always show number of lines"                 },
+
+    { xrm_String,  "terminal",             { .str  = &config.terminal_emulator  }, NULL, "Terminal to use"                             },
+    { xrm_String,  "ssh-client",           { .str  = &config.ssh_client         }, NULL, "Ssh client to use"                           },
+    { xrm_String,  "ssh-command",          { .str  = &config.ssh_command        }, NULL, "Ssh command to execute"                      },
+    { xrm_String,  "run-command",          { .str  = &config.run_command        }, NULL, "Run command to execute"                      },
+    { xrm_String,  "run-list-command",     { .str  = &config.run_list_command   }, NULL, "Command to get extra run targets"            },
+    { xrm_String,  "run-shell-command",    { .str  = &config.run_shell_command  }, NULL, "Run command to execute that runs in shell"   },
+
+    { xrm_Boolean, "disable-history",      { .num  = &config.disable_history    }, NULL, "Disable history in run/ssh"                  },
+    { xrm_Boolean, "levenshtein-sort",     { .num  = &config.levenshtein_sort   }, NULL, "Use levenshtein sorting"                     },
+    { xrm_Boolean, "case-sensitive",       { .num  = &config.case_sensitive     }, NULL, "Set case-sensitivity"                        },
+    { xrm_Boolean, "sidebar-mode",         { .num  = &config.sidebar_mode       }, NULL, "Enable sidebar-mode"                         },
+    { xrm_Number,  "lazy-filter-limit",    { .num  = &config.lazy_filter_limit  }, NULL, "Set lazy filter limit"                       },
+    { xrm_SNumber, "eh",                   { .snum = &config.element_height     }, NULL, "Row height (in chars)"                       },
+    { xrm_Boolean, "auto-select",          { .num  = &config.auto_select        }, NULL, "Enable auto select mode"                     },
+    { xrm_Boolean, "parse-hosts",          { .num  = &config.parse_hosts        }, NULL, "Parse hosts file for ssh mode"               },
+    { xrm_Boolean, "parse-known-hosts",    { .num  = &config.parse_known_hosts  }, NULL, "Parse known_hosts file for ssh mode"         },
+    { xrm_String,  "combi-modi",           { .str  = &config.combi_modi         }, NULL, "Set the modi to combine in combi mode"       },
+    { xrm_Boolean, "fuzzy",                { .num  = &config.fuzzy              }, NULL, "Do a more fuzzy matching"                    },
+    { xrm_Boolean, "glob",                 { .num  = &config.glob               }, NULL, "Use glob matching"                           },
+    { xrm_Boolean, "tokenize",             { .num  = &config.tokenize           }, NULL, "Tokenize input string"                       },
+    { xrm_Number,  "monitor",              { .snum = &config.monitor            }, NULL, ""                                            },
     /* Alias for dmenu compatibility. */
-    { xrm_SNumber, "m",                    { .snum = &config.monitor           }, NULL, "Monitor id to show on"                       },
-    { xrm_Number,  "line-margin",          { .num  = &config.line_margin       }, NULL, "Margin between rows"                         },
-    { xrm_String,  "filter",               { .str  = &config.filter            }, NULL, "Pre-set filter"                              },
-    { xrm_String,  "separator-style",      { .str  = &config.separator_style   }, NULL, "Separator style (none, dash, solid)"         },
-    { xrm_Boolean, "hide-scrollbar",       { .num  = &config.hide_scrollbar    }, NULL, "Hide scroll-bar"                             },
-    { xrm_Boolean, "markup-rows",          { .num  = &config.markup_rows       }, NULL, "Show markup"                                 },
-    { xrm_Boolean, "fullscreen",           { .num  = &config.fullscreen        }, NULL, "Fullscreen"                                  },
-    { xrm_Boolean, "fake-transparency",    { .num  = &config.fake_transparency }, NULL, "Fake transparency"                           },
-    { xrm_SNumber, "dpi",                  { .snum = &config.dpi               }, NULL, "DPI"                                         }
+    { xrm_SNumber, "m",                    { .snum = &config.monitor            }, NULL, "Monitor id to show on"                       },
+    { xrm_Number,  "line-margin",          { .num  = &config.line_margin        }, NULL, "Margin between rows"                         },
+    { xrm_String,  "filter",               { .str  = &config.filter             }, NULL, "Pre-set filter"                              },
+    { xrm_String,  "separator-style",      { .str  = &config.separator_style    }, NULL, "Separator style (none, dash, solid)"         },
+    { xrm_Boolean, "hide-scrollbar",       { .num  = &config.hide_scrollbar     }, NULL, "Hide scroll-bar"                             },
+    { xrm_Boolean, "markup-rows",          { .num  = &config.markup_rows        }, NULL, "Show markup"                                 },
+    { xrm_Boolean, "fullscreen",           { .num  = &config.fullscreen         }, NULL, "Fullscreen"                                  },
+    { xrm_Boolean, "fake-transparency",    { .num  = &config.fake_transparency  }, NULL, "Fake transparency"                           },
+    { xrm_SNumber, "dpi",                  { .snum = &config.dpi                }, NULL, "DPI"                                         },
+    { xrm_Number,  "threads",              { .num  = &config.threads            }, NULL, "Threads to use for string matching"          }
 };
 
 // Dynamic options.