Message Queue Partitioning Problem #11

New Issue

deeaitch · 2026-07-27T19:31:49-04:00

deeaitch commented

2026-07-27 19:31:49 -04:00

Analysis #05 — Message Queue Partitioning

Problem

A communication subsystem maintains a singly linked intrusive queue of outgoing messages.

Each message contains a transmission identifier, a retry flag, and a pointer to the next message:

struct Message
{
    uint32_t id;
    bool retry;
    Message* next;
};

After a transmission attempt, some messages may need to be retried.

Partition the original queue into two separate queues:

the ready queue, containing messages that do not require another transmission attempt;
the retry queue, containing messages marked for retry.

The relative order of messages must be preserved in both queues.

Requirements

no dynamic memory allocation;
no copying of messages;
reuse the existing list nodes;
preserve the original order in both resulting queues;
process the queue in O(n) time.

Example

Input

A -> B -> C -> D

Message state:

A: retry = false
B: retry = true
C: retry = false
D: retry = true

Result

Ready queue:

A -> C

Retry queue:

B -> D

The original queue is consumed during the operation, and every message must belong to exactly one of the two resulting queues.

# Analysis #05 — Message Queue Partitioning ## Problem A communication subsystem maintains a singly linked intrusive queue of outgoing messages. Each message contains a transmission identifier, a retry flag, and a pointer to the next message: ```cpp struct Message { uint32_t id; bool retry; Message* next; }; ``` After a transmission attempt, some messages may need to be retried. Partition the original queue into two separate queues: * the **ready queue**, containing messages that do not require another transmission attempt; * the **retry queue**, containing messages marked for retry. The relative order of messages must be preserved in both queues. ### Requirements * no dynamic memory allocation; * no copying of messages; * reuse the existing list nodes; * preserve the original order in both resulting queues; * process the queue in `O(n)` time. ## Example ### Input ```text A -> B -> C -> D ``` Message state: ```text A: retry = false B: retry = true C: retry = false D: retry = true ``` ### Result Ready queue: ```text A -> C ``` Retry queue: ```text B -> D ``` The original queue is consumed during the operation, and every message must belong to exactly one of the two resulting queues.

deeaitch referenced this issue from a commit

2026-07-27 19:47:14 -04:00

Closes #11

deeaitch closed this issue

2026-07-27 19:47:15 -04:00

deeaitch referenced this issue from a commit

2026-07-27 20:11:34 -04:00

Ref #11 added some UML

deeaitch referenced this issue from a commit

2026-07-27 23:35:32 -04:00

Ref #11 fixed iteration file name

Sign in to join this conversation.