| … | |
… | |
| 250 | keyboard_manager::setup_hash () |
250 | keyboard_manager::setup_hash () |
| 251 | { |
251 | { |
| 252 | unsigned int i, index, hashkey; |
252 | unsigned int i, index, hashkey; |
| 253 | vector <keysym_t *> sorted_keymap; |
253 | vector <keysym_t *> sorted_keymap; |
| 254 | uint16_t hash_bucket_size[KEYSYM_HASH_BUCKETS]; // size of each bucket |
254 | uint16_t hash_bucket_size[KEYSYM_HASH_BUCKETS]; // size of each bucket |
| 255 | uint16_t hash_bucket_counter[KEYSYM_HASH_BUCKETS]; // #elements in each bucket |
|
|
| 256 | |
255 | |
| 257 | memset (hash_bucket_size, 0, sizeof (hash_bucket_size)); |
256 | memset (hash_bucket_size, 0, sizeof (hash_bucket_size)); |
| 258 | memset (hash_bucket_counter, 0, sizeof (hash_bucket_counter)); |
|
|
| 259 | |
257 | |
| 260 | // determine hash bucket size |
258 | // determine hash bucket size |
| 261 | for (i = 0; i < keymap.size (); ++i) |
259 | for (i = 0; i < keymap.size (); ++i) |
| 262 | for (int j = min (keymap [i]->range, KEYSYM_HASH_BUCKETS) - 1; j >= 0; --j) |
260 | for (int j = min (keymap [i]->range, KEYSYM_HASH_BUCKETS) - 1; j >= 0; --j) |
| 263 | { |
261 | { |
| … | |
… | |
| 275 | } |
273 | } |
| 276 | |
274 | |
| 277 | // and allocate just enough space |
275 | // and allocate just enough space |
| 278 | sorted_keymap.insert (sorted_keymap.begin (), index + hash_bucket_size [i - 1], 0); |
276 | sorted_keymap.insert (sorted_keymap.begin (), index + hash_bucket_size [i - 1], 0); |
| 279 | |
277 | |
|
|
278 | memset (hash_bucket_size, 0, sizeof (hash_bucket_size)); |
|
|
279 | |
| 280 | // fill in sorted_keymap |
280 | // fill in sorted_keymap |
| 281 | // it is sorted in each bucket |
281 | // it is sorted in each bucket |
| 282 | for (i = 0; i < keymap.size (); ++i) |
282 | for (i = 0; i < keymap.size (); ++i) |
| 283 | for (int j = min (keymap [i]->range, KEYSYM_HASH_BUCKETS) - 1; j >= 0; --j) |
283 | for (int j = min (keymap [i]->range, KEYSYM_HASH_BUCKETS) - 1; j >= 0; --j) |
| 284 | { |
284 | { |
| 285 | hashkey = (keymap [i]->keysym + j) & KEYSYM_HASH_MASK; |
285 | hashkey = (keymap [i]->keysym + j) & KEYSYM_HASH_MASK; |
| 286 | |
286 | |
| 287 | index = hash [hashkey] + hash_bucket_counter [hashkey]; |
287 | index = hash [hashkey] + hash_bucket_size [hashkey]; |
| 288 | |
288 | |
| 289 | while (index > hash [hashkey] |
289 | while (index > hash [hashkey] |
| 290 | && compare_priority (keymap [i], sorted_keymap [index - 1]) > 0) |
290 | && compare_priority (keymap [i], sorted_keymap [index - 1]) > 0) |
| 291 | { |
291 | { |
| 292 | sorted_keymap [index] = sorted_keymap [index - 1]; |
292 | sorted_keymap [index] = sorted_keymap [index - 1]; |
| 293 | --index; |
293 | --index; |
| 294 | } |
294 | } |
| 295 | |
295 | |
| 296 | sorted_keymap [index] = keymap [i]; |
296 | sorted_keymap [index] = keymap [i]; |
| 297 | ++hash_bucket_counter [hashkey]; |
297 | ++hash_bucket_size [hashkey]; |
| 298 | } |
298 | } |
| 299 | |
299 | |
| 300 | keymap.swap (sorted_keymap); |
300 | keymap.swap (sorted_keymap); |
| 301 | |
301 | |
| 302 | #ifndef NDEBUG |
302 | #ifndef NDEBUG |
