# UNDF: UNDF-2026-000000582
# curl-0002: Curl_checkheaders O(K×H) per request → O(H) setup + O(1) per lookup

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | MEDIUM |
| Component   | `lib/transfer.c:85`, `lib/http.c` (22 call sites) |
| Function    | `Curl_checkheaders` called K≈20 times per request |
| Hot path    | Every HTTP/RTSP request with custom headers set |
| Status      | PATCHED (unit test PASS) |

## Defect

`Curl_checkheaders` performs a full O(H) linear scan of the user's `curl_slist` of
custom headers on every call. It is called approximately **20 times per HTTP request**
in `http.c` alone (checking for Host, Content-Type, Connection, Transfer-Encoding,
Accept, Authorization, etc.), plus 12 more times across `rtsp.c`, `smtp.c`, `imap.c`.

```c
// lib/transfer.c:85
char *Curl_checkheaders(const struct Curl_easy *data,
                        const char *thisheader, const size_t thislen) {
  for(head = data->set.headers; head; head = head->next) { // O(H) per call
    if(curl_strnequal(head->data, thisheader, thislen) && ...)
      return head->data;
  }
  return NULL;
}
```

With H=500 custom headers and K=20 calls per request: **10,000 string comparisons per
request**, repeated on every request in a transfer loop.

## Fix

Build a case-insensitive `HashMap<header_name, slist_node>` once when headers are set
via `CURLOPT_HTTPHEADER`, rebuild on modification. Each `Curl_checkheaders` call
becomes an O(1) hash lookup:

```c
// At curl_easy_setopt(CURLOPT_HTTPHEADER):
// rebuild data->set.headers_map from data->set.headers slist — O(H)

// Curl_checkheaders replacement:
struct curl_slist *found = Curl_hashmap_get_icase(data->set.headers_map,
                                                   thisheader, thislen);
return found ? found->data : NULL;
```

Speedup: ~500× at H=500 (20 × 500 = 10,000 → 20 × 1 = 20 effective ops).