[PATCH 2/4] xkbsupport: Create a list of used codes

This is preparation with the following changes. We create a binary
search tree with all the unicodes that are used in the generated keymap
so that we can later check whether the unicode symbol is used or not.

Signed-off-by: Alexey Gladkov <[email protected]>
---
 src/xkbsupport.c | 50 +++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 47 insertions(+), 3 deletions(-)

diff --git a/src/xkbsupport.c b/src/xkbsupport.c
index 694d516f..3caf8465 100644
--- a/src/xkbsupport.c
+++ b/src/xkbsupport.c
@@ -1,3 +1,6 @@
+#define _GNU_SOURCE
+#include <search.h>
+
 #include <stdlib.h>
 #include <string.h>
 #include <errno.h>
@@ -37,6 +40,7 @@ struct xkeymap {
 	struct xkb_context *xkb;
 	struct xkb_keymap *keymap;
 	struct lk_ctx *ctx;
+	void *used_codes;
 };
 
 /*
@@ -171,6 +175,15 @@ static const char *map_xkbsym_to_ksym(const char *xkb_sym)
 	return NULL;
 }
 
+static int compare_codes(const void *pa, const void *pb)
+{
+	if (*(int *) pa < *(int *) pb)
+		return -1;
+	if (*(int *) pa > *(int *) pb)
+		return 1;
+	return 0;
+}
+
 static void print_modifiers(struct xkb_keymap *keymap, struct xkb_mask *mask)
 {
 	xkb_mod_index_t num_mods = xkb_keymap_num_mods(keymap);
@@ -351,6 +364,32 @@ static int xkeymap_get_symbol(struct xkb_keymap *keymap,
 	return 1;
 }
 
+static int used_code(struct xkeymap *xkeymap, int code)
+{
+	return tfind(&code, &xkeymap->used_codes, compare_codes) != NULL;
+}
+
+static void remember_code(struct xkeymap *xkeymap, int code)
+{
+	int *ptr, **val;
+
+	if (used_code(xkeymap, code))
+		return;
+
+	ptr = malloc(sizeof(code));
+	if (!ptr)
+		kbd_error(1, errno, "out of memory");
+
+	*ptr = code;
+
+	val = tsearch(ptr, &xkeymap->used_codes, compare_codes);
+	if (!val)
+		kbd_error(1, errno, "out of memory");
+
+	if (*val != ptr)
+		free(ptr);
+}
+
 static void xkeymap_add_value(struct xkeymap *xkeymap, int modifier, int code, int keyvalue[MAX_NR_KEYMAPS])
 {
 	if (!modifier || (modifier & (1 << KG_SHIFT)))
@@ -438,9 +477,6 @@ static int xkeymap_walk(struct xkeymap *xkeymap)
 			}
 		}
 
-		if (getenv("LK_XKB_DEBUG"))
-			continue;
-
 process_keycode:
 		unsigned short layout = 0;
 
@@ -455,6 +491,11 @@ process_keycode:
 					keyvalue[i] = keyvalue[layout_switch[layout]];
 			}
 
+			remember_code(xkeymap, keyvalue[i]);
+
+			if (getenv("LK_XKB_DEBUG"))
+				continue;
+
 			if (lk_add_key(xkeymap->ctx, i, (int) KERN_KEYCODE(keycode), keyvalue[i]) < 0)
 				goto err;
 		}
@@ -506,6 +547,9 @@ int convert_xkb_keymap(struct lk_ctx *ctx, struct xkeymap_params *params, int op
 	}
 
 end:
+	if (xkeymap.used_codes)
+		tdestroy(xkeymap.used_codes, free);
+
 	xkb_keymap_unref(xkeymap.keymap);
 	xkb_context_unref(xkeymap.xkb);
 
-- 
2.43.0