This is an automated email from the ASF dual-hosted git repository. gnodet pushed a commit to branch spangled-spectrum in repository https://gitbox.apache.org/repos/asf/camel.git
commit f1b440090b883283132d7db7de2e7d11513cc233 Author: Guillaume Nodet <[email protected]> AuthorDate: Thu Jun 4 14:01:42 2026 +0200 CAMEL-XXXXX: Improve CaseInsensitiveMap with O(1) hash table and header key deduplication Co-Authored-By: Claude Opus 4.6 <[email protected]> --- .../impl/engine/DefaultHeadersMapFactory.java | 20 + .../apache/camel/util/CaseInsensitiveMapTest.java | 188 +++++++++ .../org/apache/camel/util/CaseInsensitiveMap.java | 418 ++++++++++++++++++++- 3 files changed, 619 insertions(+), 7 deletions(-) diff --git a/core/camel-base-engine/src/main/java/org/apache/camel/impl/engine/DefaultHeadersMapFactory.java b/core/camel-base-engine/src/main/java/org/apache/camel/impl/engine/DefaultHeadersMapFactory.java index adb863b99900..6b6d60573f9d 100644 --- a/core/camel-base-engine/src/main/java/org/apache/camel/impl/engine/DefaultHeadersMapFactory.java +++ b/core/camel-base-engine/src/main/java/org/apache/camel/impl/engine/DefaultHeadersMapFactory.java @@ -16,8 +16,12 @@ */ package org.apache.camel.impl.engine; +import java.lang.reflect.Field; +import java.util.ArrayList; +import java.util.List; import java.util.Map; +import org.apache.camel.Exchange; import org.apache.camel.spi.HeadersMapFactory; import org.apache.camel.util.CaseInsensitiveMap; @@ -29,6 +33,22 @@ import org.apache.camel.util.CaseInsensitiveMap; */ public class DefaultHeadersMapFactory implements HeadersMapFactory { + static { + List<String> keys = new ArrayList<>(); + for (Field f : Exchange.class.getFields()) { + if (f.getType() == String.class) { + try { + keys.add((String) f.get(null)); + } catch (IllegalAccessException e) { + // ignore + } + } + } + if (!keys.isEmpty()) { + CaseInsensitiveMap.registerKnownKeys(keys); + } + } + @Override public Map<String, Object> newMap() { return new CaseInsensitiveMap(); diff --git a/core/camel-core/src/test/java/org/apache/camel/util/CaseInsensitiveMapTest.java b/core/camel-core/src/test/java/org/apache/camel/util/CaseInsensitiveMapTest.java index 71768207b71b..b5edbdddeba1 100644 --- a/core/camel-core/src/test/java/org/apache/camel/util/CaseInsensitiveMapTest.java +++ b/core/camel-core/src/test/java/org/apache/camel/util/CaseInsensitiveMapTest.java @@ -502,6 +502,194 @@ public class CaseInsensitiveMapTest { service.shutdownNow(); } + @Test + public void testInsertionOrder() { + Map<String, Object> map = new CaseInsensitiveMap(); + map.put("Zebra", 1); + map.put("apple", 2); + map.put("Mango", 3); + + Iterator<Map.Entry<String, Object>> it = map.entrySet().iterator(); + Map.Entry<String, Object> e1 = it.next(); + Map.Entry<String, Object> e2 = it.next(); + Map.Entry<String, Object> e3 = it.next(); + assertFalse(it.hasNext()); + + assertEquals("Zebra", e1.getKey()); + assertEquals(1, e1.getValue()); + assertEquals("apple", e2.getKey()); + assertEquals(2, e2.getValue()); + assertEquals("Mango", e3.getKey()); + assertEquals(3, e3.getValue()); + } + + @Test + public void testIteratorRemove() { + Map<String, Object> map = new CaseInsensitiveMap(); + map.put("Foo", "cheese"); + map.put("Bar", "cake"); + map.put("Baz", "beer"); + + Iterator<Map.Entry<String, Object>> it = map.entrySet().iterator(); + it.next(); // Foo + Map.Entry<String, Object> bar = it.next(); + assertEquals("Bar", bar.getKey()); + it.remove(); + + assertEquals(2, map.size()); + assertFalse(map.containsKey("Bar")); + assertTrue(map.containsKey("Foo")); + assertTrue(map.containsKey("Baz")); + } + + @Test + public void testEntrySetRemove() { + Map<String, Object> map = new CaseInsensitiveMap(); + map.put("Foo", "cheese"); + map.put("Bar", "cake"); + + // case-insensitive key match + value match → removes + boolean removed = map.entrySet().remove(Map.entry("foo", "cheese")); + assertTrue(removed); + assertEquals(1, map.size()); + assertFalse(map.containsKey("Foo")); + + // wrong value → does not remove + boolean notRemoved = map.entrySet().remove(Map.entry("bar", "wrong")); + assertFalse(notRemoved); + assertEquals(1, map.size()); + } + + @Test + public void testEntrySetValue() { + Map<String, Object> map = new CaseInsensitiveMap(); + map.put("Foo", "cheese"); + + Map.Entry<String, Object> entry = map.entrySet().iterator().next(); + assertEquals("cheese", entry.getValue()); + + Object old = entry.setValue("cake"); + assertEquals("cheese", old); + assertEquals("cake", entry.getValue()); + assertEquals("cake", map.get("Foo")); + } + + @Test + public void testRemoveThenReput() { + Map<String, Object> map = new CaseInsensitiveMap(); + map.put("Foo", "cheese"); + map.remove("foo"); + assertTrue(map.isEmpty()); + + map.put("FOO", "cake"); + assertEquals(1, map.size()); + assertEquals("cake", map.get("foo")); + + // new key case should be used since old entry was removed + Map<String, Object> copy = new HashMap<>(map); + assertTrue(copy.containsKey("FOO")); + assertFalse(copy.containsKey("Foo")); + } + + @Test + public void testResize() { + Map<String, Object> map = new CaseInsensitiveMap(); + for (int i = 0; i < 200; i++) { + map.put("key" + i, i); + } + assertEquals(200, map.size()); + + for (int i = 0; i < 200; i++) { + assertTrue(map.containsKey("KEY" + i)); + assertEquals(i, map.get("key" + i)); + } + + // remove half and verify + for (int i = 0; i < 100; i++) { + map.remove("Key" + i); + } + assertEquals(100, map.size()); + + for (int i = 100; i < 200; i++) { + assertEquals(i, map.get("KEY" + i)); + } + } + + @Test + public void testContainsValue() { + Map<String, Object> map = new CaseInsensitiveMap(); + map.put("foo", "cheese"); + map.put("bar", null); + + assertTrue(map.containsValue("cheese")); + assertTrue(map.containsValue(null)); + assertFalse(map.containsValue("missing")); + } + + @Test + public void testNullValue() { + Map<String, Object> map = new CaseInsensitiveMap(); + map.put("foo", null); + + assertEquals(1, map.size()); + assertTrue(map.containsKey("FOO")); + assertNull(map.get("foo")); + + // distinguish null value from missing key + assertTrue(map.containsKey("foo")); + assertFalse(map.containsKey("bar")); + } + + @Test + public void testClearAndReuse() { + Map<String, Object> map = new CaseInsensitiveMap(); + map.put("Foo", "cheese"); + map.put("Bar", "cake"); + assertEquals(2, map.size()); + + map.clear(); + assertEquals(0, map.size()); + assertTrue(map.isEmpty()); + assertFalse(map.containsKey("Foo")); + + // reuse after clear + map.put("Baz", "beer"); + assertEquals(1, map.size()); + assertEquals("beer", map.get("BAZ")); + } + + @Test + public void testKnownKeyDeduplication() { + // Register known keys + CaseInsensitiveMap.registerKnownKeys(List.of("CamelCharsetName", "CamelExchangeId", "breadcrumbId")); + + Map<String, Object> map = new CaseInsensitiveMap(); + + // simulate deserialized key (new String to guarantee a different object) + String deserializedKey = new String("CamelCharsetName"); + map.put(deserializedKey, "UTF-8"); + + // the stored key should be the canonical reference, not the deserialized copy + Map.Entry<String, Object> entry = map.entrySet().iterator().next(); + assertSame("CamelCharsetName", entry.getKey()); + assertNotSame(deserializedKey, entry.getKey()); + + // case-insensitive dedup: different case should still map to canonical + Map<String, Object> map2 = new CaseInsensitiveMap(); + map2.put("camelcharsetname", "UTF-8"); + Map.Entry<String, Object> entry2 = map2.entrySet().iterator().next(); + assertSame("CamelCharsetName", entry2.getKey()); + + // non-registered key is stored as-is + String custom = new String("CustomHeader"); + map.put(custom, "value"); + for (Map.Entry<String, Object> e : map.entrySet()) { + if (e.getValue().equals("value")) { + assertSame(custom, e.getKey()); + } + } + } + @Disabled("Manual test") @Test public void testCopyMapWithCamelHeadersTest() throws Exception { diff --git a/core/camel-util/src/main/java/org/apache/camel/util/CaseInsensitiveMap.java b/core/camel-util/src/main/java/org/apache/camel/util/CaseInsensitiveMap.java index 92155488e967..7f0cbe5f35e2 100644 --- a/core/camel-util/src/main/java/org/apache/camel/util/CaseInsensitiveMap.java +++ b/core/camel-util/src/main/java/org/apache/camel/util/CaseInsensitiveMap.java @@ -16,31 +16,435 @@ */ package org.apache.camel.util; +import java.io.IOException; +import java.io.ObjectInputStream; +import java.io.ObjectOutputStream; import java.io.Serial; +import java.io.Serializable; +import java.util.AbstractMap; +import java.util.AbstractSet; +import java.util.Arrays; +import java.util.Collection; +import java.util.Iterator; import java.util.Map; -import java.util.TreeMap; +import java.util.NoSuchElementException; +import java.util.Objects; +import java.util.Set; /** * A map that uses case insensitive keys, but preserves the original key cases. * <p/> - * The map is based on {@link TreeMap} and therefore uses O(n) for lookup and not O(1) as a {@link java.util.HashMap} - * does. + * The map uses a custom hash table with case-insensitive hashing and comparison, providing O(1) for {@code get}, + * {@code put}, {@code containsKey} and {@code remove} operations without allocating temporary strings. Entries are + * stored in insertion order. * <p/> * This map is <b>not</b> designed to be thread safe as concurrent access to it is not supposed to be performed by the * Camel routing engine. */ -public class CaseInsensitiveMap extends TreeMap<String, Object> { +public class CaseInsensitiveMap extends AbstractMap<String, Object> implements Serializable { private static final @Serial long serialVersionUID = -8538318195477618308L; + private static final int DEFAULT_CAPACITY = 16; + private static final float LOAD_FACTOR = 0.75f; + private static final int EMPTY = -1; + + // Static lookup table for deduplicating well-known header keys (e.g. Exchange constants). + // Registered once at startup; read-only after that. Zero-allocation lookups. + private static volatile int[] knownTable; + private static volatile String[] knownEntries; + private static volatile int[] knownChainNext; + private static volatile int knownMask; + + /** + * Registers a set of well-known header key strings for deduplication. When a key passed to {@link #put} matches one + * of these strings (case-insensitive), the canonical reference from this set is stored instead of the caller's + * string, reducing memory when many map instances carry the same headers (e.g. deserialized exchanges). + * <p/> + * This method is intended to be called once during framework startup. + */ + public static void registerKnownKeys(Collection<String> keys) { + int sz = keys.size(); + int tableSize = tableSizeFor(Math.max((int) (sz / LOAD_FACTOR) + 1, DEFAULT_CAPACITY)); + int mask = tableSize - 1; + int[] tbl = new int[tableSize]; + Arrays.fill(tbl, EMPTY); + String[] entries = keys.toArray(new String[0]); + int[] chain = new int[entries.length]; + + for (int i = 0; i < entries.length; i++) { + int b = caseInsensitiveHash(entries[i]) & mask; + chain[i] = tbl[b]; + tbl[b] = i; + } + + knownEntries = entries; + knownChainNext = chain; + knownMask = mask; + // assign table last — readers check knownTable != null as the gate + knownTable = tbl; + } + + private static String deduplicateKey(String key) { + int[] tbl = knownTable; + if (tbl == null) { + return key; + } + int idx = tbl[caseInsensitiveHash(key) & knownMask]; + while (idx != EMPTY) { + if (knownEntries[idx].equalsIgnoreCase(key)) { + return knownEntries[idx]; + } + idx = knownChainNext[idx]; + } + return key; + } + + private transient int[] table; + private transient String[] keys; + private transient Object[] values; + private transient int[] chainNext; + + private transient int size; + private transient int usedSlots; + private transient int threshold; public CaseInsensitiveMap() { - super(String.CASE_INSENSITIVE_ORDER); + init(DEFAULT_CAPACITY); } public CaseInsensitiveMap(Map<? extends String, ?> map) { - // must use the insensitive order - super(String.CASE_INSENSITIVE_ORDER); + init(tableSizeFor(Math.max((int) (map.size() / LOAD_FACTOR) + 1, DEFAULT_CAPACITY))); putAll(map); } + private void init(int tableCapacity) { + table = new int[tableCapacity]; + Arrays.fill(table, EMPTY); + int entryCapacity = (int) (tableCapacity * LOAD_FACTOR) + 1; + keys = new String[entryCapacity]; + values = new Object[entryCapacity]; + chainNext = new int[entryCapacity]; + size = 0; + usedSlots = 0; + threshold = (int) (tableCapacity * LOAD_FACTOR); + } + + private static int tableSizeFor(int cap) { + int n = cap - 1; + n |= n >>> 1; + n |= n >>> 2; + n |= n >>> 4; + n |= n >>> 8; + n |= n >>> 16; + return Math.max(DEFAULT_CAPACITY, n + 1); + } + + static int caseInsensitiveHash(String key) { + int h = 0; + for (int i = 0, len = key.length(); i < len; i++) { + // two-step fold matches String.equalsIgnoreCase / CASE_INSENSITIVE_ORDER + h = 31 * h + Character.toLowerCase(Character.toUpperCase(key.charAt(i))); + } + return h ^ (h >>> 16); + } + + private int bucketIndex(String key) { + return caseInsensitiveHash(key) & (table.length - 1); + } + + private int findIndex(String key) { + int idx = table[bucketIndex(key)]; + while (idx != EMPTY) { + if (keys[idx].equalsIgnoreCase(key)) { + return idx; + } + idx = chainNext[idx]; + } + return EMPTY; + } + + @Override + public Object get(Object key) { + int idx = findIndex((String) key); + return idx != EMPTY ? values[idx] : null; + } + + @Override + public boolean containsKey(Object key) { + return findIndex((String) key) != EMPTY; + } + + @Override + public boolean containsValue(Object value) { + for (int i = 0; i < usedSlots; i++) { + if (keys[i] != null && Objects.equals(value, values[i])) { + return true; + } + } + return false; + } + + @Override + public Object put(String key, Object value) { + key = deduplicateKey(key); + int idx = findIndex(key); + if (idx != EMPTY) { + Object old = values[idx]; + values[idx] = value; + return old; + } + if (size >= threshold) { + resize(table.length * 2); + } + if (usedSlots >= keys.length) { + int newCap = keys.length + (keys.length >> 1); + keys = Arrays.copyOf(keys, newCap); + values = Arrays.copyOf(values, newCap); + chainNext = Arrays.copyOf(chainNext, newCap); + } + int slot = usedSlots++; + keys[slot] = key; + values[slot] = value; + int b = bucketIndex(key); + chainNext[slot] = table[b]; + table[b] = slot; + size++; + return null; + } + + @Override + public Object remove(Object key) { + int idx = findIndex((String) key); + if (idx != EMPTY) { + Object old = values[idx]; + removeByIndex(idx); + return old; + } + return null; + } + + private void removeByIndex(int idx) { + String key = keys[idx]; + int b = bucketIndex(key); + int prev = EMPTY; + int cur = table[b]; + while (cur != EMPTY) { + if (cur == idx) { + if (prev == EMPTY) { + table[b] = chainNext[idx]; + } else { + chainNext[prev] = chainNext[idx]; + } + break; + } + prev = cur; + cur = chainNext[cur]; + } + keys[idx] = null; + values[idx] = null; + size--; + } + + private void resize(int newTableCapacity) { + int[] newTable = new int[newTableCapacity]; + Arrays.fill(newTable, EMPTY); + int entryCap = Math.max((int) (newTableCapacity * LOAD_FACTOR) + 1, size + 1); + String[] newKeys = new String[entryCap]; + Object[] newValues = new Object[entryCap]; + int[] newChainNext = new int[entryCap]; + + int newSlot = 0; + for (int i = 0; i < usedSlots; i++) { + if (keys[i] != null) { + newKeys[newSlot] = keys[i]; + newValues[newSlot] = values[i]; + int b = caseInsensitiveHash(keys[i]) & (newTableCapacity - 1); + newChainNext[newSlot] = newTable[b]; + newTable[b] = newSlot; + newSlot++; + } + } + + table = newTable; + keys = newKeys; + values = newValues; + chainNext = newChainNext; + usedSlots = newSlot; + threshold = (int) (newTableCapacity * LOAD_FACTOR); + } + + @Override + public int size() { + return size; + } + + @Override + public boolean isEmpty() { + return size == 0; + } + + @Override + public void clear() { + Arrays.fill(table, EMPTY); + Arrays.fill(keys, 0, usedSlots, null); + Arrays.fill(values, 0, usedSlots, null); + size = 0; + usedSlots = 0; + } + + @Override + public void putAll(Map<? extends String, ?> m) { + for (Entry<? extends String, ?> entry : m.entrySet()) { + put(entry.getKey(), entry.getValue()); + } + } + + @Override + public Set<Entry<String, Object>> entrySet() { + return new EntrySet(); + } + + private final class EntrySet extends AbstractSet<Entry<String, Object>> { + @Override + public int size() { + return size; + } + + @Override + public boolean contains(Object o) { + if (!(o instanceof Entry<?, ?> e)) { + return false; + } + int idx = findIndex((String) e.getKey()); + return idx != EMPTY && Objects.equals(values[idx], e.getValue()); + } + + @Override + public boolean remove(Object o) { + if (!(o instanceof Entry<?, ?> e)) { + return false; + } + int idx = findIndex((String) e.getKey()); + if (idx != EMPTY && Objects.equals(values[idx], e.getValue())) { + removeByIndex(idx); + return true; + } + return false; + } + + @Override + public void clear() { + CaseInsensitiveMap.this.clear(); + } + + @Override + public Iterator<Entry<String, Object>> iterator() { + return new EntryIterator(); + } + } + + private final class EntryIterator implements Iterator<Entry<String, Object>> { + private int cursor; + private int lastReturned = EMPTY; + + EntryIterator() { + cursor = advance(0); + } + + private int advance(int from) { + for (int i = from; i < usedSlots; i++) { + if (keys[i] != null) { + return i; + } + } + return EMPTY; + } + + @Override + public boolean hasNext() { + return cursor != EMPTY; + } + + @Override + public Entry<String, Object> next() { + if (cursor == EMPTY) { + throw new NoSuchElementException(); + } + lastReturned = cursor; + cursor = advance(cursor + 1); + return new MapEntry(lastReturned); + } + + @Override + public void remove() { + if (lastReturned == EMPTY) { + throw new IllegalStateException(); + } + removeByIndex(lastReturned); + lastReturned = EMPTY; + } + } + + private final class MapEntry implements Entry<String, Object> { + private final int index; + + MapEntry(int index) { + this.index = index; + } + + @Override + public String getKey() { + return keys[index]; + } + + @Override + public Object getValue() { + return values[index]; + } + + @Override + public Object setValue(Object value) { + Object old = values[index]; + values[index] = value; + return old; + } + + @Override + public boolean equals(Object o) { + if (!(o instanceof Entry<?, ?> e)) { + return false; + } + return keys[index].equals(e.getKey()) && Objects.equals(values[index], e.getValue()); + } + + @Override + public int hashCode() { + return keys[index].hashCode() ^ Objects.hashCode(values[index]); + } + } + + @Serial + private void writeObject(ObjectOutputStream out) throws IOException { + out.defaultWriteObject(); + out.writeInt(size); + for (int i = 0; i < usedSlots; i++) { + if (keys[i] != null) { + out.writeObject(keys[i]); + out.writeObject(values[i]); + } + } + } + + @Serial + private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { + in.defaultReadObject(); + int count = in.readInt(); + init(tableSizeFor(Math.max((int) (count / LOAD_FACTOR) + 1, DEFAULT_CAPACITY))); + for (int i = 0; i < count; i++) { + String key = (String) in.readObject(); + Object value = in.readObject(); + put(key, value); + } + } + }
