From 43e835365c23f7c0898c42498440226ac5376563 Mon Sep 17 00:00:00 2001 From: Nicholas Marriott Date: Thu, 5 Nov 2009 19:29:42 +0000 Subject: Switch the tty key tree over to an (unbalanced) ternary tree which allows partial matches to be done (they wait for further data or a timer to expire, like a naked escape). Mouse and xterm-style keys still expect to be atomic. --- usr.bin/tmux/tmux.h | 15 ++- usr.bin/tmux/tty-keys.c | 236 ++++++++++++++++++++++++++++++++---------------- 2 files changed, 163 insertions(+), 88 deletions(-) diff --git a/usr.bin/tmux/tmux.h b/usr.bin/tmux/tmux.h index 5b42fce46d9..0c6ebe9ca46 100644 --- a/usr.bin/tmux/tmux.h +++ b/usr.bin/tmux/tmux.h @@ -1,4 +1,4 @@ -/* $OpenBSD: tmux.h,v 1.172 2009/11/05 10:44:36 nicm Exp $ */ +/* $OpenBSD: tmux.h,v 1.173 2009/11/05 19:29:41 nicm Exp $ */ /* * Copyright (c) 2007 Nicholas Marriott @@ -936,10 +936,13 @@ ARRAY_DECL(sessions, struct session *); /* TTY information. */ struct tty_key { + char ch; int key; - char *string; - RB_ENTRY(tty_key) entry; + struct tty_key *left; + struct tty_key *right; + + struct tty_key *next; }; struct tty_term { @@ -998,9 +1001,7 @@ struct tty { void (*key_callback)(int, struct mouse_event *, void *); void *key_data; struct event key_timer; - - size_t ksize; /* maximum key size */ - RB_HEAD(tty_keys, tty_key) ktree; + struct tty_key *key_tree; }; /* TTY command context and function pointer. */ @@ -1351,8 +1352,6 @@ int tty_term_number(struct tty_term *, enum tty_code_code); int tty_term_flag(struct tty_term *, enum tty_code_code); /* tty-keys.c */ -int tty_keys_cmp(struct tty_key *, struct tty_key *); -RB_PROTOTYPE(tty_keys, tty_key, entry, tty_keys_cmp); void tty_keys_init(struct tty *); void tty_keys_free(struct tty *); int tty_keys_next(struct tty *); diff --git a/usr.bin/tmux/tty-keys.c b/usr.bin/tmux/tty-keys.c index 2b766842c7a..68cc01a9957 100644 --- a/usr.bin/tmux/tty-keys.c +++ b/usr.bin/tmux/tty-keys.c @@ -1,4 +1,4 @@ -/* $OpenBSD: tty-keys.c,v 1.15 2009/11/05 10:44:36 nicm Exp $ */ +/* $OpenBSD: tty-keys.c,v 1.16 2009/11/05 19:29:41 nicm Exp $ */ /* * Copyright (c) 2007 Nicholas Marriott @@ -26,12 +26,19 @@ #include "tmux.h" /* - * Handle keys input from the outside terminal. + * Handle keys input from the outside terminal. tty_keys[] is a base table of + * supported keys which are looked up in terminfo(5) and translated into a + * ternary tree (a binary tree of binary trees). */ -void tty_keys_add(struct tty *, const char *, int); -void tty_keys_callback(int, short, void *); -int tty_keys_mouse(char *, size_t, size_t *, struct mouse_event *); +void tty_keys_add1(struct tty_key **, const char *, int); +void tty_keys_add(struct tty *, const char *, int); +void tty_keys_free1(struct tty_key *); +struct tty_key *tty_keys_find1( + struct tty_key *, const char *, size_t, size_t *); +struct tty_key *tty_keys_find(struct tty *, const char *, size_t, size_t *); +void tty_keys_callback(int, short, void *); +int tty_keys_mouse(char *, size_t, size_t *, struct mouse_event *); struct tty_key_ent { enum tty_code_code code; @@ -43,6 +50,11 @@ struct tty_key_ent { #define TTYKEY_RAW 0x2 }; +/* + * Default key tables. Those flagged with TTYKEY_RAW are inserted directly, + * otherwise they are looked up in terminfo(5). Any keys marked TTYKEY_CTRL + * have their last byte twiddled and are inserted as a Ctrl key as well. + */ struct tty_key_ent tty_keys[] = { /* Function keys. */ { TTYC_KF1, NULL, KEYC_F1, TTYKEY_CTRL }, @@ -186,37 +198,56 @@ struct tty_key_ent tty_keys[] = { { TTYC_KUP7, NULL, KEYC_UP|KEYC_ESCAPE|KEYC_CTRL, 0 }, }; -RB_GENERATE(tty_keys, tty_key, entry, tty_keys_cmp); - -struct tty_key *tty_keys_find(struct tty *, char *, size_t, size_t *); - -int -tty_keys_cmp(struct tty_key *k1, struct tty_key *k2) +void +tty_keys_add(struct tty *tty, const char *s, int key) { - return (strcmp(k1->string, k2->string)); + size_t size; + + if (tty_keys_find(tty, s, strlen(s), &size) == NULL) { + log_debug("new key 0x%x: %s", key, s); + tty_keys_add1(&tty->key_tree, s, key); + } } +/* Add next node to the tree. */ void -tty_keys_add(struct tty *tty, const char *s, int key) +tty_keys_add1(struct tty_key **tkp, const char *s, int key) { - struct tty_key *tk, *tl; + struct tty_key *tk; - tk = xmalloc(sizeof *tk); - tk->string = xstrdup(s); - tk->key = key; + /* Allocate a tree entry if there isn't one already. */ + tk = *tkp; + if (tk == NULL) { + tk = *tkp = xcalloc(1, sizeof *tk); + tk->ch = *s; + tk->key = KEYC_NONE; + } + + /* Find the next entry. */ + if (*s == tk->ch) { + /* Move forward in string. */ + s++; - if ((tl = RB_INSERT(tty_keys, &tty->ktree, tk)) != NULL) { - xfree(tk->string); - xfree(tk); - log_debug("key exists: %s (old %x, new %x)", s, tl->key, key); - return; + /* If this is the end of the string, no more is necessary. */ + if (*s == '\0') { + tk->key = key; + return; + } + + /* Use the child tree for the next character. */ + tkp = &tk->next; + } else { + if (*s < tk->ch) + tkp = &tk->left; + else if (*s > tk->ch) + tkp = &tk->right; } - if (strlen(tk->string) > tty->ksize) - tty->ksize = strlen(tk->string); - log_debug("new key %x: size now %zu (%s)", key, tty->ksize, tk->string); + /* And recurse to add it. */ + tty_keys_add1(tkp, s, key); } +/* Initialise a key tree from the table. */ void tty_keys_init(struct tty *tty) { @@ -225,9 +256,7 @@ tty_keys_init(struct tty *tty) const char *s; char tmp[64]; - RB_INIT(&tty->ktree); - - tty->ksize = 0; + tty->key_tree = NULL; for (i = 0; i < nitems(tty_keys); i++) { tke = &tty_keys[i]; @@ -237,12 +266,12 @@ tty_keys_init(struct tty *tty) if (!tty_term_has(tty->term, tke->code)) continue; s = tty_term_string(tty->term, tke->code); - if (s[0] != '\033' || s[1] == '\0') - continue; } + if (s[0] != '\033' || s[1] == '\0') + continue; tty_keys_add(tty, s + 1, tke->key); - if (tke->flags & TTYKEY_CTRL) { + if (!(tke->flags & TTYKEY_CTRL)) { if (strlcpy(tmp, s, sizeof tmp) >= sizeof tmp) continue; tmp[strlen(tmp) - 1] ^= 0x20; @@ -251,61 +280,80 @@ tty_keys_init(struct tty *tty) } } +/* Free the entire key tree. */ void tty_keys_free(struct tty *tty) { - struct tty_key *tk; + tty_keys_free1(tty->key_tree); +} - while (!RB_EMPTY(&tty->ktree)) { - tk = RB_ROOT(&tty->ktree); - RB_REMOVE(tty_keys, &tty->ktree, tk); - xfree(tk->string); - xfree(tk); - } +/* Free a single key. */ +void +tty_keys_free1(struct tty_key *tk) +{ + if (tk->next != NULL) + tty_keys_free1(tk->next); + if (tk->left != NULL) + tty_keys_free1(tk->left); + if (tk->right != NULL) + tty_keys_free1(tk->right); + xfree(tk); + } +/* Lookup a key in the tree. */ struct tty_key * -tty_keys_find(struct tty *tty, char *buf, size_t len, size_t *size) +tty_keys_find(struct tty *tty, const char *buf, size_t len, size_t *size) { - struct tty_key *tk, tl; - char *s; + *size = 0; + return (tty_keys_find1(tty->key_tree, buf, len, size)); +} - if (len == 0) +/* Find the next node. */ +struct tty_key * +tty_keys_find1(struct tty_key *tk, const char *buf, size_t len, size_t *size) +{ + /* If the node is NULL, this is the end of the tree. No match. */ + if (tk == NULL) return (NULL); - s = xmalloc(tty->ksize + 1); - for (*size = tty->ksize; (*size) > 0; (*size)--) { - if ((*size) > len) - continue; - memcpy(s, buf, *size); - s[*size] = '\0'; - - log_debug2("looking for key: %s", s); + /* Pick the next in the sequence. */ + if (tk->ch == *buf) { + /* Move forward in the string. */ + buf++; len--; + (*size)++; - tl.string = s; - tk = RB_FIND(tty_keys, &tty->ktree, &tl); - if (tk != NULL) { - log_debug2("got key: 0x%x", tk->key); - xfree(s); + /* At the end of the string, return the current node. */ + if (len == 0) return (tk); - } + + /* Move into the next tree for the following character. */ + tk = tk->next; + } else { + if (*buf < tk->ch) + tk = tk->left; + else if (*buf > tk->ch) + tk = tk->right; } - xfree(s); - return (NULL); + /* Move to the next in the tree. */ + return (tty_keys_find1(tk, buf, len, size)); } +/* + * Process at least one key in the buffer and invoke tty->key_callback. Return + * 1 if there are no further keys, or 0 if there is more in the buffer. + */ int tty_keys_next(struct tty *tty) { struct tty_key *tk; struct timeval tv; struct mouse_event mouse; - char *buf; + char *buf, *ptr; size_t len, size; cc_t bspace; int key; - u_char ch; buf = EVBUFFER_DATA(tty->event->input); len = EVBUFFER_LENGTH(tty->event->input); @@ -315,8 +363,8 @@ tty_keys_next(struct tty *tty) /* If a normal key, return it. */ if (*buf != '\033') { - bufferevent_read(tty->event, &ch, 1); - key = ch; + key = *buf; + evbuffer_drain(tty->event->input, 1); /* * Check for backspace key using termios VERASE - the terminfo @@ -326,29 +374,28 @@ tty_keys_next(struct tty *tty) bspace = tty->tio.c_cc[VERASE]; if (bspace != _POSIX_VDISABLE && key == bspace) key = KEYC_BSPACE; - goto found; + goto handle_key; } /* Look for matching key string and return if found. */ tk = tty_keys_find(tty, buf + 1, len - 1, &size); if (tk != NULL) { - evbuffer_drain(tty->event->input, size + 1); key = tk->key; - goto found; + goto found_key; } /* Not found. Is this a mouse key press? */ key = tty_keys_mouse(buf, len, &size, &mouse); if (key != KEYC_NONE) { evbuffer_drain(tty->event->input, size); - goto found; + goto handle_key; } /* Not found. Try to parse a key with an xterm-style modifier. */ key = xterm_keys_find(buf, len, &size); if (key != KEYC_NONE) { evbuffer_drain(tty->event->input, size); - goto found; + goto handle_key; } /* Skip the escape. */ @@ -357,32 +404,37 @@ tty_keys_next(struct tty *tty) /* Is there a normal key following? */ if (len != 0 && *buf != '\033') { - evbuffer_drain(tty->event->input, 1); - bufferevent_read(tty->event, &ch, 1); - key = ch | KEYC_ESCAPE; - goto found; + key = *buf | KEYC_ESCAPE; + evbuffer_drain(tty->event->input, 2); + goto handle_key; } /* Or a key string? */ if (len > 1) { tk = tty_keys_find(tty, buf + 1, len - 1, &size); if (tk != NULL) { - evbuffer_drain(tty->event->input, size + 2); key = tk->key | KEYC_ESCAPE; - goto found; + size++; /* include escape */ + goto found_key; } } + /* Escape and then nothing useful - fall through. */ + +partial_key: /* - * Escape but no key string. If have, already seen an escape, then the + * Escape but no key string. If have already seen an escape, then the * timer must have expired, so give up waiting and send the escape. */ if (tty->flags & TTY_ESCAPE) { evbuffer_drain(tty->event->input, 1); key = '\033'; - goto found; + goto handle_key; } + /* Fall through to start the timer. */ + +start_timer: /* Start the timer and wait for expiry or more data. */ tv.tv_sec = 0; tv.tv_usec = ESCAPE_PERIOD * 1000L; @@ -394,22 +446,45 @@ tty_keys_next(struct tty *tty) tty->flags |= TTY_ESCAPE; return (0); -found: - evtimer_del(&tty->key_timer); +found_key: + if (tk->next != NULL) { + /* Partial key. Start the timer if not already expired. */ + if (!(tty->flags & TTY_ESCAPE)) + goto start_timer; + + /* Otherwise, if no key, send the escape alone. */ + if (tk->key == KEYC_NONE) + goto partial_key; + + /* Or fall through to send the partial key found. */ + } + evbuffer_drain(tty->event->input, size + 1); + + goto handle_key; + +handle_key: + evtimer_del(&tty->key_timer); + tty->key_callback(key, &mouse, tty->key_data); + tty->flags &= ~TTY_ESCAPE; return (1); } +/* Key timer callback. */ void tty_keys_callback(unused int fd, unused short events, void *data) { struct tty *tty = data; - if (tty->flags & TTY_ESCAPE) - tty_keys_next(tty); + if (!(tty->flags & TTY_ESCAPE)) + return; + + while (tty_keys_next(tty)) + ; } +/* Handle mouse key input. */ int tty_keys_mouse(char *buf, size_t len, size_t *size, struct mouse_event *m) { @@ -418,11 +493,12 @@ tty_keys_mouse(char *buf, size_t len, size_t *size, struct mouse_event *m) * buttons, X and Y, all based at 32 with 1,1 top-left. */ - log_debug("mouse input is: %.*s", (int) len, buf); if (len != 6 || memcmp(buf, "\033[M", 3) != 0) return (KEYC_NONE); *size = 6; + log_debug("mouse input is: %.*s", (int) len, buf); + m->b = buf[3]; m->x = buf[4]; m->y = buf[5]; -- cgit v1.2.3