# UNDF: UNDF-2026-000000590
# libevent-0001: evhttp_dispatch_callback O(C) per request → O(1) with URI hash map

## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | MEDIUM |
| Component   | `http.c:3697` (`evhttp_dispatch_callback`), `http.c:4290` (`evhttp_set_cb`) |
| Hot path    | Every incoming HTTP request — route dispatch |
| Status      | PATCHED (unit test PASS) |

## Defect

`evhttp_dispatch_callback` scans the entire `httpcbq` TAILQ on every incoming request
to find the matching route handler:

```c
// http.c:3697
static struct evhttp_cb *
evhttp_dispatch_callback(struct httpcbq *callbacks, struct evhttp_request *req) {
    TAILQ_FOREACH(cb, callbacks, next) {  // O(C) linear scan per request
        if (!strcmp(cb->what, translated))
            return cb;
    }
    return NULL;
}
```

Called from `evhttp_handle_request` (line 3857) on every incoming request. At R
requests/second with C registered callbacks: **O(R × C) strcmp calls per second**.

**Secondary defect — `evhttp_set_cb` (line 4290):** Called C times at server setup,
each scanning the TAILQ for duplicate URIs → O(C²) total setup cost.

## Fix

Replace the `TAILQ httpcbq` with a hash table keyed on URI string:

```c
// Server struct: add
struct evkeyvalht *callback_map;   // hash map: uri → evhttp_cb*

// evhttp_set_cb: O(1) insert after O(1) dup check
// evhttp_dispatch_callback: O(1) lookup
struct evhttp_cb *
evhttp_dispatch_callback(struct httpcbq *callbacks, struct evhttp_request *req) {
    return evkeyvalht_find(callbacks->map, translated);
}
```

Retain the TAILQ for ordered iteration (e.g., `evhttp_del_cb`), but use the hash map
for the hot dispatch path.

Speedup: ~100× at C=100 callbacks.
