>From 5f40331ab8674bd52e27a241906b28dcdfeadc28 Mon Sep 17 00:00:00 2001
From: Rich Felker <dalias@aerifal.cx>
Date: Sat, 12 Sep 2026 18:02:56 -0400
Subject: [PATCH 03/18] add integer-keyed multi-level table lookup for new
 locale support

these functions perform a single-key or key-path lookup on an
in-memory table format designed to be practical for compile-time
construction using the C preprocessor (for built-in C locale data) and
for generation by locale tooling to produce files for mmap.
---
 src/internal/ikmlt.c | 55 ++++++++++++++++++++++++++++++++++++++++++++
 src/internal/ikmlt.h | 12 ++++++++++
 2 files changed, 67 insertions(+)
 create mode 100644 src/internal/ikmlt.c
 create mode 100644 src/internal/ikmlt.h

diff --git a/src/internal/ikmlt.c b/src/internal/ikmlt.c
new file mode 100644
index 00000000..c6e5c8ce
--- /dev/null
+++ b/src/internal/ikmlt.c
@@ -0,0 +1,55 @@
+#include "ikmlt.h"
+
+/* lookups for our integer-keyed multi-level table format supporting both
+ * explicit subtables (walked by caller intent) and subdivision levels
+ * defined by the data for representing large/sparse key spaces. */
+
+
+/* ikmlt_lookup takes a pointer to the starting table and a single
+ * integer key value and returns a pointer to the associated data
+ * which the caller is responsible for interpreting.
+ *
+ * if the table is flat (top-level shift is 0), this is just looking
+ * up an offset in an array for in-range key values and rejecting
+ * out-of-range keys. but if the table is subdivided (nonzero shift),
+ * (key-start)>>shift indexes the first level, and the remaining low
+ * bits of key-start index a subtable found at the resulting offset.
+ * this process continues iteratively until the key is rejected as
+ * out-of-range or a table with zero shift is reached. */
+
+const void *ikmlt_lookup(const unsigned char *ld, int key)
+{
+	unsigned start, shift, scale, cnt, val, x, k = key;
+
+	do {
+		start = (unsigned)ld[0]<<24 | ld[1]<<16 | ld[2]<<8 | ld[3];
+		k -= start;
+		shift = ld[4] & 31;
+		scale = ld[5] & 3;
+
+		cnt = (ld[6]<<8 | ld[7]) + 1;
+		x = k>>shift;
+		k &= (1U<<shift) - 1;
+		if (x >= cnt) return 0;
+		x <<= scale;
+
+		ld += 8;
+		for (int i=val=0; i<(1U<<scale); i++)
+			val = 256*val + ld[x+i];
+		if (!val) return 0;
+		ld += (cnt<<scale) + val-1;
+	} while (shift);
+
+	return ld;
+}
+
+
+/* ikmlt_lookup_path takes a path of keys (first element of path is
+ * the number of components) starting from the tabel ld and traversing
+ * explicit subtables until the final path component is reached. */
+
+const void *ikmlt_lookup_path(const unsigned char *ld, const int *path)
+{
+	for (int i=0; i<path[0] && ld; i++, ld=ikmlt_lookup(ld, path[i+1]));
+	return ld;
+}
diff --git a/src/internal/ikmlt.h b/src/internal/ikmlt.h
new file mode 100644
index 00000000..98b7fc5c
--- /dev/null
+++ b/src/internal/ikmlt.h
@@ -0,0 +1,12 @@
+#ifndef IKMLT_H
+#define IKMLT_H
+
+#include <features.h>
+
+#define ikmlt_lookup __ikmlt_lookup
+#define ikmlt_lookup_path __ikmlt_lookup_path
+
+hidden const void *ikmlt_lookup(const unsigned char *, int);
+hidden const void *ikmlt_lookup_path(const unsigned char *, const int *);
+
+#endif
-- 
2.21.0