… | |
… | |
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 |