gtkkeyhash.c 14.9 KB
Newer Older
1 2
/* gtkkeyhash.c: Keymap aware matching of key bindings
 *
Cody Russell's avatar
Cody Russell committed
3
 * GTK - The GIMP Toolkit
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
 * Copyright (C) 2002, Red Hat Inc.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */
21
#include "config.h"
22 23 24 25 26 27 28 29 30 31
#include "gtkdebug.h"
#include "gtkkeyhash.h"

typedef struct _GtkKeyHashEntry GtkKeyHashEntry;

struct _GtkKeyHashEntry
{
  guint keyval;
  GdkModifierType modifiers;
  gpointer value;
32 33 34 35 36

  /* Set as a side effect of generating key_hash->keycode_hash
   */
  GdkKeymapKey *keys;		
  gint n_keys;
37 38 39 40 41 42 43
};

struct _GtkKeyHash
{
  GdkKeymap *keymap;
  GHashTable *keycode_hash;
  GHashTable *reverse_hash;
44
  GList *entries_list;
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
  GDestroyNotify destroy_notify;
};

static void
key_hash_clear_keycode (gpointer key,
			gpointer value,
			gpointer data)
{
  GSList *keys = value;
  g_slist_free (keys);
}

static void
key_hash_insert_entry (GtkKeyHash      *key_hash,
		       GtkKeyHashEntry *entry)
{
  gint i;

63
  g_free (entry->keys);
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
  gdk_keymap_get_entries_for_keyval (key_hash->keymap,
				     entry->keyval,
				     &entry->keys, &entry->n_keys);
  
  for (i = 0; i < entry->n_keys; i++)
    {
      GSList *old_keys = g_hash_table_lookup (key_hash->keycode_hash,
					      GUINT_TO_POINTER (entry->keys[i].keycode));
      old_keys = g_slist_prepend (old_keys, entry);
      g_hash_table_insert (key_hash->keycode_hash,
			   GUINT_TO_POINTER (entry->keys[i].keycode),
			   old_keys);
    }
}

79 80
static GHashTable *
key_hash_get_keycode_hash (GtkKeyHash *key_hash)
81
{
82 83 84 85 86 87 88 89 90 91 92 93 94
  if (!key_hash->keycode_hash)
    {
      GList *tmp_list;
  
      key_hash->keycode_hash = g_hash_table_new (g_direct_hash, NULL);
      
      /* Preserve the original insertion order
       */
      for (tmp_list = g_list_last (key_hash->entries_list);
	   tmp_list;
	   tmp_list = tmp_list->prev)
	key_hash_insert_entry (key_hash, tmp_list->data);
    }
95

96
  return key_hash->keycode_hash;
97 98 99
}

static void
100 101
key_hash_keys_changed (GdkKeymap  *keymap,
		       GtkKeyHash *key_hash)
102
{
103
  /* The keymap changed, so we have to regenerate the keycode hash
104
   */
105 106 107 108 109 110
  if (key_hash->keycode_hash)
    {
      g_hash_table_foreach (key_hash->keycode_hash, key_hash_clear_keycode, NULL);
      g_hash_table_destroy (key_hash->keycode_hash);
      key_hash->keycode_hash = NULL;
    }
111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
}

/**
 * _gtk_key_hash_new:
 * @keymap: a #GdkKeymap
 * @item_destroy_notify: function to be called when items are removed
 *   from the hash or %NULL.
 * 
 * Create a new key hash object for doing binding resolution. 
 * 
 * Return value: the newly created object. Free with _gtk_key_hash_free().
 **/
GtkKeyHash *
_gtk_key_hash_new (GdkKeymap      *keymap,
		   GDestroyNotify  item_destroy_notify)
{
  GtkKeyHash *key_hash = g_new (GtkKeyHash, 1);

  key_hash->keymap = keymap;
130
  g_signal_connect (keymap, "keys-changed",
131
		    G_CALLBACK (key_hash_keys_changed), key_hash);
132

133 134
  key_hash->entries_list = NULL;
  key_hash->keycode_hash = NULL;
135 136 137 138 139 140 141 142 143 144 145 146 147 148
  key_hash->reverse_hash = g_hash_table_new (g_direct_hash, NULL);
  key_hash->destroy_notify = item_destroy_notify;

  return key_hash;
}

static void
key_hash_free_entry (GtkKeyHash      *key_hash,
		     GtkKeyHashEntry *entry)
{
  if (key_hash->destroy_notify)
    (*key_hash->destroy_notify) (entry->value);
  
  g_free (entry->keys);
149
  g_slice_free (GtkKeyHashEntry, entry);
150 151 152
}

static void
153
key_hash_free_entry_foreach (gpointer value,
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
			     gpointer data)
{
  GtkKeyHashEntry *entry = value;
  GtkKeyHash *key_hash = data;

  key_hash_free_entry (key_hash, entry);
}

/**
 * gtk_key_hash_free:
 * @key_hash: a #GtkKeyHash
 * 
 * Destroys a key hash created with gtk_key_hash_new()
 **/
void
_gtk_key_hash_free (GtkKeyHash *key_hash)
{
  g_signal_handlers_disconnect_by_func (key_hash->keymap,
Manish Singh's avatar
Manish Singh committed
172 173
					key_hash_keys_changed,
					key_hash);
174

175 176 177 178 179 180
  if (key_hash->keycode_hash)
    {
      g_hash_table_foreach (key_hash->keycode_hash, key_hash_clear_keycode, NULL);
      g_hash_table_destroy (key_hash->keycode_hash);
    }
  
181 182
  g_hash_table_destroy (key_hash->reverse_hash);

183 184 185
  g_list_foreach (key_hash->entries_list, key_hash_free_entry_foreach, key_hash);
  g_list_free (key_hash->entries_list);
  
186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203
  g_free (key_hash);
}

/**
 * _gtk_key_hash_add_entry:
 * @key_hash: a #GtkKeyHash
 * @keyval: key symbol for this binding
 * @modifiers: modifiers for this binding
 * @value: value to insert in the key hash
 * 
 * Inserts a pair of key symbol and modifier mask into the key hash. 
 **/
void
_gtk_key_hash_add_entry (GtkKeyHash      *key_hash,
			 guint            keyval,
			 GdkModifierType  modifiers,
			 gpointer         value)
{
204
  GtkKeyHashEntry *entry = g_slice_new (GtkKeyHashEntry);
205 206 207 208

  entry->value = value;
  entry->keyval = keyval;
  entry->modifiers = modifiers;
209
  entry->keys = NULL;
210

211 212 213 214 215
  key_hash->entries_list = g_list_prepend (key_hash->entries_list, entry);
  g_hash_table_insert (key_hash->reverse_hash, value, key_hash->entries_list);

  if (key_hash->keycode_hash)
    key_hash_insert_entry (key_hash, entry);
216 217 218 219 220 221 222 223 224 225 226 227 228 229
}

/**
 * _gtk_key_hash_remove_entry:
 * @key_hash: a #GtkKeyHash
 * @value: value previously added with _gtk_key_hash_add_entry()
 * 
 * Removes a value previously added to the key hash with
 * _gtk_key_hash_add_entry().
 **/
void
_gtk_key_hash_remove_entry (GtkKeyHash *key_hash,
			    gpointer    value)
{
230 231 232
  GList *entry_node = g_hash_table_lookup (key_hash->reverse_hash, value);
  
  if (entry_node)
233
    {
234
      GtkKeyHashEntry *entry = entry_node->data;
235

236
      if (key_hash->keycode_hash)
237
	{
238 239 240
	  gint i;
	  
	  for (i = 0; i < entry->n_keys; i++)
241
	    {
242 243 244 245 246 247 248 249 250 251 252 253 254 255
	      GSList *old_keys = g_hash_table_lookup (key_hash->keycode_hash,
						      GUINT_TO_POINTER (entry->keys[i].keycode));
	      
	      GSList *new_keys = g_slist_remove (old_keys, entry);
	      if (new_keys != old_keys)
		{
		  if (new_keys)
		    g_hash_table_insert (key_hash->keycode_hash,
					 GUINT_TO_POINTER (entry->keys[i].keycode),
					 new_keys);
		  else
		    g_hash_table_remove (key_hash->keycode_hash,
					 GUINT_TO_POINTER (entry->keys[i].keycode));
		}
256 257
	    }
	}
258 259 260
	  
      g_hash_table_remove (key_hash->reverse_hash, entry_node);
      key_hash->entries_list = g_list_delete_link (key_hash->entries_list, entry_node);
261 262 263 264 265

      key_hash_free_entry (key_hash, entry);
    }
}

266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305
static gint
lookup_result_compare (gconstpointer a,
		       gconstpointer b)
{
  const GtkKeyHashEntry *entry_a = a;
  const GtkKeyHashEntry *entry_b = b;
  guint modifiers;

  gint n_bits_a = 0;
  gint n_bits_b = 0;

  modifiers = entry_a->modifiers;
  while (modifiers)
    {
      if (modifiers & 1)
	n_bits_a++;
      modifiers >>= 1;
    }

  modifiers = entry_b->modifiers;
  while (modifiers)
    {
      if (modifiers & 1)
	n_bits_b++;
      modifiers >>= 1;
    }

  return n_bits_a < n_bits_b ? -1 : (n_bits_a == n_bits_b ? 0 : 1);
  
}

/* Sort a list of results so that matches with less modifiers come
 * before matches with more modifiers
 */
static GSList *
sort_lookup_results (GSList *slist)
{
  return g_slist_sort (slist, lookup_result_compare);
}

306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353
static gint
lookup_result_compare_by_keyval (gconstpointer a,
		                 gconstpointer b)
{
  const GtkKeyHashEntry *entry_a = a;
  const GtkKeyHashEntry *entry_b = b;

  if (entry_a->keyval < entry_b->keyval)
	return -1;
  else if (entry_a->keyval > entry_b->keyval)
	return 1;
  else
	return 0;
}

static GSList *
sort_lookup_results_by_keyval (GSList *slist)
{
  return g_slist_sort (slist, lookup_result_compare_by_keyval);
}

/* Return true if keyval is defined in keyboard group
 */
static gboolean 
keyval_in_group (GdkKeymap  *keymap,
                 guint      keyval,
                 gint       group)
{                 
  GtkKeyHashEntry entry;
  gint i;

  gdk_keymap_get_entries_for_keyval (keymap,
				     keyval,
				     &entry.keys, &entry.n_keys);

  for (i = 0; i < entry.n_keys; i++)
    {
      if (entry.keys[i].group == group)
        {
          g_free (entry.keys);
          return TRUE;
        }
    }

  g_free (entry.keys);
  return FALSE;
}

354 355 356 357 358
/**
 * _gtk_key_hash_lookup:
 * @key_hash: a #GtkKeyHash
 * @hardware_keycode: hardware keycode field from a #GdkEventKey
 * @state: state field from a #GdkEventKey
359 360
 * @mask: mask of modifiers to consider when matching against the
 *        modifiers in entries.
361 362 363
 * @group: group field from a #GdkEventKey
 * 
 * Looks up the best matching entry or entries in the hash table for
364 365
 * a given event. The results are sorted so that entries with less
 * modifiers come before entries with more modifiers.
366
 * 
367 368 369 370 371 372 373 374 375
 * The matches returned by this function can be exact (i.e. keycode, level
 * and group all match) or fuzzy (i.e. keycode and level match, but group
 * does not). As long there are any exact matches, only exact matches
 * are returned. If there are no exact matches, fuzzy matches will be
 * returned, as long as they are not shadowing a possible exact match.
 * This means that fuzzy matches won't be considered if their keyval is 
 * present in the current group.
 * 
 * Return value: A #GSList of matching entries.
376 377 378 379 380
 **/
GSList *
_gtk_key_hash_lookup (GtkKeyHash      *key_hash,
		      guint16          hardware_keycode,
		      GdkModifierType  state,
381
		      GdkModifierType  mask,
382 383
		      gint             group)
{
384 385
  GHashTable *keycode_hash = key_hash_get_keycode_hash (key_hash);
  GSList *keys = g_hash_table_lookup (keycode_hash, GUINT_TO_POINTER ((guint)hardware_keycode));
386
  GSList *results = NULL;
387
  GSList *l;
388 389 390 391
  gboolean have_exact = FALSE;
  guint keyval;
  gint effective_group;
  gint level;
392
  GdkModifierType modifiers;
393
  GdkModifierType consumed_modifiers;
394 395
  const GdkModifierType xmods = GDK_MOD2_MASK|GDK_MOD3_MASK|GDK_MOD4_MASK|GDK_MOD5_MASK;
  const GdkModifierType vmods = GDK_SUPER_MASK|GDK_HYPER_MASK|GDK_META_MASK;
396

397 398 399
  /* We don't want Caps_Lock to affect keybinding lookups.
   */
  state &= ~GDK_LOCK_MASK;
400 401 402

  gdk_keymap_map_virtual_modifiers (key_hash->keymap, &mask);

403 404 405
  gdk_keymap_translate_keyboard_state (key_hash->keymap,
				       hardware_keycode, state, group,
				       &keyval, &effective_group, &level, &consumed_modifiers);
406
  gdk_keymap_add_virtual_modifiers (key_hash->keymap, &state);
407 408 409 410 411 412 413 414 415 416 417 418

  GTK_NOTE (KEYBINDINGS,
	    g_message ("Looking up keycode = %u, modifiers = 0x%04x,\n"
		       "    keyval = %u, group = %d, level = %d, consumed_modifiers = 0x%04x",
		       hardware_keycode, state, keyval, effective_group, level, consumed_modifiers));

  if (keys)
    {
      GSList *tmp_list = keys;
      while (tmp_list)
	{
	  GtkKeyHashEntry *entry = tmp_list->data;
419 420 421

	  /* If the virtual Super, Hyper or Meta modifiers are present,
	   * they will also be mapped to some of the Mod2 - Mod5 modifiers,
422
	   * so we compare them twice, ignoring either set.
423 424 425 426
	   * We accept combinations involving virtual modifiers only if they
	   * are mapped to separate modifiers; i.e. if Super and Hyper are
	   * both mapped to Mod4, then pressing a key that is mapped to Mod4
	   * will not match a Super+Hyper entry.
427
	   */
428 429 430 431
          modifiers = entry->modifiers;
          if (gdk_keymap_map_virtual_modifiers (key_hash->keymap, &modifiers) &&
	      ((modifiers & ~consumed_modifiers & mask & ~vmods) == (state & ~consumed_modifiers & mask & ~vmods) ||
	       (modifiers & ~consumed_modifiers & mask & ~xmods) == (state & ~consumed_modifiers & mask & ~xmods)))
432 433 434 435 436 437 438 439
	    {
	      gint i;

	      if (keyval == entry->keyval) /* Exact match */
		{
		  GTK_NOTE (KEYBINDINGS,
			    g_message ("  found exact match, keyval = %u, modifiers = 0x%04x",
				       entry->keyval, entry->modifiers));
440

441 442 443 444 445 446 447
		  if (!have_exact)
		    {
		      g_slist_free (results);
		      results = NULL;
		    }

		  have_exact = TRUE;
448
		  results = g_slist_prepend (results, entry);
449 450 451 452 453 454 455 456 457 458 459 460
		}

	      if (!have_exact)
		{
		  for (i = 0; i < entry->n_keys; i++)
		    {
		      if (entry->keys[i].keycode == hardware_keycode &&
			  entry->keys[i].level == level) /* Match for all but group */
			{
			  GTK_NOTE (KEYBINDINGS,
				    g_message ("  found group = %d, level = %d",
					       entry->keys[i].group, entry->keys[i].level));
461
			  results = g_slist_prepend (results, entry);
462 463 464 465 466 467 468 469 470 471
			  break;
			}
		    }
		}
	    }

	  tmp_list = tmp_list->next;
	}
    }

472 473 474 475 476 477
  if (!have_exact && results) 
    {
      /* If there are fuzzy matches, check that the current group doesn't also 
       * define these keyvals; if yes, discard results because a widget up in 
       * the stack may have an exact match and we don't want to 'steal' it.
       */
478
      guint oldkeyval = 0;
479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496
      GtkKeyHashEntry *keyhashentry;

      results = sort_lookup_results_by_keyval (results);
      for (l = results; l; l = l->next)
        {
          keyhashentry = l->data;
          if (l == results || oldkeyval != keyhashentry->keyval)
            {
              oldkeyval = keyhashentry->keyval;
              if (keyval_in_group (key_hash->keymap, oldkeyval, group))
                {
       	          g_slist_free (results);
       	          return NULL;
                }
            }
        }
    }
    
497 498 499 500 501
  results = sort_lookup_results (results);
  for (l = results; l; l = l->next)
    l->data = ((GtkKeyHashEntry *)l->data)->value;

  return results;
502 503 504 505 506 507 508 509 510 511
}

/**
 * _gtk_key_hash_lookup_keyval:
 * @key_hash: a #GtkKeyHash
 * @event: a #GtkEvent
 * 
 * Looks up the best matching entry or entries in the hash table for a
 * given keyval/modifiers pair. It's better to use
 * _gtk_key_hash_lookup() if you have the original #GdkEventKey
512 513
 * available.  The results are sorted so that entries with less
 * modifiers come before entries with more modifiers.
514 515 516 517 518 519 520 521 522 523 524
 * 
 * Return value: A #GSList of all matching entries.
 **/
GSList *
_gtk_key_hash_lookup_keyval (GtkKeyHash     *key_hash,
			     guint           keyval,
			     GdkModifierType modifiers)
{
  GdkKeymapKey *keys;
  gint n_keys;
  GSList *results = NULL;
525
  GSList *l;
526 527 528 529

  if (!keyval)			/* Key without symbol */
    return NULL;

530
  /* Find some random keycode for this keyval
531 532 533 534 535 536
   */
  gdk_keymap_get_entries_for_keyval (key_hash->keymap, keyval,
				     &keys, &n_keys);

  if (n_keys)
    {
537 538
      GHashTable *keycode_hash = key_hash_get_keycode_hash (key_hash);
      GSList *entries = g_hash_table_lookup (keycode_hash, GUINT_TO_POINTER (keys[0].keycode));
539 540 541 542 543 544

      while (entries)
	{
	  GtkKeyHashEntry *entry = entries->data;

	  if (entry->keyval == keyval && entry->modifiers == modifiers)
545
	    results = g_slist_prepend (results, entry);
546 547 548 549 550 551 552

	  entries = entries->next;
	}
    }

  g_free (keys);
	  
553 554 555 556 557
  results = sort_lookup_results (results);
  for (l = results; l; l = l->next)
    l->data = ((GtkKeyHashEntry *)l->data)->value;

  return results;
558
}