Resolve gravity coords in menuframe so it can use the widths
[dana/openbox.git] / openbox / menu.c
1 /* -*- indent-tabs-mode: nil; tab-width: 4; c-basic-offset: 4; -*-
2
3    menu.c for the Openbox window manager
4    Copyright (c) 2006        Mikael Magnusson
5    Copyright (c) 2003-2007   Dana Jansens
6
7    This program is free software; you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation; either version 2 of the License, or
10    (at your option) any later version.
11
12    This program is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    See the COPYING file for a copy of the GNU General Public License.
18 */
19
20 #include "debug.h"
21 #include "menu.h"
22 #include "openbox.h"
23 #include "stacking.h"
24 #include "grab.h"
25 #include "client.h"
26 #include "config.h"
27 #include "actions.h"
28 #include "screen.h"
29 #include "menuframe.h"
30 #include "keyboard.h"
31 #include "geom.h"
32 #include "misc.h"
33 #include "client_menu.h"
34 #include "client_list_menu.h"
35 #include "client_list_combined_menu.h"
36 #include "gettext.h"
37 #include "obt/xml.h"
38 #include "obt/paths.h"
39
40 typedef struct _ObMenuParseState ObMenuParseState;
41
42 struct _ObMenuParseState
43 {
44     ObMenu *parent;
45     ObMenu *pipe_creator;
46 };
47
48 static GHashTable *menu_hash = NULL;
49 static ObtXmlInst *menu_parse_inst;
50 static ObMenuParseState menu_parse_state;
51 static gboolean menu_can_hide = FALSE;
52 static guint menu_timeout_id = 0;
53
54 static void menu_destroy_hash_value(ObMenu *self);
55 static void parse_menu_item(xmlNodePtr node, gpointer data);
56 static void parse_menu_separator(xmlNodePtr node, gpointer data);
57 static void parse_menu(xmlNodePtr node, gpointer data);
58 static gunichar parse_shortcut(const gchar *label, gboolean allow_shortcut,
59                                gchar **strippedlabel, guint *position,
60                                gboolean *always_show);
61
62 void menu_startup(gboolean reconfig)
63 {
64     gboolean loaded = FALSE;
65     GSList *it;
66
67     menu_hash = g_hash_table_new_full(g_str_hash, g_str_equal, NULL,
68                                       (GDestroyNotify)menu_destroy_hash_value);
69
70     client_list_menu_startup(reconfig);
71     client_list_combined_menu_startup(reconfig);
72     client_menu_startup();
73
74     menu_parse_inst = obt_xml_instance_new();
75
76     menu_parse_state.parent = NULL;
77     menu_parse_state.pipe_creator = NULL;
78     obt_xml_register(menu_parse_inst, "menu", parse_menu, &menu_parse_state);
79     obt_xml_register(menu_parse_inst, "item", parse_menu_item,
80                      &menu_parse_state);
81     obt_xml_register(menu_parse_inst, "separator",
82                        parse_menu_separator, &menu_parse_state);
83
84     for (it = config_menu_files; it; it = g_slist_next(it)) {
85         if (obt_xml_load_config_file(menu_parse_inst,
86                                      "openbox",
87                                      it->data,
88                                      "openbox_menu"))
89         {
90             loaded = TRUE;
91             obt_xml_tree_from_root(menu_parse_inst);
92             obt_xml_close(menu_parse_inst);
93         }
94         else if (obt_xml_load_file(menu_parse_inst,
95                                    it->data,
96                                    "openbox_menu"))
97         {
98             loaded = TRUE;
99             obt_xml_tree_from_root(menu_parse_inst);
100             obt_xml_close(menu_parse_inst);
101         }
102         else
103             g_message(_("Unable to find a valid menu file \"%s\""),
104                       (const gchar*)it->data);
105     }
106     if (!loaded) {
107         if (obt_xml_load_config_file(menu_parse_inst,
108                                      "openbox",
109                                      "menu.xml",
110                                      "openbox_menu"))
111         {
112             obt_xml_tree_from_root(menu_parse_inst);
113             obt_xml_close(menu_parse_inst);
114         } else
115             g_message(_("Unable to find a valid menu file \"%s\""),
116                       "menu.xml");
117     }
118
119     g_assert(menu_parse_state.parent == NULL);
120 }
121
122 void menu_shutdown(gboolean reconfig)
123 {
124     obt_xml_instance_unref(menu_parse_inst);
125     menu_parse_inst = NULL;
126
127     menu_frame_hide_all();
128
129     client_list_combined_menu_shutdown(reconfig);
130     client_list_menu_shutdown(reconfig);
131
132     g_hash_table_destroy(menu_hash);
133     menu_hash = NULL;
134 }
135
136 static gboolean menu_pipe_submenu(gpointer key, gpointer val, gpointer data)
137 {
138     ObMenu *menu = val;
139     return menu->pipe_creator != NULL;
140 }
141
142 static void clear_cache(gpointer key, gpointer val, gpointer data)
143 {
144     ObMenu *menu = val;
145     if (menu->execute)
146         menu_clear_entries(menu);
147 }
148
149 void menu_clear_pipe_caches(void)
150 {
151     /* delete any pipe menus' submenus */
152     g_hash_table_foreach_remove(menu_hash, menu_pipe_submenu, NULL);
153     /* empty the top level pipe menus */
154     g_hash_table_foreach(menu_hash, clear_cache, NULL);
155 }
156
157 void menu_pipe_execute(ObMenu *self)
158 {
159     gchar *output;
160     GError *err = NULL;
161
162     if (!self->execute)
163         return;
164     if (self->entries) /* the entries are already created and cached */
165         return;
166
167     if (!g_spawn_command_line_sync(self->execute, &output, NULL, NULL, &err)) {
168         g_message(_("Failed to execute command for pipe-menu \"%s\": %s"),
169                   self->execute, err->message);
170         g_error_free(err);
171         return;
172     }
173
174     if (obt_xml_load_mem(menu_parse_inst, output, strlen(output),
175                          "openbox_pipe_menu"))
176     {
177         menu_parse_state.pipe_creator = self;
178         menu_parse_state.parent = self;
179         obt_xml_tree_from_root(menu_parse_inst);
180         obt_xml_close(menu_parse_inst);
181     } else {
182         g_message(_("Invalid output from pipe-menu \"%s\""), self->execute);
183     }
184
185     g_free(output);
186 }
187
188 static ObMenu* menu_from_name(gchar *name)
189 {
190     ObMenu *self = NULL;
191
192     g_assert(name != NULL);
193
194     if (!(self = g_hash_table_lookup(menu_hash, name)))
195         g_message(_("Attempted to access menu \"%s\" but it does not exist"),
196                   name);
197     return self;
198 }
199
200 #define VALID_SHORTCUT(c) (((c) >= '0' && (c) <= '9') || \
201                            ((c) >= 'A' && (c) <= 'Z') || \
202                            ((c) >= 'a' && (c) <= 'z'))
203
204 static gunichar parse_shortcut(const gchar *label, gboolean allow_shortcut,
205                                gchar **strippedlabel, guint *position,
206                                gboolean *always_show)
207 {
208     gunichar shortcut = 0;
209
210     *position = 0;
211     *always_show = FALSE;
212
213     g_assert(strippedlabel != NULL);
214
215     if (label == NULL) {
216         *strippedlabel = NULL;
217     } else {
218         gchar *i;
219         gboolean escape;
220
221         *strippedlabel = g_strdup(label);
222
223         /* if allow_shortcut is false, then you can't use the '_', instead you
224            have to just use the first valid character
225         */
226
227         /* allow __ to escape an underscore */
228         i = *strippedlabel;
229         do {
230             escape = FALSE;
231             i = strchr(i, '_');
232             if (i && *(i+1) == '_') {
233                 gchar *j;
234
235                 /* remove the escape '_' from the string */
236                 for (j = i; *j != '\0'; ++j)
237                     *j = *(j+1);
238
239                 ++i;
240                 escape = TRUE;
241             }
242         } while (escape);
243
244         if (allow_shortcut && i != NULL) {
245             /* there is an underscore in the string */
246
247             /* you have to use a printable ascii character for shortcuts
248                don't allow space either, so you can have like "a _ b"
249             */
250             if (VALID_SHORTCUT(*(i+1))) {
251                 shortcut = g_unichar_tolower(g_utf8_get_char(i+1));
252                 *position = i - *strippedlabel;
253                 *always_show = TRUE;
254
255                 /* remove the '_' from the string */
256                 for (; *i != '\0'; ++i)
257                     *i = *(i+1);
258             } else if (*(i+1) == '\0') {
259                 /* no default shortcut if the '_' is the last character
260                    (eg. "Exit_") for menu entries that you don't want
261                    to be executed by mistake
262                 */
263                     *i = '\0';
264             }
265         } else {
266             /* there is no underscore, so find the first valid character to use
267                instead */
268
269             for (i = *strippedlabel; *i != '\0'; ++i)
270                 if (VALID_SHORTCUT(*i)) {
271                     *position = i - *strippedlabel;
272                     shortcut = g_unichar_tolower(g_utf8_get_char(i));
273                     break;
274                 }
275         }
276     }
277     return shortcut;
278 }
279
280 static void parse_menu_item(xmlNodePtr node, gpointer data)
281 {
282     ObMenuParseState *state = data;
283     gchar *label;
284     gchar *icon;
285     ObMenuEntry *e;
286
287     if (state->parent) {
288         /* Don't try to extract "icon" attribute if icons in user-defined
289            menus are not enabled. */
290
291         if (obt_xml_attr_string_unstripped(node, "label", &label)) {
292             xmlNodePtr c;
293             GSList *acts = NULL;
294
295             c = obt_xml_find_node(node->children, "action");
296             while (c) {
297                 ObActionsAct *action = actions_parse(c);
298                 if (action)
299                     acts = g_slist_append(acts, action);
300                 c = obt_xml_find_node(c->next, "action");
301             }
302             e = menu_add_normal(state->parent, -1, label, acts, TRUE);
303             
304             if (config_menu_show_icons &&
305                 obt_xml_attr_string(node, "icon", &icon))
306             {
307                 e->data.normal.icon = RrImageNewFromName(ob_rr_icons, icon);
308
309                 if (e->data.normal.icon)
310                     e->data.normal.icon_alpha = 0xff;
311
312                 g_free(icon);
313             }
314             g_free(label);
315         }
316     }
317 }
318
319 static void parse_menu_separator(xmlNodePtr node, gpointer data)
320 {
321     ObMenuParseState *state = data;
322
323     if (state->parent) {
324         gchar *label;
325
326         if (!obt_xml_attr_string_unstripped(node, "label", &label))
327             label = NULL;
328
329         menu_add_separator(state->parent, -1, label);
330         g_free(label);
331     }
332 }
333
334 static void parse_menu(xmlNodePtr node, gpointer data)
335 {
336     ObMenuParseState *state = data;
337     gchar *name = NULL, *title = NULL, *script = NULL;
338     ObMenu *menu;
339     ObMenuEntry *e;
340     gchar *icon;
341
342     if (!obt_xml_attr_string(node, "id", &name))
343         goto parse_menu_fail;
344
345     if (!g_hash_table_lookup(menu_hash, name)) {
346         if (!obt_xml_attr_string_unstripped(node, "label", &title))
347             goto parse_menu_fail;
348
349         if ((menu = menu_new(name, title, TRUE, NULL))) {
350             menu->pipe_creator = state->pipe_creator;
351             if (obt_xml_attr_string(node, "execute", &script)) {
352                 menu->execute = obt_paths_expand_tilde(script);
353             } else {
354                 ObMenu *old;
355
356                 old = state->parent;
357                 state->parent = menu;
358                 obt_xml_tree(menu_parse_inst, node->children);
359                 state->parent = old;
360             }
361         }
362     }
363
364     if (state->parent) {
365         e = menu_add_submenu(state->parent, -1, name);
366
367         if (config_menu_show_icons &&
368             obt_xml_attr_string(node, "icon", &icon))
369         {
370             e->data.submenu.icon = RrImageNewFromName(ob_rr_icons, icon);
371
372             if (e->data.submenu.icon)
373                 e->data.submenu.icon_alpha = 0xff;
374
375             g_free(icon);
376         }
377     }
378
379 parse_menu_fail:
380     g_free(name);
381     g_free(title);
382     g_free(script);
383 }
384
385 ObMenu* menu_new(const gchar *name, const gchar *title,
386                  gboolean allow_shortcut_selection, gpointer data)
387 {
388     ObMenu *self;
389
390     self = g_slice_new0(ObMenu);
391     self->name = g_strdup(name);
392     self->data = data;
393
394     self->shortcut = parse_shortcut(title, allow_shortcut_selection,
395                                     &self->title, &self->shortcut_position,
396                                     &self->shortcut_always_show);
397     self->collate_key = g_utf8_collate_key(self->title, -1);
398
399     g_hash_table_replace(menu_hash, self->name, self);
400
401     /* Each menu has a single more_menu.  When the menu spills past what
402        can fit on the screen, a new menu frame entry is created from this
403        more_menu, and a new menu frame for the submenu is created for this
404        menu, also pointing to the more_menu.
405
406        This can be done multiple times using the same more_menu.
407
408        more_menu->more_menu will always be NULL, since there is only 1 for
409        each menu. */
410     self->more_menu = g_slice_new0(ObMenu);
411     self->more_menu->name = _("More...");
412     self->more_menu->title = _("More...");
413     self->more_menu->collate_key = "\xff\xff\xff\xff\xff\xff\xff\xff\xff\xff";
414     self->more_menu->data = data;
415     self->more_menu->shortcut = g_unichar_tolower(g_utf8_get_char("M"));
416
417     return self;
418 }
419
420 static void menu_destroy_hash_value(ObMenu *self)
421 {
422     /* make sure its not visible */
423     {
424         GList *it;
425         ObMenuFrame *f;
426
427         for (it = menu_frame_visible; it; it = g_list_next(it)) {
428             f = it->data;
429             if (f->menu == self)
430                 menu_frame_hide_all();
431         }
432     }
433
434     if (self->destroy_func)
435         self->destroy_func(self, self->data);
436
437     menu_clear_entries(self);
438     g_free(self->name);
439     g_free(self->title);
440     g_free(self->collate_key);
441     g_free(self->execute);
442     g_slice_free(ObMenu, self->more_menu);
443
444     g_slice_free(ObMenu, self);
445 }
446
447 void menu_free(ObMenu *menu)
448 {
449     if (menu)
450         g_hash_table_remove(menu_hash, menu->name);
451 }
452
453 static gboolean menu_hide_delay_func(gpointer data)
454 {
455     menu_can_hide = TRUE;
456     menu_timeout_id = 0;
457     return FALSE; /* no repeat */
458 }
459
460 void menu_show(gchar *name, GravityPoint pos, gint monitor,
461                gboolean mouse, ObClient *client)
462 {
463     ObMenu *self;
464     ObMenuFrame *frame;
465
466     if (!(self = menu_from_name(name)) ||
467         grab_on_keyboard() || grab_on_pointer()) return;
468
469     /* if the requested menu is already the top visible menu, then don't
470        bother */
471     if (menu_frame_visible) {
472         frame = menu_frame_visible->data;
473         if (frame->menu == self)
474             return;
475     }
476
477     menu_frame_hide_all();
478
479     /* clear the pipe menus when showing a new menu */
480     menu_clear_pipe_caches();
481
482     frame = menu_frame_new(self, 0, client);
483     if (!menu_frame_show_topmenu(frame, pos, monitor, mouse))
484         menu_frame_free(frame);
485     else {
486         if (!mouse) {
487             /* select the first entry if it's not a submenu and we opened
488              * the menu with the keyboard, and skip all headers */
489             GList *it = frame->entries;
490             while (it) {
491                 ObMenuEntryFrame *e = it->data;
492                 if (e->entry->type == OB_MENU_ENTRY_TYPE_NORMAL) {
493                     menu_frame_select(frame, e, FALSE);
494                     break;
495                 } else if (e->entry->type == OB_MENU_ENTRY_TYPE_SEPARATOR)
496                     it = g_list_next(it);
497                 else
498                     break;
499             }
500         }
501
502         /* reset the hide timer */
503         if (!mouse)
504             menu_can_hide = TRUE;
505         else {
506             menu_can_hide = FALSE;
507             if (menu_timeout_id) g_source_remove(menu_timeout_id);
508             menu_timeout_id = g_timeout_add_full(G_PRIORITY_DEFAULT,
509                                                  config_menu_hide_delay,
510                                                  menu_hide_delay_func,
511                                                  NULL, NULL);
512         }
513     }
514 }
515
516 gboolean menu_hide_delay_reached(void)
517 {
518     return menu_can_hide;
519 }
520
521 static ObMenuEntry* menu_entry_new(ObMenu *menu, ObMenuEntryType type, gint id)
522 {
523     ObMenuEntry *self;
524
525     g_assert(menu);
526
527     self = g_slice_new0(ObMenuEntry);
528     self->ref = 1;
529     self->type = type;
530     self->menu = menu;
531     self->id = id;
532
533     switch (type) {
534     case OB_MENU_ENTRY_TYPE_NORMAL:
535         self->data.normal.enabled = TRUE;
536         break;
537     case OB_MENU_ENTRY_TYPE_SUBMENU:
538     case OB_MENU_ENTRY_TYPE_SEPARATOR:
539         break;
540     }
541
542     return self;
543 }
544
545 void menu_entry_ref(ObMenuEntry *self)
546 {
547     ++self->ref;
548 }
549
550 void menu_entry_unref(ObMenuEntry *self)
551 {
552     if (self && --self->ref == 0) {
553         switch (self->type) {
554         case OB_MENU_ENTRY_TYPE_NORMAL:
555             RrImageUnref(self->data.normal.icon);
556             g_free(self->data.normal.label);
557             g_free(self->data.normal.collate_key);
558             while (self->data.normal.actions) {
559                 actions_act_unref(self->data.normal.actions->data);
560                 self->data.normal.actions =
561                     g_slist_delete_link(self->data.normal.actions,
562                                         self->data.normal.actions);
563             }
564             break;
565         case OB_MENU_ENTRY_TYPE_SUBMENU:
566             RrImageUnref(self->data.submenu.icon);
567             g_free(self->data.submenu.name);
568             break;
569         case OB_MENU_ENTRY_TYPE_SEPARATOR:
570             g_free(self->data.separator.label);
571             break;
572         }
573
574         g_slice_free(ObMenuEntry, self);
575     }
576 }
577
578 void menu_clear_entries(ObMenu *self)
579 {
580 #ifdef DEBUG
581     /* assert that the menu isn't visible */
582     {
583         GList *it;
584         ObMenuFrame *f;
585
586         for (it = menu_frame_visible; it; it = g_list_next(it)) {
587             f = it->data;
588             g_assert(f->menu != self);
589         }
590     }
591 #endif
592
593     while (self->entries) {
594         menu_entry_unref(self->entries->data);
595         self->entries = g_list_delete_link(self->entries, self->entries);
596     }
597     self->more_menu->entries = self->entries; /* keep it in sync */
598 }
599
600 void menu_entry_remove(ObMenuEntry *self)
601 {
602     self->menu->entries = g_list_remove(self->menu->entries, self);
603     menu_entry_unref(self);
604 }
605
606 ObMenuEntry* menu_add_normal(ObMenu *self, gint id, const gchar *label,
607                              GSList *actions, gboolean allow_shortcut)
608 {
609     ObMenuEntry *e;
610
611     e = menu_entry_new(self, OB_MENU_ENTRY_TYPE_NORMAL, id);
612     e->data.normal.actions = actions;
613
614     menu_entry_set_label(e, label, allow_shortcut);
615
616     self->entries = g_list_append(self->entries, e);
617     self->more_menu->entries = self->entries; /* keep it in sync */
618     return e;
619 }
620
621 ObMenuEntry* menu_get_more(ObMenu *self, guint show_from)
622 {
623     ObMenuEntry *e;
624     e = menu_entry_new(self, OB_MENU_ENTRY_TYPE_SUBMENU, -1);
625     /* points to itself */
626     e->data.submenu.name = g_strdup(self->name);
627     e->data.submenu.submenu = self;
628     e->data.submenu.show_from = show_from;
629     return e;
630 }
631
632 ObMenuEntry* menu_add_submenu(ObMenu *self, gint id, const gchar *submenu)
633 {
634     ObMenuEntry *e;
635
636     e = menu_entry_new(self, OB_MENU_ENTRY_TYPE_SUBMENU, id);
637     e->data.submenu.name = g_strdup(submenu);
638
639     self->entries = g_list_append(self->entries, e);
640     self->more_menu->entries = self->entries; /* keep it in sync */
641     return e;
642 }
643
644 ObMenuEntry* menu_add_separator(ObMenu *self, gint id, const gchar *label)
645 {
646     ObMenuEntry *e;
647
648     e = menu_entry_new(self, OB_MENU_ENTRY_TYPE_SEPARATOR, id);
649
650     menu_entry_set_label(e, label, FALSE);
651
652     self->entries = g_list_append(self->entries, e);
653     self->more_menu->entries = self->entries; /* keep it in sync */
654     return e;
655 }
656
657 void menu_set_show_func(ObMenu *self, ObMenuShowFunc func)
658 {
659     self->show_func = func;
660 }
661
662 void menu_set_hide_func(ObMenu *self, ObMenuHideFunc func)
663 {
664     self->hide_func = func;
665 }
666
667 void menu_set_update_func(ObMenu *self, ObMenuUpdateFunc func)
668 {
669     self->update_func = func;
670 }
671
672 void menu_set_execute_func(ObMenu *self, ObMenuExecuteFunc func)
673 {
674     self->execute_func = func;
675     self->more_menu->execute_func = func; /* keep it in sync */
676 }
677
678 void menu_set_cleanup_func(ObMenu *self, ObMenuCleanupFunc func)
679 {
680     self->cleanup_func = func;
681 }
682
683 void menu_set_destroy_func(ObMenu *self, ObMenuDestroyFunc func)
684 {
685     self->destroy_func = func;
686 }
687
688 void menu_set_place_func(ObMenu *self, ObMenuPlaceFunc func)
689 {
690     self->place_func = func;
691 }
692
693 ObMenuEntry* menu_find_entry_id(ObMenu *self, gint id)
694 {
695     ObMenuEntry *ret = NULL;
696     GList *it;
697
698     for (it = self->entries; it; it = g_list_next(it)) {
699         ObMenuEntry *e = it->data;
700
701         if (e->id == id) {
702             ret = e;
703             break;
704         }
705     }
706     return ret;
707 }
708
709 void menu_find_submenus(ObMenu *self)
710 {
711     GList *it;
712
713     for (it = self->entries; it; it = g_list_next(it)) {
714         ObMenuEntry *e = it->data;
715
716         if (e->type == OB_MENU_ENTRY_TYPE_SUBMENU)
717             e->data.submenu.submenu = menu_from_name(e->data.submenu.name);
718     }
719 }
720
721 void menu_entry_set_label(ObMenuEntry *self, const gchar *label,
722                           gboolean allow_shortcut)
723 {
724     switch (self->type) {
725     case OB_MENU_ENTRY_TYPE_SEPARATOR:
726         g_free(self->data.separator.label);
727         self->data.separator.label = g_strdup(label);
728         break;
729     case OB_MENU_ENTRY_TYPE_NORMAL:
730         g_free(self->data.normal.label);
731         g_free(self->data.normal.collate_key);
732         self->data.normal.shortcut =
733             parse_shortcut(label, allow_shortcut, &self->data.normal.label,
734                            &self->data.normal.shortcut_position,
735                            &self->data.normal.shortcut_always_show);
736         self->data.normal.collate_key =
737             g_utf8_collate_key(self->data.normal.label, -1);
738         break;
739     default:
740         g_assert_not_reached();
741     }
742 }
743
744 void menu_show_all_shortcuts(ObMenu *self, gboolean show)
745 {
746     self->show_all_shortcuts = show;
747 }
748
749 static int sort_func(const void *a, const void *b) {
750     const ObMenuEntry *e[2] = {*(ObMenuEntry**)a, *(ObMenuEntry**)b};
751     const gchar *k[2];
752     gint i;
753
754     for (i = 0; i < 2; ++i) {
755         if (e[i]->type == OB_MENU_ENTRY_TYPE_NORMAL)
756             k[i] = e[i]->data.normal.collate_key;
757         else {
758             g_assert(e[i]->type == OB_MENU_ENTRY_TYPE_SUBMENU);
759             if (e[i]->data.submenu.submenu)
760                 k[i] = e[i]->data.submenu.submenu->collate_key;
761             else
762                 return -1; /* arbitrary really.. the submenu doesn't exist. */
763         }
764     }
765     return strcmp(k[0], k[1]);
766 }
767
768 /*!
769   @param start The first entry in the range to sort.
770   @param end The last entry in the range to sort.
771 */
772 static void sort_range(ObMenu *self, GList *start, GList *end, guint len)
773 {
774     ObMenuEntry **ar;
775     GList *it;
776     guint i;
777     if (!len) return;
778
779     ar = g_slice_alloc(sizeof(ObMenuEntry*) * len);
780     for (i = 0, it = start; it != g_list_next(end); ++i, it = g_list_next(it))
781         ar[i] = it->data;
782     qsort(ar, len, sizeof(ObMenuEntry*), sort_func);
783     for (i = 0, it = start; it != g_list_next(end); ++i, it = g_list_next(it))
784         it->data = ar[i];
785     g_slice_free1(sizeof(ObMenuEntry*) * len, ar);
786 }
787
788 void menu_sort_entries(ObMenu *self)
789 {
790     GList *it, *start, *end, *last;
791     guint len;
792
793     /* need the submenus to know their labels for sorting */
794     menu_find_submenus(self);
795
796     start = self->entries;
797     len = 0;
798     for (it = self->entries; it; it = g_list_next(it)) {
799         ObMenuEntry *e = it->data;
800         if (e->type == OB_MENU_ENTRY_TYPE_SEPARATOR) {
801             end = g_list_previous(it);
802             sort_range(self, start, end, len);
803
804             it = g_list_next(it); /* skip over the separator */
805             start = it;
806             len = 0;
807         }
808         else
809             len += 1;
810         last = it;
811     }
812     sort_range(self, start, last, len);
813 }