rxvt-unicode/src/keyboard.C

#include "../config.h"
#include "rxvt.h"
#include "keyboard.h"
#include "command.h"
#include <string.h>
#include <X11/X.h>

#ifdef KEYSYM_RESOURCE

////////////////////////////////////////////////////////////////////////////////
// default keycode translation map and keyevent handlers
keyevent_handler keysym_translator;
keyevent_handler keyrange_translator;
keyevent_handler keyrange_translator_meta8;
keyevent_handler keylist_translator;

keysym_t keyboard_manager::stock_keymap_[] =
{
  /* examples */
  /*        keysym,                state, range,                   handler,             str*/
//{XK_ISO_Left_Tab,                    0,     1,         keysym_translator,           "\033[Z"},
//{            'a',                    0,    26, keyrange_translator_meta8,           "a" "%c"},
//{            'a',          ControlMask,    26, keyrange_translator_meta8,          "" "%c"},
//{        XK_Left,                    0,     4,        keylist_translator,   "DACBZ" "\033[Z"},
//{        XK_Left,            ShiftMask,     4,        keylist_translator,   "dacbZ" "\033[Z"},
//{        XK_Left,          ControlMask,     4,        keylist_translator,   "dacbZ" "\033OZ"},
//{         XK_Tab,          ControlMask,     1,         keysym_translator,      "\033<C-Tab>"},
//{  XK_apostrophe,          ControlMask,     1,         keysym_translator,        "\033<C-'>"},
//{       XK_slash,          ControlMask,     1,         keysym_translator,        "\033<C-/>"},
//{   XK_semicolon,          ControlMask,     1,         keysym_translator,        "\033<C-;>"},
//{       XK_grave,          ControlMask,     1,         keysym_translator,        "\033<C-`>"},
//{       XK_comma,          ControlMask,     1,         keysym_translator,     "\033<C-\054>"},
//{      XK_Return,          ControlMask,     1,         keysym_translator,    "\033<C-Return>"},
//{      XK_Return,            ShiftMask,     1,         keysym_translator,    "\033<S-Return>"},
//{            ' ',            ShiftMask,     1,         keysym_translator,    "\033<S-Space>"},
//{            '.',          ControlMask,     1,         keysym_translator,        "\033<C-.>"},
//{            '0',          ControlMask,    10,       keyrange_translator,   "0" "\033<C-%c>"},
//{            '0', MetaMask|ControlMask,    10,       keyrange_translator, "0" "\033<M-C-%c>"},
//{            'a', MetaMask|ControlMask,    26,       keyrange_translator, "a" "\033<M-C-%c>"},
};

void output_string (rxvt_term *rt,
                    const char *str)
{
  assert (rt && str);
  if (strncmp (str, "proto:", 6) == 0)
    rt->cmd_write ((unsigned char*)str + 6, strlen (str) - 6);
  else
    rt->tt_write ((unsigned char*)str, strlen (str));
}

void output_string_meta8 (rxvt_term *rt,
                          unsigned int state,
                          char buf[],
                          int buflen)
{
  if (state & rt->ModMetaMask)
    {
#ifdef META8_OPTION
      if(rt->meta_char == 0x80) /* set 8-bit on */
        {
          for (char *ch = buf; ch < buf + buflen; ch++)
            *ch |= 0x80;
        }
      else if(rt->meta_char == C0_ESC) /* escape prefix */
#endif
        {
          const unsigned char ch = C0_ESC;
          rt->tt_write (&ch, 1);
        }
    }

  rt->tt_write ((unsigned char*)buf, buflen);
}

int format_keyrange_string (keysym_t *key,
                            KeySym keysym,
                            char buf[],
                            int bufsize)
{
  int len;

  assert (key->str);
  len = snprintf (buf, bufsize, key->str + 1,
                  keysym - key->keysym + (int)(key->str[0]));
  if (len >= bufsize)
    {
      fprintf (stderr, "buffer overflowed!\n");
      buf[bufsize-1] = '\0';
    }
  else if (len < 0)
    {
      perror("keyrange_translator()");
    }

  return len;
}

bool format_keylist_string (keysym_t *key,
                            KeySym keysym,
                            char buf[],
                            int bufsize)
{
  char *p;

  assert (key->str);
  strncpy (buf, key->str + key->range + 1, bufsize);
  buf[bufsize-1] = '\0';

  p = strchr (buf, key->str[key->range]);
  if (p)
    {
      *p = key->str[keysym - key->keysym];
      return true;
    }
  else
    {
      fprintf (stderr, "invalid str for keylist_translator()!\n");
      return false;
    }
}

/////////////////////////////////////////////////////////////////
void keysym_translator (rxvt_term *rt,
                        keysym_t *key,
                        KeySym keysym,
                        unsigned int state)
{
  output_string (rt, key->str);
}

void keyrange_translator (rxvt_term *rt,
                          keysym_t *key,
                          KeySym keysym,
                          unsigned int state)
{
  char buf[STRING_MAX];

  if (format_keyrange_string (key, keysym, buf, sizeof(buf)) > 0)
    output_string (rt, buf);
}

void keyrange_translator_meta8 (rxvt_term *rt,
                                keysym_t *key,
                                KeySym keysym,
                                unsigned int state)
{
  int len;
  char buf[STRING_MAX];

  len = format_keyrange_string (key, keysym, buf, sizeof(buf));
  if (len > 0)
    output_string_meta8 (rt, state, buf, len);
}

void keylist_translator (rxvt_term *rt,
                         keysym_t *key,
                         KeySym keysym,
                         unsigned int state)
{
  char buf[STRING_MAX];

  format_keylist_string (key, keysym, buf, sizeof(buf));
  output_string (rt, buf);
}

////////////////////////////////////////////////////////////////////////////////
// return: #bits of '1'
int
bitcount (unsigned int n)
{
  int i;
  for (i = 0; n; ++i, n &= (n - 1));
  return i;
}

// return: priority_of_a - priority_of_b
int
compare_priority (keysym_t *a, keysym_t *b)
{
  assert (a && b);

  // (the more '1's in state; the less range): the greater priority
  int ca = bitcount (a->state/* & AllModMask*/);
  int cb = bitcount (b->state/* & AllModMask*/);
  if (ca != cb)
    return ca - cb;
//else if (a->state != b->state) // this behavior is to be disscussed
//  return b->state - a->state;
  else
    return b->range - a->range;
}

////////////////////////////////////////////////////////////////////////////////
keyboard_manager::keyboard_manager (rxvt_term *rt)
  :term_(rt)
{
  keymap_.reserve (256);
  hash_[0] = 1; // hash_[0] != 0 indicates uninitialized data
}

keyboard_manager::~keyboard_manager ()
{
  clear ();
}

void
keyboard_manager::clear ()
{
  keymap_.clear ();
  hash_[0] = 2;

  for(unsigned int i = 0;i < user_translations_.size();++i)
    {
      delete[] user_translations_[i];
      user_translations_[i] = 0;
    }

  for(unsigned int i = 0;i < user_keymap_.size();++i)
    {
      delete user_keymap_[i];
      user_keymap_[i] = 0;
    }

  user_keymap_.clear();
  user_translations_.clear();
}

// a wrapper for register_keymap,
// so that outside codes don't have to know so much details.
//
// the string 'trans' is copied to an internal managed buffer,
// so the caller can free memory of 'trans' at any time.
void
keyboard_manager::register_user_translation (KeySym keysym,
                                             unsigned int state,
                                             const char *trans)
{
  assert(trans);

  keysym_t *key = new keysym_t;
  const char *translation = new char[1+strlen(trans)];

  if(key && translation)
    {
      key->keysym = keysym;
      key->state = state;
      key->range = 1;
      key->str = translation;

      if (strncmp (trans, "list", 4) == 0)
        {
          const char *p = &trans[4];
          if (*p && (p = strchr (p+1, *p)))
            if ((p - trans - 5 > 1) && strchr (p+1, *p))
              {
                strcpy (translation, trans+5);
                key->range = p - trans - 5;
                key->handler = keylist_translator;
              }
        }
      if (key->range == 1)
        {
          strcpy (translation, trans);
          key->handler = keysym_translator;
        }

      user_keymap_.push_back (key);
      user_translations_.push_back (translation);
      register_keymap (key);
    }
  else
    {
      delete key;
      delete[] translation;
      rxvt_fatal ("out of memory, aborting.\n");
    }
}

void
keyboard_manager::register_keymap (keysym_t *key)
{
  assert (key);
  assert (key->handler);
  assert (key->range >= 1);

  if (keymap_.size () == keymap_.capacity ())
    keymap_.reserve (keymap_.size () * 2);

  keymap_.push_back (key);
  hash_[0] = 3;
}

void
keyboard_manager::register_done ()
{
  unsigned int i, n = sizeof(stock_keymap_)/sizeof(keysym_t);

  if(keymap_.back() != &stock_keymap_[n-1])
    for(i = 0;i < n;++i)
      register_keymap(&stock_keymap_[i]);

  purge_duplicate_keymap ();

  for (i = 0; i < keymap_.size(); ++i)
    {
      keysym_t *key = keymap_[i];

      assert (bitcount (term_->ModMetaMask) == 1
              && "call me after ModMetaMask was set!");
      if (key->state & MetaMask)
        {
          //key->state &= ~MetaMask;
          key->state |= term_->ModMetaMask;
        }

      assert (bitcount (term_->ModNumLockMask) == 1
              && "call me after ModNumLockMask was set!");
      if (key->state & NumLockMask)
        {
          //key->state &= ~NumLockMask;
          key->state |= term_->ModNumLockMask;
        }
    }

  setup_hash ();
}

bool keyboard_manager::dispatch (KeySym keysym, unsigned int state)
{
  assert(hash_[0] == 0 && "register_done() need to be called");

  int index = find_keysym (keysym, state);

  if (index >= 0)
    {
      assert (term_ && keymap_[index] && keymap_[index]->handler);
      keymap_[index]->handler (term_, keymap_[index], keysym, state);
      return true;
    }
  else
  {
    // fprintf(stderr,"[%x:%x]",state,keysym);
    return false;
  }
}

// purge duplicate keymap_ entries
void
keyboard_manager::purge_duplicate_keymap ()
{
  for (unsigned int i = 0; i < keymap_.size (); ++i)
    {
      for (unsigned int j = 0; j < i; ++j)
        {
          if (keymap_[i] == keymap_[j])
            {
              while (keymap_[i] == keymap_.back ())
                keymap_.pop_back ();
              if (i < keymap_.size ())
                {
                  keymap_[i] = keymap_.back ();
                  keymap_.pop_back ();
                }
              break;
            }
        }
    }
}

void
keyboard_manager::setup_hash ()
{
  unsigned int i, index, hashkey;
  vector<keysym_t *> sorted_keymap;
  u16 hash_budget_size[KEYSYM_HASH_BUDGETS];     // size of each budget
  u16 hash_budget_counter[KEYSYM_HASH_BUDGETS];  // #elements in each budget

  memset (hash_budget_size, 0, sizeof (hash_budget_size));
  memset (hash_budget_counter, 0, sizeof (hash_budget_counter));

  // count keysyms for corresponding hash budgets
  for (i = 0; i < keymap_.size (); ++i)
    {
      assert (keymap_[i]);
      hashkey = (keymap_[i]->keysym & KEYSYM_HASH_MASK);
      ++hash_budget_size[hashkey];
    }

  // keysym A with range>1 is counted one more time for
  // every keysym B lies in its range
  for (i = 0; i < keymap_.size (); ++i)
    {
      if (keymap_[i]->range > 1)
        {
          for (int j = min (keymap_[i]->range, KEYSYM_HASH_BUDGETS) - 1;j > 0; --j)
            {
              hashkey = ((keymap_[i]->keysym + j) & KEYSYM_HASH_MASK);
              if (hash_budget_size[hashkey])
                ++hash_budget_size[hashkey];
            }
        }
    }

  // now we know the size of each budget
  // compute the index of each budget
  hash_[0] = 0;
  for (index = 0,i = 1; i < KEYSYM_HASH_BUDGETS; ++i)
    {
      index += hash_budget_size[i-1];
      hash_[i] = (hash_budget_size[i] ? index : hash_[i-1]);
    }
  // and allocate just enough space
  //sorted_keymap.reserve (hash_[i - 1] + hash_budget_size[i - 1]);
  sorted_keymap.insert (sorted_keymap.begin(), index + hash_budget_size[i - 1], 0);

  // fill in sorted_keymap
  // it is sorted in each budget
  for (i = 0; i < keymap_.size (); ++i)
    {
      for (int j = min (keymap_[i]->range, KEYSYM_HASH_BUDGETS) - 1;j >= 0; --j)
        {
          hashkey = ((keymap_[i]->keysym + j) & KEYSYM_HASH_MASK);
          if (hash_budget_size[hashkey])
            {
              index = hash_[hashkey] + hash_budget_counter[hashkey];
              while (index > hash_[hashkey] &&
                     compare_priority (keymap_[i],
                                       sorted_keymap[index - 1]) > 0)
                {
                  sorted_keymap[index] = sorted_keymap[index - 1];
                  --index;
                }
              sorted_keymap[index] = keymap_[i];
              ++hash_budget_counter[hashkey];
            }
        }
    }

  keymap_.swap (sorted_keymap);

#if defined (DEBUG_STRICT) || defined (DEBUG_KEYBOARD)
  // check for invariants
  for (i = 0; i < KEYSYM_HASH_BUDGETS; ++i)
    {
      index = hash_[i];
      for (int j = 0; j < hash_budget_size[i]; ++j)
        {
          if (keymap_[index + j]->range == 1)
            assert (i == (keymap_[index + j]->keysym & KEYSYM_HASH_MASK));
          if (j)
            assert (compare_priority (keymap_[index + j - 1],
                                      keymap_[index + j]) >= 0);
        }
    }

  // this should be able to detect most possible bugs
  for (i = 0; i < sorted_keymap.size (); ++i)
    {
      keysym_t *a = sorted_keymap[i];
      for (int j = 0; j < a->range; ++j)
        {
          int index = find_keysym (a->keysym + j, a->state & AllModMask);
          assert (index >= 0);
          keysym_t *b = keymap_[index];
          assert (i == (signed)index || // the normally expected result
              (a->keysym + j) >= b->keysym &&
              (a->keysym + j) <= (b->keysym + b->range) &&
              compare_priority (a, b) <= 0); // is effectively the same
        }
    }
#endif
}

int
keyboard_manager::find_keysym (KeySym keysym, unsigned int state)
{
  int hashkey = (keysym & KEYSYM_HASH_MASK);
  unsigned int index = hash_[hashkey];

  for (;index < keymap_.size(); ++index)
    {
      keysym_t *key = keymap_[index];
      assert (key);
      if (key->keysym <= keysym &&
          key->keysym + key->range > keysym &&
          // match only the specified bits in state and ignore others
          (key->state & (unsigned int)AllModMask) == (key->state & state))
        {
          return index;
        }
      else if (key->keysym > keysym &&
               key->range == 1)
        return -1;
    }

  return -1;
}

#endif /* KEYSYM_RESOURCE */
// vim:et:ts=2:sw=2
Revision:	1.1
Committed:	Sun Jan 16 15:59:45 2005 UTC (21 years, 8 months ago) by root
Content type:	text/plain
Branch:	MAIN
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	#include "../config.h"
2			#include "rxvt.h"
3			#include "keyboard.h"
4			#include "command.h"
5			#include <string.h>
6			#include <X11/X.h>
7
8			#ifdef KEYSYM_RESOURCE
9
10			////////////////////////////////////////////////////////////////////////////////
11			// default keycode translation map and keyevent handlers
12			keyevent_handler keysym_translator;
13			keyevent_handler keyrange_translator;
14			keyevent_handler keyrange_translator_meta8;
15			keyevent_handler keylist_translator;
16
17			keysym_t keyboard_manager::stock_keymap_[] =
18			{
19			/* examples */
20			/* keysym, state, range, handler, str*/
21			//{XK_ISO_Left_Tab, 0, 1, keysym_translator, "\033[Z"},
22			//{ 'a', 0, 26, keyrange_translator_meta8, "a" "%c"},
23			//{ 'a', ControlMask, 26, keyrange_translator_meta8, "" "%c"},
24			//{ XK_Left, 0, 4, keylist_translator, "DACBZ" "\033[Z"},
25			//{ XK_Left, ShiftMask, 4, keylist_translator, "dacbZ" "\033[Z"},
26			//{ XK_Left, ControlMask, 4, keylist_translator, "dacbZ" "\033OZ"},
27			//{ XK_Tab, ControlMask, 1, keysym_translator, "\033<C-Tab>"},
28			//{ XK_apostrophe, ControlMask, 1, keysym_translator, "\033<C-'>"},
29			//{ XK_slash, ControlMask, 1, keysym_translator, "\033<C-/>"},
30			//{ XK_semicolon, ControlMask, 1, keysym_translator, "\033<C-;>"},
31			//{ XK_grave, ControlMask, 1, keysym_translator, "\033<C-`>"},
32			//{ XK_comma, ControlMask, 1, keysym_translator, "\033<C-\054>"},
33			//{ XK_Return, ControlMask, 1, keysym_translator, "\033<C-Return>"},
34			//{ XK_Return, ShiftMask, 1, keysym_translator, "\033<S-Return>"},
35			//{ ' ', ShiftMask, 1, keysym_translator, "\033<S-Space>"},
36			//{ '.', ControlMask, 1, keysym_translator, "\033<C-.>"},
37			//{ '0', ControlMask, 10, keyrange_translator, "0" "\033<C-%c>"},
38			//{ '0', MetaMask\|ControlMask, 10, keyrange_translator, "0" "\033<M-C-%c>"},
39			//{ 'a', MetaMask\|ControlMask, 26, keyrange_translator, "a" "\033<M-C-%c>"},
40			};
41
42			void output_string (rxvt_term *rt,
43			const char *str)
44			{
45			assert (rt && str);
46			if (strncmp (str, "proto:", 6) == 0)
47			rt->cmd_write ((unsigned char*)str + 6, strlen (str) - 6);
48			else
49			rt->tt_write ((unsigned char*)str, strlen (str));
50			}
51
52			void output_string_meta8 (rxvt_term *rt,
53			unsigned int state,
54			char buf[],
55			int buflen)
56			{
57			if (state & rt->ModMetaMask)
58			{
59			#ifdef META8_OPTION
60			if(rt->meta_char == 0x80) /* set 8-bit on */
61			{
62			for (char *ch = buf; ch < buf + buflen; ch++)
63			*ch \|= 0x80;
64			}
65			else if(rt->meta_char == C0_ESC) /* escape prefix */
66			#endif
67			{
68			const unsigned char ch = C0_ESC;
69			rt->tt_write (&ch, 1);
70			}
71			}
72
73			rt->tt_write ((unsigned char*)buf, buflen);
74			}
75
76			int format_keyrange_string (keysym_t *key,
77			KeySym keysym,
78			char buf[],
79			int bufsize)
80			{
81			int len;
82
83			assert (key->str);
84			len = snprintf (buf, bufsize, key->str + 1,
85			keysym - key->keysym + (int)(key->str[0]));
86			if (len >= bufsize)
87			{
88			fprintf (stderr, "buffer overflowed!\n");
89			buf[bufsize-1] = '\0';
90			}
91			else if (len < 0)
92			{
93			perror("keyrange_translator()");
94			}
95
96			return len;
97			}
98
99			bool format_keylist_string (keysym_t *key,
100			KeySym keysym,
101			char buf[],
102			int bufsize)
103			{
104			char *p;
105
106			assert (key->str);
107			strncpy (buf, key->str + key->range + 1, bufsize);
108			buf[bufsize-1] = '\0';
109
110			p = strchr (buf, key->str[key->range]);
111			if (p)
112			{
113			*p = key->str[keysym - key->keysym];
114			return true;
115			}
116			else
117			{
118			fprintf (stderr, "invalid str for keylist_translator()!\n");
119			return false;
120			}
121			}
122
123			/////////////////////////////////////////////////////////////////
124			void keysym_translator (rxvt_term *rt,
125			keysym_t *key,
126			KeySym keysym,
127			unsigned int state)
128			{
129			output_string (rt, key->str);
130			}
131
132			void keyrange_translator (rxvt_term *rt,
133			keysym_t *key,
134			KeySym keysym,
135			unsigned int state)
136			{
137			char buf[STRING_MAX];
138
139			if (format_keyrange_string (key, keysym, buf, sizeof(buf)) > 0)
140			output_string (rt, buf);
141			}
142
143			void keyrange_translator_meta8 (rxvt_term *rt,
144			keysym_t *key,
145			KeySym keysym,
146			unsigned int state)
147			{
148			int len;
149			char buf[STRING_MAX];
150
151			len = format_keyrange_string (key, keysym, buf, sizeof(buf));
152			if (len > 0)
153			output_string_meta8 (rt, state, buf, len);
154			}
155
156			void keylist_translator (rxvt_term *rt,
157			keysym_t *key,
158			KeySym keysym,
159			unsigned int state)
160			{
161			char buf[STRING_MAX];
162
163			format_keylist_string (key, keysym, buf, sizeof(buf));
164			output_string (rt, buf);
165			}
166
167			////////////////////////////////////////////////////////////////////////////////
168			// return: #bits of '1'
169			int
170			bitcount (unsigned int n)
171			{
172			int i;
173			for (i = 0; n; ++i, n &= (n - 1));
174			return i;
175			}
176
177			// return: priority_of_a - priority_of_b
178			int
179			compare_priority (keysym_t a, keysym_t b)
180			{
181			assert (a && b);
182
183			// (the more '1's in state; the less range): the greater priority
184			int ca = bitcount (a->state/* & AllModMask*/);
185			int cb = bitcount (b->state/* & AllModMask*/);
186			if (ca != cb)
187			return ca - cb;
188			//else if (a->state != b->state) // this behavior is to be disscussed
189			// return b->state - a->state;
190			else
191			return b->range - a->range;
192			}
193
194			////////////////////////////////////////////////////////////////////////////////
195			keyboard_manager::keyboard_manager (rxvt_term *rt)
196			:term_(rt)
197			{
198			keymap_.reserve (256);
199			hash_[0] = 1; // hash_[0] != 0 indicates uninitialized data
200			}
201
202			keyboard_manager::~keyboard_manager ()
203			{
204			clear ();
205			}
206
207			void
208			keyboard_manager::clear ()
209			{
210			keymap_.clear ();
211			hash_[0] = 2;
212
213			for(unsigned int i = 0;i < user_translations_.size();++i)
214			{
215			delete[] user_translations_[i];
216			user_translations_[i] = 0;
217			}
218
219			for(unsigned int i = 0;i < user_keymap_.size();++i)
220			{
221			delete user_keymap_[i];
222			user_keymap_[i] = 0;
223			}
224
225			user_keymap_.clear();
226			user_translations_.clear();
227			}
228
229			// a wrapper for register_keymap,
230			// so that outside codes don't have to know so much details.
231			//
232			// the string 'trans' is copied to an internal managed buffer,
233			// so the caller can free memory of 'trans' at any time.
234			void
235			keyboard_manager::register_user_translation (KeySym keysym,
236			unsigned int state,
237			const char *trans)
238			{
239			assert(trans);
240
241			keysym_t *key = new keysym_t;
242			const char *translation = new char[1+strlen(trans)];
243
244			if(key && translation)
245			{
246			key->keysym = keysym;
247			key->state = state;
248			key->range = 1;
249			key->str = translation;
250
251			if (strncmp (trans, "list", 4) == 0)
252			{
253			const char *p = &trans[4];
254			if (p && (p = strchr (p+1, p)))
255			if ((p - trans - 5 > 1) && strchr (p+1, *p))
256			{
257			strcpy (translation, trans+5);
258			key->range = p - trans - 5;
259			key->handler = keylist_translator;
260			}
261			}
262			if (key->range == 1)
263			{
264			strcpy (translation, trans);
265			key->handler = keysym_translator;
266			}
267
268			user_keymap_.push_back (key);
269			user_translations_.push_back (translation);
270			register_keymap (key);
271			}
272			else
273			{
274			delete key;
275			delete[] translation;
276			rxvt_fatal ("out of memory, aborting.\n");
277			}
278			}
279
280			void
281			keyboard_manager::register_keymap (keysym_t *key)
282			{
283			assert (key);
284			assert (key->handler);
285			assert (key->range >= 1);
286
287			if (keymap_.size () == keymap_.capacity ())
288			keymap_.reserve (keymap_.size () * 2);
289
290			keymap_.push_back (key);
291			hash_[0] = 3;
292			}
293
294			void
295			keyboard_manager::register_done ()
296			{
297			unsigned int i, n = sizeof(stock_keymap_)/sizeof(keysym_t);
298
299			if(keymap_.back() != &stock_keymap_[n-1])
300			for(i = 0;i < n;++i)
301			register_keymap(&stock_keymap_[i]);
302
303			purge_duplicate_keymap ();
304
305			for (i = 0; i < keymap_.size(); ++i)
306			{
307			keysym_t *key = keymap_[i];
308
309			assert (bitcount (term_->ModMetaMask) == 1
310			&& "call me after ModMetaMask was set!");
311			if (key->state & MetaMask)
312			{
313			//key->state &= ~MetaMask;
314			key->state \|= term_->ModMetaMask;
315			}
316
317			assert (bitcount (term_->ModNumLockMask) == 1
318			&& "call me after ModNumLockMask was set!");
319			if (key->state & NumLockMask)
320			{
321			//key->state &= ~NumLockMask;
322			key->state \|= term_->ModNumLockMask;
323			}
324			}
325
326			setup_hash ();
327			}
328
329			bool keyboard_manager::dispatch (KeySym keysym, unsigned int state)
330			{
331			assert(hash_[0] == 0 && "register_done() need to be called");
332
333			int index = find_keysym (keysym, state);
334
335			if (index >= 0)
336			{
337			assert (term_ && keymap_[index] && keymap_[index]->handler);
338			keymap_[index]->handler (term_, keymap_[index], keysym, state);
339			return true;
340			}
341			else
342			{
343			// fprintf(stderr,"[%x:%x]",state,keysym);
344			return false;
345			}
346			}
347
348			// purge duplicate keymap_ entries
349			void
350			keyboard_manager::purge_duplicate_keymap ()
351			{
352			for (unsigned int i = 0; i < keymap_.size (); ++i)
353			{
354			for (unsigned int j = 0; j < i; ++j)
355			{
356			if (keymap_[i] == keymap_[j])
357			{
358			while (keymap_[i] == keymap_.back ())
359			keymap_.pop_back ();
360			if (i < keymap_.size ())
361			{
362			keymap_[i] = keymap_.back ();
363			keymap_.pop_back ();
364			}
365			break;
366			}
367			}
368			}
369			}
370
371			void
372			keyboard_manager::setup_hash ()
373			{
374			unsigned int i, index, hashkey;
375			vector<keysym_t *> sorted_keymap;
376			u16 hash_budget_size[KEYSYM_HASH_BUDGETS]; // size of each budget
377			u16 hash_budget_counter[KEYSYM_HASH_BUDGETS]; // #elements in each budget
378
379			memset (hash_budget_size, 0, sizeof (hash_budget_size));
380			memset (hash_budget_counter, 0, sizeof (hash_budget_counter));
381
382			// count keysyms for corresponding hash budgets
383			for (i = 0; i < keymap_.size (); ++i)
384			{
385			assert (keymap_[i]);
386			hashkey = (keymap_[i]->keysym & KEYSYM_HASH_MASK);
387			++hash_budget_size[hashkey];
388			}
389
390			// keysym A with range>1 is counted one more time for
391			// every keysym B lies in its range
392			for (i = 0; i < keymap_.size (); ++i)
393			{
394			if (keymap_[i]->range > 1)
395			{
396			for (int j = min (keymap_[i]->range, KEYSYM_HASH_BUDGETS) - 1;j > 0; --j)
397			{
398			hashkey = ((keymap_[i]->keysym + j) & KEYSYM_HASH_MASK);
399			if (hash_budget_size[hashkey])
400			++hash_budget_size[hashkey];
401			}
402			}
403			}
404
405			// now we know the size of each budget
406			// compute the index of each budget
407			hash_[0] = 0;
408			for (index = 0,i = 1; i < KEYSYM_HASH_BUDGETS; ++i)
409			{
410			index += hash_budget_size[i-1];
411			hash_[i] = (hash_budget_size[i] ? index : hash_[i-1]);
412			}
413			// and allocate just enough space
414			//sorted_keymap.reserve (hash_[i - 1] + hash_budget_size[i - 1]);
415			sorted_keymap.insert (sorted_keymap.begin(), index + hash_budget_size[i - 1], 0);
416
417			// fill in sorted_keymap
418			// it is sorted in each budget
419			for (i = 0; i < keymap_.size (); ++i)
420			{
421			for (int j = min (keymap_[i]->range, KEYSYM_HASH_BUDGETS) - 1;j >= 0; --j)
422			{
423			hashkey = ((keymap_[i]->keysym + j) & KEYSYM_HASH_MASK);
424			if (hash_budget_size[hashkey])
425			{
426			index = hash_[hashkey] + hash_budget_counter[hashkey];
427			while (index > hash_[hashkey] &&
428			compare_priority (keymap_[i],
429			sorted_keymap[index - 1]) > 0)
430			{
431			sorted_keymap[index] = sorted_keymap[index - 1];
432			--index;
433			}
434			sorted_keymap[index] = keymap_[i];
435			++hash_budget_counter[hashkey];
436			}
437			}
438			}
439
440			keymap_.swap (sorted_keymap);
441
442			#if defined (DEBUG_STRICT) \|\| defined (DEBUG_KEYBOARD)
443			// check for invariants
444			for (i = 0; i < KEYSYM_HASH_BUDGETS; ++i)
445			{
446			index = hash_[i];
447			for (int j = 0; j < hash_budget_size[i]; ++j)
448			{
449			if (keymap_[index + j]->range == 1)
450			assert (i == (keymap_[index + j]->keysym & KEYSYM_HASH_MASK));
451			if (j)
452			assert (compare_priority (keymap_[index + j - 1],
453			keymap_[index + j]) >= 0);
454			}
455			}
456
457			// this should be able to detect most possible bugs
458			for (i = 0; i < sorted_keymap.size (); ++i)
459			{
460			keysym_t *a = sorted_keymap[i];
461			for (int j = 0; j < a->range; ++j)
462			{
463			int index = find_keysym (a->keysym + j, a->state & AllModMask);
464			assert (index >= 0);
465			keysym_t *b = keymap_[index];
466			assert (i == (signed)index \|\| // the normally expected result
467			(a->keysym + j) >= b->keysym &&
468			(a->keysym + j) <= (b->keysym + b->range) &&
469			compare_priority (a, b) <= 0); // is effectively the same
470			}
471			}
472			#endif
473			}
474
475			int
476			keyboard_manager::find_keysym (KeySym keysym, unsigned int state)
477			{
478			int hashkey = (keysym & KEYSYM_HASH_MASK);
479			unsigned int index = hash_[hashkey];
480
481			for (;index < keymap_.size(); ++index)
482			{
483			keysym_t *key = keymap_[index];
484			assert (key);
485			if (key->keysym <= keysym &&
486			key->keysym + key->range > keysym &&
487			// match only the specified bits in state and ignore others
488			(key->state & (unsigned int)AllModMask) == (key->state & state))
489			{
490			return index;
491			}
492			else if (key->keysym > keysym &&
493			key->range == 1)
494			return -1;
495			}
496
497			return -1;
498			}
499
500			#endif /* KEYSYM_RESOURCE */
501			// vim:et:ts=2:sw=2