Pileus Git - ~andy/gtk/blob - gtk/gtkkeyhash.c

   1 /* gtkkeyhash.c: Keymap aware matching of key bindings
   2  *
   3  * GTK - The GIMP Toolkit
   4  * Copyright (C) 2002, Red Hat Inc.
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library; if not, write to the
  18  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19  * Boston, MA 02111-1307, USA.
  20  */
  21 #include "config.h"
  22 #include "gtkdebug.h"
  23 #include "gtkkeyhash.h"
  24
  25 typedef struct _GtkKeyHashEntry GtkKeyHashEntry;
  26
  27 struct _GtkKeyHashEntry
  28 {
  29   guint keyval;
  30   GdkModifierType modifiers;
  31   gpointer value;
  32
  33   /* Set as a side effect of generating key_hash->keycode_hash
  34    */
  35   GdkKeymapKey *keys;
  36   gint n_keys;
  37 };
  38
  39 struct _GtkKeyHash
  40 {
  41   GdkKeymap *keymap;
  42   GHashTable *keycode_hash;
  43   GHashTable *reverse_hash;
  44   GList *entries_list;
  45   GDestroyNotify destroy_notify;
  46 };
  47
  48 static void
  49 key_hash_clear_keycode (gpointer key,
  50                         gpointer value,
  51                         gpointer data)
  52 {
  53   GSList *keys = value;
  54   g_slist_free (keys);
  55 }
  56
  57 static void
  58 key_hash_insert_entry (GtkKeyHash      *key_hash,
  59                        GtkKeyHashEntry *entry)
  60 {
  61   gint i;
  62
  63   g_free (entry->keys);
  64   gdk_keymap_get_entries_for_keyval (key_hash->keymap,
  65                                      entry->keyval,
  66                                      &entry->keys, &entry->n_keys);
  67
  68   for (i = 0; i < entry->n_keys; i++)
  69     {
  70       GSList *old_keys = g_hash_table_lookup (key_hash->keycode_hash,
  71                                               GUINT_TO_POINTER (entry->keys[i].keycode));
  72       old_keys = g_slist_prepend (old_keys, entry);
  73       g_hash_table_insert (key_hash->keycode_hash,
  74                            GUINT_TO_POINTER (entry->keys[i].keycode),
  75                            old_keys);
  76     }
  77 }
  78
  79 static GHashTable *
  80 key_hash_get_keycode_hash (GtkKeyHash *key_hash)
  81 {
  82   if (!key_hash->keycode_hash)
  83     {
  84       GList *tmp_list;
  85
  86       key_hash->keycode_hash = g_hash_table_new (g_direct_hash, NULL);
  87
  88       /* Preserve the original insertion order
  89        */
  90       for (tmp_list = g_list_last (key_hash->entries_list);
  91            tmp_list;
  92            tmp_list = tmp_list->prev)
  93         key_hash_insert_entry (key_hash, tmp_list->data);
  94     }
  95
  96   return key_hash->keycode_hash;
  97 }
  98
  99 static void
 100 key_hash_keys_changed (GdkKeymap  *keymap,
 101                        GtkKeyHash *key_hash)
 102 {
 103   /* The keymap changed, so we have to regenerate the keycode hash
 104    */
 105   if (key_hash->keycode_hash)
 106     {
 107       g_hash_table_foreach (key_hash->keycode_hash, key_hash_clear_keycode, NULL);
 108       g_hash_table_destroy (key_hash->keycode_hash);
 109       key_hash->keycode_hash = NULL;
 110     }
 111 }
 112
 113 /**
 114  * _gtk_key_hash_new:
 115  * @keymap: a #GdkKeymap
 116  * @item_destroy_notify: function to be called when items are removed
 117  *   from the hash or %NULL.
 118  *
 119  * Create a new key hash object for doing binding resolution.
 120  *
 121  * Return value: the newly created object. Free with _gtk_key_hash_free().
 122  **/
 123 GtkKeyHash *
 124 _gtk_key_hash_new (GdkKeymap      *keymap,
 125                    GDestroyNotify  item_destroy_notify)
 126 {
 127   GtkKeyHash *key_hash = g_new (GtkKeyHash, 1);
 128
 129   key_hash->keymap = keymap;
 130   g_signal_connect (keymap, "keys-changed",
 131                     G_CALLBACK (key_hash_keys_changed), key_hash);
 132
 133   key_hash->entries_list = NULL;
 134   key_hash->keycode_hash = NULL;
 135   key_hash->reverse_hash = g_hash_table_new (g_direct_hash, NULL);
 136   key_hash->destroy_notify = item_destroy_notify;
 137
 138   return key_hash;
 139 }
 140
 141 static void
 142 key_hash_free_entry (GtkKeyHash      *key_hash,
 143                      GtkKeyHashEntry *entry)
 144 {
 145   if (key_hash->destroy_notify)
 146     (*key_hash->destroy_notify) (entry->value);
 147
 148   g_free (entry->keys);
 149   g_slice_free (GtkKeyHashEntry, entry);
 150 }
 151
 152 static void
 153 key_hash_free_entry_foreach (gpointer value,
 154                              gpointer data)
 155 {
 156   GtkKeyHashEntry *entry = value;
 157   GtkKeyHash *key_hash = data;
 158
 159   key_hash_free_entry (key_hash, entry);
 160 }
 161
 162 /**
 163  * gtk_key_hash_free:
 164  * @key_hash: a #GtkKeyHash
 165  *
 166  * Destroys a key hash created with gtk_key_hash_new()
 167  **/
 168 void
 169 _gtk_key_hash_free (GtkKeyHash *key_hash)
 170 {
 171   g_signal_handlers_disconnect_by_func (key_hash->keymap,
 172                                         key_hash_keys_changed,
 173                                         key_hash);
 174
 175   if (key_hash->keycode_hash)
 176     {
 177       g_hash_table_foreach (key_hash->keycode_hash, key_hash_clear_keycode, NULL);
 178       g_hash_table_destroy (key_hash->keycode_hash);
 179     }
 180
 181   g_hash_table_destroy (key_hash->reverse_hash);
 182
 183   g_list_foreach (key_hash->entries_list, key_hash_free_entry_foreach, key_hash);
 184   g_list_free (key_hash->entries_list);
 185
 186   g_free (key_hash);
 187 }
 188
 189 /**
 190  * _gtk_key_hash_add_entry:
 191  * @key_hash: a #GtkKeyHash
 192  * @keyval: key symbol for this binding
 193  * @modifiers: modifiers for this binding
 194  * @value: value to insert in the key hash
 195  *
 196  * Inserts a pair of key symbol and modifier mask into the key hash.
 197  **/
 198 void
 199 _gtk_key_hash_add_entry (GtkKeyHash      *key_hash,
 200                          guint            keyval,
 201                          GdkModifierType  modifiers,
 202                          gpointer         value)
 203 {
 204   GtkKeyHashEntry *entry = g_slice_new (GtkKeyHashEntry);
 205
 206   entry->value = value;
 207   entry->keyval = keyval;
 208   entry->modifiers = modifiers;
 209   entry->keys = NULL;
 210
 211   key_hash->entries_list = g_list_prepend (key_hash->entries_list, entry);
 212   g_hash_table_insert (key_hash->reverse_hash, value, key_hash->entries_list);
 213
 214   if (key_hash->keycode_hash)
 215     key_hash_insert_entry (key_hash, entry);
 216 }
 217
 218 /**
 219  * _gtk_key_hash_remove_entry:
 220  * @key_hash: a #GtkKeyHash
 221  * @value: value previously added with _gtk_key_hash_add_entry()
 222  *
 223  * Removes a value previously added to the key hash with
 224  * _gtk_key_hash_add_entry().
 225  **/
 226 void
 227 _gtk_key_hash_remove_entry (GtkKeyHash *key_hash,
 228                             gpointer    value)
 229 {
 230   GList *entry_node = g_hash_table_lookup (key_hash->reverse_hash, value);
 231
 232   if (entry_node)
 233     {
 234       GtkKeyHashEntry *entry = entry_node->data;
 235
 236       if (key_hash->keycode_hash)
 237         {
 238           gint i;
 239
 240           for (i = 0; i < entry->n_keys; i++)
 241             {
 242               GSList *old_keys = g_hash_table_lookup (key_hash->keycode_hash,
 243                                                       GUINT_TO_POINTER (entry->keys[i].keycode));
 244
 245               GSList *new_keys = g_slist_remove (old_keys, entry);
 246               if (new_keys != old_keys)
 247                 {
 248                   if (new_keys)
 249                     g_hash_table_insert (key_hash->keycode_hash,
 250                                          GUINT_TO_POINTER (entry->keys[i].keycode),
 251                                          new_keys);
 252                   else
 253                     g_hash_table_remove (key_hash->keycode_hash,
 254                                          GUINT_TO_POINTER (entry->keys[i].keycode));
 255                 }
 256             }
 257         }
 258
 259       g_hash_table_remove (key_hash->reverse_hash, entry_node);
 260       key_hash->entries_list = g_list_delete_link (key_hash->entries_list, entry_node);
 261
 262       key_hash_free_entry (key_hash, entry);
 263     }
 264 }
 265
 266 static gint
 267 lookup_result_compare (gconstpointer a,
 268                        gconstpointer b)
 269 {
 270   const GtkKeyHashEntry *entry_a = a;
 271   const GtkKeyHashEntry *entry_b = b;
 272   guint modifiers;
 273
 274   gint n_bits_a = 0;
 275   gint n_bits_b = 0;
 276
 277   modifiers = entry_a->modifiers;
 278   while (modifiers)
 279     {
 280       if (modifiers & 1)
 281         n_bits_a++;
 282       modifiers >>= 1;
 283     }
 284
 285   modifiers = entry_b->modifiers;
 286   while (modifiers)
 287     {
 288       if (modifiers & 1)
 289         n_bits_b++;
 290       modifiers >>= 1;
 291     }
 292
 293   return n_bits_a < n_bits_b ? -1 : (n_bits_a == n_bits_b ? 0 : 1);
 294
 295 }
 296
 297 /* Sort a list of results so that matches with less modifiers come
 298  * before matches with more modifiers
 299  */
 300 static GSList *
 301 sort_lookup_results (GSList *slist)
 302 {
 303   return g_slist_sort (slist, lookup_result_compare);
 304 }
 305
 306 static gint
 307 lookup_result_compare_by_keyval (gconstpointer a,
 308                                  gconstpointer b)
 309 {
 310   const GtkKeyHashEntry *entry_a = a;
 311   const GtkKeyHashEntry *entry_b = b;
 312
 313   if (entry_a->keyval < entry_b->keyval)
 314         return -1;
 315   else if (entry_a->keyval > entry_b->keyval)
 316         return 1;
 317   else
 318         return 0;
 319 }
 320
 321 static GSList *
 322 sort_lookup_results_by_keyval (GSList *slist)
 323 {
 324   return g_slist_sort (slist, lookup_result_compare_by_keyval);
 325 }
 326
 327 /* Return true if keyval is defined in keyboard group
 328  */
 329 static gboolean
 330 keyval_in_group (GdkKeymap  *keymap,
 331                  guint      keyval,
 332                  gint       group)
 333 {
 334   GtkKeyHashEntry entry;
 335   gint i;
 336
 337   gdk_keymap_get_entries_for_keyval (keymap,
 338                                      keyval,
 339                                      &entry.keys, &entry.n_keys);
 340
 341   for (i = 0; i < entry.n_keys; i++)
 342     {
 343       if (entry.keys[i].group == group)
 344         {
 345           g_free (entry.keys);
 346           return TRUE;
 347         }
 348     }
 349
 350   g_free (entry.keys);
 351   return FALSE;
 352 }
 353
 354 /**
 355  * _gtk_key_hash_lookup:
 356  * @key_hash: a #GtkKeyHash
 357  * @hardware_keycode: hardware keycode field from a #GdkEventKey
 358  * @state: state field from a #GdkEventKey
 359  * @mask: mask of modifiers to consider when matching against the
 360  *        modifiers in entries.
 361  * @group: group field from a #GdkEventKey
 362  *
 363  * Looks up the best matching entry or entries in the hash table for
 364  * a given event. The results are sorted so that entries with less
 365  * modifiers come before entries with more modifiers.
 366  *
 367  * The matches returned by this function can be exact (i.e. keycode, level
 368  * and group all match) or fuzzy (i.e. keycode and level match, but group
 369  * does not). As long there are any exact matches, only exact matches
 370  * are returned. If there are no exact matches, fuzzy matches will be
 371  * returned, as long as they are not shadowing a possible exact match.
 372  * This means that fuzzy matches won't be considered if their keyval is
 373  * present in the current group.
 374  *
 375  * Return value: A #GSList of matching entries.
 376  **/
 377 GSList *
 378 _gtk_key_hash_lookup (GtkKeyHash      *key_hash,
 379                       guint16          hardware_keycode,
 380                       GdkModifierType  state,
 381                       GdkModifierType  mask,
 382                       gint             group)
 383 {
 384   GHashTable *keycode_hash = key_hash_get_keycode_hash (key_hash);
 385   GSList *keys = g_hash_table_lookup (keycode_hash, GUINT_TO_POINTER ((guint)hardware_keycode));
 386   GSList *results = NULL;
 387   GSList *l;
 388   gboolean have_exact = FALSE;
 389   guint keyval;
 390   gint effective_group;
 391   gint level;
 392   GdkModifierType modifiers;
 393   GdkModifierType consumed_modifiers;
 394   const GdkModifierType xmods = GDK_MOD2_MASK|GDK_MOD3_MASK|GDK_MOD4_MASK|GDK_MOD5_MASK;
 395   const GdkModifierType vmods = GDK_SUPER_MASK|GDK_HYPER_MASK|GDK_META_MASK;
 396
 397   /* We don't want Caps_Lock to affect keybinding lookups.
 398    */
 399   state &= ~GDK_LOCK_MASK;
 400
 401   gdk_keymap_map_virtual_modifiers (key_hash->keymap, &mask);
 402
 403   gdk_keymap_translate_keyboard_state (key_hash->keymap,
 404                                        hardware_keycode, state, group,
 405                                        &keyval, &effective_group, &level, &consumed_modifiers);
 406   gdk_keymap_add_virtual_modifiers (key_hash->keymap, &state);
 407
 408   GTK_NOTE (KEYBINDINGS,
 409             g_message ("Looking up keycode = %u, modifiers = 0x%04x,\n"
 410                        "    keyval = %u, group = %d, level = %d, consumed_modifiers = 0x%04x",
 411                        hardware_keycode, state, keyval, effective_group, level, consumed_modifiers));
 412
 413   if (keys)
 414     {
 415       GSList *tmp_list = keys;
 416       while (tmp_list)
 417         {
 418           GtkKeyHashEntry *entry = tmp_list->data;
 419
 420           /* If the virtual Super, Hyper or Meta modifiers are present,
 421            * they will also be mapped to some of the Mod2 - Mod5 modifiers,
 422            * so we compare them twice, ignoring either set.
 423            * We accept combinations involving virtual modifiers only if they
 424            * are mapped to separate modifiers; i.e. if Super and Hyper are
 425            * both mapped to Mod4, then pressing a key that is mapped to Mod4
 426            * will not match a Super+Hyper entry.
 427            */
 428           modifiers = entry->modifiers;
 429           if (gdk_keymap_map_virtual_modifiers (key_hash->keymap, &modifiers) &&
 430               ((modifiers & ~consumed_modifiers & mask & ~vmods) == (state & ~consumed_modifiers & mask & ~vmods) ||
 431                (modifiers & ~consumed_modifiers & mask & ~xmods) == (state & ~consumed_modifiers & mask & ~xmods)))
 432             {
 433               gint i;
 434
 435               if (keyval == entry->keyval) /* Exact match */
 436                 {
 437                   GTK_NOTE (KEYBINDINGS,
 438                             g_message ("  found exact match, keyval = %u, modifiers = 0x%04x",
 439                                        entry->keyval, entry->modifiers));
 440
 441                   if (!have_exact)
 442                     {
 443                       g_slist_free (results);
 444                       results = NULL;
 445                     }
 446
 447                   have_exact = TRUE;
 448                   results = g_slist_prepend (results, entry);
 449                 }
 450
 451               if (!have_exact)
 452                 {
 453                   for (i = 0; i < entry->n_keys; i++)
 454                     {
 455                       if (entry->keys[i].keycode == hardware_keycode &&
 456                           entry->keys[i].level == level) /* Match for all but group */
 457                         {
 458                           GTK_NOTE (KEYBINDINGS,
 459                                     g_message ("  found group = %d, level = %d",
 460                                                entry->keys[i].group, entry->keys[i].level));
 461                           results = g_slist_prepend (results, entry);
 462                           break;
 463                         }
 464                     }
 465                 }
 466             }
 467
 468           tmp_list = tmp_list->next;
 469         }
 470     }
 471
 472   if (!have_exact && results)
 473     {
 474       /* If there are fuzzy matches, check that the current group doesn't also
 475        * define these keyvals; if yes, discard results because a widget up in
 476        * the stack may have an exact match and we don't want to 'steal' it.
 477        */
 478       guint oldkeyval = 0;
 479       GtkKeyHashEntry *keyhashentry;
 480
 481       results = sort_lookup_results_by_keyval (results);
 482       for (l = results; l; l = l->next)
 483         {
 484           keyhashentry = l->data;
 485           if (l == results || oldkeyval != keyhashentry->keyval)
 486             {
 487               oldkeyval = keyhashentry->keyval;
 488               if (keyval_in_group (key_hash->keymap, oldkeyval, group))
 489                 {
 490                   g_slist_free (results);
 491                   return NULL;
 492                 }
 493             }
 494         }
 495     }
 496
 497   results = sort_lookup_results (results);
 498   for (l = results; l; l = l->next)
 499     l->data = ((GtkKeyHashEntry *)l->data)->value;
 500
 501   return results;
 502 }
 503
 504 /**
 505  * _gtk_key_hash_lookup_keyval:
 506  * @key_hash: a #GtkKeyHash
 507  * @event: a #GtkEvent
 508  *
 509  * Looks up the best matching entry or entries in the hash table for a
 510  * given keyval/modifiers pair. It's better to use
 511  * _gtk_key_hash_lookup() if you have the original #GdkEventKey
 512  * available.  The results are sorted so that entries with less
 513  * modifiers come before entries with more modifiers.
 514  *
 515  * Return value: A #GSList of all matching entries.
 516  **/
 517 GSList *
 518 _gtk_key_hash_lookup_keyval (GtkKeyHash     *key_hash,
 519                              guint           keyval,
 520                              GdkModifierType modifiers)
 521 {
 522   GdkKeymapKey *keys;
 523   gint n_keys;
 524   GSList *results = NULL;
 525   GSList *l;
 526
 527   if (!keyval)                  /* Key without symbol */
 528     return NULL;
 529
 530   /* Find some random keycode for this keyval
 531    */
 532   gdk_keymap_get_entries_for_keyval (key_hash->keymap, keyval,
 533                                      &keys, &n_keys);
 534
 535   if (n_keys)
 536     {
 537       GHashTable *keycode_hash = key_hash_get_keycode_hash (key_hash);
 538       GSList *entries = g_hash_table_lookup (keycode_hash, GUINT_TO_POINTER (keys[0].keycode));
 539
 540       while (entries)
 541         {
 542           GtkKeyHashEntry *entry = entries->data;
 543
 544           if (entry->keyval == keyval && entry->modifiers == modifiers)
 545             results = g_slist_prepend (results, entry);
 546
 547           entries = entries->next;
 548         }
 549     }
 550
 551   g_free (keys);
 552
 553   results = sort_lookup_results (results);
 554   for (l = results; l; l = l->next)
 555     l->data = ((GtkKeyHashEntry *)l->data)->value;
 556
 557   return results;
 558 }