… | |
… | |
119 | |
119 | |
120 | //////////////////////////////////////////////////////////////////////////////// |
120 | //////////////////////////////////////////////////////////////////////////////// |
121 | keyboard_manager::keyboard_manager () |
121 | keyboard_manager::keyboard_manager () |
122 | { |
122 | { |
123 | keymap.reserve (256); |
123 | keymap.reserve (256); |
124 | hash[0] = 1; // hash[0] != 0 indicates uninitialized data |
124 | hash [0] = 1; // hash[0] != 0 indicates uninitialized data |
125 | } |
125 | } |
126 | |
126 | |
127 | keyboard_manager::~keyboard_manager () |
127 | keyboard_manager::~keyboard_manager () |
128 | { |
128 | { |
129 | clear (); |
129 | clear (); |
… | |
… | |
322 | { |
322 | { |
323 | for (unsigned int i = 0; i < keymap.size (); ++i) |
323 | for (unsigned int i = 0; i < keymap.size (); ++i) |
324 | { |
324 | { |
325 | for (unsigned int j = 0; j < i; ++j) |
325 | for (unsigned int j = 0; j < i; ++j) |
326 | { |
326 | { |
327 | if (keymap[i] == keymap[j]) |
327 | if (keymap [i] == keymap [j]) |
328 | { |
328 | { |
329 | while (keymap[i] == keymap.back ()) |
329 | while (keymap [i] == keymap.back ()) |
330 | keymap.pop_back (); |
330 | keymap.pop_back (); |
331 | |
331 | |
332 | if (i < keymap.size ()) |
332 | if (i < keymap.size ()) |
333 | { |
333 | { |
334 | keymap[i] = keymap.back (); |
334 | keymap[i] = keymap.back (); |
… | |
… | |
352 | memset (hash_budget_counter, 0, sizeof (hash_budget_counter)); |
352 | memset (hash_budget_counter, 0, sizeof (hash_budget_counter)); |
353 | |
353 | |
354 | // count keysyms for corresponding hash budgets |
354 | // count keysyms for corresponding hash budgets |
355 | for (i = 0; i < keymap.size (); ++i) |
355 | for (i = 0; i < keymap.size (); ++i) |
356 | { |
356 | { |
357 | assert (keymap[i]); |
357 | assert (keymap [i]); |
358 | hashkey = (keymap[i]->keysym & KEYSYM_HASH_MASK); |
358 | hashkey = (keymap [i]->keysym & KEYSYM_HASH_MASK); |
359 | ++hash_budget_size[hashkey]; |
359 | ++hash_budget_size [hashkey]; |
360 | } |
360 | } |
361 | |
361 | |
362 | // keysym A with range>1 is counted one more time for |
362 | // keysym A with range>1 is counted one more time for |
363 | // every keysym B lies in its range |
363 | // every keysym B lies in its range |
364 | for (i = 0; i < keymap.size (); ++i) |
364 | for (i = 0; i < keymap.size (); ++i) |
365 | { |
365 | { |
366 | if (keymap[i]->range > 1) |
366 | if (keymap[i]->range > 1) |
367 | { |
367 | { |
368 | for (int j = min (keymap[i]->range, KEYSYM_HASH_BUDGETS) - 1; j > 0; --j) |
368 | for (int j = min (keymap [i]->range, KEYSYM_HASH_BUDGETS) - 1; j > 0; --j) |
369 | { |
369 | { |
370 | hashkey = ((keymap[i]->keysym + j) & KEYSYM_HASH_MASK); |
370 | hashkey = ((keymap [i]->keysym + j) & KEYSYM_HASH_MASK); |
371 | if (hash_budget_size[hashkey]) |
371 | if (hash_budget_size [hashkey]) |
372 | ++hash_budget_size[hashkey]; |
372 | ++hash_budget_size [hashkey]; |
373 | } |
373 | } |
374 | } |
374 | } |
375 | } |
375 | } |
376 | |
376 | |
377 | // now we know the size of each budget |
377 | // now we know the size of each budget |
378 | // compute the index of each budget |
378 | // compute the index of each budget |
379 | hash[0] = 0; |
379 | hash [0] = 0; |
380 | for (index = 0, i = 1; i < KEYSYM_HASH_BUDGETS; ++i) |
380 | for (index = 0, i = 1; i < KEYSYM_HASH_BUDGETS; ++i) |
381 | { |
381 | { |
382 | index += hash_budget_size[i - 1]; |
382 | index += hash_budget_size [i - 1]; |
383 | hash[i] = (hash_budget_size[i] ? index : hash[i - 1]); |
383 | hash[i] = (hash_budget_size [i] ? index : hash [i - 1]); |
384 | } |
384 | } |
385 | |
385 | |
386 | // and allocate just enough space |
386 | // and allocate just enough space |
387 | //sorted_keymap.reserve (hash[i - 1] + hash_budget_size[i - 1]); |
387 | //sorted_keymap.reserve (hash[i - 1] + hash_budget_size[i - 1]); |
388 | sorted_keymap.insert (sorted_keymap.begin (), index + hash_budget_size[i - 1], 0); |
388 | sorted_keymap.insert (sorted_keymap.begin (), index + hash_budget_size [i - 1], 0); |
389 | |
389 | |
390 | // fill in sorted_keymap |
390 | // fill in sorted_keymap |
391 | // it is sorted in each budget |
391 | // it is sorted in each budget |
392 | for (i = 0; i < keymap.size (); ++i) |
392 | for (i = 0; i < keymap.size (); ++i) |
393 | { |
393 | { |
394 | for (int j = min (keymap[i]->range, KEYSYM_HASH_BUDGETS) - 1; j >= 0; --j) |
394 | for (int j = min (keymap [i]->range, KEYSYM_HASH_BUDGETS) - 1; j >= 0; --j) |
395 | { |
395 | { |
396 | hashkey = ((keymap[i]->keysym + j) & KEYSYM_HASH_MASK); |
396 | hashkey = ((keymap [i]->keysym + j) & KEYSYM_HASH_MASK); |
397 | |
397 | |
398 | if (hash_budget_size[hashkey]) |
398 | if (hash_budget_size [hashkey]) |
399 | { |
399 | { |
400 | index = hash[hashkey] + hash_budget_counter[hashkey]; |
400 | index = hash [hashkey] + hash_budget_counter [hashkey]; |
401 | |
401 | |
402 | while (index > hash[hashkey] |
402 | while (index > hash [hashkey] |
403 | && compare_priority (keymap[i], sorted_keymap[index - 1]) > 0) |
403 | && compare_priority (keymap [i], sorted_keymap [index - 1]) > 0) |
404 | { |
404 | { |
405 | sorted_keymap[index] = sorted_keymap[index - 1]; |
405 | sorted_keymap [index] = sorted_keymap [index - 1]; |
406 | --index; |
406 | --index; |
407 | } |
407 | } |
408 | |
408 | |
409 | sorted_keymap[index] = keymap[i]; |
409 | sorted_keymap [index] = keymap [i]; |
410 | ++hash_budget_counter[hashkey]; |
410 | ++hash_budget_counter [hashkey]; |
411 | } |
411 | } |
412 | } |
412 | } |
413 | } |
413 | } |
414 | |
414 | |
415 | keymap.swap (sorted_keymap); |
415 | keymap.swap (sorted_keymap); |
… | |
… | |
417 | #if defined (DEBUG_STRICT) || defined (DEBUG_KEYBOARD) |
417 | #if defined (DEBUG_STRICT) || defined (DEBUG_KEYBOARD) |
418 | // check for invariants |
418 | // check for invariants |
419 | for (i = 0; i < KEYSYM_HASH_BUDGETS; ++i) |
419 | for (i = 0; i < KEYSYM_HASH_BUDGETS; ++i) |
420 | { |
420 | { |
421 | index = hash[i]; |
421 | index = hash[i]; |
422 | for (int j = 0; j < hash_budget_size[i]; ++j) |
422 | for (int j = 0; j < hash_budget_size [i]; ++j) |
423 | { |
423 | { |
424 | if (keymap[index + j]->range == 1) |
424 | if (keymap [index + j]->range == 1) |
425 | assert (i == (keymap[index + j]->keysym & KEYSYM_HASH_MASK)); |
425 | assert (i == (keymap [index + j]->keysym & KEYSYM_HASH_MASK)); |
426 | |
426 | |
427 | if (j) |
427 | if (j) |
428 | assert (compare_priority (keymap[index + j - 1], |
428 | assert (compare_priority (keymap [index + j - 1], |
429 | keymap[index + j]) >= 0); |
429 | keymap [index + j]) >= 0); |
430 | } |
430 | } |
431 | } |
431 | } |
432 | |
432 | |
433 | // this should be able to detect most possible bugs |
433 | // this should be able to detect most possible bugs |
434 | for (i = 0; i < sorted_keymap.size (); ++i) |
434 | for (i = 0; i < sorted_keymap.size (); ++i) |
… | |
… | |
436 | keysym_t *a = sorted_keymap[i]; |
436 | keysym_t *a = sorted_keymap[i]; |
437 | for (int j = 0; j < a->range; ++j) |
437 | for (int j = 0; j < a->range; ++j) |
438 | { |
438 | { |
439 | int index = find_keysym (a->keysym + j, a->state & OtherModMask); |
439 | int index = find_keysym (a->keysym + j, a->state & OtherModMask); |
440 | assert (index >= 0); |
440 | assert (index >= 0); |
441 | keysym_t *b = keymap[index]; |
441 | keysym_t *b = keymap [index]; |
442 | assert (i == (signed) index || // the normally expected result |
442 | assert (i == (signed) index || // the normally expected result |
443 | (a->keysym + j) >= b->keysym && (a->keysym + j) <= (b->keysym + b->range) && compare_priority (a, b) <= 0); // is effectively the same |
443 | (a->keysym + j) >= b->keysym && (a->keysym + j) <= (b->keysym + b->range) && compare_priority (a, b) <= 0); // is effectively the same |
444 | } |
444 | } |
445 | } |
445 | } |
446 | #endif |
446 | #endif |
… | |
… | |
452 | int hashkey = keysym & KEYSYM_HASH_MASK; |
452 | int hashkey = keysym & KEYSYM_HASH_MASK; |
453 | unsigned int index = hash [hashkey]; |
453 | unsigned int index = hash [hashkey]; |
454 | |
454 | |
455 | for (; index < keymap.size (); ++index) |
455 | for (; index < keymap.size (); ++index) |
456 | { |
456 | { |
457 | keysym_t *key = keymap[index]; |
457 | keysym_t *key = keymap [index]; |
458 | assert (key); |
458 | assert (key); |
459 | |
459 | |
460 | if (key->keysym <= keysym && key->keysym + key->range > keysym |
460 | if (key->keysym <= keysym && key->keysym + key->range > keysym |
461 | // match only the specified bits in state and ignore others |
461 | // match only the specified bits in state and ignore others |
462 | && (key->state & OtherModMask) == (key->state & state)) |
462 | && (key->state & OtherModMask) == (key->state & state)) |