fd_set–style bit tracker for multiplexed I/O

Challenge

Build a fixed-capacity set of file-descriptor numbers backed by a bitmap — the same idea as select(2)'s fd_set.

Task

Implement this small API, where each fd is one bit in an array of 32-bit words:

typedef struct fdset fdset_t;
fdset_t *fdset_create(int max_fd);   /* tracks fds 0..max_fd inclusive */
void     fdset_add(fdset_t *s, int fd);
void     fdset_remove(fdset_t *s, int fd);
int      fdset_contains(fdset_t *s, int fd);   /* 1 if present, else 0 */
int      fdset_count(fdset_t *s);              /* number of fds currently set */
void     fdset_destroy(fdset_t *s);

Input

• max_fd: the largest fd the set must hold (>= 0); the set covers 0..max_fd.
• fd: a file-descriptor number passed to add/remove/contains.

Output

• fdset_contains returns 1 if fd is in the set, else 0.
• fdset_count returns how many fds are currently set.

Example

s = fdset_create(63)
add 0, 5, 31, 32, 63   -> count == 5, contains(5) == 1, contains(6) == 0
remove 5               -> contains(5) == 0, count == 4
add 0 again            -> count stays 4   (idempotent)
add 999 (out of range) -> count stays 4   (ignored)

Edge cases

• Adding the same fd twice counts it once.
• Removing an fd that isn't present is a no-op.
• An out-of-range fd (negative or > max_fd) is a no-op for add/remove and returns 0 for contains.

Rules

• Pack 32 fds per uint32_t; size the array as (max_fd / 32) + 1 words.
• add/remove/contains are pure bit math (no looping over the words).

Why this matters

select(2) uses an fd_set — a bitmap of file descriptor numbers. Implementing it teaches bitmap math and why epoll superseded select for high-FD-count servers.

Input format

max_fd (>=0): largest fd the set holds; fd: an int passed to add/remove/contains.

Output format

fdset_contains returns 1/0; fdset_count returns the number of fds set.

Constraints

Use (max_fd / 32) + 1 words; add/remove/contains are O(1) bit math; out-of-range fds are ignored.

Starter code

typedef struct fdset fdset_t;
fdset_t *fdset_create(int max_fd);
void     fdset_add(fdset_t *s, int fd);
void     fdset_remove(fdset_t *s, int fd);
int      fdset_contains(fdset_t *s, int fd);
int      fdset_count(fdset_t *s);
void     fdset_destroy(fdset_t *s);

Common mistakes

Indexing past the bitmap on a large fd; using a signed type so the high bit shifts wrong; double-counting in count via a manual popcount with mismatched mask.

Edge cases to handle

add same fd twice — still counted once. remove of absent fd — no-op.

Complexity

O(1) add/remove/contains. O(words) count.

Background lessons

• Bitwise operations