# UNDF: UNDF-2026-000000487
# opensearch-005: IndexGraveyard.containsIndex O(n²) List scan in DanglingIndicesState loop

## Classification
- **CWE**: CWE-407 (Inefficient Algorithmic Complexity)
- **Severity**: MEDIUM
- **Path**: Node startup and periodic dangling-index detection

## Location
`server/src/main/java/org/opensearch/cluster/metadata/IndexGraveyard.java:139`
`server/src/main/java/org/opensearch/gateway/DanglingIndicesState.java:204`

## Defect

Fork of the same defect as elasticsearch-004. OpenSearch inherits the identical pattern:

```java
// IndexGraveyard.java
private final List<Tombstone> tombstones;   // up to 500 tombstones

public boolean containsIndex(final Index index) {
    for (Tombstone tombstone : tombstones) {   // O(T) — linear scan
        if (tombstone.getIndex().equals(index)) {
            return true;
        }
    }
    return false;
}

// DanglingIndicesState.java — findNewDanglingIndices()
final IndexGraveyard graveyard = metadata.indexGraveyard();

for (IndexMetadata indexMetadata : indexMetadataList) {    // O(I)
    Index index = indexMetadata.getIndex();
    if (graveyard.containsIndex(index) == false) {         // O(T) per call
        newIndices.put(index, stripAliases(indexMetadata));
    }
}
```

Additionally, `findNewAndAddDanglingIndices` uses:
```java
danglingIndices.keySet().removeIf(graveyard::containsIndex);  // O(D × T)
```
where D = currently tracked dangling indices.

**Total complexity:** O(I × T + D × T) where T = tombstone count (max 500).

## Fix

Pre-build a `HashSet<Index>` once per call:

```java
Set<Index> graveyardSet = new HashSet<>();
for (Tombstone t : graveyard.getTombstones()) {
    graveyardSet.add(t.getIndex());
}

for (IndexMetadata indexMetadata : indexMetadataList) {
    Index index = indexMetadata.getIndex();
    if (graveyardSet.contains(index) == false) {      // O(1)
        newIndices.put(index, stripAliases(indexMetadata));
    }
}
```

**Result:** O(I + T) — linear rather than quadratic.
