# UNDF: UNDF-2026-000000415
# hazelcast-0001 — QueueContainer.compareAndRemove() O(Q×D) membership test

## Classification

| Field | Value |
|-------|-------|
| CWE | CWE-407: Algorithmic Complexity — Linear Membership Test in Outer Loop |
| Severity | HIGH |
| Component | `hazelcast/src/main/java/com/hazelcast/collection/impl/queue/QueueContainer.java` |
| Method | `compareAndRemove(Collection<Data> dataList, boolean retain)` |
| Lines | 801–820 |
| Public API | `IQueue.removeAll(Collection)` / `IQueue.retainAll(Collection)` |

## Defective Code

```java
// QueueContainer.java:801-820
public Map<Long, Data> compareAndRemove(Collection<Data> dataList, boolean retain) {
    LinkedHashMap<Long, Data> map = new LinkedHashMap<>();
    for (QueueItem item : getItemQueue()) {           // O(Q) outer loop
        if (item.getSerializedObject() == null && store.isEnabled()) {
            ...load(item)...
        }
        boolean contains = dataList.contains(item.getSerializedObject()); // O(D) per item
        if ((retain && !contains) || (!retain && contains)) {
            map.put(item.getItemId(), item.getSerializedObject());
        }
    }
    mapIterateAndRemove(map);
    return map;
}
```

`dataList` is always constructed as an `ArrayList<Data>` by `QueueProxyImpl.getDataList()`.
`getItemQueue()` returns a `LinkedList<QueueItem>` (or `PriorityQueue`).

## Root Cause

`ArrayList.contains()` is O(D) — it performs a linear scan.  Called inside an O(Q) outer
loop over every queue item, total cost is **O(Q × D)**.

With a large distributed queue (Q = 100 000 items) and a removal batch (D = 1 000 elements),
this is 100 million comparisons instead of 100 001.

## Fix

Pre-build a `HashSet<Data>` from `dataList` before the outer loop.

```java
public Map<Long, Data> compareAndRemove(Collection<Data> dataList, boolean retain) {
    Set<Data> dataSet = new HashSet<>(dataList);          // O(D) one-time setup
    LinkedHashMap<Long, Data> map = new LinkedHashMap<>();
    for (QueueItem item : getItemQueue()) {               // O(Q)
        if (item.getSerializedObject() == null && store.isEnabled()) {
            ...load(item)...
        }
        boolean contains = dataSet.contains(item.getSerializedObject()); // O(1)
        if ((retain && !contains) || (!retain && contains)) {
            map.put(item.getItemId(), item.getSerializedObject());
        }
    }
    mapIterateAndRemove(map);
    return map;
}
```

## Complexity

| | Before | After |
|-|--------|-------|
| `compareAndRemove` | O(Q × D) | O(Q + D) |
| `IQueue.removeAll(D items)` on Q-item queue | O(Q × D) | O(Q + D) |
| `IQueue.retainAll(D items)` on Q-item queue | O(Q × D) | O(Q + D) |

## Speedup Estimate

At Q = 1 000, D = 1 000 (all-distinct): **~500× fewer comparisons**.
At Q = 10 000, D = 500: **~250× fewer comparisons**.
