Commit de4098a02486beb2408f6b8d3c94316de0dbbffc
2012-09-14T17:50:31
keysym-utf8: Optimise the keysym to utf8 lookup This change adds range checks based on the lowest keysym and highest keysym in the table. This allows a quick check to be applied to identify if the keysym is inside the table. To really give value to this optimisation the table is split to have a separate table for the keypad keysyms. The test suite passes with this change. Signed-off-by: Rob Bradford <rob@linux.intel.com>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
diff --git a/src/keysym-utf.c b/src/keysym-utf.c
index ed18035..8bf04f9 100644
--- a/src/keysym-utf.c
+++ b/src/keysym-utf.c
@@ -38,10 +38,12 @@
#include "xkbcommon/xkbcommon.h"
#include "utils.h"
-const struct codepair {
+struct codepair {
xkb_keysym_t keysym;
uint16_t ucs;
-} keysymtab[] = {
+};
+
+const struct codepair keysymtab[] = {
{ 0x01a1, 0x0104 }, /* Aogonek Ą LATIN CAPITAL LETTER A WITH OGONEK */
{ 0x01a2, 0x02d8 }, /* breve ˘ BREVE */
{ 0x01a3, 0x0141 }, /* Lstroke Ł LATIN CAPITAL LETTER L WITH STROKE */
@@ -829,7 +831,9 @@ const struct codepair {
{ 0x20aa, 0x20aa }, /* NewSheqelSign ₪ NEW SHEQEL SIGN */
{ 0x20ab, 0x20ab }, /* DongSign ₫ DONG SIGN */
{ 0x20ac, 0x20ac }, /* EuroSign € EURO SIGN */
+};
+const struct codepair keysymtab_kp[] = {
{ 0xff80, 0x0020 }, /* KP_Space SPACE */
{ 0xffaa, 0x002a }, /* KP_Multiply * ASTERISK */
{ 0xffab, 0x002b }, /* KP_Plus + PLUS SIGN */
@@ -843,13 +847,39 @@ const struct codepair {
{ 0xffbd, 0x003d }, /* KP_Equal = EQUAL SIGN */
};
-XKB_EXPORT uint32_t
-xkb_keysym_to_utf32(xkb_keysym_t keysym)
+/* binary search with range check */
+static uint32_t
+bin_search(const struct codepair *table, size_t length, xkb_keysym_t keysym)
{
int min = 0;
- int max = sizeof(keysymtab) / sizeof(struct codepair) - 1;
+ int max = length;
int mid;
+ if (keysym < table[0].keysym || keysym > table[length].keysym)
+ return 0;
+
+ /* binary search in table */
+ while (max >= min) {
+ mid = (min + max) / 2;
+ if (table[mid].keysym < keysym)
+ min = mid + 1;
+ else if (table[mid].keysym > keysym)
+ max = mid - 1;
+ else /* found it */
+ return table[mid].ucs;
+ }
+
+ /* no matching Unicode value found in table */
+ return 0;
+}
+
+#define N_ELEMENTS(x) sizeof(x) / sizeof(x[0])
+
+XKB_EXPORT uint32_t
+xkb_keysym_to_utf32(xkb_keysym_t keysym)
+{
+ uint32_t retval = 0;
+
/* first check for Latin-1 characters (1:1 mapping) */
if ((keysym >= 0x0020 && keysym <= 0x007e) ||
(keysym >= 0x00a0 && keysym <= 0x00ff))
@@ -862,19 +892,14 @@ xkb_keysym_to_utf32(xkb_keysym_t keysym)
if ((keysym & 0xff000000) == 0x01000000)
return keysym & 0x00ffffff;
- /* binary search in table */
- while (max >= min) {
- mid = (min + max) / 2;
- if (keysymtab[mid].keysym < keysym)
- min = mid + 1;
- else if (keysymtab[mid].keysym > keysym)
- max = mid - 1;
- else /* found it */
- return keysymtab[mid].ucs;
- }
+ /* search smaller keypad table */
+ retval = bin_search(keysymtab_kp, N_ELEMENTS(keysymtab_kp) - 1, keysym);
- /* no matching Unicode value found */
- return 0;
+ /* search main table */
+ if (!retval)
+ retval = bin_search(keysymtab, N_ELEMENTS(keysymtab) - 1, keysym);
+
+ return retval;
}
/*