eli@haddock.ima.isc.com (Elias Israel) (08/28/89)
While working on a program that makes heavy use of XRebindKeysym and
XLookupString recently, I was bothered by certain inefficiencies in
these routines that made my work somewhat more difficult than it ought
to have been. After giving the matter some thought, I think that I have
come up with an implementation that addresses some of the problems that
I found. This stuff is all from X11R3. I haven't yet seen the R4 tape
(although we have it) so I don't know if any of this has changed there.
Some history:
I have been working for some time on a program that must provide
emulation of a particular terminal type. Necessarily, this means that
many of the function keys and other miscellaneous keys have to be
rebound using XRebindKeysym so that they send the right strings when
the users depresses them.
On many terminals, the miscellaneous keys have only one or two
different sequences that they send. Rarely are they affected by more
than three different modifier keys and usually, one modifier key will
take precedence over others. For example, Ctrl+Meta+'a' will often just
send ^A, ignoring the meta key completely. Some keys will send the same
sequence no matter what modifier keys are held down. For example, the
arrow keys on most terminals never change their tune, no matter what
other keys you press.
Attempting to duplicate this behaviour with calls to XRebindKeysym can
be quite difficult because of the way that XRebindKeysym and
XLookupString work. Keys that always send the same sequence,
regardless of modifiers, require many calls to XRebindKeysym in order
to make sure that all of the possible combinations are placed into the
lookup table for XLookupString. Further, because XLookupString uses a
linear search to find keysyms, each call to XRebindKeysym causes
XLookupString to run somewhat slower. In programs like my terminal
emulator, this can add up very quickly because of the number of keys to
be rebound and the number of modifiers combinations that exist.
Even if you assume that only Control, Shift, Caps, and Mod1 can be
pressed by the user, a key that must send the same sequence regardless
of what modifiers are pressed requires 15 calls to XRebindKeysym. If
this process is repeated for all of the miscellaneous keys (function
keys, keypad keys, arrow keys, other special keys), literally hundreds
of calls to XRebindKeysym may be necessary.
The Problems:
(1) XRebindKeysym has parameters that don't seem to make sense. In
order to rebind a keysym when a particular set of bits are on in
the state member of the XEvent structure, the programmer has to
send XRebindKeysym an array of the modifier keysyms instead of
simply sending the desired state mask. Typically, in order to be
fully portable, you have to query the server to find out what
keysyms cause the state mask that you want to be generated.
However, XRebindKeysym doesn't really care about what keys are used
to modify the rebound keysym, only the state bits that they
generate. So it decomposes the keysyms you give it back into state
bits, essentially reversing the lookup that you had to do in order
to get the right modifier keysyms in the first place.
(2) XRebindKeysym uses a singly-linked list of data structures to
maintain the list of rebound keysyms. The data structure itself is
somewhat inefficient. It keeps the list of modifier keysyms that
you passed in, even though their only use is to compute the state
bits.
(3) When XLookupString has to lookup a keysym to see if it has been
rebound, it has to to a linear search through all of the rebound
keysyms. The data structures aren't sorted at all and they're in a
data structure that prevents anything faster than O(n) lookup times
(the linked list). And you pay this price *every time you call
XLookupString*.
(4) XLookupString's algorithm for determining a match in the list of
rebound keysyms is exact equality of both the keysym and the state
bits. This means that if you want a certain keysym to send a given
string no matter what the modifiers are doing, you have to call
XRebindKeysym with every possible combination of modifier keysyms.
This can balloon very quickly into a lot of calls and a large list
for XLookupString to sift through on every keysym, especially if
you have many keys that you want to bind.
Changes that I propose:
(1) The data structure for maintaining keysym mappings should be changed
for speed and flexibility. I propose this:
struct _XKeySymMap {
int nEntries; /* number of elems in array below */
struct _XKeySymEntry *entries; /* array of _XKeySymEntry structs */
}
struct _XKeySymEntry {
KeySym keysym; /* keysym this entry maps */
int nTranslations; /* number of items in list below */
struct _XKeyTranslation *translations; /* list of key translations */
}
struct _XKeyTranslation {
struct _XKeyTranslation *next; /* next item in list */
unsigned state; /* state mask (modifiers) for keysym */
unsigned mask; /* mask for state bits above:
* bits that are on in this member
* specify which bits of the state
* mask we care about for this
* translation
*/
char *string; /* the string to send */
int len; /* number of bytes in the string */
}
(2) The parameters of XRebindKeysym should be changed for ease of use.
I propose:
XRebindKeysym(display, keysym, state, mask, string, len)
Display *display; /* the display we're working on */
Keysym keysym; /* the keysym we want to bind */
unsigned state; /* the value of the state bits */
unsigned mask; /* mask for state bits */
char *string; /* the string to send */
int len; /* length of the string in chars */
The state parameter should encode the values of the state bits
corresponding to the state member of the XEvent structure. The
mask parameter determines which of the state bits are significant.
For example, if the programmer wants to modify the behaviour of
the F1 key so that it sends "\033A" when pressed by itself and
"\033B" when pressed with control (regardless of any other modifiers),
these two calls would be made:
XRebindKeysym(display, XK_F1, ControlMask, ControlMask, "\033B", 2);
XRebindKeysym(display, XK_F1, ~ControlMask, ControlMask, "\033A", 2);
The mask parameter determines which bits of the state mask are checked
when XLookupString is searching for possible bindings. Each call
to XRebindKeysym adds another _XKeyTranslation struct to the
end of the entry for the appropriate keysym. This means that the
programmer must be careful to call XRebindKeysym with the more specific
modifier requirements before the more general ones. For example,
the code fragment:
XRebindKeysym(display, XK_F1, ControlMask, ControlMask, "\033A", 2);
XRebindKeysym(display, XK_F1, ControlMask|Mod1Mask,
Mod1Mask|ControlMask, "\033B", 2);
would probably not do what is desired. Whenever the conditions for
the second binding are true, the conditions of the first binding
are also true, since the second binding contains all of the requirements
of the first. Since the first binding will be checked before the second,
the second binding will never be used because the first will always
trigger before it.
XRebindKeysym will work something like this:
1. Find the KeyEntry for the keysym specified
2. If it was not found, enlarge the array of
entries and insert the new one into the array,
sorted by keysym number
3. Append to the key entry a new translation that
encodes the state, mask, and the string to send
(3) Changes to XLookupString:
XLookupString will work something like this:
1. Find an entry in the map that corresponds to
the keysym we're looking up.
2. If it was found:
a. look through each of the translations
and check to see if
(event->state & translation->mask) == translation->state
b. if so, return the string listed
3. Else, return the typical encoding, if any
Note that because the entries are sorted by keysym, each lookup can be
done with a quick and dirty binary search, which gives O(log(n))
performance. Linear search is only used for scanning through the
translations for a single keysym. Typically, this list will be fewer
than 10 items, so this search time should be quite fast. Even if you
could bind every keysym now defined in <X11/keysymdef.h>, its entry
could be found in 10 probes or fewer.
For anyone who's kept reading this far, I have this question:
First, does this scheme make sense? Are there any cases or requirements
that I have forgotten?
Subject to the arguments on the net that follow this, I intend to make
this proposal somewhat more formally to the X Consortium.
Elias Israel | "Justice, n. A commodity which in more or
Interactive Systems Corp. | less adulterated condition the State sells
Boston, MA | to the citizen as a reward for his allegiance,
..!ima!haddock!eli | taxes, and personal service."
| -- Ambrose Bierce, _The Devil's Dictionary_ rws@EXPO.LCS.MIT.EDU (Bob Scheifler) (08/29/89)
I haven't yet seen the R4 tape
You don't have an "R4" tape, you have an alpha release.
Typically, in order to be
fully portable, you have to query the server to find out what
keysyms cause the state mask that you want to be generated.
That's because you're thinking in terms of modifier bits, while the Xlib
interface is in terms of modifiers. For example, the client might well
want to deal with "Hyper-A", without regard to which modifier bit Hyper
is assigned to. I'm not saying a bit-interface doesn't make sense, but
a keysym-interface also makes sense.
It keeps the list of modifier keysyms that
you passed in, even though their only use is to compute the state bits.
No, they are also used if XRefreshKeyboardMapping is called.
The data structure for maintaining keysym mappings should be changed
for speed and flexibility.
You are encouraged to send implementation suggestions/code to xbugs, and we'll
take a look at them.
The parameters of XRebindKeysym should be changed for ease of use.
An incompatible change is not a possibility. An alternate interface could
be considered.eli@zgavva.IMA.ISC.COM (Elias Israel) (08/29/89)
First, thanks for the response. This was exactly what I was hoping for. >You don't have an "R4" tape, you have an alpha release. Aah. I was misinformed, then. I was told that it was out already. >That's because you're thinking in terms of modifier bits, while the Xlib >interface is in terms of modifiers. For example, the client might well >want to deal with "Hyper-A", without regard to which modifier bit Hyper >is assigned to. I'm not saying a bit-interface doesn't make sense, but >a keysym-interface also makes sense. OK. Then if any change is called for, it must preserve this functionality. I knew I'd miss something. > It keeps the list of modifier keysyms that > you passed in, even though their only use is to compute the state bits. > >No, they are also used if XRefreshKeyboardMapping is called. Oh, of course. When the keyboard mapping gets changed, you have to recompute the state bits from the original modifier keysyms. OK, modifier keysyms have to stay around, at least for the modifier-style interface that XRebindKeysym currently provides. > The parameters of XRebindKeysym should be changed for ease of use. > >An incompatible change is not a possibility. An alternate interface could >be considered. Yes, you're right, of course. A bad idea to make everyone have to re-code their clients. Still, with the exception of XRebindKeysym, all the other changes could be accommodated without a change in the interface. By adding a new routine instead of changing XRebindKeysym, it could all be made backward compatible. Ideas, Comments, Complaints, Flames? Elias Israel | "Justice, n. A commodity which in more or Interactive Systems Corp. | less adulterated condition the State sells Boston, MA | to the citizen as a reward for his allegiance, ..!ima!haddock!eli | taxes, and personal service." | -- Ambrose Bierce, _The Devil's Dictionary_