Wikipedia says
unlike the older system calls, which operate at O(n), epoll operates in O(1) [2]).
http://en.wikipedia.org/wiki/Epoll
However, the source code at fs/eventpoll.c on Linux-2.6.38, seems it is implemented with an RB tree for searching, which has O(logN)
/*
* Search the file inside the eventpoll tree. The RB tree operations
* are protected by the "mtx" mutex, and ep_find() must be called with
* "mtx" held.
*/
static struct epitem *ep_find(struct eventpoll *ep, struct file *file, int fd)
{
In fact, I couldn't see any man page saying the complexity of epoll() is O(1). Why is it known as O(1)?